论文部分内容阅读
随着网络技术的高速发展,以数据流形式呈现的数据信息大量涌现。例如传感器网络中传回的传感器数据,浏览网页产生的网络点击流,证券买卖产生的实时交易信息等等。这些数据往往具有数据量大,潜在无限,产生速度快,数据分布随时间变化等等特点。这些特点使得运行其上的数据挖掘算法必须满足如下条件:(1)整个数据流只被遍历一次;(2)每个数据必须在很短的时间被处理;(3)整个处理过程占用的存储空间是有限的;(4)算法应尽可能考虑到数据流的演化。上述要求使得传统的聚类方法无法直接应用到数据流上。
目前,已经有一些学者提出了若干适用于数据流的聚类方法。但仍存在许多尚未解决的问题。本文的贡献包括:
(1)本文提出了一种用以记录数据流摘要信息的数据结构DenseGrid树(简称DG树),通过搜索树中路经将高维空间聚类问题转化成构造DG树并利用这种数据结构搜索发现高密单元格的过程。实验表明,这种聚类方法具有良好的聚类效果和可扩展性,并且可用于发现不同形状的簇。
(2)本文提出了一种可以响应不同时间段的聚类请求的高维数据流聚类方法(DGMStream)。该方法使用倾斜时间窗口技术拓展了DG树。从而在保持DG树聚类性能的前提下,实现了高维数据流的多时间粒度聚类。
(3)结合传统的Parzen窗方法并引入一种经证明更加有效的历史数据丢弃策略,本文提出了一种新的适用于数据流的概率密度估计方法(TPWD)。
(4)本文在(3)此基础上,提出了一种计算整个数据集在低维空间投影的信息熵的方法,我们证明了信息熵与数据可聚性存在着某种内在联系,并利用信息熵实现了一种适用于高维数据流的聚类方法(PStream)。理论及实验均表明,与传统的方法相比,该方法可以在一次遍历的前提下,完成对数据流的高精度聚类,虽然其运行效率与现有的方法(如HPStream)相比差别不大,但是却明显地改善了聚类效果。