An AP Clustering Algorithm of Fine-Grain Parallelism Based on Improved Attribute Reduction

Affinity propagation (AP) clustering simultaneously considers all data points as potential exemplars. It takes similarity between pairs of data points as input measures, and clusters gradually during the message-passing procedure. AP is an efficient and fast clustering algorithm for large dataset compared with the existing clustering algorithms. Therefore, attributes reduction is important for AP. Meanwhile, fine-grain parallelism is emphasized in the design of massively parallel computers to acquire higher performance. In this paper, an AP clustering algorithm based on improved attribute reduction and fine-grain parallelism (IRPAP) is proposed. Firstly, granularity is introduced into parallel computing and granularity principle is applied as well. Secondly, data set is preprocessed by the improved attribute reduction algorithm through which elements in discernibility matrix will be calculated and selected in parallel, in order to reduce the complexity of time and space. Finally, data set is clustered by means of a parallel AP algorithm. The whole task can be divided into multiple threads to be processed simultaneously. Experimental results show that the IRPAP algorithm is more efficient than the AP algorithm for large data set clustering.