快捷導(dǎo)航

python實(shí)現(xiàn)層次聚類的方法

更新時(shí)間：2021年11月01日 11:37:53 作者：葉_蕖

層次聚類就是一層一層的進(jìn)行聚類，可以由上向下把大的類別（cluster）分割，叫作分裂法，這篇文章主要介紹了python實(shí)現(xiàn)層次聚類的方法，需要的朋友可以參考下

層次聚類算法

顧名思義，層次聚類就是一層一層的進(jìn)行聚類，可以由上向下把大的類別（cluster）分割，叫作分裂法；也可以由下向上對(duì)小的類別進(jìn)行聚合，叫作凝聚法；但是一般用的比較多的是由下向上的凝聚方法。

分裂法：

分裂法指的是初始時(shí)將所有的樣本歸為一個(gè)類簇，然后依據(jù)某種準(zhǔn)則進(jìn)行逐漸的分裂，直到達(dá)到某種條件或者達(dá)到設(shè)定的分類數(shù)目。用算法描述：
輸入：樣本集合D，聚類數(shù)目或者某個(gè)條件（一般是樣本距離的閾值，這樣就可不設(shè)置聚類數(shù)目）
輸出：聚類結(jié)果

1.將樣本集中的所有的樣本歸為一個(gè)類簇；
repeat：
    2.在同一個(gè)類簇（計(jì)為c）中計(jì)算兩兩樣本之間的距離，找出距離最遠(yuǎn)的兩個(gè)樣本a,b；
    3.將樣本a，b分配到不同的類簇c1和c2中；
    4.計(jì)算原類簇（c）中剩余的其他樣本點(diǎn)和a，b的距離，若是dis(a)<dis(b)，則將樣本點(diǎn)歸到c1中，否則歸到c2中；
util：達(dá)到聚類的數(shù)目或者達(dá)到設(shè)定的條件

凝聚法：

凝聚法指的是初始時(shí)將每個(gè)樣本點(diǎn)當(dāng)做一個(gè)類簇，所以原始類簇的大小等于樣本點(diǎn)的個(gè)數(shù)，然后依據(jù)某種準(zhǔn)則合并這些初始的類簇，直到達(dá)到某種條件或者達(dá)到設(shè)定的分類數(shù)目。用算法描述：
輸入：樣本集合D，聚類數(shù)目或者某個(gè)條件（一般是樣本距離的閾值，這樣就可不設(shè)置聚類數(shù)目）
輸出：聚類結(jié)果

1.將樣本集中的所有的樣本點(diǎn)都當(dāng)做一個(gè)獨(dú)立的類簇；
   repeat：
        2.計(jì)算兩兩類簇之間的距離（后邊會(huì)做介紹），找到距離最小的兩個(gè)類簇c1和c2；
        3.合并類簇c1和c2為一個(gè)類簇；
   util：達(dá)到聚類的數(shù)目或者達(dá)到設(shè)定的條件

例圖：

在這里插入圖片描述

歐式距離的計(jì)算公式

[image:E08D07F4-264A-4362-B98A-429FA4210548-6915-000000737A78FA8B/Euclidean-distance1.png]

類簇間距離的計(jì)算方法有許多種：
(1)就是取兩個(gè)類中距離最近的兩個(gè)樣本的距離作為這兩個(gè)集合的距離，也就是說(shuō)，最近兩個(gè)樣本之間的距離越小，這兩個(gè)類之間的相似度就越大
(2)取兩個(gè)集合中距離最遠(yuǎn)的兩個(gè)點(diǎn)的距離作為兩個(gè)集合的距離
(3)把兩個(gè)集合中的點(diǎn)兩兩的距離全部放在一起求一個(gè)平均值，相對(duì)也能得到合適一點(diǎn)的結(jié)果。
e.g.下面是計(jì)算組合數(shù)據(jù)點(diǎn)(A,F)到(B,C)的距離，這里分別計(jì)算了(A,F)和(B,C)兩兩間距離的均值。

[image:0CB2E090-F082-4282-91D6-8D6709BA4395-6915-00000073E16E99F7/AFtoBC-1024x110.png]

(4)取兩兩距離的中值，與取均值相比更加能夠解除個(gè)別偏離樣本對(duì)結(jié)果的干擾。
(5)求每個(gè)集合的中心點(diǎn)(就是將集合中的所有元素的對(duì)應(yīng)維度相加然后再除以元素個(gè)數(shù)得到的一個(gè)向量)，然后用中心點(diǎn)代替集合再去就集合間的距離

實(shí)現(xiàn)

接下來(lái)以世界銀行樣本數(shù)據(jù)集進(jìn)行簡(jiǎn)單實(shí)現(xiàn)。該數(shù)據(jù)集以標(biāo)準(zhǔn)格式存儲(chǔ)在名為WBClust2013.csv的CSV格式的文件中。其有80行數(shù)據(jù)和14個(gè)變量。數(shù)據(jù)來(lái)源

在這里插入圖片描述

為了使得結(jié)果可視化更加方便，我將最后一欄人口數(shù)據(jù)刪除了。并且在實(shí)現(xiàn)層次聚類之后加入PCA降維與原始結(jié)果進(jìn)行對(duì)比。

from scipy.cluster.hierarchy import linkage, dendrogram, fcluster
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np


data = pd.read_csv('data/WBClust2013.csv')
data.pop('Pop')
# data.pop('RuralWater')
# data.pop('CellPhone')
# data.pop('LifeExp')
data = data[:20]
country = list(data['Country'])
data.pop('Country')

# 以下代碼為僅使用層次聚類

plt.figure(figsize=(9, 7))
plt.title("original data")
mergings = linkage(data, method='average')
# print(mergings)
dendrogram(mergings, labels=country, leaf_rotation=45, leaf_font_size=8)
plt.show()
Z = linkage(data, method='average')
print(Z)
cluster_assignments = fcluster(Z, t=3.0, criterion='maxclust')
print(cluster_assignments)
for i in range(1, 4):
    print('cluster', i, ':')
    num = 1
    for index, value in enumerate(cluster_assignments):
        if value == i:
            if num % 5 == 0:
                print()
            num += 1
            print(country[index], end='  ')
    print()

# 以下代碼為加入PCA進(jìn)行對(duì)比
class myPCA():

    def __init__(self, X, d=2):
        self.X = X
        self.d = d

    def mean_center(self, data):
        """
        去中心化
        :param data: data sets
        :return:
        """
        n, m = data.shape
        for i in range(m):
            aver = np.sum(self.X[:, i])/n
            x = np.tile(aver, (1, n))
            self.X[:, i] = self.X[:, i]-x

    def runPCA(self):

        # 計(jì)算協(xié)方差矩陣，得到特征值，特征向量
        S = np.dot(self.X.T, self.X)
        S_val, S_victors = np.linalg.eig(S)
        index = np.argsort(-S_val)[0:self.d]
        Y = S_victors[:, index]
        # 得到輸出樣本集
        Y = np.dot(self.X, Y)
        return Y

# data_for_pca = np.array(data)
# pcaObject=myPCA(data_for_pca,d=2)
# pcaObject.mean_center(data_for_pca)
# res=pcaObject.runPCA()

# plt.figure(figsize=(9, 7))
# plt.title("after pca")
# mergings = linkage(res,method='average')
# print(mergings)
# dendrogram(mergings,labels=country,leaf_rotation=45,leaf_font_size=8)
# plt.show()
# Z = linkage(res, method='average')
# print(Z)
# cluster_assignments = fcluster(Z, t=3.0, criterion='maxclust')
# print(cluster_assignments)
# for i in range(1,4):
#     print('cluster', i, ':')
#     num = 1
#     for index, value in enumerate(cluster_assignments):
#         if value == i:
#             if num % 5 ==0:
#                 print()
#             num+=1
#             print(country[index],end='  ')
#     print()

兩次分類結(jié)果都是一樣的：

cluster 1 :
China  United States  Indonesia  Brazil  
Russian Federation  Japan  Mexico  Philippines  Vietnam  
Egypt, Arab Rep.  Germany  Turkey  Thailand  France  
United Kingdom  
cluster 2 :
India  Pakistan  Nigeria  Bangladesh  
cluster 3 :
Ethiopia

通過(guò)樹(shù)狀圖對(duì)結(jié)果進(jìn)行可視化

原始樹(shù)狀圖：

在這里插入圖片描述