层次聚类方法是古老而且常用的聚类方法。层次聚类方法的基本思想是：通过某种相似性测度计算节点之间的相似性，并按相似度由高到低排序，逐步重新连接个节点。
事实上，层次聚类有两大种策略，一种是自下至上，一种是自上到下。
凝聚的层次聚类算法与分裂的层次聚类算法
凝聚：先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。
分裂：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。该种方法一般较少使用
AGNES算法（凝聚）
AGNES算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步一步地合并。例如，在簇A中的一个对象和簇B中的一个对象之间的距离是所有属于不同簇的对象之间最小的，那么A、B可能被合并。这是一种单链接方法，其每一个簇都可以被簇中所有对象代表，两个簇间的相似度由这两个簇中距离最近的数据点的相似度来确定。聚类的合并过程反复进行直到所有的对象最终合并形成一个簇。在聚类中，用户可定义希望得到的簇数目作为一个结束条件。
1、执行步骤
step1：将数据集中的每个样本初始化为一个簇，并放入集合C中。当前簇的个数为q。
step2：当q大于k（目标数量）时在C中找到距离最近的两个簇C(i)和C(j), 将C(i)和C(j)合并，更新集合C。q-1。
step3：循环步骤2直到q=k，返回聚类集合C
2、优缺点
（1）优点
- 简单，但可能遇到合并点选择困难的情况。如果在某一步没有很好地选择出合并点，很可能导致低质量的聚类结果。
（2）缺点
- 一旦一组对象被合并，不能撤销
- 此算法没有良好的可伸缩性，算法的复杂度为O(n的平方)，复杂度较高不适合大数据集。
3、代码实现
# coding=utf-8
'''
AGNES算法
'''
import numpy as np
import math
import matplotlib.pyplot as plt
flag = 1
#==============================================
# 计算距离
#==============================================
def euclidean_dist(p, q):
'''
欧式距离(L2范数)
INPUT -> 长度一致的向量1、向量2
'''
p = np.mat(p)
q = np.mat(q)
return math.sqrt(np.sum(np.power(p-q, 2)))
def dist_min(C1, C2):
'''
两个簇中最小距离
INPUT -> 簇1、簇2
'''
return min(euclidean_dist(i, j) for i in C1 for j in C2)
def dist_max(C1, C2):
'''
两个簇中最大距离
INPUT -> 簇1、簇2
'''
return max(euclidean_dist(i, j) for i in C1 for j in C2)
def dist_avg(C1, C2):
'''
两个簇中平均距离
INPUT -> 簇1、簇2
'''
return sum(euclidean_dist(i, j) for i in C1 for j in C2)/(len(C1)*len(C2))
#==============================================
# 找到距离最小的簇
#==============================================
def find_Min(ClusterSet):
'''
找到簇间距离中最小的一对
INPUT -> 簇的集合
'''
min = 10000
x = 0
y = 0
for i in range(len(ClusterSet)):
for j in range(len(ClusterSet)):
if i != j and dist_min(ClusterSet[i], ClusterSet[j]) < min:
min = dist_min(ClusterSet[i], ClusterSet[j])
x = i
y = j
return (x, y)
#==============================================
# 算法核心部分
#==============================================
def AGNES(dataSet, k):
'''
AGNES算法
INPUT -> 数据集、聚类中心数
'''
global flag
# 聚类结果
output = []
for i in dataSet:
temp = []
temp.append(i)
output.append(temp)
# 当前簇个数
q = len(output)
# 合并更新
while q >= k:
# 打印聚类过程
print('------------------------第'+str(flag)+'次迭代--------------------------')
for i in range(q):
print('第'+str(i+1)+'组:', output[i], end='\n')
x, y = find_Min(output)
output[x].extend(output[y])
output.remove(output[y])
q -= 1
flag += 1
print('已收敛，执行结束')
return output
#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
a = [np.random.randint(0, 50) for _ in range(50)]
b = [np.random.randint(10, 100) for _ in range(50)]
c = [np.random.randint(0, 10) for _ in range(50)]
points = [[a,b,c] for a,b,c in zip(a,b,c)]
output = AGNES(dataSet=points, k=5)
print(output)
