《数据挖掘数据聚类课件》由会员分享，可在线阅读，更多相关《数据挖掘数据聚类课件（82页珍藏版）》请在金锄头文库上搜索。
1、第第8章章 数据聚类数据聚类13.1 引言引言3.2 相似性度量相似性度量3.3 聚类准则聚类准则3.4 基于试探的两种聚类算法基于试探的两种聚类算法3.5 系统聚类法系统聚类法3.6 动态聚类动态聚类3.7 聚类评价聚类评价主要内容主要内容23.1 引言引言聚类：将数据分组成为多个类别，在同一个类内对聚类：将数据分组成为多个类别，在同一个类内对象之间具有较高的相似度，不同类之间的对象差别象之间具有较高的相似度，不同类之间的对象差别较大。较大。根据各个待分类的模式特征相似程度进行分类，根据各个待分类的模式特征相似程度进行分类，相相似似的归为一类，不相似的作为另一类。的归为一类，不相似的作为另一
2、类。u监督学习：监督学习：需要用训练样本进行学习和训练需要用训练样本进行学习和训练u非监督学习：对于没有类别标签的样本集，根非监督学习：对于没有类别标签的样本集，根据该问题本身的目的和样本的特性，把全体据该问题本身的目的和样本的特性，把全体N个样本划分为若干个子集，同类样本特性相差个样本划分为若干个子集，同类样本特性相差小，异类样本特性相差大。小，异类样本特性相差大。3聚类应用聚类应用花瓣的花瓣的“物以类聚物以类聚”4聚类应用聚类应用u早在孩提时代，人就通过不断改进下意识中的聚类早在孩提时代，人就通过不断改进下意识中的聚类模式来学会如何区分猫和狗，动物和植物模式来学会如何区分猫和狗，动物和植物
3、u谁经常光顾商店，谁买什么东西，买多少？谁经常光顾商店，谁买什么东西，买多少？u按照卡记录的光临次数、光临时间、性别、年龄、按照卡记录的光临次数、光临时间、性别、年龄、职业、购物种类、金额等变量分类职业、购物种类、金额等变量分类u这样商店可以这样商店可以.u识别顾客购买模式（如喜欢一大早来买酸奶和鲜肉，识别顾客购买模式（如喜欢一大早来买酸奶和鲜肉，习惯周末时一次性大采购）习惯周末时一次性大采购）u刻画不同的客户群的特征刻画不同的客户群的特征5聚类应用聚类应用u挖掘有价值的客户，并制定相应的促销策略：挖掘有价值的客户，并制定相应的促销策略：u如，对经常购买酸奶的客户如，对经常购买酸奶的客户u对累
4、计消费达到对累计消费达到12个月的老客户个月的老客户u针对潜在客户派发广告，比在大街上乱发传单针对潜在客户派发广告，比在大街上乱发传单命中率更高，成本更低！命中率更高，成本更低！6聚类应用聚类应用谁是银行信用卡的黄金客户？谁是银行信用卡的黄金客户？u利用储蓄额、刷卡消费金额、诚信度等变量对客户分利用储蓄额、刷卡消费金额、诚信度等变量对客户分类，找出类，找出“黄金客户黄金客户”！u这样银行可以制定更吸引的服务，留住客户！比如：这样银行可以制定更吸引的服务，留住客户！比如：u一定额度和期限的免息透支服务！一定额度和期限的免息透支服务！u商场的贵宾打折卡！商场的贵宾打折卡！u在他或她生日的时候送上一
5、个小蛋糕！在他或她生日的时候送上一个小蛋糕！7聚类应用聚类应用u经济领域：经济领域：u帮助市场分析人员从客户数据库中发现不同的客户群，帮助市场分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。并且用购买模式来刻画不同的客户群的特征。u谁喜欢打国际长途，在什么时间，打到那里？谁喜欢打国际长途，在什么时间，打到那里？u对住宅区进行聚类，确定自动提款机对住宅区进行聚类，确定自动提款机ATM的安放位置的安放位置u股票市场板块分析股票市场板块分析u生物学领域生物学领域u推导植物和动物的分类；推导植物和动物的分类；u对基因分类，获得对种群的认识对基因分类，获得对种群的认识u数
6、据挖掘领域数据挖掘领域u作为其他数学算法的预处理步骤，获得数据分布状况，作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步的研究集中对特定的类做进一步的研究8聚类分析原理聚类分析原理聚类分析中聚类分析中“类类”的特征：的特征：u聚类所说的类不是事先给定的，而是根据数据的相聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分似性和距离来划分u聚类的数目和结构都没有事先假定聚类的数目和结构都没有事先假定9聚类分析原理聚类分析原理聚类方法的目的是寻找数据中：聚类方法的目的是寻找数据中：u潜在的潜在的自然分组结构自然分组结构u感兴趣的感兴趣的关系关系10聚类分析原理聚类分析
7、原理什么是什么是自然分组结构自然分组结构?有有16张牌，如何将他们分组呢？张牌，如何将他们分组呢？AKQJ11聚类分析原理聚类分析原理分成四组：每组里分成四组：每组里花色相花色相同同，组与组之间花色相异，组与组之间花色相异AKQJ花色相同的牌为一组花色相同的牌为一组12聚类分析原理聚类分析原理分成四组，分成四组，符号相同符号相同的牌的牌为一组为一组AKQJ符号相同的的牌为一组符号相同的的牌为一组13聚类分析原理聚类分析原理分成两组，分成两组，颜色相同颜色相同的牌的牌为一组为一组AKQJ颜色相同的牌为一组颜色相同的牌为一组14聚类分析原理聚类分析原理u分组的意义在于我们怎么定义并度量分组的意义在
8、于我们怎么定义并度量“相似性相似性”u因此衍生出一系列度量相似性的算法因此衍生出一系列度量相似性的算法15聚类分析原理聚类分析原理相似性的度量（统计学角度）相似性的度量（统计学角度）u距离距离Q型聚类（主要讨论）型聚类（主要讨论）u主要用于对样本分类主要用于对样本分类u常用的距离有：常用的距离有：u明考夫斯基距离明考夫斯基距离(包括：绝对距离、欧式距离、切比包括：绝对距离、欧式距离、切比雪夫距离雪夫距离)u兰氏距离兰氏距离u马氏距离马氏距离u斜交空间距离斜交空间距离u此不详述，可参考此不详述，可参考应用多元分析应用多元分析（第二版）王（第二版）王学民学民16聚类分析原理聚类分析原理u相似系数相
9、似系数R型聚类型聚类u用于对变量分类，可以用变量之间的相似系数用于对变量分类，可以用变量之间的相似系数的变形，如的变形，如1rij定义距离定义距离17聚类分析原理聚类分析原理变量按测量尺度分类变量按测量尺度分类u间隔尺度变量间隔尺度变量 连续变量，如长度、重量、速度、温度等连续变量，如长度、重量、速度、温度等u有序尺度变量有序尺度变量 等级变量，不可加，但可比，如一等、二等、三等级变量，不可加，但可比，如一等、二等、三等奖学金等奖学金u名义尺度变量名义尺度变量 类别变量，不可加也不可比，如性别、职业等类别变量，不可加也不可比，如性别、职业等183.2 相似性度量相似性度量聚类分析符合聚类分析符
10、合“物以类聚，人以群分物以类聚，人以群分“的原则，它的原则，它把相似性大的样本聚集为一个类型把相似性大的样本聚集为一个类型 聚类分析的关键问题：如何在聚类过程中自动地确聚类分析的关键问题：如何在聚类过程中自动地确定类型数目定类型数目 19相似性度量相似性度量20相似性度量相似性度量u距离相似性度量距离相似性度量 u角度相似性度量角度相似性度量 21距离相似性度量距离相似性度量 模式样本向量与之间的欧氏距离定义为：模式样本向量与之间的欧氏距离定义为： u若距离阈值若距离阈值ds选择过大，则全部样本被视作一选择过大，则全部样本被视作一个唯一类型；若个唯一类型；若ds选取过小，则可能造成每个选取过小
11、，则可能造成每个样本都单独构成一个类型样本都单独构成一个类型22距离相似性度量距离相似性度量距离阈值对聚类的影响距离阈值对聚类的影响23距离相似性度量距离相似性度量u特征选取不当使聚类无效特征选取不当使聚类无效u特征选取不足引起误分类特征选取不足引起误分类u模式特征坐标单位的选取也会强烈地影响聚类结模式特征坐标单位的选取也会强烈地影响聚类结果果24距离相似性度量距离相似性度量特征选取不当使聚类无效特征选取不当使聚类无效1225距离相似性度量距离相似性度量特征选取不足引起误分类特征选取不足引起误分类12326距离相似性度量距离相似性度量acbd27解决尺度问题解决尺度问题标准化标准化28解决尺度
12、问题解决尺度问题 为了进行聚类，我们需要一种合适的距离度量尺为了进行聚类，我们需要一种合适的距离度量尺度。度。u这种距离度量尺度依赖于特征标准化方法这种距离度量尺度依赖于特征标准化方法u为了选择标准化方法我们必须知道聚类的类型为了选择标准化方法我们必须知道聚类的类型u试错法是唯一的避免这种恶性循环的方法。选择试错法是唯一的避免这种恶性循环的方法。选择不同的条件进行试验，通过观察、数据解释和效不同的条件进行试验，通过观察、数据解释和效用分析评价相应的解。平衡各特征值的贡献，并用分析评价相应的解。平衡各特征值的贡献，并保持原有的语义信息。保持原有的语义信息。29角度相似性度量角度相似性度量 样本与
13、之间的角度相似性度量定义为它们之间夹角样本与之间的角度相似性度量定义为它们之间夹角的余弦的余弦 303.3 聚类准则聚类准则u相似性度量相似性度量 集合与集合的相似性集合与集合的相似性u相似性准则相似性准则 分类效果好坏的评价准则分类效果好坏的评价准则 聚类准则聚类准则:u试探法试探法 定义一种相似性度量的阈值定义一种相似性度量的阈值u聚类准则函数法聚类准则函数法 聚类准则是反映类别间相似性或分离性的函数聚类准则是反映类别间相似性或分离性的函数u误差平方和准则（最常用的）误差平方和准则（最常用的）u加权平均平方距离和准则加权平均平方距离和准则 31误差平方和准则误差平方和准则假定有混合样本假定
14、有混合样本X=x1, x2, , xn采用某种相似性度量，采用某种相似性度量，X被聚合成被聚合成c个分离开的子集个分离开的子集X1, X2, , Xc。每个子集是一个类型，它们分别包。每个子集是一个类型，它们分别包含含n1, n2, , nc个样本个样本为了衡量类的质量，采用误差平方和为了衡量类的质量，采用误差平方和Jc聚类准则函数，聚类准则函数，定义为：定义为：mj为类型为类型Xj中样本的均值，中样本的均值，mj是是c个集合的中心，可个集合的中心，可以用来代表以用来代表c个类型。个类型。32误差平方和准则误差平方和准则误差平方和准则适用于各类样本比较密集且样本数误差平方和准则适用于各类样本比
15、较密集且样本数目悬殊不大的样本分布目悬殊不大的样本分布 33误差平方和准则误差平方和准则例：例：34加权平均平方距离和准则加权平均平方距离和准则 定义加权平均平方距离和准则：定义加权平均平方距离和准则：式中：式中：Sj*是类内样本间平均平方距离是类内样本间平均平方距离 Xj中的样本个数中的样本个数nj，Xj中的样本两两组合共有中的样本两两组合共有nj(nj-1)/2种种 表示所有样本之间距离之和表示所有样本之间距离之和Pj为为j类的先验概率，可以用样本数目类的先验概率，可以用样本数目nj和样本总和样本总数目数目n来估计，来估计，Pj=nj/n, j=1,2,c35加权平均平方距离和准则加权平均
16、平方距离和准则例：例：363.4 基于试探的两种聚类算法基于试探的两种聚类算法u采用最近邻规则的聚类算法采用最近邻规则的聚类算法 u最大最小距离聚类算法最大最小距离聚类算法 37采用最近邻规则的聚类算法采用最近邻规则的聚类算法选取距离阈值选取距离阈值T，并且任取一个样本作为第一个聚，并且任取一个样本作为第一个聚合中心合中心Z1，如：，如：Z1=x1计算样本计算样本x2到到Z1的距离的距离D21 若若D21T，则，则x2Z1，否则令，否则令x2为第二个聚合中心，为第二个聚合中心，Z2=x2 设设Z2=x2，计算，计算x3到到Z1和和Z2的距离的距离D31和和D32，若，若D31T和和D32T，则
17、建立第三个聚合中心，则建立第三个聚合中心Z3。否则把。否则把x3归于归于最近邻的聚合中心。依此类推，直到把所有的最近邻的聚合中心。依此类推，直到把所有的n个个样本都进行分类。样本都进行分类。按照某种聚类准则考察聚类结果，若不满意，则重按照某种聚类准则考察聚类结果，若不满意，则重新选取距离阈值新选取距离阈值T、第一个聚合中心、第一个聚合中心Z1，返回，返回，直到满意，算法结束。直到满意，算法结束。38采用最近邻规则的聚类算法采用最近邻规则的聚类算法u最近邻规则的聚类算法：计算模式特征矢量到最近邻规则的聚类算法：计算模式特征矢量到聚类中心的距离，和门限聚类中心的距离，和门限T比较，决定归属哪类比较
18、，决定归属哪类或作为新的聚类中心。或作为新的聚类中心。u该算法的优点是简单，如果有样本分布的先验该算法的优点是简单，如果有样本分布的先验知识用于指导阈值和起始点的选取，则可较快知识用于指导阈值和起始点的选取，则可较快得到合理结果。得到合理结果。u算法的结果在很多程度上取决于第一个聚合中算法的结果在很多程度上取决于第一个聚合中心的选取和距离阈值的大小。心的选取和距离阈值的大小。39阈值对聚类的影响阈值对聚类的影响40起始点对聚类的影响起始点对聚类的影响Z=x1Z=x5Z=x741最大最小距离聚类算法最大最小距离聚类算法若若Dk1=maxDi1，则取，则取xk为第二个聚合中心为第二个聚合中心Z2，
19、计算所有样，计算所有样本到本到Z1和和Z2的距离的距离Di1和和Di2。若若Dl=maxmin(Di1, Di2)，i=1,2,n，并且，并且DlD12， D12为为Z1和和Z2间距离，则取间距离，则取xl为第三个聚合中心为第三个聚合中心Z3。注意：注意：Di1=|xi-Z1|，Di2 =|xi-Z2|。如果如果Z3存在，则计算存在，则计算Dj=maxmin(Di1, Di2, Di3), i=1, 2, , n，若，若DjD12，则建立第四个聚合中心。依此类推，直到，则建立第四个聚合中心。依此类推，直到最大最小距离不大于最大最小距离不大于D12时，结束寻找聚合中心的计算。时，结束寻找聚合中心
20、的计算。给定给定，01，并且任取一个样本作为第一个聚合中心，并且任取一个样本作为第一个聚合中心，Z1=x1寻找新的聚合中心，计算其它所有样本到寻找新的聚合中心，计算其它所有样本到Z1的距离的距离Di142最大最小距离聚类算法最大最小距离聚类算法按最近邻原则把所有样本归属于距离最近的聚按最近邻原则把所有样本归属于距离最近的聚合中心合中心按照某聚类准则考查聚类结果，若不满意，则按照某聚类准则考查聚类结果，若不满意，则重新选择重新选择，第一个聚合中心，返回到，第一个聚合中心，返回到，直到，直到满意，算法意，算法结束。束。u最大最小距离聚类算法：在模式特征矢量集中最大最小距离聚类算法：在模式特征矢量集
21、中以最大距离原则选取新的聚类中心，以最小距以最大距离原则选取新的聚类中心，以最小距离准则进行模式归类。离准则进行模式归类。u独立性能不好，依赖先验知识。独立性能不好，依赖先验知识。43最大最小距离聚类算法最大最小距离聚类算法例：例：44最大最小距离聚类算法最大最小距离聚类算法 453.5 系统聚类法系统聚类法(层次化聚类层次化聚类)u融合算法融合算法u会在每一步减少聚类中心数量，聚类产生的结会在每一步减少聚类中心数量，聚类产生的结果来自于前一步的两个聚类的合并；果来自于前一步的两个聚类的合并；u分裂算法分裂算法u在每一步增加聚类中心的数量，每一步聚类产在每一步增加聚类中心的数量，每一步聚类产生
22、的结果，都是将前一步的一个聚类中心分裂生的结果，都是将前一步的一个聚类中心分裂成两个得到。成两个得到。46层次聚类n分裂或凝聚分裂或凝聚算法运行到某一阶段，类别划分结果达到聚类标准时算法运行到某一阶段，类别划分结果达到聚类标准时即可停止分裂或凝聚即可停止分裂或凝聚;47融合算法融合算法融合算法基本思想：融合算法基本思想：u给定给定n个样本个样本xi，最初把每个样本看成一类，最初把每个样本看成一类i=xi，设聚类数，设聚类数c=nu当当c1时，重复进行以下操作：时，重复进行以下操作：u利用合适的相似性度量尺度和规则确定最相利用合适的相似性度量尺度和规则确定最相近的两个聚类近的两个聚类i 和和ju
23、合并合并i和和j：ij=i,j，从而得到一个类，从而得到一个类别数为别数为c-1的聚类解的聚类解u将将c值递减值递减u注意：在确定最近的两个聚类时，需要同时依注意：在确定最近的两个聚类时，需要同时依靠相似性度量和用于评价聚类相似性的规则。靠相似性度量和用于评价聚类相似性的规则。48融合算法融合算法设初始模式样本共有设初始模式样本共有N个，每个样本自成一类，即建立个，每个样本自成一类，即建立N类：类：G1(0), G2(0), , GN(0)。计算各类之间（在起始时也就是各。计算各类之间（在起始时也就是各个样本之间）的距离，可得一个个样本之间）的距离，可得一个N*N维的距离矩阵维的距离矩阵D(0
24、)如在如在距离运算中心已求得距离矩阵距离运算中心已求得距离矩阵D(n)，则求，则求D(n)中的最中的最小元素。如果它是小元素。如果它是Gi(n), Gj(n)两类之间的距离，则将两类之间的距离，则将Gi(n), Gj(n)两类合并为一类两类合并为一类Gij(n+1)。由此建立新的分类。由此建立新的分类G1(n+1), G2(n+1), 。计算合并后的新类别之间的距离，得计算合并后的新类别之间的距离，得D(n+1)。计算。计算Gij(n+1)与其与其他没有发生合并的他没有发生合并的G1(n+1), G2(n+1), 之间的距离时，有多种之间的距离时，有多种不同的距离计算准则。不同的距离计算准则。
25、跳到跳到，重复计算合并，可一直将全部样本聚集成一类。，重复计算合并，可一直将全部样本聚集成一类。49融合算法融合算法n视视N个模式各成为一类，计算类与类之间的距离，个模式各成为一类，计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的选择距离最小的一对合并成一个新类，计算在新的类别分划下各类之间的距离，再将距离最近的两类类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。合并，直至所有模式聚成两类为止。50融合算法融合算法例：给出例：给出6个样本待征矢量如下，按最小距离原则进个样本待征矢量如下，按最小距离原则进行聚类。行聚类。 x1=(0,3,1,2,0)
26、T x2=(1,3,0,1,0)T x3=(3,3,0,0,1)T x4=(1,1,0,2,0)T x5=(3,2,l,2,1)T x6=(4,1,1,1,0)T5152融合算法融合算法系统聚类过程可绘成树状表示，如图所示系统聚类过程可绘成树状表示，如图所示 53融合算法融合算法聚类聚类1 = Aveiro, Setubal, V.Castelo；财产方面的高犯罪率，超过对人身安全方面的犯罪率；财产方面的高犯罪率，超过对人身安全方面的犯罪率；聚类聚类2=Beja, Braga, Braganca, Coimbra, Porto, Santarem, Viseu；财产方面的高犯罪率，低于对人身安
27、全方面的犯罪率。财产方面的高犯罪率，低于对人身安全方面的犯罪率。聚类聚类3=C.Branco, Evora, Faro, Guarda, Leiria, Lisboa, Portalegre, V.Real；财产和人身安全方面的平均水平的犯罪率。；财产和人身安全方面的平均水平的犯罪率。 54融合算法融合算法w1=I，Dw2=A，B，C，E，F，G，Hw3=8，9w4=1，2，3，4，5，6，7 55融合算法改进融合算法改进u可将类间距离门限可将类间距离门限T作为停止条件，当作为停止条件，当D (k)中最中最小阵元大于小阵元大于T时，聚类过程停止；时，聚类过程停止；u也可将预定的类别数目作为停止
28、条件，在类别合并也可将预定的类别数目作为停止条件，在类别合并过程中，类数等于预定值时，聚类过程停止。过程中，类数等于预定值时，聚类过程停止。56层次化聚类联接规则层次化聚类联接规则联接规则：衡量聚类之间相异程度的方法。联接规则：衡量聚类之间相异程度的方法。u单联接单联接u完全联接规则完全联接规则u类间平均联接规则类间平均联接规则u类内平均联接规则类内平均联接规则uWard方法方法57最短距离法n理论基础理论基础n最短距离法认为，只要两类的最小距离小于阈值，就最短距离法认为，只要两类的最小距离小于阈值，就将两类合并成一类。定义将两类合并成一类。定义DI,J为为wi类中所有样品和类中所有样品和wj
29、类中所有样品间的最小距离，即类中所有样品间的最小距离，即n其中其中dUV表示表示wi类中的样品类中的样品U与与wj类中的样品类中的样品V之间的之间的距离。若距离。若wj类是由类是由wm、wn两类合并而成的，则两类合并而成的，则58n递推可得递推可得n计算计算w1到到w3,4的距离的距离D1,34，先计算，先计算w1类中各类中各个样品到个样品到w3类中各个样品的距离，取最小值为类中各个样品的距离，取最小值为D1,3；然后计算；然后计算w1类中各个样品到类中各个样品到w4类中各个类中各个样品的距离，取最小值为样品的距离，取最小值为D1,4；取；取D1,3、D1,4中的最小值为中的最小值为D1,34
30、。59实现步骤n获得所有样品特征。获得所有样品特征。n输入阈值输入阈值T（计算所有样品距离的最大值与最小值，输出，（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。作为阈值的参考）。n将所有样品各分一类，聚类中心数将所有样品各分一类，聚类中心数centerNum=样品总数，样品总数，m_pattern(i).category=i；m_center(i).feature=m_pattern(i).feature。n对所有样品循环：对所有样品循环：n找到距离最近的两类找到距离最近的两类pi、pj，设距离为，设距离为minDis。n若若minDisT，则合并，则合并pi、pj，将类号大的归
31、入到类号小的，将类号大的归入到类号小的类中，调整其他类保持类号连续。否则类中，调整其他类保持类号连续。否则minDisT，两类间的，两类间的最小距离大于阈值，则退出循环。最小距离大于阈值，则退出循环。60最长距离法n理论基础理论基础n在该算法中，两类中的所有样品间的距离必须都小在该算法中，两类中的所有样品间的距离必须都小于阈值，才能将两类合并。定义于阈值，才能将两类合并。定义Di,j为为wi类中所有样类中所有样品与品与wj中所有样品间的最大距离，则有中所有样品间的最大距离，则有Di,j=maxd U v , d U v:wi类中的样品类中的样品U与与wj类类中的样品中的样品V之间的距离。之间的
32、距离。n若若wj是由是由wm,wn两类合并而成，则两类合并而成，则nDi,j = maxDi,m , Di,n61实现步骤获得所有样品的特征值。获得所有样品的特征值。输入阈值输入阈值T将所有样品各分一类，聚类中心数为将所有样品各分一类，聚类中心数为centerNum,样品总数为样品总数为patternNum.对所有样品循环：对所有样品循环：计算所有聚类中心的距离，两类间的距离等于两类间样计算所有聚类中心的距离，两类间的距离等于两类间样品的最大距离品的最大距离maxdis取所有取所有maxDis中的最小值，设中的最小值，设pi类和类和pj类的距离最小，类的距离最小，为为minDis.若若minD
33、isT,所有类间距离均大于阈值，则推出循环，所有类间距离均大于阈值，则推出循环，归类完成。归类完成。62中间距离法n理论基础理论基础n最短距离法和最长距离法采用的是分类距离的两个最短距离法和最长距离法采用的是分类距离的两个极端。中间距离法则介于两者之间，若极端。中间距离法则介于两者之间，若wj类是由类是由wm、wn两类合并而成，则两类合并而成，则wi、wj两类的中间距两类的中间距离定义为离定义为n例如，计算距离例如，计算距离D1,34，先计算，先计算w1类中各个样品类中各个样品到到w3类中各个样品的距离类中各个样品的距离D1,3，然后计算，然后计算w1类中类中各个样品到各个样品到w4类中各个样
34、品的距离类中各个样品的距离D1,4，按照下，按照下式计算式计算D1,34：63实现步骤n获得所有样品特征。获得所有样品特征。n输入阈值输入阈值T（计算所有样品距离的最大值与最小值，输出，（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。作为阈值的参考）。n将所有样品各分一类，聚类中心数将所有样品各分一类，聚类中心数centerNum=样品总样品总数，数，m_pattern(i).category=i；m_center(i).feature=m_pattern(i).feature。n建立距离矩阵建立距离矩阵centerDistance，记录各类间的距离，初，记录各类间的距离，初始值为
35、各样品间的距离。始值为各样品间的距离。n对所有样品循环：对所有样品循环：n找到找到centerDistance中的最小值中的最小值td=centerDistance(ti, tj)，即，即ti类和类和tj类距离最小。类距离最小。n若若tdT，则将所有，则将所有tj类成员归入类成员归入ti类；类；centerNum=centerNum-1；重新顺序排列类号；根据；重新顺序排列类号；根据上式重新计算距离矩阵上式重新计算距离矩阵centerDistance，否则（，否则（tdT）终）终止循环，分类借宿。止循环，分类借宿。643.6 动态聚类算法n动态聚类算法选择若干样品作为聚类中心，再按照动态聚类算
36、法选择若干样品作为聚类中心，再按照某种聚类准则，如最小距离准则，将其余样品归入某种聚类准则，如最小距离准则，将其余样品归入最近的中心，得到初始分类。最近的中心，得到初始分类。n然后判断初始分类是否合理，若不合理则按照特定然后判断初始分类是否合理，若不合理则按照特定的规则重新修改不合理的分类，如此反复迭代，知的规则重新修改不合理的分类，如此反复迭代，知道分类合理。道分类合理。653.6 动态聚类算法动态聚类算法u算法首先选择某种样本相似性度量和适当的聚类准算法首先选择某种样本相似性度量和适当的聚类准则函数，使用迭代算法，在初始划分的基础上，逐则函数，使用迭代算法，在初始划分的基础上，逐步优化聚类
37、结果，使准则函数达到极值。步优化聚类结果，使准则函数达到极值。u算法要解决的关键问题：算法要解决的关键问题：u首先选择有代表性的点作为起始聚合中心。若类首先选择有代表性的点作为起始聚合中心。若类型数目已知，则选择代表点的数目等于类型数目；型数目已知，则选择代表点的数目等于类型数目；若未知，那么聚类过程要形成的类型数目，是一若未知，那么聚类过程要形成的类型数目，是一个问题。个问题。u代表点选择好之后，如何把所有样本区分到以代代表点选择好之后，如何把所有样本区分到以代表点为初始聚合中心的范围内，形成初始划分表点为初始聚合中心的范围内，形成初始划分66动态聚类算法动态聚类算法k-均值聚类算法使用的聚
38、类准则函数是误差平方均值聚类算法使用的聚类准则函数是误差平方和准则：和准则： uk-均值聚类算法均值聚类算法uISODATA算法算法67K-均值算法：理论基础nK均值算法能够使聚类域中所有样品到聚类中心距均值算法能够使聚类域中所有样品到聚类中心距离的平方和最小。离的平方和最小。n原理：原理：n先取先取K个初始距离中心，计算每个样品到这个个初始距离中心，计算每个样品到这个K个中个中心的距离，找出最小距离把样品归入最近的聚类中心。心的距离，找出最小距离把样品归入最近的聚类中心。n修改中心点的值为本类所有样品的均值，再计算各个修改中心点的值为本类所有样品的均值，再计算各个样品到样品到k个中心的距离，
39、重新归类，修改新的中心点。个中心的距离，重新归类，修改新的中心点。n直到新的距离中心等于上次的中心点结束。直到新的距离中心等于上次的中心点结束。68k-均值聚类算法均值聚类算法69k-均值聚类算法均值聚类算法算法特点：算法特点：每次迭代中都要考查每个样本的分类是否正确，若每次迭代中都要考查每个样本的分类是否正确，若不正确，就要调整，在全部样本调整完之后，再修不正确，就要调整，在全部样本调整完之后，再修改聚合中心，进入下一次迭代。如果在某一个迭代改聚合中心，进入下一次迭代。如果在某一个迭代运算中，所有的样本都被正确分类，则样本不会调运算中，所有的样本都被正确分类，则样本不会调整，聚合中心也不会有
40、变化，也就是收敛了。整，聚合中心也不会有变化，也就是收敛了。初始聚合中心的选择对聚类结果有较大影响。初始聚合中心的选择对聚类结果有较大影响。70k-均值聚类算法均值聚类算法例：现有混合样本集，共有样本例：现有混合样本集，共有样本20个，分布如下图个，分布如下图所示，类型数目所示，类型数目c=2。试用。试用k-均值算法进行聚类分析均值算法进行聚类分析 71k-均值聚类算法均值聚类算法72改进改进k-均值算法均值算法(c-均值算法均值算法)7374k-均值聚类算法均值聚类算法uk-均值算法的结果受如下选择的影响：均值算法的结果受如下选择的影响：n所选聚类的数目所选聚类的数目n聚类中心的初始分布聚类
41、中心的初始分布n模式样本的几何性质模式样本的几何性质n读入次序读入次序n在实际应用中，需要试探不同的在实际应用中，需要试探不同的K值和选择不同的值和选择不同的聚类中心的起始值。聚类中心的起始值。n如果模式样本可以形成若干个相距较远的小块孤立如果模式样本可以形成若干个相距较远的小块孤立的区域分布，一般都能得到较好的收敛效果。的区域分布，一般都能得到较好的收敛效果。nk-均值算法比较适合于分类数目已知的情况。均值算法比较适合于分类数目已知的情况。75ISODATAn此算法与此算法与K均值算法有相似之处，即聚类中心也是均值算法有相似之处，即聚类中心也是通过样品均值的迭代运算来决定的。但通过样品均值的
42、迭代运算来决定的。但ISODATA加入了一些试探性的步骤。能吸取中间结果所得到加入了一些试探性的步骤。能吸取中间结果所得到的经验，在迭代过程中可以将一类一份为二，也可的经验，在迭代过程中可以将一类一份为二，也可将两类合并，即自组织，具有启发性。将两类合并，即自组织，具有启发性。76ISODATA算法算法基本步骤和思路基本步骤和思路(1)选择某些初始值。可选不同的指标，也可在迭代选择某些初始值。可选不同的指标，也可在迭代过程中人为修改，以将过程中人为修改，以将N个模式样本按指标分配到个模式样本按指标分配到各个聚类中心中去。各个聚类中心中去。(2)计算各类中诸样本的距离指标函数。计算各类中诸样本的
43、距离指标函数。(3)(5)按给定的要求，将前一次获得的聚类集进行按给定的要求，将前一次获得的聚类集进行分裂和合并处理分裂和合并处理(4)为分裂处理，为分裂处理，(5)为合并处理为合并处理)，从而获得新的聚类中心。，从而获得新的聚类中心。(6)重新进行迭代运算，计算各项指标，判断聚类结重新进行迭代运算，计算各项指标，判断聚类结果是否符合要求。经过多次迭代后，若结果收敛，果是否符合要求。经过多次迭代后，若结果收敛，则运算结束。则运算结束。77迭代自组织数据分析迭代自组织数据分析(ISODATA)算法算法与与k-均值算法的比较均值算法的比较uk-均值算法通常适合于分类数目已知的聚类，而均值算法通常适
44、合于分类数目已知的聚类，而ISODATA算法则更加灵活；算法则更加灵活；u从算法角度看，从算法角度看， ISODATA算法与算法与K-均值算法相似，均值算法相似，聚类中心都是通过样本均值的迭代运算来决定的；聚类中心都是通过样本均值的迭代运算来决定的；uISODATA算法加入了一些试探步骤，并且可以结算法加入了一些试探步骤，并且可以结合成人机交互的结构，使其能利用中间结果所取得合成人机交互的结构，使其能利用中间结果所取得的经验更好地进行分类。的经验更好地进行分类。783.7 聚类评价聚类评价u聚类中心间的距离聚类中心间的距离u距离值大，通常可考虑分为不同类距离值大，通常可考虑分为不同类u每个聚类域中的样本数目每个聚类域中的样本数目u样本数目少且聚类中心距离远，可考虑是否为噪声样本数目少且聚类中心距离远，可考虑是否为噪声u每个聚类域内样本的距离方差每个聚类域内样本的距离方差u方差过大的样本可考虑是否属于这一类方差过大的样本可考虑是否属于这一类798081上机要求上机要求1.编写最近邻规则的聚类算法程序编写最近邻规则的聚类算法程序2.编写编写k-均值的聚类算法程序均值的聚类算法程序82
