起步

层次聚类( Hierarchical Clustering )是聚类算法的一种，通过计算不同类别的相似度类创建一个有层次的嵌套的树。

层次聚类算法介绍

假设有 n 个待聚类的样本，对于层次聚类算法，它的步骤是：

步骤一：(初始化)将每个样本都视为一个聚类；

步骤二：计算各个聚类之间的相似度；

步骤三：寻找最近的两个聚类，将他们归为一类；

步骤四：重复步骤二，步骤三；直到所有样本归为一类。

整个过程就是建立一棵树，在建立的过程中，可以在步骤四设置所需分类的类别个数，作为迭代的终止条件，毕竟都归为一类并不实际。

聚类之间的相似度

聚类和聚类之间的相似度有什么来衡量呢？既然是空间中的点，可以采用距离的方式来衡量，一般有下面三种：

Single Linkage

又叫做 nearest-neighbor ，就是取两个类中距离最近的两个样本的距离作为这两个集合的距离。这种计算方式容易造成一种叫做 Chaining 的效果，两个 cluster 明明从“大局”上离得比较远，但是由于其中个别的点距离比较近就被合并了，并且这样合并之后 Chaining 效应会进一步扩大，最后会得到比较松散的 cluster 。

Complete Linkage

这个则完全是 Single Linkage 的反面极端，取两个集合中距离最远的两个点的距离作为两个集合的距离。其效果也是刚好相反的，限制非常大。这两种相似度的定义方法的共同问题就是指考虑了某个有特点的数据，而没有考虑类内数据的整体特点。

Average Linkage 这种方法就是把两个集合中的点两两的距离全部放在一起求均值，相对也能得到合适一点的结果。有时异常点的存在会影响均值，平常人和富豪平均一下收入会被拉高是吧，因此这种计算方法的一个变种就是取两两距离的中位数。

python 实现层次聚类

空间中点的距离使用欧式距离：

import math

import numpy as np

def euler_distance(point1: np.ndarray, point2: list) -> float:

"""

计算两点之间的欧拉距离，支持多维

"""

distance = 0.0

for a, b in zip(point1, point2):

distance += math.pow(a - b, 2)

return math.sqrt(distance)

定义聚类数的节点:

class ClusterNode(object):

def __init__(self, vec, left=None, right=None, distance=-1, id=None, count=1):

"""

:param vec: 保存两个数据聚类后形成新的中心

:param left: 左节点

:param right: 右节点

:param distance: 两个节点的距离

:param id: 用来标记哪些节点是计算过的

:param count: 这个节点的叶子节点个数

"""

self.vec = vec

self.left = left

self.right = right

self.distance = distance

self.id = id

self.count = count

vec 表示合并后的聚类中心，是一个点，代表整个聚类的位置；distance 表示左节点和右节点的距离。

计算层次聚类算法的类：

class Hierarchical(object):

def __init__(self, k = 1):

assert k > 0

self.k = k

self.labels = None

def fit(self, x):

nodes = [ClusterNode(vec=v, id=i) for i,v in enumerate(x)]

distances = {}

point_num, future_num = np.shape(x) # 特征的维度

self.labels = [ -1 ] * point_num

currentclustid = -1

while len(nodes) > self.k:

min_dist = math.inf

nodes_len = len(nodes)

closest_part = None # 表示最相似的两个聚类

for i in range(nodes_len - 1):

for j in range(i + 1, nodes_len):

# 为了不重复计算距离，保存在字典内

d_key = (nodes[i].id, nodes[j].id)

if d_key not in distances:

distances[d_key] = euler_distance(nodes[i].vec, nodes[j].vec)

d = distances[d_key]

if d < min_dist:

min_dist = d

closest_part = (i, j)

# 合并两个聚类

part1, part2 = closest_part

node1, node2 = nodes[part1], nodes[part2]

new_vec = [ (node1.vec[i] * node1.count + node2.vec[i] * node2.count ) / (node1.count + node2.count)

for i in range(future_num)]

new_node = ClusterNode(vec=new_vec,

left=node1,

right=node2,

distance=min_dist,

id=currentclustid,

count=node1.count + node2.count)

currentclustid -= 1

del nodes[part2], nodes[part1] # 一定要先del索引较大的

nodes.append(new_node)

self.nodes = nodes

self.calc_label()

def calc_label(self):

"""

调取聚类的结果

"""

for i, node in enumerate(self.nodes):

# 将节点的所有叶子节点都分类

self.leaf_traversal(node, i)

def leaf_traversal(self, node: ClusterNode, label):

"""

递归遍历叶子节点

"""

if node.left == None and node.right == None:

self.labels[node.id] = label

if node.left:

self.leaf_traversal(node.left, label)

if node.right:

self.leaf_traversal(node.right, label)

最后将聚类的列表标记保存于 labels 中。

测试

与 sklearn 进行对比：

iris = datasets.load_iris()

my = Hierarchical(4)

my.fit(iris.data)

print(np.array(my.labels))

sk = cluster.AgglomerativeClustering(4)

sk.fit(iris.data)

print(sk.labels_)

得到输出：

[3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 2 1 2 2 2 2 1 2 2 2 2

2 2 1 1 2 2 2 2 1 2 1 2 1 2 2 1 1 2 2 2 2 2 1 2 2 2 2 1 2 2 2 1 2 2 2 1 2

2 1]

[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 2 3 2 3 2 3 3 2 3 2 3 2 3 3 2 3 2 2 2 2

2 2 2 0 2 3 3 3 3 2 3 2 2 2 3 3 3 2 3 3 3 3 3 2 3 3 0 2 0 0 0 0 3 0 0 0 0

0 0 2 2 0 0 0 0 2 0 2 0 2 0 0 2 2 0 0 0 0 0 2 2 0 0 0 2 0 0 0 2 0 0 0 2 0

0 2]

结果还算是理想的。

层次聚类的优缺点

优点：

一次性得到聚类树，后期再分类无需重新计算；

相似度规则容易定义；

可以发现类别的层次关系。

缺点：

计算复杂度高，不适合数据量大的；

算法很可能形成链状。

附录

from scipy.cluster import hierarchy

0.层次聚类的概念

层次聚类和k-means一样都是很常用的聚类方法。层次聚类是对群体的划分，最终将样本划分为树状的结构。他的基本思路是每个样本先自成一类，然后按照某种规则进行合并，直到只有一类或者某一类的样本只有一个点。层次聚类又分为自底而上的聚合层次聚类和自顶而下的分裂层次聚类。

0.1 聚合层次聚类

每一个点初始为1类，得到N(样本点个数)类，计算每一类之间的距离，计算方法有很多，具体可以参考距离的计算方法。聚合层次聚类方法的终止条件是所有样本点都处于同一类了，或者两类之间的距离超过设置的某个阈值。大多数层次聚类都是聚合层次聚类。

0.2 分裂层次聚类

和聚合层次聚类是反着的，属于自上而下的一种聚类方法。刚开始的时候所有的样本点都位于同一类，然后一步步划分，终止条件是所有的样本点都位于单独的一类，或者两类之间的距离超过设置的某个阈值。

下面这个图可以比较好的说明这个过程：

层次聚类的两种方法

1.凝聚层次聚类算法步骤

1.1 算法过程

1)N个样本单独成类，G1(0)、G2(0)、G3(0)、……、GN(0)，0代表初始状态。

2)更新距离矩阵D(n)，找出D(n)中最小值，把对应的两类合并为1类。

3)更新距离矩阵D(n+1)，重复步骤2-3。

当两类之间的最小距离小于给定的阈值或者所有样本都单独成类的时候，结束算法。

1.2算法案例

有个老师带了五个学生，想给学生分组，让他们分组学习，采用层次聚类来对学生进行聚类，基础数据如下图。

学生基础数据

先来算距离D(0)，就采用欧式距离就好了。

初始距离矩阵

找到最小的那两个合并为1类。

合并后的新数据

然后计算更新后的距离D(1)

合并的后新距离

以后的以此类推：

聚类的整体过程

我们看到其实124是一类，35是一类。

画出图来就是下面这个格式：

聚类结果

3.Python处理层次聚类的包

用的是在scipy.cluster里的hierarchy方法，下面来看代码，支持hierarchical clustering 和 agglomerative clustering。

首先来看一些基本函数的用法

linkage

scipy.cluster.hierarchy.linkage(data,method = 'single')

method 参数是类距离的计算公式

singele 两个类之间最短的点的距离

complete 两个类之间最长距离的点的距离

centroid 两个类所有点的中点的距离

pdist计算样本点之间的两两距离

scipy.cluster.hierarchy.distance.pdist(data, metric='euclidean')

metric参数是求距离的方法，默认是欧氏距离，可选的还有：

‘braycurtis’, ‘canberra’, ‘chebyshev’, ‘cityblock’, ‘correlation’, ‘cosine’, ‘dice’, ‘euclidean’, ‘hamming’, ‘jaccard’, ‘jensenshannon’, ‘kulsinski’, ‘mahalanobis’, ‘matching’, ‘minkowski’, ‘rogerstanimoto’, ‘russellrao’, ‘seuclidean’, ‘sokalmichener’, ‘sokalsneath’, ‘sqeuclidean’, ‘yule’

关于求距离的函数我可能还会再更一篇文章，感兴趣的朋友可以等一下。笔者之前算字符相似度自己还写了一个杰尔卡德相似度，现在看看真实太费事了。

dendrogram(linkage)

scipy.cluster.hierarchy.dendrogram(linkage)，这个函数是画图用的。

import numpy

import pandas

from sklearn import datasets

import scipy.cluster.hierarchy as hcluster

import scipy

#iris = datasets.load_iris()

#data = iris.data

#target = iris.target

points=scipy.randn(20,4)

# Compute and plot first dendrogram.

linkage = hcluster.linkage(points, method='centroid')

hcluster.dendrogram(linkage, leaf_font_size=10.)

p = hcluster.fcluster( linkage, 3, criterion='maxclust')

聚类结果如下图所示：

聚类结果

以上就是层次聚类的简单应用，当然有不同的需求可以继续探索一些函数的参数，这个方法还是很好用的。