Computer and Modernization

    Next Articles

A Novel Fuzzy C-Means Algorithm Based on k-d Tree

  

  1. （College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China）
  • Received:2015-08-03 Online:2015-11-12 Published:2015-11-16

Abstract: Abstract: The performance of the Fuzzy C-Means(FCM) algorithm largely depends on the selection of the initial cluster center. A set of good initial cluster centers which are close to the actual final cluster center will not only speed up the rate of convergence but also reduce the overall processing time of the FCM dramatically. In this paper, we propose a novel FCM algorithm based on k-d tree which is a kind of multidimensional binary tree. The original data sets are split into several grids by using k-d tree. Then we form a new simplified data set by using the weighted centers of the grids, and based on which we find a good initial cluster center that is close to actual final cluster center so that reduce the iterations of FCM signally. The experiments on sixteen artificial datasets and real-life image data show that comparing with original FCM algorithm, the convergence rate of the proposed algorithm is advanced nearly twice as FCM algorithm, and the overall processing time reduce to less than half of the FCM.

Key words: Fuzzy C-Means cluster algorithm, k-d tree, initial cluster center, unsupervised learning

CLC Number: