2.1 距离聚类的概念 2.2 相似性测度和聚类准则 2.3 基于距离阈值的聚类算法 2.4 系统聚类法 2.5 分解聚类法 第2章 聚类分析 2.1 距离聚类的概念 2.2 相似性测度和聚类准则 2.3 基于距离阈值的聚类算法 2.4 系统聚类法 2.5 分解聚类法 2.6 动态聚类法
分类与聚类的区别 分类:用已知类别的样本训练集来设计分类器(监督学习) 聚类(集群):用事先不知样本的类别,而利用样本的先验知识来构造分类器(无监督学习)
2.1 距离聚类的概念 1. 概念:“物以类聚” 聚类分析:根据模式之间的相似性对模式进行分类,是一种非监督分类方法。 2.相似性的含义 2.1 距离聚类的概念 1. 概念:“物以类聚” 聚类分析:根据模式之间的相似性对模式进行分类,是一种非监督分类方法。 2.相似性的含义 有n个特征值则组成n维向量 ,称为该样本的特征向量。它相当于特征空间中的一个点,以特征空间中,点间的距离函数作为模式相似性的测量,以“距离”作为模式分类的依据,距离越小,越“相似”。 注意:聚类分析是否有效,与模式特征向量的分布形式有很大关系。选取的特征向量是否合适非常关键。 例:酱油与可乐。
2.2 相似性测度和聚类准则 2.2.1 相似性测度 相似性测度:衡量模式之间相似性的一种尺度。如:距离。 复习:已知向量 ,则:
1. 欧氏距离(Euclid,欧几里德) ——简称距离 设X1、X2为两个n维模式样本, 欧氏距离定义为: 距离越小,越相似。 ( D_Distance ) 注意: 1)各特征向量对应的维上应当是相同的物理量; 注意物理量的单位。 某些维上物理量采用的单位发生变化,会导致对同样的点集出现不同聚类结果的现象。
2)解决方法:使特征数据标准化,使其与变量的单位无关。 b(5,0) d(4,5) c(1,4) a(0,1) 1 2 3 4 5 (a) d(0.4,5) c(0.1,4) a(0,1) 1 2 3 4 5 b(0.5,0) (b) b(5,0) c(1,0.4) d(4,0.5) a(0,0.1) 1 2 3 4 5 (c) 2)解决方法:使特征数据标准化,使其与变量的单位无关。
2. 马氏距离(Maharanobis) 平方表达式: 式中,X:模式向量; M:均值向量; C:该类模式总体的协方差矩阵。 ( M_Mean ) ( C_covariance) 对n维向量: ,
表示的概念是各分量上模式样本到均值的距离,也就是在各维上模式的分散情况。 越大,离均值越远。 优点:排除了模式样本之间的相关影响 。 当C = I 时,马氏距离为欧氏距离。
n维模式样本向量Xi、Xj间的明氏距离表示为 : 3. 明氏距离( Minkowaki ) n维模式样本向量Xi、Xj间的明氏距离表示为 : 式中, xik、xjk分别表示Xi和Xj的第k个分量。 当m=2时,明氏距离为欧氏距离。 当m=1时: 称为“街坊”距离 (“City block”distance)。 欧氏 街坊 当k=2时:图示
4.汉明(Hamming)距离 设Xi、Xj 为n维二值(1或-1)模式样本向量,则 汉明距离: 式中, xik、xjk分别表示Xi和Xj的第k个分量。 两个模式向量的各分量取值均不同:Dh(Xi, Xj)=n; 全相同: Dh(Xi, Xj)=0 5.角度相似性函数 是模式向量Xi,Xj之间夹角的余弦。
6.Tanimoto测度 用于0,1二值特征的情况, 相似性测度函数的共同点都涉及到把两个相比较的向量Xi,Xj的分量值组合起来,但怎样组合并无普遍有效的方法,对具体的模式分类,需视情况作适当选择。
2.2.2 聚类准则 聚类准则:根据相似性测度确定的,衡量模式之间是否相似的标 准。即把不同模式聚为一类还是归为不同类的准则。 确定聚类准则的两种方式: 1. 阈值准则:根据规定的距离阈值进行分类的准则。 2. 函数准则:利用聚类准则函数进行分类的准则。 聚类准则函数:在聚类分析中,表示模式类间相似或差异性 的函数。 它应是模式样本集{X }和模式类别 的函数。可使聚类分析转化为寻找准则函数极值的最优化问题。一种常用的指标是误差平方之和。
聚类准则函数: 式中:c为聚类类别的数目, 为属于 集的样本的均值向量, 为 中样本数目。 J代表了分属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。 适用范围: 适用于各类样本密集且数目相差不多,而不同类间的样本又明显分开的情况。
例1: 类长轴两端距离中心很远,J值较大,结果不易令人满意。 类内误差平方和很 小,类间距离很远。 可得到最好的结果。
例2:另一种情况 有时可能把样本数目多的一类分拆为二,造成错误聚类。 原因:这样分开,J值会更小。 正确分类 错误分类
2.3 基于距离阈值的聚类算法 2.3.1 近邻聚类法 1. 问题:有N个待分类的模式 ,要求按距离阈值T分类到以 为聚类中心的模式类中。 2.3 基于距离阈值的聚类算法 2.3.1 近邻聚类法 1. 问题:有N个待分类的模式 ,要求按距离阈值T分类到以 为聚类中心的模式类中。 (T_threshold ) 2. 算法描述 ① 任取样本Xi 作为第一个聚类中心的初始值,如令Z1 = X1 。 ② 计算样本X2 到Z1 的欧氏距离 , 若 ,定义一新的聚类中心Z2 = X2 ; 否则 X2 ∈以Z1为中心的聚类。
……依此类推,直到将所有的N个样本都进行分类。 ③ 假设已有聚类中心Z1、Z2,计算 和 , 若 且 ,则建立第三个聚类中心Z3 = X3; 否则X3∈离Z1和Z2中最近者(最近邻的聚类中心)。 3. 算法特点 1)局限性:很大程度上依赖于第一个聚类中心的位置选择、待 分类模式样本的排列次序、距离阈值T的大小以及样本分布 的几何性质等。 2)优点:计算简单。(一种虽粗糙但快速的方法)
4.算法讨论 用先验知识指导阈值T 和起始点Z1的选择,可获得合理的聚类结果。否则只能选择不同的初值重复试探,并对聚类结果进行验算,根据一定的评价标准,得出合理的聚类结果。 对结果验算,类内各样本点间距离方差之和太大 减小T,修改中心Z。
2.3.2 最大最小距离算法(小中取大距离算法 ) 1. 问题:已知N个待分类的模式 , 分类到聚类中心 对应的类别中 。 2. 算法描述 ① 选任意一模式样本做为第一聚类中心Z1。 ② 选择离Z1距离最远的样本作为第二聚类中心Z2。 ③ 逐个计算各模式样本与已确定的所有聚类中心之间的距离,并选出其中的最小距离。例当聚类中心数k=2时,计算 min( Di1 , Di2 ),i=1,…,N (N个最小距离)
④ 在所有最小距离中选出最大距离,如该最大值达到 的一定分数比值( 阈值T ) 以上,则相应的样本点取为新的聚类中心,返回③;否则,寻找聚类中心的工作结束。 例k =2时 (θ:用试探法取为一固定分数,如1/2。) 则Z3存在。 ⑤ 重复步骤③④,直到没有新的聚类中心出现为止。 ⑥ 将样本 按最近距离划分到相应聚类中心对应 的类别中。 思路总结: 先找中心后分类;关键:怎样开新类,聚类中心如何定。 为使聚类中心更有代表性,可取各类的样本均值作为聚类中心。
例2.1 对图示模式样本用最大最小距离算法进行聚类分析。 例2.1 对图示模式样本用最大最小距离算法进行聚类分析。 10个最小距离中,X7对应的距离>T, ③ ②距Z1最远,选为Z2。计算T。 ③对应最小距离中的最大值, 且>T,选作Z3。 ④ 用全体模式对三个聚类中心计算最小距离中的最大值,无>T 情况,停止寻找中心。 结果:Z1=X1;Z2=X6; Z3=X7 。 ①选Z1=X1 ⑤ 聚类
2.4 系统聚类法 思路:每个样本先自成一类,然后按距离准则逐步合并,减少类数。 2.4 系统聚类法 思路:每个样本先自成一类,然后按距离准则逐步合并,减少类数。 系统聚类:先把每个样本作为一类,然后根据它们间的相似性和相邻性聚合。 相似性、相邻性一般用距离表示 1. 算法描述 1)N个初始模式样本自成一类,即建立N 类: 计算各类之间(即各样本间)的距离,得一N×N维距离矩阵D(0)。“0”表示初始状态。 (G_Group)
2)假设已求得距离矩阵D(n)(n为逐次聚类合并的次数),找出D(n)中的最小元素,将其对应的两类合并为一类。由此建立新的分类: 4)跳至第2步,重复计算及合并。 。 结束条件: 1)取距离阈值T,当D(n)的最小分量超过给定值 T 时,算法停 止。所得即为聚类结果。 2)或不设阈值T,一直将全部样本聚成一类为止,输出聚类的分 级树。
1)最短距离法 两类中相距最近的两样品间的距离。 2. 问题讨论:类间距离计算准则 1)最短距离法 两类中相距最近的两样品间的距离。 如H、K是两个聚类,则两类间的最短距离定义为: :H类中的某个样本XH和K类中的某个样本XK之间 的欧氏距离。 DHK:H类中所有样本与K类中所有样本之间的最小距离。 H K
2)最长距离法两类中相距最远的两个样本间的距离。 如果K类由I和J两类合并而成,则 √ H K I J 得到递推公式: 2)最长距离法两类中相距最远的两个样本间的距离。 若K类由I、J两类合并而成,则 有:
2、最长距离 :两类中相距最远的两个样本间的距离。 3、中间距离:最短距离和最长距离都有片面性,因此有时用中间距离。设ω1类和ω23类间的最短距离为d12,最长距离为d13,ω 23类的长度为d23,则中间距离为: 上式推广为一般情况:
4、重心距离:均值间的距离 5、类平均距离:两类中各个元素两两之间的距离平方相加后取平均值
6、 离差平方和: 设N个样品原分q类,则定义第i类的离差平方和为: 离差平方和增量:设样本已分成ωp,ωq两类,若把ωp,ωq合为ωr类,则定义离差平方:
(2)系统聚类的算法(略) 例:如下图所示 1、设全部样本分为6类, 2、作距离矩阵D(0)
ω1 ω2 ω3 ω4 ω5 9 1 16 49 64 25 4 36 ω6 81
3、求最小元素: 4、把ω1,ω3合并ω7=(1,3) ω4,ω6合并ω8=(4,6) 5、作距离矩阵D(1) ω7 ω2 ω8 9 49 16 ω5 25 4
6、若合并的类数没有达到要求,转3。否则停止。 7、求最小元素: 8、ω8,ω5,ω2合并, ω9=(2,5,4,6)
例:给出6个五维模式样本如下,按最短距离准则进行系统聚类分类。 解:(1)将每一样本看作单独一类,得: 计算各类间欧氏距离: , , , ; ; …
得距离矩阵D(0): (2)将最小距离 对应的类 和 合并为1类,得 新的分类。 计算聚类后的距离矩阵D(1): (2)将最小距离 对应的类 和 合并为1类,得 新的分类。 D(0) * 计算聚类后的距离矩阵D(1): 由D(0) 递推出D(1) 。
D(0) D(1) * * (3)将D(1)中最小值 对应的类合为一类, 得D(2)。 D(2)
(4)将D(2)中最小值 对应的类合为一类,得D(3)。 * D(3) 若给定的阈值为 ,D(3)中的最小元素 ,聚类结束。 若无阈值,继续分下去,最终全部样本归为一类。可给出聚类过程的树状表示图。
类间距离 阈值增大, 分类变粗。 层次聚类法的树状表示
2.5 分解聚类 N:总样本数, :ω1类样本数 :ω2类样本数, 分解聚类:把全部样本作为一类,然后根据相似性、相邻性分解。 2.5 分解聚类 分解聚类:把全部样本作为一类,然后根据相似性、相邻性分解。 目标函数 两类均值方差 N:总样本数, :ω1类样本数 :ω2类样本数,
分解聚类框图: 初始分类 调整分类方案 最终结果 目标函数 达到最优先?
例:已知21个样本,每个样本取二个特征,原始资料矩阵如下表: 对分算法:略 例:已知21个样本,每个样本取二个特征,原始资料矩阵如下表: 样本号 1 2 3 4 5 6 7 8 9 10 x1 x2 11 12 13 14 15 16 17 18 19 20 21 -4 -2 -3 -5 1 -1 3 2
解:第一次分类时计算所有样本,分别划到 时的E值,找出最大的。 1、开始时, ∴目标函数 ∴
2、分别计算当 划入 时的E值 把 划入 时有
E(1)=56.6 再继续进行第二,第三次迭代… 计算出 E(2) , E(3) , … 然后再把 划入 时对应的E值,找出一个最大的E值。 ∴ E(1)=56.6 再继续进行第二,第三次迭代… 计算出 E(2) , E(3) , …
次数 E值 1 56.6 2 79.16 3 90.90 4 102.61 5 120.11 6 137.15 7 154.10 8 176.15 9 195.26 10 213.07 11 212.01
每次分类后要重新计算 的值。可用以下递推公式: 第10次迭代 划入 时,E最大。于是分成以下两类: ∴ 每次分类后要重新计算 的值。可用以下递推公式:
作业: 样本 1 2 3 4 5 6 7 8 0 2 1 5 6 5 6 7 0 2 1 3 3 4 4 5 用对分法编程上机,分成两类画出图形。
2.6 动态聚类——兼顾系统聚类和分解聚类 一、动态聚类的方法概要 ① 先选定某种距离作为样本间的相似性的度量; 2.6 动态聚类——兼顾系统聚类和分解聚类 一、动态聚类的方法概要 ① 先选定某种距离作为样本间的相似性的度量; ② 确定评价聚类结果的准则函数; ③ 给出某种初始分类,用迭代法找出使准则函数取极值的最好的聚类结果。
* 迭代自组织的数据分析算法(ISODATA, iterative self-organizing 判断 合理性 选初始 中心 聚类 合理 不合理 输出 修改 两种常用算法: * K-均值算法(或C-均值算法) * 迭代自组织的数据分析算法(ISODATA, iterative self-organizing data analysis techniques algorithm)
2.5.1 K-均值算法 基于使聚类准则函数最小化, 准则函数:聚类集中每一样本点到该类中心的距离平方和。 对于第j个聚类集,准则函数定义为 Sj:第j个聚类集(域),聚类中心为Zj ; Nj:第j个聚类集Sj中所包含的样本个数。 对所有K个模式类有 K-均值算法的聚类准则:聚类中心的选择应使准则函数J极小, 即使Jj的值极小。
应有 即 可解得 上式表明,Sj类的聚类中心应选为该类样本的均值。 1. 算法描述 (1)任选K个初始聚类中心:Z1(1), Z2(1),…, ZK(1) 括号内序号:迭代运算的次序号。
(2)按最小距离原则将其余样品分配到K个聚类中心中的某一 个,即: 若 ,则 注意:k——迭代运算次序号;K——聚类中心的个数 。 (3)计算各个聚类中心的新向量值: Nj:第j类的样本数。 这里:分别计算K个聚类中的样本均值向量,故称K-均值算法。 (4)如果 ,则回到(2),将模式 样本逐个重新分类,重复迭代计算。 如果 ,算法收敛,计算完毕。
“动态”聚类法 ? 聚类过程中, 聚类中心位置或个数发生变化。 2. 算法讨论 结果受到所选聚类中心的个数和其初始位置,以及模式样 2. 算法讨论 结果受到所选聚类中心的个数和其初始位置,以及模式样 本的几何性质及读入次序等的影响。实际应用中需要试探不同 的K值和选择不同的聚类中心起始值。
二、代表点的选取方法:代表点就是初始分类的聚类中心数k ① 凭经验选代表点,根据问题的性质、数据分布,从直观上看来较合理的代表点k;
③ 按密度大小选代表点: ④ 用前k个样本点作为代表点。 ③ 按密度大小选代表点: 以每个样本作为球心,以d为半径做球形;落在球内的样本数称为该点的密度,并按密度大小排序。首先选密度最大的作为第一个代表点,即第一个聚类中心。再考虑第二大密度点,若第二大密度点距第一代表点的距离大于d1(人为规定的正数)则把第二大密度点作为第二代表点,,否则不能作为代表点,这样按密度大小考察下去,所选代表点间的距离都大于d1。d1太小,代表点太多,d1太大,代表点太小,一般选d1=2d。对代表点内的密度一般要求大于T。T>0为规定的一个正数。 ④ 用前k个样本点作为代表点。
三、初始分类和调整 ① 选一批代表点后,代表点就是聚类中心,计算其它样本到聚类中心的距离,把所有样本归于最近的聚类中心点,形成初始分类,再重新计算各聚类中心,称为成批处理法。 ② 选一批代表点后,依次计算其它样本的归类,当计算完第一个样本时,把它归于最近的一类,形成新的分类。再计算新的聚类中心,再计算第二个样本到新的聚类中心的距离,对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。 ③ 直接用样本进行初始分类,先规定距离d,把第一个样品作为第一类的聚类中心,考察第二个样本,若第二个样本距第一个聚类中心距离小于d,就把第二个样本归于第一类,否则第二个样本就成为第二类的聚类中心,再考虑其它样本,根据样本到聚类中心距离大于还是小于d,决定分裂还是合并。
最佳初始分类。 如图所示,随着初始分类k的增大,准则函数下降很快,经过拐点A后,下降速度减慢。拐点A就是最佳初始分类。
第一步:令K=2,选初始聚类中心为 四、K次平均算法:成批处理法( 算法略) 例:已知有20个样本,每个样本有2个特征,数据分布如下图 样本序号 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 特征x1 1 2 3 6 7 特征x2 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 8 6 7 9 第一步:令K=2,选初始聚类中心为
转第二步。 第四步: ∵ 第二步:重新计算 到z1(2) , z2(2) 的距离,把它们归为最近聚类中心,重新分为两类, 第三步:根据新分成的两类建立新的聚类中心 第四步: ∵ 转第二步。 第二步:重新计算 到z1(2) , z2(2) 的距离,把它们归为最近聚类中心,重新分为两类,
第三步,更新聚类中心
第四步, 第二步, 第三步,更新聚类中心
上机作业 已知十个样本,每个样本2个特征,数据如下: 用K次平均算法和ISODATA算法分成3类,编程上机,并画出分类图。 样本序号 1 2 3 4 5 6 7 8 9 10 x1 0 1 2 4 5 5 6 1 1 1 x2 0 1 1 3 3 4 5 4 5 6
例2.3:已知20个模式样本如下,试用K-均值算法分类。 ② 计算距离,聚类: : :
: : ……,可得到: ③ 计算新的聚类中: ④ 判断: ,故返回第②步。
② 从新的聚类中心得: : ┋ : 有: ③ 计算聚类中心:
④ 返回第②步,以Z1(3), Z2(3)为中心进行聚类。 ② 以新的聚类中心分类,求得的分类结果与前一次迭代结果相 同: ③ 计算新聚类中心向量值,聚类中心与前一次结果相同,即: ④ ,故算法收敛,得聚类中心为 结果图示:
X1 X4 X3 X5 X8 X9 X7 X10 X2 X6 x1 x2 1 3 5 7 9 X11 X12 X13 X14 X15 X16 X17 X18 X19 X20 图2.10 K-均值算法聚类结果
上述K-均值算法,其类型数目假定已知为K个。当K未知时, 可以令K逐渐增加, 此时J j 会单调减少。最初减小速度快,但当 3、聚类准则函数Jj与K的关系曲线 上述K-均值算法,其类型数目假定已知为K个。当K未知时, 可以令K逐渐增加, 此时J j 会单调减少。最初减小速度快,但当 K 增加到一定数值时,减小速度会减慢,直到K =总样本数N 时,Jj = 0。Jj-K关系曲线如下图: Jj A 1 3 5 7 2 4 6 8 10 9 K 曲线的拐点 A 对应着接近最优 的K值(J 值减小量、计算量以及 分类效果的权衡)。 并非所有的情况都容易找到关 系曲线的拐点。迭代自组织的数据 分析算法可以确定模式类的个数K 。
2.5.2 迭代自组织的数据分析算法 (iterative self-organizing data analysis techniques algorithm,ISODATA) 算法特点 加入了试探性步骤,组成人机交互的结构; 可以通过类的自动合并与分裂得到较合理的类别数。 与K-均值算法比较: 相似:聚类中心的位置均通过样本均值的迭代运算决定。 相异: K-均值算法的聚类中心个数不变; ISODATA的聚类中心个数变化。 1.算法简介
基本思路: (1)选择初始值——包括若干聚类中心及一些指标。可在迭代运 算过程中人为修改,据此将N个模式样本分配到各个聚类中 心去。 (2)按最近邻规则进行分类。 (3)聚类后的处理:计算各类中的距离函数等指标,按照给定的 要求,将前次获得的聚类集进行分裂或合并处理,以获得新 的聚类中心,即调整聚类中心的个数。 (4)判断结果是否符合要求: 符合,结束; 否则,回到(2)。
算法共分十四步: 第一 ~ 六步:预选参数,进行初始分类。 为合并和分裂准备必要的数据。 第七步:决定下一步是进行合并还是进行分裂。 第八 ~ 十步:分裂算法。 第十一 ~ 十三步:合并算法。 第十四步:决定算法是否结束。 2.算法描述 设有N个模式样本X1,X2,…,XN 。 预选参数,进行初始分类。 第一步:预选NC个聚类中心 , NC也是聚类过程 中实际的聚类中心个数。预选指标:
K:希望的聚类中心的数目。 θN:每个聚类中应具有的最少样本数。若样本少于θN ,则该 类不能作为一个独立的聚类,应删去。 θS :一个聚类域中样本距离分布的标准差阈值。标准差向量的 每一分量反映样本在特征空间的相应维上,与聚类中心的 位置偏差(分散程度)。要求每一聚类内,其所有分量中 的最大分量应小于θS,否则该类将被分裂为两类。 θC :两聚类中心之间的最小距离。若两类中心之间距离小于 θC,则合并为一类。 L:在一次迭代中允许合并的聚类中心的最大对数。 I:允许迭代的次数。
第二步:把N个样本按最近邻规则分配到NC个聚类中。 若 则 第三步:若Sj中的样本数Nj<θN ,则取消该类,并且NC减去1。 第四步:修正各聚类中心值。 θN:每类应具有的 最少样本数。 第五步:计算Sj类的类内平均距离 。 第六步:计算总体平均距离 ,即全部样本到各自聚类中心距 离的平均距离。
第七步:判决是进行分裂还是进行合并,决定迭代步骤等。 判断分裂还是合并。 第七步:判决是进行分裂还是进行合并,决定迭代步骤等。 1) 如迭代已达I次(最后一次),置θC=0 ,跳到第十一步(合并)。 2) 若NC≤K/2,即聚类中心小于或等于希望数的一半,进入 第八步(分裂) 。 3) 如果迭代的次数是偶数,或NC≥2K,即聚类中心数目大于或 等于希望数的两倍,则跳到第十一步(合并)。否则进入第八步 (分裂)。 I:允许迭代的次数。 θC :两聚类中心之间的最小距离。 NC:预选的聚类中心数。 K:希望的聚类中心的数目。
分裂处理。 第八步:计算每个聚类中样本距离的标准差向量。对第Sj类有 分量: 是聚类数; 是维数(特征个数 )。 第九步:求每个标准差向量的最大分量。σj的最大分量记为 σjmax, j=1,2, …,NC。
说明Sj类样本在对应方向上的标准差大于允许的值。此 时,又满足以下两个条件之一: 第十步:在最大分量集 中,如有 , 说明Sj类样本在对应方向上的标准差大于允许的值。此 时,又满足以下两个条件之一: 1) 和 ,即类内平均距离大于总体平均距离, 并且Sj类中样本数很大。 2) ,即聚类数小于或等于希望数目的一半。 则将Zj分裂成两个新的聚类中心 和 ,并且NC加1。其中 :分裂系数 按邻近规则聚类 若完成了分裂运算,迭代次数加1,跳回第二步;否则,继续。 θS :聚类域中样本距离分布的标准差阈值。 θN:每个聚类中应具有的最少样本数。
第十一步:计算所有聚类中心之间的距离。Si类和Sj类中心间 的距离为 合并处理。 第十一步:计算所有聚类中心之间的距离。Si类和Sj类中心间 的距离为 第十二步:比较所有Dij与θC的值,将小于θC的Dij按升序排列 第十三步:如果将距离为 的两类合并,得到新的聚类中心 为 每合并一对,NC减1。 θC :两聚类中心之间的最小距离。