一种新的滑动窗口模型数据流聚类方法
小型微型计算机系统Journal o f Chi nese Co m puter Sy stem s
2010年12月第12期V o l 31N o .122010
收稿日期:2009 09 08 基金项目:国家自然科学基金项目(60675031)资助. 作者简介:陈荣晖,男,1983年生,硕士研究生,研究方向为智能信息处理理论及应用;王伦文,男,1966年生,博士,副教授,研究方向为计算智能、机器学习等.
一种新的滑动窗口模型数据流聚类方法
陈荣晖
1,2
,王伦文
1
1(电子工程学院309室,安徽合肥230037)2
(电子工程学院研一队,安徽合肥230037)
E m ai:l chenronghu i 1109@https://www.wendangku.net/doc/433491317.html,
摘 要:基于构造型神经网络引入一种新的数据流聚类相似性函数,并根据滑动窗口模型数据流聚类的特点,定义了平均覆盖和重叠覆盖等概念,进而提出基于构造型神经网络的滑动窗口模型数据流聚类算法.该算法可以降低计算量,提高聚类速度.大规模无线电监测数据聚类实验验证了该算法的有效性.
关键词:数据流;聚类;构造型神经网络;滑动窗口
中图分类号:T P311 文献标识码:A 文章编号:1000 1220(2010)12 2355 04
New Clustering A lgorit h m for SlidingW indow M odel Data strea m
CHEN R ong hui 1,2,W AN G L un w en 1
1(309Research D ivisi on of E lectron i c Eng i neeri n g Institute,H ef ei 230037,C h i na )
2
(Th e F irst Tea m o fP ostgraduate D epart m ent at E lectron i c Eng i neering Insti tu t e,H efei 230037,C h i na )
Abstrac t :T he a rtic l e i ntroduces a new c l ustering si m il ar ity ba sed on t he constructi v e neura l net w o rk s .T he conceptions o f av erag e co ver and ove r cov er are def i ned to m eet the need o f sli d i ng w i ndow s m odel da t a strea m c l usteri ng,and t hen a cluster i ng algo rit h m fo r sli d i ng w i ndow s m ode l data strea m is present ba sed on the constructi v e neural net w o rks .It can be fo und that t he calculati on can be lessened and t he speed o f c l ustering can be fa ster w it h the use o f t h is algo r it h m.T he exper i m en tal results o f larg e sca l e comm un i ca tion datase ts de m on strate its effic i ency.K ey word s :data strea m;c l usteri ng;constructive neural ne t w o rk ;sli d i ng w i ndow
1 引 言
近年来,一种区别于传统静态数据的数据形态 数据流,受到越来越多的关注.这种数据模型具有数据量大,潜在无限,到达速度不确定且只能进行一次扫描等特点,对聚类的实时性以及时空复杂度提出了很高的要求
[1]
.
斯坦福大学的S .G uha 提出基于分而治之思想(D iv i de and C onque r)的LO CA L SEARCH 算法.O 'C a llaghan 在LO CA L SEARCH 算法思想的基础上提出了STREAM 算法[2].但这些算法只能描述数据流的聚类结果,不能表达数据流的变化情况,难以挖掘过程规律.C.A g garw a l 第一个提出了可以表达数据流变化情况的聚类算法C l uStrea m 算法[3]
.C l uS trea m 算法是数据流聚类的经典算法,文[4 6]等都是在C luStrea m 算法的基础上提出了自己的算法,但这些算法都是基于界标窗口模型的数据流聚类算法,没有及时地淘汰"旧"数据,不能及时准确反映当前数据的变化情况.
文[7]提出了一种基于滑动窗口的数据流聚类方法C l u W i n ,该算法提出了纳伪拒真指数直方图,实现了滑动窗口模型数据流聚类,能够及时删除了过期数据,减少它们对聚类结果的影响,这种算法聚类质量高,聚类速度较快.但算法采用数据点与聚类中心之间的距离作为相似性函数,通过统计类
中数据的线性和以及平方和来推算聚类块的半径作为相似性阈值,计算相对较繁琐.由于数据流聚类相似性阈值是随着数据的流入动态调整的,数据流入一次,相似性阈值就要调整一次,相似性阈值推算复杂,一定程度上影响了聚类的速度.因此,如果能找到一种新的有效的相似性函数,减小相似性阈值的计算量,就可以提高聚类的速度.
基于上述思想,本文提出一种构造型的数据流聚类算法(C onstructi v e C l usteri ng A lgo rith m fo r D a t a stream ),简称CC l u D S 算法,用于对滑动窗口模型数据流聚类.第二节介绍CC l u D S 算法的原理;第三节详细解析CC lu D S 算法的步骤;第四节通过实验比较CC l u D S 算法与其它算法的优劣性,分析其性能;最后总结本文.
2 CC lu D S 算法原理
构造型神经网络是张铃教授和张钹院士,在M P 神经元几何意义的基础上提出来的.该算法的主要思想是将d 维向量投影到d +1维球面上,把神经网络的设计问题转化成某种求领域覆盖的问题.具体地说,就是将d 维空间中的有界集合D 作变换T:D S d ,映射到S d 是d +1维空间中的超球面上.其中,变换关系为:T (x )=(x,
(R 2-|x |2)),R m ax {|x |,
x !D }.通过变换,将D 一一映射到半径为R 的超球面上,进
而在超球面上对数据进行分析和处理.从而构造一个网络,就等价于求出一组领域,对给定样本集的点,能够用领域覆盖将
它们分隔开来.这样,就将神经网络的最优设计问题转化成某种求最优覆盖的问题.详细内容可参见文献[8,9].2.1 聚类相似性函数的选择
设d 维空间上某一类样本集S n ={ X 1, X 2,?, X n }投影到d +1的超球面上记为{ Y 1, Y 2,?, Y n },用超球面上的一个"球形覆盖领域"来表示该类,该类样本覆盖的中心点为!W =1n
#n
i=1 Y i .如图1所示,由于超球面的半径R 为常量
,
图1 数据投影图
F ig .1 D a ta pro jecti ng
数据点与中心之间夹角余弦
co s i = Y i ?!
W | Y i ||!W |,可以准确地表达数据点与中心点之间的距离,其中i =1,2,?,n.如果用夹角余弦作为相似性函数,根据文[7]中相似性
阈值为各数据点到中心点距离平均值的思想,以所有夹角余弦求平均值co s =1
n (co s 1+co s 2+?+co s n )=|!W
|/R 作为相似性阈值,其中R 为超球面的半径.不难发现相似性阈值的推算比文[7]中要简单很多,且只需统计聚类的中心向量!W ,即各数据点的线性和.这样不但减少了相似性阈值的计算量,而且减小了描述聚类特征的统计量,有效地缩短了聚类时间,提高了聚类速度.
构造型神经网络几何意义明显、运算复杂度低,但是,传统的覆盖思想不能很好地满足滑动窗口模型数据流聚类的需求.为了解决这一问题,本文定义了平均覆盖和重叠覆盖的概念,下面对这些概念进行具体介绍.2.2 CC luDS 算法中的基本概念2.2.1 平均覆盖领域
设d 维空间上样本集S ={ X 1, X 2,?, X t ,?,},集合S 可以聚成k 类,某一聚类中的n 个数据点{ X 1, X 2,?, X n }投影到球面以后记为{ Y 1, Y 2,?, Y n },取一批"球形领域"{C j ,j =
1,2,?,m },使得C j 的中心点!W =1n #n
i=1 Y i
,球形领域边界点
与中心之间的夹角余弦co s =|!W |/R,其中R 为超球面的半径.称这些"球形领域"为平均覆盖领域.2.2.2 聚类特征的表示
设一组在t i 1,?,t i n 时刻到达的d 维数据 X i 1,?, X i n 经过一次非线性变换以后记为 Y i 1,?, Y i n .用一个n +3维的3元组(!W ,n,t)表示聚类特征,其中!W 是这n 个数据聚类后平均覆盖领域的中心点,n 表示覆盖聚类中数据点的个数,t 表示聚类中最近到达的数据点的时间.
不妨把聚类特征记为ConCF ,用ConCF (P )表示一组数据集合P 的聚类特征.要想对数据流进行聚类,数据的聚类特征描述必须具有伸缩性,文[3]的性质1和性质2和文[7]中的性质1都证明了这一点.本文的聚类特征也具有伸缩性.
性质1.相加性C onCF (P 1%P 2)可由ConC F (P 1)和
ConC F (P 2)构建.具体操作如下:
!W =
1
n 1+n 2(n 1
*!W 1+n 2*!W 2);
n =n 1+n 2;
t 为t 1和t 2中较现在相近的时刻点.
性质2.相减性C onCF (P 1-P 2)可由ConC F (P 1)和ConC F (P 2)构建.具体操作如下:
!W =1
n 1-n 2(n 1
*!W 1-n 2*!W 2);
n =n 1-n 2;t 为t 1和t 2中较现在相近的时刻点.2.2.3 重叠覆盖
前面讲到我们用"平均覆盖"C j 来表示聚类结果.为了满足滑动窗口模型数据流聚类的要求,实时删除过时数据对数据流聚类的影响,只用一个覆盖描述聚类结果是不够的,这里借鉴文[7]中聚类特征指数直方图的思想,提出一种重叠覆盖的结构.这种结构不但能很好的满足上述要求,还能很好地保存当前窗口内数据分布情况.
设一重叠覆盖中数据 X i 1,?, X i n ,它们分别在t i 1,?,t i n
时刻到达,投影到超球面记为 Y i 1,?, Y i n ,根据数据到达的先后顺序,用若干个平均覆盖领域C q p 对它们进行覆盖,其中q =0,1,2,?表示覆盖的层数,p =1,2,?表示每一层中第几个覆盖.这些覆盖需要满足下列约束条件:
(1)若i (2)第i 层覆盖含有2i 个数据,由两个第i -1层覆盖合并而成; (3)除了第0层和最高层之外,每层均含有&1/ 或者&1/ +1个覆盖.这里的 为用户自己定义的相对误差(即数据中含有过期数据的比率,0< <1).根据文[7]和文[10]中的理论,我们不难得出若该类中含有n 个数据,则这个重叠覆盖中最多包含[(1/ )+1](l o g( n +1)+1)个覆盖. 从几何意义上看,这些覆盖是对一个子类中某些数据的覆盖,它们重叠在一起,因此我们称之为重叠覆盖,本文把它记为OC ov. 2.2.4 重叠覆盖的维护 图2描述了OC ov 的动态维护过程,图中的虚线覆盖表示该覆盖已经被合并.假设 =0.5(实际上 应该是远远小 图2 重叠覆盖维护过程图F i g.2 M a i n tenance pro ce ss o f OC ov 于1的一个小数,这里只是为了描述方便做的假设).如图所 2356 小 型 微 型 计 算 机 系 统 2010年 示每一个数据点?X i 到达时生成一个0层覆盖,因为只有一个点,实际上0层覆盖只是一个虚拟覆盖,C onCF 只需保存(!W,t ),其中!W 是 X i 的投影值 Y i ,t 为数据点到达的时刻.当数据点 X 4到达时,有4个0层覆盖,由于4>&(1/ ) +1=3,因 此我们将前两个0层覆盖C 01和C 02合并成一个第1层覆盖C 11.在数据点 X 10到达时,C 07和C 08合并成C 14后1层覆盖也出现了4个,需要将C 11和C 12合并成C 21.依此类推逐层构建多层覆盖,其中聚类特征增量维护的具体计算参考性质1、2.从 图中也看出,当数据点n =10时,共有5个覆盖,这也符合最 多有[(1/ )+1](l o g( n +1)+1)=5.33个覆盖的结论.在增量维护一个子类重叠覆盖的同时还需要维护一个总覆盖CC s ,其中s =1,2,?,表示子类的个数.CC s 包含该子类中所有数据点,用ConC F (CC s )表示子类特征. 每一个数据进来,就会有一个数据的时标超出滑动窗口的范围,对于这些过期数据,滑动窗口聚类需要将它们删除,本算法中只要找到这个时标对应的相应覆盖,删除该覆盖即可.在删除某个覆盖后,对应的O Cov 需要进行维护,具体计算参照性质1、2.2.2.5 重叠覆盖(O Co v )的合并 数据流聚类中一个很重要的问题是在聚类过程中,当子类多到内存无法容纳时,需要将一些子类进行合并,文[3]中是对"微簇"进行合并,文[7]中是对特征指数直方图进行合并.这里需要对重叠覆盖进行合并.由于结构和文[7]中聚类特征指数直方图类似,合并O Co v 可以参考E HCF 树的方法,这里不再赘述. 3 CC luDS 算法实现步骤 ?记录一定数量的数据,构建超球面上OC ov 的基本布局;(获取新数据点 X i ,进行非线性变换,得到超球面上数 据 Y i ,若无新数据则转入);?逐个计算 Y i 与各个总覆盖CC s 中心向量!W s 之间的夹角余弦co s s ,若存在co s s |!W s |/R ,将数据点放入相应的O Cov,转入+,否则转入,; ,判断是否存在 s 使得 3R 2+|!W |2/2R ?co s s <|!W s |/R,选出使co s s 最大的 s ,若同时存在两个最大值,则取CC s 中n 较大的一项,将数据点放入相应的O Cov,转入+,否则转入.; .为新数据点创建一个新的OC ov,其总覆盖CC 的顶点!W 定义为 Y i ,半径r 为所有总覆盖中最小半径的1/2; +找到过期的时标,删除其对应的覆盖,若该OC ov 中所有覆盖都被删除,则删除该OC ov; /根据2.2.4所述方法,对有变动的O Co v 进行相应的维护; 0判断O Co v 的数量是否超过内存允许的最大值,如果超过,用2.2.5所述的方法对O Co v 进行合并; 1重复(~0; )结束算法. 对于根据窗口中特征向量C onCF (CC s )(s =1,2,?表示 子类的个数)生成用户所需的聚类结果,只需采用任意一种加权聚类的方法,文[3]中有详细解析.这里不作详细讨论. 4 实验分析与结论 本文的实验平台是Penti u m I V 3.0G Hz 的PC 机,内存为1GH z ,W i ndow X P 专业版操作系统.用V isual C ++实现算 法.将算法与文[7]中C l u W i n 算法比较. 图3 原始时频图F ig .3 O rig i na l ti m e frequency 数据采用无线电监测数据.通过计算机遥控某短波接收 机,使其在15M H z 至16M H z 频段内,按照3KH z 步进,从低到高循环搜索,每2秒循环一次.搜索到任一频点时从接收机的中频输出端采集信号,并经快速傅立叶变换后转化为频域数据,本实验采集了三天的监测数据进行处理,即每一个频点上有129600个数据点.与文[7]中KDD CU P99数据库相似,本实验先将全部数据存储后再构造数据流,用记录的输入顺序作为数据流的记录顺序.聚类时,将 设为0.1,窗口大小等于6小时内采集的数据量,即窗口大小N =10800.其中C l u W i n 算法选择纳伪C lu W i n . 图4 C l u W i n 算法聚类后的时频图 F i g.4 T i m e frequency a fter cluster i ng w it h C l u W i n 图3所示为15M H z 至16M H z 的三天频域数据占度图.其中横轴代表时间,以天为单位,纵轴代表频率,以M H z 为单位,图中点的实虚代表该点对应的时间和频率上信号的有无.图4为用文[7]中的C lu W i n 算法聚类后的时频图,图5为用本文CC l uD S 算法聚类后的时频图.图4、5坐标意义与图3相同.通过对比图4和图5可以看出,监测数据经C l u W i n 算法和CC l uD S 算法聚类后效果差不多,都能较好地显示信号的本来面目. 2357 12期 陈荣晖等:一种新的滑动窗口模型数据流聚类方法 为了更好地分析CC lu D S 算法的优劣性,用两种算法分别对15.3M H z 频点的采样数据聚类,对比分析它们的SS Q 值和聚类时间.SS Q 值是聚类分析中常用的度量指标,它是指平方距离和[3](Su m o fSquaredD istance,简称SSQ ),具体 的 图5 CC l uD S 算法聚类后的时频图 F i g.5 T i m e frequency after c l usteri ng w it h CC l uD S 定义为:设当前时标为T c ,窗口长度为N,处于T c -N 范围内的数据点X i 与其聚类中心C j 之间的距离为dist (X i ,C j ),将所有dist 2(X i ,C j )的和记为SSQ.为减少实验的偶然性,文中的结果是三次实验后的平均值 . 图6 聚类质量对比图F i g.6 Q ua lit y com parison 图7 聚类时间对比图F i g.7 T i m e com par ison 图6显示的是数据量为43200,86400和129600时,窗口内数据经两种算法聚类后的SS Q 值,从图中可以看出这两种算法的聚类质量相差不多. 图7是随着数据量的增加,两种算法聚类所需的时间对比图,横轴代表数据量,纵轴代表聚类时间,以秒为单位.观察图7中可以发现,CC lu D S 算法的聚类速度较C l u W i n 算法有明显的提高. 另外本文还做了一个模拟数据实验.任意选取10个频点的数据集,将10组模拟数据分别插入数据集中,用两种算法分别对这10个频点数据集聚类,判断算法能否将模拟数据正确聚类.实验结果是CC l u D S 算法将10组数据全部正确聚类,而C l u W i n 算法正确聚类9个,说明CC l uD S 算法的正确率要略高于C lu W i n 算法,这也证明了CC lu D S 算法在提高聚类速度的同时,保证了聚类质量. 5 结束语 本文提出一种基于构造型神经网络的滑动窗口模式数据流聚类算法,通过将数据进行非线性变换后聚类,以数据向量与中心向量之间的夹角余弦作为相似性函数,降低了计算量,提高了聚类速度.同时针对滑动窗口模型数据流聚类的特点,采用平均覆盖和重叠覆盖等结构,较好地保存当前窗口内的 数据分布状况,保证了聚类质量.最后用大规模无线电监测数据动态聚类实验验证该算法,实验结果表明这种聚类方法对数据流聚类具有较高的聚类质量和更快的聚类速度.R eferences : [1]Sun Yu fen ,Lu Y an s heng .An ov erv i ew of strea m dat a m i n i ng [J].C o m pu ter S ci ence ,2007,34(1):1 5.[2]G uh a S,M i shra N,M ot w an i R , et a.l C lusteri n g data strea m s [C ].In:FOC S2000,359 366. [3]A ggarw al C,H an J ,W ang J ,et a.l A fra m e w ork for clusteri n g e vo l v i ng dat a strea m s [C ].In:VLDB 2003,81 92. [4]Z huW ei heng ,Y i n Ji an,X ieY i huang .A rb itrary s hape cluster al gorit hm for cl u st eri ng data strea m [J].Jou rnal of Soft w are ,2006,17(3):379 387. [5]Y ang C hun yu ,Z hou J i e .A heterogeneous data strea m cl u steri ng algorit hm [J].C h i nese J ourna lo f Com pu t ers ,2007,30(8):1364 1371. [6]L i u Q i ng bao ,Dai C hao fan ,Deng Su , et a.l G ri d bas ed data stream cl u st eri ng al gorith m [J].C om puter S ci ence ,2007,34(3): 159 161,180. [7]C han g J i an l ong ,C ao Feng ,Zhou Ao y i ng .C lusteri n g evo l v i ng data strea m s over sli d i ng W i ndow s[J].J ou rnal of So ft w are ,2007,18(4):905 918 [8]L i ng Zhang,B o Zhang.A geom etri cal representati on of M cCu l l och p itts neu ralm odel and its app lication s[J].I EEE T ran sacti on s on NeuralN et w ork s ,1999,10:925 929. [9]W ang Lun w en,Zhang L i ng .A rev i e w on the con structive neural net w ork s[J].Pattern Recogn iti on and A rtifi ci a l Intelligence ,2008, 21(1):49 55. [10]DatarM,G i on i s A,I ndyk P ,et a.lM ai n t a i n i ng st rea m statistics o ver sli d i ng W i ndow s[C ].I n:Proc .of t he 13t h AnnualACM SI AM Sy m p . on D is crete A lgo rit hm s (SODA ),San Fran cis co, 2002,635 644. [11]Xu Y i n,Zhou W en ji an g ,W ang Lun w en .A s hort w ave frequen cy hoppi n g si gnal detecti n g m et hod s u it ab le for co m p lex el ectro m agnetic env ironm ent[J].J ourna l of C h i nes e C o m puter Syste m s ,2008,29(9):1750 1754. 附中文参考文献: [1]孙玉芬,卢炎生.数据流挖掘综述[J].计算机科学,2007,34(1): 1 5. [4]朱蔚恒,印 鉴,谢益煌.基于数据流的任意形状聚类算法[J]. 软件学报,2006,17(3):379 387. [5]杨春雨,周 杰.一种混合属性数据流聚类算法[J].计算机学 报,2007,30(8):1364 1371. [6]刘青宝,戴超凡,邓 苏,等.基于网格的数据流聚类算法[J]. 计算机科学.2007,34(3):159 161,180. [7]常建龙,曹 锋,周傲英.基于滑动窗口的进化数据流聚类[J]. 软件学报,2007,18(4):905 918. [9]王伦文,张 铃.构造型神经网络综述[J].模式识别与人工智 能,2008,21(1):49 55. [11]徐 银,周文江,王伦文.一种适合于复杂电磁环境下短波跳 频信号的检测方法[J ].小型微型计算机系统.2008,29(9):1750 1754. 2358 小 型 微 型 计 算 机 系 统 2010年 3)国家自然科学基金(60172012)。刘青宝 博士生,副教授,主要研究方向为数据仓库技术和数据挖掘;戴超凡 博士,副教授,主要研究方向为数据仓库技术和数据挖掘;邓 苏 博士,教授,主要研究方向指挥自动化、信息综合处理与辅助决策;张维明 博士生导师,教授,主要研究方向为军事信息系统、信息综合处理与辅助决策。 计算机科学2007Vol 134№13 基于网格的数据流聚类算法3) 刘青宝 戴超凡 邓 苏 张维明 (国防科学技术大学信息系统与管理学院 长沙410073) 摘 要 本文提出的基于网格的数据流聚类算法,克服了算法CluStream 对非球形的聚类效果不好等缺陷,不仅能在 噪声干扰下发现任意形状的类,而且有效地解决了聚类算法参数敏感和聚类结果无法区分密度差异等问题。关键词 聚类,数据流,聚类参数,相对密度 G rid 2based Data Stream Clustering Algorithm L IU Qing 2Bao DA I Chao 2Fan DEN G Su ZHAN G Wei 2Ming (College of Information System and Management ,National University of Defense Technology ,Changsha 410073) Abstract With strong ability for discovering arbitrary shape clusters and handling noise ,grid 2based data stream cluste 2ring algorithm efficiently resolves these problem of being very sensitive to the user 2defined parameters and difficult to distinguish the density distinction of clusters.K eyw ords Clustering ,Data stream ,Clustering parameter ,Relative density 随着计算机和传感器技术的发展和应用,数据流挖掘技术在国内外得到广泛研究。它在网络监控、证券交易分析、电信记录分析等方面有着巨大的应用前景。特别在军事应用中,为了获得及时的战场态势信息,大量使用了各种传感器,对这些传感器数据流的分析处理已显得极为重要。针对数据流数据持续到达,且速度快、规模大等特点,数据流挖掘技术的研究重点是设计高效的单遍数据集扫描算法[12]。数据流聚类问题一直是吸引许多研究者关注的热点问题,已提出多种一次性扫描的方法和算法,如文[1～4]等等,但它们的聚类结果通常是球形的,不能支持对任意形状类的聚类[5]。 本文提出的基于网格的数据流聚类算法,在有限内存条件下,以单遍扫描方式,不仅能在噪声干扰下发现任意形状的类,而且有效地解决了基于绝对密度聚类算法所存在的高密度聚类结果被包含在相连的低密度聚类结果中的问题。 本文第1节简要介绍数据流聚类相关研究,并引出基于网格的数据流聚类算法的思路及其与相关研究的异同;第2节给出基于网格的数据流聚类算法所使用到的基本概念;第3节给出一个完整的基于网格的数据流聚类算法,详细解析算法的执行过程;第4节进行算法性能分析对比;最后总结本文的主要工作和贡献,并指出需要进一步研究和改进的工作。 1 相关研究 在有限内存约束下,一般方法很难对数据流进行任意形状的聚类。第一个增量式聚类挖掘方法是文[6]提出的In 2crementalDBSCAN 算法,它是一个用于数据仓库环境(相对稳定的数据流)的有效聚类算法,可以在有噪声的数据集中发现任意形状的类。但是,它为了形成任意形状的类,必须用类中的所有点来表示,要求获得整个数据流的全局信息,这在内存有限情况下是难以做到的。而且,它采用全局一致的绝对 密度作参数,使得聚类结果对参数值非常敏感,设置的细微不同即可能导致差别很大的聚类结果。 Aggarwal 在2003年提出的一个解决数据流聚类问题的框架CluStream [1]。它使用了两个过程来处理数据流聚类问题:首先,使用一个在线的micro 2cluster 过程对数据流进行初级聚类,并按一定的时间跨度将micro 2cluster 的结果按一种称为pyramid time f rame 的结构储存下来。同时,使用另一个离线的macro 2cluster 过程,根据用户的具体要求对micro 2cluster 聚类的结果进行再分析。但它采用距离作为度量参数,聚类结果通常是球形的,不能支持对任意形状类的聚类。而且,它维护的是micro 2cluster 的聚类特征向量(CF 2x ;CF 1x ;CF 2t ;CF 1t ;n ),这在噪声情况下,会产生干扰误差。 2006年,Feng Cao 等人在文[5]中提出了针对动态进化数据流的DenStream 算法。它相对CluStream 有很大的改进,继承了IncrementalDBSCAN 基于密度的优点,能够支持对有噪声的动态进化(非稳定)的数据流进行任意形状的聚类。但由于采用全局一致的绝对密度作参数,使得聚类结果对参数值非常敏感。同时,与CluStream 算法相比,它只能提供对当前数据流的一种描述,不能反映用户指定时间窗内的流数据的变化情况。 朱蔚恒等在文[13]中提出的基于密度与空间的ACluS 2tream 聚类算法,通过引入有严格空间的意义聚类块,在对数据流进行初步聚类的同时,尽量保留数据的空间特性,有效克服了CluStream 算法不能支持对任意形状聚类的缺陷。但它在处理不属于已有聚类块的新数据点时,使用一种类似“抛硬币”的方法来猜测是否为该点创建一个新的聚类块,误差较大。而且它以绝对密度做参考,所以在聚类结果中无法区分密度等级不同的簇[7]。 本文提出的基于网格的数据流聚类算法GClustream Density-Based Clustering for Real-Time Stream Data 基于密度的实时数据流聚类(D-Stream) 翻译by muyefei E-mail: muyefei@https://www.wendangku.net/doc/433491317.html, 注释：版权归作者所有，文档仅用于交流学习，可以用大纲视图查看文档结构 摘要：现有的聚类算法比如CluStream是基于k-means算法的。这些算法不能够发现任意形状的簇以及不能处理离群点。而且，它需要预先知道k值和用户指定的时间窗口。为了解决上述问题，本文提出了D-Stream算法，它是基于密度的算法。这个算法用一个在线部分将数据映射到一个网格，在离线部分计算网格的密度然后基于密度形成簇。算法采用了密度衰减技术来捕获数据流的动态变化。为了探索衰减因子、数据密度以及簇结构之间的关系，我们的算法能够有效的并且有效率地实时调整簇。而且，我们用理论证明了移除那些属于离群点的稀疏网格是合理的，从而提高了系统的时间和空间效率。该技术能聚类高速的数据流而不损失聚类质量。实验结果表明我们的算法在聚类质量和效率是有独特的优势，并且能够发现任意形状的簇，以及能准确地识别实时数据流的演化行为。 关键词 流数据挖掘基于密度的聚类D-Stream 分散的网格 1 介绍 实时聚类高维数据流是困难的但很重要。因为它在各个领域应用到。比如... 聚类是一项关键的数据挖掘任务。挖掘数据流有几项关键的挑战： （1）单遍扫描 （2）将数据流视为数据一个很长的向量在很多应用中捉襟见肘，用户更加关注簇的演化行为。 近来，出现了许多数据流聚类方法。比如STREAM、CluStream以及扩展（在多数据流，分布式数据流，并行数据流上的扩展）等。 CluStream以及扩展的算法有以下一些缺陷： 1、只能发现球形簇，不能发现任意形状的簇。 2、不能够识别噪声和离群点。 3、基于k-means的算法需要多次扫描数据（其实CluStream利用两阶段方法和微簇解决了该问题）。 基于密度的聚类算法介绍。基于密度的方法可以发现任意形状的簇，可以处理噪声，对原始数据集只需一次扫描。而且，它不需要像k-means算法那样预先设定k值。 文本提出了D-Stream,一种基于密度的数据流聚类框架。它不是简单用基于密度的算法替代k-means的数据流算法。它有两项主要的技术挑战： 首先，我们不大愿意将数据流视为静态数据很长的一个序列，因为我们对数据流演化的时间特征更加感兴趣。为了捕获簇的动态变化，我们提出了一个新颖的方案，它可以将衰减 【子空间聚类】Sparse Subspace Clustering(SSC) Algorithm Symbol definition： is n linear subspace of . is the dimentsion of . is N noise-free data points. is a rank- matrix, represent (>) points that lie in . is a unknown permutation matrix. SSC Algorithm: Step 1: Solve the sparse optimization program ①Uncorrupted data ②Corrupted data ps: E corresponds to a matrix of sparse outlying entries, and Z is a noise matrix. Step 2: Normalize the columns of C as . ps: max norm : . Step 3: Form a similarity grahp with N nodes wegiths on the edges between the nodes by . ps: Step: Use spectral clustering to the similarity graph. Output: . Subspace-Sparse Recovery Theory Definition: ① ps: is said to be independent. ② ③Principle angle between and Sparse subspace clustering:Algorithm,theory,and Application 稀疏子空间聚类（SSC）的算法，理论和应用 参考文献： 1、E. Elhamifar and R. Vidal. Sparse subspace clustering: Algorithm,theory,and Application. IEEE Transactions on Pattern Analysis and Machine Intelligence,2013 2、E. Elhamifar and R. Vidal. Sparse subspace clustering. In CVPR, 2009 2013年的这篇论文写得比09年那篇容易懂一些，讨论和实验也更详细。2013年的这篇可以看成是09那篇会议的扩展版。 一、算法 数据没有损坏，求解模型（5）获得矩阵C： 数据有损坏（noise and sparse outlying entries)，求解模型（13）获得矩阵C： 仿射子空间模型： 二、理论 1、independent子空间 设rank(Yi)=di，Yi表示从第i个子空间Si抽取的Ni个样本构成的矩阵，di 表示Si的维数。论文的定理1表明，模型（5）的解C*是一个块对角矩阵，属于同一个子空间的数据间的cij可能非零，不属于同一个子空间的数据间的cij=0. 2、disjoint子空间 对于disjoint子空间，除了满足条件rank(Yi)=di外，还需要满足公式（21）： 则可获得与independent子空间下类似的结论： 数据流挖掘中的聚类方法综述 徐天音? (南京大学计算机科学与技术系, 南京 210093) A Survey of Clustering Methods in Mining Data Streaming Tianyin Xu* (Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China) Abstract: The research to data streaming model has recently gained a high attraction due to its applications, including real-time surveillance systems, network intrusion detection and click streams. Clustering, one of the most important problems in streaming mining, has recently been highly explored because its application to data summarization and outlier detection. Due to the characteristics of data streaming against traditional data mining technique, new requirements and challenges have been proposed. This paper is a survey of various kinds of clustering methods in mining data streaming. In this paper, we’ll make an effort to review the state-of-the-art of clustering methods of data streaming mining and provide a big picture of this domain. To achieve this goal, we’ll first introduce the basic concepts, requirements and fundamental techniques. Then, we’ll look back into history to track the development of the clustering methods. After describing some classic and popular clustering algorithms, we’ll discuss what problems have already been solved. At last, we’ll put forward some further research issues in this domain. Key words: Clustering; Data Streaming; Data Mining; Clustering Data Streaming; Streaming Mining 摘 要: 近期，随着诸如实时监控系统、网络入侵检测和web上用户点击流等动态的应用环境源源不断地产生海量的、时序的、快速变化的和潜在无限的数据流，对数据流挖掘的研究变得重要而富有意义。聚类分析作为数据流挖掘领域的一个重要问题，在近期被高度重视和广泛研究。由于数据流模型不同于传统数据集的特殊性质，新的要求和挑战应运而生。本文对数据流挖掘中各种聚类分析算法和处理框架做了综述。文章力图回顾数据流聚类分析领域的最近发展水平，提供给读者该领域的一个清晰的蓝图。为了实现这个目标，我们将首先介绍数据流聚类的基本概念、要求和底层的支撑技术。然后，我们将回顾历史，追寻各类数据流聚类算法和处理框架的发展轨迹将有助于深入理解这些算法。在详细描述一些经典和流行的聚类算法和处理框架后，我们将讨论该领域中哪些问题已经得到解决。最后，我们将展望未来，提出数据流聚类领域中进一步的研究热点和研究方向。 关键词: 聚类; 数据流; 数据挖掘; 数据流聚类; 数据流挖掘 ?作者简介: 徐天音，南京大学计算机科学与技术系，研究生 稀疏子空间聚类算法与模型建立 稀疏子空间聚类是一种基于谱聚类的子空间聚类方法， 基本思想：假设高位空间中的数据本质上属于低维子空间，能够在低维子空间中进行线性表示,能够揭示数据所在的本质子空间, 有利于数据聚类. 基 本方法是, 对给定的一组数据建立子空间表示模型,寻找数据在低维子空间中的表示系数, 然后根据表示系数矩阵构造相似度矩阵, 最后利用谱聚类方法如规范化割(Normalized cut, Ncut)[22] 获得数据的聚类结果。 基本原理 稀疏子空间聚类[32] 的基本思想是: 将数据 αS x i ∈表示为所有其他数据的线性组合, j i j ij i x Z x ∑≠= （1） 并对表示系数施加一定的约束使得在一定条件下对所有的αS x j ?, 对应的0=ij Z 。将所有数据及其表示系数按一定方式排成矩阵 ，则式（1）等价于 XZ X = （2） 且系数矩阵N N R Z ?∈ 满足: 当i x 和j x 属于不同的子空间时, 有0=ij Z . 不同于用一组基或字典表示数据, 式（2）用数据集本身表示数据, 称为数据的自表示. 若已知数据的子空间结构, 并将数据按类别逐列排放, 则在一定条件下可使系数矩阵Z 具有块对角结构, 即 ????? ???????=k Z Z Z Z 00000021 （3） 这里),,1(k Z =αα 表示子空间αS 中数据的表示系数矩阵; 反之, 若Z 具有块对角结构, 这种结构揭示了数据的子空间结构. 稀疏子空间聚类就是通过对系数矩阵Z 采用不同的稀疏约束, 使其尽可能具有理想结构, 从而实现子空间聚类. Elhamifar 等[32] 基于一维稀疏性提出了稀疏子空间聚类(Sparse subspace clustering,SSC) 方法, 其子空间表示模型为 1min Z Z 0,..==ii Z XZ X t s （4） 第27卷第2期通化师范学院学报Vol.27No.2 2006年3月JOURNAL OF TON GHUA TEACHERS’COLL EGE Mar.2006 数据流聚类算法研究① 赵法信1,刘俊岭2 (1.通化师范学院网络中心,吉林通化134002;2.沈阳建筑大学计算中心辽宁沈阳110004) 摘 要:数据流是一类新的数据对象,流挖掘是数据库领域的研究热点,有很大的应用前景.本文 首先综述了传统聚类算法的分类及其各自特点,并对它们进行了分析评价.然后结合流聚类分析的要 求,对目前最新的几个数据流聚类研究成果进行了分析,并对数据流聚类进一步的研究方向进行了讨 论. 关键词:数据挖掘;聚类分析;数据流;数据流聚类 中图分类号:TP311.13 文献标识码:A 文章编号:1008-7974(2006)02-0029-04 近年来,越来越多的应用产生数据流,它不同于传统的存储在磁盘上的静态的数据,而是一类新的数据对象,它是连续的、有序的、快速变化的、海量的数据[1].典型的数据流包括网络与道路交通监测系统的监测信息数据、电信部门的通话记录数据、由传感器传回的各种监测数据、股票交易所的股票价格信息数据以及环境温度的监测数据等.数据流分析是数据流研究的一个重要方向,目前的研究主要包括数据流聚类、分类、频繁模式以及数据流OLAP等[3][4][5].数据流本身的特点决定了数据流聚类与传统数据聚类的不同,本文根据数据流本身的特点分析了数据流对聚类的要求以及数据流聚类方面的最新研究成果,并对数据流聚类下一步的研究方向进行了讨论. 1 传统聚类分析 随着数据聚类的蓬勃发展,各种聚类算法相继提出,每一种算法都是针对不同的情况而设计的,在数据挖掘领域对聚类算法的要求主要有以下几个方面[2]:算法的可伸缩性、对所处理属性值的要求、对数据分布的适应性、最少的参数和确定参数值的领域知识、有效地识别噪声数据、对于输入顺序的敏感性、高维性、基于约束的聚类以及聚类结果的可解释性和可用性.许多聚类算法都是为特定的领域设计的,都有各自的特点和应用范围,因而任何聚类算法都不可能在每个标准上都优越于其它算法.传统的聚类算法主要分为基于划分的方法(如K-means[6])、基于层次的方法(如BIRCH[7])、基于密度的方法(如DB2 SCAN[8])、基于网格的方法(如CL IQU E[9])及基于模型的方法(如COBWEB[10]).本文对这些算法进行了研究,对它们的性能在以下几个方面进行了比较分析: 表1 聚类算法的比较 类别算法聚类 质量 可伸缩性聚类形状 输 入 敏感性 噪声处 理能力 数据 类型 基于划分K-means差球状是差数值 PAM差球状是好数值 CLARANS好球状是好数值基于层次A GN ES差球状不差数值 BIRCH好好球状是好数值 CURE好好任意不好数值 ROCK好好任意不好分类 Chameleon较好好任意不好数值基于密度DBSCAN好好任意不好数值 OPTICS好好任意不好数值 DENCLU E较好一般任意不好数值基于网格STIN G一般好任意不好数值 CL IQU E一般好任意不好数值 WaveCluster一般好任意不好数值基于模型COBWEB好差特定不好分类 CLASSIT好差特定不好数值 ①收稿日期:2005-05-08 作者简介:赵法信(1974-),男,河南浚县人,硕士,通化师范学院工程师,主要研究领域为数据仓库与数据挖掘. 计算机研究与发展ＤＯＩ：１０．７５４４桙ｉｓｓｎ１０００‐１２３９．２０１６．２０１４８３６２ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ５３（７）：１６０５１６１１，２０１６ 收稿日期：２０１４－１２－０９；修回日期：２０１５－０６－０９ 基金项目：国家自然科学基金项目（６１３７３０５５）；江苏省自然科学基金项目（ＢＫ２０１４０４１９）；江苏省高校自然科学研究计划重大项目 （１４ＫＪＢ５２０００１） ＴｈｉｓｗｏｒｋｗａｓｓｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ（６１３７３０５５），ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＪｉａｎｇｓｕＰｒｏｖｉｎｃｅｏｆＣｈｉｎａ（ＢＫ２０１４０４１９），ａｎｄｔｈｅＭａｊｏｒＰｒｏｇｒａｍｏｆＲｅｓｅａｒｃｈＰｌａｎｏｆｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅｉｎＨｉｇｈｅｒＥｄｕｃａｔｉｏｎｏｆＪｉａｎｇｓｕＰｒｏｖｉｎｃｅｏｆＣｈｉｎａ（１４ＫＪＢ５２０００１）． 通信作者：吴小俊（ｗｕ＿ｘｉａｏｊｕｎ＠ｊｉａｎｇｎａｎ．ｅｄｕ．ｃｎ）基于分布式低秩表示的子空间聚类算法 许 凯 吴小俊 尹贺峰 （江南大学物联网工程学院 江苏无锡 ２１４１２２） （ｘｕｋａｉ３４７＠ｓｉｎａ．ｃｏｍ） ＤｉｓｔｒｉｂｕｔｅｄＬｏｗＲａｎｋＲｅｐｒｅｓｅｎｔａｔｉｏｎ‐ＢａｓｅｄＳｕｂｓｐａｃｅＣｌｕｓｔｅｒｉｎｇＡｌｇｏｒｉｔｈｍＸｕＫａｉ，ＷｕＸｉａｏｊｕｎ，ａｎｄＹｉｎＨｅｆｅｎｇ（ＳｃｈｏｏｌｏｆＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓＥｎｇｉｎｅｅｒｉｎｇ，ＪｉａｎｇｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｗｕｘｉ，Ｊｉａｎｇｓｕ２１４１２２） Ａｂｓｔｒａｃｔ Ｖｉｓｉｏｎｐｒｏｂｌｅｍｒａｎｇｉｎｇｆｒｏｍｉｍａｇｅｃｌｕｓｔｅｒｉｎｇｔｏｍｏｔｉｏｎｓｅｇｍｅｎｔａｔｉｏｎｃａｎｎａｔｕｒａｌｌｙｂｅｆｒａｍｅｄａｓｓｕｂｓｐａｃｅｓｅｇｍｅｎｔａｔｉｏｎｐｒｏｂｌｅｍ，ｉｎｗｈｉｃｈｏｎｅａｉｍｓｔｏｒｅｃｏｖｅｒｍｕｌｔｉｐｌｅｌｏｗｄｉｍｅｎｓｉｏｎａｌｓｕｂｓｐａｃｅｓｆｒｏｍｎｏｉｓｙａｎｄｃｏｒｒｕｐｔｅｄｉｎｐｕｔｄａｔａ．Ｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｕｂｓｐａｃｅｓｅｇｍｅｎｔａｔｉｏｎａｌｇｏｒｉｔｈｍ（ＬＲＲ）ｆｏｒｍｕｌａｔｅｓｔｈｅｐｒｏｂｌｅｍａｓａｃｏｎｖｅｘｏｐｔｉｍｉｚａｔｉｏｎａｎｄａｃｈｉｅｖｅｓｉｍｐｒｅｓｓｉｖｅｒｅｓｕｌｔｓ．Ｈｏｗｅｖｅｒ，ｉｔｎｅｅｄｓｔｏｔａｋｅａｌｏｎｇｔｉｍｅｔｏｓｏｌｖｅｔｈｅｃｏｎｖｅｘｐｒｏｂｌｅｍ，ａｎｄｔｈｅｃｌｕｓｔｅｒｉｎｇａｃｃｕｒａｃｙｉｓｎｏｔｈｉｇｈｅｎｏｕｇｈ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ（ＤＬＲＲＳ）．ＤＬＲＲＳａｄｏｐｔｓｔｈｅｄｉｓｔｒｉｂｕｔｅｄｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇｔｏｇｅｔｔｈｅｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ，ｔｈｅｎｔａｋｅｔｈｅａｂｓｏｌｕｔｅｖａｌｕｅｏｆｅａｃｈｅｌｅｍｅｎｔｏｆｔｈｅｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ，ａｎｄｒｅｔａｉｎｔｈｅｋｌａｒｇｅｓｔｃｏｅｆｆｉｃｉｅｎｔｓｐｅｒｃｏｌｕｍｎａｎｄｓｅｔｔｈｅｏｔｈｅｒｅｌｅｍｅｎｔｓｔｏ０ｔｏｇｅｔａｎｅｗｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ．Ｆｉｎａｌｌｙ，ＤＬＲＲＳｐｅｒｆｏｒｍｓｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇｏｖｅｒｔｈｅｎｅｗｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ．Ｂｕｔｉｔｄｏｅｓｎ摧ｔｈａｖｅｉｎｃｒｅｍｅｎｔａｌｌｅａｒｎｉｎｇｆｕｎｃｔｉｏｎ，ｓｏｔｈｅｒｅｉｓａｓｃａｌａｂｌｅｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ（ＳＤＬＲＲＳ）ｈｅｒｅ．Ｉｆｎｅｗｓａｍｐｌｅｓａｒｅｂｒｏｕｇｈｔｉｎ，ＳＤＬＲＲＳｃａｎｕｓｅｔｈｅｆｏｒｍｅｒｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｔｏｃｌａｓｓｉｆｙｔｈｅｎｅｗｓａｍｐｌｅｓｔｏｇｅｔｔｈｅｆｉｎａｌｒｅｓｕｌｔ．ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｏｎＡＲａｎｄＥｘｔｅｎｄｅｄＹａｌｅＢｄａｔａｓｅｔｓｓｈｏｗｔｈａｔｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｓｃａｎｎｏｔｏｎｌｙｏｂｖｉｏｕｓｌｙｒｅｄｕｃｅｔｈｅｒｕｎｎｉｎｇｔｉｍｅ，ｂｕｔａｌｓｏａｃｈｉｅｖｅｈｉｇｈｅｒａｃｃｕｒａｃｙ，ｗｈｉｃｈｖｅｒｉｆｉｅｓｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｓａｒｅｅｆｆｉｃｉｅｎｔａｎｄｆｅａｓｉｂｌｅ．Ｋｅｙｗｏｒｄｓ ｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ；ｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇ；ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ；ｉｎｃｒｅｍｅｎｔａｌｌｅａｒｎｉｎｇ；ｃｏｅｆｆｉｃｉｅｎｔｓｒｅｃｏｎｓｔｒｕｃｔｉｏｎ 摘 要 针对基于低秩表示的子空间分割算法运算时间较长、 聚类的准确率也不够高，提出一种基于分布式低秩表示的稀疏子空间聚类算法（ｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ，ＤＬＲＲＳ），该算法采用分布式并行计算来得到低秩表示的系数矩阵，然后保留系数矩阵每列的前ｋ个绝对值最大系数，其他系数置为０，用此系数矩阵构造一个稀疏的样本关系更突出的相似度矩阵，接着用谱聚类得到聚类结果．但是其不具备增量学习功能，为此再提出一种基于分布式低秩表示的增量式稀疏子空间聚类算法（ｓｃａｌａｂｌｅｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ，ＳＤＬＲＲＳ），如果有新增样本，可以利用前面的聚类结果对新增样本进行 聚类分析中几种算法的比较 2009-04-13 23:12 将数据库中的对象进行聚类是聚类分析的基本操作，其准则是使属于同一类的个体间距离尽可能小，而不同类个体间距离尽可能大，为了找到效率高、通用性强的聚类方法人们从不同角度提出了近百种聚类方法，典型的有K-means 方法、K-medoids方法、CLARANS方法,BIRCH方法等，这些算法适用于特定的问题及用户。本文综合提出了评价聚类算法好坏的5个标准，基于这5个标准，对数据挖掘中常用聚类方法作了比较分析，以便于人们更容易、更快捷地找到一种适用于特定问题及用户的聚类算法。 聚类算法研究及比较框架 聚类算法一般有五种方法，最主要的是划分方法和层次方法两种。划分聚类算法通过优化评价函数把数据集分割为K个部分，它需要K作为输人参数。典型的分割聚类算法有K-means算法, K-medoids算法、CLARANS算法。层次聚类由不同层次的分割聚类组成，层次之间的分割具有嵌套的关系。它不需要输入参数，这是它优于分割聚类算法的一个明显的优点，其缺点是终止条件必须具体指定。典型的分层聚类算法有BIRCH算法、DBSCAN算法和CURE算法等。 对各聚类算法的比较研究基于以下5个标准： ①是否适用于大数据量，算法的效率是否满足大数据量高复杂性的要求; ②是否能应付不同的数据类型，能否处理符号属性; ③是否能发现不同类型的聚类; ④是否能应付脏数据或异常数据; ⑤是否对数据的输入顺序不敏感。 下面将在该框架下对各聚类算法作分析比较。 数据挖掘常用聚类算法比较分析 3.1 K-pototypes算法 K-pototypes算法结合了K-means方法和根据K-means方法改进的能够处理符号属性的K-modes方法，同K-means 方法相比，K-pototypes 算法能够处理符号属性。 3.2 CLARANS算法（划分方法） CLARANS算法即随机搜索聚类算法，是一种分割聚类方法。它首先随机选择一个点作为当前点，然后随机检查它周围不超过参数Maxneighbor个的一些邻接点，假如找到一个比它更好的邻接点，则把它移人该邻接点，否则把该点作为局部最小量。然后再随机选择一个点来寻找另一个局部最小量，直至所找到的局部最小量数目达到用户要求为止。该算法要求聚类的对象必须都预先调人内存，并且需多次扫描数据集，这对大数据量而言，无论时间复杂度还是空间复杂度都相当大。虽通过引人R-树结构对其性能进行改善，使之能够处理基于磁盘的大型数据库，但R*-树的构造和维护代价太大。该算法对脏数据和异常数据不敏感，但对数据物人顺序异常敏感，且只能处理凸形或球形边界聚类。 3.3 BIRCH算法（层次方法） BIRCH算法即平衡迭代削减聚类法，其核心是用一个聚类特征3元组表示一个簇的有关信息，从而使一簇点的表示可用对应的聚类特征，而不必用具体的一组点来表示。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。BIRCH算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法的聚类特征树是一个具有两个参数分枝因子B和类直径T的高度平衡树。分枝因子规定了树的每个节点子女的最多个数，而类直径体现了对一类点的直径大小的限制即这些点在多大范围内可以聚为一类，非叶子结点为它的子女的最大关键字，可以根据这些关键字进行插人索引，它总结了其子女的信息。 聚类特征树可以动态构造，因此不要求所有数据读人内存，而可以在外存上逐个读人。新的数据项总是插人到树中与该数据距离最近的叶子中。如果插人后使得该叶子的直径大于类直径T，则把该叶子节点分裂。其它叶子结点也需要检查是否超过分枝因子来判断其分裂与否，直至该数据插入到叶子中，并且满足不超过类直径，而每个非叶子节点的子女个数不大于分枝因子。算法还可以通过改变类直径修改特征树大小，控制其占内存容量。 BIRCH算法通过一次扫描就可以进行较好的聚类，由此可见，该算法适合于大数据量。对于给定的M兆内存空间，其空间复杂度为O(M)，时间间复杂度为O(dNBlnB(M/P)).其中d为维数,N为节点数,P为内存页的大小，B为由P决定的分枝因子。I/O花费与数据量成线性关系。BIRCH算法只适用于类的分布呈凸形及球形的情况，并且由于BIRCH算法需提供正确的聚类个数和簇直径限制，对不可视的高维数据不可行。 3.4 CURE算法（层次方法） CURE算法即使用代表点的聚类方法。该算法先把每个数据点看成一类，然后合并距离最近的类直至类个数为所要求的个数为止。CURE算法将传统对类的表示方法进行了改进，回避了用所有点或用中心和半径来表示一个类，而1基于网格的数据流聚类算法
数据流聚类算法D-Stream
子空间聚类Sparse Subspace Clustering SSC
【子空间聚类】Sparse Subspace Clustering(SSC) Algorithm=
数据流挖掘中的聚类方法综述
稀疏子空间聚类算法
数据流聚类算法研究
基于分布式低秩表示的子空间聚类算法
聚类分析中几种算法的比较