《第六章 数据挖掘基本算法优秀课件.ppt》由会员分享，可在线阅读，更多相关《第六章 数据挖掘基本算法优秀课件.ppt（122页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章数据挖掘基本算法第1页，本讲稿共122页数据仓库与数据挖掘数据仓库与数据挖掘第一章数据仓库与数据挖掘概述第二章数据仓库的分析第三章数据仓库的设计与实施第四章信息分析的基本技术第五章数据挖掘过程第六章第六章 数据挖掘基本算法数据挖掘基本算法第七章非结构化数据挖掘第八章离群数据挖掘第九章数据挖掘语言与工具的选择第十章知识管理与知识管理系统第2页，本讲稿共122页第六章第六章 数据挖掘基本算法数据挖掘基本算法6.1 分类规则挖掘分类规则挖掘6.2预测分析与趋势分析规则6.3数据挖掘的关联算法6.4 数据挖掘的聚类算法数据挖掘的聚类算法6.5数据挖掘的统计分析算法6.6数据挖掘的品种优化算法6.
2、7数据挖掘的进化算法第3页，本讲稿共122页6.4 数据挖掘的聚类算法数据挖掘的聚类算法聚类分析是对群体及成员进行分类的递归过程。一个簇是一组数据对象的集合，在同一簇中的对象彼此类似，而不同簇中的对象彼此相异。将一组物理或抽象对象分组成由类似对象组成的多个簇的过程被称为聚类。聚类就是将数据对象分组成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。距离是经常采用的度量方式。第4页，本讲稿共122页6.4 数据挖掘的聚类算法数据挖掘的聚类算法聚类分析的应用：市场或客户分割、模式识别、生物学研究、空间数据分析、Web文档分类等。聚类分析可以用作独立的数据挖掘式工具，来获
3、得对数据分布的了解，也可以作为其他数据挖掘算法的预处理步骤。聚类的质量是基于对象相异度来评估的。相异度是描述对象的属性值来计算的。相异度可以对多种类型的数据来计算，包括区间标度变量、二元变量、标称变量、序数型变量和比例度型变量类型的组合。第5页，本讲稿共122页6.4 数据挖掘的聚类算法数据挖掘的聚类算法聚类分析的算法可以分为：划分方法：首先得到初始的K个划分的集合。如K-平均、K-中心点、CLARANS以及对它们的改进。层次方法：创建给定数据对象集合的一个层次性的分解。根据层次分解的过程可以分为凝聚（自底向上）或分裂（自顶向下）。基于密度的方法：根据密度的概念来聚类对象，如DBSCAN、DE
4、NCLUE、OPTICS。基于网格的方法：首先将对象空间量化为有限数目的单元，形成网格结构，然后在网格结构上进行聚类，如STING、CLIQUE、WaveCluster。基于模型的方法：为每个簇假设一个模型，发现数据对模型的最好匹配，如COBWEB、CLASSIT和AutoClass。第6页，本讲稿共122页6.4 数据挖掘的聚类算法数据挖掘的聚类算法类别类别算法算法分裂/划分方法K-MEANS（K-平均）、K-MEDOIDS算法（K-中心点）、CLARANS算法（基于选择的方法）层次法BIRCH算法（平衡迭代规约和聚类）、CURE算法（代表聚类）、CHAMELEON算法（动态模型）基于密度的
5、方法DBSCAN算法（基于高密度连接区域）、OPTICS算法（对象排序识别）、DENCURE算法（密度分布函数）基于网格的方法STING算法（统计信息网格）、CLIQUE算法（聚类高维空间）、WAVE-CLUSTER算法（小波变换）基于模型的方法统计学方法、神经网络方法表6.9主要的聚类算法的分类第7页，本讲稿共122页6.4 数据挖掘的聚类算法数据挖掘的聚类算法6.4.1聚类分析的概念6.4.2聚类分析中两个对象之间的相异度计算方法6.4.3划分方法6.4.4层次方法*6.4.5基于密度的方法*6.4.6基于网格的方法*6.4.7基于模型的聚类方法*6.4.8模糊聚类算法*第8页，本讲稿共1
6、22页6.4.1 聚类分析的概念聚类分析的概念聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽可能小，类内相似性尽可能大。聚类是一个无监督学习的过程，它与分类的根本区别在于，分类是需要事先知道所依据的数据特征，而聚类是要找到这个数据特征。因此在很多应用中，聚类分析作为一种数据预处理过程，是进一步分析和处理数据的基础。聚类是一种对具有共同趋势和模式的数据元组进行分组的方法，试图找出数据集中的共性和差异并将具有共性的元组聚合在相应的类或段中。第9页，本讲稿共122页6.4.1 聚类分析的概念聚类分析的概念数据挖掘对聚类的典型要求如下：1）可伸缩性：算法能够处理海量的数据库对象。2）处理
7、不同类型属性的能力3）发现具有任意形状的聚类的能力4）输入参数对领域知识的弱依赖性5）处理噪声数据或离群数据的能力6）结果对于输入记录顺序的无关性7）处理高维度数据的能力8）结果的可解释性和可用性9）基于约束的聚类分析能力第10页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法基于内存的聚类算法多选择如下两种有代表性的数据结构：（1）数据矩阵（）数据矩阵（data matrix）数据矩阵用m个变量（也称属性）来表现n个对象，这种数据结构是关系表的形式，或nm维（n个对象m个属性）的矩阵。(6-12)第11页，本讲稿共122页6.4.2
8、聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法（2）相异度矩阵（）相异度矩阵（dissimilatory matrix）存储n个对象两两之间的近似性，通常用一个nn维的矩阵表示。其中d(i,j)是对象i和对象j之间的测量差或相异度，通常它是一个非负的数值。对象i和j之间越相似，其值越接近0；两个对象越不同，其值越大。由于d(i,j)=d(j,i)；且d(i,i)=0，可以得到（6-13）。(6-13)第12页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法数据矩阵的行和列代表不同的实体，也被称为二模矩阵。相
9、异度矩阵的行和列代表相同的实体，也被称为单模矩阵。许多聚类算法都是以相异度矩阵为数据源运行的，如果数据是用数据矩阵的形式存储的，在使用聚类算法之前要将其转化为相异度矩阵。第13页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法计算相异度的常用方法有：区间标度变量计算方法，二元变量计算方法，标称、序数和比例标度计算方法，或这些变量类型的组合来描述对象的相异度计算方法。第14页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法（1）区间标度变量计算方法）区间标度变量计算方法区间标度变量
10、是一个粗略线性标度的连续度量。度量单位的选用将直接影响聚类分析的结果。一般而言，所用的度量单位越小，变量可能的值域就越大，这样对聚类的结果影响就越大。因此为了避免对度量单位选择的依赖，应该对数据进行标准化。标准化度量值试图给所有的变量相等的权重，当没有关于数据的先验知识时，这样做是十分有效的。第15页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法为了实现度量值的标准化，一种方法是将原来的度量值转化为无单位的值。给定一个变量f的变量值，可以进行如下的变换。其中，x1f,x2f,xnf是f的n个度量值，mf是f的平均值，即1）计算均值绝对
11、偏差sf第16页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法均值绝对偏差sf比标准的偏差f对于孤立点具有更好的鲁棒性。在计算均值绝对值偏差时，度量值与平均值的偏差没有被平方，因此孤立点的影响在一点程度上减小了。采用均值绝对偏差的优点在于孤立点的z-score值不会太小，因此孤立点仍可别发现。2）计算标准化的度量值第17页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法标准化后，或者在某些应用中不需要标准化，区间标度变量描述的对象间的相异度（或相似度）通常基于对象间的距离来计算
12、。常用的距离度量方法如下：1）欧几里德距离其中，是两个n维的数据对象。第18页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法2）曼哈顿距离3）明考斯基距离是欧几里德距离和曼哈顿距离的推广。其中，p是一个正整数。p=1时，它表示曼哈顿距离；p=2时，它表示欧几里德距离。第19页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法如果对每个变量根据其重要性赋予一个权重，加权的欧几里德距离可以计算如下：同理，加权也可以用于曼哈顿距离和明考斯基距离。第20页，本讲稿共122页6.4.2 聚
13、类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法例6.7x1=(2,9)和x2=(4,6)表示两个对象，计算x1和x2的欧几里德距离和曼哈顿距离。x1和x2的欧几里德距离x1和x2的曼哈顿距离第21页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法（2）二元变量计算方法）二元变量计算方法一个二元变量只有两个状态：0或1，其中0表示该变量为空，1表示该变量存在。如果所有的二元变量具有相同的权重，可以得到一个两行两列的可能性如表6.10所示。第22页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方
14、法聚类分析中两个对象之间的相异度计算方法表6.10中，q表示对象i和对象j的值都为1的变量的数目；r表示在对象i中值为1，但在该对象j中值为0的变量的数目；s表示在对象i中值为0，但在该对象j中值为1的变量的数目；t表示对象i和对象j的值都为0的变量的数目。变量的总数是p，p=q+r+s+t。对象j10求和对象i1qrq+r0sts+t求和q+sr+tp=q+r+s+t表6.10二元变量的相依表第23页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法评价两个对象i和j之间的相异度标准如下。（1）简单匹配系数（2）Jaccard系数（3）
15、Rao系数第24页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法例6.8二元变量之间的相异度使用实例假设一个病人记录表（表6.11）包含属性姓名、性别、发烧、咳嗽、test-1、test-2、test-3和test-4，其中姓名是对象标识，属性都是二元变量。值Y和P被置为1，值N被置为0。求病人间患病的相似情况。表6.11二元属性的关系变量姓名性别发烧咳嗽test-1test-2test-3test-4ZhangMYNPNNNLiFYNPNPNWangMYNNNNP第25页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计
16、算方法聚类分析中两个对象之间的相异度计算方法根据Jaccard系数公式，三个病人Zhang，Li和Wang两两之间的相异度如下：d(Zhang,Li)=(0+1)/(2+0+1)=0.33d(Zhang,Wang)=(1+1)/(1+1+1)=0.67d(Li,Wang)=(1+2)/(1+1+2)=0.75因此，Wang和Li患有相似的疾病可能性较低，因为他们有着最高的相异度，而Zhang和Li最可能有类似的疾病。第26页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法（3）标称型、序数型和比例标度型变量计算方法）标称型、序数型和比例
17、标度型变量计算方法1）标称变量标称变量是二元变量的推广，它可以具有多于两个状态的值。假设一个标称变量的状态数目是M。这些状态可以用字母、符号，或者一组整数来表示（注意：这些整数只是用于数据处理，并不代表任何特定的顺序）。两个对象i和j之间的相异度可以用简单匹配方法来计算：这里m是匹配的数目，即对i和j取值相同的变量的数目；而p是全部变量的数目。可以通过赋权重来增加m的影响，或者赋给有较多状态的变量的匹配更大的权重。第27页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法2）序数型变量一个离散的序数型变量类似于标称变量，不同在于序数型变量
18、的M个状态是以有意义的序列排序的。序数型变量对记录那些难以客观度量的主观评价是非常有用的。一个连续的序数型变量看起来像一个未知刻度的的连续数据的集合，即值的相对顺序是必要的，而其实际的大小则不重要。将区间标度变量的值域划分为有限个区间，从而将其值离散化，可以得到序数型变量。一个序数型变量的值可以映射为排序。例如，一个变量f有Mf个状态，这些有序的状态定义了一个序列1,Mf。第28页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法处理序数型变量：在计算对象的相异度时，序数型变量的处理与区间标度变量的处理方法类似。假设f是用于描述n个对象的
19、一组序数型变量之一，关于f的相异度计算步骤如下：Step1第i个对象的f值为xif，变量f有Mf个有序的状态，对应于序列1,Mf。用对应的秩rif代替xif，rif1,Mf。Step2既然每个序数变量可以有不同数目的状态，必须经常将每个变量的值域映射到0.0,1.0上，以便每个变量都有相同的权重。这一点可以通过zif代替rif来实现。(6-14)第29页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法Step3相异度的计算可以采用任意一种距离度量方法，采用zif作为第i个对象的f值。第30页，本讲稿共122页6.4.2 聚类分析中两个对
20、象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法3）比例标度型变量比例标度型变量在非线性的标度取正的度量值，例如指数标度，近似地遵循AeBT。计算用比例标度型变量描述的对象之间的相异度，目前有三种方法：采用与处理区间标度变量同样的方法。缺点：标度可能被扭曲。对比例标度型变量进行对数变换。变换得到的值可用区间标度方法计算，对于比例标度型变量可以采用log-log或者其他形式的变换，具体做法取决于定义和应用。将xif看作连续的序数型数据，将其秩作为区间标度的值来对待。第31页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算方法（4）
21、混合类型的变量计算方法）混合类型的变量计算方法一个数据库可能包含区间标度量、对称二元变量、不对称二元变量、标称变量、序数型变量或者比例标度变量。第一种方法：计算用混合类型变量描述的对象之间的相异度方法是将变量按类型分组，对每种类型的变量进行单独的聚类分析。如果这些分析得到兼容的结果，这种做法是可行的。但在实际应用中，这种情况是不大可能的。第二种方法：将所有变量一起处理，只进行一次聚类分析。将不同类型的变量组合在单个的相异度矩阵中，把所有有意义的变量转换到共同的值域区间0.0,1.0上。第32页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方法聚类分析中两个对象之间的相异度计算
22、方法假设数据集包含p不个同类型的变量，对象i和对象j之间相异度d(i,j)定义为：(6-15)其中，如果xif或者xjf缺失，或者xif=xjf=0，且变量f是不对称的二元变量，则指示项，否则。第33页，本讲稿共122页6.4.2 聚类分析中两个对象之间的相异度计算方聚类分析中两个对象之间的相异度计算方法法变量f对i和j之间相异度的计算方式与其具体类型有关。1）如果f是二元变量或标称变量：2）如果f是区间标度变量：3）如果f是序数型或者比例标度型变量：第34页，本讲稿共122页6.4.3 划分方法划分方法给定一个包含n个数据对象的数据库，以及要生成的簇的数目k，一个划分类的算法将数据对象组织为
23、k个划分（kn），其中每个划分代表一个簇。通常会采用一个划分准则（相似度函数）以便在同一个簇中的对象是“相似的”，而不同簇中的对象是“相异的”。第35页，本讲稿共122页6.4.3 划分方法划分方法（1）典型的划分方法：）典型的划分方法：k-平均和平均和k-中心点中心点最著名与最常用的划分方法是k-平均、k-中心点和它们的变种。1）基于簇的重心技术：k-平均方法k-means算法是基于质心的算法。k-means算法以k为参数，把n个对象分为k个簇，以使簇内具有较高的相似度，而簇间的相似度最低。相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。第36页，本讲稿共122页6.4.3 划
24、分方法划分方法k-means聚类算法的具体流程：Step1从数据集中任意选择k个对象C1,C2,Ck作为初始的簇中心；Step2把每个对象分配到与之最相似的聚合。每个聚合用其中所有对象的均值来代表，“最相似”就是指距离最小。对于每个点Vi，找出一个质心Cj，使它们之间的距离d(Vi,Cj)最小，并把Vi分到第j组。Step3把所有的点分配到相应的簇之后，重新计算每个组的质心Cj。Step4循环执行Step2和Step3，直到数据的划分不再发生变化。第37页，本讲稿共122页6.4.3 划分方法划分方法通常采用的准则函数是平方误差准则函数，其定义如下：(6-16)其中，E是数据库中所有对象的平方
25、误差的总和；p是空间中的点，表示给定的数据对象；mi是簇Ci的平均值（p和mi都是多维的）。也就是说，对于每个簇中的每个对象，求对象到其簇中心距离的平方，然后求和。这个准则试图使生成的结果簇尽可能地紧凑和独立。第38页，本讲稿共122页6.4.3 划分方法划分方法输入：k：簇的数目n：数据库对象的个数输出：k个簇，使平方误差最小方法：随机选择k个对象作为初始的代表对象；repeat；根据与每个中心的距离，将每个对象赋给最近的簇；重新计算每个簇的平均值；until不再发生变化。第39页，本讲稿共122页6.4.3 划分方法划分方法例例6.9 k-means算法使用实例算法使用实例设数据对象集合如
26、表6.12所示。簇数目k=2，采用k-means算法对其进行聚类。表6.12pxy11121.21.230.81.240.90.751.30.9611.473383.12.893.23.4102.73.3112.62.9第40页，本讲稿共122页6.4.3 划分方法划分方法第一次迭代：选择p3(0.8,1.2)，p8(3.1,2.8)为簇C1，C2的初始簇代表。所以，将p1分配给p3所属的类C1，同理，将p2、p3、p4、p5、p6分配给p3所属的类C1，将p7、p8、p9、p10、p11分配给p8所属的类C2。第41页，本讲稿共122页6.4.3 划分方法划分方法第二次迭代，用m1(1.03
27、3,1.067)，m2(2.92,3.08)作为簇C1，C2的簇中心，重新对数据进行划分。将p1、p2、p3、p4、p5、p6分类C1，将p7、p8、p9、p10、p11分配给类C2。m1=(1.033,1.067)，m2=(2.92,3.08)，E=1.023第42页，本讲稿共122页6.4.3 划分方法划分方法由于在两次迭代过程中，2个簇中心都不变，所以停止迭代过程。得到的两个聚类分别为：C1=p1,p2,p3,p4,p5,p6C2=p7,p8,p9,p10,p11第43页，本讲稿共122页6.4.3 划分方法划分方法k-means聚类算法尝试找出使平方误差函数值最小的k个划分。当结果簇是
28、密集的，而簇与簇之间区别明显时，它的效果较好。对处理大数据集，该算法是相对可伸缩的和高效率的，复杂度是O(nkt)，n是所有对象的数目，k是簇的数目，t是迭代的次数。第44页，本讲稿共122页6.4.3 划分方法划分方法不足：k-means算法只有在簇的平均值被定义的情况下才能使用。k-means算法的不足之处在于它要多次扫描数据库。k-means算法只能找出球形的类，而不能发现任意形状的类。初始质心的选择对聚类结果有较大的影响。k-means算法对于噪声和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。k-平均算法的变种：k-模方法、EM算法等第45页，本讲稿共122页6.4.
29、3 划分方法划分方法2）基于有代表性的对象的技术：k-中心点法为了避免k-means算法对孤立点的敏感性，不采用簇中对象的平均值作为参照点，可以选用簇中位置最中心的对象，即medoid。这样的划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。这是k-medoids方法的基础。通常采用的准则函数是绝对误差准则函数，其定义如下：(6-17)其中，E是数据库中所有对象的绝对误差的总和；p是空间中的点，表示给定的数据对象；oi是簇Ci中的代表对象。第46页，本讲稿共122页6.4.3 划分方法划分方法k-medoids算法的基本策略：首先随机选择k个对象，每个对象代表一个簇，把
30、其余的对象分别分配给最相似的簇。然后，反复地尝试把每个中心分别用其他非中心来代替，检查聚类的质量是否有所提高。若是，则保留该替换，重复上述过程，直到不再发生变化。为了判定一个非代表对象Orandom是否是当前一个代表对象Oj的好的替代，对于每一个非中心点对象，考虑下面的四种情况：第一种情况：p当前隶属于中心点对象Oj。如果Orandom代替Oj作为一个中心点，且p离Oi最近，ij，那么p被重新分配给Oi。第47页，本讲稿共122页6.4.3 划分方法划分方法第二种情况：p当前隶属于中心点对象Oj。如果Orandom代替Oj作为一个中心点，且p离Orandom最近，那么p被重新分配给Orando
31、m。第三种情况：p当前隶属于中心点对象Oi，ij。如果Orandom代替Oj作为一个中心点，且p离Oi最近，那么对象的隶属不发生变化。第四种情况：p当前隶属于中心点对象Oi，ij。如果Orandom代替Oj作为一个中心点，且p离Orandom最近，那么p被重新分配给Orandom。第48页，本讲稿共122页6.4.3 划分方法划分方法每当重新分配时，平方-误差E所产生的差别对代价函数有影响。因此，如果一个当前的中心点对象被非中心点所代替，就通过代价函数计算平方-误差值所产生的差别。替换的总代价是所有非中心点对象所产生的代价之和。如果总代价是负的，那么实际的平方-误差将会减少，Oj可以被Oran
32、dom代替。如果总代价是正的，则当前的中心点Oj被认为是可接受的，在本次迭代中没有变化发生。第49页，本讲稿共122页6.4.3 划分方法划分方法输入：k：簇的数目n：数据库对象的个数输出：k个簇，使所有对象与其最近代表对象的相异度总和最小方法：随机选择k个对象作为初始的代表对象；repeat；指派每个剩余的对象给离它最近的代表对象所代表的簇；随意地选择一个非代表对象Orandom；计算用Orandom代替Oj的总代价S；如果S0，则用Orandom替换Oj，形成新的k个代表对象的集合；until不发生变化。第50页，本讲稿共122页6.4.3 划分方法划分方法k-medoids算法的过程和k
33、-means算法的不同之处在于：k-medoids算法用类中最靠近中心的一个对象来代表聚类，而k-means算法用质心来代表聚类。k-means算法对噪声非常敏感，因为一个极大的值会对质心的计算带来很大的影响，而k-medoids算法中，通常用中心来代替质心，可以有效地消除该影响。第51页，本讲稿共122页6.4.3 划分方法划分方法PAM（partitioningaroundmedoid,围绕中心点的划分）是最早提出的k-中心点算法之一。它试图对n个对象给出k个划分。最初随机选择k个中心点后，该算法反复地进行，试图找出更好的中心点：对所有可能的对象进行分析，每两个对象的一个对象被看作是中心点
34、，而另一个不是；对可能的各种组合，计算聚类结果的质量。一个对象Oj被可以产生最大平方-误差值减少的对象代替，使在一次迭代中产生的最佳对象的集合为下次迭代的中心点。第52页，本讲稿共122页6.4.3 划分方法划分方法（2）大型数据库中的划分方法：基于选择的）大型数据库中的划分方法：基于选择的k-中心点中心点CLARANS方法方法典型的k-中心点划分算法PAM方法，对小的数据集合非常有效，由于没有良好的可伸缩性，所以不适合答的数据集合。为了处理较大的数据集合，可以采用一个基于选择的方法CLARA（clusteringlargeapplications,CLARA）。CLARA的基本思想是：不考虑
35、整个数据集合，选择实际数据的一小部分作为数据的样本。然后用PAM方法从样本中选择中心点。如果样本是以非随机方式选取，它应当足以代表原来的数据集合。第53页，本讲稿共122页6.4.3 划分方法划分方法改进CLARA的聚类质量和可伸缩性是将CLARANS（clusteringlargeapplicationsbaseduponrandomizedsearch,CLARANS）的采样技术和PAM结合起来。与CLARA不同，CLARANS没有在任一给定时间内局限于任一样本，即不同于CLARA在搜索的每个阶段都有一个固定的样本，CLARANS在搜索的每一步带一定随机性地抽取一个样本。6.56.5数据挖
36、掘的统计分析算法数据挖掘的统计分析算法第54页，本讲稿共122页6.4.4 层次方法层次方法一个层次的聚类方法将数据对象组成一棵聚类的树。根据层次分解是自底向上，还是自顶向下形成，层次的聚类方法可以进一步分为凝聚和分裂层次聚类。一个纯粹的层次聚类方法的聚类质量受限于如下特点：一个合并或分裂一旦执行，就不能修正。（1）凝聚的和分裂的层次聚类（2）BIRCH：平衡迭代归约和聚类（3）ROCK：分类属性层次聚类算法（4）CURE：使用代表点聚类方法（5）Chameleon：动态建模层次聚类第55页，本讲稿共122页（1）凝聚的和分裂的层次聚类凝聚的和分裂的层次聚类1）凝聚的方法首先将每个对象作为单独
37、的一个原子簇然后相继地合并相近的对象或原子簇直到所有的原子簇合并为一个（层次的最上层），或者达到一个终止条件2）分裂的方法首先将所有的对象置于一个簇中在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件第56页，本讲稿共122页（1）凝聚的和分裂的层次聚类凝聚的和分裂的层次聚类四个常用的簇间距离度量方法如下：最小距离：最大距离：平均值的距离：平均距离：(6-18)(6-19)(6-20)(6-21)其中，|p-p|是两个对象p和p之间的距离，mi是簇Ci的平均值，而ni是簇Ci中对象的数目。第57页，本讲稿共122页（2）BIRCH：平衡迭代归约和聚
38、类：平衡迭代归约和聚类利用层次方法的平衡迭代规约和聚类（BalancedIterativeReducingandClusteringusingHierarchies,BIRCH）用于欧几里德向量空间数据，即平均值有意义的数据。该算法通过聚类特征（ClusteringFeature,CF）对簇的信息进行汇总描述，然后对簇进行分类。假设某个簇中包含N个d维的数据点或者数据对象oi，则该簇的聚类特征定义如下：(6-22)其中，N是簇中数据对象的数目，是N个对象的线性和，即SS是对象的平方和，即，它记录了计算聚类和有效利用存储的关键度量。第58页，本讲稿共122页（2）BIRCH：平衡迭代归约和聚类：
39、平衡迭代归约和聚类BIRCH算法的主要目标是使I/O时间尽可能小，原因在于大型数据集通常不能完全装入内存中。BIRCH算法通过把聚类分为多个阶段来达到此目的。首先通过构建CF-树对原数据集进行预聚类，在前面预聚类的基础上进行聚类。CF1CF2CFnCF11CF12CF1n根层第一层图6.10CF树的结构第59页，本讲稿共122页（2）BIRCH：平衡迭代归约和聚类：平衡迭代归约和聚类BIRCH共包含四个阶段：预聚类阶段：扫描整个数据库，构建初始聚类特征树，该树保存在内存中，用简洁的汇总信息或者叶子节点中的子聚类来代表数据点的密集区域。（可选阶段）重新扫描叶子节点项，来构建一个更小的CF-树。采
40、用别的聚类算法，对CF-tree的叶子节点进行聚类。（可选阶段）把前一个阶段中找到的聚类的质心，用作种子来创建最终的聚类。其它数据点根据到这些种子所代表聚类的远近来重新分配到各个聚类中。第60页，本讲稿共122页（2）BIRCH：平衡迭代归约和聚类：平衡迭代归约和聚类BIRCH算法的主要缺点之一就是在初始扫描完成之后，它使用基于质心的方法来形成聚类，当聚类的形状不同或大小各异的情况下，就容易出现问题。BIRCH算法采用直径作为控制参数，所以当类的形状非球形或不同大小的类时，聚类效果不佳。BIRCH算法对数据的输入顺序很敏感，还需要用户手工设置一些参数。第61页，本讲稿共122页（3）ROCK：
41、分类属性层次聚类算法：分类属性层次聚类算法分类属性的层次聚类算法（RobustClusteringusinglinKs），针对具有分类属性的数据使用了链接（指两个对象共同的近邻数目）的概念。对于聚类包含布尔或分类属性的数据，传统聚类算法使用距离函数，然而实验表明对分类数据聚类时，这些距离度量不能产生高质量的簇。大多数聚类算法在进行聚类时只估计点与点之间的相似度；也就是说，在每一步中那些最相似的点合并到一个簇中。这种局部方法很容易导致错误。第62页，本讲稿共122页（3）ROCK：分类属性层次聚类算法：分类属性层次聚类算法ROCK算法采用一种比较全局的观点，通过考虑成对点的邻域情况进行聚类。如果
42、两个相似的点同时具有相似的邻域，那么这两个点可能属于同一个簇而合并。ROCK算法使用一个相似度阈值和共享邻域的概念从一个给定的数据相似度矩阵中首先构建一个稀疏图，然后在这个稀疏图上执行凝聚层次聚类。使用一个优度度量评价聚类。采用随机抽样处理大规模的数据集。ROCK算法在最坏情况下的时间复杂度为O(n2+nmmma+n2logn)，其中mm和ma分别是近邻数目的最大值和平均值，n是对象的个数。第63页，本讲稿共122页（4）CURE：使用代表点聚类方法：使用代表点聚类方法使用代表点的聚类方法（ClusteringUsingRepresentative,CURE）解决了偏好球形和相似大小的问题，在
43、处理孤立点上也更加健壮。CURE选择了位于基于质心和基于代表对象方法之间的中间策略，它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。一个簇的代表点通过如下方式产生：首先选择簇中分散的对象然后根据一个特定的分数或收缩因子向簇中心收缩或移动它们在算法的每一步，有最近距离的代表点对（每个点来自于一个不同的簇）的两个簇被合并第64页，本讲稿共122页（4）CURE：使用代表点聚类方法：使用代表点聚类方法每个簇有多于一个的代表点使得CURE算法可以适应非球形的几何形状。簇的收缩或凝聚可以有助于控制孤立点的影响。因此，CURE算法对于孤立点的处理更加健壮，而且能够识别非球形和
44、大小变化较大的簇。对于大规模数据库，它也具有良好的伸缩性，而且没有牺牲聚类质量。第65页，本讲稿共122页（4）CURE：使用代表点聚类方法：使用代表点聚类方法针对大型数据库，CURE算法采用随机取样和划分两种方法的组合：一个随机样本首先被划分，每个划分在被部分聚类；然后这些聚类结果簇被聚类产生希望的结果。该算法的具体过程如下。Step1源数据对象中抽取一个随机样本S；Step2将样本S分割为一组划分；Step3对每个划分局部地聚类；Step4通过随机取样剔除孤立点。如果一个簇增长的太慢，就去掉它；Step5对局部的簇进行聚类。落在每个新形成的簇中的代表点根据用户定义的一个收缩因子收缩或向簇中
45、心移动。这些点代表了簇的形状；Step6用相应的簇标签来标记数据。第66页，本讲稿共122页（4）CURE：使用代表点聚类方法：使用代表点聚类方法CURE算法特点：CURE算法可以适应非球形的几何形状算法对孤立点的处理更加健壮能够识别非球形和大小变化较大的簇；CURE算法的复杂性为O(n)。CURE从源数据对象中抽取一个随机样本S，基于对此样本的划分进行聚类，如果抽取的样本发生倾斜，则会严重影响聚类结果。第67页，本讲稿共122页（5）Chameleon：动态建模层次聚类：动态建模层次聚类Chameleon是一个在层次聚类中利用动态模型的层次聚类算法，属于凝聚聚类技术。在聚类过程中，如果两个簇
46、之间的互连性和近似度与簇内部对象间的互连性和近似度高度相关，则合并这两个簇。基于动态模型的合并过程有利于自然的和相似的聚类的发现，而且只要定义了相似度函数就可以应用于所有类型的数据。第68页，本讲稿共122页（5）Chameleon：动态建模层次聚类：动态建模层次聚类Chameleon通过两个簇的相对互连度RI(Ci,Cj)和相对接近度RC(Ci,Cj)来决定簇之间的相似度。相对互连度是被簇的内部互联度规范化的两个簇的绝对互连度，如果结果簇中的点之间连接几乎和原来的每个簇一样强，两个簇合并，数学表述为：其中，ECCi,Cj是连接簇Ci和Cj的边之和；类似地，ECCi（或ECCj）是二分簇Ci（
47、或Cj）的割边最小和。(6-23)第69页，本讲稿共122页（5）Chameleon：动态建模层次聚类：动态建模层次聚类相对接近度是被簇的内部互联度规范化的两个簇的绝对接近度，两个簇合并，仅当结果簇中的点之间的接近程度几乎与原来的每个簇一样。数学表述为：其中，|Ci|和|Cj|分别是簇Ci和Cj的大小；(6-24)是连接Ci和Cj节点的边的平均权值；是二分簇Ci（或Cj）的边的平均权值；EC表示割边。第70页，本讲稿共122页（5）Chameleon：动态建模层次聚类：动态建模层次聚类Chameleon算法的思想是：首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类，然后用一个凝聚的层
48、次聚类算法通过反复地合并子类来找到真正的结果簇。Chameleon既考虑了互连性，又考虑了簇间的近似度，特别是簇内部的特征，来确定最相似的子簇。它不依赖于一个静态的，用户提供的模型，能够自动地适应被合并的簇的内部特征。第71页，本讲稿共122页（5）Chameleon：动态建模层次聚类：动态建模层次聚类与CURE和DBSCAN相比：Chameleon在发现高质量的任意形状的聚类方面有更强的能力但是在最坏的情况下，高维数据的处理代价可能对n个对象需要O(n2)的时间第72页，本讲稿共122页6.4.5 基于密度的聚类方法基于密度的聚类方法基于密度的聚类方法将簇看作数据空间中由低密度区域分隔开的高
49、密度对象区域。主要思想：只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类，即对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。基于密度的聚类方法可以用来过滤噪声孤立点数据，发现任意形状的簇。（1）DBSCAN：基于高密度连通区域聚类（2）OPTICS：通过点排序识别聚类结构（3）DENCLUE：基于密度分布函数的聚类第73页，本讲稿共122页（1）DBSCAN：基于高密度连通区域聚类：基于高密度连通区域聚类基于高密度连通区域的聚类（Density-BasedSpatialClusteringofApplicationwithNoise,DBSCAN）将具有
50、足够高密度的区域划分为簇，并可以在带有噪声的空间数据库中发现任意形状的聚类。它定义簇为密度相连的点的最大集合。定义：一个给定对象周围半径内的区域称为该对象的邻域。如果一个对象的邻域至少包含最小数目MinPts的对象，那么该对象称为核心对象。给定一个对象集合D，如果p是在q的邻域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。第74页，本讲稿共122页（1）DBSCAN：基于高密度连通区域聚类：基于高密度连通区域聚类如果存在一个对象链p1,p2,pn，p1=q，pn=p，对piD，1in，pi+1是从pi关于和MinPts直接密度可达的，则对象p是从对象q关于和MinPts密度