流数据的聚类方法研究

《流数据的聚类方法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、流数据的聚类方法研究报告人：导师：Email:xxx@1yzu.edu.cn2007.4.14介绍提纲◆选题依据◆国内外研究动态◆课题研究目标◆课题的主要关键技术和研究方法◆计划安排选题依据流数据流数据的定义及其特点数据流的三种模型构造概要数据结构的方法聚类聚类定义传统的聚类方法数据流聚类的特点流数据流数据是一种大量的连续到达、时间有序、快速变化、潜在无限的数据。流数据的特点是：※数据量十分庞大，这些数据随着时间的增长数量急剧上升※流数据均按照时间顺序连续到达。※相比于有限的内存，不可能存储整个数据集，只能存储数据的汇总信息。※大多数流数据本质上是多维，多层的数据，需

2、要多维多层次的处理。数据流的三种模型按照数据流上各个元素重要程度的不同可以将其分为三种子模型：界标模型，滑动窗口模型和衰减窗口模型。界标模型：考虑从某一个特定的时间点s开始到当前时间点N之间的所有数据，查询范围是[s…N]。滑动窗口模型：仅考虑最近的w个元素。衰减窗口模型：数据流算法的范围从初始时间点到当前时间点，查询范围是[0…N]。但各个元素的重要程度是不同的。新到达的元素，重要程度较高，旧的元素，重要程度较低。构造概要数据结构的方法直方图技术(histograms）:等宽直方图、v-优化直方图随机采样（randomsampling）:常用的方法:水库抽样小波方法

3、（wavelet）梗概（sketches）基于滑动窗口模型的方法●指数直方图(exponentialhistogram)按照元素的到达次序购建桶。桶的容量按照不同级别而指数递增。●基本窗口（basicwindow）将大小为W的窗口按照时间次序划分成k个等宽的子窗口，成为基本窗口，每个基本窗口包含W/k个元素聚类聚类问题将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程称为聚类。这些对象与同一簇中的对象彼此相似，与其他簇中的对象相异。传统聚类方法：基于划分：k-meansk-mediods基于层次：BIRCH基于密度:DBScan基于网格：STING基于模型：

4、COBWEB算法性能比较国内外研究动态数据流聚类问题是近些年数据挖掘理论研究和应用领域中的热点问题。研究的主要方向有单层数据流的聚类、双层数据流聚类、高维数据流聚类、基于密度的数据流聚类、多数据流聚类等。◇2000年,Guha提出针对数据流聚类的LOCALSEARCH算法。基于分治的思想使用一个不断的迭代过程实现有限空间对数据流进行k-means聚类.。◇2002年，O’Callaghan提出了STREAM，是单层数据流聚类算法的经典之作。◇2003年，AGGARWALC等人设计了一种更加行之有效的算法框架CluStream。双层数据流聚类框架应运而生。◇2003年,

5、Barbard总结了数据流聚类算法的要求，并对一些可能适用于数据流的聚类算法做了一次总结。◇2004年，AGGARWALC提出了一种高维，投影数据流聚类算法HPstream。◇2006年，ZHUWei-Heng等人详细分析了数据流聚类算法CluStream的不足之处，提出了一种采用空间分割、组合以及按密度聚类的算法ACluStream。国内外研究动态◇多数据流的实时聚类◇满足用户需求的多数据流聚类◇基于相位差的数据流的聚类◇高维流数据的降维的聚类◇基于密度的流数据的聚类本课题研究的主要内容有：1.多数据流的实时聚类（1）问题描述及研究背景设在时间t有条数据流，其中。对

6、多条数据流在时间t、跨度L上的聚类,就是要将流数据分为类：使得目标函数最大。（2）已有的研究工作YangJiong用带权重的快照差的和作为流数据间距离的度量,不能反映流数据间趋势变化的相似度。Beringer等人通过对流数据标准化等预处理后用离散傅立叶变换减少噪声,用增量在线的k-means算法进行聚类。算法质量和执行效率都依赖于DFT系数个数,难以在效率和质量间达到平衡。1.多数据流的实时聚类(3)我们的研究思路我们针对多数据流的实时聚类问题，提出了一种基于相关系数的聚类算法CORREL-cluster。◇相关系数（优于欧氏距离）：◇衰减系数（如取=0.99）：突出

7、新数据比旧数据在聚类结构中有更大的重要性◇更新时间片段：将长度为的时间片里的数据分为段,每段长为个单位时间。在任意时刻,算法保存个数据段。算法CORREL-cluster对不断到达的流数据实时形成其统计信息，并按一定的时间段进行保存。在一定的时间间隔以后,算法根据统计信息进行聚类。提出一种动态的k-means的聚类算法。该算法首先用k-means方法产生初始聚类。在以后的各次聚类操作中,由于流数据的变化是逐渐的,相邻两次的聚类结果之间有大部分是重叠的。因而每次聚类时,仅需在前一次聚类的基础上,用少量的几次k-means迭代就可以得到结果。使用聚类调整