클러스터링 (Clustering)

r4v3n-k 2019. 12. 22. 15:08

2019. 12. 22. 15:08

개념 (Concept)

- 군집 분석(Cluster analysis)은 비지도 학습으로, 지도 학습이 분류(Classification)를 위해 미리 레이블(label)되어 있어 전문가(해당 데이터셋에 대한 분석이 필요, 레이블의 의미 등)의 도움이 필요하다는 점에서 차이가 있다. 그러나 군집 분석도 큰 데이터 집합(a cloud of data points)이 주어지면 그 구조를 이해해야 한다.

- 점들의 집합(set of points)이 주어지면, 점들간의 거리를 이용하여 몇 개의 클러스터로 그룹화를 해야 한다.

클러스터 내 점들은 서로 가까워야(유사해야) 한다.
다른 클러스터의 점들은 거리가 멀어야(유사하지 않아야) 한다.

- 보통 점들은 고차원 공간에 있다. → 데이터 집합에서 feature 가 많다. → 차원 축소 (필요 없는 feature 걸러내기)

- 유사도(Similarity)는 거리 척도를 이용해서 정의된다.

Euclidean
Cosine
Jaccard
edit distance (두 문자열 사이의 거리 = 몇 개를 바꿔야 그 문자열이 되는가?)

- Outlier 는 어느 클러스터에도 속하지 못하는 점으로, 탐지가 어렵다.

- 2차원에서의 클러스터링은 쉬워보인다. 데이터가 적은 양을 클러스터링하는 것은 쉽기 때문이다. 그러나, 많은 경우 2차원이 아닌 10차원 혹은 10,000 차원에 해당된다.

- 고차원 공간은 다르게 보기 → 대부분 점들은 모여있어서 특정 점으로부터 같은 거리에 있다.

- 예제: 음악 CD → 직관적으로, 음악은 카테고리로 분류되고, 고객들은 몇 가지 카테고리를 선호한다.

접근: 비슷한 CD(같은 카테고리)를 구매한 고객들의 집합으로 CD를 표현
비슷한 사람들이 구매했을 것
유사한 CD는 유사한 고객들의 집합을 가진다. 역도 성립
모든 CD의 공간: 1차원의 공간으로 생각하면, 각 고객에 대해 차원 내 값은 0~ 1사이 일지도 모른다. 하나의 CD는 이 공간 내 점이다. (X, X, …, Xk) 여기서 Xi=1 이면 i번째 고객이 CD를 구매한 것이다. → 유사한 CD를 그룹화하는 클러스터 찾는 것이 해야할 일이다.

- 예제: 문서(Documents) → 주제 찾기

벡터로 문서를 표현 → (X1, X2, …, Xk)
여기서 Xi는 i번째 단어가 그 문서에 나타났음을 의미한다. k가 무한한 것은 중요하지 않다. (단어의 집합을 제한하지 않음)
유사한 단어의 집합을 가진 문서는 같은 주제일 것이다.

- 거리 개념: Cosine, Jaccard, and Euclidean

Sets as vectors: 유사도는 Cosine distance 로 표현된다.
Sets as sets: 유사도는 Jaccard distance 로 표현된다.
Sets as points: 유사도는 Euclidean distance 로 표현된다.

클러스터링 방법

- 계층 구조(Hierarchical)

Agglomerative → Bottom up: 초기의 각 점은 클러스터이다. 반복적으로 두 개의 가까운 클러스터를 하나의 클러스터로 결합한다. 이를 반복
Divisive → Top down: 하나의 클러스터를 2개씩 나눈다. 이를 반복

- Point assignment: 이미 있는 클러스터들 중 새로운 점을 가장 가까운 클러스터에 할당한다.

계층적 클러스터링(Hierarchical Clustering)

- 핵심 연산: 가장 가까운 클러스터끼리 반복적으로 결합하는 것

- 고려 사항

클러스터간 거리는 어떻게 표현?
- 각 클러스터의 위치를 정의
가까움(nearness)을 어떻게 결정?
클러스터 결합을 언제 멈춤?

- centroid = 클러스터 내 점들의 평균 (포함된 점이 아닐 수 있음, 즉 좌표)

가까움은 centroid 의 Euclidean distance 로 정의된다.

o = data point, x = centroid

- clustroid = 클러스터 내 점들과 가장 가까운(closest) 점

가까움은 clustroid 의 Euclidean distance 로 정의된다.
closest 의 다양한 의미
- 다른 점들에 가장 작은 최대 거리
- 다른 점들에 가장 작은 평균 거리
- 다른 점들에 가장 작은 거리제곱합(Sum of squares of distances)

- 그 외 가까움을 정의하는 방법

Intercluster distance = 각 클러스터에서 클러스터 내 두 점들 사이에 거리의 최솟값
클러스터의 cohesion 의 표기법을 선택, 즉 clustroid 에서 최대 거리
병합된 클러스터의 diameter 를 사용 → 클러스터에서 점들 사이의 최대 거리
클러스터에서 점들 사이에 평균 거리를 사용
밀집도(density) 기반의 접근법 → diameter 또는 평균 거리를 구한 뒤, 클러스터 내 점들의 개수로 나눔

- 구현

각 단계에서, 클러스터의 모든 쌍 사이에 거리를 계산하고 결합
O(N^3) → 우선순위 큐를 사용하면 O(N^2*logN)으로 줄일 수는 있다.
그러나 여전히 비용이 비싸다.

k-평균 클러스터링(k-means clustering)

- Point assignment 의 대표적인 방법으로, 여기서 k는 클러스터의 개수를 의미한다.

- 알고리즘

유클리디안 공간이나 거리를 가정한다.
클러스터 개수 k를 선택
클러스터별 하나의 점(centroid 역할)을 선택해서 클러스터를 초기화한다.
- 랜덤으로 k번째 점을 고르는 방법, 여기서 k-1개의 다른 점들은 이전 점들과 가능한 멀리 떨어져 있다.
각 점을 그 점과 가장 가까운 centroid를 갖는 클러스터에 포함시킨다.
모든 점들이 할당된 후, k개의 클러스터들의 centroid의 위치를 갱신한다.
모든 점들을 가장 가까운 centroid를 갖는 클러스터로 재할당한다. 여기서 클러스터 내 점들이 바뀔 수 있다. 이를 클러스터의 변화가 없을 때(convergence = 점들이 움직이지 않음)까지 반복한다.

- 클러스터 개수 선택: 클러스터 개수를 1개씩 늘리면서 centroid 간의 평균 거리가 더 이상 많이 감소하지 않는 경우의 k를 선택한다. 개수가 늘 때마다 평균이 급격히 감소하는데 적절한 k가 발견되면 매우 천천히 감소한다.

- 클러스터 개수가 적으면, centroid 의 거리가 매우 길다. 적절한 개수이면 거리가 점점 짧아진다. 개수가 많으면, 평균 거리가 매우 조금씩 줄어든다.

Bradley-Fayyad-Reina (BFR) Algorithm

- 매 반복마다 거리를 계산한다면, 디스크 입출력(메인 메모리에 데이터를 많이 못올리는 경우) 시 데이터가 많을수록 비효율적이다.

- 매우 큰 데이터 집합을 다루기 위해 설계된 k-means의 확장버전

- 유클리디안 공간에서 클러스터들이 보통 centroid 주변에 분산되었다고 가정

다른 차원에서의 표준 편차는 다양할 수 있다. → x축, y축으로 볼 때 각 그래프를 보는 관점이 다름
2차원 그래프에서는 표준편차가 높을수록 넓은 산 모양이고, 낮을수록 좁은 산 모양이다.

- 클러스터를 모으는 효율적인 방법

데이터를 묶어서 단위별로 메모리에 로드시킨 후, 특징을 추출(통계적 연산)하고나면 디스크로 보내고 새 묶음을 다시 로드

- 시작할 때, 초기 로드 시 최초의 k를 선택할 때 접근법

k 개의 점들을 랜덤으로 선택
선택적으로 작은 랜덤 샘플과 클러스터를 선택
샘플을 선택하면, 랜덤으로 점을 선택한 뒤 k-1 개의 다른 점들은 이전에 선택된 점들로부터 가능한 멀리 떨어져 있어야 한다.

- 점들의 3개의 클래스

Discard set (DS): 합쳐질, centroid에 충분히 가까운 점들의 집합
Compression set (CS): 어떤 centroid에 가깝지 않고 서로 가까운 점들의 집합, 이 점들은 합쳐지지만 하나의 클러스터로 할당되지는 않는다.
Retained set (RS): compression set으로 할당되어지기를 대기하는 고립된 점들의 집합

- 점들의 집합을 합치는 법: 각 점들에 대해, discard set (DS) 이 다음 사항에 의해 합쳐진다.

N = 클러스터 내 점들의 개수
SUM = i번째 요소는 i차원에서 점들의 좌표(coordinates)의 합을 의미하는 벡터
SUMSQ = i번째 요소는 i번째 차원에서 좌표의 제곱의 합을 의미하는 벡터

- 점들의 집합을 설명하는 법

차원 수가 d라고 정의될 때, 각 클러스터의 크기는 2d + 1 로 표현된다.
각 차원에서 평균은 SUMi/N 으로 계산된다. 여기서 SUMi는 벡터 SUM의 i번째 요소
i 차원에서 클러스터의 discard set (DS)의 분산은 (SUMSQi / N) - (SUMi / N)^2 으로 정의된다.
표준편차는 위에서 구한 분산의 제곱근

- 메모리 로드하는 법

centroid 에 충분히 가까운 점들을 찾고, DS와 클러스터에 그 점들을 추가
오래된 RS에 남은 점들을 군집화하기 위한 메인 메모리 상의 클러스터링 알고리즘을 사용
- 클러스터들은 CS로 가고, outlier 들은 RS로 이동
- RS는 다음 반복에서 사용된다.
DS set: 새로운 점들을 설명하기 위해 클러스터의 통계적 연산을 적용 (N, SUM, SUMSQ)
CS에서 압축될 집합(compressed sets)을 합병
마지막 반복인 경우, CS에서 모든 압축될 집합과 모든 RS 내 점들을 그것들의 가장 가까운 클러스터로 병합

- 해당 클러스터로 점을 추가할 그 클러스터에 충분히 가까운 것을 어떻게 결정?

새로운 점을 클러스터로 놓을 지를 결정할 방법이 필요한데, BFR은 2가지 방법을 제시
Mahalanobis distance < threshold: centroid로부터 정규화된 유클리디안 거리

만약 d 차원에 정규분포로 클러스터가 존재하면, 변형(trasformation) 이후, 표준편차는 sqrt(d)가 됨
즉, centroid에서 거리가 68% 정도 되면 같은 클러스터로 볼 수 있다.

현재 가장 가까운 클러스터에 속할 확률이 높은 점(높은 우도를 가진 점)

- 2개의 압축될 집합(CS)을 하나로 결합 할 지를 어떻게 결정?

결합된 subcluster의 분산을 계산 (N, SUM, SUMSQ 이용)
만약 결합된 분산값이 어떤 임계값보다 낮으면 결합 (분산 < 임계값)

Clustering-Using-REpresentatives (CURE) Algorithm

- BFR/k-means의 문제점

클러스터들이 각 차원에서 정규분포 형태라고 가정하고 알고리즘을 수행한다.
- 그러나 대부분 데이터들이 정규분포가 아닐 수 있음
고차원 공간에서 각 축은 고정되어 있으나 타원(데이터가 모여서 만들어진 모양)의 각도는 그렇지 못하다.

- CURE 알고리즘 특징

유클리디안 거리를 가정
어떤 모양이든 클러스터링이 가능
클러스터를 표현하기 위해 대표적인 점들을 수집

- 2 Pass Algorithm: 첫번째 단계

메인 메모리에 맞는 랜덤 샘플(점들의 집합)을 선택
초기 클러스터는 계층적으로 점들을 군집화한다. 가장 가까운 점들, 클러스터들끼리 그룹화
대표 점을 선택: 각 클러스터에 대해, 가능한 흩어진 점들의 샘플을 선택한다.
해당 샘플로부터 클러스터의 centroid로 20% 씩 이동시키면서 대표 점을 수정하여 선택한다.

- 2 Pass Algorithm: 두번째 단계

전체 데이터 집합을 다시 스캔하고 데이터 집합에서 각 점 p를 방문한다.
가장 가까운 클러스터에 그 점을 놓는다.
- 가까움의 일반적인 정의는 점 p에 가장 가까운 대표 점을 찾고, 대표점의 클러스터에 찾은 점을 할당하는 것
- 초기에는 centroid 중심으로 정규분포화된 클러스터를 가정하고 이후 대표 점을 중심으로 점들을 옮긴다.
- 다양한 형태가 나올 수 있다.

- 정리하자면, 클러스터링은 주어진 점들의 집합에서 점들간 거리를 정의하고 몇 개의 클러스터들로 점들을 그룹화한다.

차원 축소 (Dimensionality Reduction)