数据挖掘算法
第27卷第7期
2007年7月
文章编号:1001-9081(2007)07-1680-05
计算机应用
ComputerApplications
Vol.27No.7
July2007
一种适用于高维数据流的子空间聚类方法
颜晓龙,沈 鸿
(中国科学技术大学计算机科学技术系,合肥230027)
(hongshen@ustc.edu.cn)
摘 要:受频繁模式挖掘中FP树算法的启发,结合静态高维数据聚类中CLIQUE算法所体现的思想,设计一种树形数据结构DenseGrid树(简称DG树),以记录用于聚类的数据流摘要信息,并通过搜索树中路径从高维数据流中发现存在聚类的低维子空间,从而将高维空间聚类问题转化成构造DG树并利用这种树形数据结构搜索高密网格单元的过程。实验表明,类效果和伸缩性。
关键词:数据挖掘;高维;数据流;子空间;聚类;FP中图分类号:TP311.13 文献标志码:ensionaldatastream
YANXiao2long,SHENHong
(DmofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,
HefeiAnhui230027,China)
Abstract:InspiredbytheFPalgorithmusedinminingfrequentpatternsandtheideausedinCLIQUEwhichisaclassicalmethodforclusteringstaticdata,anewdatastructurenameddensegrid2tree(DG2treeforshort)wasproposedtorecordthesynopsisofthedatastreamsforclustering.
Thentheclusteringproblemwastransformedtotheproblemof
constructingaDG2treeandsearchingfordensegridcellsintheDG2tree.WiththehelpofDG2tree,thesubspacecontainingclusterswasfound.Experimentalresultsshowthatthismethodhasgoodclusterquality.
Keywords:datamining;highdimension;datastreams;subspace;clustering;FP2tree
0 引言
近些年,随着网络技术的高速发展,面向数据流的服务
(如点击流分析,日志分析等)大量涌现。基于数据流模型的
有数据量大、潜在无限、到达速率不确定等特点,所以要求数据流聚类算法具有能够在有限的内存空间上执行,对数据进行一次或较少次数的线性扫描的能力[3]。这些限制条件无疑大大增加了设计数据流聚类算法,特别是用于高维数据流的聚类算法的挑战。
数据挖掘算法已成为重要的研究课题。聚类分析作为一种非常重要的数据挖掘方法,在面向数据流的服务中有着非常广泛的应用前景。对于聚类问题我们可以简单地做如下描述,
即希望根据某种相似度判别依据(如欧式距离、马氏距离等)将数据集分为若干类,使得类间数据的相似度较小而类内数据的相似度较大。传统的聚类算法往往需要多遍扫描数据集,因此大都不能直接应用到数据流上。在高维数据上进行聚类分析所面临的困难主要有两点:1)高维数据的许多维度往往是不相关的,这些不相关的维度彼此视对方为噪声,从而将大量有意义的聚类信息埋藏在毫无意义的噪声之中;2)针对高维数据的算法往往会陷入一种称为维度灾难的效应,这是因为,高维数据的稀疏性导致了在高维空间中数据点之间的距离趋于一致,从而使大量在低维空间中很有效的数据分析技术,随着数据维度的增长而逐渐失效,甚至无法工作
[1,2]
1 研究进展
和数据流相关的研究发展非常迅速,目前已经有了一些专门针对数据流设计的聚类算法:如LOCAL2SEARCH算
[5][6][7]法[4]、STREAM算法、CluStream算法和CD2STREAM
算法。但这些算法有一个共同点,即只适用于低维数据流,对高维数据流聚类效果不佳。
2004年C.Aggarwal,JiaweiHan,PhilipYu等人提出了HPStream算法
[8]
,该算法是对CluStream算法的改进,它采用
投影技术解决了数据流的高维聚类问题,但要求用户输入平均聚类维数———参数l,这在实际应用中往往比较困难,同时也没有解决对非凸形状聚类的问题[9]。
2005年周晓云、杨宜东等人提出了SHStream算法
[9]
,这
。图1是在3维空间的两个2维子空间中各存在两个
簇的例子,尽管3维并不是一个很高的维度,但我们仍然可以从中看出维度效应对聚类分析过程的影响。
在数据流上进行聚类比普通的聚类面临更多的困难。数据流可以被看作是一系列按序到达的数据点。由于数据流具
是一种基于Hoeffding界的高维数据流的子空间聚类算法。算法首先将数据流分段(分段长度由Hoeffding界确定),然后在数据分段上进行子空间聚类,并通过迭代逐步得到满足聚类精度要求的聚类结果,同时,针对数据流的动态性,算法对
[10]
聚类结果进行调整和维护。但由于这种算法是对CLIQUE
收稿日期:2007-01-22;修回日期:2007-03-23。 基金项目:中国科学院“百人计划”资助项目。
作者简介:颜晓龙,男,安徽淮南人,硕士研究生,主要研究方向:数据流挖掘; 沈鸿,男,教授,博士生导师,主要研究方向:并行与分布计算、高性能网络、数据挖掘。
一种基于网格方法的高维数据流子空间聚类算法_工学_高等教育_教育专区。数据... 2一种适用于高维数据流的... 6页 1下载券 高维分类属性的子空间聚... ...
一种适用于高维数据流的子... 1人阅读 6页 2.00元 一种大规模高维数据...一种基于Hoeffding界的高维数据流的子空间聚类发现及维护算法--SHStream.算法将...
高维数据流的自适应子空间聚类算法* 任家东 1,2, 周玮玮 1+, 何海涛 1 ...但是, 它没有考虑 历史数据的衰减问题, 当被适用于高维数据流的 聚类时, ...
一种基于数据流的软子空间聚类算法朱 林 1,2, 雷景生 1, 毕忠勤 1, 杨...处理技术的聚类算法,不能很好地应用于高维 数据流或大规模数据的聚类研究中....
一种高维数据集的子空间聚类算法_信息与通信_工程科技_专业资料 暂无评价0人阅读0次下载举报文档 一种高维数据集的子空间聚类算法_信息与通信_工程科技_专业...
2一种适用于高维数据流的子... 2基于分层聚类的k_means算... 2基于子...[ 5 ] 和基于 Hoeff ding 界的高维数据的子空间聚类方法 [ 6 ] 等1 其...
出一种 处理 高维分类数据 集的子 空间聚类 算法( FP—Tree—based SUBspaee clusetring algorithm, FPSUB),利用频 繁模 式树 将 聚类 问题 转化为 寻找 属性...
今后的发展趋势,即 在子空间聚类过程中融入其他传统聚类方法的思想,以提高聚类... 2一种适用于高维数据流的... 6页 1下载券喜欢此文档的还喜欢...
的发展趋势, 即 在子空间聚类过程中融入其他传统聚类方法的思想, 以提高聚类...研究 致力于 减小甚至消除 维度 灾难对 高维 数据 处理 的影 响 [ 1, 2]...
热门文档