聚类分析综述.ppt

基于网格方法 基于网格方法将对象空间划分为有限数目的单元以形成网格结构。所有聚类操作均是在这一网格结构上进行的。 这种方法主要优点就是处理时间由于与数据对象个数无关而仅与划分对象空间的网格数相关，从而显得相对较快。 STING就是一个典型的基于网格的方法。CLIQUE和WAVE－Cluster是两个基于网格和基于密度的聚类方法。 STING算法 STING（Statistical Inforation Grid-based Method，基于统计信息网格的方法）是针对空间数据挖掘的算法，它利用层次结构将空间区域划分为矩形单元，在每个单元中存储对象的统计参数（如均值、方差、最小值、最大值、分布的类型等），用以描述有关数据特征。STING通过对数据集进行一次扫描，计算单元中的统计参数。因此，若n表示对象的个数，则生成簇的时间复杂度为O (n)。 Each Cell at (i-1)th level has 4 children at ith level (can be changed) Parameter Generation i 1 2 3 4 ni 100 50 60 10 mi 20.1 19.7 21 20.5 si 2.3 2.2 2.4 2.1 mini 4.5 5.5 3.8 7 maxi 36 34 37 40 disti Normal Normal Normal None The parameters of the current cell are N=220 m=20.27 s=2.37 min=3.8 max=40 dist=NORMAL This is so because there are 220 data points out of which 10 are not NORMAL So confl/n=10/220=0.0450.05 hence it is still NORMAL. The parameters are calculated only once so overall compilation time is O(N) But querying requires much less time as we only scan the number of grid cells K i.e. O(K) 提纲 聚类分析简介 聚类分析中的数据类型 划分方法 层次方法 基于密度的方法 基于网格的方法 基于模型的聚类方法 基于模型方法 基于模型方法就是为每个聚类假设一个模型，然后再去发现符合相应模型的数据对象。 一个基于模型（统计学模型、神经网络模型）的算法可以通过构造一个描述数据点空间分布的密度函数来确定具体聚类。 它根据标准统计方法并考虑到“噪声”或异常数据，可以自动确定聚类个数；因而它可以产生很鲁棒的聚类方法。 COBWEB(1) COBWEB是一种简单增量概念聚类算法，它以一个分类树的形式创建层次聚类。 COBWEB采用启发式估算度量——分类效用来指导分类树的构建。如果要将对象加入分类树，就要加入到能产生最高分类效用的位置。即根据产生最高分类效用的划分，把对象置于一个存在的类中，或者为它创建一个新类。 COBWEB可以自动修正划分中类的数目，不需用户提供相应参数。 COBWEB的局限性在于假设每个属性上的概率分布相互独立，而实际上属性常常是相关的。 类内相似性 类间相异性 分类效用 COBWEB(2) 神经网络聚类方法 神经网络方法将每个簇描述为一个样本。样本作为聚类的原型，不一定对应特定的数据实例和对象。 神经网络聚类方法包括Rumelhart等人提出的竞争学习神经网络和Kohonen提出的自组织特征映射（SOM）神经网络。 神经网络聚类方法处理时间较长，并且有较高的数据复杂性。 * * * * * * K-Means算法示例 K-Means方法的变化(1) K－Means 算法还有一些变化 在初始k个聚类中心的选择； 差异程度计算； 聚类均值的计算方法。 一个常常有助于获得好的结果的策略就是首先应用自下而上层次算法来获得聚类数目，并发现初始分类；然后再应用循环再定位（聚类方法）来帮助改进分类结果。 K－Modes算法：该算法通过用模来替换聚类均值、采用新差异性计算方法来处理符号量，以及利用基于频率对各聚类模进行更新方法，从而将K－Means 算法的应用范围从数值量扩展到符号量。 K－Means 算法和K－Modes 算法结合到一起，就可以对采用数值量和符号量描述对象进行聚类分析，从而构成了K－Prototype算法。 K-Means方法的变化(2) 而EM（期望最大化）算法又从多个方面对K－Means 算法进行了扩展。其中包括：它根据描述聚类所属程度