Journal of Guangxi Normal University(Natural Science Edition) ›› 2011, Vol. 29 ›› Issue (2): 161-166.

Previous Articles     Next Articles

More Effcient Clustering Algorithm Over Uncertain Data

LI Yun-fei, WANG Li-zhen, ZHOU Li-hua   

  1. School of Information Science and Engineering,Yunnan University,Kunming Yunnan 650091,China
  • Received:2011-05-08 Published:2018-11-19

Abstract: Clustering of uncertain data is an important researchdirection in the clustering research field.It has far-reaching applications inreal life.An improved clustering algorithm kd-means is proposed by optimizingclassical ck-means algorithm.The ck-means algorithm needs to calculate the distance of each cluster to the centroid of all objects,so when thesample is large,the clustering efficiency is not very good.The improved algorithm based on the kd-tree structure presented in the paper only needs to calculate part of the distances,which greatly improves the performance of the ck-means algorithm.Experiments demonstrate that the new algorithm is efficient.

Key words: kd-tree, ck-means algorithm, expected centroid, candidate set, pruning

CLC Number: 

  • TP391
[1] HAN Jia-wei,KAMBER M.DataMining:concepts and techniques[M].SanFrancisco:Morgan Kaufmann Publishers,2000.
[2] CHAU M,CHENG R,KAO B.Uncertain data mining:a new research direction[C]//Proceeding Workshop on the Sciences of the Artificial.Washington DC:IEEE Computer Society,2005:199-204.
[3] NGAI W K,KAO B,CHUI C K,et al.Efficient clustering of uncertain data[C]//Proceeding of the 6th IEEE International Conference on Data Mining (ICDM 2006).Washington DC:IEEE Computer Society,2006:436-445.
[4] KRIEGEL H P,PFEIFLE M.Hierarchical density-based clustering of uncertain data[C]//Proceedings of the 5th IEEE International Conference on DataMining (ICDM 2005).Washington DC:IEEE Computer Society,2005:689-692.
[5] NG R T,HAN Jia-wei.Efficient and effective clustering methods forspatial datamining[C]//Proceedings of the VLDB Conference.Santiago:Morgan Kaufmann,1994:144-155.
[6] GUHA S,RASTOGI R,SHIM K.CURE:an efficient clustering algorithm forlarge databases[J].Information Systems,2001,26(1):35-58.
[7] ELKAN C.Using the triangle inequality to accelerate k-means[C]//Proceeding of the International Conference on Machine Learning 2003 (ICML 2003).Washington DC:IEEE Press,2003:609-616.
[8] CHENG R,KALASHNIKOV D,PRABHAKAR S.Querying imprecise data in moving object environments[J].IEEE Transactions on Knowledge and Data Engineering,2004,16(9):1112-1127.
[9] MICHAEL C,REYNOLD C,BEN K,et al.Uncertain data mining:an example in clustering location data[C]//Proceeding of the 10th Pacific-Asia Conferenceon Knowledge Discovery and Data Mining (PAKDD 2006).Berlin:Springer Verlag,2006:199-204.
[10] LEE S D,KAO B,CHENG R.Reducing uk-means to K-means[C]//The 1st Workshop on Data Mining of Uncertain Data (DUNE),in conjunction with ICDM.Trenton,NJ:IEEE Press,2007:483-488.
[1] ZHANG Canlong, LI Yanru, LI Zhixin, WANG Zhiwen. Block Target Tracking Based on Kernel Correlation Filter and Feature Fusion [J]. Journal of Guangxi Normal University(Natural Science Edition), 2020, 38(5): 12-23.
[2] WANG Jian, ZHENG Qifan, LI Chao, SHI Jing. Remote Supervision Relationship Extraction Based on Encoder and Attention Mechanism [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(4): 53-60.
[3] XIAO Yiqun, SONG Shuxiang, XIA Haiying. Fast Pedestrian Detection Method Based on Multi-Features    and Implementation [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(4): 61-67.
[4] WANG Xun, LI Tinghui, PAN Xiao, TIAN Yu. Image Segmentation Method Based on Improved Fuzzy C-means Clustering and Otsu Maximum Variance [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(4): 68-73.
[5] CHEN Feng,MENG Zuqiang. Topic Discovery in Microblog Based on BTM and Weighting K-Means [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(3): 71-78.
[6] ZHANG Suiyuan, XUE Yuanhai, YU Xiaoming, LIU Yue, CHENG Xueqi. Research on Short Summary Generation of Multi-Document [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(2): 60-74.
[7] SUN Ronghai, SHI Linfu, HUANG Liyan, TANG Zhenjun, YU Chunqiang. Reversible Data Hiding Based on Image Interpolation and Reference Matrix [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(2): 90-104.
[8] ZHU Yongjian, PENG Ke, QI Guangwen, XIA Haiying, SONG Shuxiang. Defect Detection of Solar Panel Based on Machine Vision [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(2): 105-112.
[9] WANG Qi,QIU Jiahui,RUAN Tong,GAO Daqi,GAO Ju. Recurrent Capsule Network for Clinical Relation Extraction [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(1): 80-88.
[10] WU Wenya,CHEN Yufeng,XU Jin’an,ZHANG Yujie. High-level Semantic Attention-based Convolutional Neural Networks for Chinese Relation Extraction [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(1): 32-41.
[11] YUE Tianchi, ZHANG Shaowu, YANG Liang, LIN Hongfei, YU Kai. Stance Detection Method Based on Two-Stage Attention Mechanism [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(1): 42-49.
[12] YU Chuanming,LI Haonan,AN Lu. Analysis of Text Emotion Cause Based on Multi-task Deep Learning [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(1): 50-61.
[13] LIN Yuan, LIU Haifeng, LIN Hongfei, XU Kan. Group Ranking Methods with Loss Function Incorporation [J]. Journal of Guangxi Normal University(Natural Science Edition), 2019, 37(1): 62-70.
[14] WAN Fucheng,MA Ning,HE Xiangzhen. Tibetan Information Extraction Technology Integrated with Event Feature and Semantic Role Labeling [J]. Journal of Guangxi Normal University(Natural Science Edition), 2018, 36(2): 18-23.
[15] XIA Haiying,LIU Weitao,ZHU Yongjian. An Improved Fast SUSAN Chessboard Corner Detection Algorithm [J]. Journal of Guangxi Normal University(Natural Science Edition), 2018, 36(1): 44-52.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!