数据仓库与数据挖掘原理及应用(第二版) 教学课件 ppt 作者 王丽珍 周丽华 陈红梅 第7章

1,第七章 聚类分析,2,第七章 目录,7.1 概述 7.2 K均值算法 7.3 BIRCH算法 7.4 DBSCAN算法 7.5 STING算法 7.6 EM算法 7.7 本章小结,3,7.1 概述,7.1.1 聚类概念 7.1.2 相似性测度 7.1.3 聚类过程 7.1.4 聚类算法分类,4,7.1.1聚类概念(1),聚类是将物理或抽象对象的集合分成相似的对象类的过程。使得同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性。 聚类可形式描述为： =o1, o2, , on表示一个对象集合， oi表示第i个对象，i=1, 2,n； Cx表示第x个簇，Cx，x=1，2，k； Similarity(oi, oj)表示对象oi与对象oj之间的相似度；,5,1） 2）对于 ， 有 3）,7.1.1聚类概念(2),若各簇Cx是刚性聚类结果，则各Cx需满足如下条件：,6,7.1.2 相似性测度,1）距离相似性度量。距离越近越相似。 2）密度相似性度量。密度越相近，相似性越高。 3）连通性相似性度量。 4）概念相似性度量。共性（比如共享最近邻）越多越相似。,7,7.1.3 聚类过程,典型聚类过程：,聚类分析的三要素是相似性测度、聚类准则和聚类算法。,8,7.1.4 聚类方法分类(1),1）划分式聚类算法（partitioning method）：预先指定聚类数目或聚类中心，通过反复迭代运算，逐步优化准则函数的值，当准则函数收敛时，得到最终聚类结果。 例：k均值算法、k中心点算法及它们的变种。 2）层次聚类算法（hierarchical method）：将数据对象组织成一棵聚类树，使用数据的联接规则，透过一种架构方式，反复将数据进行分裂或聚合，以形成一个层次序列的聚类问题解。 例：BIRCH、ROCK和Chameleon 等。,9,3）基于密度的聚类算法（density-based method）：通过数据密度来发现簇，将簇看作是数据空间中被低密度区域（代表噪声）分割开的稠密对象区域。 例：DBSCAN、OPTICS、DENCLUE。 4）基于网格的聚类算法（gridbased method）：使用一种多分辨率的网格数据结构，将对象空间量化为有限数目的单元，形成网格结构，所有的聚类操作都在网格上进行，从而获得较快的处理速度。 例：STING、WaveCluster。,7.1.4 聚类方法分类(2),10,5）基于模型的聚类算法（model-based method）：基于“数据根据潜在的混合概率分布生成”假设，为每个簇假定一个模型，并寻找数据对给定模型的最佳拟合。这类算法通过构建反映数据点空间分布的密度函数来定位簇，能考虑“噪声”数据和离群点的影响，鲁棒性较好。 例：EM 、COBWEB 、SOM。,7.1.4 聚类方法分类(3),11,7.2 K均值算法,7.2.1 误差平方和准则 7.2.2 K均值算法,12,7.2.1误差平方和准则,若Nx是第Cx个簇中的对象数目，mx是这些对象的均值，即 误差平方和准则J 就是所有簇的簇中各个对象与均值间的误差平方和之和，即： J 度量了用k个聚类中心m1,m2,mk代表k个簇C1,C2,Ck时所产生的总的误差平方和。对于不同的聚类，J的值不同，使J 值极小的聚类是误差平方和准则下的最优结果。,13,7.2.2 K均值算法(1),核心思想是：首先选定k个初始聚类中心，根据最小距离原则将每个数据对象分配到某一簇中，然后不断迭代计算各个簇的聚类中心并依新的聚类中心调整聚类情况，直至收敛（J 值不再变化）。 当存在噪声和离群数据时，k中心点算法比k均值算法效果好，但是k中心点聚类算法的执行代价比k均值算法高。 k均值算法描述如下： 算法：k均值聚类算法（D，k） 输入：数据对象集合D，簇数目k 输出：k个簇的集合,14,步骤： （1） 从D中随机选取k个不同的数据对象作为k个簇C1，C2，Ck的中心m1，m2，mk （2） repeat （2.1）for D中每个数据对象o （2.1.1） 寻找i， （2.1.2）将o分配给簇Ci （2.2）for 每个簇计算 计算,7.2.2 K均值算法(2),15,/计算新的聚类中心， 为当前簇 中的对象数目 3）计算平方误差 3. Until J 不再发生变化,7.2.2 K均值算法(3),16,7.3 BIRCH算法,7.3.1 聚类特征 7.3.2 CF树 7.3.3 CF树的构造 7.3.4 BIRCH算法,17,7.3.1 聚类特征(Clustering Feature，CF),聚类特征是一个三元组，概括了对象簇的信息。如果某个簇包含N个d维的数据点oi，则CF=（N，LS，SS），其中N是簇中点的数目，LS是N个点的线性和（即 ），SS是数据点的平方和（即 ）。 例7.2 假定在簇C1中有两个点（1，2),(2，1），簇C2中有两个点（7，8),（8，9），簇C3由C1和C2合并而成。则： CF1=（2，（1+2，2+1），（12+22，22+12）=（2，（3，3），（5，5） CF2=（2，（7+8，8+9），（72+82，82+92）=（2，（15，17），（113，145） CF3=（2+2，（3+15，3+17），（5+113，5+145）=（4，（18，20），（118，150）,18,CF树是一棵高度平衡的树，它有两个参数：分支因子B和阈值T。每个非叶节点最多包含B个形如CFi，childi（i=1，2，B）的条目，childi是指向第i个孩子的指针，CFi是由这个孩子所代表的子簇的聚类特征。一个非叶节点代表了一个簇，这个簇由该节点的条目所代表的所有子簇构成。一个叶节点最多包含L个形如CFi（i=1，2，L）的条目。每个叶节点也代表了一个簇，这个簇也由该叶节点的条目所代表的所有子簇构成，这些子簇的直径必须小于阈值T。,7.3.2 CF树,19,CF树的构造过程就是对象不断插入的过程。 过程如下： 1）识别合适的叶节点：从根节点开始逐层下降，递归查找最近的孩子，直至叶节点。 2）修改叶节点：假设叶节点中与Ent最近的条目是Li，检测Li与Ent合并的簇直径是否小于阈值，若小于，则更新Li的CF；否则为Ent创建一个新条目。如果叶节点有空间存放这个新条目，则存储，否则分裂该叶节点。分裂时选择相距最远的条目作为种子，其余条目按最近距离分配到两个新的叶节点中。,7.3.3 CF树的构造(1),20,3）修改到叶节点的路径：将Ent插入一个叶节点后，更新每一个非叶节点的CF信息。如果不存在分裂，只需要进行加法运算；如果发生分裂，则在其父节点上要插入一个非叶节点来描述新创造的叶节点。修改过程重复进行，直至根节点。 4）在每次分裂之后跟随一个合并步。如果一个叶节点发生分裂，并且分裂过程持续到非叶节点Nj，扫描Nj，找出两个最近的条目。如果不对应于刚分裂产生的条目，则试图合并这些条目及其对应的孩子节点。如果两个孩子节点中的条目多于一页所能容纳的条目，则将合并结果再次分裂。,7.3.3 CF树的构造(2),21,BIRCH算法采用了一种多阶段聚类技术，初始的微聚类阶段采用层次聚类算法，后来的宏聚类阶段采用其他聚类算法，所以它是层次聚类和其他聚类算法的集成。 BIRCH聚类算法由4个阶段构成： 阶段一：扫描数据库，构造一棵能够存放于内存中的CF树。 阶段二（可选）：压缩CF树（T增值，然后重新插入叶节点项。 阶段三：选用一个聚类算法对CF树的叶节点聚类，把稀疏的簇当做离群点删除，把稠密的簇合并为更大的簇。 阶段四（可选）：精化聚类结果。,7.3.4 BIRCH算法,22,7.4 DBSCAN算法,7.4.1 相关概念 7.4.2 DBSCAN算法,23,1. 数据对象p的-邻域N(p) 以p为圆心，以为半径的圆形区域内的数据对象的集合，即： N(p)=q|qD d(p，q) （7.13） 其中，D是数据对象集合，d(p，q)是对象p与对象q间的距离。 显然，如果qN(p)，则p N(q)。对象p的-邻域N(p)如图7.4所示。,7.4.1 相关概念(1),24,2. 核心对象 如果对象p的-邻域至少包含最小数目MinPts个对象，则称p为核心对象。图7.4，如果MinPts=3，则p为核心对象。 3. 直接密度可达 给定一个对象集合D，如果p在q的-邻域内，而q是一个核心对象，则称对象p是从对象q出发关于和MinPts直接密度可达的。,7.4.1 相关概念(2),直接密度可达关系不对称，即如果p从q出发是直接密度可达的，那么q是核心对象，但是p可能不是核心对象。如图7.5所示：,25,4. 密度可达 如果存在一个对象链p1，p2，pn，p1=q，pn=p，对于piD（1in），pi+1是从pi出发关于和MinPts直接密度可达的，则对象p是从对象q 出发关于和MinPts密度可达的。,7.4.1 相关概念(3),pi（1in-1）是核心对象，pi+1在pi的-邻域中。密度可达关系也不对称。如果p是从q出发关于和MinPts密度可达的，那么q是核心对象，但是p可能不是核心对象。如图7.6所示：,26,5. 密度相连 如果存在对象oD，使对象p和q都是从o出发关于和MinPts密度可达的，那么对象p到q是关于和MinPts密度相连的。 密度相连关系是对称的。如图7.7所示。,7.4.1 相关概念(4),27,6. 基于密度的簇 基于密度的簇是基于密度可达性的最大的密度相连对象的集合。即簇C是满足如下条件的D的非空子集： 1）连通性：对于任意的p，qC，有p与q是关于和MinPts密度相连的。 2）极大性：对于任意的p，q，如果pC，并且q是从p出发关于和MinPts密度可达的，则qC。 D中不包含在任何簇中的对象是噪声。即Noise=p|pD pCi，1ik。k是簇的数目。,7.4.1 相关概念(5),28,定理7.1 给定,MinPts及数据对象集合D，满足如下条件的D的非空子集O是关于和MinPts的簇： O=o|p,oD, ,o是从p出发关于和MinPts密度可达的 证明： 连通性。 对于任意的r , tO，因为r，t都是从p出发关于和 MinPts密度可达的，所以，r与t是关于和MinPts密度相连的。,7.4.1 相关概念(6),29, 极大性。 对于任意的r、t，因为 如果rO，则r是从p出发关于和MinPts密度可达的。 如果t是从r出发关于和MinPts密度可达的，则t是从p出 发关于和MinPts密度可达的。 所以 tO。,7.4.1 相关概念(7),30,定理7.2 给定，MinPts及数据对象集合D，某个关于和MinPts的簇C等于满足如下条件的D的非空子集O： O=o| pC , ,oD , o是从p出发关于和MinPts密度可达的 证明： C O 对于任意qC，因为pC,所以，根据簇的连通性，p与q是关于和MinPts密度相连的，即存在r满足p与q都是从r出发关于和MinPts密度可达的。 又因为|N(p)|Minpts,所以，r是从p出发关于和MinPts密度可达的，q是从p出发关于和MinPts密度可达的，即qO,7.4.1 相关概念(8),31, O C 对于任意qO，因为q是从p出发关于和MinPts密度可达的。又因为 pC 所以，根据簇的极大性，qC。 定理7.