Volume 9 Number 3 (Mar. 2014)
Home > Archive > 2014 > Volume 9 Number 3 (Mar. 2014) >
JSW 2014 Vol.9(3): 732-737 ISSN: 1796-217X
doi: 10.4304/jsw.9.3.732-737

CUDAP: A Novel Clustering Algorithm for Uncertain Data Based on Approximate Backbone

Ping Jin1, 2, Shichao Qu2, 3, Yu Zong1, Xin Li2
1Information and Engineering School, West Anhui University, Luan, China
2School of Computer Science, University of Science and Technology of China, Hefei, China
3School 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 M times random sampling on the original uncertain data set Dm to generate M sampled data sets DS={Ds1,Ds2,…,DsM}; (2) capture the M local optimal clustering results P={C1,C2,…,CM} from DS by running UK-Medoids algorithm on each sample data set Dsi, i=1,…M; (3) design a greedy search algorithm to find out the approximate backbone(APB) from P; (4) run UK-Medoids again on the original uncertain data set Dm guided by new initialization which was generated from APB. Experimental results on synthetic and real world data sets demonstrate the superiority of the proposed approach in terms of clustering quality measures.

Index Terms—NP-hard Problem; Uncertain Data Clustering Problem; Heuristic Clustering Algorithm; Approximate Backbone

[PDF]

Cite: Ping Jin, Shichao Qu, Yu Zong, 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.

General Information

ISSN: 1796-217X (Online)
Frequency:  Bimonthly (Since 2020)
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, Google Scholar, ProQuest, INSPEC(IET), ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Apr 26, 2021 News!

    Vol 14, No 4- Vol 14, No 12 has been indexed by IET-(Inspec)     [Click]

  • Jun 22, 2020 News!

    Papers published in JSW Vol 14, No 1- Vol 15 No 4 have been indexed by DBLP     [Click]

  • Sep 13, 2021 News!

    The papers published in Vol 16, No 6 have all received dois from Crossref    [Click]

  • Jan 28, 2021 News!

    [CFP] 2021 the annual meeting of JSW Editorial Board, ICCSM 2021, will be held in Rome, Italy, July 21-23, 2021   [Click]

  • Sep 13, 2021 News!

    Vol 16, No 6 has been published with online version     [Click]