Clustering (군집화)

Clustering

클러스터링이란 데이터를 meaningful & useful group으로 나누는 것을 의미한다. 여기서 'meaningful'은 training data가 비슷한 데이터끼리 그룹핑되는 structure를 이해할 수 있어야 함을 의미하고, 'useful'은 전체 training data 모두를 가질 필요 없이 그 크기를 줄여 대표적인 데이터만 가지고 분석할 수 있어야함을 의미한다. 결국 클러스터링은 class(=group/cluster)을 찾는 것을 목표로 하는데, 클러스터링의 정의는 아래와 같이 정의할 수 있다.

 

"Maximize the similarity within a group and Maximize the difference between groups"

 같은 cluster 내의 data는 서로 유사하게 다른 cluster끼리의 data는 상이하게 그룹핑하는 것이다.

 

(사진)

 

하지만 아래 사진을 보면 원본의 데이터를 보고 cluster의 개수를 다 다르게 생각할 수 있다.

그러므로 우리는 여러 번 반복하여 원하는 모양이 나올 때까지 반복해야할 것이다.

 

 

classification , partitioning, segmentation

종종 클러스터링은 classification, segmentation, partitioning으로 여겨지기도 하지만 각각의 차이는 존재한다.

그 차이를 간단하게 표로 정리하였다.

 

classification	supervised (지도 학습) class가 정해진 object로 만든 model을 이용해 새로운 데이터가 들어오면 어느 class에 속할 지 예측
segmentation	unsupervised (비지도 학습) 데이터만 보고 분류
partitioning	단순히 데이터를 여러 그룹으로 나누는 것 ex ) 수입을 기반으로 그룹핑, 이미지를 픽셀과 색상으로 나눔, 구매패턴이 비슷한 고객끼리 그룹핑
clustering	특정 구역으로 나누는 것

 

Types of Clusterings

클러스터링은 다양한 타입이 존재하는데, 각 타입의 특징을 설명할 것이다.

각 타입에 해당하는 알고리즘들은 추후 포스팅에서 설명하고자 한다.

 

Partitional clustering	데이터를 non-overlapping subsets으로 나누는 것
Hierarchical clustering	트리 구조처럼 nested cluster로 만드는 것  각 node는 subcluster를 가지고 있고, root node는 모든 objects을 포함하는 클러스터
Exclusive clustering	각 object은 하나의 cluster에 할당하는 것 (non-overlapping)
overlapping clustering	object는 하나 이상의 cluster에 할당될 수 있음 (non-exclusive)
Fuzzy clustering	모든 object는 각 cluster에 속할 확률을 가지고 있음
complete clustering	모든 object를 무조건 cluster에 속하도록 모두 할당
Partital clustering	모든 object을 cluster에 속하게 하지 않음 noise, outlier, uninteresting background의 경우에는 클러스터에 할당하지 않음
Prototype-based	cluster는 각 object를 대표하는 prototype (e.g., a centroid)을 중심으로 구축됨 원형의 cluster가 많이 형성되는 방식
Density-based
Graph-based	cluster는 서로 유사한 node로만 이루어진 connected component

 

 

Distance Measures

클러스터링은 유사한 점들끼리 그룹핑하는 과정인데, 점들간의 유사도는 거리를 통해 결정된다. 그렇기 때문에 어떠한 거리 개념을 먼저 정의 내려야할 필요가 있다.

 

1) Euclidean distance

 

먼저 유클리드 거리는 가장 흔한? 측정방식으로 우리가 보통 생각하는 거리의 개념이다. 벡터 x, y가 존재할 때 유클리드 거리는 다음과 같이 구할 수 있다.

 

2) Jaccard distance

 

Jaccard distance는 두 개의 집합간의 거리를 측정할 때 사용된다. 먼저 Jaccard Similarity는 집합의 교집합 / 합집합으로 나타내며, 1에서 유사도를 빼주면 Jaccard distance가 된다. 위의 예시에서 두 집합간의 합집합은 8, 교집합은 3이므로 1에서 3/8을 빼주면 distance는 5/8이 된다.

 

3) Cosine distance

 

cosine distance는 두 벡터간의 유사도 측정하기 위함으로 그 각도가 작을 수록 유사하다고 판단한다. cosine distance는 vector x와 y가 존재할 때 두 벡터의 내적 / 두 벡터의 각 크기의 곱 이 된다. 두 벡터의 방향이 완전히 동일한 경우에는 1의 값을 가지며, 90°의 각을 이루면 0, 180°로 반대의 방향을 가지면 -1의 값을 갖게 된다. 즉, 결국 코사인 유사도는 -1 이상 1 이하의 값을 가지며 값이 1에 가까울수록 유사도가 높다.

 

4) Edit distance

Edit distance는 두 문자열 데이터간의 거리로, insertion과 deletion을 최소화하는 거리를 의미한다. 예를 들어 x = abcde , y = acfdeg라고 하면 edit distance는 3이 된다.

1) b를 삭제 → 2) f를 c뒤에 넣음 → 3) e뒤에 g를 넣음

 

하지만 이러한 방식은 문자열이 길어질 수록 적합하지 않기 때문에, LCS(Longest Common Subsequence)를 사용한다.

edit distance = ||x|| + ||y|| - 2*||LCS||

LCS = 왼쪽에서 오른쪽으로 순서대로 가장 긴 sequence의 길이 ( 중요한 것은, 반드시 연속적일 필요가 없다는 것!!!! )

 

위의 예시를 다시 살펴보면 ( x = abcde , y = acfdeg )

||x|| = 5 , ||y|| = 6 , ||LCS|| = 4 이므로, edit distance = 5 + 6 -2*4 = 3

 

 

5) Hamming distance

 

Hamming distance는 벡터가 0과 1로 이루어진 binary형태일 때 각 자리마다 다른 component의 개수를 업데이트한다. 예를 들어, 10101 과 11110라는 두 벡터가 주어졌다면 Hamming distance는 3이된다.