第10章 聚类方法(续)

第10章聚类方法10.4基于密度的聚类算法很多算法都使用距离来描述数据之间的相似性，但对于非凸数据集，只用距离来描述是不够的。此时可用密度来取代距离描述相似性，即基于密度的聚类算法。它不是基于各种各样的距离，所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。10.4.1DBSCAN算法DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）算法是一种性能优越的基于密度的空间聚类算法。它的基本思想是，如果一个点p和另一个点q是密度相连的，则p和q属于同一个簇。1.相关概念定义10.6以数据集D中一个点p为圆心，以ε为半径的圆形区域内的数据点的集合称为p的ε-邻域，用N(p)表示，即：N(p)={q|qD∧dist(p，q)≤ε}点p的ε-邻域定义10.7给定一个参数MinPts，如果数据集D中的一个点p的ε-邻域至少包含MinPts个点（含点p自身），则称p为核心点。在图10.36中，如果MinPts=7，则p为核心点（核心点用实心圆点表示）。p为核心点定义10.8给定数据集D中的两个点p、q，如果q在p的ε-邻域内，而p是一个核心点，则称点q是从p出发直接密度可达的。在图10.36中，qN(p)，如果p是一个核心点，则q是从p出发直接密度可达。p为核心点，q是从p出发直接密度可达定义10.9对于给定的ε和MinPts，如果数据集D中存在一个点链p1、p2、…、pn，p1=q，pn=p，对于piD（1≤in），pi+1是从pi出发直接密度可达的，则点p是从点q出发密度可达的。点p是从点q密度可达的定义10.10对于给定的ε和MinPts，如果数据集D中存在如果存在点oD，使点p和q都是从o出发密度可达的，那么点p到q是密度相连的。密度相连关系是对称的。如图10.38所示，p到q是密度相连的，则q到p是密度相连的。p到q是密度相连的定义10.12数据集D中不是核心点，但落在某个核心点的邻域内的点称为边界点。边界点可能落在多个核心点的邻域内，边界点为稠密区域边缘上的点。数据集D中不是核心点也不是边界点的点称为噪声点，噪声点不属于任何簇，它属于稀疏区域中的点。例如，如图10.39所示，MinPts=4，用实心圆点表示核心点，用空心圆点表示边界点，用方形点表示噪声点。核心点、边界点和噪声点2.DBSCAN算法DBSCAN算法基本思想是：首先选取一个未标记类别的核心点，并创建一个新簇；然后，寻找所有从该核心点出发关于ε和MinPts密度可达的点，并标记为该簇。重复这个过程，直至处理完所有点，即没有未标记簇的核心点。输入：数据集D，邻域半径ε，最小点数MinPts输出：关于（ε，MinPts）的所有簇的集合方法：其过程描述如下：do{从数据集D中抽取一个未处理过的点p;if(p是核心点)找出所有从p出发关于（ε，MinPts）密度可达的点，形成一个簇;elsep是边界点或噪声点（非核心点），跳出本次循环，寻找下一点；}until(所有点都被处理);【例10.11】有如表10.14所示的数据集，其在二维空间中的分布情况如图10.40所示。用户输入ε=1，MinPts=4，采用DBSCAN算法进行聚类的过程如下。序号属性1属性2序号属性1属性2110741240851301902411101252111426311213散点图步骤选择的点在ε邻域中点的个数通过计算可达点而找到的新簇112无222无333无445簇C1：{1，3，4，5，9，10，12}553已在一个簇C1中663无775簇C2：{2，6，7，8，11}882已在一个簇C2中993已在一个簇C1中10104已在一个簇C1中，11112已在一个簇C2中12122已在一个簇C1中DBSCAN算法的优点是基于密度定义，相对抗噪音，能处理任意形状和大小的簇。其缺点是对参数（ε，MinPts）敏感，当簇的密度变化太大时，会产生较大误差。10.4.2OPTICS算法OPTICS并不显示的产生结果簇，而是为聚类分析生成一个增广的簇排序（比如以可达距离为纵轴，样本点输出次序为横轴的坐标图），这个排序代表了各样本点基于密度的聚类结构。它包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类，换句话说，从这个排序中可以得到基于任何参数ε和MinPts的DBSCAN算法的聚类结果。定义10.13设o是数据集D中一个点，ε为距离，MinPts是一个自然数，MinPts-dist(o)是o到其最邻近的MinPts个邻接点的最大距离，则o的核心距离为：o的核心距离=无定义若o不是核心点若o是核心点MinPts-dist(o)也就是说，对于点o，它的核心距离为使o成为核点的最小ε'。如果o不是核心对象，则o的核心距离没有定义。定义10.14设点p、o为数据集D中的点，ε为距离，MinPts是一个自然数，点p关于点o的可达距离定义为：p关于o的可达距离=无定义若o不是核心点若o是核心点MAX{o的核心距离，dist(o，p)}也就是说，点p关于点o的可达距离是指o的核心距离和o与p之间欧几里得距离之间的较大值。如果o不是核心对象，o和p之间的可达距离没有意义。例如，如图10.41所示，设ε=6，MinPts=5。显然o为核心点，点o到最邻近的5个点（含自身）的最大距离为ε‘=3，所以核心点o的核心距离为3。点p关于o的可达距离=MAX{3，dist(o，p)}=3（点p属于o的最邻近的MinPts个点之一）。点q关于o的可达距离=MAX{3，dist(o，q)}=dist(o，q)（点q属于o的邻域内的点，但不属于最邻近的MinPts个点之一）。OPTICS算法产生了数据集的排序，并为每个点存储了核心距离和相应的可达距离。也就是说，OPTICS的结果是将所有点按照其直接密度可达的最近的核心点的可达距离进行排序，称为簇排序。然后可以基于OPTICS产生的排序信息来提取簇，对于从该排序中提取小于ε的每个距离值ε'的聚类已经足够。基于数据集的簇排序可以图形化的描述，有助于理解。例如，图10.42是一个简单的二维数据集的可达性图，它给出了如何对数据结构化和聚类的一般观察。数据点连同它们各自的可达距离按簇顺序绘出。从中看到，核心距离ε'比ε会生成更好的聚类结果。【例10.12】有如表10.16所示的数据集，在二维空间中的分布情况如图10.43所示。当设置ε=2，MinPts=4时，采用OPTICS算法进行聚类的过程如下：点名称属性1属性2点名称属性1属性2a23j76b24k85c14l1002d13m820e22n819f32o718g87p717h86q821i77散点图（1）求各个点的可达距离，其结果如表10.17所示，表中序号指出输出次序，对于未输出的点，表示该点的可达距离没有定义，用OPTICS簇次序图表示，其结果如图10.44所示，其中横坐标对应点的簇次序，纵坐标对应点的可达距离。序号点名称可达距离序号点名称可达距离1a1.09k1.412e1.010i1.413b1.011h1.414d1.012n2.05c1.013q2.06f1.014o2.07g1.4115m2.08j1.41OPTICS中的簇次序图（2）从图中看到，根据可达距离的大小可以分成3个簇，即{a，e，b，d，c，f}，{g，j，k，i，h}，{n，q，o，m}。这和DBSCAN算法设置ε=1.0，MinPts=4时的聚类结果是相同的。OPTICS中的簇次序图（3）通过分析簇次序图还能直接得到这样的结果：当参数ε=1.5，MinPts=4时的聚类结果只有两个簇，即{a，e，b，d，c，f}，{g，j，k，i，h}，也就是说，在OPTICS簇次序图中所有可达距离Y值小于1.5的样本点都不加区分地划入一个簇中这和DBSCAN算法设置ε=1.5，MinPts=4时的聚类结果是相同的。不在这两个簇中的其他点被认为是离群点。OPTICS中的簇次序图OPTICS算法的特点如下：①对于真实的，高维的数据集合而言，绝大多数算法对参数值是非常敏感的，参数的设置通常是依靠经验，难以确定。而OPTICS算法可以帮助找出合适的参数。②OPTICS算法通过对象排序识别聚类结构。③OPTICS没有显式地产生一个数据类簇，它为自动和交互的聚类分析计算一个簇排序。这个次序代表了数据的基于密度的聚类结构。10.5基于网格的聚类算法基于网格的聚类方法使用一种多分辨率的网格数据结构，将对象空间量化为有限数目的单元，形成网格结构，所有的聚类操作都在网格上进行。其处理速度独立于数据对象的个数，仅依赖于量化空间中每一维的单元个数，因此处理速度快。10.5.1STING算法STING（StatistaicalINformationGrid）算法是基于空间数据挖掘的算法，将数据空间区域划分为矩形单元，并且对应于不同级别的分辨率，存在着不同层次的矩形单元，高层的每个单元被分为多个低一层的单元。每个网络单元的统计信息被预先计算和存储，供处理和查询使用。STING结构中的结点通常每个单元具有以下统计信息方面的参数：①单元内的对象数目count；②单元内所有对象的均值mean；③单元内对象属性的标准差stdev；④单元内对象属性的最小值min；⑤单元内对象属性的最大值max；⑥单元内对象属性值遵循的分布类型distr，可以是正态的、均匀的、指数的或NONE（分布未知）。较高层单元的参数可以很容易地从低层单元的参数计算得到。设count、mean、stdev、min、max和distr分别表示当前单元的参数，与该单元相对应的低层单元的参数分别用counti、meani、stdevi、mini、maxi和distri表示，则count、mean、stdev、min、max和distr可以按如下方式计算：iicountcountcountcountmeanmeaniii222)(meancountcountmeanstdevstdeviiii……在完成一个有关空间信息的查询时，先将查询转化为统计信息，然后使用STING算法在层次结构中查找相关的统计参数。STING算法如下：输入：层次网格结构T，查询要求Q输出：满足查询要求的相关单元的区域方法：其过程描述如下：（1）从层次结构T的一个层次开始;（2）对于这一层次的每个单元，计算查询Q相关的属性值;（3）从计算的属性值及其约束条件中，将每一个单元标注成相关或者不相关;（4）如果这一层是底层，则转到（6），否则就转（5）;（5）由层次结构转到下一层依照（2）进行计算;（6）若查询结果满足，转到（8），否则转到（7）;（7）恢复数据到相关的单元格进一步处理以得到满意结果，转到（8）;（8）算法结束。【例10.13】有如图10.46所示的层次网格结构，共3层，第3层中每个单元的面积为10m2，第2层和第3层中每个单元的count=4。采用STING算法查询某个房屋的占地面积的过程如下。从第一层开始，假设找到该房屋的相关单元有3个，所有相并单元用阴影表示，再在第2层中找到相关单元共10个，继续在第3层中找到相关单元共28个，最后求出面积为28×10共280m2。STING算法具有如下优点：①存储在每个单元的统计信息是不依赖于具体的查询的，所以基于网格的计算独立于查询。②网格层次结构有利于增量更新和并行处理。③执行效率高，扫描一遍数据集计算出每个单元的统计信息，产生聚类的时间复杂度是O(n)，n是数据集中对象的个数。层次结构建成后，查询处理时间是O(k)，k是最低层网格单元的数目，通常kn。STING算法的缺点如下：①如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低层的粒度太粗，将会降低聚类分析的质量。②在构建一个父单元时没有考虑孩子单元和其相邻单元之间的关系，因此，结果簇的边界或者是水平的，或者是竖直的，没有斜的分界线。③尽管该技术有快速的处理速度，但可能降低簇的质量和精确性。10.5.2WaveCluster算法Wa