基于倾斜分布的变流速数据流聚类算法

Data Stream Clustering Algorithm with Variable Flow Rate Based on Skew Distribution

处理倾斜分布特征的数据流聚类算法TDCA存在聚类速度与内存利用率上的不足,且变流速的数据流环境对聚类结果的质量有严重影响。针对上述问题,提出一种数据流聚类算法GR-Stream。采用网格单元作为数据点的聚集形式,以基于R-tree的扩展数据结构作为组织网格单元的索引结构,在此基础上引入剪枝策略,并调整数据点进入树的方式。在真实数据集KDD-CUP99上进行测试,结果表明,与TDCA算法相比,该算法在聚类过程中可以提高40%的访问速度,应用剪枝策略节省至少一半的内存使用量,同时在变流速的数据流环境下将聚类结果的平均纯度保持在90%以上。

The skew distribution characteristics of data stream clustering algorithm TDCA lack of clustering speed and memory utilization. Variable flow rate data stream environment has a serious impact on the quality of the clustering results. In order to deal with the above problems, a data stream clustering algorithm named GR-Stream is presented. It uses grid cells as the aggregation of data points, Based on an extension of the R-tree structure as the organization of grid cell index structure, it introduces pruning strategy on the basis of this structure, and adjusts the way of data points into the tree. It adopts the real dataset the KDD-CUP99 on algorithm test. Experimental results show that, compared with the TDCA algorithm data structure organizing data, this index structure can improve the clustering speed by 40%, and the application of pruning strategy to save at least half memory usage, at the same time maintaining more than 90% of the average purity of the clustering results in the variable flow rate of the data stream environment.