模式识别课件之数据聚类

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