文章基本信息

标题：CUDAP: A Novel Clustering Algorithm for Uncertain Data Based on Approximate Backbone
本地全文：下载
作者：Jin, Ping ; Qu, Shichao ; Zong, Yu 等
期刊名称：Journal of Software
印刷版ISSN：1796-217X
出版年度：2014
卷号：9
期号：3
页码：732-737
DOI：10.4304/jsw.9.3.732-737
语种：English
出版社：Academy Publisher
摘要：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 D^m to generate M sampled data sets DS= { Ds₁,Ds₂,…,Ds_M }; (2) capture the M local optimal clustering results P ={ C₁,C₂,…,C_M } from DS by running UK-Medoids algorithm on each sample data set Ds_i, 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 D^m 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.
关键词：NP-hard Problem;Uncertain Data Clustering Problem;Heuristic Clustering Algorithm;Approximate Backbone