Clustering

군집분석은 데이터마이닝(통계), 기계학습분야에 있는 이론이다. 기계학습에서 이 군집분석이 들어가는 카테고리는 비지도학습(Unsupervised Learning), 다르게 말하면 비교사학습이다. 통계에서는 데이터마이닝쪽에 들어가게 되고 이 데이터마이닝이 패턴인식 혹은 통계적규칙을 찾아내는 학문인데, 이러한 군집분석은 특성에 따라 데이터의 패턴이나 규칙을 통해 여러개의 집단으로 나누는 것이므로 이러한 마이닝 분야에 들어갈 수 있겠다. 군집화는 예측보다는 지식의 발견에 사용된다. 마이닝에서 군집분석의 첫번째 목적은 적절한 군집으로 나누는 것이고, 두 번째 목적은 각 군집의 특성, 군집간의 차이 등에 대해 분석하는 것이다.

사실 엄밀히 말하면 데이터마이닝과 기계학습 분야에서의 clustering의 의미는 약간 다르다. 데이터 마이닝에서는 결과그룹들이 주요 관심사지만, 자동분류(기계학습분야)에서는 결과 구별능력이 주요 관심사이기 때문이다. 이는 그들이 같은 용어와 종종 같은 알고리즘들을 쓰나 목표가 다르기 때문에 구별되어야된다.

정리해 보면 군집분석은 데이터의 군집(Cluster)를 찾는 방법이다. 기본적인 골격은 동일한 군집에 속한 개체는 서로 닮고, 다른군집에 속한개체는 다르다는 것이다. 좀 더 풀어서 쓰면 다양한 데이터를 작은 수의 그룹으로 구분하는데 복잡성을 줄이고 관계의 패턴에 대한 의미있는 데이터 구조를 만든다. 끝이다 이게 군집분석의 전부다.

Cluster의 정의를 엄격히 내리거나 객관적으로 딱 올바른 클러스터링 알고리즘은 없다. 모든 분석 혹은 기계학습이 그렇듯 데이터에 따라 그에 맞는 알고리즘을 선택하는 것이 정답이다.

본격적으로 들어가기 전에 Clustering의 전형적인 종류들에 대해서 알아보자.

• Connectivity models : 예를 들어,Hierarchical clustering은 거리 연결성에 기초한 모델들을 세운다.

• Centroid models : 예를들어, K-means 알고리즘은 하나의 단일 평균벡터로 각 클러스터를 나타낸다.
• Distribution models : Cluster들은 EM 알고리즘에서 사용된 다변량 정규분포같이, 통계분포들을 사용하여 Cluster들을 모델링한다.
• Density Models : 예를들어, DBSCAN 과 OPTICS는 클러스터를 데이터 공간에서 연결된 밀도 지역들로 정의한다.
• Subspace models : Biclustering(Co-clustering 또는 two-mode-clustering이라고도 알려짐.)에서 클러스터들은 Cluster members와 연관 특징들(변수들)로 모델링 된다.
• Group models : 몇몇 알고리즘들은 그들의 결과에 대해 정제?(refined)된 모델을 제공하지 않는다. 단지 그룹핑된 정보들만을 제공한다.
• Graph-based models : subset에서 모든 2개의 노드들이 한 엣지에 의해서 연결되어 지듯 한 그래프에서 노드들의 subset(clique)은 하나의 견본적인 형태의 클러스터로 여겨질 수 있다. HCS clustering algorithm에서와 같이, 완전 연결 요구의(엣지들의 한 부분은 유실될 수 있다.) relaxation들은 quasi-cliques로 알려졌다. 

또는 크게 Hard clustering 과 soft clustering으로 나뉘어 지기도 한다.(위키참조)

더 세분화된 구별은

• strict partitioning clustering: 한 클러스터에 각 객체들이 속해있다.
• strict partitioning clustering with outliers: 어느 클러스터에도 들지 못한 객체가 있으며, 아웃라이어로 취급된다.
• overlapping clustering (also: alternative clustering, multi-view clustering): 보통 hard clustering(하나당 한개의 클러스터에 할당되는거)로 취급되지만, 한 객체가 하나이상의 클러스터에 들어갈 수도 있다.
• hierarchical clustering: 자식 클러스에 들어가 있는 개체가 또한 부모클러스터에도 들어가 있는것.(당연한말 아닌가?..)
• subspace clustering: overlapping clustering과는 반대로, 유일하게 정의된 subspace에서 , 클러스터들은 겹치지 않는다. 

전체적인 분류는 이렇다. 

그렇다면 문제점은 무엇인가?

어떤 측정( 혹은 측정조합)이 군집에 개별 데이터를 각각 할당하는 가장 좋은 방법인지 알 수 없다. 이러한 할당을 실행하는 3가지 방법은

1. K-means와 같은 함수를 사용해 사용자가 군집의 수를 (임의로) 설정한후 분할함. (전통적 군집분석)

2. 분리된 개별 개체를 hclust와 같은 함수를 사용해 이를 하나로 묶는 계층적 방법(hierrarchical clustering)

3. 모든 개체를 하나로 묶은 후 이를 모든 개체가 서로 다른 군집으로 분리 될 때 까지 나누는 분할법(아마..nonhierarchical clustering?)

그럼 1번째 방법인 분할 방법은 고객등급과 고객분(신규/기존)이라는 두 변수로 나누거나, 현재가치와 미래가치를 기준으로 4분면이나 9개 집단으로 나누는 등 다양한 방법들이 있다. K-means 함수에 대해서는 다음 포스팅에서 자세히 다루겠다.

이러한 분할 방법은 변수를 선정하고 구간대로 나눈다음, 이를 기준으로 격자형으로 단순히 나누고 집단이 적으면 병합하는 식과 단순 클러스터링, K-means가 있는데, 문제는 단순 격자형은 작업에 오랜시간이 소요되고, 후처리로 병합시 원칙이 명확하지 않다는 것이다. 사실 이유가 이해가 안되는데, 분리된 격자셀의 프로파일을 보고 유사한 근처 집단으로 나누어야 하는데, 집단간 프로파일에 차이가 나지 않는 경우가 있다. 물론 세분화 변수와 프로파일링 변수는 달라야한다. 그리고 격자나 cluster, K-means의 공통적인 문제는 변수의 특성으로 인한 변동에 따라 의미없이 고객 집단이 이동하게 된다는 것이다. A,B,C집단이 유지돼도 분포가 매우 틀리고 A,B,C1으로 프로파일 자체가 변하는 일이 생긴다.  해결책은 K-means에 SRM을 결합해 세분집단의 변화가 많지 않게 한 것이다.

2번째 방법은 계층적 군집 분석이다. 표본의 집합 중 어떤 것이 서로 가장 비슷한지 보여주고 이런 비슷한 표본을 트리의 동일한 가지로 묶어주는 것이다. 서로 다른 표본 그룹은 다른 가지에 위치하게 된다. 여기서 사용되는 기술은 '가장 유사함'의 뜻을 정의 하는 방법이 필요하다. 각 표본은 데이터 프레임 내의 m개의 변수로 정의된 m차원의 공간에 있다고 가정할 수 있다. 이 m 차원 공간에서 두 표본간의 거리에 근거해 유사도를 정의할 수 있다. 일부 다른 거리 측정 방법(유클리드, 맨하탄, 캔버라, 민코우스키 등)이 사용 될 수 있지만 기본적으로 유클리드 거리를 사용한다. 이런식으로 모든 표본에 대해서 다른 모든 표본들과의 거리를 측정한다. 그렇다면 이제 데이터간의 거리를 측정 했지만 어느 순서 혹은 어느 기준으로 묶어 나갈지가 문제다. 즉 군집간 거리에 대한 정의가 필요하다. 이렇나 군집간 거리를 정의하는 방법으로는 최단연결법, 최장연결법, 평균연결법, 와드연결법(편차들의 제곱합이 가장 작은것부터 묶는 방법)이 있다. 이렇게 군집간의 거리, 자기 자신의 군집에 속해 있는 각 표본을 대상으로 hclust 알고리즘을 반복 실행하여 각 단계마다 두개의 가장 유사한 클러스터를 합치는 과정을 단 하나의 클러스터가 남을 때까지 반복한다.

실제의 경우 데이터를 생성할때 이미 최선의 그룹 갯수를 알면 오차가 적게 발생하고, 작업량이 적겠지만 모른다면 수없이 많은 오차가 발생할 것이다. 

3번째 방법은 비계층적 군집분석이다. n개의 개체를 g개의 군집으로 나눌 수 있는 모든 가능한 방법을 점검해 최적화한 군집을 형성하는 것이다. 대표적 방법으로 K-means 가 있는데.

1. 원하는 군집의 개수와 초기값들을 정해 seed 중심으로 군집을 형성한다.(사실 이 초기값을 설정하는데 문제가 있음. 그게 K-means의 문제)
2. 각 데이터를 거리가 가장 가까운 seed가 있는 군집으로 분류한다.
3. 각 군집의 seed값을 다시 계산한다.
4. 모든 개체가 군집으로 할당될 때까지 위 과정들을 반복한다.

K-평균법은 계층적 군집 방법과는 달리 한 개체가 속해 있던 군집에서 다른 군집으로 이동해 재배치가 가능하다. 초기값에 의존하는 방법으로 군집의 초기값 선택이 최종 군집 선택에 영향을 미친다. 몇가지 방법으로 초기값을 선택한 후 결과를 비교하는 것이 유용하다. 

비계층적 군집화의 장점 (계층적 군집화의 단점)은 

1. 주어진 데이터의 내부구조에 대한 사전정보 없이 의미 있는 자료구조를 찾을 수 있는 방법이다.
2. 다양한 형태의 데이터에 적용가능하다. 즉 관찰치 간의 거리를 데이터형태에 맞게 정의하면 모든 형태의 데이터에 대해 적용이 가능한 방법이다.
3. 분석방법의 적용이 용이하다.

비계층적 군집하의 단점 (계층적 군집화의 장점)은

1. 가중치와 거리정의가 어렵다.
2. 초기 군집수를 결정하기 어렵다.
3. 사전에 주어진 목적이 없으므로 결과 해석이 어렵다.
   
   

정리를 해보자 전통적 군집분석은 한마디로 사람이 정한 다시말해 데이터의 거리를 재거나 군집간 거리의 정의 같은 기준이 없이, 사회적 통념상의 기준같은 주관적 기준으로 데이터 군집을 나눈다는 말이고, 계층적 군집과 비계층적 군집은 객관적 기준(데이터 거리 측정)으로 군집을 나눈다는 측면에서는 같으나, 고정된 초기값( 초기 군집개수)의  유/무와 군집 간 거리의 정의 유/무로 둘의 구분이 생긴다. 그런데 전통적 군집분석과 비계층적 군집에서는 K-means가 이 둘다에 포함되는 것 같다. 왜냐하면 일단 초기값 자체를 어떤 통념이나 해당 분석가의 판단에 의해 제공되고 이는 전통적인 성격에 맞고 , 초기값 설정후 군집 간 거리측정은 어떠한 객관적 기준으로 측정해 군집을 나누기 때문에 그렇다.

다음 포스팅에서는 대표적인 Clustering 알고리즘 2개 K-means 와 DBSCAN을 볼것이다.