论文部分内容阅读
数据挖掘,又称数据库中的知识发现,是指从大型数据库或数据仓库中提取隐含的、事先未知的、潜在有用的信息或模式。它融合了数据库、人工智能、机器学习和统计学等多个领域的理论和技术,是数据库研究中的一个很有应用价值的新领域。而聚类分析是数据挖掘中很重要的分析手段。聚类是依据事物的某些属性将其聚集成类。使类间相似性尽量小,类内相似性尽量大,即“物以类聚,人以群分”。聚类本身是一个发现过程,其结果可以解释数据分布的本质特征,同时也为应用其他的数据挖掘及分析技术奠定了基础。 在当今的经济生活中,许多庞大的机构每天都会产生数以百万记的记录。在科学研究中,科学数据的采集通常每天都会产生十亿字节的数据。对于达到这个数量级的数据,应用数据挖掘技术,特别是聚类分析手段来提取人们感兴趣的知识和模式来说是非常有意义的。但现有的挖掘复杂数据模型的算法都不能在有效的时间内完成挖掘任务,因为在传统的数据挖掘过程中,被考虑的数据假设已经被载入一个稳定且很少更新的数据库中,而面对大量、无限和快速的数据流时,数据挖掘系统应该是以数据到来的速度来处理和挖掘数据的。克服这样的状态需要我们转换的观念,将挖掘数据库中的静态数据转换为挖掘动态的数据流。 在众多的针对数据流的聚类算法中,当首推由Stanford大学stream小组的Guha等人开发的STREAM算法。STREAM算法经过四年左右的改进,已经成为数据流聚类算法的经典之作。Guha等人不仅在实践中体现了STREAM算法的可行性,而且在理论上证明了数据流聚类的时间空间复杂性。如果单独从满足数据流的自身特点出发,现有的数据流聚类算法可以说是显示出很强的优势。但是聚类是一个应用性很强的问题,我们应该将我们的视角转向实用角度。在现实的数据流应用中,数据量不仅浩瀚如海,而且数据通常变化很大。我们在满足聚类质量的同时,还要满足用户从不同应用角度获取聚类结果的要求。而现有的数据流聚类算法恰恰忽略了这些方面。 Clustream是Aggarwal在2003年提出的一个解决数据流聚类问题的框架。它使用了两个过程来处理数据流聚类问题。它通过在线的micro-cluster过程对数据流进行初级聚类,再使用另一个离线的macro-cluster过程,根据用户的具体要求对micro-cluster聚类的结果进行再分析。虽然很好的解决了上述问题,但是此框架也增加了查询的响应时间。 同时,现有的数据流聚类算法无论是单层框架还是双层框架,它们都假设每次聚类的流数据大小不会突破内存的限制。但是,当聚类的时间跨度太大或者数据流到达的速率太快时,上述算法都不能很好的工作。本文作者提出了基于压缩滑动窗口的数据流聚类算法,有效地解决了上述问题。 本文的主要工作是设计和实现了混合平均数据流聚类方法、基于滑动窗口的数据流聚类方法以及基于压缩滑动窗口的数据流聚类算法,并设计了系统原型以处理用户的聚类查询处理。主要有三方面的贡献:一是提出一个利用混合平均的方法对流入的数据进行聚类的方法;二是将滑动窗口应用到数据流聚类中,根据每次聚类大小动态地调整滑动窗口的大小,将对整个数据流的聚类简化为对每个滑动窗口内的流数据进行聚类操作;三是当滑动窗口的时间跨度太长或者数据流到达速率太快时,利用一种有效的滑动窗口压缩算法,缩减了存储滑动窗口所需的空间。从而使得所需数据能完全放在内存中,扩大了每次聚类的数据集大小,从而使聚类结果更加精确,支持具有更大时间跨度的查询。