数据挖掘中聚类分析的技术方法
汤效琴 戴汝源
摘 要：数据挖掘是信息产业界近年来非常热门的研究方向，聚类分析是数据挖掘中的核心技术。本文对数据挖掘领域的聚类分析方法及代表算法进行分析，并从多个方面对这些算法性能进行比较，同时还对聚类分析在数据挖掘中的几个应用进行了阐述。
关键词：数据挖掘；聚类分析；聚类算法
Technique of Cluster analysis in Data mining
Tang Xiaoqin Dai Ruyuan
(Computer Center Ningxia University, Yinchuan 750021,China)
Abstract: Data Mining is 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 application of the cluster analysis in Data Mining.
Keywords: Data Mining; Cluster analysis; Cluster algorithm
0 引言
数据挖掘(Data Mining)是指从存放在数据库、数据仓库或其他信息库中的大量数据中提取隐含的、未知的、有潜在应用价值的信息或模式的过程。数据挖掘涉及多学科技术，包括数据库技术、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号处理和空间数据分析。被信息产业界认为是数据库系统最重要的前沿之一，是信息产业最有前途的交叉学科。
数据挖掘的根本在于统计学，统计方法中多元数据分析的三大方法之一的聚类分析则是数据挖掘采用的核心技术，成为该研究领域中一个非常活跃的研究课题。聚类分析基于“物以类聚”的朴素思想，根据事物的特征对其进行聚类或分类。本文对数据挖掘领域的聚类分析方法及代表算法进行分析，并从多个方面对常用算法的性能面进行分析比较。最后阐述了聚类分析在数据挖掘中的应用。 1 数据挖掘领域中聚类算法的分类
聚类算法大体可以划分为以下几类：划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法。
1．1划分方法（partitioning method）
给定一个包含n个数据对象或元组的数据库，一个划分方法构建数据的c个划分，每个划分表示一个簇，且c≤n。通常会采用一个划分准则（经常称为相似度函数），例如距离，以便在同一个簇中的对象是“相似的”，在不同簇中的对象是“相异的”。这些聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。 1．2层次方法(hierarchical method)
层次方法对给定数据对象集合进行层次的分解。根据层次分解是自底向上还是自顶向下形成，层次聚类的方法可以进一步分为凝聚的和分裂的。层次聚类方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消，因此而不能更正错误的决定。改进层次方法的聚类质量的一个有希望的方向是将层次聚类和其他聚类技术进行集成，形
成多阶段聚类。
1．3基于密度的方法(density-based method)
提出了基于密度的聚类方法是为了发现任意形状的聚类结果。其主要思想是：只要临近区域的密度超过某个阈值，就继续聚类。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。
1．4基于网格的方法(grid-based method)
基于网格的聚类方法采用一个多分辨率的网格数据结构。把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构上进行。这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。
1．5基于模型的方法(model-based method)
基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。基于模型的算法可能性通过构建反映数据点空间分布的密度函数来定位聚类。这种聚类方法试图优化给定的数据和某些数学模型之间的适应性。 2．数据挖掘领域中常用的聚类算法
2．1 CLARANS算法（随机搜索聚类算法）
划分方法中最早提出的一些算法大多对小数据集合非常有效，但对大的数据集合没有良好的可伸缩性，如PAM。CLARA是基于C-中心点类型的算法，能处理更大的数据集合。CLARA算法不考虑整个数据集合，而是随机的选择实际数据的一小部分作为样本，然后用PAM方法从样本中选择中心点。这样从中选出的中心点很可能和整个数据集合中选出的非常近似。重复此方法，最后返回最好的聚类结果作为输出。
CLARANS是CLARA算法的一个改进算法。不象CLARA那样每个阶段选取一个固定样本，它在搜索的每一步都带一定随机性的选取一个样本，在替换了一个中心点后得到的聚类结果被称为当前聚类结果的邻居，搜索的邻居点数目被用户定义的一个参数加以限制。如果找到一个比它更好的邻居，则把中心点移到该邻居节点上，否则把该点作为局部最小量。然后，再随机选择一个点来寻找另一个局部最小量。该算法的计算复杂度大约是O(n2)，n是对象的数目。 2．2 CURE算法（利用代表点聚类）
CURE算法选择基于质心和基于代表对象方法之间的中间策略。该算法首先把每个数据点看成一簇，然后再以一个特定的收缩因子向中心“收缩”它们，即合并两个距离最近的代表点的簇。它回避了用所有点或单个质心来表示一个簇的传统方法，将一个簇用多个代表点来表示，使CURE可以适应非球形的几何形状。另外，收缩因子降底了噪音对聚类的影响，从而使CURE对孤立点的处理更加健壮，而且能识别非球形和大小变化比较大的簇。CURE的复杂度是O(n)，n是对象的数目。 2．3 BIRCH算法（利用层次方法的平衡迭代归约和聚类）
BIRCH是一个综合的层次聚类方法。它用聚类特征和聚类特征树（CF）来概括聚类描述。描述如下：
对于一具有N个d维数据点的簇{xi }(i=1,2,3,…,N)，它的聚类特征向量定义为：
? CF = (N , LS, SS) 其中N为簇中点的个数；LS表示N个点的线性和(数据点的平方和(
???Ni?1i?o)，反映了簇的重心，SS是
?2o?i?1i)，反映了类直径的大小。
N此外，对于聚类特征有如下定理：
??定理１ 假设CF1?(N1,LS1,SS1)与CF2?(N2,LS2,SS2)分别为两个类的聚类特
征，合并后的新类特征为
?? CF1?CF2?(N1?N2,LS1?LS2,SS1?SS2)
该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。 CF树是一个具有两个参数分支因子B和阈值T的高度平衡树，它存储了层次聚类的聚类特征。 分支因子定义了每个非叶节点孩子的最大数目，而阈值给出了存储在树的叶子节点中的子聚类的最大直径。CF树可以动态的构造，因此不要求所有的数据读入内存，而可在外存上逐个读入数据项。一个数据项总是被插入到最近的叶子条目（子聚类）。如果插入后使得该叶子节点中的子聚类的直径大于阈值，则该叶子节点及可能有其他节点被分裂。新数据插入后，关于该数据的信息向树根传递。可以通过改变阈值来修改CF树的大小来控制其占内存容量。BIRCH算法通过一次扫描就可以进行较好的聚类，故该算法的计算复杂度是O（n）,n是对象的数目。
2．4 DBSCAN算法（基于高密度连接区域的密度聚类方法）
DBSCAN算法可以将足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的聚类。该算法定义簇为密度相连的点的最大集合。
基于密度的聚类的基本思想有以下一些定义： ·给定对象半径?内的区域为该对象的?-邻域 ·如果一个对象的?-邻域至少包含最小数目MinPts个对象，则称该对象为核心对象。 ·给定一个对象集合D，如果p是在q的?-邻域内，而q是一个核心对象，则称对象p从对象q出发是直接密度可达的。
·如果存在一个对象链p1,p2,?,pn,p1?q,pn?p, 对pi?D,(1?i?n),pi?1是从pi关于?和MinPts直接密度可达的，则对象p是从对象q关于?和MinPts密度可达的。
·如果对象集合D中存在一个对象o，使得对象p和q是从o关于?和MinPts密度可达的，那么对象p和q是关于?和MinPts密度相连的。
DBSCAN通过检查数据库中每个点的?-邻域来寻找聚类。如果一个点p的?-邻域包含多于MinPts个点，则创建一个以p作为核心对象的新簇。然后反复地寻找从这些核心对象直接密度可达的对象，当没有新的点可以被添加到任何簇时，该过程结束。不包