Clustering Algorithm LINK @ KUT Youn-Hee Han

What is Clustering? 클러스터링이란 밀접히 관련된 사물, 사람, 아이디어 들의 그룹을 찾는 기법 데이터 세트 내에서 유사항목을 가진 그룹을 검출 어떠한 올바른 답을 찾는 것이 아니고 데이터 집합 내에서 구조를 발견하는데 목적이 있음 보통 그룹핑의 결과를 시각화하는 것 까지 포함 Algorithm

What is Clustering? 클러스터링 응용의 예 고객이 구매한 상품을 기록하는 소매상은 일반적인 통계적 정보와 이 구매정보를 활용하여 유사한 구매 행태를 가진 고객 그룹들을 자동으로 검출 Algorithm

Clustering Algorithms Algorithms based on cluster structure Single-link Hierarchical Average-link MST-based Single-link Cluster Schemes MST: minimum spanning tree K-means Partitional Nearest Neighbor Algorithm

Adjacency Matrix(인접행렬) 유사도(인접도) 형성 각 클러스터 간의 각각의 속성(Attribute)들에 대하여 유사도(Similarity)를 산정 <- Original Data Set Algorithm

Adjacency Matrix(인접행렬) 유사도(인접도) 형성 주어진 데이터 셋을 기반으로 유클리디안 거리, 피어슨계수 등으로 유사도를 산정하여 행렬 구성 Algorithm

유사도 산정 방식 - I 유클리디안 거리점수 Q) Point A( x=24, y=3)와 Point B (x=12, y=11)의 Euclidean Distance? Algorithm

유사도 산정 방식 - II 피어슨 상관계수 두 개의 데이터 집합이 한 직선으로 얼마나 잘 표현되는가를 나타내는 측정값 유클리디안 거리점수보다 공식이 더 복잡하지만 잘 정규화되지 않은 데이터의 경우에도 훨씬 나은 결과를 제공 Algorithm

유사도 산정 방식 - III Cosine 유사도 The resulting similarity −1 : exactly opposite, 1 : exactly the same, 0 : indicate independence, in-between values : indicating intermediate similarity or dissimilarity. Algorithm

Hierarchical clustering 계층적 군집화 가장 유사한 두 그룹을 계속 병합하는 방식으로 그룹 계층을 만듬. 개별 항목으로 시작하여 매 반복마다 이 함수는 모든 그룹 쌍 간의 인접성을 계산하여 인접성이 가장 높은 것 것들끼리 함께 병합하여 새로운 그룹을 생성 이 과정을 최종적으로 한 개 그룹만 남을 때까지 반복 계층적 군집화 종류 Agglomerative: 아래에서부터 위로(개별 항목부터 시작하여 수퍼(최종)클러스터까지 병합) Divisive: 수퍼 클러스터부터 시작하여 개별 항목이 남을 때까지 나눔 Algorithm

Hierarchical clustering 계층적 군집화 실행모습 Algorithm

Hierarchical clustering 계층적 군집화가 진행되거나 끝난 후의 최종 모습은 다음과 같은 Dendrogram (계통도) 형태가 된다. A C D B E 1 2 3 4 Algorithm

Hierarchical clustering Single-link algorithm 클러스터 내의 여러 점들 중 두 개의 점의 인접성이 가장 작은 것들 부터 병합하는 알고리즘 Average-link algorithm 클러스터 내의 여러 점들간의 거리 평균에 대한 인접성이 가장 작은 것들 부터 병합하는 알고리즘 Algorithm

Partitional clustering 분할적 군집화 사전에 생성할 군집의 개수를 지정하는 방식 대표적으로 K-means algorithm이 있다. Algorithm

Partitional clustering K-means algorithm 무작위로 선정된 k개의 중심점을 선정하고 그 점에서 가장 근접한 항목들을 클러스터에 할당 할당 후에는 할당된 모든 노드들의 평균 위치로 중심점을 이동시키고 재할당을 수행 할당이 더 이상 없을 때까지 이 과정을 반복 실행시간이 빠르다는 장점이 있으나 적절한 초기 입력값 K의 선정이 중요 노드들의 중심점(centroid) Algorithm

Partitional clustering K-means algorithm 실행모습 (K=2) Algorithm