流数据聚类方法研究.pptVIP

流数据的聚类方法研究 报告人： 导 师： Email: xxx@1yzu.edu.cn 2007.4.14 介绍提纲 选题依据 流数据 流数据的定义及其特点 数据流的三种模型 构造概要数据结构的方法 聚类 聚类定义 传统的聚类方法 数据流聚类的特点 流数据 流数据是一种大量的连续到达、时间有序、快速变化、 潜在无限的数据。 流数据的特点是： ※数据量十分庞大，这些数据随着时间的增长数量急剧上升 ※流数据均按照时间顺序连续到达。 ※相比于有限的内存，不可能存储整个数据集，只能存储数据的汇总信息。 ※大多数流数据本质上是多维，多层的数据，需要多维多层次的处理。 数据流的三种模型 按照数据流上各个元素重要程度的不同可以将其分为三种子模型：界标模型，滑动窗口模型和衰减窗口模型。 界标模型：考虑从某一个特定的时间点s开始到当前时间点N之间的所有 数据，查询范围是[s…N]。 滑动窗口模型：仅考虑最近的w个元素。 衰减窗口模型：数据流算法的范围从初始时间点到当前时间点，查询范 围是[0…N]。但各个元素的重要程度是不同的。新到达的元素，重要程度较高，旧的元素，重要程度较低。 构造概要数据结构的方法 直方图技术 (histograms）:等宽直方图、v-优化直方图 随机采样（random sampling）:常用的方法:水库抽样 小波方法（wavelet） 梗概（sketches） 基于滑动窗口模型的方法 ●指数直方图(exponential histogram) 按照元素的到达次序购建桶。桶的容量按照不同级别而指数递增。 ●基本窗口（basic window） 将大小为W的窗口按照时间次序划分成k个等宽的子窗口，成为基本窗口，每个基本窗口包含W/k个元素 聚类 聚类问题 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程称为聚类。这些对象与同一簇中的对象彼此相似，与其他簇中的对象相异。 传统聚类方法： 基于划分：k-means k-mediods 基于层次：BIRCH 基于密度: DBScan 基于网格：STING 基于模型：COBWEB 国内外研究动态 数据流聚类问题是近些年数据挖掘理论研究和应用领域中的热点问题。研究的主要方向有单层数据流的聚类、双层数据流聚类、高维数据流聚类、基于密度的数据流聚类、多数据流聚类等。 国内外研究动态 ◇2000年,Guha 提出针对数据流聚类的LOCALSEARCH算法。基于分治的思想使用一个不断的迭代过程实现有限空间对数据流进行k-means 聚类.。 ◇2002年，O’Callaghan提出了STREAM， 是单层数据流聚类算法的经典之作。 ◇2003年，AGGARWAL C等人设计了一种更加行之有效的算法框架CluStream。双层数据流聚类框架应运而生。 ◇2003年,Barbard 总结了数据流聚类算法的要求，并对一些可能适用于数据流的聚类算法做了一次总结。 ◇2004年，AGGARWAL C提出了一种高维，投影数据流聚类算法HPstream。 ◇ 2006年，ZHU Wei-Heng等人详细分析了数据流聚类算法CluStream 的不足之处，提出了一种采用空间分割、组合以及按密度聚类的算法ACluStream。 本课题研究的主要内容有： ◇多数据流的实时聚类 ◇满足用户需求的多数据流聚类 ◇基于相位差的数据流的聚类 ◇高维流数据的降维的聚类 ◇基于密度的流数据的聚类 1.多数据流的实时聚类 （1）问题描述及研究背景 设在时间t有条数据流 ，其中 。对多条数据流在时间t、跨度L上的聚类, 就是要将流数据分为类： 使得目标函数 最大 。 （2）已有的研究工作 Yang Jiong用带权重的快照差的和作为流数据间距离的度量, 不能反映流数据间趋势变化的相似度 。 Beringer等人通过对流数据标准化等预处理后用离散傅立叶变