[정보검색] 제5장 문헌 클러스터링
이 글은 정영미 교수님의 정보검색연구를 바탕으로 연세대학교 문성빈 교수님의 수업을 공부한 기록입니다.
1. 자동분류 개요
자동분류 (Automatic Classification) 개념
- 분류 알고리즘에 의해 대상물(object)들을 유사한 패턴을 갖는 것끼리 모아 집단화하는 작업
- 정보검색 분야에서 분류 대상물(object): 주로 문헌이나 용어
- 문헌 자동분류
- 유사한 내용의 문헌들을 미리 집단화함으로써 검색을 용이하게 하려는 목적
- 용어 자동분류
- 용어 클래스들을 생성함으로써 자동 시소러스를 작성하려는 목적
- 검색 시 질의어와 유사한 용어 클래스의 다른 용어들을 질의에 추가함으로써 검색 성능을 향상시키려는 목적
- Cluster-Based Retrieval
- 이전에는 쿼리와 문헌을 일대일로 유사도 계산 (비효과적)
- 최근에는 유사한 문헌들을 묶어 클러스터를 생성한 후
- 쿼리와 클러스터를 비교하여 가장 유사한 클러스터 선택한 후
- 쿼리와 해당 클러스터 내 문헌들을 일대일로 유사도 계산 (효과적)
문헌 자동분류 유형
- 사전(a priori) 분류체계의 활용 여부에 따라
- 문헌 클러스터링 (Document Clustering)
- 사전 분류체계 없이 문헌 간의 유사성에 근거하여 유사한 내용의 문헌들의 집단을 형성하는 것
- 학습 데이터를 필요로 하지 X
- 비지도학습(Unsupervised Learning) 분류
- 텍스트 범주화 (Text Categorization)
- 기계학습(machine learning) 방법에 의해 각 문헌을 사전 분류체계의 가장 적절한 주제범주에 배정하는 것
- 각 범주를 대표하는 이름(class label)과 학습 데이터(training data)를 사용
- 지도학습(Supervised Learning) 분류
자동분류 기법의 유형
- 분류기법의 유형
- 중복적(Overlapping) 분류
- 하나의 대상물이 복수의 분류 범주에 속하도록 허용
- 즉 하나의 문헌을 여러 범주에 속하도록 하는 경우
- 예: 복수의 범주로 문헌을 분류할 수 있는 텍스트 범주화
- 배타적(Exclusive) 분류
- 대상물을 단 하나의 범주에만 배정
- 즉 하나의 문헌을 한개의 주제범주로만 분류하는 경우
- 외재적(extrinsic) 분류
- 유사도 행렬 이외에 사전에 부여된 범주명을 함께 사용하는 지도 학습 분류에 해당
- 예: 텍스트 범주화
- 내재적(intrinsic) 분류
- 분류 대상물에 대한 데이터 행렬(data matrix)이나 대상물 간의 유사도(proximity matrix)만을 사용하는 비지도 학습 분류에 해당
- 예: 문헌 클러스터링
2. 문헌 클러스터링 개요
문헌 클러스터링 개념
- 각 문헌을 표현하는 자질(feature)들을 비교하여 문헌 간 유사성을 측정
- 비슷한 내용의 문헌들을 동일한 집단에 속하도록 군집화
- 클러스터링 결과 생성된 유사한 문헌들의 집단, 즉 문헌 클러스터들은 각 클러스터를 대표하는 클러스터 프로파일(클러스터 센트로이드)을 갖게 되며
- 검색 시 질의와 클러스터 프로파일이 비교되어 질의에 가장 적합한 클러스터가 검색
문헌 클러스터링 가설
- “밀집하게 상호 관련된 문헌들은 동일한 정보요구에 의해 대해 모두 적합할 것이다.”
- “특정한 정보요구에 대해 적합한 문헌들과 부적합한 문헌들은 서로 다른 클러스터에 속할 것이다.”
- 즉 특정한 질의에 대해 검색된 문헌 클러스터는 질의에 적합한 문헌들을 모두 포함하고
- 나머지 클러스터들은 질의와는 다른 주제에 관련된 문헌들을 포함할 것이라고 보는 것
- 따라서 먼저 질의와 가장 유사한 클러스터를 검색한 다음
- 검색된 클러스터에 포함된 문헌들을 모두 질의에 적합한 문헌으로 판정하여 제공하거나
- 다시 각 문헌과 질의와의 유사도를 산출하여 적합성 순위에 따라 제공
문헌 클러스터링 과정에 필요한 요소
- 분류 대상들인 문헌들의 집합
- 각 문헌을 표현하는 분류자질 집합
- 문헌 간 유사도를 측정하는 유사성 척도
- 문헌들을 군집화하는 클러스터링 알고리즘
문헌 클러스터링 과정
- 분류자질 선정
- 문헌을 표현하는 자질로는 문헌의 주제를 나타내는 용어들을 주로 선정
- 분류자질의 수가 너무 많을 경우에는 분류자질 집합의 크기를 축소하기도 O
- 분류자질의 선정 기준: 용어의 문헌빈도(DF) 혹은 장서빈도(CF)
- 너무 적은 수의 문헌에 출현했거나 전체 문헌집합 내 출현빈도가 너무 적은 용어들은 분류자질에서 제외
- 예: 용어가 출현한 문헌의 수가 5 민만인 용어(DF<5)는 분류자질로 사용하지 X
- 문헌 표현
- 분류자질이 선정된 각 문헌은 d개의 용어들의 가중치가 벡터 요소가 되는 d차원의 문헌벡터로 표현
- D = (x1, …, xd)
- 문헌집합은 n x d 크기의 문헌-용어 행렬로 표현
- 문헌 간 유사도 산출
- 문헌-용어 행렬로부터 각 문헌쌍 Di와 Dj 간의 유사도 S(Di, Dj)를 산출하여
- 문헌-문헌 유사도 행렬 생성
- 유사도 산출에는 다양한 거리계수나 유사계수 공식을 사용
- 클러스터 생성
- 클러스터링 알고리즘을 적용하여 유사도가 높은 문헌들을 묶은 클러스터를 생성
- 클러스터링 알고리즘으로는 계층적 클러스터링 알고리즘이나 비계층적 클러스터링 알고리즘을 사용
3. 문헌 간 유사도 측정
유사도 척도
- 클러스터링의 대상이 되는 문헌들 간의 유사도를 측정하기 위하여 사용하는 것
- 거리계수와 유사계수로 구분
- 거리계수는 두 문헌 X, Y 간의 거리를 측정
- 유사계수는 두 문헌 X, Y 간의 유사성을 측정
- 분류자질 값의 유형(등간데이터, 빈도데이터, 이진데이터 등)에 따라 적합한 척도가 선택
- 문헌 분류자질 출현여부 분할표
- a : 문헌 X에 출현 O & 문헌 Y에 출현 O 용어의 수
- b : 문헌 X에 출현 O & 문헌 Y에 출현 X 용어의 수
- c : 문헌 X에 출현 X & 문헌 Y에 출현 O 용어의 수
- d : 문헌 X에 출현 X & 문헌 Y에 출현 X 용어의 수
거리계수
- 유클리드 거리
- 등간 데이터 : $D(X, Y) = \sqrt{\sum_i (x_i - y_i)^2}$
- 이진 데이터 : $D(X, Y) = \sqrt{(b+c)}$
유사계수
- 코사인 계수
- 등간 데이터 : $S(X, Y) = \frac{\sum_i (x_i, y_i)}{\sqrt{\sum_i (x_i)^2 \sum_i (y_i)^2}}$
- 다이스 계수
- 이진 데이터 : $S(X, Y) = \frac{2a}{(2a+b+c)}$
- 등간 데이터 : $S(X, Y) = \frac{2 \sum_i (x_i, y_i)}{\sqrt{\sum_i (x_i)^2 \sum_i (y_i)^2}}$
- 자카드 계수
- 이진 데이터 : $S(X, Y) = \frac{a}{a+b+c}$
- 등간 데이터 : $S(X, Y) = \frac{\sum_i (x_i, y_i)}{\sqrt{\sum_i (x_i)^2 + \sum_i (y_i)^2 - \sum_i (x_i, y_i)}}$
- 내적 계수
- $S(X, Y) = \sum_i x_i \times y_i$
[예제] 문헌벡터가 이원 벡터로 표현되는 경우
$X = (1, 1, 1, 0, 0, 0, 1, 1)$
$Y = (1, 1, 1, 0, 0, 1, 0, 0)$
코사인 계수 = $\frac{3}{\sqrt{(3+2)(3+1)}}$
다이스 계수 = $\frac{2 \times 3}{2 \times 3 + 2 + 1}$
자카드 계수 = $\frac{3}{3+2+1}$
[예제] 문헌벡터가 용어 가중치 벡터로 표현되는 경우
$X = (3, 2, 1, 0, 0, 0, 1, 1)$
$Y = (2, 1, 1, 0, 0, 3, 0, 0)$
코사인 계수 = $\frac{3 \times 2 + 2 \times 1 + 1 \times 1}{\sqrt{(3^2+2^2+1^2+1^2+1^2) \times (2^2+1^2+1^2+3^2)}}$
다이스 계수 = $\frac{2 \times 9}{16 + 15}$
자카드 계수 = $\frac{9}{16+15-9}$
내적 계수 = $3 \times 2 + 2 \times 1 + 1 \times 1$
유클리드 계수 = $\sqrt{(3-2)^2+(2-1)^2+(1-1)^2+(0-3)^2+(1-0)^2+(1-0)^2}$
4. 클러스터링 기법
계층적(hierarchical) 클러스터링
- 데이터 집합(문헌집단) 내의 모든 대상물이 연결될 때까지 대상물이나 클러스터 쌍들을 연속적으로 연결해가는 기법
- 클러스터들의 계층을 형성
비계층적(non-hierarchical) 클러스터링 = 분할적(partitional) 클러스터링
- 경험적 기법 = 자기발견적(heuristic) 기법
- 클러스터링 이전에 미리 생성할 클러스터의 수, 클러스터의 크기, 클러스터 생성 기준치 등을 결정
- 재배치(reallocation) 클러스터링 = 반복적 분할 클러스터링
- 대개 초기 데이터 집합을 여러 개의 클러스터로 분할한 다음 대상물을 보다 적절한 클러스터로 재배치하는 과정을 거쳐 최적의 클러스터들을 생성
응집적(agglomerative) 알고리즘
- 클러스터링 이전의 데이터 집합으로부터 대상물이나 클러스터 쌍들이 결합되기 시작하는데 모두 N-1번의 결합 과정을 거치게 되는 것
- 클러스터링 초기에 각 대상물은 자신만으로 구성되는 단독개체 클러스터를 형성하고
- 이 클러스터들은 결합하여 점점 큰 클러스터를 형성하게 되어
- 최종적으로 모든 대상물이 포함되는 단일 클러스터를 생성하는 것
- 상향식(bottom-up) 알고리즘
- 개별 대상물에서 시작하여 점점 큰 클러스터를 형성해 가기 때문
분열적(divisive) 알고리즘
- 모든 대상물을 포함하는 단일 클러스터에서 시작하여 한 클러스터가 더 작은 클러스터로 쪼개지는 모두 N-1번의 분열 과정을 거치게 되는 것
- 하향식(top-down) 알고리즘
- 전체 데이터 집합으로부터 시작하여 점점 작은 클러스터를 생성해 가기 때문
계층적 클러스터링 기본 과정
- 문헌을 용어들의 벡터로 표현하여 문헌-용어 행렬을 작성한다.
- 문헌 쌍 간의 유사도 또는 거리를 산출하여 문헌-문헌 유사도 행렬을 작성한다.
- 개별 대상물로 각각의 초기 클러스터를 형성한다.
- 유사도가 가장 큰 즉 거리가 가장 가까운 클러스터 쌍을 찾아 통합한다,
- 새로운 클러스터와 나머지 클러스터 간의 유사도를 산출하여 4번 단계로 돌아간다. 한개의 클러스터로 통합될 때까지 이 과정을 반복한다.
- 계층적 클러스터링 결과 생성된 클러스터 계층은 흔히 덴드로그램으로 표현한다.
계층적 클러스터링 알고리즘 유형
- 유사한 클러스터들의 통합 방법 즉 클러스터 간 유사도 산출 방법에 따라 구분
- 단일연결 기법 (Single Link Method) (Single Linkage Method)
- 통합되는 두 클러스터 간의 유사도는 가장 유사한 즉 가장 거리가 가까운 두 구성원 간의 유사도로 측정
- 완전연결 기법 (Complete Link Method)
- 통합되는 두 클러스터 간의 유사도는 가장 유사하지 않은 즉 거리가 가장 먼 두 구성원 간의 유사도로 측정
- 집단평균연결 기법 (Group Average link Method)
- 통합되는 두 클러스터 간의 유사도는 모든 구성원 쌍 간의 유사도 값의 평균으로 측정
- 워드 기법 (Ward’s Method)
- 단일연결 기법 (Single Link Method) (Single Linkage Method)
- 결과적으로 단일연결 기법은 완전연결 기법에 비해 구성원 간의 응집력이 약하며 크기가 큰 클러스터를 생성
- 완전연결 기법이 단일연결 기법에 비해 높은 유사도
단일연결 기법
- 통합 대상이 되는 두 클러스터 안에서 가장 유사한 즉 거리가 가까운 두 구성원 간의 유사도를 새로 통합할 두 클러스터의 유사도로 간주
- 가장 가까운 이웃 기법
완전연결 기법
- 통합 대상이 되는 두 클러스터 안에서 가장 유사하지 않은 즉 거리가 먼 두 구성원 간의 유사도를 새로 통합할 두 클러스터의 유사도로 사용
- 가장 먼 이웃 기법
- 크기가 큰 & 적은 수의 클러스터 생성
집단평균연결 기법
- 클러스터 통합의 대상이 되는 두 클러스터의 모든 구성원들 간의 유사도 평균을 산출하여 이 유사도 값이 가장 큰 두 클러스터를 통합하여 새로운 클러스터를 생성
[예제] 거리계수가 다음과 같을 때 단일연결 기법과 완젼연결 기법에 의한 클러스터링 결과를 보여주시오. 단일연결 기법
1단계 클러스터링
결과: $\{A, C\}, \{B\}, \{D\}, \{E\}$
2단계 클러스터링
$d(\{A,C\}, \{B\}) = \min [d(A,B), d(C,B)] = \min (0.5, 0.4) = 0.4$
$d(\{A,C\}, \{D\}) = \min [d(A,D), d(C,D)] = \min (0.3, 0.6) = 0.3$
$d(\{A,C\}, \{E\}) = \min [d(A,E), d(C,E)] = \min (0.7, 0.2) = 0.2$
$d(\{B\}, \{D\}) = 0.75$
$d(\{B\}, \{E\}) = 0.9$
$d(\{D\}, \{E\}) = 0.8$
결과: $\{A,C,E\}, \{B\}, \{D\}$
3단계 클러스터링
결과: $\{A,C,D,E\}, \{B\}$
완전연결 기법
1단계 클러스터링
결과: $\{A, C\}, \{B\}, \{D\}, \{E\}$
2단계 클러스터링
$d(\{A,C\}, \{B\}) = \max [d(A,B), d(C,B)] = \max (0.5, 0.4) = 0.5$
$d(\{A,C\}, \{D\}) = \max [d(A,D), d(C,D)] = \max (0.3, 0.6) = 0.6$
$d(\{A,C\}, \{E\}) = \max [d(A,E), d(C,E)] = \max (0.7, 0.2) = 0.7$
$d(\{B\}, \{D\}) = 0.8$
$d(\{B\}, \{E\}) = 0.9$
$d(\{D\}, \{E\}) = 0.75$
결과: $\{A,B,C\}, \{D\}, \{E\}$
3단계 클러스터링
$d(\{A,B,C\}, \{D\}) = \max [d(A,D), d(B,D), d(C,D)] = \max(0.3, 0.8, 0.6) = 0.8$
$d(\{A,B,C\}, \{E\}) = \max[d(A,E), d(B,E), d(C,E)] = \max(0.7, 0.9, 0.2) = 0.9$
$d(\{D\}, \{E\}) = 0.75$
결과: $\{A,B,C\}, \{D, E\}$
[예제] 유사계수가 다음과 같을 때 집단평균연결 기법에 의한 클러스터링 결과를 보여주시오.
1단계 클러스터링
결과: $\{A, C\}, \{B\}, \{D\}$
2단계 클러스터링
$s(\{A, C\}, \{B\}) = \frac{0.9 + 0.3 + 0.6}{3} = 0.6$
$s(\{A, C\}, \{D\}) = \frac{0.9 + 0.3 + 0.4}{3} = 0.67$
$s(\{B\}, \{D\}) = 0.2$
결과: $\{A, C, D\}, \{B\}$
워드 기법
- 각 클러스터링 단계에서 전체 오류제곱의 합의 증가가 최소가 되는 두 클러스터를 찾아 통합하는 클러스터링 기법
- $E(G)= \sum_{x_i \in G} \lVert x_i - M(G) \rVert ^2$
- 클러스터 $G$에 대한 오류제곱 합 $E(G)$는 클러스터 G의 센트로이드 M(G)와 클러스터에 속하는 문헌 xi 간 제곱 유클리드 거리의 합
- $E(\lambda) = E(G_1) + E(G_2) + \cdots + E(G_N)$
- 클러스터 집합 $\lambda$에 대한 전체 오류제곱 합 $E(\lambda)$은 클러스터 집합을 구성하는 각 클러스터의 오류제곱합을 모두 더한 값
비계층적 클러스터링
- 임의로 생성된 초기 클러스터들로부터 시작하여, 문헌을 보다 유사한 클러스터에 재배치하는 과정을 거쳐, 최종 클러스터 집합을 생성
- 클러스터 센트로이드 (Centroid)
- 클러스터링 과정에서 생성된 클러스터들을 대표하는 중심문헌
- 클러스터에 포함된 문헌들의 평균벡터를 산출
- 예
D1 = (1, 2, 3, 0, 0, 4, 1, 0, 2, 1)
D2 = (0, 1, 2, 0, 0, 3, 1, 1, 0, 1)
D3 = (0, 3, 4, 0, 1, 5, 0, 1, 1, 1)
센트로이드(C1) = (1/3, 2, 3, 0, 1/3, 4, 1, 0, 2, 1)
- 문헌과 클러스터 간 유사도는 문헌의 벡터와 센트로이드의 벡터를 비교함으로써 측정
- 비계층적 클러스터링에서 검토할 중요한 문제
- 초기의 클러스터를 어떻게 산정할 것인가?
- 재배치 과정을 언제 멈출 것인가?
싱글패스 기법
- 클러스터 대상물이 재배치 과정을 거치지 않고 단 한번씩만 처리 대상이 되는 매우 간단한 클러스터링 기법
- 입력된 문헌은 이미 형성된 클러스터에 포함되거나 새로운 클러스터의 중심문헌(센트로이드)가 되는 것
- 싱글패스 알고리즘 처리 과정
- 첫번째로 입력된 문헌은 첫번째 클러스터의 센트로이드가 된다.
- 다음에 입력되는 문헌은 그 시점에서 이미 형성되어 있는 모든 클러스터의 센트로이드와 비교하여 유사도를 산출한다.
- 기존 클러스터와의 유사도가 기준치를 넘으면 이 문헌을 기준 클러스터에 배정하고 해당 클러스터의 센트로이드를 다시 산출한다.
- 기존 클러스터와의 유사도가 기준치를 넘지 않으면 이 문헌은 새로운 클러스터의 센트로이드가 된다.
- 문헌의 입력 순서에 따라 클러스터링 결과가 변하기 때문에 좋은 클러스터링 기준의 하나인 순서독립성을 만족시키지 못한다는 단점 존재
K-means 기법
- K-means 알고리즘 처리 과정
- 임의로 k개의 클러스터 센트로이드(중심문헌)를 선정한다.
- 가장 유사한 센트로이드를 갖는 클러스터로 나머지 문헌들을 배치한다.
- 새로 형성된 클러스터들의 센트로이드를 다시 산출한다.
- 클러스터가 안정되거나 오류제곱 값의 감소가 최소가 될 때까지 2, 3의 과정을 반복한다.
- 싱글패스 기법에 비해 K-means 기법 많이 사용
5. 문헌 클러스터링의 타당성 및 성능 평가
클러스터 타당성 (Cluster Validity) 평가
- 클러스터링 결과 생성된 데이터 구조가 연구 대상인 특정 현상에 대한 통계적인 증거를 제공하는가를 확인하는 방법
- 다음과 같은 질문에 대한 대답을 제공
- 데이터 집합이 작위적인 클러스터링 경향을 갖고 있는가?
- 클러스터링 결과 생성된 계층 구조가 원래의 데이터 집합의 구성원 간 유사관계를 얼마나 잘 반영하는가?
- 문헌 클러스터링 결과가 검색 성능 향상에 효과적인가?
클러스터링 경향 (Clustering Tendency) 검사
- 클러스터링 대상이 되는 데이터 집합이 클러스터링에 적합한가 즉 클러스터링 결과 의미 있는 클러스터들이 생성될 수 있는가를 검사하는 것
- 대개 검색 성능 향상을 목표로 하는 문헌 클러스터링은 상당한 전산 자원을 필요로 하기 때문에 특정한 문헌 집단 또는 데이터베이스가 클러스터링 기법의 적용에 효과적으로 반응할 수 있는지를 미리 평가해보는 것이 필요
- 중복도 검사 (Overlap Test)
- 질의에 대한 적합성 판정이 내려져 있는 문헌 집단에 적용
- 질의에 대해 모든 적합 문헌-적합 문헌 간 유사도와 적합 문헌-부적합 문헌 간 유사도를 산출한 다음 중복도를 계산
- 낮은 중복도 값을 갖는 집단이 높은 중복도 값을 갖는 집단에 비해 클러스터링에 적합한 것으로 판단
- 최근접 이웃 검사 (Nearest Neighbor Test)
- 특정 질의에 적합한 각 문헌이 갖는 n개의 최근접 이웃 문헌 가운데 몇 개가 실제로 적합한가를 반영한 수치를 척도로 사용
- 용어 밀도 검사 (Term Density Test)
- 데이터베이스 내 전체 포스팅(postings: 색인파일 내 색인어 아래 나열된 문헌번호) 수를 문헌 수와 색인어 수를 곱해서 나눈 값으로 밀도를 측정
- 밀도가 높은 문헌 집단이 낮은 집단에 비해 클러스터링 기법을 적용하기에 적합
클러스터링 성능 평가
- 클러스터링 결과 생성된 클러스터의 품질(cluster quality)을 평가하는 것
- 문헌 쌍을 측정의 단위로
- 개별 문헌을 측정의 단위로
클러스터 품질 평가 척도
- 외적 품질(external quality) 척도
- 수작업 분류 결과 생성된 문헌 클래스들과 클러스터링 결과 생성된 문헌 클러스터들을 비교
- 클러스터링 결과가 수작업 분류 결과와 얼마나 유사한가를 측정하는 데에 유용
- 내적 품질(internal quality) 척도
- 수작업 분류 결과 없이 서로 다른 기법에 의해 생성된 문헌 클러스터들을 비교
- 서로 다른 클러스터링 기법들이 얼마나 유사한 클러스터들을 생성하는가 즉 클러스터링 결과의 유사도를 평가하기에 적합
- 클러스터링 결과 생성된 클러스터 집합의 품질을 평가하기 위해 사용
- 클러스터들 간의 유사도는 낮고 동일한 클러스터 내 문헌들 간의 유사도는 높은 기법이 좋은 클러스터링 기법으로 평가
- 랜드 지수 (Rand Index)
- F 척도
- 퓨리티 (Purity) 척도
랜드지수 (Rand Index)
- 문헌 쌍을 사용
- 단순일치계수를 적용하여 두 클러스터 집합 간의 유사도를 측정
- 두 클러스터 집합에 속하는 문헌 쌍들이 각 클러스터 집합에서 동일한 클러스터에 속하는지 여부를 나타내는 2*2 분할표를 이용하여 성능을 평가
- CA : 클러스터링 기법 A에서 생성한 클러스터들
- CB : 클러스터링 기법 B에서 생성한 클러스터들
- a : 두 클러스터 집합에서 모두 동일한 클러스터에 속하는 모든 문헌 쌍의 수
- b, c : 한 클러스터 집합에서만 동일한 클러스터에 속하는 문헌 쌍의 수
- $Rand(CA, CB) = \frac{a+d}{a+b+c+d}$
- 클러스터의 수가 많아질수록 d값이 커지기 때문에 유사도 값이 상대적으로 작아지게 되는 문제점 존재
- CSIM (Cluster SIMilarity) 척도
- 클러스터 집합 CA에서 같은 클러스터에 속한 문헌 쌍이 클러스터 집합 CB에서도 같은 클러스터에 속할 확률
- $CSIM(CA, CB) = \frac{2a}{2a+b+c}$
- 예
CA = {1, 2, 5} {3, 6} {4, 7}
CB = {1, 5} {2, 3} {4, 6, 7} CA 집합에서 같은 클러스터에 속하는 문헌 쌍 : (1, 2) (1, 5) (2, 5) (3, 6) (4, 7)
CB 집합에서 같은 클러스터에 속하는 문헌 쌍 : (1, 5) (2, 3) (4, 6) (4, 7) (6, 7)
a = 2 : CA 집합과 CB 집합에서 같은 클러스터에 속한 문헌 쌍은 (1, 5) (4, 7)이기 때문
b + c = 6
CSIM 값 = 4 / 10 = 0.4
[예제] 8개의 문헌을 클러스터링한 결과 두 개의 클러스터 집합이 형성되었다고 할 때, C1과 C2의 CSIM(Cluster Similarity)를 구하시오.
C1 = ({1, 2, 4}, {3, 5, 6}, {7, 8})
C2 = ({1, 2, 5}, {3, 4}, {6, 7, 8})
C1 집합에서 같은 클러스터에 속하는 문헌 쌍 : (1, 2) (1, 4) (2, 4) (3, 5) (3, 6) (5, 6) (7, 8)
C2 집합에서 같은 클러스터에 속하는 문헌 쌍 : (1, 2) (1, 5) (2, 5) (3, 4) (6, 7) (6, 8) (7, 8)
a = 2 : C1 집합과 C2 집합에서 같은 클러스터에 속한 문헌 쌍은 (1, 2) (7, 8)이기 때문
b + c = 10 : 다른 클러스터에 속한 문헌 쌍
CSIM = (2*2) / (2*2 + 5 + 5) = 4 / 14 = 2 / 7
F 척도
- 개별 문헌을 측정의 단위로 하는 외적 품질 척도
- 자동 생성된 클러스터는 질의에 대해 검색한 문헌들을 포함하고, 수작업 분류클래스는 질의에 대한 적합문헌들을 포함하는 것으로 간주
- 각 분류 클래스에 대한 특정한 클러스터의 재현율과 정확률을 계산하고 이들을 결합하여 F값 산출
- $P(i, j) = \frac{n_{ij}}{n_j}$ (정확률)
- $R(i, j) = \frac{n_{ij}}{n_i}$ (재현율)
- $F(i, j) = \frac{2 P(i,j) R(i,j)}{P(i,j) + R(i,j)}$
- $n_{ij}$ : 클러스터 $j$에 포함된 분류 클래스 $i$의 문헌 수 : $a$
- $n_i$: 분류 클래스 $i$의 문헌 수 : $a + b$
- $n_j$: 클러스터 $j$의 문헌 수 : $a + c$
- 예
분류 클래스: (AC1, AC2, AC3)
클러스터: (BC1, BC2, BC3)
AC1의 문헌 수 = 3
BC1의 문헌 수 = 2
공통된 문헌 수 = 1- P(1, 1) = 1 / 2
- R(1, 1) = 1 / 3
- F(1, 1) = 2 / 5
- P(1, 2) = , R(1, 2) = , F(1, 2) =
- P(1, 3) = , R(1, 3) = , F(1, 3) =
- F(1, 1), F(1, 2), F(1, 3) 중 최대가 되는 F값을 분류 클래스 AC1에 대한 F값으로 선택
- 각 분류 클래스 $i$에 대한 F값은 해당 클래스에 대해 산출된 각 클러스터의 F값 가운데 최대값
- 모든 분류 클래스에 대한 전체 F값은 가중치 $n_i$가 부여된 평균
- $F = \sum_i \frac{n_i}{n} \max F(i, j)$
- $\frac{n_i}{n}$ : 분류 클래스 i의 문헌 수 / 전체 문헌 수
[예제] 분류 클래스는 A = {A1, A2} G = {G1, G2, G3} R = {R1, R2, R3, R4} 이고 클러스터는 C1= {A1, R1, R2, G2} C2= {A2, G1, G3, R3, R4} 일 때 다음 질문에 답하시오.
분류클래스 A에 대한 P(A, C1), R(A, C1), F(A, C1)의 값을 구하시오.
P(A, C1) = 1/4
R(A, C1) = 1/2
F(A, C1) = (2*1/4*1/2)/(1/4+1/2) = 1/3
분류클래스 A에 대한 P(A, C2), R(A, C2), F(A, C2)의 값을 구하시오.
P(A, C2) = 1/5
R(A, C2) = 1/2
F(A, C2) = (2*1/5*1/2)/(1/5+1/2) = 2/7
분류 클래스 G에 대한 P(G, C1), R(G, C1), F(G, C1)의 값을 구하시오.
P(G, C1) = 1/4
R(G, C1) = 1/3
F(G, C1) = (2*1/4*1/3)/(1/4+1/3) = 2/7
분류 클래스 G에 대한 P(G, C2), R(G, C2), F(G, C1)의 값을 구하시오.
P(G, C2) = 2/5
R(G, C2) = 2/3
F(G, C1) = (2*2/5*2/3)/(2/5+2/3) = 1/2
분류 클래스 R에 대한 P(R, C1), R(R, C1), F(R, C1)의 값을 구하시오.
P(R, C1) = 2/4
R(R, C1) = 2/4
F(R, C1) = (2*2/4*2/4)/(2/4+2/4) = 1/2
분류 클래스 R에 대한 P(R, C2), R(R, C2), F(R, C1)의 값을 구하시오.
P(R, C2) = 2/5
R(R, C2) = 2/4
F(R, C1) = (2*2/5*2/4)/(2/5+2/4) = 4/9
전체 분류 클래스 (A, G, R)의 F값을 구하시오.
F = 2/9*1/3 + 3/9*1/2 + 4/9*1/2
F 척도 (Manning)
- F 척도를 문헌 쌍에 적용하여 클러스터링 성능을 평가하는 방법
- b : 같은 분류 클래스에 속하는 문헌 쌍이 다른 클러스터에 속하는 경우
- c : 같은 클러스터에 속하는 문헌 쌍이 다른 분류 클래스에 속하는 경우
- $P = \frac{a}{a+c}$
- $R = \frac{a}{a+b}$
- $F = \frac{2 \times P \times R}{P + R}$
- 예
분류 클래스 A = {A1, A2} G = {G1, G2} R = {R1, R2, R3, R4}
클러스터 C1= {R1, R2, R3, G1, G2} C2= {A1, A2, R4}
$a = 5$ : (R1, R2) (R1, R3) (G1, G2) (A1, A2)
$b = 3$ : (R1, R4) (R2, R4) (R3, R4)
$c = 8$
$P = \frac{5}{13}$
$R = \frac{5}{8}$
$F = 0.476$
[예제] 분류 클래스는 A = {A1, A2} G = {G1, G2, G3} R = {R1, R2, R3, R4} 이고 클러스터는 C1= {A1, R1, R2, G2} C2= {A2, G1, G3, R3, R4} 일 때 3개의 분류클래스(A, G, R)들을 문헌 쌍에 적용했을 경우의 P, R, F값을 구하시오.
$a = 3$ : (R1, R2) (G1, G3) (R3, R4)
$b = 7$
$c = 13$
$P = \frac{3}{3+13} = \frac{3}{16}$
$R = \frac{3}{3+7} = \frac{3}{10}$
$F = \frac{2 \times \frac{3}{16} \times \frac{3}{10}}{\frac{3}{16} + \frac{3}{10}} = \frac{9}{39}$
퓨리티 척도
- $Purity(CA, CB) = \frac{1}{N} \sum_k \max \left \vert W_k \cap C_j \right \vert$
- $CA$ : 분류 클래스 집합
- $C_j$ : 각각의 분류 클래스
- $CB$ : 클러스터 집합
- $W_k$ : 각각의 클러스터
- $N$: 전체 문헌 수
- 각 클러스터와 각 분류 클래스에 공통적으로 속해있는 문헌 수를 산출하여 각 클러스터와 가장 유사한 클래스를 선정한 후 최대 공통 문헌 수를 더하여 정규화 한 것
- 예
클러스터 W1과 가장 유사한 분류 클래스 C1의 공통 문헌 수가 5 (max 값)
클러스터 W2와 가장 유사한 분류 클래스 C3의 공통 문헌 수가 4 (max 값)
클러스터 W3과 가장 유사한 분류 클래스 C2의 공통 문헌 수가 3 (max 값)
퓨리티 값 = 5+4+3 / 전체 문헌 수 - 퓨리티 값 = 0
- 성능이 좋지 않은 기법
- 퓨리티 값 = 1
- 분류 클래스 집합과 클러스터 집합의 내용이 완전히 일치하는 완벽한 클러스터링의 경우
댓글남기기