基于动态可调衰减滑动窗口的变速数据流聚类算法

SPEED-VARIED DATA STREAM CLUSTERING ALGORITHM BASED ON DYNAMICALLY WEAKENING ADJUSTABLE SLIDING WINDOW

在数据流聚类算法中,滑动窗口技术可以及时淘汰历史元组、只关注近期元组,从而改善数据流的聚类效果。如果同时数据流流速无规律地随时间动态变化,原来单纯的滑动窗口技术在解决这类问题时存在缺陷,所以,在充分考虑了滑动窗口大小和数据流流速之间关系的前提下,提出了基于动态可调衰减滑动窗口的变速数据流聚类算法。该算法对历史元组和近期元组分别赋予一定的权重进行处理,然后依据数据流流速的不同函数改变窗口的大小,从而实现数据流的聚类。提出了该数据流聚类算法的数据结构——变异数据流聚类的数据结构。通过真实数据和模拟数据来构造动态变速数据流从而作为验证算法的原始数据。实验结果表明,与Clu Stream聚类算法相比,该方法具有较高的聚类质量、较小的内存开销和较少的聚类处理时间。

In data stream clustering algorithms, sliding window technique can eliminate promptly the historical tuples and only concern with recent tuples, thus can improve the clustering effect of data stream. However, if the data stream velocity dynamically varying with the time erratically, the original pure sliding window technique will have the flaw in solving such kind of problems. Therefore, in this paper we propose the speed-varied data stream clustering algorithm, which is based on dynamically weakening adjustable sliding window, on the premise of taking the relationship between the size of sliding window and data stream velocity into full account. The algorithm assigns certain weight to historical tuples and recent tuples respectively to process them, and then alters window size in accordance with different functions of data stream velocity so as to achieve data stream clustering. In this paper we also propose the data structure of the data stream clustering algorithm, i. e. , the data structure of mutated data stream clustering. We construct the dynamically speed-varied data stream with actual data and simulated data and therefore use it as the primitive data for verifying the algorithm. Experimental results indicate that compared with CluStream clustering algorithm, the proposed method has higher clustering quality, less memory cost and faster clustering processing rate.