基于代表点的快速聚类算法
2010，46（33）1概述
聚类技术是数据挖掘中重要的研究课题之一。文献[1]
把聚类定义为：将物理或抽象对象的集合划分成相似对象类的过程。在当前数据爆炸的时代，聚类技术可以挖掘出隐藏在海量数据之下的信息和数据固有的结构分布。聚类分析在许多应用领域已经得到广泛应用，在商务中，对购买模式进行聚类能划分不同的客户群，刻画客户群的特征。在生物学中，根据动物或植物的主要属性进行聚类来推导分类发现新的物种或者在同一个种的数据集上进行聚类从而划分出不同的亚种。聚类还可以应用于离群点检测，进行信用卡欺诈检测和监控电子商务中的犯罪活动。此外在心理学、考古学、地质学、地理学以及市场营销研究中也都有重要应用
[1-4]
。
郭晓娟等在文献[5]中提出了基于部分重叠划分POP 的改进HAC 算法。康卫鲜等在文献[6]中详细介绍了CURE 算法，并提出了一种改进算法。沈洁等提出了CURE 的一种改进算法K-CURE [7]
。本文受CURE [8]
聚类算法启发，采用一定个数的代表点来代表簇对象进行相似度的度量，并结合90_10规则，对传统的层次聚类算法进行了改进，提出了一种改进的层次聚类算法REPBFC 。
2基于划分的聚类和层次聚类
2.1基于划分方法的聚类
基于划分的聚类就是把给定的n 个数据对象或元组根据相似性指派到k 个类簇中心，使聚类准则函数最优，簇内数据对象相似性最大，簇间数据对象相似性最小，最后形成对n 个数据对象的k 个划分。对于硬聚类而言，要求：（1）每个簇中至少包含一个数据对象；（2）每个数据对象只能属于一个簇；（3）k 个划分的并集等于整个数据集。这种聚类方法的关键是聚类个数的确定和聚类中心的选择。该方法的典型代表算法有：K -means 、K -medoids 以及它们的变种K -modes 、EM 、PAM 、
CLARANS 。
K-means 算法描述：（1）从n 个数据对象中随机选择k 个不同的点作为初始聚类中心；（2）根据相似性分别把n 个数据对象指派到与自己最相似的簇中；（3）更新簇的质心；（4）重复步骤（2）、步骤（3）直到达到终止条件。终止条件一般设为达到最大迭代次数或平方误差函数收敛。K -means 是以簇的质心来代表簇对象的。
K -medoids 算法描述：（1）从n 个数据对象中随机选择k 个不同的点作为初始类簇的代表对象；（2）根据相似性分别把n 个数据对象指派到与自己最相似的簇中；（3）随机地选择一个
基于代表点的快速聚类算法
贾瑞玉，耿锦威，宁再早，何成刚
JIA Rui-yu ，GENG Jin-wei ，NING Zai-zao ，HE Cheng-gang
安徽大学计算机科学与技术学院，合肥230039
School of Computer Science and Technology ，Anhui University ，Hefei 230039，China E-mail ：jiaruiyu267@https://www.docsj.com/doc/565585725.html,
JIA Rui-yu ，GENG Jin-wei ，NING Zai-zao ，et al.Fast clustering algorithm based on representative https://www.docsj.com/doc/565585725.html,puter Engi-neering and Applications ，2010，46（33）：121-123.
Abstract ：To the drawback of traditional hierarchical clustering algorithm that only merges one pair of the most similar clus-ters each iteration ，easily influenced by outliers and favoring clusters with spherical shapes ，inspired by CURE algorithm and the 90_10rule ，an improved clustering algorithm named REPBFC （REpresentative Points Based Fast Clustering ）is proposed.The experiments show that the improved algorithm is efficient.Key words ：90_10rule ；multistage clustering ；clustering algorithm 摘
要：针对传统的层次聚类算法每次迭代只将距离最小的那对类簇合并，容易受离群点影响，偏向于发现凸状或球状簇等缺
点，受CURE 算法启发，采用簇中固定数量代表点来代表簇对象进行距离的计算，并结合90_10规则，提出了一种改进的层次聚类算法REPBFC （REpresentative Points Based Fast Clustering ），实验表明该算法是有效的。关键词：90_10规则；多阶段聚类；聚类算法DOI ：10.3778/j.issn.1002-8331.2010.33.034
文章编号：1002-8331（2010）33-0121-03
文献标识码：Ａ
中图分类号：TP301.6
基金项目：安徽省自然科学研究项目基金（the Anhui Province Natural Science Foundation ，China under Grant No.KJ2008B092）。
作者简介：贾瑞玉（1965-），女，副教授，硕士生导师，主要研究方向为数据挖掘、人工智能、计算机图形学；耿锦威（1986-），男，硕士研究生，主要研
究方向为数据挖掘。
收稿日期：2010-05-24
修回日期：2010-08-27
Computer Engineering and Applications 计算机工程与应用
121