数据挖掘中聚类分析的技术方法

《数据挖掘中聚类分析的技术方法》由会员分享，可在线阅读，更多相关《数据挖掘中聚类分析的技术方法（7页珍藏版）》请在装配图网上搜索。

1、数据挖掘中聚类分析的技术方法汤效琴 戴汝源摘 要：数据挖掘是信息产业界近年来非常热门的研究方向，聚类分析是数据挖掘中的核心技术。本文对数据挖掘领域的聚类分析方法及代表算法进行分析，并从多个方面对这些算法性能进行比较，同时还对聚类分析在数据挖掘中的几个应用进行了阐述。关键词：数据挖掘；聚类分析；聚类算法Technique of Cluster analysis in Data miningTang Xiaoqin Dai Ruyuan(Computer Center Ningxia University, Yinchuan 750021,China)Abstract: Data Mining i

2、s one of the pop research in information industry last few years. Cluster analysis is the core technique of Data Mining. This paper analyzes the cluster analysis method and representation cluster algorithm in the area of the Data Mining, and compares the algorithm capability. And also expatiate the

3、application of the cluster analysis in Data Mining.Keywords: Data Mining; Cluster analysis; Cluster algorithm0 引言数据挖掘(Data Mining)是指从存放在数据库、数据仓库或其他信息库中的大量数据中提取隐含的、未知的、有潜在应用价值的信息或模式的过程。数据挖掘涉及多学科技术，包括数据库技术、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号处理和空间数据分析。被信息产业界认为是数据库系统最重要的前沿之一，是信息产业最有前途的交叉学科。数据挖掘的根本

4、在于统计学，统计方法中多元数据分析的三大方法之一的聚类分析则是数据挖掘采用的核心技术，成为该研究领域中一个非常活跃的研究课题。聚类分析基于“物以类聚”的朴素思想，根据事物的特征对其进行聚类或分类。本文对数据挖掘领域的聚类分析方法及代表算法进行分析，并从多个方面对常用算法的性能面进行分析比较。最后阐述了聚类分析在数据挖掘中的应用。1 数据挖掘领域中聚类算法的分类聚类算法大体可以划分为以下几类：划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法。11划分方法（partitioning method）给定一个包含n个数据对象或元组的数据库，一个划分方法构建数据的c个划分，每个划分表示

5、一个簇，且cn。通常会采用一个划分准则（经常称为相似度函数），例如距离，以便在同一个簇中的对象是“相似的”，在不同簇中的对象是“相异的”。这些聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。12层次方法(hierarchical method) 层次方法对给定数据对象集合进行层次的分解。根据层次分解是自底向上还是自顶向下形成，层次聚类的方法可以进一步分为凝聚的和分裂的。层次聚类方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消，因此而不能更正错误的决定。改进层次方法的聚类质量的一个有希望的方向是将

6、层次聚类和其他聚类技术进行集成，形成多阶段聚类。13基于密度的方法(density-based method) 提出了基于密度的聚类方法是为了发现任意形状的聚类结果。其主要思想是：只要临近区域的密度超过某个阈值，就继续聚类。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。14基于网格的方法(grid-based method) 基于网格的聚类方法采用一个多分辨率的网格数据结构。把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构上进行。这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。15基于模型

7、的方法(model-based method)基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。基于模型的算法可能性通过构建反映数据点空间分布的密度函数来定位聚类。这种聚类方法试图优化给定的数据和某些数学模型之间的适应性。2数据挖掘领域中常用的聚类算法21 CLARANS算法（随机搜索聚类算法） 划分方法中最早提出的一些算法大多对小数据集合非常有效，但对大的数据集合没有良好的可伸缩性，如PAM。CLARA是基于C-中心点类型的算法，能处理更大的数据集合。CLARA算法不考虑整个数据集合，而是随机的选择实际数据的一小部分作为样本，然后用PAM方法从样本中选择中心点。这样从中选出

8、的中心点很可能和整个数据集合中选出的非常近似。重复此方法，最后返回最好的聚类结果作为输出。CLARANS是CLARA算法的一个改进算法。不象CLARA那样每个阶段选取一个固定样本，它在搜索的每一步都带一定随机性的选取一个样本，在替换了一个中心点后得到的聚类结果被称为当前聚类结果的邻居，搜索的邻居点数目被用户定义的一个参数加以限制。如果找到一个比它更好的邻居，则把中心点移到该邻居节点上，否则把该点作为局部最小量。然后，再随机选择一个点来寻找另一个局部最小量。该算法的计算复杂度大约是O(n2)，n是对象的数目。22 CURE算法（利用代表点聚类）CURE算法选择基于质心和基于代表对象方法之间的中间

9、策略。该算法首先把每个数据点看成一簇，然后再以一个特定的收缩因子向中心“收缩”它们，即合并两个距离最近的代表点的簇。它回避了用所有点或单个质心来表示一个簇的传统方法，将一个簇用多个代表点来表示，使CURE可以适应非球形的几何形状。另外，收缩因子降底了噪音对聚类的影响，从而使CURE对孤立点的处理更加健壮，而且能识别非球形和大小变化比较大的簇。CURE的复杂度是O(n)，n是对象的数目。23 BIRCH算法（利用层次方法的平衡迭代归约和聚类）BIRCH是一个综合的层次聚类方法。它用聚类特征和聚类特征树（CF）来概括聚类描述。描述如下：对于一具有N个d维数据点的簇 (i=1,2,3,N)，它的聚类

10、特征向量定义为： CF = (N , , SS)其中N为簇中点的个数；表示N个点的线性和()，反映了簇的重心，SS是数据点的平方和()，反映了类直径的大小。此外，对于聚类特征有如下定理：定理 假设与分别为两个类的聚类特征，合并后的新类特征为 该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。CF树是一个具有两个参数分支因子B和阈值T的高度平衡树，它存储了层次聚类的聚类特征。 分支因子定义了每个非叶节点孩子的最大数目，而阈值给出了存储在树的叶子节点中的子聚类的最大直径。CF树可以动态的构造，因此不要求所有的数据读入内存，而可在外存上逐个读入数据项。一个数据项总是被插入到最近

11、的叶子条目（子聚类）。如果插入后使得该叶子节点中的子聚类的直径大于阈值，则该叶子节点及可能有其他节点被分裂。新数据插入后，关于该数据的信息向树根传递。可以通过改变阈值来修改CF树的大小来控制其占内存容量。BIRCH算法通过一次扫描就可以进行较好的聚类，故该算法的计算复杂度是O（n）,n是对象的数目。 24 DBSCAN算法（基于高密度连接区域的密度聚类方法）DBSCAN算法可以将足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的聚类。该算法定义簇为密度相连的点的最大集合。基于密度的聚类的基本思想有以下一些定义：给定对象半径内的区域为该对象的-邻域如果一个对象的-邻域至少

12、包含最小数目MinPts个对象，则称该对象为核心对象。给定一个对象集合D，如果是在的-邻域内，而是一个核心对象，则称对象从对象出发是直接密度可达的。如果存在一个对象链 对是从关于和MinPts直接密度可达的，则对象是从对象关于和MinPts密度可达的。如果对象集合D中存在一个对象，使得对象和是从关于和MinPts密度可达的，那么对象和是关于和MinPts密度相连的。DBSCAN通过检查数据库中每个点的-邻域来寻找聚类。如果一个点的-邻域包含多于MinPts个点，则创建一个以作为核心对象的新簇。然后反复地寻找从这些核心对象直接密度可达的对象，当没有新的点可以被添加到任何簇时，该过程结束。不包含在

13、任何簇中的对象被认为是“噪声”。如果采用空间索引，DBSCAN的计算复杂度是，这里是数据库中对象数目。否则，计算复杂度是。25 STING算法（统计信息风格）STING（Statistaical Information Grid_based method）是一种基于风格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易地从低层单元的计算得到。这些参数包括：属性无关的参数count；属性相关的参数m（平均值），s（标准偏差），min（最小值），max（最

14、大值），以及该单元中属性值遵循的分布（distribution）类型。STING算法中由于存储在每个单元中的统计信息提供了单元中的数据不依赖于查询的汇总信息，因而计算是独立于查询的。该算法主要优点是效率高，且利于并行处理和增量更新。STING扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是O（n），基中n是对象的数目。在层次结构建立后，查询处理时间是O(g)，g是最低层风格单元的数目，通常远远小于n。26 COBWEB算法（流行的简单增量概念聚类算法）概念聚类是机器学习中的一种聚类方法，大多数概念聚类方法采用了统计学的途径，在决定概念或聚类时使用概率度量。COBWEB以一个分类树

15、的形式创建层次聚类，它的输入对象用分类属性-值对来描述。分类树和判定树不同。分类树中的每个节点对应一个概念，包含该概念的一个概率描述，概述被分在该节点下的对象。概率描述包括概念的概率和形如P(Ai=Vij|Ck)的条件概率，这里Ai=Vij是属性-值对，Ck是概念类。在分类树某层次上的兄弟节点形成了一个划分。COBWEB采用了一个启发式估算度量分类效用来指导树的构建。分类效用定义如下：是在树的某个层次上形成一个划分的节点、概念或“种类”的数目。分类效用回报类内相似性和类间相异性：概率P(Ai=Vij|Ck)表示类内相似性。该值越大，共享该属性-值对的类成员比例就越大，更能预见该属性-值对是类成

16、员概率P(Ck|Ai=Vij)表示类间相异性。该值越大，在对照类中的对象的共享该属性-值对就越少，更能预见该属性-值对是类成员给定一个新的对象，COBWEB沿一条适当的路径向下，修改计数，寻找可以分类该对象的最好节点。该判定基于将对象临时置于每个节点，并计算结果划分的分类效用。产生最高分类效用的位置应当是对象节点的一个好的选择。26 模糊聚类算法FCM以上介绍的几种聚类算法可以导出确定的聚类，也就是说，一个数据点或者属于一个类，或者不属于一个类，而不存在重叠的情况。我们可以称这些聚类方法为“确定性分类”。在一些没有确定支持的情况中，聚类可以引入模糊逻辑概念。对于模糊集来说，一个数据点都是以一定

17、程度属于某个类，也可以同时以不同的程度属于几个类。常用的模糊聚类算法是模糊C平均值FCM（Fuzzy C-Means）算法。该算法是在传统C均值算法中应用了模糊技术。FCM算法中，用隶属度函数定义的聚类损失函数可以写为：， （6-1）其中，b1是一个可以控制聚类结果的模糊程度的常数。要求一个样本对于各个聚类的隶属度之和为1，即 ， (6-2)在条件式（6-2）下求式（6-1）的极小值，令对和的偏导数为0，可得必要条件： ， （6-3） ， 。 （6-4）用迭代法求解式（6-3）和式（6-4），就是FCM算法。当算法收敛时，就得到了各类的聚类中心和各个样本对于各类的隶属度值勤，从而完成了模糊聚类

18、划分。3聚类算法的性能比较 基于上述的分析，下面对常用聚类算法的性能从可伸缩性、发现聚类的形状、对“噪声”的敏感性、对数据输入顺序的敏感性、高维性和算法效率六个方面进行比较，如表1所示。 表1 聚类算法比较可伸缩性发现聚类的形状对“噪声”的敏感性对数据输入顺序的敏感性高维性算法效率CLARANS好凸形或球形不敏感非常敏感一般较低CURE较差任意形状不敏感敏感好较高BIRCH较差凸开或球形一般不太敏感好高STING好任意形状不敏感不敏感好高DBSCAN较好任意形状不敏感敏感一般一般COBWEB较好任意形状一般敏感好较低FCM 好任意形状敏感不敏感好较高 由于数据挖掘在不同领域的应用对聚类算法提出

19、了各自特殊的要求，表1则可以给聚类算法的研究和应用的选择提供参考。4聚类分析在数据挖掘中的应用 聚类分析在数据挖掘中的应用主要有两个方面：一、聚类分析可以作为其他算法的预处理步骤，这些算法再在生成的簇上进行处理。可作为特征和分类算法的预处理步骤，也可将聚类结果用于进一步关联分析。二、可以作为一个独立的工具来获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇做进一步分析。可用在市场细分、目标顾客定位、业绩评估、生物群种划分等方面。如在商务上，聚类分析可以帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。三、聚类分析可以完成孤立点挖掘。许多数据挖掘算法试

20、图使孤立点影响最小化，或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为。参考文献：1 M.Halkidi, Y.Batistakis, M.Vazirgiannis Clustering algorithms and validity measures IEEE 2001.3-222 GEHRKE J,AGRAWAL R,GUNOPULOS D. Automatic Subspace Clustering of High Dimensional Data fro Data caitonsJ. ACM SIMOD,1998,72(2):94-105.3 Ng

21、 RT, CALBERSON J,Efficient and Effective Clustering Methods for Spatial Data MiningA.In:Porc of the VC.Santiago,Chile,1994.144-155.4 周晓宇等 数据挖掘技术初探J 小型微型计算系统 2002(3) 342-3455 范明,孟小峰译 数据挖掘：概念与技术聚类分析M.北京：机械工业出版社，2001.223-2586 边肇祺 张学工等 模式识别（第二版）。北京：清华大学出版社，2002.273-2837 钱锋等，知识发现中的聚类分析及其应用J 杭州师范学院学报 2001(2) 34-37作者简介：汤效琴，女，1970年生，讲师，硕士生，主要从事程序设计语言、数据库和信息管理系统等方向的教学与科研工作。联系电话：0951-2080215。E-mail:Tang_xq。通讯地址：宁夏银川市宁夏大学北校区计算中心。邮政编码：750021 戴汝源，男，1969年生，硕士生。宁夏大学物理电气信息学院，讲师。