开始
层次聚类(Hierarchical Clustering )是一种聚类算法，通过计算不同类别的相似度类别来创建层次嵌套树。
层次聚类算法介绍
假设有n个要群集的样本。 对于层次聚类算法，其步骤如下：
步骤1 ()初始化：将每个样本视为一个集群；
步骤2 :计算各簇之间的相似度
步骤3 )寻找最近的两个集群，将他们归为一类；
步骤4 :重复步骤2、步骤3； 直到所有的样品都归为一类。
整个过程是种树，在制作过程中，步骤4可以设置所需分类的类数，作为迭代的结束条件，任何一个分类都是不现实的。
集群间相似度
聚类和聚类之间的相似度用什么来衡量呢？ 因为是空间中的点，所以可以用距离来测量。 一般有以下三种。
单链接
也称为nearest-neighbor，将两个类中距离最近的两个样本的距离作为这两个集合的距离。 这种计算方式容易产生被称为Chaining的效果。 两个集群明明脱离了“大局”，但其中每个点的距离很近，所以会合并。 并且，这样合并后，Chaining效果进一步扩大，最终得到比较宽松的集群。
完成链接
这完全是Single Linkage相反一侧的极端，将两个集合中最远的两个点的距离作为两个集合的距离。 其效果正好相反，限制非常大。 这两种相似度定义方法的共同问题是考虑了某些特征性数据，而没有考虑类中数据的整体特征。
Average Linkage方法是将两个集合中的点两个距离全部汇总起来求平均，从而得到相对也合适的结果。 虽然异常点的存在有时会影响平均值，但普通人和富豪平均收入会上升吧。 因此，该计算方法的变种之一是取2、2的距离的中位数。
python实现层次聚类
空间中点的距离使用欧式距离。
导入匹配
import numpy as np
defeuler _ distance (point 1: NP.nd array，point2: list )- float:
''''
计算两点之间的欧拉距离，支持多维
''''
距离=0.0
for a，binzip(point1，point2) :
距离=math.pow (a-b，2 ) )。
返回矩阵. sqrt (距离) )。
定义群集数量的节点：
群集节点(对象) :
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表示聚合群集的中心，而距离是表示整个群集位置的点，表示左节点和右节点之间的距离。
计算层次聚类算法的类：
类日立(对象) :
def __init__(self，k=1) :
资产k 0
self.k=k
self.labels=None
deffit(self，x ) :
nodes=[集群节点(vec=v，id=i ) for i，vinenumerate(x ) ]
距离={ }
point_num，future_num=NP.shape(x ) #特征的维度
self.labels=[ -1 ] * point_num
currentclustid=-1
wileLen(nodes ) self.k:
min_dist=math.inf
nodes_len=len(nodes )
科斯
t_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]
结果还算是理想的。
层次聚类的优缺点
优点：
一次性得到聚类树，后期再分类无需重新计算；
相似度规则容易定义；
可以发现类别的层次关系。
缺点：
计算复杂度高，不适合数据量大的；
算法很可能形成链状。
附录