聚类分析方法与应用.ppt

6.3.4 DIANA聚类方法 在聚类中，用户能定义希望得到的簇数目作为一个结束条件。同时，它使用下面两种测度方法。 1. 簇的直径：在一个簇中的任意两个数据点都有一个距离（如欧氏距离），这些距离中的最大值是簇的直径。 2. 平均相异度（平均距离）： (6.8) 其中：davg(x,C)表示点x在簇C中的平均相异度，n为簇C中点的个数，d(x, y)为点x与点y之间的距离（如欧式距离）。 6.3.4 DIANA聚类方法 DIANA算法描述： 输入：包含n个数据对象的数据库，终止条件簇的数目k输出：达到终止条件规定的k个簇 处理流程： Step1 将所有对象整个当成一个初始簇； Step2 在所有簇中挑出具有最大直径的簇； Step3 找出所挑簇里与其他点平均相异度最大的一个点放入splinter group，剩余的放入old party中； Step4 在old party里找出到splinter group中点的最近距离不大于到old party中点的最近距离的点，并将该点加入splinter group。 Step5 循环Step2到Step4直到没有新的old party的点分配给splinter group； Step6 splinter group和old party为被选中的簇分裂成的两个簇，与其他簇一起组成新的簇集合。 6.3.5 DBSCAN聚类方法 DBSCAN是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。 下面首先介绍关于密度聚类涉及的一些定义。 6.3.5 DBSCAN聚类方法 定义6.3 对象的? - 邻域：给定对象在半径? 内的区域。 定义6.4 核心对象：如果一个对象的? - 邻域至少包含最小数目MinPts个对象，则称该对象为核心对象。 定义6.5 直接密度可达：给定一个对象集合D，如果p是在q的? - 邻域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。 6.3.5 DBSCAN聚类方法 定义6.6 间接密度可达的：如果存在一个对象链p1, p2, …, pn, p1=q，pn=p，对pi∈D，1≤i≤n， pi+1是从pi关于? 和MitPts直接密度可达的，则对象p是从对象q关于? 和MinPts密度可达的。例如，已知半径? ，MitPts，q是一个核心对象，p1是从q关于? 和MitPts直接密度可达的，若p是从p1关于? 和MitPts直接密度可达的，则对象p是从q关于? 和MitPts间接密度可达的。 6.3.5 DBSCAN聚类方法 定义6.7 密度相连的：如果对象集合D中存在一个对象o，使得对象p和q是从o关于?和MitPts密度可达的，那么对象p和q是关于? 和MinPts密度相连的。 定义6.8 噪声：一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”。 6.3.5 DBSCAN聚类方法 DBSCAN通过检查数据集中每个对象的? - 邻域来寻找聚类。如果一个点p的? - 邻域包含多余MinPts个对象，则创建一个p作为核心对象的新簇。然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。 6.3.5 DBSCAN聚类方法 DBSCAN算法描述： 输入：包含n个数据对象的数据库，半径?，最少数目MinPts 输出：所有达到密度要求的簇 处理流程： Step1 从数据库中抽取一个未处理的点； Step2 IF抽出的点是核心点 THEN找出所有从该点密度可达的对象，形成一个簇； Step3 ELSE抽出的点是边缘点（非核心对象），跳出本次循环，寻找下一个点； Step4 循环Step1到Step3直到所有点都被处理； 6.4 小结 聚类分析作为一种非常重要的数据挖掘模型，在很多领域都广泛应用，本章对聚类方法的基本理论、常见分类做出详细说明，主要描述了基于划分的聚类方法、基于层次的聚类方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法。同时详细介绍了五种聚类方法（包括k-means、k-mediods、AGNES、DIANA以及DBSCAN算法）的算法模型及实例应用。 本章内容结束！ 6.2.4基于网格的聚类方法 常见的基于网格的方法有：STING算法、CLIQUE算法和WAVE-CLUSTER算法。STING利用存