doi: 10.4304/jsw.9.3.732-737
CUDAP: A Novel Clustering Algorithm for Uncertain Data Based on Approximate Backbone
- 1 Information and Engineering School, West Anhui University, Luan, China
- 2 School of Computer Science, University of Science and Technology of China, Hefei, China
- 3 School of Software, Dalian University of Technology, Dalian, China
Abstract
Clustering for uncertain data is an interesting research topic in data mining. Researchers prefer to define uncertain data clustering problem by using combinatorial optimization model. Heuristic clustering algorithm is an efficient way to deal with this kind of clustering problem, but initialization sensitivity is one of inevitable drawbacks. In this paper, we propose a novel clustering algorithm named CUDAP (Clustering algorithm for Uncertain Data based on Approximate backbone). In CUDAP, we (1) make <em>M</em> times random sampling on the original uncertain data set <em>D<sup>m</sup></em> to generate <em>M</em> sampled data sets <em>DS</em>={<em>Ds</em><sub>1</sub>,<em>Ds</em><sub>2</sub>,…,<em>Ds<sub>M</sub></em>}; (2) capture the <em>M</em> local optimal clustering results <em>P</em>={<em>C</em><sub>1</sub>,<em>C</em><sub>2</sub>,…,<em>C<sub>M</sub></em>} from <em>DS</em> by running UK-Medoids algorithm on each sample data set <em>Ds<sub>i</sub></em>, <em>i</em>=1,…<em>M</em>; (3) design a greedy search algorithm to find out the approximate backbone(<em>APB</em>) from <em>P</em>; (4) run UK-Medoids again on the original uncertain data set <em>D<sup>m</sup></em><sup> </sup>guided by new initialization which was generated from <em>APB</em>. Experimental results on synthetic and real world data sets demonstrate the superiority of the proposed approach in terms of clustering quality measures.
Keywords
- NP-hard
- Problem;
- Uncertain
- Data
- Clusteri
How to Cite
Ping Jin, Shichao Qu, Yu Zong, and Xin Li, "CUDAP: A Novel Clustering Algorithm for Uncertain Data Based on Approximate Backbone," Journal of Software, vol. 9, no. 3, pp. 732-737, 2014. https://doi.org/ 10.4304/jsw.9.3.732-737
Copyright & License
Copyright © 2014 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).