论文部分内容阅读
随着网络融合演进的加速，以多媒体应用为代表的流数据业务在网络中所占比例越来越高，逐渐成为主流的数据存在形式。与传统数据不同，这些数据具有快速连续到达、持续增长、动态演化的特点，使得对数据流进行聚类分析产生了诸多难题，受到了国内外学者的广泛关注。本文首先以研究传统聚类算法为基础，分析了对静态数据聚类性能影响较大的因素，然后从这些因素入手，针对静态复杂数据的聚类问题开展深入研究，通过分析发现仿射传播算法的聚类性能有很大优势，且有利于向数据流聚类扩展，因而将仿射传播算法作为本文重点研究的算法；其次针对实时到达的复杂数据流的聚类问题开展深入研究，进一步将仿射传播算法应用到进化数据流中，实现对进化数据流的高效、准确、快速的聚类性能；最后，结合大规模网络数据流的特点，针对分布式环境下的数据流聚类问题进行研究，设计了分布式环境下的应用机制，并结合依托项目需求具体实现了一种基于流聚类模型的异常信息样本快速发现方法。围绕着复杂数据流的聚类问题，本文主要进行了以下三个方面的理论研究工作：1）提出了一种处理海量复杂数据的仿射传播聚类算法。针对仿射传播算法只能发现超球形聚类的缺点，依据聚类的局部一致性和全局一致性假设，设计了一种局部密度自适应的流形距离核测度，据此提出了基于混合测度的仿射传播聚类算法APCHM（Affinity Propagation Clustering based on Hybrid Measure），该算法克服了原有算法不能处理非凸形结构聚类的缺陷。在此基础上提出了一种并行的APCHM算法P-APCHM（Parallel Affinity Propagation Clustering based on Hybrid Measure），能够在保持聚类性能的同时大大提高算法运算速度。2）提出了针对数据流的快速、高效、自适应簇变化的在线聚类算法。针对目前算法应用到复杂数据流聚类存在的不足，将APCHM算法扩展到数据流聚类算法当中，提出一种基于仿射传播和密度融合的进化数据流聚类算法StrDenAP (DataStream Clustering Base on Density and Affinity Propagation)。该算法采用在线/离线两阶段处理框架，通过引入微簇衰减密度来精确反映数据流的演化信息，并采用在线动态维护和删减微簇机制，使算法模型更符合原始数据流的内在特性，同时能够快速检测到新的类模式出现，并能给出任意时间的聚类结果。在真实数据集和人工数据集上的实验表明，该算法具有良好的适用性、有效性和可扩展性，能够取得较好的聚类效果。3）提出了针对分布式环境下的数据流聚类的应用机制。进一步将StrDenAP算法应用到分布式环境中，设计了一种分布式算法的应用机制D-StrDenAP (Distream Stream Clustering based on Density and Affinity Propagation)。各个局部站点在滑动窗口下运行StrDenAP进行局部站点聚类，然后将得到的局部概要数据结构上传给中心站点，中心站点对所有局部站点上传的概要结构采用基于密度融合的方式进行综合处理从而获得全局结果并反馈到局部站点。实验表明，该算法不仅提高了分布式数据流的聚类质量，而且明显降低了通信代价。