机器学习——层次聚类（超详细）
层次聚类
层次聚类：层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。
层次聚类类型：⾃下⽽上（bottom-up）或称聚合(agglomerative)、⾃上⽽下(top-down)或称分裂（divisive）。年度审计计划
谨记：层次聚类中每个样本只属于⼀个类，所以层次聚类属于硬聚类。（⼀般来说聚类分为硬聚类和软聚类，硬聚类明确⼀个样本只属于⼀个类，⽽软聚类的⼀个样本可以属于多个类）。
聚合聚类
开始将每个样本各分到⼀个类，之后将距离相近的两类合并，建⽴⼀个新的类，重复此操作直到满⾜停⽌条件，得到层次化的类别。
分裂聚类
开始将所有的样本分到⼀个类，之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满⾜停⽌条件，得到层次化的类别。
实际问题中多以聚合聚类为主，故本⽂仅研究聚合聚类算法.
聚合聚类三要素：
（1）距离或相似度（可⽤闵可夫斯基距离、马哈拉诺⽐斯距离、相关系数、夹⾓余弦）；
（2）合并规则（类间距离最⼩）；
（3）停⽌条件（类的个数达到阈值）。
聚合聚类算法
输⼊：n个样本组成的样本集合及样本之间的距离；
所有
输出：对样本集合的⼀个层次化聚类。
（1）计算n个样本两两之间的欧⽒距离{dij}，记作矩阵D=[dij]n*n.
（2）构造n个类，每个类只包含⼀个样本。
（3）合并类间距离最⼩的两个类，其中最短距离为类间距离，构建⼀个新类。
（4）计算新类与当前各类的距离。若类的个数为1，终⽌计算，否则回到步（3）
n3
聚合层次聚类的时间复杂度是O( m)，其中m样本的维数，n是样本个数。
举个例⼦，将26个字母随机分配了坐标(x,y)
假设 K=3 ，合并的步骤为：
（1）26个字母⾸先被分配成 26 个簇
（2）两两欧⽒距离最近的两个簇合并，此时簇变成了 13 个
（3）再次两两欧⽒距离最近的两个簇合并，此时⼀共有 12 个簇合并成了6个簇，还余下⼀个簇，因此此时剩下 6+1=7 个簇
（4）⼀直重复上⼀步的操作，直到簇的数量为 3 的时候，就算是分簇完成
相应python代码如下：
# !/usr/bin/python3.4
# -*- coding: utf-8 -*-
import random
# ⽣成坐标字典
def buildclusters():
clusters ={}
keys =[chr(i)for i in range(ord('A'),ord('Z')+1)]
# ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
# ⽣成第⼀个分簇坐标
for i in range(0,9):
# A-I
temp ={}
x = random.randint(0,40)
y = random.randint(0,40)
temp["x"]= x
temp["y"]= y
clusters[keys[i]]= temp
clusters[keys[i]]= temp大学申请
# ⽣成第⼆个分簇坐标
for i in range(9,18):
# J-R
temp ={}
x = random.randint(60,100)
y = random.randint(0,40)
temp["x"]= x
temp["y"]= y
clusters[keys[i]]= temp
# ⽣成第三个分簇坐标
for i in range(18,26):
# S-Z
temp ={}
x = random.randint(40,60)
y = random.randint(60,100)
temp["x"]= x
temp["y"]= y
clusters[keys[i]]= temp
# {'K': {'y': 34, 'x': 81}, 'V': {'y': 68, 'x': 50}, 'G': {'y': 1, 'x': 10}, 'C': {'y': 2, 'x': 9}, 'T': {'y': 78, 'x': 40}, 'A': {'y': 20, 'x': 12}, 'B': {'y': 21, 'x': 39}, 'N': {'y': 37, 'x': 6 7}, 'S': {'y': 92, 'x': 56}, 'Q': {'y': 7, 'x': 62}, 'D': {'y': 18, 'x': 4}, 'E': {'y': 0, 'x': 38}, 'Z': {'y': 92, 'x': 46}, 'H': {'y': 30, 'x': 32}, 'I': {'y': 21, 'x': 35}, 'U': {'y': 71, 'x': 51}, 'L': {'y': 1, 'x': 96}, 'W': {'y': 99, 'x': 59}, 'F': {'y': 10, 'x': 14}, 'O': {'y': 16, 'x': 97}, 'J': {'y': 37, 'x': 76}, 'X': {'y': 86, 'x': 49}, 'Y': {'y': 67, 'x': 50}, 'P': {'y': 17, 'x': 76}, 'M': {'y': 32, 'x': 88}, 'R': {'y': 6, 'x': 70}}
return clusters
# 两点间的距离公式/欧式距离
def distance(x1, x2, y1, y2):
distan =((x1 - x2)**2+(y1 - y2)**2)**0.5
return distan
# 计算各个分簇直到达到分簇的效果
def splitcluster(clusters):nrce
dict={}
newdict ={}
arr =[]
i =1
for key1 in clusters:
temp ={}
for key2 in clusters:
if key1 != key2:
if key1 in arr or key2 in arr:
pass
el:
双胞胎英语name =str(key1 +"->"+ key2)
temp[name]= distance(clusters[key1]["x"], clusters[key2]["x"], clusters[key1]["y"],
clusters[key2]["y"])
arr.append(key1)
arr.append(key2)
if temp:
# rever=Fal值按照从⼩到⼤排序
temp =sorted(temp.items(), key=lambda d: d[1], rever=Fal)
newdict[temp[0][0]]= temp[0][1]
newdict =sorted(newdict.items(), key=lambda d: d[1], rever=Fal)
英语八下单词
for item in newdict:
name ="cluster"+str(i)
i +=1
dict[name]= item[0]
# {'cluster13': 'B->T', 'cluster11': 'U->M', 'cluster10': 'Z->H', 'cluster5': 'L->D', 'cluster1': 'F->E', 'cluster4': 'G->A', 'cluster12': 'I->S', 'cluster3': 'W->V', 'clust
# {'cluster13': 'B->T', 'cluster11': 'U->M', 'cluster10': 'Z->H', 'cluster5': 'L->D', 'cluster1': 'F->E', 'cluster4': 'G->A', 'cluster12': 'I->S', 'cluster3': 'W->V', 'clust er8': 'C->R', 'cluster9': 'P->X', 'cluster2': 'K->N', 'cluster7': 'O->Q', 'cluster6': 'Y->J'}
return dict
# 判断分簇
def judgecluster(clusters, firstcluster, K):
dict={}
i =1
arr =[]
for item in firstcluster:
temparr = firstcluster[item].split("->")
distan ={}
for judge in temparr:
if judge in arr:
pass
el:
for value in clusters:
if value in temparr:
pass
elif value in arr:
pass
el:
for key in temparr:
name = value +"->"+ key
distan[name]= distance(clusters[key]["x"], clusters[value]["x"], clusters[key]["y"],
clusters[value]["y"])
if key in arr:
pass
el:
arr.append(key)
if distan:
distan =sorted(distan.items(), key=lambda d: d[1], rever=Fal)
# print(distan)
element = distan[0][0].split("->")[0]
for ele in firstcluster:
elearr = firstcluster[ele].split("->")
if element in elearr:
values = firstcluster[item]
for va in elearr:
values = values +"->"+ va
arr.append(va)
cluster ="cluster"+str(i)
i +=1
dict[cluster]= values
if len(arr)!=26:
# ⽣成26个字母
letters =[chr(i)for i in range(ord('A'),ord('Z')+1)]
# 得到剩下没有被放到dict的字母
remain =[]
for letter in letters:
if letter in arr:
pass
el:
remain.append(letter)
开学啦作文dis ={}
for letter in remain:
for item in dict:
elearr =dict[item].split("->")
for ele in elearr:
name = letter +"->"+ ele
dis[name]= distance(clusters[letter]["x"], clusters[ele]["x"], clusters[letter]["y"],
clusters[ele]["y"])
难忘的旅行作文
if dis:
dis =sorted(dis.items(), key=lambda d: d[1], rever=Fal)
dis =sorted(dis.items(), key=lambda d: d[1], rever=Fal)
element = dis[0][0].split("->")
for cluster in dict:
array =dict[cluster].split("->")
for item in element:
if item in array:
values ="->".join(remain)
dict[cluster]=dict[cluster]+"->"+ values
if len(dict)== K:
print(dict)
# {'cluster1': 'M->X->P->Y->J->U->T->R->L->O', 'cluster3': 'V->B->W->N->E->A->I->G', 'cluster2': 'C->H->Q->F->D->S->Z->K'} return dict
el:
judgecluster(clusters,dict, K)
if __name__ =='__main__':
K =3
clusters = buildclusters()
firstcluster = splitcluster(clusters)
judgecluster(clusters, firstcluster, K)
结果如下：
