聚类方法(十).PPTVIP

第三步：根据新分成的两类建立新的聚类中心 第四步： ∵ 转第二步。 第二步：重新计算 到z1(2) , z2(2) 的距离，把它们归为最近聚类中心，重新分为两类， 第三步，更新聚类中心 第四步， 第二步， 第三步，更新聚类中心 说明： (1)K是指需要分成K类，均值是指每类的中心,就是该类所有样本的平均值，不一定就有某个样本在这个位置上。 (2)算法的收敛性判别：前后两次迭代的结果，也就是每迭代分类后，分类都是一样的，此时停止。 (3)K值和初始聚类中心对分类的结果影响很大。通常需要其它的算法来确定这两个的选取。 讨论 K-均值算法的结果受如下选择的影响： 所选聚类的数目 聚类中心的初始分布 模式样本的几何性质 读入次序 在实际应用中，需要试探不同的K值和选择不同的聚类中心的起始值。 如果模式样本可以形成若干个相距较远的孤立的区域分布，一般都能得到较好的收敛效果。 K-均值算法比较适合于分类数目已知的情况。 作业 1. 给定5个6维模式样本（如下），试按最小(欧氏)距离准则进行系统聚类分析。 2.已知十个样本，每个样本2个特征，数据如下： 用K-均值算法分成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 聚类方法 第十一章 划分聚类 一、按最邻近规则的简单试探法 给N个待分类的模式样本 ，要求按距离阈值T分类到聚类中心 算法过程： Step 1：取任意的样本xi作为一聚类中的初始值，如令z1=x1，计算 若D21＞T，确定一新的聚类中心z2=x2 否则x2∈以z1为中心的聚类； Step 2：假如已有聚类中心z1和z2，计算 若D31＞T和D32＞T ，则确定一新的聚类中心z3=x3； Step i： ……… 讨论 这种方法的优点：计算简单，若模式样本的集合分布的先验知识已知，则可获得较好的聚类结果。 在实际中，对于高维模式样本很难获得准确的先验知识，因此只能选用不同的阈值和起始点来试探，并对结果进行验证。 这种方法在很大程度上依赖于以下因素： 第一个聚类中心的位置（初始化问题） 待分类模式样本排列次序（聚类样本的选择问题） 距离阈值T的大小（判决准则问题） 样本分布的几何性质（样本的固有特性问题） 层次聚类 系统聚类：先把每个样本作为一类，然后根据它们间的相似性或相邻性聚合，类别由多到少，直到获得合适的分类要求为止；相似性、相邻性用距离表示。聚合的关键就是每次迭代中形成的聚类之间以及它们和样本之间距离的计算，不同的距离函数会得到不同结果。 两类间距离计算准则： 1. 最短距离：两类中相距最近的两样本间的距离 2. 最长距离 ：两类中相距最远的两个样本间的距离。 3. 类平均距离：两类中各个元素两两之间的距离平方相加后取平均值 4. 类中心距离 算法过程描述：Step1：初始距离矩阵的计算D(0) 说明：（1）距离矩阵元素的值是类与类之间的距离，距离的定义有多种。 （2）距离矩阵，是对称矩阵。对角线上的元值表示同类之间的距离，即为0。 Step2：对于第n次迭代的距离矩阵D(n)进行聚合 说明：距离矩阵中选择距离最小的，如果有相同的可以任选其中一个，要忽略对角线上的元素。 Step3：根据第n次聚合结果，计算合并后的新类别之间的距离矩阵D(n+1) 说明：合并类的距离计算应该符合距离的运算规则。如，距离反映的是两类的重心距离，那么合并后，应该仍然反映的重心的距离。 Step4：收敛性判决 说明：算法的收敛条件判断准则的确定。 例1：如下图所示（简单的一维情况） 1、设全部样本分为6类， 2、计算距离矩阵D(0) Ω1 Ω2 Ω3 Ω4 Ω5 Ω6 Ω1 0 Ω2 9 0 Ω3 1 16 0 Ω4 49 16 64 0 Ω5 25 4 36 4 0 Ω6 64 25 81 1 9 0 3、求最小元素： 4、把Ω1, Ω3合并Ω7=(1,3) Ω4, Ω6合并Ω8=(4,6) 5、作距离矩阵D(1)，按最小距离准则 Ω7 Ω2 Ω8 Ω5 Ω7 0 Ω2 9 0 Ω8 49 16 0 Ω5 25 4 4 0 6、若合并的类数没有达到要求，转3。否则停止。 3、求最小元素： 4、Ω8, Ω5, Ω2合并, Ω9=（2,5,4,6） 分解聚类 分解聚类：把全部