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

• 비지도 학습(Unsupervised learning)
• 문헌을 범주로 분류하는 전문가가 없음
• 평면 군집화(Flat clustering)
• 군집화 결과가 평면적으로만 분리되어 있으며 어떤 형태의 구조를 가지지는 않음
• 계층 군집화(Hierarchic clustering)
• 군집화 결과가 계층 구조를 가짐

16.1 정보 검색의 군집화

• 군집 가설(Cluster hypothesis)
• 같은 군집에 있는 문헌들은 정보 요구에 대한 적합성이 비슷함

16.2 문제 정의

• 평면적 경군집화의 요소
• 문헌 집합
• 원하는 군집 수
• 군집의 질을 평가하는 목적 함수(Objective function)
• 경군집하는 한 문헌이 하나 혹은 그 이상의 군집에 완전히 속할 수 있음
• 분할 군집화(Partitional clustering)
• 각 문헌은 정확하게 한 군집에만 속함
• 그러나 분할 계층 군집화에서 한 군집에 속한 모든 문헌은 그 군집의 부모 군집에도 속하므로, 경군집화도 정의에 따라 여러 군집에 속할 수 있음
• 경군집화(1 혹은 0)와 연군집화(임의의 양수)의 차이는 소속 함수 값에 있음
• 완전 군집화(Exhaustive clustering)
• 각 문헌이 한 군집에 속하는 경우

16.3 군집화 평가

• 내부 기준(Internal criterion)
• 군집 내의 유사도는 최대가 되게 하고, 군집 간의 유사도는 최소가 되도록 하는 것
• 외부 기준(External criterion)
• 군집화 결과가 평가용 벤치마크와 얼마나 잘 맞는지를 평가하는 것
• 순도(Purity)
• 일반적으로 군집이 많으면 순도가 높음
• 순도는 군집의 수와 군집의 질이 반비례하여 잘 이용되지 않음
• 정규화된 상호 정보(NMI, Normalized Mutual Information)
• 정보 이론에 기반을 둔 척도
• 긍정 정답이면 비슷한 두 문헌이 같은 군집에 속하고, 부정 정답이면 두 비슷하지 않은 문헌이 다른 군집에 속함
• 하지만 여전히 긍정 오류와 부정 오류에서 오류를 범할 수 있음
• Rand 지수(Rand index)
• 군집화 과정에서 긍정 오류와 부정 오류에 불리하게 함
• F-척도(F measure)
• 긍정 오류와 부정 오류에 대해 가중치를 줌

16.4 K-means

• 가장 중요한 평면 군집화 알고리즘으로, 문헌들과 그 문헌이 속한 군집의 중심과의 평균 Euclidean 거리를 최소화하는 것을 목적으로 함
• 잔차제곱합(RSS, Residual Sum of Squares)
• 중심이 군집에 속한 문헌을 얼마나 잘 표현하는가를 나타내는 척도
• RSS는 K-means의 목적 함수로 이를 최소화해야 함
• 처음 임의의 K개 문헌을 선택하여 초기 중심으로 군집 씨앗(Seed)을 선택함
• 반복 종료 조건
• 미리 정한 반복 횟수 I에 도달할 때까지 반복함
• 문헌이 속한 군집이 더 이상 변하지 않을 때까지 반복함
• 중심이 더 이상 변하지 않을 때까지 반복함
• RSS가 임계값 이하로 떨어질 때까지 반복함
• RSS의 감소폭이 임계값 이하로 떨어질 때까지 반복함
• 예외 자료(Outlier)의 경우 낮은 RSS를 가지더라도 단문헌 군집(Singleton cluster)이 될 수 있음
• 군집 씨앗 선택 규칙
• 군집 씨앗으로 선택된 문헌이 예외 자료일 경우에는 이를 배체함
• 여러 군집 씨앗으로 시작해서 군집화를 구성하고 이들 중 가장 적합한(평가 척도의 값이 낮은) 군집을 선택함
• 계층 군집화와 같은 다른 방법을 통해서 군집 씨앗을 구함
• 군집 기수를 정하기 위한 목적 함수
• 왜곡(Distortion)
• 문헌들이 원래의 군집으로부터 얼마나 많이 벗어나는가를 측정
• 모델 복잡도(Model complexity)
• 보통 군집의 수나 군집 수에 대한 함수임
• AIC(Akaike information Criterion)
• 모델 복잡도와 왜곡의 반비례를 정보 이론적으로 측정하는 방법

16.5 모델 기반 군집화

• 모델 기반 군집화(Model based clustering)
• 모델로 자료를 생성하고 생성된 자료로부터 모델을 복원한다고 가정함
• 자료로부터 복원된 모델은 군집과 문헌 할당을 정의함
• 모델 인수를 추정하는 일반적인 기준은 최대 우도이며, 최대 우도 기준은 자료 D를 생성하는 로그 우도(Log likelihood)를 최대로하는 인수를 선택하는 것임
• EM 알고리즘(Expectation Maximization algorithm)
• 모델 기반 군집화에서 가장 일반적으로 사용되는 알고리즘
• 기대값 계산 단계(Expectation step)와 최대화 단계(Maximization step)가 번갈아가면서 동작함(K-means와 비슷함)