数据挖掘中聚类算法比较研究.pdf

数据挖掘中聚类算法比较研究

张红云刘向东段晓东苗夺谦马垣。
(同济大学电子与信息工程学院上海2ooo92)(大连民族学院计算机系大连116600)
(鞍山科技大学计算机科学与工程学院鞍山114002)

摘要聚类算法是数据挖掘的核心技术，本文综合提出了评价聚类算法好坏的5个标准，基于这5个标准，对数据挖掘中常用
聚类算法作了比较分析，以便于人们更容易、更快捷地找到一种适用干特定问题的聚类算法。

关键词数据挖掘平衡迭代削减聚类算法代表点聚类算法基于密度的聚类算法

TlⅢC0oNoFCIITERDⅧDATAⅧND

ZhangHongyunMiaoDuqianLiuXiangdong~DuanXiaodong2MaYuan。

(ofElectronicandInformation肪驴咖，University，S~nghai200092)
。(DⅡ】伽ofComputers．DalianNationalities，Dalian1166OO)

(Sd~oZofCornptaerS&E，AnshanUnlvemtyofSd~＆Technology．Anshan114002)

AbstractClusteringmethodisthecoreofdatamini~technology．Inthispaper，fivestandardswereputforwardwhichareusedtoevaluatethese

clusteringmethods．TheseclusteringmethodswerecomparedandanalyzedaccordingtothestandardsSOthatpeoplecalleasilyandquicklyfindaclus-

tefingmethodthatsuitaspecialproblem．

KeywordsDataMiningBIRCHDBSCANCURE

CURE算法等。
1引言本文对各聚类算法的比较研究基于以下5个标准：
①是否适用于大数据量，算法的效率是否满足大数据量、

把数据库中的对象分类是数据挖掘的基本操作，其准则是高复杂性的要求；
②是否能应付不同的数据类型，能否处理符号属性；
使属于同一类的个体间距离尽可能小，而不同类个体间距离尽
③是否能发现不同类型的聚类；
可能大，为了找到效率高、通用性强的聚类方法，人们从不同角
④是否能应付脏数据或异常数据；
度提出了近百种聚类方法，典型的有K一咖方法、K—me．
⑤是否对数据的输入顺序不敏感。
dS方法、CLARANS方法、BIRCH方法等，这些算法适用于特定
下面将在该框架下对各聚类算法作分析比较。
的问题及用户。本文综合提出了评价聚类算法好坏的5个标
准，基于这5个标准，对数据挖掘中常用聚类方法作了比较分
3数据挖掘常用聚类算法比较分析
析，以便于人们更容易、更快捷地找到一种适用于特定问题及
用户的聚类算法。
3．1BIRCH算法
BIRCH算法即平衡迭代削减聚类法，其核心是用一个聚类
2数据挖掘聚类算法研究及比较框架特征3元组表示一个簇的有关信息，从而使一簇点的表示可用
对应的聚类特征，而不必用具体的一组点来表示。它通过构造
聚类算法一般分为分割和分层两种。分割聚类算法通过
满足分支因子和簇直径限制的聚类特征树来求聚类。BIRCH
优化评价函数把数据集分割为K个部分，它需要K作为输入参
算法通过聚类特征可以方便地进行中心、半径、直径及类内、类
数。典型的分割聚类算法有K-means算法、K—medoids算法、
间距离的运算。算法的聚类特征树是一个具有两个参数分枝
CLARANS算法。分层聚类由不同层次的分割聚类组成，层次之

间的分割具有嵌套的关系。它不需要输入参数，这是它优于分收稿13期：20Ol一09—12。本课题得到国家博士后科研基金与扛宁
割聚类算法的一个明显的优点，其缺点是终止条件必须具体指省博士启动基金项目资助(2000014512)。张红云，博士生．主研领域：数
定。典型的分层聚类算法有BIRCH算法、DBSCAN算法和据库与知识系统。

·5·

因子B和类直径T的高度平衡树。分枝因子规定了树的每个个最临近的对象之间的距离。然后，根据求得的距离由小到大
节点子女的最多个数，而类直径体现了对一类点的直径大小的排序，并绘出排序后的图，称做k—dist图。k—dist图中的横坐
限制，即这些点在多大范围内可以聚为一类，非叶子结点为它标表示数据对象与它的第k个最近的对象间的距离；纵坐标为
的子女的最大关键字，可以根据这些关键字进行插入索引，它对应于某一k—dist距离值的数据对象的个数。R一树的建立
总结了其子女的信息。和k—dist图的绘制非常消耗时间。此外，为了得到较好