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