机器学习——层次聚类（超详细）.pdfVIP

机器学习——层次聚类 （超详细） 层次聚类 层次聚类 ：层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中 层次聚类类型 ：⾃下⽽上 （bottom-up）或称聚合(agglomerative)、⾃上⽽下(top-down)或称分裂 （divisive） 谨记 ：层次聚类中每个样本只属于⼀个类，所以层次聚类属于硬聚类 （⼀般来说聚类分为硬聚类和软聚类，硬聚类明确 ⼀个样本只属于⼀ 个类，⽽软聚类的⼀个样本可以属于多个类） 聚合聚类 开始将每个样本各分到⼀个类，之后将距离相近的两类合并，建⽴⼀个新的类，重复此操作直到满⾜停⽌条件，得到层次化的类别 分裂聚类 开始将所有的样本分到⼀个类，之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满⾜停⽌条件，得到层次化的类别 实际问题中多以聚合聚类为主，故本⽂仅研究聚合聚类算法. 聚合聚类三要素 ： （1）距离或相似度 （可⽤闵可夫斯基距离、马哈拉诺⽐斯距离、相关系数、夹⾓余弦） ； （2）合并规则 （类间距离最⼩） ； （3）停⽌条件 （类的个数达到阈值） 聚合聚类算法 输⼊ ：n个样本组成的样本集合及样本之间的距离； 输出：对样本集合的⼀个层次化聚类 （1）计算n个样本两两之间的欧⽒距离{dij },记作矩阵D=[dij ]n*n. （2）构造n个类，每个类只包含⼀个样本 （3）合并类间距离最⼩的两个类，其中最短距离为类间距离，构建⼀个新类 （4）计算新类与当前各类的距离 若类的个数为 1，终⽌计算，否则回到步 （3） 3 聚合层次聚类的时间复杂度是O(n m),其中m样本的维数，n是样本个数 举个例⼦，将26个字母随机分配了坐标(x,y) 假设 K=3 ，合并的步骤为 ： （1）26个字母⾸先被分配成 26 个簇 （2）两两欧⽒距离最近的两个簇合并，此时簇变成了 13 个 （3）再次两两欧⽒距离最近的两个簇合并，此时⼀共有 12 个簇合并成了6个簇，还余下⼀个簇，因此此时剩下 6+ 1=7 个簇 （4）⼀直重复上⼀步的操作，直到簇的数量为 3 的时候，就算是分簇完成 相应python代码如下 ： # !/ usr/bin/py thon3.4 # - *- coding : utf-8 - *- import random # ⽣成坐标字典 def buildclusters() : clusters = {} keys = [chr(i) for i in range(ord(A) ord(Z) + 1)] # [ A , B, , 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