Clustering Methods

2019-01-11

study

클러스터링 방법

1. K-Means 클러스터링

앞서 언급했던 5가지 클러스터링 방법 중 첫번째로 소개할 K-Means 클러스터링 알고리즘은 가장 단순하고 빠른 클러스터링 알고리즘 중 하나다. 이 클러스터링 방법에서는 아래 목적함수 값이 최소화될 때까지 클러스터의 중심(centroid) 위치와 각 데이터가 소속될 클러스터를 반복해서 찾는다. 목적함수 값을 inertia 라고도 한다.

$J = \sum^K_{k=1}\sum_{i\in C} d(x_i, \mu_k)$

$K$ : 클러스터의 개수
$C_k$ : $k$ 번째 클러스터에 속하는 데이터 집합
$\mu_k$ : $k$ 번째 클러스터의 중심 위치
$d(x_i,\mu_k)$ : 두 데이터 $x_i, \mu_k$ 사이의 거리 혹은 비유사도
- 유클리드 거리를 사용할 경우: $d(x_i,\mu_k) = ||x_i - \mu_k ||^2$

K-Means 클러스터링 방법의 세부 알고리즘은 다음과 같다.

임의 중심값 $\mu_k$ 를 고른다. 보통 데이터 샘플 중에서 $K$개를 선택한다.
중심값에서 각 데이터까지의 거리를 계산한다.
각 데이터에서 가장 가까운 중심을 선택하여 클러스터를 갱신한다.
다시 만들어진 클러스터에 대해 중심을 다시 계산하고 위 과정을 반복한다.

Scikit-learn의 cluster 서브패키지는 K-Means 클러스터링을 위한 KMeans 클래스를 제공하고, 다음과 같은 인수를 받는다.

n_clusters : 클러스터의 개수
init : 초기화 방법. random 이면 무작위, k-means++이면 K-Means++ 방법. 또는 각 데이터의 클러스터 라벨
n_init : 초기 중심값 시도 횟수. 디폴트는 10. 횟수만큼의 무작위 중심값 중 가장 좋은 값을 선택함
max_iter : 최대 반복 횟수
random_state : 시드값

다음은 make_blobs 명령으로 만든 데이터를 2개의 클러스터로 K-means클러스터링 하는 과정이다. 마커의 모양은 클러스터를 나타내며, 크기가 큰 마커가 중심값이다. 각 단계에서 중심값은 전 단계의 클러스터의 평균으로 다시 계산된다.

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

X, _ = make_blobs(n_samples=20, random_state=4)

def plot_KMeans(n):
    model = KMeans(n_clusters=2, init="random", n_init=1, max_iter=n, random_state=8).fit(X)
    c0, c1 = model.cluster_centers_
    plt.scatter(X[model.labels_ == 0, 0], X[model.labels_ == 0, 1], marker='v', facecolor='r', edgecolors='k')
    plt.scatter(X[model.labels_ == 1, 0], X[model.labels_ == 1, 1], marker='^', facecolor='y', edgecolors='k')
    plt.scatter(c0[0], c0[1], marker='v', c="r", s=200)
    plt.scatter(c1[0], c1[1], marker='^', c="y", s=200)
    plt.grid(False)
    plt.title("iteration={}, score={:5.2f}".format(n, model.score(X)))

plt.figure(figsize=(8, 8))
plt.subplot(321)
plot_KMeans(1)
plt.subplot(322)
plot_KMeans(2)
plt.subplot(323)
plot_KMeans(3)
plt.subplot(324)
plot_KMeans(4)
plt.tight_layout()
plt.show()

K-Means++

K-Means++ 알고리즘은 KMeans 클러스터링 클래스의 인수로 설정할 수 있는, 초기 중심값을 설정하기 위한 알고리즘이다. 랜덤하게 초기중심값을 설정했을 때 클러스터링 성능이 떨어지는 점을 보완하기 위한 방법이 된다. 다음과 같은 방법을 통해 되도록 서로 멀리 떨어진 중심값 집합을 찾아낸다.

중심값을 저장할 집합 $M$ 을 준비한다.
일단 하나의 중심 $\mu_0$ 를 랜덤하게 선택해 $M$ 에 넣는다.
$M$ 에 속하지 않는 모든 샘플 $x_i$ 에 대해 거리 $d(M, x_i)$를 계산한다. $M$ 안에 현재까지 들어있는 모든 중심값 $\mu_k$ 중 해당 데이터 $x_i$ 와 가장 가까운 중심값과의 거리에 해당한다.
$d(M, x_i)$에 비례하는 확률로 다음 중심 $\mu$ 를 선택한다.
$k$개의 중심이 선택될 때까지 위 과정을 반복한다.
$k$ 개의 중심값에 대해 K-Means 알고리즘을 사용해 클러스터링을 진행한다.

다음은 K-Means++ 알고리즘을 사용해 MNist Digit 이미지를 클러스터링한 결과이다.

from sklearn.datasets import load_digits

digits = load_digits()

model = KMeans(init="k-means++", n_clusters=10, random_state=0)
model.fit(digits.data)
y_pred = model.labels_

def show_digits(images, labels):
    f = plt.figure(figsize=(8, 2))
    i = 0
    while (i < 10 and i < images.shape[0]):
        ax = f.add_subplot(1, 10, i + 1)
        ax.imshow(images[i], cmap=plt.cm.bone)
        ax.grid(False)
        ax.set_title(labels[i])
        ax.xaxis.set_ticks([])
        ax.yaxis.set_ticks([])
        plt.tight_layout()
        i += 1
        
def show_cluster(images, y_pred, cluster_number):
    images = images[y_pred == cluster_number]
    y_pred = y_pred[y_pred == cluster_number]
    show_digits(images, y_pred)
    

for i in range(10):
    show_cluster(digits.images, y_pred, i)

연습 문제

붓꽃 데이터를 K=3인 K-Means 클러스터링하여 adjusted Rand index, adjusted mutual information, 실루엣 계수를 각각 계산하라.

2. DBSCAN 클러스터링

K-Means 클러스터링 방법은 단순하고 강력한 방법이지만 클러스터의 모양이 원형이 아닌 경우에는 잘 동작하지 않으며 클러스터의 개수를 사용자가 지정해주어야 한다는 단점이 있다.

DBSCAN(Density-Based Spatial Clustering of Applications with Noise) 방법은 데이터가 밀집한 정도를 이용하기 때문에 클러스터의 형태에 구애받지 않으며 클러스터의 개수도 지정해줄 필요가 없다. 이 방법에서는 초기데이터로부터 근접한 데이터를 찾아나가는 방식으로 클러스터를 확장한다. 이 때 사용되는 사용자 인수는 다음과 같다.

epsilon $\epsilon$ : 이웃(neighborhood)을 정의하기 위한 거리(이웃 영역의 반지름)
최소 데이터 개수(minimum points) : 밀집지역을 정의하기 위해 필요한 이웃의 개수

만약 어떤 데이터에서 $\epsilon$ 거리 반경 안에 있는, 즉 해당 데이터의 이웃 영역 안에 최소 데이터개수(MinPts) 이상의 데이터가 있으면, 그 데이터는 핵심 데이터(core point)이다.

이 핵심 데이터의 이웃 영역 안에 있는 데이터들을 핵심데이터와 연결된 고밀도 데이터(density-reachable points)라고 한다. 고밀도 데이터의 이웃영역 안에 있는 데이터 또한 연결된 고밀도 데이터가 된다.

고밀도 데이터에 더이상 이웃이 없으면, 그 고밀도 데이터는 경계데이터(border data)라고 하며, 연결은 끝난다. 아무 데이터에도 연결되지 않은 데이터를 아웃라이어(outlier) 라고 한다.

scikit-learn의 cluster 서브패키지에서 제공하는 DBSCAN 클래스를 이용하면 다음과 같은 인수를 지정해 클러스터링을 할 수 잇다.

eps : 이웃을 정의하기 위한 거리 $\epsilon$
core_sample_indices_ : 핵심 데이터의 인덱스

다음은 make_circles 명령과 make_moons 명령으로 만든 동심원, 초승달 데이터를 DBSCAN 방법으로 클러스터링한 결과를 나타낸 것이다. 마커의 모양은 클러스터를 나타내고, 마커의 크기가 큰 데이터가 핵심데이터, x 표시된 데이터는 아웃라이어다.

3. 계층적 클러스터링

계층적 클러스터링(Hierarchical Clustering)은 하나의 데이터샘플을 하나의 클러스터로 보고 가장 유사도가 높은 클러스터끼리 합치면서 클러스터의 개수를 줄여가는 방법이다.

클러스터간 거리 측정

클러스터간의 비유사도 혹은 거리를 측정하는 방법에는 다음과 같은 것들이 있다.

비귀납적 방법
- centroid
- single
- complete
- average
귀납적 방법
- median
- weighted
- Ward

비귀납적 방법

1) centroid

두 클러스터 $u, v$의 중심점(centroid) $c_u, c_v$를 정의한 다음 두 중심점의 거리를 클러스터간 거리로 정의한다.

$d(u, v) = ||c_u-c_v||^2$

2) single

클러스터 $u$ 의 모든 데이터 $i$와 클러스터 $v$ 의 모든 데이터 $j$ 의 모든 조합에 대해 거리를 측정해 그 중 최소값 클러스터간 거리로 정의한다. 최소거리(Nearest Point) 방법이라고도 한다.

$d(u, v) = \min(dist(u[i], v[j]))$

3) complete

클러스터 $u$ 의 모든 데이터 $i$와 클러스터 $v$ 의 모든 데이터 $j$ 의 모든 조합에 대해 거리를 측정해 그 평균을 클러스터간 거리로 정의한다. $|u|$ 와 $|v|$ 는 각각 두 클러스터의 원소의 개수를 의미한다.

$d(u,v) = \sum_{ij} \frac{d(u[i],v[j])}{|u||v|}$

귀납적 방법

귀납적 방법에 속하는 아래 방법들은 Agglomerative Clustering에서 사용할 수 있는 방법들이다.

1) median

centroid 방법의 변형으로, 만약 클러스터 $u$가 클러스터 $s$ 와 $t$ 의 결합으로 생겨난 클러스터라면 $u$ 클러스터의 중심점은 새로 계산하지 않고 원래 두 클러스터의 중심점의 평균으로 사용한다.

2) weighted

만약 클러스터 $u$가 클러스터 $s$ 와 $t$ 의 결합으로 생겨난 클러스터라면 $u$ 클러스터와 $v$ 클러스터간의 거리는 $v$에서 원래 두 클러스터까지의 거리의 평균으로 정의한다.

$d(u, v) = (dist(s,v)+dist(t,v))/2$

3) Ward

만약 클러스터 $u$가 클러스터 $s$ 와 $t$ 의 결합으로 생겨난 클러스터라면 $u$ 클러스터와 $v$ 클러스터간의 거리는 $v$ 에서 $s, t$ 각각까지의 거리의 가중평균에서 $s$ 와 $t$ 간 거리를 보정한 값으로 정의한다.

$d(u,v)\\ = \sqrt{\frac{|v|+|s|}{|v|+|s|+|t|}d(v,s)^2+\frac{|v|+|t|}{|v|+|s|+|t|}d(v,t)^2 - \frac{|v|}{|v|+|s|+|t|}d(s,t)^2}$

SciPy의 계층적 클러스터링

파이썬으로 계층적 클러스터링을 하려면 SciPy 패키지의 linkage 명령을 사용하거나 scikit-learn 패키지의 AgglomerativeClustering 클래스를 사용한다. Scipy패키지는 클러스터링 결과를 tree형태로 시각화해주는 dendogram 명령도 지원한다.

MNIST digit 이미지 중 20개를 무작위로 골라 계층적 클러스터링을 적용해보자.

from sklearn.datasets import load_digits

digits = load_digits()
n_image = 20
np.random.seed(0)
idx = np.random.choice(range(len(digits.images)), n_image)
X = digits.data[idx]
images = digits.images[idx]

plt.figure(figsize=(12, 1))
for i in range(n_image):
    plt.subplot(1, n_image, i + 1)
    plt.imshow(images[i], cmap=plt.cm.bone)
    plt.grid(False)
    plt.xticks(())
    plt.yticks(())
    plt.title(i)

from scipy.cluster.hierarchy import linkage, dendrogram

Z = linkage(X, 'ward') # 귀납적 방법 중 'Ward'를 적용한 계층적 클러스터링 실시
from matplotlib.offsetbox import OffsetImage, AnnotationBbox

plt.figure(figsize=(10, 4))
ax = plt.subplot()

ddata = dendrogram(Z)

dcoord = np.array(ddata["dcoord"])
icoord = np.array(ddata["icoord"])
leaves = np.array(ddata["leaves"])
idx = np.argsort(dcoord[:, 2])
dcoord = dcoord[idx, :]
icoord = icoord[idx, :]
idx = np.argsort(Z[:, :2].ravel())
label_pos = icoord[:, 1:3].ravel()[idx][:20]

for i in range(20):
    imagebox = OffsetImage(images[i], cmap=plt.cm.bone_r, interpolation="bilinear", zoom=3)
    ab = AnnotationBbox(imagebox, (label_pos[i], 0),  box_alignment=(0.5, -0.1), 
                        bboxprops={"edgecolor" : "none"})
    ax.add_artist(ab)

plt.show()

4. Affinity Propagation

모든 데이터가 특정한 기준에 따라 자신을 대표할 대표 데이터를 선택한다. 만약 스스로가 자기 자신을 대표하게 되면, 그 데이터가 클러스터의 중심이 된다.

responsibility $r(i, k)$
- $k$번째 데이터가 $i$ 번째 데이터의 대표가 되어야 한다는 근거
availability $a(i, k)$
- $i$ 번째 데이터가 $k$ 번째 데이터를 대표로 선택해야 한다는 근거
다음 수식을 $r,a$ 값이 수렴할 때까지 반복

$r(i, k) \leftarrow s(i,k) - \max_{k'\neq k}(a(i,k')+ s(i,k'))$ $a(i,k) \leftarrow \min(0, r(k,k) + \sum_{i'\neq i,k}r(i',k))$

여기에서 $s(i,k)$ 는 다음과 같이 음의 거리로 정의되는 유사도이다.

$s(i,k) = -||x_i - x_k||^2$

특히 $s(k,k)$ 는 특정한 음수값으로 사용자가 지정해주게 되는데, 이 값에 따라 클러스터의 개수가 달라지는 하이퍼 모수가 된다. $s(k,k)$값이 크면 자기 자신에 대한 유사도가 커져서 클러스터 수가 증가한다.

위 알고리즘으로 계산하는 $r, a$ 가 더 이상 변화하지 않고 수렴하면 게산이 종료되고, 종료 시점에서 $r(k,k) + a(k,k) > 0$ 인 데이터가 클러스터의 중심이 된다.

from sklearn.datasets.samples_generator import make_blobs
from sklearn.cluster import AffinityPropagation
from sklearn.metrics import *
from itertools import cycle

centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=300, centers=centers, cluster_std=0.5, random_state=0)

model = AffinityPropagation(preference=-50).fit(X)

cluster_centers_indices = model.cluster_centers_indices_
labels = model.labels_
n_clusters_ = len(cluster_centers_indices)

colors = cycle('rgb')
for k, col in zip(range(n_clusters_), colors):
    class_members = labels == k
    cluster_center = X[cluster_centers_indices[k]]
    plt.plot(X[class_members, 0], X[class_members, 1], col + '.')
    for x in X[class_members]:
        plt.plot([cluster_center[0], x[0]], [cluster_center[1], x[1]], col, alpha=0.25)
    plt.plot(cluster_center[0], cluster_center[1], 'o', mec='k', mew=3, markersize=7)

plt.show()

Study With Yujin

MathClassification