数据流聚类的分析与思考.doc

《数据流聚类的分析与思考.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据流聚类的分析与思考【摘要】数据流聚类是目前国际数据库和数据管理领域的新型研究热点，综述了数据流聚类的研究进展，在介绍数据流聚类的相关理论和常用技术的基础上，探讨了目前基于聚类的数据流演化国内外研究的状况，最后展望了将来可能的研究方向。【关键词】数据流聚类交互式数据【中图分类号】G64【文献标识码】A【文章编号】2095-3089(2014)04-0236-01一、数据流及其聚类在线交互式数据分析与处理的难点在于从多源异构，复杂内联和动态演化的角度构建新的数据处理策略与方法。基于在线数据获得的知识通常具有不确定性、不完整性、不协调性和

2、不恒常性等特点，对在线数据进行提炼、排疑、融合、重组等处理，结合数据的动态变化规律定性和定量地分析隐藏在数据中的知识演化规律，从而为提高数据的应用价值提供解决方案和技术支撑。在线交互式数据处理应该具备在线短的时间内，有效地整合与调度资源、数据源之间彼此关联、快速演化形式、进而提出在用户体验方面与之前业务截然不同的表现，适应在线信息服务的灵活性和快速演化的要求。基本的动态数据模型有三种：1•动态模糊数据模型DFDM；2•动态模糊数据的扩展模型EMDFD；3.动态模糊关系数据模型DFRDMo随着时间的变化，数据的统计性质往往会发生变化，即数

3、据的分布是随时间而变化的，这也被称为“分布漂移”。造成这种分布变化的因素可以分为两种，一种是数据本身的本质“概念”变化，另一种是噪声的变化,如在不同的时刻，搜集数据时条件不相同，数据噪声也不相同，在这样的数据上的聚类就是一个新问题一一演化聚类。在数据流上进行聚类，其基本任务就是要在对当前数据进行聚类的同时，随着新数据的不断流入，动态地调整和更新聚类的结果以真实反映数据流的聚类形态。这种在线的增量聚类使得常规的聚类技术难以在数据流上直接应用，算法必须要满足如下耍求：1•内存限制。由于内存容量有限，不可能将数据量庞人的数据流全部存储于内存，

4、再进行聚类。在内存屮只维护一个反应当前数据流特征的概要数据结构是目前常用的技术；2.实时性。数据流聚类要求具备很短的响应时间，能够响应anytime的用户聚类请求，要求算法处理速度快；3•单遍扫描或者有限次扫描。在对数据流进行聚类时，只能按数据点流入的顺序访问一次或儿次。以上只是基本要求，对一个搞笑的实时数据流聚类算法来说，还必须考虑：1•聚类簇数事先未知。算法不可能预知数据流将会被分为几个聚类簇，不但如此，随着新数据不断地流入，聚类簇数目和状态都在不断地变化；2•对孤立点的分析能力。由于数据流的不断流动和进化，当前时间窗口内的孤立点，

5、有可能随着新数据的加入变成一个新聚类簇，也有可能仍然是孤立点而被剔除，聚类算法必须能对这一情况及时鉴别和处理；3•聚类形状任意。传统的基于欧式距离的相似度准则易于产生球形聚类，真实数据流所隐含的聚类簇一般包含很多非凸形状的聚类，算法必须具备识别任意形状聚类的能力。二、目前国内外研究状况分析在演化聚类中，算法最终的冃的是要为每个时刻的数据给出聚类结果，该结果不仅要求能够把当前时刻的数据划分的很好，还要求各时刻的聚类模式在时间轴上保持一定的连续性。聚类结果应保持时间轴上的连续性是演化聚类问题屮很重要的一点，它来自于实际应用的需要。在实际应用

6、中，这样的性质能带来很多益处。演化聚类算法可以是在线的，第一个在线的演化数据聚类方法是CHAKRABARTID等在evolutionaryclustering论文中提出。他们在静态聚类的损失函数上增加一个时间损失项，每一个聚类都被匹配到上一时刻顕离最近的那个聚类，把所有这种配对的聚类之间的距离相加作为时间损失。这种启发式最近匹配方法可能不稳定，会对聚类中心小的扰动十分敏感。在研究中，其中包括两种数据形式：1•与传统的学习问题相同，数据样本被表示为共同的有限维特征空间中的向量。2•关系型数据。数据样本没有自身的特征表示，而只有样木之间的链

7、接关系，这样的数据实际构成一个图，图的结点就是一个样本点，而随时间推进，结点Z间的链接关系会发生变化，之前存在的链接可能消失，之前没有的链接可能建立。在非参数贝叶斯方法中能够发现多个关联演化子集中的复杂演化模式，包括聚类的出现、变化、消失以及在不同子集之间的传播，而口，在该方法中，所有的聚类数都是从数据中自动学习，不需要人为指定。另外，在马尔可夫跳转模型屮不难发现难点在于如何定义“状态”以及不同时刻Z间的转移矩阵。该方法采用了传统的优先混合模型，需要用户指定每一时刻的聚类数冃，属于参数化方法。在最近的数据流聚类研究中，有将多种原有技术进

8、行结合使用，也有很多新颖的方法不断出现，其中受到广泛关注的3类方法是基于网格的数据流聚类技术、子空间聚类技术、混合属性数据流聚类，代表了当前数据流聚类研究的主流方向。（一）D-Stream算法网格聚类首先将