小 型 微 型 计 算 机 系 统
Journal of Chinese Computer System s
2010年 8月 第 8期
Vol131 No. 8 2010
收稿日期 : 2009205218 收修改稿日期 : 2009207220 基金项目 :国家自然科学基金项目 ( 60673191 )资助 ; 广东省自然科学基金项目
(9151026005000002)资助 ;广东省高等学校自然科学研究重点项目 (06Z012) 资助. 作者简介 :蒋盛益 ,男 , 1963年生 ,博士 ,教授 ,研究方向为
数据挖掘、网络安全 ;庞观松 ,男 , 1988年生 ,硕士研究生 ,研究方向为数据挖掘应用 ;张黎莎 ,女 , 1987年生 ,硕士研究生 ,研究方向为数据挖掘应
用.
Cham eleon算法的改进
蒋盛益 , 庞观松 ,张黎莎
(广东外语外贸大学 信息学院 ,广东 广州 510420)
E2m ail: jiangshengyi@163. com
摘 要 : 结合 Cham eleon算法可以发现高质量的任意形状、大小和密度的自然簇及一趟聚类算法快速高效的特点 ,研究可以处
理混合属性的高效聚类算法 . 首先简单改进 Cham eleon算法 ,使之可以处理含分类属性的数据 ;进而提出一种两阶段聚类算法.
第一阶段使用一趟聚类算法对数据集进行初始划分 ,第二阶段利用改进的 Cham eleon算法归并初始划分而得到最终聚类. 在真
实数据集和人造数据集上的实验结果表明 ,提出的两阶段聚类算法是有效可行的 .
关 键 词 : 一趟聚类算法 ;基于图的聚类算法 ;任意形状簇
中图分类号 : TP309 文献标识码 : A 文 章 编 号 : 100021220 (2010) 0821643204
Enhanced Cham eleon C luster ing A lgor ithm
J IANG Sheng2yi , PAN G G uan2song , ZHAN G L i2sha
( School of Informa tics, Guangdong U niversity of Foreign S tudies, G uangzhou 510420, China )
Abstract: In view of the fac t that Cham eleon clustering a lgorithm can iden tify the da ta w ith arb itrary shape, s ize and density, and one2
pass clus te ring a lgorithm has the eff ic ien t fea ture, an eff ic ient clustering a lgorithm is p resen ted, the c lus te ring algorithm can p rocess
the data w ith categorica l a ttribu tes. F irst, Cham eleon is im p roved to p rocess the data w ith categorica l a ttributes. Second, by com bi2
n ing one2pass c lus te ring a lgorithm w ith im p roved Cham eleon c lus te ring a lgorithm , a tw o2s tage enhanced Cham eleon c lus te ring algo2
rithm is p resen ted. In the firs t s tage, one2pass clus tering a lgorithm is used for group ing the da ta (w e call it orig ina l partition) . In the
second stage, w e m erge tha t partition w ith im p roved Cham eleon c lus te ring algorithm so tha t the f ina l clus ters are ob ta ined. The exper2
im en ta l results on rea l da tase ts and synthe tic da tase ts show that the p resented c lus te ring algorithm is effec tive and p rac ticable.
Key words: one2pass clus tering a lgorithm; graph2based c lus te ring algorithm; arbitra ry shape cluster
1 引 言
聚类分析是数据挖掘中的重要任务 ,就是根据对象之间
的相似度将对象划分为不同的组 ,使得同一组内的对象相似
度最大化 ,而不同组内的对象相似度最小化的方法. 聚类分析
通常用于从大量数据中寻找隐含的数据分布和模式 ,既可以
作为一个独立的工具来使用 ,也可以作为其它算法 (如特征
构造与分类等 )的预处理步骤. 聚类分析已得到广泛的研究 ,
在文献中已有许多聚类算法 ,然而对于大规模数据集的高效
聚类算法的研究仍然是一个充满挑战的问题.
Cham eleon算法 [ 1 ]是一种基于图的层次聚类算法 ,该算
法利用基于图的方法得到的初始数据划分与一种新颖的层次
聚类
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
相结合 ,使用簇间的接近性和互连性概念以及簇的
局部建模来高质量地发现具有不同形状、大小和密度的簇. 近
年来 ,许多学者对 Cham eleon算法进行了研究改进 ,文献 [ 22
3 ]对 Cham eleon算法进行了研究分析 ,并列举出实现的方法 ,
文献 [ 4 ]将 Cham eleon算法应用于网站建设 ,得到了很好的
效果. 文献 [ 5 ]对 Cham eleon算法进行了简单改进 ,事先对 K2
最近邻图进行修剪后再进行聚类. Cham eleon算法及其已有
改进算法存在两方面的不足 : ( 1 ) 只能处理数值属性数据 ;
(2)时间复杂度为 O (N2 ) (N 为记录总数 ) ,难以适用于大规
模数据集.
文献 [ 6 ]提出一种面向混合属性数据的基于最小距离原
则的一趟聚类算法 ,同时也给出了计算聚类阈值的指导性方
法. 该算法具有近似线性时间复杂度 ,但这一算法本质上是将
数据划分为大小几乎相同的超球体 ,不能用于发现非凸形状
的簇 ,或具有各种不同大小的簇. 对于具有任意形状簇的数据
集 ,算法可能将一个大的自然簇划分成几个小的簇 ,而难以得
到理想的聚类结果.
本文将文献 [ 1, 6 ]的聚类思想结合起来 ,提出一种两阶
段聚类算法. 首先对 Cham eleon算法进行简单推广 ,使之可以
处理含分类属性的数据 ,在此基础上 ,对 Cham eleon算法进一
步改进. 该算法第一阶段 ,使用一趟聚类算法对数据集进行初
步划分 ,第二阶段 ,将第一阶段获得的结果中每个簇看成一个
对象 ,利用改进的 Cham eleon算法对初始划分进行归并. 这种
两阶段聚类算法结合了两种聚类算法的优点 ,达到了优势互
补的效果 ,不仅可以应用于大规模数据集 ,而且可以发现数据
集中任意形状、大小和密度的簇 ,获得了很好的性能.
2 符号与定义
为描述方便 ,引入文献 [ 1, 6 ]中给出的一组记号及相关
概念的定义. 用 N表示数据集 D 包含的记录总数 ,每条记录
有 m个属性 ,其中有 mC 个分类属性和 mN 个数值属性 , m =
mC +mN ,第 i个分类属性 D i 有 ni 个不同的取值 ,为简单起
见 ,假设分类属性位于数值属性之前. K表示对 D 执行一趟
聚类后簇的个数 ; N0 是最终聚类结果包含的簇个数 ; r表示一
趟聚类阈值 ; R I{C i , C j }和 RC {C i , C j }分别是 Cham eleon算法
里两个簇间的相对互连性和相对近似度.
定义 1. 簇 C的摘要信息 CSI (C luster Summ ary Inform a2
tion)定义为 : CSI = { n, C lusterID , Summ a ry} ,其中 n为簇 C的
大小 ( n = | C | ) ; C lus terID 为簇中对象标识号 ID 的集合 ,即记
录该簇由哪些对象构成 ; Summ a ry由分类属性中不同取值的
频度信息和数值型属性的质心构成 ,即 :
Summ a ry = {〈Sta t1 , ⋯, S ta tmC , cmC + 1 , cm C + 2 , ⋯, cm C +mN 〉}
这里 Sta ti = { ( a, F reqC |D i ( a ) ) | a∈C |D i }表示属性 D i ( 1≤ i
≤mC )上不同取值的频度集合 , C |D i表示 D i 在 C上的投影 ,
F reqC |D i ( a )表示属性值 a在 C |D i中出现的频度 ,若 a | C |D i ,
则 F reqC |D i ( a ) = 0; cj表示数值属性 D j (mC + 1≤j≤mC +mN )
的质心.
定义 2. 簇 C1 与 C2 间的距离定义为 d ( C1 , C2 ) =
∑
m
i = 1
d if (C (1)i , C (2)i ) 2 /m,这里 d if ( C (1)i , C (2)i )为 C1 与 C2 在
属性D i上的差异 ,对于分类属性D i其值定义 C1与 C2中 | C1 | ·
| C2 |对对象在属性 D i (1≤ i≤mC )上的距离平均值 :
d if (C (1)i , C (2)i ) = 1 - 1| C1 | · | C2 | ∑p∈C 1 F reqC1 |D i (p i ) ·F reqC 2 |D i
(p i ) = 1 - 1| C1 | · | C2 | ∑q∈C 2 F reqC 1 |D i ( qi ) ·F reqC 2 |D i ( qi )
这里 p = [ p1 , p2 , ⋯, pm ] , q = [ q1 , q2 , ⋯, qm ]是 D 中两个对
象 ;数值属性 D i , d if (C (1)i , C (2)i )定义为两质心间绝对偏差 : d if
(C (1)i , C (2)i ) = | c (1)i - c (2)i | (mC + 1≤ j≤mC + mN ) ,这里 c (1)i ,
c
(2)
i 分别为 C1、C2 对应于属性 D i的质心.
特别地 ,将单个对象看成仅包含一个对象的簇 ,就能计算
两个对象及一个对象与一个簇之间的距离.
定义 3.
(1) Gk 图的每个点表示数据集中的一个数据点 ,若数据
点 a i到另一个数据点 bi的距离值是所有数据点到数据点 bi
的距离值中 k个最小值之一 ,则称数据点 a i是数据点 bi的 k2
最近邻对象 ,在这两个点之间加一条带权边 ,边的权重表示两
个数据点之间的近似度. 对数据集中每一数据点找出它的所
有 k2最近邻对象 ,分别在它们之间加带权边 ,就构造出 Gk 图.
(2)内部互连性 EC {C i }:一个子簇 C i 做极小割截粗略
平分时需要去掉的边的权重之和.
(3) 绝对互连性 EC {C i , C j }:连接子簇 C i 和 C j 之间的
边的权重之和.
(4) 相对互连性 R I{C i , C j }:子簇 C i和 C j之间绝对互连
性关于两个簇间的内部互连性的规范化 ,即 : .
R I{C i , C j } =
2EC {C i , C j }
EC {C i } + EC {C j }
(5) 内部近似度 TC { C i }:一个子簇 C i 做极小割截粗略
平分时需要去掉的边的平均权重.
(6) 绝对近似度 TC { C i , C j }:连接子簇 C i 和 C j 之间的
边的平均权重.
(7) 相对近似度 RC {C i , C j }:子簇 C i 和 C j 之间绝对近
似度关于两个簇间的内部近似度的规范化 ,即 :
RC {C i , C j } =
TC {C i , C j }
| C i |
| C i | + | C j | ×TC {C i } +
| C j |
| C i | + | C j | ×TC {C j }
(8) 相似度函数 :相对互连性与相对近似度这两个指标
的乘积 ,即为 R I{C i , C j } ×RC {C i , C j } a ,其中 a是用户指定的
参数 ,通常大于 1. a取 1表示两个量度标准有相等的权重 ,而
减小 a的值表示 R I{C i , C j }更重要.
Cham eleon算法采用动态建模的层次聚类方法进行聚
类 ,其正确性由下述事实保证 :仅当合并后的结果簇类似于原
来的两个簇时 ,这两个簇才应当合并. Cham eleon算法由三个
关键步骤组成 :稀疏化、图划分和层次聚类. 具体描述如下 :
(1) 由数据集构造成一个 k2最近邻图 Gk;
(2) 通过一个多层图划分算法将图 Gk 划分成大量的子
图 ,每个子图代表一个初始子簇 ;
(3) 合并关于相似度函数 R I{C i , C j } ×RC { C i , C j } a 而
言 ,最好地保持簇的自相似性的簇 ;
(4) 重复步骤 ( 3) ,直至不再有可以合并的簇或者用户
指定停止合并时的簇个数.
Cham eleon算法能够有效地聚类空间数据 ,能识别具有
不同形状、大小和密度的簇 ,对噪声和异常数据不敏感 . Cha2
m eleon算法的时间复杂度为 O (N2 ) ,因此 ,使用 Cham eleon
算法对中小规模数据集的聚类分析是个很好的选择 ,但对于
在大规模数据集其应用受到了限制.
3 Cham eleon算法的改进
将一趟聚类算法的高效性与 Cham eleon算法能发现任意
形状、大小和密度的簇的优点结合 ,提出一种两阶段聚类算
法. 第一阶段 ,使用一趟聚类算法对数据集进行初步划分 ,作
用是对原始数据进行压缩表示 ,将充分接近的对象作为一个
整体对待 ;第二阶段 ,将第一阶段得到的划分中每个簇看成一
个对象 ,利用 Cham eleon算法聚类 ,即使用 Cham eleon算法对
第一阶段获得的聚类结果归并 . 下面描述该算法并分析性能.
3. 1 Cham eleon算法的简单改进
原始 Cham eleon算法及已有改进算法只能用于数值属性
数据 ,不能处理含分类属性的数据 ,定义 2可计算含分类属性
的数据之间的距离 ,采用定义 2可将基本的 Cham eleon算法
进行简单推广 ,使之可以处理含分类属性的数据 ,这种改进的
Cham eleon算法对数据的适应性增强了 ,但其时间复杂度仍
为 O (N2 ) ,不能用于大规模数据集的处理.
3. 2 两阶段聚类算法设计
两阶段聚类算法聚类过程描述如下 :
4461 小 型 微 型 计 算 机 系 统 2010年
Stage 1. 初始聚类的划分
利用一趟聚类算法将数据集 D 分割为半径几乎相同的 k
个簇 : C = {C1 , C2 , ⋯, Ck }. 聚类过程如下 :
(1)初始时 , 簇集合为空 ,读入一个新的对象 ;
(2)以这个对象构造一个新的簇 ;
(3)若已到数据库末尾 ,则转 (6) ,否则读入新对象 ,利用
给定的距离定义 ,计算它与每个已有簇间的距离 ,并选择最小
的距离 ;
(4)若最小距离超过给定的半径阈值 r,转 (2) ;
(5)否则将该对象并入具有最小距离的簇中并更新该簇
各分类属性值的统计频度及数值属性的质心 ,转 (3) ;
(6)结束.
Stage 2. 聚类归并
对第一阶段的聚类结果以 Cham eleon算法进行归并 ,即
将第一阶段得到的每个簇看成一个对象 ,使用 Cham eleon算
法再次聚类 ,对 k个簇 : C = { C1 , C2 , ⋯, Ck }执行 Cham eleon
算法得到 N0 个簇 : C′= {C′1 , C′2 , ⋯, C′N 0 } . 归并过程为 :
(1) 把一趟聚类结果中每个簇看成一个对象 ,计算任意
两个簇之间的相似度 ,得到簇间相似度矩阵 ;
(2) 基于得到的相似度矩阵 ,构造 k2最近邻图 ;
(3) 使用多层图划分算法划分 k2最近邻图 ;
(4) 合并对于相似度函数而言 ,具有最大的值的簇 ;
(5) 重复步骤 (4) ,直至不能合并为止 ,得到 N0 个簇.
3. 3 算法的时间复杂度分析
第一阶段 ,得到初始簇 ,时间复杂度为 O (N ·k ( ∑m Ci = 1 ni
+mN ) ) ,期望的时间复杂度为 O (N·k·m ) [ 6 ] .
第二阶段 ,时间复杂度为 O ( k2 ) .
由于 k
本文档为【Chameleon算法的改进】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。