数据流聚类分析算法

《数据流聚类分析算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、後旦大擎博士学位论文数据流聚类分析算法AlgorithmsforClusteringoverDataStreamsV955535院系：计算机科学与工程系专业：计算机软件与理论姓名：曹锋指导教师：周傲英教授指导小组：周水庚教授钱卫宁博士王晓玲博士述数据流中任意形状的簇，并提出潜在核心微簇(potentialcore-micro-cluster)和离群微簇(outliermicro-cluster)结构分别用于维护并区分数据流中潜在的簇和离群点。DenStream基于这些概念包含了一种新颖的淘汰策略，该策略可利用次线性空间的内存维护并保证各微簇权值

2、的精度。3．本文利用性能强大、目趋廉价且在数据流领域尚未引起足够重视的图形处理器(GPU)处理数据流聚类挖掘问题。我们提出一类基于GPU的快速聚类方法，包括基于女．mealls的基本聚类方法，基于GPU的数据流聚类以及数据流簇进化分析方法。这些方法的共同特点就是充分利用GPU强大的处理能力和流水线特性。与以往具有独立框架的数据流聚类算法不同，基于GPU的聚类算法具有同一框架和多种聚类分析功能，为数据流聚类分析提供了统一平台。4．本文提出了一个分布式聚类处理框架CluDistream。该框架可高效地实时处理分布式数据流中海量数据，有噪声、有损或不

3、完整数据记录，以及有交叠的数据集。在CluDistre锄基于期望最大化(ExpectationMaximization)的算法中，每个数据记录可以以不同的隶属度属于不同的簇。这种软聚类方式能较好地反映簇的交叠性．对有噪声、损坏的或不完整的数据记录，算法可通过最大化数据簇的似然度来学习数据流的底层分布。此外，CluDistream算法中测试后聚类的策略可有效地减少算法的平均处理代价，这对分布式数据流的在线实时聚类挖掘非常有效。总之，本文研究了数据流聚类分析的四个基本问题并分别提出了新的解决方案。滑动窗口是处理数据流的基本模型之一，如何在滑动窗口内

4、对数据流进行聚类分析是一个基本问题；具有任意形状簇相对于球形簇是更为一般的数据簇模型，如何挖掘任意形状的簇也是一个基本问题；如何提高数据流聚类算法的处理速度是一个基本问题，这是由数据流聚类算法实时在线挖掘的特点所决定的；分布式数据流的数据聚类问题，其基础性在于现实应用中数据流往往是在分布式环境中产生的。本文算法是对现有数据流上的聚类分析技术的有益补充和改进。理论分析和实验结果表明本文算法能够高效地解决相应问题，与现有数据流聚类方法相比，本文算法在存储空间开销、挖掘处理速度以及结果准确性上具有优势。关键词：数据流，聚类分析，进化，窗口，图形处理器

5、分类号：TP301AbstractRecently,variousapplicationsgeneratealargenumberofstreamingdata，suchasnetworkflow，seusordata，andwebpageclicks．Miningandanalyzingsuchkindofdatahasbeenbecomingahottopic．Asabasicmethodofdatamining，clusteringindatastreamsettingshasbeenwildlyconcernedfromacademia

6、andindustry．Differentfromtraditionaldatabases．datastreamshavethefollowingdistinguishedcharacteristics：(1)unboundedvolumeofdata；(2)rapidarrivingrateofdata；(3)uncontroUabilityoftuples’arrivingorder；(4)beingprocessedonlyonceforeachtuple，exceptbeingreserved．Abovecharacteristicsp

7、roposethefollowingrequirementsonclusteringoverdatastreams：Firstly,algorithmsshouldbeonlinemining，beabletofastprocesseachtu-ple，andoutputtheminingresultontime；Secondly,becauseofthelimitedmemorycomparedtounlimiteddatastreams，algorithmsshouldhavelowspacecomplexity,thespacecompl

8、exityshouldbeintherangeoflogboundofdatavolume．Thirdly,bytheconstraintofonli