模式识别课件--数据聚类

1、1第三章第三章 数据聚类数据聚类23.1 引言引言3.2 相似性度量相似性度量3.3 聚类准则聚类准则3.4 基于试探的两种聚类算法基于试探的两种聚类算法3.5 系统聚类法系统聚类法3.6 动态聚类动态聚类3.7 聚类评价聚类评价主要内容主要内容33.1 引言引言聚类：将数据分组成为多个类别，在同一个类内对聚类：将数据分组成为多个类别，在同一个类内对象之间具有较高的相似度，不同类之间的对象差别象之间具有较高的相似度，不同类之间的对象差别较大。较大。根据各个待分类的模式特征相似程度进行分类，根据各个待分类的模式特征相似程度进行分类，相相似似的归为一类，不相似的作为另一类。的归为一类，不相似的作为

2、另一类。u 监督学习：监督学习：需要用训练样本进行学习和训练需要用训练样本进行学习和训练u 非监督学习：对于没有类别标签的样本集，根非监督学习：对于没有类别标签的样本集，根据该问题本身的目的和样本的特性，把全体据该问题本身的目的和样本的特性，把全体N个样本划分为若干个子集，同类样本特性相差个样本划分为若干个子集，同类样本特性相差小，异类样本特性相差大。小，异类样本特性相差大。4聚类应用聚类应用花瓣的花瓣的“物以类聚物以类聚”5聚类应用聚类应用u早在孩提时代，人就通过不断改进下意识中的聚类早在孩提时代，人就通过不断改进下意识中的聚类模式来学会如何区分猫和狗，动物和植物模式来学会如何区分猫和狗，动

3、物和植物u谁经常光顾商店，谁买什么东西，买多少？谁经常光顾商店，谁买什么东西，买多少？u按照卡记录的光临次数、光临时间、性别、年龄、按照卡记录的光临次数、光临时间、性别、年龄、职业、购物种类、金额等变量分类职业、购物种类、金额等变量分类u这样商店可以这样商店可以.u识别顾客购买模式（如喜欢一大早来买酸奶和鲜肉，识别顾客购买模式（如喜欢一大早来买酸奶和鲜肉，习惯周末时一次性大采购）习惯周末时一次性大采购）u刻画不同的客户群的特征刻画不同的客户群的特征6聚类应用聚类应用u挖掘有价值的客户，并制定相应的促销策略：挖掘有价值的客户，并制定相应的促销策略：u如，对经常购买酸奶的客户如，对经常购买酸奶的客

4、户u对累计消费达到对累计消费达到12个月的老客户个月的老客户u针对潜在客户派发广告，比在大街上乱发传单针对潜在客户派发广告，比在大街上乱发传单命中率更高，成本更低！命中率更高，成本更低！7聚类应用聚类应用谁是银行信用卡的黄金客户？谁是银行信用卡的黄金客户？u利用储蓄额、刷卡消费金额、诚信度等变量对客户分利用储蓄额、刷卡消费金额、诚信度等变量对客户分类，找出类，找出“黄金客户黄金客户”！u这样银行可以制定更吸引的服务，留住客户！比如：这样银行可以制定更吸引的服务，留住客户！比如：u一定额度和期限的免息透支服务！一定额度和期限的免息透支服务！u商场的贵宾打折卡！商场的贵宾打折卡！u在他或她生日的时

5、候送上一个小蛋糕！在他或她生日的时候送上一个小蛋糕！8聚类应用聚类应用u经济领域：经济领域：u帮助市场分析人员从客户数据库中发现不同的客户群，帮助市场分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。并且用购买模式来刻画不同的客户群的特征。u谁喜欢打国际长途，在什么时间，打到那里？谁喜欢打国际长途，在什么时间，打到那里？u对住宅区进行聚类，确定自动提款机对住宅区进行聚类，确定自动提款机ATM的安放位置的安放位置u股票市场板块分析股票市场板块分析u生物学领域生物学领域u推导植物和动物的分类；推导植物和动物的分类；u对基因分类，获得对种群的认识对基因分类，获得对种群的

6、认识u数据挖掘领域数据挖掘领域u作为其他数学算法的预处理步骤，获得数据分布状况，作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步的研究集中对特定的类做进一步的研究9聚类分析原理聚类分析原理聚类分析中聚类分析中“类类”的特征：的特征：u聚类所说的类不是事先给定的，而是根据数据的聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分相似性和距离来划分u聚类的数目和结构都没有事先假定聚类的数目和结构都没有事先假定10聚类分析原理聚类分析原理聚类方法的目的是寻找数据中：聚类方法的目的是寻找数据中：u潜在的潜在的自然分组结构自然分组结构u感兴趣的感兴趣的关系关系11聚类分析原

7、理聚类分析原理什么是什么是自然分组结构自然分组结构?有有16张牌，如何将他们分组呢？张牌，如何将他们分组呢？AKQJ12聚类分析原理聚类分析原理分成四组：每组里分成四组：每组里花色相花色相同同，组与组之间花色相异，组与组之间花色相异AKQJ花色相同的牌为一组花色相同的牌为一组13聚类分析原理聚类分析原理分成四组，分成四组，符号相同符号相同的的牌为一组牌为一组AKQJ符号相同的的牌为一组符号相同的的牌为一组14聚类分析原理聚类分析原理分成两组，分成两组，颜色相同颜色相同的的牌为一组牌为一组AKQJ颜色相同的牌为一组颜色相同的牌为一组15聚类分析原理聚类分析原理u分组的意义在于我们怎么定义并度量分

8、组的意义在于我们怎么定义并度量“相似性相似性”u因此衍生出一系列度量相似性的算法因此衍生出一系列度量相似性的算法16聚类分析原理聚类分析原理相似性的度量（统计学角度）相似性的度量（统计学角度）u距离距离Q型聚类（主要讨论）型聚类（主要讨论）u主要用于对样本分类主要用于对样本分类u常用的距离有：常用的距离有：u明考夫斯基距离明考夫斯基距离(包括：绝对距离、欧式距离、切比包括：绝对距离、欧式距离、切比雪夫距离雪夫距离)u兰氏距离兰氏距离u马氏距离马氏距离u斜交空间距离斜交空间距离u此不详述，可参考此不详述，可参考应用多元分析应用多元分析（第二版）王（第二版）王学民学民17聚类分析原理聚类分析原理u

9、相似系数相似系数R型聚类型聚类u用于对变量分类，可以用变量之间的相似系数用于对变量分类，可以用变量之间的相似系数的变形，如的变形，如1rij定义距离定义距离18聚类分析原理聚类分析原理变量按测量尺度分类变量按测量尺度分类u间隔尺度变量间隔尺度变量 连续变量，如长度、重量、速度、温度等连续变量，如长度、重量、速度、温度等u有序尺度变量有序尺度变量 等级变量，不可加，但可比，如一等、二等、三等级变量，不可加，但可比，如一等、二等、三等奖学金等奖学金u名义尺度变量名义尺度变量 类别变量，不可加也不可比，如性别、职业等类别变量，不可加也不可比，如性别、职业等193.2 相似性度量相似性度量聚类分析符合

10、聚类分析符合“物以类聚，人以群分物以类聚，人以群分“的原则，它的原则，它把相似性大的样本聚集为一个类型把相似性大的样本聚集为一个类型 聚类分析的关键问题：如何在聚类过程中自动地确聚类分析的关键问题：如何在聚类过程中自动地确定类型数目定类型数目 20相似性度量相似性度量21相似性度量相似性度量u距离相似性度量距离相似性度量 u角度相似性度量角度相似性度量 22距离相似性度量距离相似性度量 模式样本向量与之间的欧氏距离定义为：模式样本向量与之间的欧氏距离定义为： u若距离阈值若距离阈值ds选择过大，则全部样本被视作一选择过大，则全部样本被视作一个唯一类型；若个唯一类型；若ds选取过小，则可能造成每

11、个选取过小，则可能造成每个样本都单独构成一个类型样本都单独构成一个类型diiieyxyxyxD12|),(23距离相似性度量距离相似性度量距离阈值对聚类的影响距离阈值对聚类的影响24距离相似性度量距离相似性度量u特征选取不当使聚类无效特征选取不当使聚类无效u特征选取不足引起误分类特征选取不足引起误分类u模式特征坐标单位的选取也会强烈地影响聚类模式特征坐标单位的选取也会强烈地影响聚类结果结果25距离相似性度量距离相似性度量特征选取不当使聚类无效特征选取不当使聚类无效1226距离相似性度量距离相似性度量特征选取不足引起误分类特征选取不足引起误分类12327距离相似性度量距离相似性度量acbd28解

12、决尺度问题解决尺度问题标准化标准化iiyxms minmaxminiiiiiyxxxx maxminiiiiyxxxiiyx a29解决尺度问题解决尺度问题 为了进行聚类，我们需要一种合适的距离度量尺为了进行聚类，我们需要一种合适的距离度量尺度。度。u这种距离度量尺度依赖于特征标准化方法这种距离度量尺度依赖于特征标准化方法u为了选择标准化方法我们必须知道聚类的类型为了选择标准化方法我们必须知道聚类的类型u试错法是唯一的避免这种恶性循环的方法。选择试错法是唯一的避免这种恶性循环的方法。选择不同的条件进行试验，通过观察、数据解释和效不同的条件进行试验，通过观察、数据解释和效用分析评价相应的解。平衡

13、各特征值的贡献，并用分析评价相应的解。平衡各特征值的贡献，并保持原有的语义信息。保持原有的语义信息。30角度相似性度量角度相似性度量 样本与之间的角度相似性度量定义为它们之间夹角样本与之间的角度相似性度量定义为它们之间夹角的余弦的余弦 |cos),(yxyxyxST313.3 聚类准则聚类准则u相似性度量相似性度量 集合与集合的相似性集合与集合的相似性u相似性准则相似性准则 分类效果好坏的评价准则分类效果好坏的评价准则 聚类准则聚类准则:u试探法试探法 定义一种相似性度量的阈值定义一种相似性度量的阈值u聚类准则函数法聚类准则函数法 聚类准则是反映类别间相似性或分离性的函数聚类准则是反映类别间相

14、似性或分离性的函数u误差平方和准则（最常用的）误差平方和准则（最常用的）u加权平均平方距离和准则加权平均平方距离和准则 32误差平方和准则误差平方和准则假定有混合样本假定有混合样本X=x1, x2, , xn采用某种相似性度量，采用某种相似性度量，X被聚合成被聚合成c个分离开的子集个分离开的子集X1, X2, , Xc。每个子集是一个类型，它们分别包含。每个子集是一个类型，它们分别包含n1, n2, , nc个样本个样本为了衡量类的质量，采用误差平方和为了衡量类的质量，采用误差平方和Jc聚类准则函数，聚类准则函数，定义为：定义为：mj为类型为类型Xj中样本的均值，中样本的均值，mj是是c个集合

15、的中心，可个集合的中心，可以用来代表以用来代表c个类型。个类型。33误差平方和准则误差平方和准则误差平方和准则适用于各类样本比较密集且样本数误差平方和准则适用于各类样本比较密集且样本数目悬殊不大的样本分布目悬殊不大的样本分布 34误差平方和准则误差平方和准则例：例：35加权平均平方距离和准则加权平均平方距离和准则 定义加权平均平方距离和准则：定义加权平均平方距离和准则：式中：式中：Sj*是类内样本间平均平方距离是类内样本间平均平方距离 cjjjjSPJ1* jjXxXxjjjxxnnS2*|) 1(2Xj中的样本个数中的样本个数nj，Xj中的样本两两组合共有中的样本两两组合共有nj(nj-1)

16、/2种种 表示所有样本之间距离之和表示所有样本之间距离之和Pj为为j类的先验概率，可以用样本数目类的先验概率，可以用样本数目nj和样本总和样本总数目数目n来估计，来估计，Pj=nj/n, j=1,2,c2 jjXxXxxx36加权平均平方距离和准则加权平均平方距离和准则例：例：373.4 基于试探的两种聚类算法基于试探的两种聚类算法u采用最近邻规则的聚类算法采用最近邻规则的聚类算法 u最大最小距离聚类算法最大最小距离聚类算法 38采用最近邻规则的聚类算法采用最近邻规则的聚类算法n选取距离阈值选取距离阈值T，并且任取一个样本作为第一个聚，并且任取一个样本作为第一个聚合中心合中心Z1，如：，如：Z

17、1=x1n 计算样本计算样本x2到到Z1的距离的距离D21 若若D21T，则，则x2Z1，否则令，否则令x2为第二个聚合中心，为第二个聚合中心，Z2=x2 设设Z2=x2，计算，计算x3到到Z1和和Z2的距离的距离D31和和D32，若，若D31T和和D32T，则建立第三个聚合中心，则建立第三个聚合中心Z3。否则把。否则把x3归于归于最近邻的聚合中心。依此类推，直到把所有的最近邻的聚合中心。依此类推，直到把所有的n个个样本都进行分类。样本都进行分类。n 按照某种聚类准则考察聚类结果，若不满意，则重按照某种聚类准则考察聚类结果，若不满意，则重新选取距离阈值新选取距离阈值T、第一个聚合中心、第一个聚

18、合中心Z1，返回，返回，直到满意，算法结束。直到满意，算法结束。39采用最近邻规则的聚类算法采用最近邻规则的聚类算法u最近邻规则的聚类算法：计算模式特征矢量到最近邻规则的聚类算法：计算模式特征矢量到聚类中心的距离，和门限聚类中心的距离，和门限T比较，决定归属哪类比较，决定归属哪类或作为新的聚类中心。或作为新的聚类中心。u该算法的优点是简单，如果有样本分布的先验该算法的优点是简单，如果有样本分布的先验知识用于指导阈值和起始点的选取，则可较快知识用于指导阈值和起始点的选取，则可较快得到合理结果。得到合理结果。u算法的结果在很多程度上取决于第一个聚合中算法的结果在很多程度上取决于第一个聚合中心的选取

19、和距离阈值的大小。心的选取和距离阈值的大小。40阈值对聚类的影响阈值对聚类的影响41起始点对聚类的影响起始点对聚类的影响Z=x1Z=x5Z=x742最大最小距离聚类算法最大最小距离聚类算法若若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存在，则计算存在

20、，则计算Dj=maxmin(Di1, Di2, Di3), i=1, 2, , n，若若DjD12，则建立第四个聚合中心。依此类推，直到最大，则建立第四个聚合中心。依此类推，直到最大最小距离不大于最小距离不大于D12时，结束寻找聚合中心的计算。时，结束寻找聚合中心的计算。u给定给定，01，并且任取一个样本作为第一个聚合中心，并且任取一个样本作为第一个聚合中心，Z1=x1u寻找新的聚合中心，计算其它所有样本到寻找新的聚合中心，计算其它所有样本到Z1的距离的距离Di143最大最小距离聚类算法最大最小距离聚类算法n 按最近邻原则把所有样本归属于距离最近的聚按最近邻原则把所有样本归属于距离最近的聚合中

21、心合中心n 按照某聚类准则考查聚类结果，若不满意，则按照某聚类准则考查聚类结果，若不满意，则重新选择重新选择，第一个聚合中心，返回到，第一个聚合中心，返回到，直到，直到满意，算法结束。满意，算法结束。u最大最小距离聚类算法：在模式特征矢量集中最大最小距离聚类算法：在模式特征矢量集中以最大距离原则选取新的聚类中心，以最小距以最大距离原则选取新的聚类中心，以最小距离准则进行模式归类。离准则进行模式归类。u独立性能不好，依赖先验知识。独立性能不好，依赖先验知识。44最大最小距离聚类算法最大最小距离聚类算法例：例：45最大最小距离聚类算法最大最小距离聚类算法 463.5 系统聚类法系统聚类法(层次化聚

22、类层次化聚类)u融合算法融合算法u分裂算法分裂算法47融合算法融合算法融合算法基本思想：融合算法基本思想：u给定给定n个样本个样本xi，最初把每个样本看成一类，最初把每个样本看成一类i=xi，设聚类数，设聚类数c=nu当当c1时，重复进行以下操作：时，重复进行以下操作：u利用合适的相似性度量尺度和规则确定最相利用合适的相似性度量尺度和规则确定最相近的两个聚类近的两个聚类i 和和iu合并合并i和和j：ij=i,j，从而得到一个类别，从而得到一个类别数为数为c-1的聚类解的聚类解u将将c值递减值递减u注意：在确定最近的两个聚类时，需要同时依注意：在确定最近的两个聚类时，需要同时依靠相似性度量和用于

23、评价聚类相似性的规则。靠相似性度量和用于评价聚类相似性的规则。48融合算法融合算法n 设初始模式样本共有设初始模式样本共有N个，每个样本自成一类，即建立个，每个样本自成一类，即建立N类：类：G1(0), G2(0), , GN(0)。计算各类之间（在起始时也就是各个样。计算各类之间（在起始时也就是各个样本之间）的距离，可得一个本之间）的距离，可得一个N*N维的距离矩阵维的距离矩阵D(0)n 如在如在距离运算中心已求得距离矩阵距离运算中心已求得距离矩阵D(n)，则求，则求D(n)中的最小中的最小元素。如果它是元素。如果它是Gi(n), Gj(n)两类之间的距离，则将两类之间的距离，则将Gi(n)

24、, Gj(n)两两类合并为一类类合并为一类Gij(n+1)。由此建立新的分类。由此建立新的分类G1(n+1), G2(n+1), 。n 计算合并后的新类别之间的距离，得计算合并后的新类别之间的距离，得D(n+1)。计算。计算Gij(n+1)与其与其他没有发生合并的他没有发生合并的G1(n+1), G2(n+1), 之间的距离时，有多种之间的距离时，有多种不同的距离计算准则。不同的距离计算准则。n 跳到跳到，重复计算合并，可一直将全部样本聚集成一类。，重复计算合并，可一直将全部样本聚集成一类。49融合算法融合算法n视视N个模式各成为一类，计算类与类之间的距离，个模式各成为一类，计算类与类之间的距

25、离，选择距离最小的一对合并成一个新类，计算在新选择距离最小的一对合并成一个新类，计算在新的类别分划下各类之间的距离，再将距离最近的的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。两类合并，直至所有模式聚成两类为止。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)T51选择距离函数的形式选择聚类的方法输

26、入N个模式样本的特征向量计算N*N维距离矩阵D(0)设置迭代次数n=N按不同的距离函数计算求距离矩阵中的元素，将二类合并。建立新的距离矩阵D(n+1) n=n-1n=0输出聚类的分级树是否52融合算法融合算法系统聚类过程可绘成树状表示，如图所示系统聚类过程可绘成树状表示，如图所示 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方法方法,minijijxydxy ,maxijijxydxy 1,ijijxyijdxynn ,1,2ijijx yijdxyC nn 2,1,ijijxijdxmnn 573.6 动态聚类算法动态聚类

29、算法u算法首先选择某种样本相似性度量和适当的聚类准算法首先选择某种样本相似性度量和适当的聚类准则函数，使用迭代算法，在初始划分的基础上，逐则函数，使用迭代算法，在初始划分的基础上，逐步优化聚类结果，使准则函数达到极值。步优化聚类结果，使准则函数达到极值。u算法要解决的关键问题：算法要解决的关键问题：u首先选择有代表性的点作为起始聚合中心。若类首先选择有代表性的点作为起始聚合中心。若类型数目已知，则选择代表点的数目等于类型数目；型数目已知，则选择代表点的数目等于类型数目；若未知，那么聚类过程要形成的类型数目，是一若未知，那么聚类过程要形成的类型数目，是一个问题。个问题。u代表点选择好之后，如何把

30、所有样本区分到以代代表点选择好之后，如何把所有样本区分到以代表点为初始聚合中心的范围内，形成初始划分表点为初始聚合中心的范围内，形成初始划分58动态聚类算法动态聚类算法k-均值聚类算法使用的聚类准则函数是误差平方均值聚类算法使用的聚类准则函数是误差平方和准则：和准则： cjnkjkcjmxJ112|uk-均值聚类算法均值聚类算法uISODATA算法算法59k-均值聚类算法均值聚类算法60k-均值聚类算法均值聚类算法算法特点：算法特点：每次迭代中都要考查每个样本的分类是否正确，若每次迭代中都要考查每个样本的分类是否正确，若不正确，就要调整，在全部样本调整完之后，再修不正确，就要调整，在全部样本调

31、整完之后，再修改聚合中心，进入下一次迭代。如果在某一个迭代改聚合中心，进入下一次迭代。如果在某一个迭代运算中，所有的样本都被正确分类，则样本不会调运算中，所有的样本都被正确分类，则样本不会调整，聚合中心也不会有变化，也就是收敛了。整，聚合中心也不会有变化，也就是收敛了。初始聚合中心的选择对聚类结果有较大影响。初始聚合中心的选择对聚类结果有较大影响。61k-均值聚类算法均值聚类算法例：现有混合样本集，共有样本例：现有混合样本集，共有样本20个，分布如下图个，分布如下图所示，类型数目所示，类型数目c=2。试用。试用k-均值算法进行聚类分析均值算法进行聚类分析 62k-均值聚类算法均值聚类算法63改进改进k-均值算法均值算法(c-均值算法均值算法)6465k-均值聚类算法均值聚类算法uk-均值算法的结果受如下选择的影响：均值算法的结果受如下选择的影响：n所选聚类的数目所选聚类的数目n聚类中心的初始分布聚类中心的初始分布n模式样本的几何性质模式样本的几何性质n读入次序读入次序n在实际应用中，需要试探不同的在实际应用中，需要试探不同的K值和选择不同的值和选择不同的聚类中心的起始值。聚类中心的起始值。n如果模式样本可以形成若干个相距较远的小块孤如