文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 2一种适用于高维数据流的子空间聚类方法
侵权投诉

2一种适用于高维数据流的子空间聚类方法

数据挖掘算法

第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。  基金项目:中国科学院“百人计划”资助项目。

  作者简介:颜晓龙,男,安徽淮南人,硕士研究生,主要研究方向:数据流挖掘; 沈鸿,男,教授,博士生导师,主要研究方向:并行与分布计算、高性能网络、数据挖掘。

第1页

你可能喜欢

热门文档

相关文档

  • 一种基于网格方法的高维数据流子空间聚类算法

    一种基于网格方法的高维数据流子空间聚类算法_工学_高等教育_教育专区。数据... 2一种适用于高维数据流的... 6页 1下载券 高维分类属性的子空间聚... ...

  • 高维数据流子空间聚类发现及维护算法

    一种适用于高维数据流的子... 1人阅读 6页 2.00元 一种大规模高维数据...一种基于Hoeffding界的高维数据流的子空间聚类发现及维护算法--SHStream.算法将...

  • 高维数据流的自适应子空间聚类算法

    高维数据流的自适应子空间聚类算法* 任家东 1,2, 周玮玮 1+, 何海涛 1 ...但是, 它没有考虑 历史数据的衰减问题, 当被适用于高维数据流的 聚类时, ...

  • 一种基于数据流的软子空间聚类算法

    一种基于数据流的软子空间聚类算法朱 林 1,2, 雷景生 1, 毕忠勤 1, 杨...处理技术的聚类算法,不能很好地应用于高维 数据流或大规模数据的聚类研究中....

  • 一种高维数据集的子空间聚类算法

    一种高维数据集的子空间聚类算法_信息与通信_工程科技_专业资料 暂无评价0人阅读0次下载举报文档 一种高维数据集的子空间聚类算法_信息与通信_工程科技_专业...

  • 1基于单元区域的高维数据聚类算法

    2一种适用于高维数据流的子... 2基于分层聚类的k_means算... 2基于子...[ 5 ] 和基于 Hoeff ding 界的高维数据的子空间聚类方法 [ 6 ] 等1 其...

  • 高维分类属性的子空间聚类算法

    出一种 处理 高维分类数据 集的子 空间聚类 算法( FP—Tree—based SUBspaee clusetring algorithm, FPSUB),利用频 繁模 式树 将 聚类 问题 转化为 寻找 属性...

  • 高维数据聚类方法综述

    今后的发展趋势,即 在子空间聚类过程中融入其他传统聚类方法的思想,以提高聚类... 2一种适用于高维数据流的... 6页 1下载券喜欢此文档的还喜欢...

  • 高维数据聚类方法综述

    的发展趋势, 即 在子空间聚类过程中融入其他传统聚类方法的思想, 以提高聚类...研究 致力于 减小甚至消除 维度 灾难对 高维 数据 处理 的影 响 [ 1, 2]...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email