'Study/Information Retrieval'에 해당되는 글 21건

• 계층 군집화(Hierarchical clustering)
• 군집화 결과로 계층적인 구조를 생성하며, 일반적으로 계층적인 구조는 평면적인 구조에 비해 더 유용함
• 미리 군집 수를 정할 필요가 없음
• 알고리즘 복잡도가 문헌 수의 제곱에 비례하여 효율성이 떨어짐
• K-means와 EM의 복잡도는 문헌 수에 비례함

17.1 계층 병합 군집화

• 상향식
• 계층 병합 군집화(HAC, Hierarchical Agglomerative Clustering)
• 각 문헌이 독립된 하나의 군집이 된 후, 가장 유사한 두 군집을 하나의 군집으로 병합하면서 모든 문헌이 하나의 군집에 포함될 때까지 반복함
• 단조성(Monotonicity)
• 병합이 단조 연산임

17.2 단일 및 완전-연결 군집화

• 단일 연결 군집화(Single-link clustering): 최대 유사도
• 두 군집 중 가장 가까이에 있는 문헌 간의 유사도
• 완전-연결 군집화(Complete-link clustering): 최소 유사도
• 두 군집 중 가장 멀리 있는 문헌 간의 유사도
• 클릭(Clique)
• 그래프에 포함된 모든 정점 쌍이 서로 연결된 집합
• 연쇄(Chaining)
• 병합 기준이 아주 지역적이므로 병합된 전체 군집의 분포에 관계없이 계속 길게 뻗어질 수 있음

17.3 그룹-평균 병합 군집화

• 그룹-평균 병합 군집화(GAAC, Group-Average Agglomerative Clustering)
• 문헌들의 모든 유사성을 이용해서 군집의 품질을 평가함

17.4 중심 군집화

• 군집 유사도는 두 군집의 중심 사이의 유사도
• GAAC는 두 군집의 모든 문헌 사이의 평균 유사도를 군집 유사도로 간주하지만, 중심 군집화는 서로 다른 군집 간 문헌 사이의 평균 유사도를 군집 유사도로 간주함
• 도치(Inversion)
• 중심 군집화는 군집 유사도가 단조감소하지 않아 나중에 병합된 군집 유사도가 오히려 더 높을 수 있음

17.5 HAC의 최적성

• GAAC에서 가장 좋은 결과를 얻을 수 있음
• 연쇄와 도치 현상이 발생하지 않으며, 예외 자료로부터도 그다지 민감하게 반응하지 않음
• 예외 조건
• 벡터 공간에만 적용할 수 있음
• 벡터공간이 아닌 경우 완전-연결 방식을 사용해야 함
• 군집화의 목적이 전체 문헌을 대상으로 하는 경우가 아닌 경우 GAAC는 바람직하지 않음

17.6 분할 군집화

• 하향식 군집화(Top-down clustering) 혹은 분할 군집화(Divisive clustering)
• 하향식
• 한 군집을 여러 군집으로 나누는 방법

17.7 군집 작명법

• 차별 군집 작명법(Differential cluster labeling)
• 어떤 군집에 속하는 용어의 분포와 다른 군집에 속하는 용어의 분포를 비교해서 군집의 이름을 선택하는 것
• 자주 사용되지 않는 용어를 불리하게 하는 방법
• 군집 내부 작명법(Cluster-internal labeling)
• 다른 군집에 의존하지 않고 자신의 군집 내에서 이름을 찾음
• 군집 중심에 가장 가까운 문헌의 제목을 군집의 이름으로 간주하는 방법이 있음