《聚类方法(第十一章)00》由会员分享，可在线阅读，更多相关《聚类方法(第十一章)00（38页珍藏版）》请在金锄头文库上搜索。
1、聚类方法第十一章划分聚类一、按最邻近规则的简单试探法 给N个待分类的模式样本 ，要求 按距离阈值T分类到聚类中心v算法过程： vStep 1：取任意的样本xi作为一聚类中的初始 值，如令z1=x1，计算若D21T，确定一新的聚类中心z2=x2 否则x2以z1为中心的聚类；vStep 2：假如已有聚类中心z1和z2，计算若D31T和D32T ，则确定一新的聚类中心 z3=x3；vStep i： v讨论 v这种方法的优点：计算简单，若模式样本的集 合分布的先验知识已知，则可获得较好的聚类 结果。 v在实际中，对于高维模式样本很难获得准确的 先验知识，因此只能选用不同的阈值和起始点 来试探，并对结果
2、进行验证。 v这种方法在很大程度上依赖于以下因素： v第一个聚类中心的位置（初始化问题） v待分类模式样本排列次序（聚类样本的选择问题） v距离阈值T的大小（判决准则问题） v样本分布的几何性质（样本的固有特性问题）层次聚类v系统聚类：先把每个样本作为一类，然后根据它们 间的相似性或相邻性聚合，类别由多到少，直到获 得合适的分类要求为止；相似性、相邻性用距离表 示。聚合的关键就是每次迭代中形成的聚类之间以 及它们和样本之间距离的计算，不同的距离函数会 得到不同结果。 v两类间距离计算准则： v1. 最短距离：两类中相距最近的两样本间的距离v 2. 最长距离 ：两类中相距最远的两个样本间的 距离
3、。v3. 类平均距离：两类中各个元素两两之间的距离 平方相加后取平均值 v4. 类中心距离v算法过程描述： Step1：初始距离矩阵的计算D(0)说明：（1）距离矩阵元素的值是类与类之间的距离，距离的 定义有多种。 （2）距离矩阵，是对称矩阵。对角线上的元值表示同类之间 的距离，即为0。Step2：对于第n次迭代的距离矩阵D(n)进行聚合说明：距离矩阵中选择距离最小的，如果有相同的可以任选其 中一个，要忽略对角线上的元素。vStep3：根据第n次聚合结果，计算合并后的 新类别之间的距离矩阵D(n+1) 说明：合并类的距离计算应该符合距离的运算 规则。如，距离反映的是两类的重心距离，那 么合并后
4、，应该仍然反映的重心的距离。vStep4：收敛性判决说明：算法的收敛条件判断准则的确定。例1：如下图所示（简单的一维情况） 1、设全部样本分为6类， 2、计算距离矩阵D(0)1234561029031160449166405254364066425811903、求最小元素： 4、把1, 3合并7=(1,3) 4, 6合并8=(4,6) 5、作距离矩阵D(1)，按最小距离准则7285702908491605254406、若合并的类数没有达到要求，转3。否则停止 。3、求最小元素：4、8, 5, 2合并, 9=（2,5,4,6）分解聚类v分解聚类：把全部样本作为一类，然后 根据相似性、相邻性分解。
5、 v目标函数：两类中心的距离N：总样本数， ：1类样本数：2类样本数，分解聚类框图初始分类调整分类方案最终结果目标函数 达到最优先？例2：已知21个样本，每个样本取二个特征， 如下表：样本号 12345678910 x10022445667 x2655343121011 12 13 14 15 16 17 18 19 20 21-4-2-3-3-5100-1-1-3322021-1-2 -1-3-5目标函数解：第一次分类时计算所有样本，分别划到 时的E值，找出最大E值对应的样本。 1、开始时，2、分别计算当 划入时的E值把 划入 时有然后再计算把 划入 时对应的E 值，找出一个最大的E值。一直
6、计算下去 把 划为 的E值最大。 E(1)=56.6再继续进行第二，第三次迭代 计算出 E(2) , E(3) , 次数 E值1 56.62 79.163 90.904 102.615 120.116 137.157 154.108 176.159 195.2610 213.0711 212.01第10次迭代 划入 时，E最大。于是分成以 下两类： 每次分类后要重新计算 的值。可用以下递推公 式：动态聚类-K-means一、动态聚类的方法概要 先选定某种距离作为样本间的相似性 的度量; 确定评价聚类结果的准则函数; 给出某种初始分类，用迭代法找出使 准则函数取极值的最好的聚类结果。选代表点初始
7、分类分类合理否最终分类修改分类YN动态聚类框图二、代表点（种子点）的选取方法： 代表点就是初始分类的k个聚类中心 凭经验选代表点，根据问题的性质、数据 分布，从直观上看来较合理的k个代表点; 将全部样本随机分成k类，计算每类重心 ，把这些重心作为每类的代表点; 用前k个样本点作为代表点。 按密度大小选代表点：以每个样本作为球心，以d为半径做球形；落 在球内的样本数称为该点的密度，并按密度大小 排序。首先选密度最大的作为第一个代表点，即 第一个聚类中心。再考虑第二大密度点，若第二 大密度点距第一代表点的距离大于d1（人为规定 的正数）则把第二大密度点作为第二代表点， 否则不能作为代表点，这样按密
8、度大小考察下去 ，所选代表点间的距离都大于d1。d1太小，代表 点太多，d1太大，代表点太小，一般选d12d。 对代表点内的密度一般要求大于T。T0为规定的 一个正数。三、初始分类和调整 选一批代表点后，代表点就是聚类中心，计算 其它样本到聚类中心的距离，把所有样本归于最近 的聚类中心点，形成初始分类，再重新计算各聚类 中心，称为成批处理法。 选一批代表点后,依次计算其它样本的归类，当 计算完第一个样本时，把它归于最近的一类，形成 新的分类。再计算新的聚类中心，再计算第二个样 本到新的聚类中心的距离，对第二个样本归类。即 每个样本的归类都改变一次聚类中心。此法称为逐 个处理法。 直接用样本进行
9、初始分类，先规定距离d,把第 一个样品作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于d，就把 第二个样本归于第一类，否则第二个样本就成为第 二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于d，决定分裂还是合并。 最佳初始分类：如图所示，随着初始分类k的增 大，准则函数下降很快，经过拐点A后，下降速 度减慢。拐点A就是最佳初始分类。四、K-均值算法：成批处理法例：已知有20个样本，每个样本有2个特征，数据分布如下图第一步：令K=2，选初始聚类中心为样本序号x1x2x3x4x5x6x7x8x9x10 特征x10101212367特征x200111222
10、66x11x12x13x14x15x16x17x18x19x20 86789789896777788899第三步：根据新分成的两类建立新的聚类中心第四步： 转第二步。 第二步：重新计算 到z1(2) , z2(2) 的距离 ，把它们归为最近聚类中心，重新分为两类，第三步，更新聚类中心第四步， 第二步，第三步，更新聚类中心v说明：(1)K是指需要分成K类，均值是指每类的中心, 就是该类所有样本的平均值，不一定就有某个 样本在这个位置上。(2)算法的收敛性判别：前后两次迭代的结果 ，也就是每迭代分类后，分类都是一样的，此 时停止。(3)K值和初始聚类中心对分类的结果影响很大 。通常需要其它的算法来
11、确定这两个的选取。v讨论 v K-均值算法的结果受如下选择的影响： v所选聚类的数目 v聚类中心的初始分布 v模式样本的几何性质 v读入次序 v在实际应用中，需要试探不同的K值和选择 不同的聚类中心的起始值。 v如果模式样本可以形成若干个相距较远的孤 立的区域分布，一般都能得到较好的收敛效 果。 vK-均值算法比较适合于分类数目已知的情况 。作业 1. 给定5个6维模式样本（如下），试按最小(欧氏)距 离准则进行系统聚类分析。2.已知十个样本，每个样本2个特征，数据如下：用K-均值算法分成3类。样本序号1 2 3 4 5 6 7 8 9 10 x10 1 2 4 5 5 6 1 1 1 x20 1 1 3 3 4 5 4 5 6
