AncomWiki

최소 일관 부분집합 커버 문제 (MCSC): 데이터 마이닝의 최소화 관점

Properties1
description본 논문은 데이터 마이닝 작업을 '최소 일관 부분집합 커버(MCSC) 문제'로 일반화하여 접근한다. 주어진 집합 X와 제약 조건 t에 대해, X를 커버하는 최소한의 일관된 부분집합을 찾는 문제로 정의되며, 이는 전통적인 집합 커버 문제와 최소 클릭 파티션 문제 등을 포괄한다. 규칙 학습, 클러스터링, 패턴 마이닝 등 다양한 데이터 마이닝 작업(최소 규칙 집합, 역 k-클러스터링, 패턴 요약 등)을 MCSC 인스턴스로 공식화할…

8 min read

최소 일관 부분집합 커버 문제 (MCSC): 데이터 마이닝의 최소화 관점

Source

  • Evernote/Papers/The Minimum Consistent Subset Cover Problem A Minimization View of Data Mining.md

Summary

본 논문은 데이터 마이닝 작업을 ‘최소 일관 부분집합 커버(MCSC) 문제’로 일반화하여 접근한다. 주어진 집합 X와 제약 조건 t에 대해, X를 커버하는 최소한의 일관된 부분집합을 찾는 문제로 정의되며, 이는 전통적인 집합 커버 문제와 최소 클릭 파티션 문제 등을 포괄한다. 규칙 학습, 클러스터링, 패턴 마이닝 등 다양한 데이터 마이닝 작업(최소 규칙 집합, 역 k-클러스터링, 패턴 요약 등)을 MCSC 인스턴스로 공식화할 수 있음을 제시한다. 또한, 이진 할당 그래프를 기반으로 한 예제 기반 구체-일반 탐색을 수행하는 범용 알고리즘 CAG(Covering Algorithm via Graph)를 제안하여, 이러한 MCSC 인스턴스에 직접 적용 가능함을 보인다.

Key Points

  • MCSC 문제 정의: 제약 조건을 만족하는 최소한의 부분집합으로 전체 집합을 커버하는 문제
  • 기존 문제 일반화: 집합 커버 문제, 최소 클릭 파티션 문제(MCP) 등을 포함하는 상위 개념
  • 데이터 마이닝 적용: 규칙 학습(MRS), 클러스터링(역 k-클러스터링), 패턴 요약 등을 MCSC 프레임워크로 통합
  • 제안 알고리즘 CAG: 이진 할당 그래프를 동적으로 유지하며, 최대 최적 부분 해를 구축한 후 구체-일반 탐색을 수행하는 범용 알고리즘

그래프 뷰

백링크