Clustering - Hierarchical, DBSCAN, Affinity Propagation

2020-06-04

Hierarchical clustering(계층적 군집화)

계층적 군집화(hierachical clustering)는 여러개의 군집 중에서 가장 유사도가 높은 혹은 거리가 가까운 군집 두개를 선택하여 하나로 합치면서 군집 개수를 줄여 가는 방법을 말한다. 합체 군집화(agglomerative clustering)라고도 한다. 가장 처음에는 모든 군집이 하나의 데이터만을 가진다. 따라서 최초에는 데이터 개수만큼 군집이 존재하지만 군집을 합치면서 최종적으로 하나의 군집만 남게 된다.

계층적 군집화 개념 - 01

계층적 군집화 개념 - 02

계층적 군집화 개념 - 03

계층적 군집화 개념 - 04

군집간의 거리 측정

계층적 군집화를 하려면 우선 모든 군집 간에 거리를 측정해야 한다. 군집 간의 거리를 측정하는 방법에는 계층적 방법에 의존하지 않는 비계층적 방법과 이미 이전 단계에서 계층적 방법으로 군집이 합쳐진 적이 있다는 가정을 하는 계층적 방법 두 가지가 있다.

비계층적 거리 측정법

비계층적 거리측정법은 계층적 군집화가 아니더라도 모든 경우에 사용할 수 있는 거리 측정 방법이다. 중심거리, 단일거리, 완전거리, 평균거리 등이 있다. 다음에 설명할 계층적 거리측정법에 비해 계산량이 많은 단점이 있다.

비계층적 거리 측정 방법들

중심(centroid)거리

두 군집의 중심점(centroid)를 정의한 다음 두 중심점의 거리를 군집간의 거리로 정의한다.

$d(u,v) = \|c_u - c_v\|_2$

여기에서 $ d(u, v) $ 는 군집 $ u $ 와 군집 $ v $ 사이의 거리를 뜻한다. 또한 $ c_{u} $ 와 $ c_{v} $ 는 각각 두 군집 $ u $ 와 $ v $ 의 중심점이다. 군집의 중심점은 그 군집에 포함된 모든 데이터의 평균을 사용한다.

$c_u = \dfrac{1}{|u|}\sum_i u_i$

이 식에서 $ |\cdot| $ 기호는 군집의 원소의 개수를 말한다.

단일(single)거리

군집 $ u $ 의 모든 데이터 $ u_{i} $ 와 군집 $ v $ 의 모든 데이터 $ v_{j} $ 의 모든 조합에 대해 데이터 사이의 거리 $ d( u_{i}, v_{j} ) $ 를 측정해서 가장 작은 값을 구한다. 최소 거리(Nearest Point) 방법이라고도 한다.

$d(u,v) = \min(d(u_i,v_j))$

완전(complete) 거리

군집 $ u $ 의 모든 데이터 $ u_{i} $ 와 군집 $ v $ 의 모든 데이터 $ v_{j} $ 의 모든 조합에 대해 데이터 사이의 거리 $ d(u_{i}, v_{j}) $ 를 측정해서 가장 큰 값을 구한다. 최장 거리(Farthest Point) 방법이라고도 한다.

$d(u,v) = \max(d(u_i,v_j))$

평균(average) 거리

군집 $ u $ 의 모든 데이터 $ u_{i} $ 와 군집 $ v $ 의 모든 데이터 $ v_{j} $ 의 모든 조합에 대해 데이터 사이의 거리 $ d(u_{i}, v_{j}) $ 를 측정해서 평균을 구한다. $ |u| $ 와 $ |v| $ 는 각각 두 군집의 원소의 개수를 뜻한다.

$d(u,v) = \sum_{i,j} \frac{d(u_i, v_j)}{|u||v|}$

계층적 거리 측정법

계층적 거리 측정법은 계층적 군집화에서만 사용할 수 있는 방법이다. 즉, 이전 단계에서 이미 어떤 두 개의 군집이 하나로 합쳐진 적이 있다고 가정하여 이 정보를 사용하는 측정법이다. 비계층적 거리 측정법에 비해 계산량이 적어 효율적이다.

중앙값(median)거리

이 방법은 중심거리 방법의 변형이다. 중심거리 방법처럼 군집의 중심점의 거리를 군집간의 거리라고 한다. 하지만 군집의 중심점을 계산하는 방법이 다르다. 만약 군집 $ u $ 가 군집 $ s $ 와 군집 $ t $ 가 결합하여 생겼다면

$u \leftarrow s + t$

군집 $ u $ 의 중심점은 새로 계산하지 않고 원래 군집의 두 군집의 중심정의 평균을 사용한다.

$c_u = \dfrac{1}{2}(c_s + s_t)$

따라서 해당 군집의 모든 데이터를 평균하여 중심점을 구하는 것 보다 계산이 빠르다.

가중(weighted)거리

가중거리를 사용하려면 원래 어떤 두 개의 군집이 합쳐져서 하나의 군집이 만들어졌는지 알아야 한다. 만약 군집 $ u $ 가 군집 $ s $ 와 군집 $ t $ 가 결합하여 생겼다면

$u \leftarrow s + t$

이 군집 $ u $ 와 다른 군집 $ v $ 사이의 거리는 군집 $ u $ 를 구성하는 원래 군집 $ s $, $ t $ 와 $ v $ 사이의 두 거리의 평균을 사용한다.

$d(u,v) = \dfrac{1}{2}(d(s,v) + d(t,v))$

계층적 거리 - 가중 거리

와드(Ward)거리

계층적 거리 - 와드 거리 개념

와드 거리는 가중거리 방법의 변형이다. 만약 군집 $ u $ 가 군집 $ s $ 와 군집 $ t $ 가 결합하여 생겼다면

$u \leftarrow s + t$

이 군집 $ u $ 와 다른 군집 $ v $ 사이의 거리를 구하는데 있어서 군집 $ u $ 를 구성하는 원래 군집 $ s $, $ t $ 와 $ v $ 사이의 거리를 사용하는 것은 가중거리 방법과 같지만 원래의 두 군집 $ s $, $ t $ 가 너무 가까우면 $ v $ 와의 거리가 더 먼것으로 인식한다.

$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의 계층적 군집화

Python으로 계층적 군집화를 하려면 Scipy 패키지의 linkage 명령을 사용하거나 Scikit-Learn 패키지의 AgglomerativeClustering 클래스를 사용한다. 각각 장단점이 있는데 Scipy 패키지는 군집화 결과를 트리 형태로 시각화해주는 dendrogram 명령도 지원한다.

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=(20, 15))
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)
# plt.savefig("random_sample_MNIST")

임의로 추출한 MNIST 이미지

from scipy.cluster.hierarchy import linkage, dendrogram

Z = linkage(X, 'ward')
Z

결과

array([[ 3.        , 18.        , 23.51595203,  2.        ],
       [13.        , 19.        , 25.27844932,  2.        ],
       [ 1.        , 14.        , 28.67054237,  2.        ],
       [17.        , 21.        , 31.04298096,  3.        ],
       [ 4.        ,  7.        , 31.51190251,  2.        ],
       [ 6.        ,  8.        , 32.54228019,  2.        ],
       [ 9.        , 10.        , 33.36165464,  2.        ],
       [ 0.        , 24.        , 34.51086785,  3.        ],
       [ 2.        , 22.        , 37.03151811,  3.        ],
       [11.        , 26.        , 43.25505751,  3.        ],
       [12.        , 15.        , 45.31004304,  2.        ],
       [16.        , 20.        , 45.36151085,  3.        ],
       [ 5.        , 27.        , 53.54437412,  4.        ],
       [30.        , 32.        , 56.6892112 ,  6.        ],
       [25.        , 29.        , 60.16809786,  5.        ],
       [28.        , 34.        , 66.61618922,  8.        ],
       [31.        , 33.        , 70.35228813,  9.        ],
       [23.        , 36.        , 80.11172754, 12.        ],
       [35.        , 37.        , 93.57946712, 20.        ]])

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.grid()
plt.show()

MNIST 임의 20개 이미지의 계층적 군집화 결과

DBSCAN Clustering

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

DBSCAN(Density-Based Spatial Clustering of Application with Noise) 군집화 방법은 데이터가 밀집한 정도 즉, 밀도를 이용한다. DBSCAN 군집화는 군집의 형태에 구애받지 않으며 군집의 갯수를 사용자가 지정할 필요가 없다. DBSCAN 군집화 방법에서는 초기 데이터로부터 근접한 데이터를 찾아나가는 방법으로 군집을 확장한다. 이 때 다음 사용자 인수를 사용한다.
- 최소거리 $ \varepsilon $ : 이웃(neighborhood)을 정의하기 위한 거리
- 최소 데이터 개수(minimum points) : 밀집지역을 정의하기 위해 필요한 이웃의 개수

DBSCAN 개념

만약 $ \varepsilon $ 최소 거리 안의 이웃 영역 안에 최소 데이터 개수 이상의 데이터가 있으면 그 데이터는 핵심(core) 데이터이다. 이렇게 핵심 데이터를 찾아낸 다음에는 이 핵심 데이터의 이웃 영역 안에 있는 데이터를 이 핵심데이터와 연결된 핵심 데이터로 정의한다. 핵심 데이터의 이웃 영역안에 있는 데이터도 마찬가지로 연결된 핵심 데이터가 된다. 만약 고밀도 데이터에 더이상 이웃이 없으면 이 데이터는 경계(border) 데이터라고 한다. 핵심 데이터도 아니고 경계 데이터도 아닌 데이터를 outlier라고 한다.

DBSCAN

DBSCAN 알고리즘

DBSCAN 알고리즘 예시들

Scikit-learn의 cluster 서브패키지는 DBSCAN 클래스를 제공한다. 다음과 같은 인수를 받을 수 있다.
- eps : 이웃을 정의하기 위한 거리. epsilon
- min_samples : 핵심 데이터를 정의하기 위해 필요한 이웃영역안의 데이터 개수.

DBSCAN 파라미터 설정시 유의점

군집화가 끝나면 객체는 다음 속성을 갖는다.
- labels_ : 군집번호. 아웃라이어는 -1 값을 갖는다.
- core_sample_indices_ : 핵심 데이터의 인덱스. 여기에 포함되지 않고 outlier도 아닌 데이터는 경계 데이터이다.

DBSCAN 군집화의 장단점

다음은 make_circles 명령과 make_moons 명령으로 만든 동심원, 초승달 데이터를 DBSCAN으로 군집화한 결과를 나타낸 것이다. 마커(marker)의 모양은 군집을 나타내고 마커의 크기가 큰 데이터는 핵심데이터, x 표시된 데이터는 outlier이다.

from sklearn.datasets import make_circles, make_moons
from sklearn.cluster import DBSCAN

n_samples = 1000
np.random.seed(2)
X1, y1 = make_circles(n_samples=n_samples, factor=.5, noise=.09)
X2, y2 = make_moons(n_samples=n_samples, noise=.1)

def plot_DBSCAN(title, X, eps, xlim, ylim):
    model = DBSCAN(eps=eps)
    y_pred = model.fit_predict(X)
    idx_outlier = model.labels_ == -1
    plt.scatter(X[idx_outlier, 0], X[idx_outlier, 1], marker='x', lw=1, s=20)
    plt.scatter(X[model.labels_ == 0, 0], X[model.labels_ == 0, 1], marker='o', facecolor='g', s=5)
    plt.scatter(X[model.labels_ == 1, 0], X[model.labels_ == 1, 1], marker='s', facecolor='y', s=5)
    X_core = X[model.core_sample_indices_, :]
    idx_core_0 = np.array(list(set(np.where(model.labels_ == 0)[0]).intersection(model.core_sample_indices_)))
    idx_core_1 = np.array(list(set(np.where(model.labels_ == 1)[0]).intersection(model.core_sample_indices_)))
    plt.scatter(X[idx_core_0, 0], X[idx_core_0, 1], marker='o', facecolor='g', s=80, alpha=0.3)
    plt.scatter(X[idx_core_1, 0], X[idx_core_1, 1], marker='s', facecolor='y', s=80, alpha=0.3)
    plt.grid(False)
    plt.xlim(*xlim)
    plt.ylim(*ylim)
    plt.xticks(())
    plt.yticks(())
    plt.title(title)
    return y_pred

plt.figure(figsize=(10, 5))
plt.subplot(121)
y_pred1 = plot_DBSCAN("동심원 군집", X1, 0.1, (-1.2, 1.2), (-1.2, 1.2))
plt.subplot(122)
y_pred2 = plot_DBSCAN("초승달 군집", X2, 0.1, (-1.5, 2.5), (-0.8, 1.2))
plt.tight_layout()
plt.show()

군집을 이루는 모양에 따른 DBSCAN 결과

from sklearn import datasets
import pandas as pd

iris = datasets.load_iris()
labels = pd.DataFrame(iris.target)
labels.columns=['labels']
data = pd.DataFrame(iris.data)
data.columns=['Sepal length','Sepal width','Petal length','Petal width']
data = pd.concat([data,labels],axis=1)

feature = data[ ['Sepal length','Sepal width','Petal length','Petal width']]

from sklearn.cluster import DBSCAN
import matplotlib.pyplot  as plt
import seaborn as sns

# create model and prediction
model = DBSCAN(eps=0.5,min_samples=5)
predict = pd.DataFrame(model.fit_predict(feature))
predict.columns=['predict']

# concatenate labels to df as a new column
r = pd.concat([feature,predict],axis=1)

print(r)

결과

Sepal length  Sepal width  Petal length  Petal width  predict
0             5.1          3.5           1.4          0.2        0
1             4.9          3.0           1.4          0.2        0
2             4.7          3.2           1.3          0.2        0
3             4.6          3.1           1.5          0.2        0
4             5.0          3.6           1.4          0.2        0
..            ...          ...           ...          ...      ...
145           6.7          3.0           5.2          2.3        1
146           6.3          2.5           5.0          1.9        1
147           6.5          3.0           5.2          2.0        1
148           6.2          3.4           5.4          2.3        1
149           5.9          3.0           5.1          1.8        1

DBSCAN 결과 시각화

1
2
3

#pairplot with Seaborn
sns.pairplot(r,hue='predict')
plt.show()

iris 데이터를 DBSCAN 군집한 결과

1
2
3

#pairplot with Seaborn
sns.pairplot(data,hue='labels')
plt.show()

iris raw 데이터의 pair plot

Kmeans 결과와 비교

from sklearn.cluster import KMeans
km = KMeans(n_clusters = 3, n_jobs = 4, random_state=21)
km.fit(feature)
new_labels =pd.DataFrame(km.labels_)
new_labels.columns=['predict']
r2 = pd.concat([feature,new_labels],axis=1)

#pairplot with Seaborn
sns.pairplot(r2,hue='predict')
plt.savefig('k_means_iris_pair_plot')
plt.show()

DBSCAN의 결과보다 더 좋게 군집을 나눈것을 볼 수 있다. K-means는 원형으로 군집을 이룬 데이터에 대해 더 예측력이 좋다는 사실을 확인할 수 있다. 또한, K-means는 대체로 균등적으로 군집의 데이터를 나누어 주기 때문에 아래 그림에서 볼 수 있듯이 군집마다 데이터의 개수가 비슷해 보인다.

k-means 군집화 결과의 pair plot

참고로, DBSCAN의 파라미터에 민감한 단점을 보완한 HDBSCAN이 있다.

1	pip install hdbscan

참조.html)

DataLatte's IT Blog using Hexo

machine learning

Clustering - Hierarchical, DBSCAN, Affinity Propagation

Hierarchical clustering(계층적 군집화)

군집간의 거리 측정

비계층적 거리 측정법

중심(centroid)거리

단일(single)거리

완전(complete) 거리

평균(average) 거리

계층적 거리 측정법

중앙값(median)거리

가중(weighted)거리

와드(Ward)거리

Scipy의 계층적 군집화

결과

DBSCAN Clustering

결과

DBSCAN 결과 시각화

Kmeans 결과와 비교