数据挖掘2015最新精品课程完整课件(第15讲)---基于网格的聚类算法剖析

基于网格的聚类方法1基于网格的聚类基本思想是将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合（对于的讨论我们假设属性值是序数的、区间的或者连续的）。每个对象落入一个网格单元，网格单元对应的属性区间包含该对象的值。优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。2STING:统计信息网格STING是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先计算和存储。这些统计信息用于回答查询。3STING:统计信息网格网格中常用参数count-网格中对象数目mean-网格中所有值的平均值stdev-网格中属性值的标准偏差min-网格中属性值的最小值max-网格中属性值的最大值distribution-网格中属性值符合的分布类型。如正态分布、均匀分布、指数分布或者none（分布类型未知）4STING:统计信息网格5STING聚类的层次结构STING:统计信息网格6levelileveli+1leveli+2acellof(i-1)thlevelcorrespondsto4cellsof(i)thlevelSTING:统计信息网格7假设当前层的属性x的统计信息记为n,m,s,min,max,dist,而ni,mi,si,mini,maxi是相对于当前层来说，对应于更低一层的统计参数。那么n,m,s,min,max,dist可以用以下方法计算:distSTING:统计信息网格8STING:统计信息网格当数据加载到数据库时。最底层的单元参数直接由数据计算，若分布类型事先知道，可以用户直接指定，而较高层的分布类型可以基于它对应的低层单元多数的分布类型，用一个阈值过滤过程的合取来计算，若低层分布彼此不同，则高层分布设置为none。高层单元的统计参数可以很容易的从低层单元的参数计算得到。9STING:统计信息网格统计处理思想：使用自顶向下的方法回答空间数据的查询从一个预先选择的层次开始－通常包含少量的单元，为当前层的每个单元计算置信区间不相关的单元不再考虑当检查完当前层，接着检查下一个低层次重复这个过程直到达到底层10STING:统计信息网格算法步骤：1从一个层次开始2对于这一层次的每个单元格，我们计算查询相关的属性值3从计算的属性值及其约束条件中，我们将每一个单元格标注成相关或者不相关4如果这一层是底层，则转到步骤6，否则就行步骤55我们由层次结构转到下一层依照步骤2进行计算6查询结果满足，转到步骤8，否则转到步骤77恢复数据到相关的单元格进一步处理以得到满意结果，转到步骤88停止11STING:统计信息网格——应用STING能够用来帮助各种不同的空间查询。这最常见的请求查询是区域查询。例如查询满足一定条件的区域。查找加利福尼亚州地区的房屋以得到房屋所在区域相关方面数据。查询的对象是房屋，价格是其中的一个属性。区域须满足约束条件：哪些区域面积至少是A,单元地区至少有c栋房屋,至少d%的房屋其价格在a到b之间的置信度为1-t.且mn,.查询语言（sql语言）SELECTREGIONFROMhouse-mapWHEREDENSITYin[c,∞)ANDPRICErange[a,b]WITHpercent[d%,l]ANDAREA(A,+)ANDLOCATIONCalifornia12STING:统计信息网格假设选择第一层作为查询过程的开始点(也可以选择包含少量单元网格的其他层)并假设最底层的网格的属性price近似服从标准分布，高层网格的price属性的分布可能是NONE。假设houses的price在[a,b]的概率p，我们可以求得p置信区间(或者估计其概率范围)[p1,p2],可以检查每个网格单元是否与给定查询相关(p2*nA*C*d%成立?)，若相关，则标记该网格为relevant否则标记为not-relevant.处理层次结构中的下一层。这个处理过程反复进行。直到到达最底层。最后返回满足查询要求的相关单元的区域。查找结束。13STING:统计信息网格优点如下：计算是独立于查询的；有利于并行处理和增量更新；效率很高。STING算法扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是o(n)，其中n是对象的数目。在层次结构建立后，查询处理时间是，这里g是最低层网格单元的数目o(g)，通常远小于n。14STING:统计信息网格缺点如下：如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低层的粒度太粗，将会降低聚类分析的质量；在构建一个父亲单元时没有考虑孩子单元和其相邻单元之间的关系，因此，结果簇的形状是isothetic，即所有的聚类边界或者是水平的，或者是竖直的，没有斜的分界线。尽管该技术有快速的处理速度，但可能降低簇的质量和精确性15CLIQUE:一种类似于Apriori的子空间聚类方法CLICQUE算法是基于网格的空间聚类算法，但它同时非常好地结合了基于密度的聚类算法思想，因此既可以像基于密度的方法发现任意形状的簇，又可以像基于网格的方法处理较大的多维数据集。CLIQUE把每个维划分成不重叠的区间，从而把数据对象的整个嵌入空间划分成单元。它使用一个密度阀值识别稠密单元，一个单元是稠密的，如果映射到它的对象超过该密度阀值16CLIQUE:一种类似于Apriori的子空间聚类方法算法概述：算法需要两个参数值，一个是网格的步长，一具是密度阈值。网格步长决定了空间的划分，而密度阈值用来定义密集网格。聚类思想：算法首先扫描所有网格，当发现第一个密集网格时，便以该网格开始扩展，扩展原则是若一个网格与已知密集区域内的网格邻接并且其自身也是密集的，则将该网格加入到该密集区域中、直到不再有这样的网格被发现为止。算法再继续扫描网格并重复上述过程，直至所有网格被遍历。以自动地发现最高维的子空间，高密度聚类存在于这些子空间中，并且它对元组的输入顺序不敏感，无需假设任何规范的数据分布。它随输入数据的大小线性地扩展，当数据的维数增加时具有良好的可伸缩性。17CLIQUE:一种类似于Apriori的子空间聚类方法CLIQUE识别候选搜索空间的主要策略是使用稠密单元关于维度的单调性。在子空间聚类的背景下，单调性陈述如下：一个k-维(k1)单元c至少有m个点，仅当c的每个(k-1)-维投影(它是(k-1)-维单元)至少有m个点。如下图嵌入数据空间包括3个维：age,salary和vacation。例如，子空间age和salary中的一个二维单元包含m个点，仅当该单元在每个维上的投影都至少包含m个点。1819Salary(10,000)2030405060age543126702030405060age54312670Vacation(week)ageVacation3050=3CLIQUE:一种类似于Apriori的子空间聚类方法相关定义：网格密度：网格中所包含的空间对象的数目。密集网格：给定刻度阈值σ,当网格g的密度≥σ时，网格g是密集网格，否则是非密集网格。网格刻度连通区域：设Grids为一个网格集合，若集合中的所有网格相互邻接且均是密集网格，则称Grid是网格密度连通区域。20CLIQUE:一种类似于Apriori的子空间聚类方法21CLIQUE:一种类似于Apriori的子空间聚类方法以二维空间为例说明该算法：σ=422基于网格的聚类-总结优点:可能是非常有效的。给定每个属性的划分，单遍数据扫描就可以确定每个对象的网格单元和网格单元的计数。此外，尽管潜在的网格单元数量可能很高，但是只需要为非空单元创建网格。这样，定义网格、将每个对象指派到一个单元并计算每个单元的密度的时间复杂度和空间复杂度为O(m)，其中，m是点的个数。如果邻接的、已占据的单元可以有效的访问（例如，通过使用搜索树）则整个聚类过程将非常高效，例如具有O(mlogm)的时间复杂度。缺点：（1）像大多数基于密度的聚类算法一样、基于网格的聚类非常依赖于密度阈值的选择。（太高，簇可能或丢失；太低，本应分开的簇可能被合并）；（2）如果存在不同密度的簇和噪声，则也许不可能找到适合于数据空间所有部分的值；（3）随着维度的增加，网格单元个数迅速增加（指数增长）。即对于高维数据，基于网格的聚类倾向于效果很差。23算法评估聚类评估主要包括如下任务：估计聚类趋势确定数据集中的簇数测定聚类质量24算法评估—估计聚类趋势聚类趋势评估确定给定的数据集是否具有可以导致有意义的聚类的非随机结构。聚类要求数据的非均匀分布。“如何评估数据集的聚类趋势?”直观地看，我们可以评估数据集被均匀分布产生的概率。这可以通过空间随机性的统计检验来实现。为了解释这一思想，我们考虑一种简单但有效的统计量—霍普金斯统计量。霍普金斯统计量是一种空间统计量，检验空间分布的变量的空间随机性。给定数据集D，它可以看做随机变量O的一个样本，我们想要确定O在多大程度上不同于数据空间中的均匀分布。25算法评估—估计聚类趋势霍普金斯统计量-计算（1）均匀地从D的空间中抽取n个点p1,…,pn。也就是说，D的空间中的每个点都以相同的概率包含在这个样本中。对于每个点pi(1≤i≤n),我们找出pi在D中的最邻近，并令xi为pi与它在D中的最近邻之间的距离，即xi=min{dist(pi,v)}(其中v∈D)（2）均匀地从D中抽取n个点q1,…qn.对于每个点qi(1≤i≤n),我们找出qi在D-{qi}中的最邻近，并令yi为qi它在D-{qi}中的最近邻之间的距离，即yi=min{dist(qi,v)}(其中v∈D,v≠qi)（3）计算霍普金斯统计量H:26算法评估—估计聚类趋势“霍普金斯统计量告诉我们数据集D有多大可能遵循数据空间的均匀分布?”如果D是均匀分布的，则∑yi和∑xi将会很接近，因而H大约为0.5。然而，如果D是高度倾斜的，则∑yi将显著地小于∑xi，因而H将接近0。我们的假设是同质假设——D是均匀分布的，因而不包含有意义的簇。非均匀假设(即D不是均匀分布，因而包含簇)是备择假设。我们可以迭代地进行霍普金斯统计量检验，使用0.5作为拒绝备择假设阈值，即如果H0.5，则D不大可能具有统计显著的簇。27算法评估—确定簇数确定数据集中”正确的”簇数是重要的，因为合适的簇数可以控制适当的聚类分析粒度，这可以看做在聚类分析的可压缩性与准确性之间寻找好的平衡点。简单的经验方法：对于n个点的数据集，设置簇数p大约为√n/2.在期望情况下，每个簇大约有√2n个点。肘方法：给点k0,我们可以使用一种像k-均值这样的算法对数据集聚类，并计算簇内方差和—var(k).然后，我们绘制var关于k的曲线。曲线的第一个(或者最显著的)拐点暗示”正确的”簇数。还有一些其他的方法，可以依情况选择合适的方法。28算法评估—测定聚类质量对于测定聚类的质量，我们有几种方法可供选择。一般而言，根据是否有基准可用，这些方法可以可以分成两类。这里，基准是一种理想的聚类，通常由专家构建。如果有基准可用，则外在方法可以使用它。外在方法比较聚类结构和基准。如果没有基准可用，则我们可以使用内在方法，通过考虑簇的分离情况评估聚类的好坏。基准可以看做一种簇标号形式的监督。因此，外在方法又称为监督方法，而内在方法是无监督方法。29算法评估—外在方法外在方法核心：给定基准Cg，对聚类C赋予一个评分Q(C,Cg),一种外在方法是否有效很大程度上依赖于该方法使用的度量Q,度量Q应满足：簇的同质性：要求聚类中的簇越纯，聚类越好簇的完全性：要求对于聚类来说，根据基准如果两个对象属于相同的类别，则他们应该被分配到相同的簇。碎布袋：把一个异种对象放入一个纯的簇中应该比放入碎布袋中受更大的”处罚”。小簇保持性：把小类别划分成小