第8章数据挖掘课件数据聚类.ppt

《第8章数据挖掘课件数据聚类.ppt》由会员分享，可在线阅读，更多相关《第8章数据挖掘课件数据聚类.ppt（82页珍藏版）》请在三一文库上搜索。

1、1,第8章 数据聚类,2,3.1 引言 3.2 相似性度量 3.3 聚类准则 3.4 基于试探的两种聚类算法 3.5 系统聚类法 3.6 动态聚类 3.7 聚类评价,主要内容,3,3.1 引言,聚类：将数据分组成为多个类别，在同一个类内对象之间具有较高的相似度，不同类之间的对象差别较大。 根据各个待分类的模式特征相似程度进行分类，相似的归为一类，不相似的作为另一类。,监督学习：需要用训练样本进行学习和训练 非监督学习：对于没有类别标签的样本集，根据该问题本身的目的和样本的特性，把全体N个样本划分为若干个子集，同类样本特性相差小，异类样本特性相差大。,4,聚类应用,花瓣的“物以类聚”,5,聚类应

2、用,早在孩提时代，人就通过不断改进下意识中的聚类模式来学会如何区分猫和狗，动物和植物 谁经常光顾商店，谁买什么东西，买多少？ 按照卡记录的光临次数、光临时间、性别、年龄、职业、购物种类、金额等变量分类 这样商店可以. 识别顾客购买模式（如喜欢一大早来买酸奶和鲜肉，习惯周末时一次性大采购） 刻画不同的客户群的特征,6,聚类应用,挖掘有价值的客户，并制定相应的促销策略： 如，对经常购买酸奶的客户 对累计消费达到12个月的老客户 针对潜在客户派发广告，比在大街上乱发传单命中率更高，成本更低！,7,聚类应用,谁是银行信用卡的黄金客户？ 利用储蓄额、刷卡消费金额、诚信度等变量对客户分类，找出“黄金客户”

3、！ 这样银行可以制定更吸引的服务，留住客户！比如： 一定额度和期限的免息透支服务！ 商场的贵宾打折卡！ 在他或她生日的时候送上一个小蛋糕！,8,聚类应用,经济领域： 帮助市场分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。 谁喜欢打国际长途，在什么时间，打到那里？ 对住宅区进行聚类，确定自动提款机ATM的安放位置 股票市场板块分析 生物学领域 推导植物和动物的分类； 对基因分类，获得对种群的认识 数据挖掘领域 作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步的研究,9,聚类分析原理,聚类分析中“类”的特征： 聚类所说的类不是事先给定的，而是

4、根据数据的相似性和距离来划分 聚类的数目和结构都没有事先假定,10,聚类分析原理,聚类方法的目的是寻找数据中： 潜在的自然分组结构 感兴趣的关系,11,聚类分析原理,什么是自然分组结构? 有16张牌，如何将他们分组呢？,12,聚类分析原理,分成四组：每组里花色相同，组与组之间花色相异,花色相同的牌为一组,13,聚类分析原理,分成四组，符号相同的牌为一组,符号相同的的牌为一组,14,聚类分析原理,分成两组，颜色相同的牌为一组,颜色相同的牌为一组,15,聚类分析原理,分组的意义在于我们怎么定义并度量“相似性” 因此衍生出一系列度量相似性的算法,16,聚类分析原理,相似性的度量（统计学角度） 距离Q

5、型聚类（主要讨论） 主要用于对样本分类 常用的距离有： 明考夫斯基距离(包括：绝对距离、欧式距离、切比雪夫距离) 兰氏距离 马氏距离 斜交空间距离 此不详述，可参考应用多元分析（第二版）王学民,17,聚类分析原理,相似系数R型聚类 用于对变量分类，可以用变量之间的相似系数的变形，如1rij定义距离,18,聚类分析原理,变量按测量尺度分类 间隔尺度变量 连续变量，如长度、重量、速度、温度等 有序尺度变量 等级变量，不可加，但可比，如一等、二等、三等奖学金 名义尺度变量 类别变量，不可加也不可比，如性别、职业等,19,3.2 相似性度量,聚类分析符合“物以类聚，人以群分“的原则，它把相似性大的样本

6、聚集为一个类型,聚类分析的关键问题：如何在聚类过程中自动地确定类型数目,20,相似性度量,21,相似性度量,距离相似性度量 角度相似性度量,22,距离相似性度量,模式样本向量与之间的欧氏距离定义为： 若距离阈值ds选择过大，则全部样本被视作一个唯一类型；若ds选取过小，则可能造成每个样本都单独构成一个类型,23,距离相似性度量,距离阈值对聚类的影响,24,距离相似性度量,特征选取不当使聚类无效 特征选取不足引起误分类 模式特征坐标单位的选取也会强烈地影响聚类结果,25,距离相似性度量,特征选取不当使聚类无效,26,距离相似性度量,特征选取不足引起误分类,27,距离相似性度量,28,解决尺度问题

7、标准化,29,解决尺度问题,为了进行聚类，我们需要一种合适的距离度量尺度。 这种距离度量尺度依赖于特征标准化方法 为了选择标准化方法我们必须知道聚类的类型 试错法是唯一的避免这种恶性循环的方法。选择不同的条件进行试验，通过观察、数据解释和效用分析评价相应的解。平衡各特征值的贡献，并保持原有的语义信息。,30,角度相似性度量,样本与之间的角度相似性度量定义为它们之间夹角的余弦,31,3.3 聚类准则,相似性度量 集合与集合的相似性 相似性准则 分类效果好坏的评价准则 聚类准则: 试探法 定义一种相似性度量的阈值 聚类准则函数法 聚类准则是反映类别间相似性或分离性的函数 误差平方和准则（最常用的）

8、 加权平均平方距离和准则,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，X

9、j中的样本两两组合共有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。否则把

10、x3归于最近邻的聚合中心。依此类推，直到把所有的n个样本都进行分类。 按照某种聚类准则考察聚类结果，若不满意，则重新选取距离阈值T、第一个聚合中心Z1，返回，直到满意，算法结束。,39,采用最近邻规则的聚类算法,最近邻规则的聚类算法：计算模式特征矢量到聚类中心的距离，和门限T比较，决定归属哪类或作为新的聚类中心。 该算法的优点是简单，如果有样本分布的先验知识用于指导阈值和起始点的选取，则可较快得到合理结果。 算法的结果在很多程度上取决于第一个聚合中心的选取和距离阈值的大小。,40,阈值对聚类的影响,41,起始点对聚类的影响,Z=x1,Z=x5,Z=x7,42,最大最小距离聚类算法,若Dk1=m

11、axDi1，则取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,

12、最大最小距离聚类算法,按最近邻原则把所有样本归属于距离最近的聚合中心 按照某聚类准则考查聚类结果，若不满意，则重新选择，第一个聚合中心，返回到，直到满意，算法结束。 最大最小距离聚类算法：在模式特征矢量集中以最大距离原则选取新的聚类中心，以最小距离准则进行模式归类。 独立性能不好，依赖先验知识。,44,最大最小距离聚类算法,例：,45,最大最小距离聚类算法,46,3.5 系统聚类法(层次化聚类),融合算法 会在每一步减少聚类中心数量，聚类产生的结果来自于前一步的两个聚类的合并； 分裂算法 在每一步增加聚类中心的数量，每一步聚类产生的结果，都是将前一步的一个聚类中心分裂成两个得到。,47,层次聚

13、类,分裂或凝聚,算法运行到某一阶段，类别划分结果达到聚类标准时即可停止分裂或凝聚;,48,融合算法,融合算法基本思想： 给定n个样本xi，最初把每个样本看成一类i=xi，设聚类数c=n 当c1时，重复进行以下操作： 利用合适的相似性度量尺度和规则确定最相近的两个聚类i 和j 合并i和j：ij=i,j，从而得到一个类别数为c-1的聚类解 将c值递减 注意：在确定最近的两个聚类时，需要同时依靠相似性度量和用于评价聚类相似性的规则。,49,融合算法,设初始模式样本共有N个，每个样本自成一类，即建立N类：G1(0), G2(0), , GN(0)。计算各类之间（在起始时也就是各个样本之间）的距离，可得

14、一个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), 之间的距离时，有多种不同的距离计算准则。 跳到，重复计算合并，可一直将全部样本聚集成一类。,50,融合算法,视N个模式各成为一类，计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的类别分划下各类之间的

15、距离，再将距离最近的两类合并，直至所有模式聚成两类为止。,51,融合算法,例：给出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)T,52,53,融合算法,系统聚类过程可绘成树状表示，如图所示,54,融合算法,聚类1 = Aveiro, Setubal, V.Castelo； 财产方面的高犯罪率，超过对人身安全方面的犯罪率； 聚类2=Beja, Braga, Braganca, Coimbra, Porto,

16、 Santarem, Viseu； 财产方面的高犯罪率，低于对人身安全方面的犯罪率。 聚类3=C.Branco, Evora, Faro, Guarda, Leiria, Lisboa, Portalegre, V.Real；财产和人身安全方面的平均水平的犯罪率。,55,融合算法,w1=I，D w2=A，B，C，E，F，G，H w3=8，9 w4=1，2，3，4，5，6，7,56,融合算法改进,可将类间距离门限T作为停止条件，当D (k)中最小阵元大于T时，聚类过程停止； 也可将预定的类别数目作为停止条件，在类别合并过程中，类数等于预定值时，聚类过程停止。,57,层次化聚类联接规则,联接规则：

17、衡量聚类之间相异程度的方法。 单联接 完全联接规则 类间平均联接规则 类内平均联接规则 Ward方法,58,最短距离法,理论基础 最短距离法认为，只要两类的最小距离小于阈值，就将两类合并成一类。定义DI,J为wi类中所有样品和wj类中所有样品间的最小距离，即 其中dUV表示wi类中的样品U与wj类中的样品V之间的距离。若wj类是由wm、wn两类合并而成的，则,59,递推可得 计算w1到w3,4的距离D1,34，先计算w1类中各个样品到w3类中各个样品的距离，取最小值为D1,3；然后计算w1类中各个样品到w4类中各个样品的距离，取最小值为D1,4；取D1,3、D1,4中的最小值为D1,34。,6

18、0,实现步骤,获得所有样品特征。 输入阈值T（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。 将所有样品各分一类，聚类中心数centerNum=样品总数，m_pattern(i).category=i；m_center(i).feature=m_pattern(i).feature。 对所有样品循环： 找到距离最近的两类pi、pj，设距离为minDis。 若minDisT，则合并pi、pj，将类号大的归入到类号小的类中，调整其他类保持类号连续。否则minDisT，两类间的最小距离大于阈值，则退出循环。,61,最长距离法,理论基础 在该算法中，两类中的所有样品间的距离必须都小于阈值，

19、才能将两类合并。定义Di,j为wi类中所有样品与wj中所有样品间的最大距离，则有Di,j=maxd U v , d U v:wi类中的样品U与wj类中的样品V之间的距离。 若wj是由wm,wn两类合并而成，则 Di,j = maxDi,m , Di,n,62,实现步骤,获得所有样品的特征值。 输入阈值T 将所有样品各分一类，聚类中心数为centerNum,样品总数为patternNum. 对所有样品循环： 计算所有聚类中心的距离，两类间的距离等于两类间样品的最大距离maxdis 取所有maxDis中的最小值，设pi类和pj类的距离最小，为minDis. 若minDisT,所有类间距离均大于阈值

20、，则推出循环，归类完成。,中间距离法,理论基础 最短距离法和最长距离法采用的是分类距离的两个极端。中间距离法则介于两者之间，若wj类是由wm、wn两类合并而成，则wi、wj两类的中间距离定义为 例如，计算距离D1,34，先计算w1类中各个样品到w3类中各个样品的距离D1,3，然后计算w1类中各个样品到w4类中各个样品的距离D1,4，按照下式计算D1,34：,实现步骤,获得所有样品特征。 输入阈值T（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。 将所有样品各分一类，聚类中心数centerNum=样品总数，m_pattern(i).category=i；m_center(i).fea

21、ture=m_pattern(i).feature。 建立距离矩阵centerDistance，记录各类间的距离，初始值为各样品间的距离。 对所有样品循环： 找到centerDistance中的最小值td=centerDistance(ti, tj)，即ti类和tj类距离最小。 若tdT，则将所有tj类成员归入ti类；centerNum=centerNum-1；重新顺序排列类号；根据上式重新计算距离矩阵centerDistance，否则（tdT）终止循环，分类借宿。,65,3.6 动态聚类算法,动态聚类算法选择若干样品作为聚类中心，再按照某种聚类准则，如最小距离准则，将其余样品归入最近的中心，

22、得到初始分类。 然后判断初始分类是否合理，若不合理则按照特定的规则重新修改不合理的分类，如此反复迭代，知道分类合理。,66,3.6 动态聚类算法,算法首先选择某种样本相似性度量和适当的聚类准则函数，使用迭代算法，在初始划分的基础上，逐步优化聚类结果，使准则函数达到极值。 算法要解决的关键问题： 首先选择有代表性的点作为起始聚合中心。若类型数目已知，则选择代表点的数目等于类型数目；若未知，那么聚类过程要形成的类型数目，是一个问题。 代表点选择好之后，如何把所有样本区分到以代表点为初始聚合中心的范围内，形成初始划分,67,动态聚类算法,k-均值聚类算法使用的聚类准则函数是误差平方和准则：,k-均值

23、聚类算法 ISODATA算法,68,K-均值算法：理论基础,K均值算法能够使聚类域中所有样品到聚类中心距离的平方和最小。 原理： 先取K个初始距离中心，计算每个样品到这个K个中心的距离，找出最小距离把样品归入最近的聚类中心。 修改中心点的值为本类所有样品的均值，再计算各个样品到k个中心的距离，重新归类，修改新的中心点。 直到新的距离中心等于上次的中心点结束。,69,k-均值聚类算法,70,k-均值聚类算法,算法特点： 每次迭代中都要考查每个样本的分类是否正确，若不正确，就要调整，在全部样本调整完之后，再修改聚合中心，进入下一次迭代。如果在某一个迭代运算中，所有的样本都被正确分类，则样本不会调整

24、，聚合中心也不会有变化，也就是收敛了。 初始聚合中心的选择对聚类结果有较大影响。,71,k-均值聚类算法,例：现有混合样本集，共有样本20个，分布如下图所示，类型数目c=2。试用k-均值算法进行聚类分析,72,k-均值聚类算法,73,改进k-均值算法(c-均值算法),74,75,k-均值聚类算法,k-均值算法的结果受如下选择的影响： 所选聚类的数目 聚类中心的初始分布 模式样本的几何性质 读入次序 在实际应用中，需要试探不同的K值和选择不同的聚类中心的起始值。 如果模式样本可以形成若干个相距较远的小块孤立的区域分布，一般都能得到较好的收敛效果。 k-均值算法比较适合于分类数目已知的情况。,76

25、,ISODATA,此算法与K均值算法有相似之处，即聚类中心也是通过样品均值的迭代运算来决定的。但ISODATA加入了一些试探性的步骤。能吸取中间结果所得到的经验，在迭代过程中可以将一类一份为二，也可将两类合并，即自组织，具有启发性。,77,ISODATA算法,基本步骤和思路 (1)选择某些初始值。可选不同的指标，也可在迭代过程中人为修改，以将N个模式样本按指标分配到各个聚类中心中去。 (2)计算各类中诸样本的距离指标函数。 (3)(5)按给定的要求，将前一次获得的聚类集进行分裂和合并处理(4)为分裂处理，(5)为合并处理)，从而获得新的聚类中心。 (6)重新进行迭代运算，计算各项指标，判断聚类

26、结果是否符合要求。经过多次迭代后，若结果收敛，则运算结束。,78,迭代自组织数据分析(ISODATA)算法,与k-均值算法的比较 k-均值算法通常适合于分类数目已知的聚类，而ISODATA算法则更加灵活； 从算法角度看， ISODATA算法与K-均值算法相似，聚类中心都是通过样本均值的迭代运算来决定的； ISODATA算法加入了一些试探步骤，并且可以结合成人机交互的结构，使其能利用中间结果所取得的经验更好地进行分类。,79,3.7 聚类评价,聚类中心间的距离 距离值大，通常可考虑分为不同类 每个聚类域中的样本数目 样本数目少且聚类中心距离远，可考虑是否为噪声 每个聚类域内样本的距离方差 方差过大的样本可考虑是否属于这一类,80,81,82,上机要求,1.编写最近邻规则的聚类算法程序 2.编写k-均值的聚类算法程序,