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

数据挖掘中聚类分析的技术方法汤效琴戴汝源摘要：数据挖掘是信息产业界近年来非常热门的研究方向，聚类分析是数据挖掘中的核心技术。本文对数据挖掘领域的聚类分析方法及代表算法进行分析，并从多个方面对这些算法性能进行比较，同时还对聚类分析在数据挖掘中的几个应用进行了阐述。关键词：数据挖掘；聚类分析；聚类算法TechniqueofClusteranalysisinDataminingTangXiaoqinDaiRuyuan(ComputerCenterNingxiaUniversity,Yinchuan750021,China)Abstract:DataMiningisoneofthepopresearchininformationindustrylastfewyears.ClusteranalysisisthecoretechniqueofDataMining.ThispaperanalyzestheclusteranalysismethodandrepresentationclusteralgorithmintheareaoftheDataMining,andcomparesthealgorithmcapability.AndalsoexpatiatetheapplicationoftheclusteranalysisinDataMining.Keywords:DataMining;Clusteranalysis;Clusteralgorithm0引言数据挖掘(DataMining)是指从存放在数据库、数据仓库或其他信息库中的大量数据中提取隐含的、未知的、有潜在应用价值的信息或模式的过程。数据挖掘涉及多学科技术，包括数据库技术、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号处理和空间数据分析。被信息产业界认为是数据库系统最重要的前沿之一，是信息产业最有前途的交叉学科。数据挖掘的根本在于统计学，统计方法中多元数据分析的三大方法之一的聚类分析则是数据挖掘采用的核心技术，成为该研究领域中一个非常活跃的研究课题。聚类分析基于“物以类聚”的朴素思想，根据事物的特征对其进行聚类或分类。本文对数据挖掘领域的聚类分析方法及代表算法进行分析，并从多个方面对常用算法的性能面进行分析比较。最后阐述了聚类分析在数据挖掘中的应用。1数据挖掘领域中聚类算法的分类聚类算法大体可以划分为以下几类：划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法。1．1划分方法（partitioningmethod）给定一个包含n个数据对象或元组的数据库，一个划分方法构建数据的c个划分，每个划分表示一个簇，且c≤n。通常会采用一个划分准则（经常称为相似度函数），例如距离，以便在同一个簇中的对象是“相似的”，在不同簇中的对象是“相异的”。这些聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。1．2层次方法(hierarchicalmethod)层次方法对给定数据对象集合进行层次的分解。根据层次分解是自底向上还是自顶向下形成，层次聚类的方法可以进一步分为凝聚的和分裂的。层次聚类方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消，因此而不能更正错误的决定。改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。1．3基于密度的方法(density-basedmethod)提出了基于密度的聚类方法是为了发现任意形状的聚类结果。其主要思想是：只要临近区域的密度超过某个阈值，就继续聚类。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。1．4基于网格的方法(grid-basedmethod)基于网格的聚类方法采用一个多分辨率的网格数据结构。把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构上进行。这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。1．5基于模型的方法(model-basedmethod)基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。基于模型的算法可能性通过构建反映数据点空间分布的密度函数来定位聚类。这种聚类方法试图优化给定的数据和某些数学模型之间的适应性。2．数据挖掘领域中常用的聚类算法2．1CLARANS算法（随机搜索聚类算法）划分方法中最早提出的一些算法大多对小数据集合非常有效，但对大的数据集合没有良好的可伸缩性，如PAM。CLARA是基于C-中心点类型的算法，能处理更大的数据集合。CLARA算法不考虑整个数据集合，而是随机的选择实际数据的一小部分作为样本，然后用PAM方法从样本中选择中心点。这样从中选出的中心点很可能和整个数据集合中选出的非常近似。重复此方法，最后返回最好的聚类结果作为输出。CLARANS是CLARA算法的一个改进算法。不象CLARA那样每个阶段选取一个固定样本，它在搜索的每一步都带一定随机性的选取一个样本，在替换了一个中心点后得到的聚类结果被称为当前聚类结果的邻居，搜索的邻居点数目被用户定义的一个参数加以限制。如果找到一个比它更好的邻居，则把中心点移到该邻居节点上，否则把该点作为局部最小量。然后，再随机选择一个点来寻找另一个局部最小量。该算法的计算复杂度大约是O(n2)，n是对象的数目。2．2CURE算法（利用代表点聚类）CURE算法选择基于质心和基于代表对象方法之间的中间策略。该算法首先把每个数据点看成一簇，然后再以一个特定的收缩因子向中心“收缩”它们，即合并两个距离最近的代表点的簇。它回避了用所有点或单个质心来表示一个簇的传统方法，将一个簇用多个代表点来表示，使CURE可以适应非球形的几何形状。另外，收缩因子降底了噪音对聚类的影响，从而使CURE对孤立点的处理更加健壮，而且能识别非球形和大小变化比较大的簇。CURE的复杂度是O(n)，n是对象的数目。2．3BIRCH算法（利用层次方法的平衡迭代归约和聚类）BIRCH是一个综合的层次聚类方法。它用聚类特征和聚类特征树（CF）来概括聚类描述。描述如下：对于一具有N个d维数据点的簇{ix}(i=1,2,3,…,N)，它的聚类特征向量定义为：CF=(N,SL,SS)其中N为簇中点的个数；SL表示N个点的线性和(iNio1)，反映了簇的重心，SS是数据点的平方和(Niio12)，反映了类直径的大小。此外，对于聚类特征有如下定理：定理１假设),,(1111SSSLNCF与),,(2222SSSLNCF分别为两个类的聚类特征，合并后的新类特征为),,(21212121SSSSSLSLNNCFCF该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。CF树是一个具有两个参数分支因子B和阈值T的高度平衡树，它存储了层次聚类的聚类特征。分支因子定义了每个非叶节点孩子的最大数目，而阈值给出了存储在树的叶子节点中的子聚类的最大直径。CF树可以动态的构造，因此不要求所有的数据读入内存，而可在外存上逐个读入数据项。一个数据项总是被插入到最近的叶子条目（子聚类）。如果插入后使得该叶子节点中的子聚类的直径大于阈值，则该叶子节点及可能有其他节点被分裂。新数据插入后，关于该数据的信息向树根传递。可以通过改变阈值来修改CF树的大小来控制其占内存容量。BIRCH算法通过一次扫描就可以进行较好的聚类，故该算法的计算复杂度是O（n）,n是对象的数目。2．4DBSCAN算法（基于高密度连接区域的密度聚类方法）DBSCAN算法可以将足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的聚类。该算法定义簇为密度相连的点的最大集合。基于密度的聚类的基本思想有以下一些定义：·给定对象半径内的区域为该对象的-邻域·如果一个对象的-邻域至少包含最小数目MinPts个对象，则称该对象为核心对象。·给定一个对象集合D，如果p是在q的-邻域内，而q是一个核心对象，则称对象p从对象q出发是直接密度可达的。·如果存在一个对象链,,,,,,121ppqppppnn对1),1(,iipniDp是从ip关于和MinPts直接密度可达的，则对象p是从对象q关于和MinPts密度可达的。·如果对象集合D中存在一个对象o，使得对象p和q是从o关于和MinPts密度可达的，那么对象p和q是关于和MinPts密度相连的。DBSCAN通过检查数据库中每个点的-邻域来寻找聚类。如果一个点p的-邻域包含多于MinPts个点，则创建一个以p作为核心对象的新簇。然后反复地寻找从这些核心对象直接密度可达的对象，当没有新的点可以被添加到任何簇时，该过程结束。不包含在任何簇中的对象被认为是“噪声”。如果采用空间索引，DBSCAN的计算复杂度是)log(nnO，这里n是数据库中对象数目。否则，计算复杂度是)(2nO。2．5STING算法（统计信息风格）STING（StatistaicalInformationGrid_basedmethod）是一种基于风格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易地从低层单元的计算得到。这些参数包括：属性无关的参数count；属性相关的参数m（平均值），s（标准偏差），min（最小值），max（最大值），以及该单元中属性值遵循的分布（distribution）类型。STING算法中由于存储在每个单元中的统计信息提供了单元中的数据不依赖于查询的汇总信息，因而计算是独立于查询的。该算法主要优点是效率高，且利于并行处理和增量更新。STING扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是O（n），基中n是对象的数目。在层次结构建立后，查询处理时间是O(g)，g是最低层风格单元的数目，通常远远小于n。2．6COBWEB算法（流行的简单增量概念聚类算法）概念聚类是机器学习中的一种聚类方法，大多数概念聚类方法采用了统计学的途径，在决定概念或聚类时使用概率度量。COBWEB以一个分类树的形式创建层次聚类，它的输入对象用分类属性-值对来描述。分类树和判定树不同。分类树中的每个节点对应一个概念，包含该概念的一个概率描述，概述被分在该节点下的对象。概率描述包括概念的概率和形如P(Ai=Vij|Ck)的条件概率，这里Ai=Vij是属性-值对，Ck是概念类。在分类树某层次上的兄弟节点形成了一个划分。COBWEB采用了一个启发式估算度量——分类效用来指导树的构建。分类效用定义如下：nVAPCVAPCPnkijijijikijik122])()|()[(n是在树的某个层次上形成一个划分{nCCC,,,21}的节点、概念或“种类”的数目。分类效用回报类内相似性和类间相异性：•概率P(Ai=Vij|Ck)表示类内相似性。该值越大，共享该属性-值对的类成员比例就越大，更能预见该属性-值对是类成员•概率P(Ck|Ai=Vij)表示类间相异性。该值越大，在对照类中的对象的共享该属性-值对就越少，更能预见该属性-值对是类成员给定一个新的对象，COBWEB沿一条适当的路径向下，修改计数，寻找可以分类该对象的最好节点。该判定基于将对象临时置于每个节点，并计算结果划分的分类效用。产生最高分类效用的位置应当是对象节点的一个好的选择。2．6模糊聚类算法FCM以上介绍的几种聚类算法可以导出确定的聚类，也就是说，一个数据点或者属于一个类，或者不属于一个类，而不存在重叠的情况。我们可以称这些聚类方法为“确定性分类”。在一些没有确定支持的情况中，聚类可以引入模糊逻辑概念。对于模糊集来说，一个数据点都是以一定程度属于某个类，也可以同时以不同的程度属于几个类。常用的模糊聚类算法是模糊C平均值FCM（FuzzyC-Mean