一、Hierarchical Clustering之算法原理

算法介绍
首先呢，Hierarchical Clustering是属于无监督的聚类方法，具体来说又分为多种更细的方法，如合并法、分解法、树状图。本文主要实现的是合并法。而像常用的Kmeans并不属于层次聚类，而是属于非层次聚类。
算法原理
Hierarchical Clustering中的合并法很好理解，先将样本划分为多个集合，然后计算两两集合之间的距离并构造距离矩阵D，具体来说每个集合的特征表示可以为集合内所有样本均值等多种方法，本文主要考虑取集合中样本均值作为集合的特征值，其他方法就不深究了。得到距离矩阵D之后，找出距离最小的两个集合并合并，然后更新距离矩阵D并执行下一次合并，直到所有集合的数量满足为自己所要的类别数量，算法停止。
具体实例（说人话）
假设有n=1000条样本，最终聚类目标是m = 10个类别。那么将1000条样本划分为1000个集合，每个集合目前只包含一条样本。计算两两集合距离矩阵D，其维度是1000*1000，对角线上是0。找出D中的最小值min(D)，并合并对应的行列所代表的样本，成为一个新的集合。此时集合数量为999个了，更新一下距离矩阵D，注意如果此处根据我写的代码重新计算则:
计算复杂度= n²+(n-1)²+(n-2)²+…+(m+1)²=∑ （不太懂怎么码这个katex，看懂了就行吧)
然后我就发现我1000条数据预估要跑半天，迭代实在是太慢了，在数据导入的时候使用了.sample(n=50)，嘿嘿，这下子还是很快的。各位大佬们可以自己改一下矩阵更新的过程，保留上一次迭代大部分距离矩阵D的内容，只更新当次迭代进行了合并的集合，只有它们的距离发生了改变。

二、python源码

代码如下（示例）：

1.Hierarchical Clustering.py

# -*- coding: utf-8 -*-

import pandas as pd
import numpy as np


class HC(object):

    def __init__(self, data,categorynums):
        self.Clustering_Data = data
        self.hc = []
        self.cnt = 0
        self.categorynums = categorynums
        self.start()

    def indmin_matrix(self, M):
        row, col = divmod(np.argmin(M), np.shape(M)[1])
        return row, col

    def em(self, A, B):
        efunc = lambda a, b: np.power(float(a) - float(b), 2)
        func = np.frompyfunc(efunc, 2, 1)
        em = np.sqrt(sum(func(A, B)))
        return em

    def AverageLinkage(self, A, B):
        total = 0.0
        for i in A:
            for j in B:
                total += self.em(i, j)
        ret = total / (np.shape(A)[0] * np.shape(B)[0])
        return ret

    def start(self):
        self.cnt += 1
        print('\n\n===================%d times Hierarical Clustring================' % self.cnt)
        # 首次进行算法，要初始化结果数组
        if 0 == np.shape(self.hc)[0]:
            initData = [[i] for i in range(np.shape(self.Clustering_Data)[0])]
            self.hc = [initData]
            print('init self.hc:', self.hc)
        preHC, n = self.hc[-1], np.shape(self.hc[-1])[0]
        print('preHC:', preHC)
        # 剩下的集合数量为categorynums时停止聚类
        if self.categorynums == n:
            print('succeed hierarical clustring:\n', )
            for i in range(np.shape(self.hc)[0]):
                print(self.hc[i])
            return self.hc
        # 继续聚类
        dist = np.full(shape=(n, n), fill_value=np.inf)
        value = np.array(self.Clustering_Data)[:, -1]
        for i in range(n):
            for j in np.arange(start=i + 1, stop=n, step=1):
                A, B = value[preHC[i]], value[preHC[j]]
                dist[i, j] = self.AverageLinkage(A, B)
        print('dist:\n', dist)
        # 更新聚类结果
        row, col = self.indmin_matrix(dist)
        C = []
        newHC = []
        for i in range(n):
            if row == i or col == i:
                if np.shape(C)[0] == 0:
                    C = preHC[row] + preHC[col]
                    newHC.append(C)
                continue
            newHC.append(preHC[i])
        # 更新HC结果数组
        self.hc.append(newHC)
        # for i in range(np.shape(self.hc)[0]):
        #     print(self.hc[i])
        return self.start()


if __name__ == '__main__':
    #n是采样数，建议值为100以下，否则运算太慢
    df = pd.read_csv('../../../../Tencent/2668630468/FileRecv/BWGHT.csv')
    df = df.fillna(0)
    df = df.reset_index()
    temp = np.linspace(0, df.shape[0], num=df.shape[0], endpoint=False)
    df['index'] = pd.DataFrame(temp, columns=['index'])
    data = []
    for i in range(df.shape[0]):
        templist = []
        linelist = list(df.loc[i][:].values)
        templist.append([linelist[-1]])
        templist.append(linelist[0:-2])
        data.append(templist)
    # 5是聚类结果的类别数量，可以自行设定
    hc = HC(data,5)