Data Clustering Algorithm

군집화 Clustering

데이터를 모아놓았을 때 가장 궁금해하는 것 중 하나. 

 

무슨 데이터가 서로 비슷하고 무슨 데이터가 서로 다른가?

데이터를 서로 유사한 군집으로 나눌 수 없을까?

 

Clustering은 예측이 아닌 분석이다. 즉 정답이 존재하지 않는다. ( Output Variable X)

Unsupervised learning

데이터의 분포나 경향을 파악하기에 좋다.

향후 예측을 위한 사전 단계가 될 수 있다.

 

군집화의 기준은?

데이터간의 유사도

유사한 데이터는 하나의 군집 안에 묶일 수록 좋다.

유사하지 않은 데이터는 서로 다른 군집에 속할 수록 좋다.

유사도는 거리의 역수. → 군집화는 거리 기반.

 

ex)

숫자로된 Data Set을 갖고 있다 가정했을 때

무엇이 이상한 Data?, 무엇이 남과 다른 Data?, 어떤 Data가 서로 비슷한가?

유사함/이상함의 기준은 데이터간의 거리로 생각한다.(distance)

 

군집화를 하는이유

각 군집 별로 패턴을 파악할 수 있다.

각 군집 별로 대응을 분리해서 할 수 있다.

아무 군집에도 속하지 않는 이상한 데이터(특이값)을 찾아낼 수 있다.

 

군집화 방법론

비계층적(non-Hierarchical Clustering) 방법론

• k-means clustering
• DBSCAN

계층적(Hierarchical Clustering) 방법론

• Agglomerative
• Divisive

 

K-means Algorithm

대표적인 분리형 군집화 알고리즘.

중심(centroid)를 가진다. 객

1. 군집의 개수 k를 정한다.

2. k개의 초기 군집중심(centroid)을 설정한다. → 최초에는 random한 값

 

3. 아래 과정을 반복한다.

3.1 모든데이터와 군집 중심 사이의 거리를 계산한다.

3.2 각 데이터를 가장 가까운 군집으로 할당한다. (assign)

3.3 할당된 데이터에 기반해서 군집 중심을 갱신한다 (update)

4. 종료조건이 만족하면 알고리즘을 종료한다.

 

K 정하기

 

→ 위에서 정해주는 숫자, 경험적으로 이미 알고 있는 숫자 (과학적이지 못하다)

 

→ 서로 다른 k를 test해보고 좋은 k 정하기

• 서로다른 k에 대해 군집화 결과 평가.
• 가장 좋은 평가를 받은 k를 정한다.
• 정량적 방법(평가를 정량적으로)

좋은 초기 군집중심을 잡으면 좋은 결과를 얻을 수 있다.

단 나쁜 초기 군집중심이 잡히면 회복이 안된다.

 

k-means는 비슷한 크기의 원(구) 형태의 군집을 생성하려는 경향이 있다.

군집 마다 크기, 밀도, 모양이 다를 수 있다.

 

군집화 결과평가

 

Infra/Inter cluster scatter

Infra cluster = 군집 내 거리 = 가까울 수록 좋다. (같은 군집)

Inter cluster = 군집 간 거리 = 멀 수록 좋다. (다른 군집)

 

 

Scatter Ratio

장점

• 직관적으로 이해하기 쉽다.
• 데이터 사이즈에 큰 영향을 받지 않는다. O(nkt)
• 거리계산 + 정렬이므로 구현이 편하다.

단점

• 데이터의 모양 및 밀도에 영향을 받는다
• k값을 정하는 문제와 초기 군집중심을 잡는 문제가 open problem (np 문제)

 

 

 

... 향후 작성 목록 

 

K-medoids Algorithm

 

Centroid-based-clustering Algorithm

 

Single-link Algorithm

 

Completed-link Algorithm

 

 

DBSCAN ( Density-Based Spatial Clustering of Applications with Noise ) Clustering

밀도에 따라 Clustering 하는 알고리즘. 

 

EM (Expectation-Maximization) Clustering

 

Probablistic Latent Semantic Indexing(PLSI)