层次聚类算法

顾名思义，层次聚类就是一层一层的进行聚类，可以由上向下把大的类别（cluster）分割，叫作分裂法；也可以由下向上对小的类别进行聚合，叫作凝聚法；但是一般用的比较多的是由下向上的凝聚方法。

分裂法：

分裂法指的是初始时将所有的样本归为一个类簇，然后依据某种准则进行逐渐的分裂，直到达到某种条件或者达到设定的分类数目。用算法描述：
输入：样本集合D，聚类数目或者某个条件（一般是样本距离的阈值，这样就可不设置聚类数目）
输出：聚类结果

1.将样本集中的所有的样本归为一个类簇；
repeat：
    2.在同一个类簇（计为c）中计算两两样本之间的距离，找出距离最远的两个样本a,b；
    3.将样本a，b分配到不同的类簇c1和c2中；
    4.计算原类簇（c）中剩余的其他样本点和a，b的距离，若是dis(a)<dis(b)，则将样本点归到c1中，否则归到c2中；
util： 达到聚类的数目或者达到设定的条件

凝聚法：

凝聚法指的是初始时将每个样本点当做一个类簇，所以原始类簇的大小等于样本点的个数，然后依据某种准则合并这些初始的类簇，直到达到某种条件或者达到设定的分类数目。用算法描述：
输入：样本集合D，聚类数目或者某个条件（一般是样本距离的阈值，这样就可不设置聚类数目）
输出：聚类结果

  1.将样本集中的所有的样本点都当做一个独立的类簇；
   repeat：
        2.计算两两类簇之间的距离（后边会做介绍），找到距离最小的两个类簇c1和c2；
        3.合并类簇c1和c2为一个类簇；
   util： 达到聚类的数目或者达到设定的条件

例图：

类簇间距离的计算方法有许多种：
(1)就是取两个类中距离最近的两个样本的距离作为这两个集合的距离，也就是说，最近两个样本之间的距离越小，这两个类之间的相似度就越大
(2)取两个集合中距离最远的两个点的距离作为两个集合的距离
(3)把两个集合中的点两两的距离全部放在一起求一个平均值，相对也能得到合适一点的结果。
e.g.对于u中所有点i和v中所有点j

其中|u|，|v|是聚类u和v中元素的的个数，这也被称为UPGMA算法（非加权组平均）法。
(4)取两两距离的中值，与取均值相比更加能够解除个别偏离样本对结果的干扰。
(5)求每个集合的中心点(就是将集合中的所有元素的对应维度相加然后再除以元素个数得到的一个向量)，然后用中心点代替集合再去就集合间的距离

实现

接下来以世界银行样本数据集进行简单实现。该数据集以标准格式存储在名为WBClust2013.csv的CSV格式的文件中。其有80行数据和14个变量。数据来源

将数据分为三个聚簇，并且在实现层次聚类之后加入PCA降维与原始结果进行对比。

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 = data[:20]
country = list(data['Country'])
data.pop('Country')
data_zs = 1.0*data/data.max()#归一化
# print(data_zs)

# 以下代码为仅使用层次聚类
plt.figure(figsize=(9, 7))
plt.title("original data")
mergings = linkage(data_zs, method='average')
dendrogram(mergings, labels=country, leaf_rotation=45, leaf_font_size=8)
plt.show()

cluster_assignments = fcluster(mergings, 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进行对比
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):

        # 计算协方差矩阵，得到特征值，特征向量
        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_zs)
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()

# cluster_assignments = fcluster(mergings, 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()

原始数据分类后的聚簇：

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

PCA降维后的分类聚簇：

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

可以看出，分类结果都是一样的。

通过树状图对结果进行可视化

以下为建树数据（以原始数据为例）：

[[18.         19.          0.21641882  2.        ]
 [15.         20.          0.32365701  3.        ]
 [ 2.          9.          0.39212766  2.        ]
 [16.         21.          0.45344319  4.        ]
 [ 8.         22.          0.50024778  3.        ]
 [ 4.         10.          0.50648091  2.        ]
 [13.         14.          0.51344362  2.        ]
 [23.         24.          0.58762227  7.        ]
 [ 3.         25.          0.58872577  3.        ]
 [11.         26.          0.64184605  3.        ]
 [ 5.          6.          0.71918707  2.        ]
 [17.         28.          0.72310738  4.        ]
 [ 0.          1.          0.84679303  2.        ]
 [ 7.         12.          0.90714675  2.        ]
 [30.         33.          0.97508395  4.        ]
 [27.         31.          1.00112956 11.        ]
 [29.         32.          1.15491503  5.        ]
 [35.         36.          1.29675568 16.        ]
 [34.         37.          1.76337101 20.        ]]

对以上数据解析为：第一列和第二列为聚类簇编号；第三列为两个聚簇之间的距离；第四列为包含的聚簇数量。
其中聚簇间距离的计算为上文提到的第三种方法。

原始数据树状图：

PCA降维后的结果：