Big data Analysis 섬머스쿨 - Clustering

JPL-Caltech Virtual Summer school - Big data Analysis(7)

강의 링크 : https://class.coursera.org/bigdataschool-001/wiki/Day_7

참고자료 : http://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html (evaluation 공부에 참고)

Clustering

클러스터링이란 무엇인가?

클러스터링은 비지도학습법(Unsupervised Learning)의 한 방법이다.

Cluster는 다음과 같은 가정으로 작동한다 : 같은 군집의 object들은 정보(attribute)에 비례하여 비슷하게 움직인다. 같은 군집이면 비슷한 위치에 있으며 natural grouping을 찾을 수 있다.

하지만 클러스터링은 주관적일 수 있다. 심슨가족의 예시를 보자

심슨 가족을 성별로 분류할 수도 있고, 극의 역활로 분류할 수 도 있다.

군집을 몇개로 나누냐도 주관적이다. 같은 데이터셋을 2개의 군집, 4개의군집, 6개의 군집으로 나눌 수도 있다. 즉 클러스터링의 라벨 갯수나 방향은 클러스터 모델의 의도에 따라 주관적으로 작동한다.

그러면 왜 클러스터링을 쓰는가?

클러스터링은 데이터 속 서로의 연관관계를 알려준다.(Gene clustering이 대표적인 예시) 또한, outlier를 찾아낼 수도 있다. 

Formal Statement

클러스터는 보통 feature vector D 를 인풋으로 받는다. D = [x1,x2,x3, ... ,xn]를 원하는 클러스터 갯수 k개로 분류한다. object function은 g이며, 우리는 g를 최소화(또는 최대화) 하는  f: D->{1,2,3, ... , k} 를 찾도록 계산한다.

오브젝트 펑션 G는 일반적으로 samples나 cluster들 사이의 similarity나 distance로 정의된다.

클러스터링의 평가(evaluation)

즉 얼마나 클러스터가 잘되었냐는 1. Internel criterion : 같은 클러스터의 거리와 클러스터간의 거리를 통한 평가 2. External Criterion: Direct evaluation 이나 benchmark 등을 사용한다.

internel Criterion의 경우엔 intra clsuet distance는 minimized 되어야 하며, inter cluster의 거리는 maximized 되어야 한다.

하지만 good source가 항상 good effectiveness 를 의미하진 않는다. 또한, algoritm에 따라 biased 될 수 있다. 

External Measures

즉 외부적인 요소로 평가하는 방법이 있다. 이는 클러스터링이 얼마나 실제 class에 맞는지 평가하는 것이다. 이는 labeled sub-sample을 gold standard로 사용한다. 

여기에는 purity, normalized mutual information, rand index, F-measure, Jaccard measure 등이 있다.

Purity 란 무엇인가. 이는 제대로 분류된 샘플들의 비율 이다. 하지만, 만약 각각 cluster가 샘플이 한개라면 항상 1 이라는 문제가 생긴다.

purity 계산의 예시

Normalized Mutual information은 클러스터를 분류했을때 클레스에 대한 정보가 얼마나 gain 되었냐를 가지고 판단한다. 만약 NMI 가 0이라면 이는 class membership과 cluster의 관계가 랜덤하다는 것이다. 만약 cluster가 class에 완전하게 비례한다면 최고 값을 찍는다.

(추가 자료)

NMI 에대한 수식적 증명 ( 출처 : http://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html )

Rand index()는 올바르게 분류된 decisions들의 비율을 의미한다(accuracy)

F-meaure는 RI와 비슷한데 weight를 사용한다.

이때 만약 beta 가 1보다 크다면, 이는 FN에 penalty를 주는 것이다.

Type of Clustering

Hierarchical : 그전에 이미 판별된 클러스터를 통하여 이어지는 클러스터들을 구하는 것 decision tree 같은 방식

 Partitional : non-overlapping subsets으로 data를 나누는 것

다른 구분은

Model based : 처음부터 데이터들은 특정 모델을 가지고 있고 이를 다시 찾아가는 과정으로 clustering을 하는 방식 ( eg.EM )

Density based : cluster를 higher density를 가진곳으로 define 하는 것. sparse area에 있는 애들은 noise나 경계점으로 생각한다 ( eg. DBSACN)

Hierarchical Clustering (계층 클러스터링)

그전에 이미 분류된 subsequent cluster를 찾아서 다음 클러스터를 분류한다. 모든 possible tree를 테스트하지 못한다.

Agglomerative(bottom - up) : 이미 분류된 클러스터에서 시작하여 property에 따라 합쳐가며 위로 올라간다.

Divisive (top - down) : 같은 cluster에 분류된 애들부터 시작하여 점점 아래로 divide 한다.

Hierarchical cluseter는 dendogram으로 시각화 될 수 있다.

Hierarchical clustering의 장점은 클러스터의 갯수를 미리 정할필요가 없고, 직관적으로 이해하기 편하다는 것이다. 하지만 space complexity 가 O(n^2) 라는 치명적이 단점이 있고, global optima를 찾기 힘들며, 주관적으로 clustering 된다는 단점이있다.

Disatance Between Clusters

클러스터간의 거리를 구하는 방법에는 여러가지가 있다. 

이 외에도, Modoid 와 Centroid 의 거리를 이용하여 구할 수 있다.

Similarity Measures

클러스터간의 similiarty는 보통 distance metric 을 이요하여 구한다. distance의 기준들은 위와 같으며 다음과 같은 성질을 만족시켜야 한다.

Distance 자체를 구하는 방법

가장 쉬운 방법은 유클리디안 디스턴스(euclidian distance) 이다. 하지만, 유클리디안 디스턴스는 triangluar unequaliy를 만족시키지 못할 수도 있다는 단점이 있다. 그럼에도 불구하고 가장 많이 쓰이는 방식이다. 일반적으로 구모양의 cluster들이 있을때 사용된다.

멘하탄 디스턴스(menhatan distance) : 멘타한 거리 방식은 두 점사이의 카르테시안 좌표의 차이의 절대값을 사용한다. 이는 보통 다이아몬드 모양의 클러스터에서 사용된다.

Mahalanobis Distance는 점사이에 거리와 distribution을 구하여 사용한다. 

Cosine Similiarity 는 둘 사이의 코사인 값으로 구한다. 이는 두 데이터가 비슷하면 같이 분포되어있고 다르면 멀리 분포되어있을때 유용하다.

Partitional Clustering

기본적으로 Flat clustering 방식이다. 이는 몇개의 클러스터로 나뉠지 결정되어 있어야 한다. Each instance는 하나의 cluster에 할당되며. Hard 와 Soft clustering을 가진다.

Hard clustering은 각각의 샘플이 꼭 하나의 클러스터에 들어가는 것이고(e.g k-means), Soft clustering은 각각의 샘플이 각각 클러스터에 확률(degree)로 들어가는 것이다. (eg, Expectation-Maximization(EM))