데이터 과학 - 11. Clustering

* Clustering이란 인식된 object들을 구분하는 방법이다. 구분을 하되 따로 label을 매기거나 class를 정의하지는 않는다.(unsupervised learning이므로 y-val이 없다.) 즉, 데이터들을 기반으로 패턴을 발견하여 Similarity에 기반해 grouping을 하는 것이다. Unsupervised Learning problem의 예시로는 Clustering과 Dimensionality Reduction이 있다.

 

* Clustering은 데이터 요약, 압축, KNN Finding, Outlier Detection 등 preprocessing의 도구로 사용될 수 있다.

=> 그렇다면, 무엇이 좋은 Clustering일까?

=> good clustering method는 high quality clusters를 제공하는 것이다.(주관적) 쉽게 이야기하여 다른건 다른 그룹에 비슷한건 같은 그룹에 있어야한다는 말이다. 이 때, clustering method의 quality는 "Similarity"에 따라 달라질 수 있다.

=> "Similarity"는 distance function으로 정의될 수 있다. 즉, 다양한 유형과 차원의 데이터에 대해 어떻게 distance metric을 정의하여 Clustering할 것인지가 중요하다.

(고려될 수 있는 요소 : Partitioning 기준(단일, 계층), Separation of clusters(각 노드당 한 개의 region, 한 노드가 여러 개의 region), Similarity measure(Distance-based, Connectivity based), Clustering space(Full, subspaces)

 

* Clustering의 중요한 사항

1. Scalability : 주어져 있는 데이터를 전부 Clustering 해야한다.

2. 다양한 class들에 대한 distance가 정의되어야 한다.

3. Constraint-based clustering 기능이 필요하다.(학습에 파라미터 사용)

4. Clustering의 결과는 해석하기 쉬워야하며 유용해야한다.

---

* Partitioning Algorithm

-> ci가 Cluster의 centroid 일 때, 다음을 최소화 시키는 방식으로 n개의 object들을 k개의 그룹으로 나누는 것이다.

-> 진짜 모든 노드 하나하나 다 하면서 분류할 수도 있지만, 그건 사실상 불가능한 경우가 더 많다. 따라서 간접적으로 분류를 하는 방법을 사용한다.

---

* K-Means Clustering

k 개의 random center를 선정하고, 주변 노드들을 어떤 center node와 가까운지 기준으로 Clustering을 반복하는 방법이다.(수렴까지)

이러한 데이터가 있다 할 때, k=2 라고 하고 K-Mean algorithm을 적용하자.

2개의 랜덤한 center를 선정한다.

Iteration 0

centor에 가까운 쪽으로 data들이 분류된다.

그 후, 분류된 clustering 결과에 대해 center를 선정한다.

Iteration 1

다시 반복한다.

이렇게 계속 반복하다보면 더 이상 변화가 없는 시점이 온다. 이것이 최종 결과가 된다.

(생각보다 햇갈리는 사람도 있을 수 있는데, K-Means와 K-NN 알고리즘은 다른 알고리즘이다. K-Means는 설명한데로 n개의 노드들을 K개의 Cluster로 분류하는 clustering 알고리즘이고, K-NN 알고리즘은 자신의 주변에 있는 node들을 voting해서 자신의 class나 value를 정하는 supervised learning 알고리즘이다.)

---

* Properties of Distance Measure

Distance metric은 어떤 특성을 가지고 있어야할까? 현실에서 거리를 생각하면 이해가 편하다.

1. Symmetric : D(A, B) = D(B, A)

2. Positive : D(A,B)>=0

3. Self-similarity : if A=B, D(A, B) = 0

4. Triangle inequiality : D(A, B)+D(B, C) >= D(A, C)

(쉽게 말해서 A->C로 직행하는 것 보다 어떤 점 B를 들렀다 가는 것이 무조건 더 크거나 같을 수밖에 없다.)

---

* Minimizing Inertia

다음과 같은 K=4 K-Means Clustering 결과가 있다고 해보자.

K-Means를 실행할 때마다 초기 Random center에 따라 다른 결과를 가져올 수 있다.

그럼 당연히 '저 중 뭐가 제일 좋은건데?'라는 생각이 들 수 밖에 없다. 처음에 떠오르는 방법은 loss function을 정의하는 것이다. K-Means에서 쓰이는 loss function은 Inertia(center로부터의 거리 square 총합), Distortion(center로부터의 weighted squared distance 총합)

그러면 Inertia든 Distortion이든 작을 수록 error가 적다는 뜻이라고 해석이 가능해진다.

따라서 3개의 random.seed K-means Clustering result data들 중에서 왼쪽이 가장 좋음을 알 수 있다.

---

다시 K-Means로 돌아와서 생각해보자. 데이터 마이닝이란 과목이 그냥 수치 놀음이 아니란 것을 해당 사진으로부터 알 수 있다. 앞서 loss function으로 정의된 Inertia가 작을 수록 high-quality라고 볼 수 있다고 했다. 그러면 무조건 오른쪽의 결과가 좋은 결과일까?

"설명력"의 관점에서 보면 B보단 A가 훨씬 이해되기 쉽다는 것을 알 수 있다. 그렇다고 B가 잘못된 결과인 것도 아니다. Inertia 등 Distance based loss function의 특성 상, 거리가 줄어드는 쪽으로 최적화가 맞춰져서 일어나는 현상이며, 어떤 관점에서는 B가 더 좋은 결과일 수 있다. 따라서, 최종적으로는 어떤 데이터를 사용할지 결정하는 사람이 중요하다는 의미를 이해할 수 있다.

이런 경우, K-Means는 제대로 Clustering을 해내게 쉽지 않다. 이렇게 X,Y based feature가 구성될 시, K-Means를 적용하려면 다음과 같이 Feature transform을 해주는 방법을 사용할 수 있다.

X,Y 에서 반지름, 세타 값으로 Feature를 수정하였다.

 

* Hierarchical Agglomerative Clustering

각 데이터 포인트를 독립적인 Cluster로 두고 시작하여 점차적으로 유사한 Cluster를 병합하는 방식이다.

1. 처음에는 각 데이터 포인트를 개별 클러스터로 취급한다.

2. 가장 유사한 pair의 데이터 포인트나 cluster를 지속적으로 합치며 Clustering 과정을 반복한다. (bottom-up)

=> Cluster를 합칠 순서를 결정하는 다양한 기준을 "Linkage Criterion"이라고 한다. Linkage Criterion에는 minimum, maximum, average가 있으며, 이는 Cluster 간의 유사성을 측정하는 방법에 따라 달라진다.

 

- Linkage Criteria의 종류

1. Single linkage : cluster 간 거리를 최소화 하는 방향

2. Complete linkage : cluster 간 관계를 최대화하는 방향

3. Average linkage : cluster의 point 들의 평균을 similarity로 사용함.

Ex) (Single linkage)

=> 12개의 데이터 포인트가 있으므로, 12 cluster가 존재한다. 10,11이 가장 가까우므로, 이들을 Clustering 한다.

=> 다음은 0,4가 가까우므로 이들을 clustering 한다. 이를 정해준 k개의 cluster가 형성될 때까지 반복한다.

이 때, 3과 가장 먼 0이 3과 0의 거리가 된다. (Complete-Link approach)

Merging History Visualization

=> Agglomerative Clustering은 hierarchical clustering의 한 형태이다.

---

* Picking K
=> 계속 설명하며 사전에 몇개의 Cluster를 구할지 K 값을 정해야한다고 했다. 그런데 이 K 값은 어떻게 정해야할까?

 

- elbow method

=> 다양한 K 값에 대해 Inertia 그래프를 그리고 적당한 K를 선정하는 것이다. (보통 팔처럼 생겼다고 보고 elbow 쪽을 고른다.) 그러나 이 방법은 복잡한 대형 데이터에서는 사용하기 어렵다.

 

- Silhouette Scores

=> 얼마나 잘 클루스터링되었는지 따지는 metric으로는 Silhouette Score도 고려될 수 있다. 

A는 각 데이터 포인트 X에 대해 동일한 cluster 내의 모든 다른 포인트 들과 X의 평균 거리이다.

(자신과 해당 Cluster가 얼마나 잘 맞는지 판별)

B는 X에서 가장 가까운 다른 cluster의 포인트들과의 평균 거리로, X가 다른 Cluster에 속해야할 가능성을 나타낸다.

S는 1~-1을 가질 수 있다. B가 크고 A가 작으면 작을 수록 자신이 속한 Cluster의 중앙에 있는 것이다.

상단은 k=2 case, 하단은 k=3 case

=> k=3일 때 Average silhouette score가 더 낮으므로 k=2가 더 좋게 평가될 여지가 있다.

이러한 수치적 접근 외에도 옷 size를 xs,s,m,l,xl 로 나누는 등 현실 세계에서 주로 사용하는 k 값을 사용하는 등 현실 세계 기반 방법이 있다.