论文部分内容阅读
在信用卡欺诈检测、股票和证券市场交易(金融分析)、网络入侵监测、社交网络分析等现实世界的行为活动中,数据以无限的、实时的、动态的流形式出现。根据数据流无穷、实时、有序、大规模等特性可知,对静态数据进行聚类的算法无法达到数据流的处理要求。本文针对以上问题从三个方面予以研究:1、根据CluStream聚类算法的主要架构思想,把OOSCA算法(Online Offline Spectral Clustering Algorithm,OOSCA)分为在线层汇总数据概要结构信息和离线层精确聚类双层架构模型。由于数据流大规模高维的特性,本文利用核函数成分分析法(KPCA)对数据进行降维,又因为界标窗口不能解决滑动窗口数据模型,而滑动窗口对大量信息的维护增加了数据存储的负载,因此,提出基于KPCA的时间衰减的数据流在线聚类方法。2、离线层采用基于图论思想的谱聚类规划方法,可以利用图的最优、最佳划分的解决方案来代替对大量数据集的聚类操作。它能够适用于现实世界中任何形态的样本集合,并可以最大程度地接近最优解。首先,本文利用NIF(New Intuitionistic Fuzzy,NIF)相似度量的方法创建相似矩阵。为了提高聚类的效果和精度,采用改进的t-最近邻方法对相似矩阵进行稀疏化,并对其结果作离群点调优处理。应用ε-最近邻粗糙集模型计算k-means的初始聚类中心并对数据进行聚类。3、在数据进行聚类的过程中存在大规模的繁杂运算,因此算法时间复杂度较高。在构建相似矩阵、求解Laplacian矩阵的前k个特征向量和计算k-means初始聚类中心时,它们之间不存在相互依赖的紧密关系,所以本文结合Hadoop MapReduce分布式存储和并行计算等各种有利的特性,对上述三个阶段进行并行计算,进而减少聚类复杂运算所花费的时间。实验结果表明,改进后的数据流分布式并行谱聚类算法在聚合质量、精度、减少计算量等各方面具有较好的效果。最后,对本文所做的相关工作予以总结,并对其他方面的探索做出展望。