위키득계정 ↗
기술

친화도 전파 군집화

친화도 전파 군집화기술
영문명
Affinity propagation
대표점
자료에 실제 존재하는 표본
주요 설정
선호도와 감쇠 계수
주요 입력
표본 사이의 유사도
친화도 전파 군집화는 표본 사이에 대표점 선택에 관한 메시지를 주고받아 군집과 대표 표본을 찾는 방법이다. 군집 수를 직접 지정하는 대신 표본 간 유사도와 대표점 선호도 등이 결과에 영향을 준다.

대표 표본을 찾는 관점

세 표본의 위치가 0,2,9일 때 대표점을 2 하나로 두면 다른 표본을 그 대표점으로 설명해야 한다. 대표점이 0과 9라면 가까운 두 표본과 멀리 떨어진 한 표본을 나누는 구성이 가능하다. 친화도 전파는 각 점이 누구를 대표점으로 삼을지, 해당 점이 대표점으로 적합한지에 관한 메시지를 반복해 갱신한다. 대표점은 평균 좌표처럼 새로 만든 점이 아니라 실제 표본에서 선택한다.

선호도에 따른 비교

서로 다른 점 사이의 유사도를 음의 제곱거리로, 각 점의 자기 선호도를 p로 두자. 대표점 2 하나인 구성의 유사도 합은 p-53이다. 대표점 0,9인 구성은 2p-4이고 모두 자신을 대표하면 3p이다. p=-10이면 차례로 -63,-24,-30이므로 이 세 후보 중에서는 두 대표점 구성이 가장 큰 합을 갖는다. 이는 선호도의 역할을 설명하는 후보 비교이며 실제 반복 알고리즘의 수렴을 보장하는 계산은 아니다.

메시지의 감쇠

새 메시지 값을 바로 전부 적용하면 반복 중 값이 흔들릴 수 있다. 감쇠는 이전 값과 새 값을 섞어 갱신을 완만하게 하는 장치다. 감쇠를 주었다는 사실만으로 항상 올바른 군집이나 수렴이 보장되지는 않는다. 선호도, 초기 상태, 반복 제한을 바꿨을 때 대표점과 군집이 얼마나 달라지는지 확인한다.

결과와 비용

유사도는 값이 클수록 더 잘 맞는다는 의미로 정해야 한다. 큰 값이 멀리 떨어졌다는 뜻인 거리 행렬을 그대로 넣는 것과는 다르다. 표본 쌍의 행렬을 다루므로 자료가 많으면 메모리와 계산 부담이 커질 수 있다. 수렴하지 않았더라도 결과 배열이 나오는 구현이 있어 종료 상태를 확인해야 한다. 군집 수가 자동으로 정해진다는 이유만으로 결과가 객관적으로 유일한 것은 아니다.

관련 문서

군집화 / K 평균 군집화 / 평균 이동 군집화 / 스펙트럴 군집화 / 유클리드 거리 / 기계 학습