基于置信半径的分布式聚类算法的研究与应用

摘要

聚类分析作为数据挖掘的一个重要研究方向，可以有效地挖掘出这些数据背后所包含的知识，在金融、电信、保险业、市场营销、网络异常检测、网络安全、科学决策等方面具有十分重要的应用价值。传统的聚类算法只适用于集中式数据的聚类，随着信息技术、数据库技术、特别是网络技术的快速发展，基于单个服务器的集中式聚类分析已不能适应处理这些分布式、海量数据的需求。本文在整理归纳前人的研究成果基础上，研究利用对等网络(Peer-to-Peer，P2P)进行分布式海量数据的聚类方法。论文主要工作如下：
　　 首先，介绍了分布式聚类算法的基础理论以及国内外相关研究成果，其中包括集中式聚类分析的概述、分布式聚类概述以及基于P2P网络的分布式聚类算法。
　　 其次，本文引入了置信半径的思想来加快分布式聚类收敛速度。在此思想基础上，本文先提出了一种基于节点数据密度的分布式K-Means聚类算法。该算法通过计算P2P网络节点上数据分布密度的梯度，找到同一类数据在节点的稠密和稀疏分布，确定稠密数据的置信半径并用以指导下一步的聚类迭代，从而可以用较少的带宽消耗(即迭代数)使网络上的数据聚类快速达到稳定状态。
　　 再次，本文在前一个算法的基础上，提出了基于Fisher线性判别率的分布式K-Means聚类算法。该算法根据数据在节点上的局部分布，通过Fisher线性判别率计算出数据稠密分布和稀疏分布的分界，从而确定数据的置信半径并用以指导下一步的聚类。以达到消耗较少网络带宽并提高聚类精度的目的。
　　 根据模拟和真实数据所做实验表明，本文所提两个算法与集中式聚类算法以及DFEKM算法相比，在保证聚类精度的基础上，大幅减少聚类时所需迭代数，以及消耗的网络带宽。而基于节点数据密度的分布式K-Means聚类算法与基于Fisher。线性判别率的分布式K-Means聚类算法相比，前者在聚类精度上优于后者，而后者在算法效率和带宽消耗上优于前者。