Chameleon算法的改进

小 型 微 型 计 算 机 系 统 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之间绝对互连 性关于两个簇间的内部互连性的 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 化 ,即 : . 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