基于快速高斯变换的不确定数据聚类算法

doi:10.11959/j.issn.1000-436x.2017061

通信学报 ›› 2017, Vol. 38 ›› Issue (3): 101-111.doi: 10.11959/j.issn.1000-436x.2017061

基于快速高斯变换的不确定数据聚类算法

迟荣华¹,程媛^2,³,朱素霞²,黄少滨¹,陈德运^2,³

¹ 哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨 150001
² 哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨 150080
³ 哈尔滨理工大学计算机科学与技术学院博士后流动站，黑龙江哈尔滨 150080

修回日期:2016-09-15 出版日期:2017-03-01 发布日期:2017-04-13
作者简介:迟荣华（1981-），男，黑龙江哈尔滨人，哈尔滨工程大学博士生，主要研究方向为复杂网络、不确定性研究等。|程媛（1985-），女，黑龙江哈尔滨人，哈尔滨理工大学讲师，主要研究方向为数据挖掘、不确定性研究等。|朱素霞（1978-），女，山东寿光人，哈尔滨理工大学副教授，主要研究方向为高性能体系结构、并行计算。|黄少滨（1965-），男，黑龙江哈尔滨人，哈尔滨工程大学教授、博士生导师，主要研究方向为分布式计算与仿真、模型检测、数据集成等。|陈德运（1962-），男，黑龙江哈尔滨人，哈尔滨理工大学教授、博士生导师，主要研究方向为图像处理、探测和成像技术。
基金资助:
国家自然科学青年基金资助项目(61502123);黑龙江省青年科学基金资助项目(QC2015084);黑龙江省普通高等学校青年学术骨干支持计划基金资助项目(1253G017)

Uncertain data analysis algorithm based on fast Gaussian transform

Rong-hua CHI¹,Yuan CHENG^2,³,Su-xia ZHU²,Shao-bin HUANG¹,De-yun CHEN^2,³

¹ College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China
² College of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China
³ Postdoctoral Research Station,College of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China

Revised:2016-09-15 Online:2017-03-01 Published:2017-04-13
Supported by:
The National Natural Science Foundation of China for Youths(61502123);Heilongjiang Province Science Foundation for Youths(QC2015084);Heilongjiang Province Support Program for Youth Academic Backbones in Regular Institutions of Higher Education(1253G017)

摘要/Abstract

摘要：

数据中不确定性的存在使对其聚类分析时要充分考虑不确定性的影响。针对现有不确定数据聚类算法中构建不确定数据模型以及距离度量时存在的影响结果准确性与聚类性能等问题，提出一种基于快速高斯变换的不确定数据聚类算法。首先在不假设数据分布的前提下，构建符合不确定性分布特征的数据模型；然后结合不确定对象的2个重要特征：属性特征与表示不确定数据分布特征的概率密度函数，度量不确定数据对象间的相似性；并以此为基础提出不确定数据聚类算法；最后在UCI以及真实数据集上的实验结果表明，所提算法在运行效率和聚类准确性方面均能取得较好效果。

关键词: 聚类分析, 不确定数据, 概率密度函数, 快速高斯变换, 核密度估计

Abstract:

The effect of the uncertainties needs to be taken full advantage during uncertain data clustering.An uncertain data clustering algorithm based on fast Gaussian transform was proposed,to solve the problems about the impact on the accuracy of clustering results and the clustering efficiency caused by the uncertainties,during the construction of uncertain data models and the distance measurement,which existed in the current researches.First,the data model according to the characteristic of the uncertainty distribution was constructed,without the premise of assuming the data distribution.And the similarity between uncertain data objects was measured by combining the two important features of uncertain objects,attribute features and the probability density function representing the characteristic of uncertainty distribution.And then the uncertain data clustering algorithm was proposed.Finally,the experiment results on UCI and real datasets indicate the better efficiency and accuracy of proposed algorithm.

Key words: clustering analysis, uncertain data, probability density function, fast Gaussian transform, kernel density estimation

中图分类号:

TP399

迟荣华,程媛,朱素霞,黄少滨,陈德运. 基于快速高斯变换的不确定数据聚类算法[J]. 通信学报, 2017, 38(3): 101-111.

Rong-hua CHI,Yuan CHENG,Su-xia ZHU,Shao-bin HUANG,De-yun CHEN. Uncertain data analysis algorithm based on fast Gaussian transform[J]. Journal on Communications, 2017, 38(3): 101-111.

图/表 11

图1

表1

表2

图2

图3

图4

表3

表4

图5

图6

图7

参考文献 29

[1]	WANG Y , LI X , LI X ,et al. A survey of queries over uncertain data[J]. Knowledge and Information Systems, 2013,37(3): 485-530.
[2]	SEN P , DESHPANDE A . Representing and querying correlated tuples in probabilistic databases[C]// IEEE 23rd International Conference on Data Engineering. Istanbul,Turkey,IEEE, 2007: 596-605.
[3]	MUZAMMAL M , RAMAN R . Mining sequential patterns from probabilistic databases[J]. Knowledge and Information Systems, 2015,44(2): 325-358.
[4]	SOLIMAN M , ILYAS I , CHANG K . Top-k query processing in uncertain databases[C]// IEEE 23rd International Conference on Data Engineering. Istanbul,Turkey,IEEE, 2007: 896-905.
[5]	AGGARWAL C . Managing and mining uncertain data[M]. USA: SpringerPress, 2009: 1-35.
[6]	BARBARá D , GARCIA-MOLINA H , PORTER D . The management of probabilistic data[J]. IEEE Transactions on Knowledge and Data Engineering, 1992,4(5): 487-502.
[7]	ANTOVA L , JANSEN T , KOCH C ,et al. Fast and simple relational processing of uncertain data[C]// IEEE 24th International Conference on Data Engineering. Cancun,Mexico,IEEE, 2008: 983-992.
[8]	TANG R , CHENG R , WU H ,et al. A framework for conditioning uncertain relational data[J]. Database and Expert Systems Applications, 2012,37(3): 71-87.
[9]	TASKAR B , SEGAL E , KOLLER D . Probabilistic classification and clustering in relational data[C]// The Seventeenth International Joint Conference on Artificial Intelligence.San Francisco,USA:Morgan Kaufmann Publishers Inc. 2001: 870-878.
[10]	NGAI W K , KAO B , CHUI C K ,et al. Efficient clustering of uncertain data[C]// The Sixth International Conference on Data Mining. 2006: 436-445.
[11]	KRIEGEL H , PFEIFLE M . Density-based clustering of uncertain data[C]// The 11st ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. Chicago,USA:ACM, 2005: 672-677.
[12]	KRIEGEL H , PFEIFLE M . Hierarchical density-based clustering of uncertain data[C]// Fifth IEEE International Conference on Data Mining. Houston,USA,IEEE, 2005: 689-692.
[13]	李云飞, 王丽珍, 周丽华 . 不确定数据的高效聚类算法[J]. 广西师范大学学报：自然科学版, 2011,29(2): 161-166.
	LI Y F , WANG L Z , ZHOU L H . More efficient clustering algorithm over uncertain data[J]. Journal of Guangxi Normal University (Natural Science Edition), 2011,29(2): 161-166.
[14]	金萍, 宗瑜, 屈世超 ,等. 面向不确定数据的近似骨架启发式聚类算法[J]. 南京大学学报 (自然科学), 2015,51(1): 197-205.
	JIN P , ZONG Y , QU S C ,et al. Approximate backbone guided heuristic clustering algorithm for uncertain data[J]. Journal of Nanjing University (Natural Sciences), 2015,51(1): 197-205.
[15]	肖宇鹏, 何云斌, 万静 ,等. 基于模糊 C-均值的空间不确定数据聚类[J]. 计算机工程, 2015,41(10): 47-52.
	XIAO Y P , HE Y B , WAN J ,et al. Clustering of space uncertain data based on fuzzy C-means[J]. Computer Engineering, 2015,41(10): 47-52.
[16]	CORMODE G , MCGREGOR A . Approximation algorithms for clustering uncertain data[C]// The 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. Vancouver,Canada,ACM, 2008: 191-200.
[17]	ZüFLE A , EMRICH T , SCHMID K A ,et al. Representative clustering of uncertain data[C]// The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York,USA,ACM, 2014: 243-252.
[18]	SCHUBERT E , KOOS A , EMRICH T ,et al. A framework for clustering uncertain data[C]// The 41st International Conference on Very Large Data Bases. Hawaii,USA,VLDB Endowment, 2015: 1976-1979.
[19]	XU L , HU Q , HUNG E ,et al. Large margin clustering on uncertain data by considering probability distribution similarity[J]. Neurocomputing, 2015,158: 81-89.
[20]	JIANG B , PEI J , TAO Y ,et al. Clustering uncertain data based on probability distribution similarity[J]. IEEE Transactions on Knowledge and Data Engineering, 2013,25(4): 751-763.
[21]	LóPEZ-RUBIO E , JOSE . Probability densty function estimation with the frequency polygon transform[J]. Information Science, 2015,298: 136-158.
[22]	ELGAMMAL A , DURAISWAMI R , DAVIS L S . Efficient kernel density estimation using the fast gauss transform with applications to color modeling and tracking[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003,25(11): 1499-1504.
[23]	SCOTT D . On optimal and data-based histograms[J]. Biometrika, 1979,66(3): 605-610.
[24]	GREENGARD L , STRAIN J . The fast Gauss transform[J]. SIAM Journal on Scientific and Statistical Computing, 1991,12(1): 79-94.
[25]	YANG C , DURAISWAMI R , GUMEROV N ,et al. Improved fast gauss transform and efficient kernel density estimation[C]// Ninth IEEE International Conference on Computer Vision. Nice,France:IEEE, 2003: 664-671.
[26]	ZHAO Y , KARYPIS G . Criterion functions for document clustering:experiment and analysis[R]. Technical Report TR 01-40,Department of Computer Science,University of Minnesota,USA, 2001.
[27]	MANNING C D , RAGHAVAN P , SCHUTZE H ，著. 王斌,译信息检索导论[M]. 北京: 人民邮电出版社, 2010.
	MANNING C D , RAGHAVAN P , SCHUTZE H.WANG B,translate WANG B ,translate. Introduction to information retrieval[M]. Beijing: PTPRESS, 2010.
[28]	DEMSAR J . Statistical comparisons of classifiers over multiple data sets[J]. Journal of Machine Learning Research, 2006(7): 1-30.
[29]	ARBELAITZ O , GURRUTXAGA I , MUGUERZA J ,et al. An extensive comparative study of cluster validity indices[J]. Pattern Recognition, 2013,46(1): 243-256.

数据集	对象个数	属性个数	类别数
Iris	150	4	3
Ecoli	336	8	8
Yeast	1 484	8	10
Abalone	4 177	8	16
Letter	20 000	16	26

服务人数	采集时间	经度/°	纬度/°
889	2013/2/4 1:00	126.683 3	45.750 97
888	2013/2/4 1:00	126.683 3	45.750 97
…	…	…	…
443	2013/2/4 2:00	126.683 3	45.750 97
441	2013/2/4 2:00	126.683 3	45.750 97
…	…	…	…
510	2013/2/4 1:00	128.038 8	45.950 6
…	…	…	…

指标	IUK-means& UK-means	IUK-means& MC	IUK-means& LMHIK
Purity	0.001	0.746	0.039
Entropy	0.001	0.446	0.027
NMI	0.001	0.353	0.002
F-measure	0.001	0.221	0.017

服务人数观测值	采集周期	经度/°	纬度/°
889 888 … 888 887	2013/2/4 1:00	126.683 3	45.7509 7
443 441 … 444 442	2013/2/4 1:00	126.683 3	45.7509 7
418 417 … 417 418	2013/2/4 1:00	126.683 3	45.7509 7
…	…	…	…
510 509 … 511 508	2013/2/4 1:00	128.038 8	45.950 6
…	…	…	…

基于快速高斯变换的不确定数据聚类算法

Uncertain data analysis algorithm based on fast Gaussian transform

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 29

相关文章 14

Metrics

推荐阅读 0

[1]	李骜, 冯聪, 牛宇童, 徐士彪, 张英涛, 孙广路. 面向视角非对齐数据的多视角聚类方法[J]. 通信学报, 2022, 43(7): 143-152.
[2]	张忠平, 刘伟雄, 张玉停, 邓禹, 魏棉鑫. ERDOF：基于相对熵权密度离群因子的离群点检测算法[J]. 通信学报, 2021, 42(9): 133-143.
[3]	赵春晖,李雪源,崔颖. 混合编码方式的图像聚类算法[J]. 通信学报, 2017, 38(2): 1-9.
[4]	房玉琢,许志勇,赵兆. 基于近似核密度估计的近场多声源定位算法[J]. 通信学报, 2017, 38(1): 106-116.
[5]	丁伟,徐杰,卓文辉. 基于层次聚类的网络流识别算法研究[J]. 通信学报, 2014, 35(Z1): 41-45.
[6]	丁伟，徐杰，卓文辉. 基于层次聚类的网络流识别算法研究[J]. 通信学报, 2014, 35(Z1): 9-45.
[7]	刘文杰1，伍之昂2，曹杰2，潘金贵1. 基于成对约束Info-Kmeans聚类的图像索引方法[J]. 通信学报, 2013, 34(7): 18-166.
[8]	刘文杰,伍之昂,曹杰,潘金贵. 基于成对约束Info-Kmeans聚类的图像索引方法[J]. 通信学报, 2013, 34(7): 159-166.
[9]	闫健恩1，袁春阳2，许海燕1，张兆心1. 基于多维流量特征的IRC僵尸网络频道检测[J]. 通信学报, 2013, 34(10): 6-55.
[10]	闫健恩,袁春阳,许海燕,张兆心. 基于多维流量特征的IRC僵尸网络频道检测[J]. 通信学报, 2013, 34(10): 49-55.
[11]	王亢,徐志江,孟利民. 对称alpha稳定分布的两段曲线逼近算法[J]. 通信学报, 2013, 34(1): 178-184.
[12]	周恩策,刘纯平,张玲燕,龚声蓉,刘全. 基于时间窗的自适应核密度估计运动检测方法[J]. 通信学报, 2011, 32(3): 106-115.
[13]	胡春华,罗新星,王四春,刘耀. 云计算环境下基于信任推理的服务评价方法[J]. 通信学报, 2011, 32(12): 72-81.
[14]	王博,贾焰,杨树强,周斌. 适用于不确定文本分类的特征选择算法[J]. 通信学报, 2009, 30(8): 32-38.