随着产品追溯系统的应用推广,追溯数据量急剧增加,追溯数据作为一种典型的数据流具有重要的研究意义和应用价值。数据流挖掘已经成为当前数据挖掘领域研究热点之一,在有限的内存中对数据流快速处理以获得高质量聚类成为数据流挖掘的一个重要方向。基于密度网格的数据流聚类方法计算速度快、可形成任意形状簇,但存在参数难以设置、聚类精度低等不足。针对这些缺点,本文改进基于密度网格数据流聚类算法,并设计实现并行化算法,最后将其应用到追溯系统中。所做工作总结如下:(1)基于D-Stream算法提出结合质心的不均匀网格数据流聚类算法NCDStream。算法首先通过加权平均密度设置自适应参数,并根据网格簇数量动态调整阈值。其次对网格簇边缘的稀疏网格采用不均匀划分,提高聚类精度。然后使用并查集优化网格簇合并,提高聚类效率。最后采用金字塔模型存储时间快照为网格簇演化分析提供依据。实验表明,相比于其他算法,NCD-Stream算法聚类效果更好,执行效率更高。(2)基于NCD-Stream提出面向分布式环境的数据流聚类算法DNCD-Stream。算法将数据空间分成多个网格块并行地进行局部聚类,并判断网格块的边界网格状态进行全局聚类。通过Spark Streaming实现算法,并进行实验。实验表明,随着并行度增加,算法能够在保证聚类质量的同时,有效提高执行效率。(3)将DNCD-Stream算法应用到追溯系统中,设计并实现追溯数据流处理系统。