聚类K-means算法及并行化研究

数据挖掘（Data Mining）,又称为数据库中的知识发现(简称KDD),是从大量数据中提取可信的、新颖的、有效的并能被人们理解的模式的处理过程。它是一门新兴的交叉学科，汇集了来自机器学习、模式识别、数据库、统计学、人工智能等各领域的研究成果。聚类分析是数据挖掘中的一个重要研究领域。它将数据对象分组成为若干个类或簇，使得在同一个簇中的对象比较相似，而不同簇中的对象差别很大。 K-means属于聚类分析中一种基本的划分方法，常采用误差平方和准则函数作为聚类准则，该算法在处理大数据集时是相对可伸缩且高效率的，同时具有潜在的数据并行性。但是这种算法依赖于初始值的选择以及数据的输入顺序；此外，当运用误差平方和准则函数测度聚类效果时，如果各簇的形状和大小差别很大，为使误差平方和Jc值达到最小有可能出现将大的聚类簇分割的现象。针对K-means算法采用准则函数衡量聚类质量存在的局限性以及对初值的依赖性，通过分析和研究，基于多次取样一次聚类寻找最优初值的思想，提出了一种新改进的算法，并辅以实验证明了改进后算法的稳定性。 为了进一步提高算法的执行效率，论文同时研究了并行K-means算法的实现。选用局域网环境，并行虚拟机PVM和LINUX，共同搭建的机群系统作为并行计算平台；在并行程序的模型上采用了Master/Slave模型。该并行算法将数据集分配到各个Slave节点机上实现数据并行，最后由Master节点机进行汇总给出结果。在研究K-means算法自身的特点以及各机器节点的处理能力的基础上，提出了一种较优的数据划分策略。论文以时间复杂度和加速比等指标从理论和实验结果两个方面对并行算法进行了评价。实验结果表明：并行K-means算法的聚类结果与串行算法相同，但执行效率得到了很大的提高。