GPU加速的改进PAM聚类算法研究与应用

发布时间：2018-02-10 12:46

本文关键词： K-Medoids 模拟退火 GPU 并行计算空间聚类分析　出处：《地球信息科学学报》2017年06期 　论文类型：期刊论文

【摘要】：空间聚类是空间数据挖掘的重要方法,而K-Medoids是一种常用的空间聚类算法。K-Medoids聚类算法存在初始点选择问题,而且计算复杂。为了提高算法的有效性和时间效率,本文结合模拟退火算法思想,改进了传统的K-Medoids算法PAM,提出一种基于GPU计算的并行模拟退火PAM算法。类比矩阵乘法运算,定义了一种新的矩阵计算方法,可以有效减少数据在GPU全局内存和共享内存之间的传输,提高了算法在GPU中的执行效率。利用模拟退火算法搜索聚类中心点,保证了聚类结果的全局最优性。基于不同的数据集,将串行和并行模拟退火PAM算法以及已有的遗传PAM算法进行比较,结果表明并行模拟退火PAM算法聚类结果正确,且时间效率高。最后,应用本文改进算法对贵州省安监系统的安全监管隐患数据进行聚类分析,发现了隐患聚集中心,相关结果对政府的决策具有一定的实际应用价值。
[Abstract]:Spatial clustering is an important method of spatial data mining, and K-Medoids is a commonly used spatial clustering algorithm. K-Medoids clustering algorithm has the problem of initial point selection, and the computation is complex. Based on the idea of simulated annealing, this paper improves the traditional K-Medoids algorithm, proposes a parallel simulated annealing PAM algorithm based on GPU computation, and defines a new method of matrix calculation by analogy to matrix multiplication. It can effectively reduce the transmission of data between GPU global memory and shared memory, and improve the efficiency of the algorithm in GPU. The simulated annealing algorithm is used to search the cluster center point. The global optimality of the clustering results is ensured. Based on different data sets, the serial and parallel simulated annealing PAM algorithm and the existing genetic PAM algorithm are compared. The results show that the parallel simulated annealing PAM algorithm clustering results are correct. And the time efficiency is high. Finally, the improved algorithm is used to cluster the hidden danger data of security supervision system in Guizhou province, and the hidden danger gathering center is found. The relevant results have some practical application value to the government decision-making.
【作者单位】：北京大学遥感与地理信息系统研究所;中国矿业大学(北京)资源与安全工程学院;
【基金】：国家重点研发计划重点专项(2016YFC0801800)
【分类号】：P208

【相似文献】