论文部分内容阅读
随着人们生产生活的越来越繁杂,使得数据量高速增加,数据挖掘技术在人们的生活中起着越来越重要的作用。而聚类分析作为数据挖掘的一种重要技术,对各种数据的分析起着至关重要的作用,本文主要就多维数据的聚类算法进行了研究,提出了两种针对多维数据的聚类算法。同时为了解决海量数据的处理时间问题,进行了相关算法的GPU加速研究。本文的主要研究工作阐述如下:针对多维数据聚类过程数据的每个属性对聚类所起的作用不同,本文提出了一种基于属性权重的Global K-means算法,即Global weighted K-means(GWKM)算法。GWKM算法结合了LAW K-means(LKM)算法的属性权重技术和Global K-means(GKM)算法的聚类框架,在GKM算法每次进行聚类中心的选取过程中,引入LAW K-means算法,不仅求得了聚类中心,而且确定了聚类属性权重,最终得到了更加准确和稳定的聚类结果。但当遇到一些数据,其维度的稀疏性较大,将会给多维数据的聚类带来很大问题。为了能够有效地解决稀疏多维数据所带来的聚类问题,本文提出了一种新的基于熵权重的Global K-means算法,即Global Entropy weighted K-means(GEWKM)算法.GEWKM算法结合了Entropy Weighting K-means(EWKM)算法的熵权重和Global K-means(GKM)算法的聚类框架,在GKM算法每次进行聚类中心的选取过程中,引入了Entropy Weighting K-means算法,采用更加合理的熵权重计算属性权重值,得到了更为理想的结果。实验表明,所提出的算法是稳定的,能够有效地解决数据稀疏性所带来的聚类问题。由于本文提出的GWKM算法和GEWKM算法都是基于Global K-means算法框架,但是由于Global K-means算法的计算复杂度较大,限制了其在海量数据上的应用,所以为了解决Global K-means算法计算复杂度大,不能满足处理大规模数据挖掘问题的时间要求,本文提出了基于GPU的并行Global K-means算法-PGKM_Mix算法,该算法并行了其中最为耗时的聚类中心的选取,为了更加充分地挖掘PGKM_Mix算法的数据并行性,进一步提出了PGKM IRG算法,该算法引入了非规则归约方法来并行聚类中心的更新。并着重描述了在GPU上实现这两种并行算法的设计方案和操作细节。通过人工数据集和UCI数据集上进行的实验,验证了并行算法在不影响性能的基础上实现了很高的加速比,说明了提出的并行算法的有效性。本文工作得到西安电子科技大学基本科研业务费资助项目(JY10000902033)资助。