2-3-9. 군집화 알고리즘

군집화는 자동으로 데이터를 군집으로 나누거나 유사한 것끼리 연결하는 기계학습 분야이며 우리가 찾고 있는 것이 무엇인지 모르기 때문에 군집화는 예측보다 지식의 발견에 사용된다. 인공지능의 군집화는 인간의 오랜 인식이 잘못되어 있는 것을 찾아 내기도 하는 의외의 연관성을 찾기도 하는 통찰을 보이기도 한다

구성상태에 따라 계층적 군집화와 분할 군집화로 나눌 수 있다.

1) 계층적 군집화(hierarchical clustering)

-군집화의 결과가 계층적으로 나타나는 것인데, 가까운 것끼리 작은 군집을 형성하고, 가까이에 있는 작은 군집이 결합해서 더 큰 군집을 형성하는 형태임.  클러스터를 미리 정할 필요가 없다는 것. 계층적 군집은 각 개체를 하나의 군집으로 보고 가까운 군집끼리 합해 나가는 응집분석과 개체전체를 하나의 군집으로 보고 각 군집을 두 개의 군집으로 계속 나누는 분할 분석으로 구분.

그러나 한 계층에서 어떤 군집에 할당되면 그 계층 아래에서는 다른 위 계층에서 나뉘 다른 군집으로 할당 될 수 없다는 특징이 있다. 따라서 계층적 군집화는 종종 탐색적인 의미로 사용되고 있으며, 최종적 군집화는 비계층적 군집화를 통하여 이루어지는 경우가 많다

--응집분석의 알고리즘

 `각 개체를 하나의 군집으로 하여 전체 n개의 군집을 형성한다

 `각 군집 간의 거리를 계산하여 가장 가까운 두 개의 군집을 합친다.

 `전 개체가 하나의 군집이 될 때까지 군집을 계속 합친다

방법으로는 단일연결법, 완전 연결법, 평균 연결법이 있다.

 

계층적 군집화와 덴드로그램. 덴드로그램의 y축은 군집내부의 유사도를 나타내는 값

 

2) 분할 군집화(partitioning clustering)

계층적 구조를 만들지 않고 전체 데이터를 유사한 것들끼리 나누어서 묶는 것이다. 분할군집화의 대표적인 알고리즘이 k-means 알고리즘.

k-평균 알고리즘(k-mean)알고리즘

주어진 데이터를  k개의 클러스터로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작.

--절차

1. 전체 데이터 중에서 무작위로 k개의 데이터를 선택해서 각각을 군집의 초기 중심으로 정함

2. 각 데이터와 각 군집 중심 간의 거리를 계산

3. 각각의 점들을 방금 구한 무게중심 가운데 제일 가까운 것에 연결지음으로써 새로이 집합을 나눌 수 있음.

4. 각 군집에 대해 배정된 모든 데이터의 평균을 구해서, 이것을 새로운 군집 중심으로 정함

5. 이전 상태와 비교하여 군집의 변화가 있다면, 단계2로 돌아감. 그렇지 않으면 종료.

 

알고리즘

i번째 클러스터의 중심을 , 클러스터에 속하는 점의 집합을 Si 라고 할때, 전체 분산은 다음과 같이 계산

이 값을 최소화하는 Si를 찾는 것이 알고리즘의 목표가 됨

알고리즘은 우선 초기의 를 임의로 설정하는 것으로 시작한다. 그 다음에는 다음의 두 단계를 반복함

----클러스터 설정 : 각 점에 대해, 그 점에서 가장 가까운 클러스터를 찾아 배당

----클러스터 중심 재조정 : Ui를 각 클럿터에 있는 점들의 평균값으로 재설정해 줌

 

만약 클러스터가 변하지 않는다면 반복을 중지.

 

 

 

데이터에 있는 군집의 갯수는 알 수 없지만 k-mean 알고리즘은 군집의 갯수 k를 스스로 제공한다

 

□