数据挖掘课件-数据聚类.ppt

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