개념 클러스터링

개념 클러스터링은 Ryszard S에 의해 정의된 비감독 분류를 위한 기계 학습 패러다임이다. 1980년 미할스키(Fisher 1987, 미할스키 1980)로 주로 1980년대에 개발되었습니다.생성된 각 클래스에 대한 개념 설명을 생성하여 일반적인 데이터 클러스터링과 구별됩니다.대부분의 개념 군집화 방법은 계층 범주 구조를 생성할 수 있습니다. 계층에 대한 자세한 내용은 분류를 참조하십시오.개념 클러스터링은 공식적인 개념 분석, 의사결정 트리 학습 및 혼합 모델 학습과 밀접하게 관련되어 있습니다.

개념 클러스터링과 데이터 클러스터링 비교

개념 클러스터링은 분명히 데이터 클러스터링과 밀접하게 관련되어 있습니다.그러나 개념 클러스터링에서는 클러스터 형성을 촉진하는 데이터의 고유 구조뿐만 아니라 학습자가 사용할 수 있는 설명 언어도 중요합니다.따라서, 일반적인 개념 기술 언어가 특정 규칙성을 설명할 수 없는 경우, 통계적으로 강력한 데이터 그룹을 학습자가 추출하지 못할 수 있다.대부분의 구현에서 기술 언어는 기능 결합으로 제한되지만 COBWEB(아래의 "COBWEB" 참조)에서는 기능 언어는 확률적입니다.

공개된 알고리즘 목록

개념 클러스터링을 위해 상당한 수의 알고리즘이 제안되었습니다.몇 가지 예를 다음에 제시하겠습니다.

클러스터/2(Michalski & Stepp 1983)
COBWEB (1987년 피셔)
CYRUS (1983년)
GALOIS (카르피네토 & 로마노 1993),
GCF (Talavera & Béjar 2001)
INC(Hadzikadic & Yun 1989)
ITERATE (Biswas, Weinberg & Fisher 1998),
미로(Thompson & Langley 1989년)
SUBDU(Jonyer, Cook & Holder 2001).
UNIMEM (1987년)
WITT(Hanson & Bauer 1989),

개념 클러스터링에 대한 보다 일반적인 논의와 리뷰는 다음 출판물에서 확인할 수 있습니다.

미할스키 (1980년)
Gennari, Langley, and Fisher (1989)
Fisher & Pazzani (1991)
Fisher & Langley (1986)
스테프 & 미할스키 (1986)

예: 기본 개념 클러스터링 알고리즘

이 섹션에서는 개념 클러스터링 알고리즘 COBWEB의 기초에 대해 설명합니다.다양한 휴리스틱스 및 "카테고리 선량" 또는 카테고리 평가 기준을 사용하는 다른 알고리즘이 많이 있지만 COBWEB은 가장 잘 알려진 알고리즘 중 하나입니다.독자는 다른 방법에 대해 참고 문헌 목록을 참조한다.

지식 표현

COBWEB 데이터 구조는 각 노드가 특정 개념을 나타내는 계층(트리)입니다.각 개념은 개체의 집합(실제로 다중 집합 또는 가방)을 나타내며, 각 개체는 이진 값 속성 목록으로 표시됩니다.각 트리 노드(즉, 개념)와 관련된 데이터는 해당 개념의 객체에 대한 정수 속성 수입니다.예를 들어 (그림 참조) $C_{1}$ $C_{1}$ 1 $(\$ 에 $C_{1}$ 다음 4개의 오브젝트(반복되는 오브젝트 허용)가 포함되어 있다고 합니다.

샘플 COBWEB 지식 표현, 확률론적 개념 계층.파란색 상자는 실제 개체를 나열하고 보라색 상자는 특성 수를 나열합니다.자세한 내용은 텍스트를 참조하십시오.주의: 이 다이어그램은 COBWEB의 데이터 구조만을 설명하기 위한 것입니다.이 그림은 반드시 "좋은" 개념의 트리를 나타내는 것은 아니며, 실제 데이터에서 실제로 구성되는 개념의 트리를 나타내는 것은 아닙니다.

[1 0 1]
[0 1 1]
[0 1 0]
[0 1 1]

세 가지 속성은 예를 들어 다음과 같습니다.[is_male, has_wings, is_nocturnal]그러면 이 개념 노드에 저장되는 것이 속성 개수입니다.[1 3 3]이는 개념의 개체 중 1개가 수컷이고, 3개가 날개를 가지고 있으며, 3개가 야행성임을 나타냅니다.개념 설명은 노드 속성의 범주 조건부 확률(우도)입니다.따라서 물체가 범주 $C_{1}$ 1 $($ ) C1( $표시$ 스타일 $C_{$ 1 $C_{1}$ 에 속한다고 $가정$ 할 때 수컷일 $1/4=0.25$ 은 1 $1/4=0.25$ $.$ 25( $표시$ 스타일 1/ $4$ $=0.$ 25 $1/4=0.25$ 입니다. 마찬가지로 물체가 야행성이거나 둘 다일 확률은 3 $3/4=0.75$ $표시 스타일$ 3.75)입니다.따라서 ncept description은 단순하게 다음과 같이 주어질 수 있다.[.25 .75 .75]이는 $({$ $style$ C_ ${$ $1})$ 에 $C_{1}$ 해당합니다. $p(x|C_{1})=(0.25,0.75,0.75)$ , p $x$ $p(x|C_{1})=(0.25,0.75,0.75)$ 1) $p(x|C_{1})=(0.25,0.75,0.75)$ ( $p(x|C_{1})=(0.25,0.75,0.75)$ 0. $0$ . $p(x|C_{1})=(0.25,0.75,0.75)$ $1$ }) = ( $0.25, 0.75)$ .

오른쪽 그림은 5가지 개념으로 구성된 개념 트리를 보여줍니다. $C_{0}$ 0 $(\$ 은 $C_{0}$ 루트 개념으로 데이터 세트 내의 10개 오브젝트를 모두 포함합니다. $C_{1}$ $C_{1}$ 1 $(\$ 및 $C_{1}$ $C_{2}$ 2(\ $displaystyle C_{2})$ 는 $C_{2}$ C $(\$ 의 자식입니다.전자는 4개의 오브젝트를 포함하며, 후자는 6개의 오브젝트를 포함합니다. $C_{2}$ $C_{2}$ 2 $({$ 는 $C_{2}$ 컨셉 $C_{3}$ 3({ $displaystyle C_{3$ $C_{4}$ 4 $({$ $C_{$ $4$ $C_{5}$ C $({$ 의 부모이기도 합니다.각각 오브젝트는 3개, 2개, 1개입니다.각 부모 노드(상대 상위 개념)에는 자식 노드(상대 하위 개념)에 포함된 모든 개체가 포함되어 있습니다.Fisher(1987)의 COBWEB 설명에서는 총 속성 수(조건부 확률 및 객체 리스트가 아님)만 노드에 저장되어 있음을 나타냅니다.모든 확률은 필요에 따라 속성 개수에서 계산됩니다.

COBWEB 언어

COBWEB의 기술 언어는 완전히 확률적이어서 어떤 개념도 기술할 수 있기 때문에 느슨한 의미의 "언어"입니다.그러나, 어떤 개념이 나타낼 수 있는 확률 범위에 제약이 가해진다면, 더 강력한 언어를 얻을 수 있다.예를 들어, 적어도 하나의 확률이 0.5와 $\alpha$ α $이상$ 차이가 나는 개념만 허용할 수 있습니다. 이 제약 조건 하에서 $\alpha =0.3$ 0. $\alpha =0.3$ {\ $displaystyle$ \ $alpha$ = $\alpha =0.3$ 0.3 $\alpha =0.3$ 인 경우, 다음과 같은 개념은 다음과 같습니다.[.6 .5 .7]학습자에 의해 구성될 수 없었다; 그러나 같은 개념[.6 .5 .9]0.5와 최소 $1개$ 의 $\alpha$ α 이상 차이가 나기 때문에 접근할 수 있습니다. 따라서 이러한 제약 조건 하에서 우리는 전통적인 개념 언어와 같은 것을 얻습니다 $.$ 모든 특징에 대해 α $\alpha =0.5$ 0. $(\displaystyle \alpha = 0.5)$ 이므로 $\alpha =0.5$ 개념의 모든 확률은 0 또는 1이어야 하는 제한적인 경우, 결과는 결합에 따른 특징 언어 기반이다. 즉, 표현될 수 있는 모든 개념은 특징(및 그 부정)의 조합으로 설명될 수 있으며, 그리고 표현할 수 없는 개념도 설명할 수 있다.이렇게 기술된 것은 표현할 수 없습니다.

평가기준

COBWEB에 대한 Fisher의 설명(1987)에서 계층의 품질을 평가하기 위해 사용하는 척도는 Gluck and Corter의 범주 효용(CU) 측정이며, 그는 논문에서 이를 다시 도출했습니다.이 조치의 동기는 Quinlan이 의사 결정 트리 학습을 위해 도입한 "정보 획득" 조치와 매우 유사합니다.이전에 특성 기반 분류에 대한 CU는 특성 변수와 클래스 변수 간의 상호 정보와 동일하다는 것이 입증되었다(Gluck & Corter, 1985; Corter & Gluck, 1992). 이 측정이 훨씬 더 잘 알려져 있기 때문에, 우리는 "선도" 범주의 측정으로 상호 정보를 가지고 이 작업을 진행한다.

평가하고자 하는 것은 객체를 특정 계층 분류 구조로 그룹화하는 전반적인 유틸리티입니다.일련의 가능한 분류 구조를 고려할 때, 우리는 어떤 것이 다른 것보다 나은지 결정해야 한다.

레퍼런스

Biswas, G.; Weinberg, J. B.; Fisher, Douglas H. (1998). "Iterate: A conceptual clustering algorithm for data mining". IEEE Transactions on Systems, Man, and Cybernetics - Part C: Applications and Reviews. 28 (2): 100–111. doi:10.1109/5326.669556.

Carpineto, C.; Romano, G. (1993). "Galois: An order-theoretic approach to conceptual clustering". Proceedings of 10th International Conference on Machine Learning, Amherst. pp. 33–40.

Fisher, Douglas H. (1987). "Knowledge acquisition via incremental conceptual clustering" (PDF). Machine Learning. 2 (2): 139–172. doi:10.1007/BF00114265.

Fisher, Douglas H. (1996). "Iterative optimization and simplification of hierarchical clusterings". Journal of Artificial Intelligence Research. 4: 147–178. arXiv:cs/9604103. Bibcode:1996cs........4103F. doi:10.1613/jair.276. S2CID 9841360.

Fisher, Douglas H.; Langley, Patrick W. (1986). "Conceptual clustering and its relation to numerical taxonomy". In Gale, W. A. (ed.). Artificial Intelligence and Statistics. Reading, MA: Addison-Wesley. pp. 77–116.

Fisher, Douglas H.; Pazzani, Michael J. (1991). "Computational models of concept learning". In Fisher, D. H.; Pazzani, M. J.; Langley, P. (eds.). Concept Formation: Knowledge and Experience in Unsupervised Learning. San Mateo, CA: Morgan Kaufmann. pp. 3–43.

Gennari, John H.; Langley, Patrick W.; Fisher, Douglas H. (1989). "Models of incremental concept formation". Artificial Intelligence. 40 (1–3): 11–61. doi:10.1016/0004-3702(89)90046-5.

Hanson, S. J.; Bauer, M. (1989). "Conceptual clustering, categorization, and polymorphy". Machine Learning. 3 (4): 343–372. doi:10.1007/BF00116838.

Jonyer, I.; Cook, D. J.; Holder, L. B. (2001). "Graph-based hierarchical conceptual clustering". Journal of Machine Learning Research. 2: 19–43. doi:10.1162/153244302760185234.

Lebowitz, M. (1987). "Experiments with incremental concept formation". Machine Learning. 2 (2): 103–138. doi:10.1007/BF00114264.

Michalski, R. S. (1980). "Knowledge acquisition through conceptual clustering: A theoretical framework and an algorithm for partitioning data into conjunctive concepts". International Journal of Policy Analysis and Information Systems. 4: 219–244.

Michalski, R. S.; Stepp, R. E. (1983). "Learning from observation: Conceptual clustering" (PDF). In Michalski, R. S.; Carbonell, J. G.; Mitchell, T. M. (eds.). Machine Learning: An Artificial Intelligence Approach. Palo Alto, CA: Tioga. pp. 331–363.

Stepp, R. E.; Michalski, R. S. (1986). "Conceptual clustering: Inventing goal-oriented classifications of structured objects" (PDF). In Michalski, R. S.; Carbonell, J. G.; Mitchell, T. M. (eds.). Machine Learning: An Artificial Intelligence Approach. Los Altos, CA: Morgan Kaufmann. pp. 471–498.

Talavera, L.; Béjar, J. (2001). "Generality-based conceptual clustering with probabilistic concepts". IEEE Transactions on Pattern Analysis and Machine Intelligence. 23 (2): 196–206. doi:10.1109/34.908969.

외부 링크

Search

개념 클러스터링

네임스페이스

더

목차