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

算法评估—估计聚类趋势 “霍普金斯统计量告诉我们数据集D有多大可能遵循数据空间的均匀分布?”如果D是均匀分布的，则∑yi和∑xi将会很接近，因而H大约为0.5。然而，如果D是高度倾斜的，则∑yi将显著地小于∑xi，因而H将接近0。 我们的假设是同质假设——D是均匀分布的，因而不包含有意义的簇。非均匀假设(即D不是均匀分布，因而包含簇)是备择假设。我们可以迭代地进行霍普金斯统计量检验，使用0.5作为拒绝备择假设阈值，即如果H0.5，则D不大可能具有统计显著的簇。 * 算法评估—确定簇数 确定数据集中”正确的”簇数是重要的，因为合适的簇数可以控制适当的聚类分析粒度，这可以看做在聚类分析的可压缩性与准确性之间寻找好的平衡点。 简单的经验方法：对于n个点的数据集，设置簇数p大约为√n/2.在期望情况下，每个簇大约有√2n个点。 肘方法：给点k0,我们可以使用一种像k-均值这样的算法对数据集聚类，并计算簇内方差和—var(k).然后，我们绘制var关于k的曲线。曲线的第一个(或者最显著的)拐点暗示”正确的”簇数。 还有一些其他的方法，可以依情况选择合适的方法。 * 算法评估—测定聚类质量 对于测定聚类的质量，我们有几种方法可供选择。一般而言，根据是否有基准可用，这些方法可以可以分成两类。这里，基准是一种理想的聚类，通常由专家构建。 如果有基准可用，则外在方法可以使用它。外在方法比较聚类结构和基准。如果没有基准可用，则我们可以使用内在方法，通过考虑簇的分离情况评估聚类的好坏。基准可以看做一种簇标号形式的监督。因此，外在方法又称为监督方法，而内在方法是无监督方法。 * 算法评估—外在方法 外在方法核心：给定基准Cg，对聚类C赋予一个评分Q(C,Cg),一种外在方法是否有效很大程度上依赖于该方法使用的度量Q,度量Q应满足： 簇的同质性：要求聚类中的簇越纯，聚类越好 簇的完全性：要求对于聚类来说，根据基准如果两个对象属于相同的类别，则他们应该被分配到相同的簇。 碎布袋：把一个异种对象放入一个纯的簇中应该比放入碎布袋中受更大的 ”处罚”。 小簇保持性：把小类别划分成小片比将大类别划分成小片更有害。 例子：Bcubed精度和召回率 见P318 * 算法评估—内在方法 当没有数据集的基准可用时，我么必须使用内在方法来评估聚类的质量。一般而言，内在方法通过考察簇的分离情况和簇的紧凑情况来评估聚类。许多内在方法都利用数据集的对象之间的相似性度量。 轮廓系数：对于n个对象的数据集D，假设D被划分成k个簇C1,…,CK.对于每个对象o与o所属的簇的其他对象之间的平均距离y(o).类似地，b(o)是o到不属于o的所有粗的最小平均距离。假设o€Ci(1≤i≤k),则 y(o)=(∑dist(o,o’))/(|Ci|-1) (o’€Ci,o≠o’) 而b(o)=min{∑dist(o,o’)/|Ci|} (Cj:1≤j≤k,j≠i) 对象o的轮廓系数定义为s(o)=(b(o)-y(o))/max{y(o),b(o)}，其值在-1和1之间。 y(o)反应o所属的簇的紧凑性，值越小越好；b(o)捕获o与其它簇的分离程度， 值越大越好。当s(o)的值接近1时，包含o的簇是紧凑的并且远离其它簇，可取情况；当其值为负时，这意味在期望情况下，o距离其它簇的对象比距离与自己同在簇的对象更近，不可取情况。 * * OPTICS：通过点排序识别聚类结构 数据集的排序可以用图形描述，有助于可视化和理解数据集中聚类结构，例如下图是一个简单的二维数据集的可达图。其中三个高斯“凸起”反映数据集中比较稠密的部分。 * * OPTICS：通过点排序识别聚类结构 Step 1：有序种子队列初始为空．结果队列初始为空 ； Step 2：如果所有点处理完毕．算法结束；否则选择一个未处理对象（即不在结果队列中）放人有序种子队列： Step 3：如果有序种子队列为空，返回Step 2，否则选择种子队列中的第一个对象P进行扩张： Step 3.1：如果P不是核心节点．转Step 4；否则，对P 的E邻域内任一未扩张的邻居q 进行如下处理 Step 3.1.1：如果q已在有序种子队列中且从P到 q的可达距离小于旧值，则更新q的可达距离，并调整q到相应位置以保证队列的有序性； Step 3.1.2：如果q不在有序种f队列中，则根据P 到q的可达距离将其插入有序队列； Step 4：从有序种子队列中删除P．并将P写入结果队列中，返回Step 3 DENCLUE—基于密度分布函数的聚类 DENCLUE是一种基于一组密度分布函数的聚类算法。该算法的原理是： 每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据点在邻域内的影响，被称为影响函