정보검색론 5. 문헌 클러스터링 (2)

5.4. 클러스터링 기법

계층적 클러스터링 기법

* 응집적 알고리즘 : N개의 클러스터에서 출발해 N-1번의 결합과정을 거쳐서 한 덩어리로 뭉쳐짐. 주로 사용됨.

* 분열적 알고리즘 : 1개의 클러스터에서 출발해 N-1번의 분열과정을 거쳐서 N개의 클러스터로 나눠짐.

클러스터간의 유사도를 측정하는 방법에 따라 다음과 같이 구분할 수 있다.

* 단일연결 : 두 클러스터 간의 유사도가 가장 가까운 구성원 사이의 거리를 유사도로 측정.

* 완전연결 : 두 클러스터 간의 유사도가 가장 먼 구성원 사이의 거리를 유사도로 측정.

* 집단평균 : 모든 구성원 사이의 유사도를 평균내서 이를 유사도로 측정.

* 워드기법 : 오류제곱의 합이 최소로 증가하는 결합을 행함.

5.4.1.1. 단일연결 기법

문헌 A, B, C, D, E의 거리 계수 행렬은 아래와 같다.

	A	B	C	D	E
A
B	1.0
C	4.0	2.0
D	9.0	9.0	5.0
E	8.0	8.0	6.0	2.5

상태1. A, B, C, D, E

가장 가까운 클러스터 쌍을 찾아 통합한다. D(A,B)가 1.0으로 제일 작으므로 A, B가 통합된다.

상태2. {A, B}, C, D, E

역시 가장 가까운 클러스터 쌍을 찾아 통합한다. D({A, B}, C)는 D(A, C)=4, D(B, C)=2이므로, 둘 중에 더 가까운 값인 2로 결정된다. {A, B}와 C의 거리가 제일 작으므로 통합된다.

상태3. {A, B, C}, D, E

가장 가까운 클러스터 쌍을 찾아 통합한다. D(D, E)가 2.5로 제일 작으므로, D, E가 통합된다.

상태4. {A, B, C}, {D, E}

D({A, B, C}, {D, E})는 C와 D의 거리가 5로 제일 작으므로, 5로 결정된다. 마지막으로 {A, B, C}와 {D, E}가 통합된다.

5.4.1.2. 완전연결 기법

위와 같은 표를 이용해서 완전연결 기법으로 클러스터링해볼것이다. 완전연결 기법에서는 D({A, B}, C)가 D(A, C)=3와 D(B, C)=2 중에 가장 큰 값인 3으로 결정된다.

상태1. A, B, C, D, E

가장 가까운 클러스터 쌍을 찾아 통합한다. D(A,B)가 1.0으로 제일 작으므로 A, B가 통합된다.

상태2. {A, B}, C, D, E

역시 가장 가까운 클러스터 쌍을 찾아 통합한다. D({A, B}, C)는 D(A, C)=4, D(B, C)=2이므로, 둘 중에 더 먼 값인 4로 결정된다. {A, B}와 C의 거리보다 D,E의 거리가 2.5로 더 작으므로 D, E가 통합된다.

상태3. {A, B}, C, {D, E}

가장 가까운 클러스터 쌍을 찾아 통합한다. D({A, B}, C)는 4이고, D(C, {D, E})는 6이므로, {A, B}와 C가 통합된다.

상태4. {A, B, C}, {D, E}

D({A, B, C}, {D, E})는 A와 D의 거리가 9로 제일 크므로, 9로 결정된다. 마지막으로 {A, B, C}와 {D, E}가 통합된다.

5.4.1.3. 집단평균연결 기법

집단평균연결 기법에는 집단 간 평균과 집단 내 평균이 이용될 수 있는데, 집단 간 평균은 집단 내 평균과는 달리, 같은 집단 내에 속하는 문헌간의 거리를 평균계산에 넣지 않는다. 위의 표를 이용해서 집단 간 평균 기법으로 클러스터링해본다.

상태1. A, B, C, D, E

가장 가까운 클러스터 쌍을 찾아 통합한다. D(A,B)가 1.0으로 제일 작으므로 A, B가 통합된다.

상태2. {A, B}, C, D, E

역시 가장 가까운 클러스터 쌍을 찾아 통합한다. D({A, B}, C)는 D(A, C)=4, D(B, C)=2이므로, 둘의 평균 값인 3로 결정된다. {A, B}와 C의 거리보다 D,E의 거리가 2.5로 더 작으므로 D, E가 통합된다.

상태3. {A, B}, C, {D, E}

가장 가까운 클러스터 쌍을 찾아 통합한다. D({A, B}, C)는 3이고, D(C, D)=5, D(C, E)=6이므로 D(C, {D, E}) 는 5와 6의 평균인 5.5가 된다. {A, B}와 C가 통합된다.

상태4. {A, B, C}, {D, E}

D({A, B, C}, {D, E})는 D(A, D)=9, D(A, E)=8, D(B, D)=9, D(B, E)=8, D(C, D)=5, D(C, E)=6의 평균인 7.2로 결정된다. 마지막으로 {A, B, C}와 {D, E}가 통합된다.

5.5.1. 클러스터 타당성 평가

문헌 클러스터의 타당성 평가는 다음과 같은 질문에 대답을 제공한다.

* 데이터 집합이 nonrandom한 클러스터링 경향을 갖고 있는가?

* 클러스터링 결과 생성된 계층 구조가 원래의 데이터 집합의 구성원 간 유사관계를 잘 반영하는가?

* 검색 성능 향상에 효과적인가?

클러스터링 경향 검사

* 중복도 검사

* 최근접 이웃 검사

* 용어 밀도 검사

5.5.2. 클러스터링 성능 평가

* 외적 품질 척도: 수작업 분류 결과와 클러스터링 결과를 비교함

* 내적 품질 척도: 서로 다른 기법에 의해 생성된 클러스터링 결과를 비교함

랜드지수

		클러스터집합B
		포함	비포함
클러스터집합A	포함	a	b
	비포함	c	d

인데, d의값이 커질수록 유사도의 값이 작아지기 때문에 CSIM지수를 더 자주 사용한다.

CSIM 지수

집합A와 집합B에서 같은 클러스터에 속하는 문헌쌍을 모조리 뽑아서, 겹치는 쌍의 수가 a, A에만 등장하는 쌍의 수가 b, B에만 등장하는 쌍의 수가 c.

F척도

1. 문헌 수 이용 방법

수작업으로 분류한 클래스와 클러스터링으로 분류한 클래스를 비교하여 P, R을 구해낸뒤 F척도를 계산함.

		클러스터
		포함	비포함
수작업	포함	a	b
	비포함	c	d

정확도 P = a / (a+c)

재현률 R = a / (a+b)

f = 2PR / (P+R)

로 계산하고,

가중치를 부여하여 전체 클러스터링의 척도 F는 다음과 같이 구한다.

2. 문헌 쌍 이용 방법

CSIM지수를 구할때처럼, 수작업 분류 클래스의 모든 문헌쌍을 끄집어내고, 자동 클러스터링 클래스의 모든 문헌쌍을 끄집어내어

f = 2PR / (P+R) 공식에 대입하여 계산한다.

정영미, 2012, [정보검색연구], 연세대학교 출판 문화원.