基于密度的聚类和基于网格的两大聚类算法

数据挖掘

DataMining肖婷112090501

第十章聚类

2基于密度的聚类方法划分和层次方法旨在发现球状簇。他们很难发现任意形状的簇。改进思想，将簇看作数据空间中由低密度区域分隔开的高密度对象区域。这是基于密度的聚类方法的主要策略。基于密度的聚类方法可以用来过滤噪声孤立点数据，发现任意形状的簇。DBSCAN：基于高密度连通区域聚类OPTICS：通过点排序识别聚类结构DENCLUE:基于密度分布函数的聚类

3DBSCAN基于密度的簇是密度相连的点的集合主要思想寻找被低密度区域分离的高密度区域只要临近区域的密度（单位大小上对象或数据点的数目）超过某个阈值，就继续聚类

4DBSCAN两个参数：Eps:邻域的最大半径MinPts:一个核心对象以Eps为半径的邻域内的最小顶点数MinPts=5Eps=1cmpq5DBSCAN密度=制定半径(Eps)内点的个数如果一个对象的Eps邻域至少包含最小数目MinPts个对象，则称该对象为核心对象（Corepoint）如果一个对象是非核心对象,但它的邻域中有核心对象，则称该对象为边界点（Borderpoint

）除核心对象和边界点之外的点是噪声点（Noisepoint

）6DBSCAN7DBSCAN密度可达的（Density-reachable）对于对象p和核心对象q(关于E和MinPts),我们称p是从q(关于E和MinPts)直接密度可达，若对象p在对象q的E邻域内。如果存在一个对象链p1,…,pn,p1=q,pn=p

，pi+1是从pi关于Eps和MinPts

直接密度可达的，则对象p是从对象q关于Eps和MinPts

密度可达的。密度可达性是直接密度可达性的传递闭包，这种关系是非对称的。只有核心对象之间是相互可达的。pqp18DBSCAN密度相连的（Density-connected）如果对象集合D中存在一个对象o，使得对象p和q是从o关于Eps

和MinPts密度可达的，那么对象p和q是关于Eps

和MinPts密度相连的。密度相连性是一个对称的关系。pqo9DBSCAN:算法算法：DBSCAN输入：D-数据对象集合；Eps-邻域或称为半径；MinPts-密度阈值输出：基于密度的簇的集合方法：Step1

读取D中任意一个未分类的对象p；Step2

检索出与p的距离不大于Eps的所有对象Neps(p)；Step3

如果|Neps(p)|<MinPts（即p为非核心对象），则将p标记为噪声，并执行Step1；Step4

否则（即p为核心对象），给Neps(p)中的所有对象打上一个新的类标签newid，然后将这些对象压入堆栈的Seeds中；Step5

让CurrentObject=Seeds.top；然后检索属于Neps(CurrentObject)的所有对象；如果|Neps(CurrentObject)|>MinPts，则剔除已经打上标记的对象，将余下的未分类对象打上类标签newid，然后压入堆栈；Step6

Seeds.pop，判断Seeds是否为空，是，则执行Step1

，否则执行Step5。10DBSCANOriginalPointsClusters特点：抗噪声能处理任意形状聚类11OPTICS：通过点排序识别聚类结构对于真实的，高维的数据集合而言，参数的设置通常是依靠经验，难以确定。绝大多数算法对参数值是非常敏感的：设置的细微不同可能导致差别很大的聚类结果。OPTICS算法通过对象排序识别聚类结构。OPTICS没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇排序。这个次序代表了数据的基于密度的聚类结构。较稠密中的对象在簇排序中相互靠近。12OPTICS簇排序选择这样的对象：即关于最小的E值，它是密度可达的，以便较高密度（较低E值）的簇先完成。对象p的核心距离：使p成为核心对象的最小Ɛ’。如果p不是核心对象，那么p的核心距离没有任何意义。可达距离：对象q到对象p的可达距离是指p的核心距离和p与q之间欧几里得距离之间的较大值。如果p不是核心对象，p和q之间的可达距离没有意义。13OPTICS：通过点排序识别聚类结构算法思路首先检查数据对象集合D中任一个对象的E—邻域。设定其可达距离为“未定义”，并确定其核心距离，然后将对象及其核心距离和可达距离写入文件。如果P是核心对象，则将对象P的E—邻域内的对象N(P)插入到一个种子队列中，包含在种子队列中的对象p’按到其直接密度可达的最近的核心对象q的可达距离排序。种子队列中具有最小可达距离的对象被首先挑选出来，确定该对象的E一邻域和核心距离，然后将其该对象及其核心距离和可达距离写入文件中，如果当前对象是核心对象，则更多的用于扩展的后选对象被插入到种子队列中。这个处理一直重复到再没有一个新的对象被加入到当前的种子队列

中。OPTICS：通过点排序识别聚类结构数据集的排序可以用图形描述，有助于可视化和理解数据集中聚类结构，例如下图是一个简单的二维数据集的可达图。其中三个高斯“凸起”反映数据集中比较稠密的部分。1415OPTICS：通过点排序识别聚类结构Step1：有序种子队列初始为空．结果队列初始为空；Step2：如果所有点处理完毕．算法结束；否则选择一个未处理对象（即不在结果队列中）放人有序种子队列：Step3：如果有序种子队列为空，返回Step2，否则选择种子队列中的第一个对象P进行扩张：Step3.1：如果P不是核心节点．转Step4；否则，对P的E邻域内任一未扩张的邻居q进行如下处理Step3.1.1：如果q已在有序种子队列中且从P到q的可达距离小于旧值，则更新q的可达距离，并调整q到相应位置以保证队列的有序性；Step3.1.2：如果q不在有序种f队列中，则根据P到q的可达距离将其插入有序队列；Step4：从有序种子队列中删除P．并将P写入结果队列中，返回Step3DENCLUE—基于密度分布函数的聚类DENCLUE是一种基于一组密度分布函数的聚类算法。该算法的原理是：每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据点在邻域内的影响，被称为影响函数。数据空间的整体密度(全局密度函数)可以被模拟为所有数据点的影响函数的

总和；聚类可以通过确定密度吸引点(density

attractor)来得到，这里的密度吸引点是全局密度函数的局部最大值。一个点

x

是被一个密度吸引点

x*密度吸引的，如果存在一组点

x0，x1，…,xk，使得x0=x，xk=x*，对

0<i<k，xi-1

的梯度是在

xi的方向上，也就是说xi-1在xi的方向上变化最快。

使用一个步进式爬山过程，把待分析的数据分配到密度吸引点

x*所代表的簇中。16DENCLUE—基于密度分布函数的聚类17DENCLUE—基于密度分布函数的聚类算法步骤：（1）对数据点占据的空间推导密度函数；（2）通过沿密度增长最大的方向(即梯度方向)移动，识别密度函数的局

部最大点（这是局部吸引点），将每个点关联到一个密度吸引点；（3）定义与特定的密度吸引点相关联的点构成的簇；（4）丢弃与非平凡密度吸引点相关联的簇（密度吸引点x’称为非平凡密

度吸引点，如果f*(x’)<η(其中f*是密度函数,η是指定的阀值)；（5）若两个密度吸引点之间存在密度大于或等于η的路径，则合并他们

所代表的簇。对所有的密度吸引点重复此过程，直到不再改变时

算法中止。1819基于密度的聚类方法主要特征：发现任意形状的聚类处理噪声（孤立点数据）一次扫描需要密度参数作为终止条件基于网格的聚类聚类分析的算法有很多，其中一大类的传统算法是基于距离的，这种基于距离的缺点在于只能发现球状的簇、处理大数据集和高维数据集时不够有效，另一方面它能发现的聚类个数常常依赖于用户参数的指定，这对用户来说经常是很困难的。基于网格(dding-based)指将对象空间量化为有限数目的单元，形成一个网格结构，所有聚类都在这个网格结构上进行。20基于网格的聚类基本思想是将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合（对于的讨论我们假设属性值是序数的、区间的或者连续的）。每个对象落入一个网格单元，网格单元对应的属性区间包含该对象的值。优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。21STING:统计信息网格STING是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先计算和存储。这些统计信息用于回答查询。22STING:统计信息网格网格中常用参数count-网格中对象数目mean-网格中所有值的平均值stdev-网格中属性值的标准偏差min-网格中属性值的最小值max-网格中属性值的最大值distribution-网格中属性值符合的分布类型。如正态分布、均匀分布、指数分布或者none（分布类型未知）23STING:统计信息网格24STING聚类的层次结构STING:统计信息网格25levelileveli+1leveli+2

acellof(i-1)thlevelcorrespondsto4cellsof(i)thlevelSTING:统计信息网格26假设当前层的属性x的统计信息记为n,m,s,min,max,dist,而ni,mi,si,mini,maxi是相对于当前层来说，对应于更低一层的统计参数。那么n,m,s,min,max,dist可以用以下方法计算:

distSTING:统计信息网格27STING:

统计信息网格当数据加载到数据库时。最底层的单元参数直接由数据计算，若分布类型事先知道，可以用户直接指定，而较高层的分布类型可以基于它对应的低层单元多数的分布类型，用一个阈值过滤过程的合取来计算，若低层分布彼此不同，则高层分布设置为none。高层单元的统计参数可以很容易的从低层单元的参数计算得到。28STING:统计信息网格统计处理思想：使用自顶向下的方法回答空间数据的查询从一个预先选择的层次开始－通常包含少量的单元，为当前层的每个单元计算置信区间不相关的单元不再考虑当检查完当前层，接着检查下一个低层次重复这个过程直到达到底层29STING:统计信息网格算法步骤：1从一个层次开始2对于这一层次的每个单元格，我们计算查询相关的属性值3从计算的属性值及其约束条件中，我们将每一个单元格标注成相关或者不相关4如果这一层是底层，则转到步骤6，否则就行步骤55我们由层次结构转到下一层依照步骤2进行计算6查询结果满足，转到步骤8，否则转到步骤77恢复数据到相关的单元格进一步处理以得到满意结果，转到步骤88停止30STING:统计信息网格——应用STING能够用来帮助各种不同的空间查询。这最常见的请求查询是区域查询。例如查询满足一定条件的区域。查找加利福尼亚州地区的房屋以得到房屋所在区域相关方面数据。查询的对象是房屋，价格是其中的一个属性。区域须满足约束条件：哪些区域面积至少是A,单元地区至少有c栋房屋,至少d%的房屋其价格在a到b之间的置信度为1-t.且m<n,.

查询语言（sql语言）SELECTREGIONFROMhouse-mapWHEREDENSITYin[c,∞)ANDPRICErange[a,b]WITHpercent[d%,l]ANDAREA(A,+)ANDLOCATIONCalifornia

31STING:统计信息网格假设选择第一层作为查询过程的开始点(也可以选择包含少量单元网格的其他层)并假设最底层的网格的属性price近似服从标准分布，高层网格的price属性的分布可能是NONE。假设houses的price在[a,b]的概率p，我们可以求得p置信区间(或者估计其概率范围)[p1,p2],可以检查每个网格单元是否与给定查询相关(p2*n>A*C*d%成立?)，若相关，则标记该网格为relevant否则标记为not-relevant

.处理层次结构中的下一层。这个处理过程反复进行。直

到到达最底层。最后返回满足查询要求的相关单元的区域。

查找结束。

32STING:统计信息网格优点如下：计算是独立于查询的；有利于并行处理和增量更新；效率很高。STING算法扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是o(n)，其中n是对象的数目。在层次结构建立后，查询处理时间是，这里g是最低层网格单元的数目o(g)，通常远小于n。33STING:统计信息网格缺点如下：如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低层的粒度太粗，将会降低聚类分析的质量；在构建一个父亲单元时没有考虑孩子单元和其相邻单元之间的关系，因此，结果簇的形状是isothetic，即所有的聚类边界或者是水平的，或者是竖直的，没有斜的分界线。尽管该技术有快速的处理速度，但可能降低簇的质量和精确性34CLIQUE:一种类似于Apriori的子空间聚类方法CLICQUE算法是基于网格的空间聚类算法，但它同时非常好地结合了基于密度的聚类算法思想，因此既可以像基于密度的方法发现任意形状的簇，又可以像基于网格的方法处理较大的多维数据集。CLIQUE把每个维划分成不重叠的区间，从而把数据对象的整个嵌入空间划分成单元。它使用一个密度阀值识别稠密单元，一个单元是稠密的，如果映射到它的对象超过该密度阀值35CLIQUE:一种类似于Apriori的子空间聚类方法算法概述：算法需要两个参数值，一个是网格的步长，一具是密度阈值。

网格步长决定了空间的划分，而密度阈值用来定义密集网格。

聚类思想：算法首先扫描所有网格，当发现第一个密集网格时，便以该网格开始扩展，扩展原则是若一个网格与已知密集区域内的网格邻接并且其自身也是密集的，则将该网格加入到该密集区域中、直到不再有这样的网格被发现为止。算法再继续扫描网