论文部分内容阅读
聚类分析是数据挖掘领域一项重要的研究课题。近年来,由于计算机应用技术的高速发展,人们获取数据的能力得到了极大的提高。数据流作为一种重要的数据来源,也得到了人们越来越多的关注,例如电话通信记录、卫星传输数据、网络监控日志、电子商务记录等。这些数据适合用数据流模型进行描述。与传统的静态数据相比,数据流是高速的、连续的、动态的、变化的、无限的,对它们的访问只能是顺序的、一次或有限次的、对它们的存储也只能是动态的、概要的。数据流的这些特性,给数据流的挖掘带来了极大的困难,也给数据流的聚类算法提出了更高的要求。
本文深入研究了数据流的聚类问题,分析了现有的数据流聚类算法。在Clustream算法的基础上提出了基于密度的改进双层数据流聚类算法,该算法由第一层一在线快速计算层和第二层--离线精确计算层组成。在线快速计算层将数据流聚集成微簇后,利用基于密度的评估方法找到微簇中的聚类密集区域,然后应用不完全划分策略输出这些聚类密集区域。这一层主要是对数据流进行快速处理,在最大限度地规约数据的同时保留足够的数据信息,将相对较小的中间结果输出到离线精确计算层,并对中间结果采用基于密度的方法进行评估,使得第二层算法的输入更加有效。离线精确计算层使用N-维球数据结构描述密集区域,利用渐进扩展的方式搜索高密度区域,从而对N-维球集合目标进行基于密度的聚类。离线层面临的数据压力相对较小,可以用复杂的算法深入分析第一层得到的结果,从更高的粒度上得到聚类结果。这个双层数据流聚类算法给用户提供了更大的自由性,在面对变化较快的数据流时,它能在不同的时间范围内给出相应的聚类结果,因此,更加适用于实际应用。
我们利用实际数据集和人造数据集对算法进行了测试。将测试结果做了有关聚类质量、可扩展性和参数敏感性等方面的系列分析,并同其它数据流聚类算法的相关测试数据比较,验证了本算法框架具有强大的优势和广阔的发展前景。