高效数据流聚类算法的研究与应用

摘要

数据流是一种当今广泛存在的数据形式，如web点击数据流、网络深度包数据流等。数据流聚类分析在社交媒体、电子商务、网络入侵检测和环境监控等领域有着极其重要的应用价值。由于数据流具有海量、高维、时序、快速变化与潜在无限等特性，不可能在内存或硬盘上进行存储，导致多遍扫描与处理数据流中每个数据点的传统静态聚类算法不再适用。近十多年来，众多学者和IT技术人员对高效的数据流聚类算法展开了较为深入的研究，并产生了一些较为有效的聚类算法。但已有的算法主要存在以下缺陷：1)算法具有多个人为设置的常量参数，以致这些参数不具有自学习能力，不能适应数据流的动态变化；2)算法一般不能有效地处理高维数据流；3)算法的聚类精度和时间性能离实际应用仍有一定的距离。因此，研究新型高效的数据流聚类算法，使其适应于能解决实际的数据流聚类应用问题，将具有十分重要的理论意义与应用价值。 为了克服已有数据流聚类算法的缺陷，作者针对高效的数据流聚类算法及其应用展开了较为深入的研究，论文主要工作如下：1)提出了数据流聚类算法参数响应数据流变化的自学习和自动更新策略，使所提出的数据流聚类算法能及时捕获并反映数据流的动态变化；2)给出了本文基于网格+密度的数据流聚类算法中的数据流投影网格有效维度的提取方法，以间接方式有效地降低了数据流的维度，提高了算法处理效率；3)引出了网格质心及网格强匹配的概念，以及其计算与判别方法。基于上述策略，提出了一种新的高效的数据流聚类算法ED-Stream；4)不同于现有广泛使用的数据流聚类算法框架，采用两个同时在线的实时处理过程：数据准备阶段和聚类分析阶段，分五个模块以流水线方式对数据流进行实时分布式聚类处理，提出了一种新型高效的分布式数据流聚类算法DED-Stream；5)采用不同形状和密度的人工合成数据流集，与现有最好的数据流聚类算法进行了仿真实验性能对比。同时，采用真实数据流集验证了本文算法在网络深度包数据流聚类与森林覆盖类型数据流聚类实际应用中的可行性。实验结果表明：本文算法可以有效地识别数据流中各种形状和密度的类簇，能及时捕获并反映数据流的动态变化，所提出的算法的时间与精度性能远优于现有最好的数据流聚类算法，并且本文所提出的新的数据流聚类算法可有效地应用于具体的数据流聚类问题。 作者今后的努力方向是进一步提高本文算法的时间与精度性能，并努力将所提出的算法应用于关键领域的数据流分析处理中。

目录

第一个书签之前