Please wait a minute...
Advanced Search
数据分析与知识发现  2017, Vol. 1 Issue (12): 84-91     https://doi.org/10.11925/infotech.2096-3467.2017.0724
  研究论文 本期目录 | 过刊浏览 | 高级检索 |
基于局部密度的不确定数据聚类算法*
罗彦福1, 钱晓东2()
1兰州交通大学自动化与电气工程学院 兰州 730070
2兰州交通大学经济管理学院 兰州 730070
Uncertain Data Clustering Algorithm Based on Local Density
Luo Yanfu1, Qian Xiaodong2()
1School of Automation and Electrical Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China
2School of Economics and Management, Lanzhou Jiaotong University, Lanzhou 730070, China
全文: PDF (702 KB)   HTML ( 3
输出: BibTeX | EndNote (RIS)      
摘要 

目的】为解决由经典聚类算法改进而来的不确定数据聚类算法往往存在原有算法本身的缺点问题, 提出一种新的不确定数据聚类方法。【方法】改进不确定距离的度量方法, 确保两个不确定对象在以一定概率存在的前提下, 再进行二者概率差异的比较; 确定聚类中心后, 依据局部密度定义最大支持点、密度链域等概念, 据此提出一种将数据对象归入相应聚类中心所在簇的新算法。【结果】利用UCI机器学习库中的数据集验证本文聚类算法, 实验结果表明, F值较传统不确定数据聚类算法(UK-Means和FDBSCAN)在两组数据集上分别最高提升13.23%和23.44%, 算法主要在计算距离矩阵的过程中用时较多, 整体聚类时间相较于传统算法略有优势, 但不明显。【局限】本文唯一需要设定的参数的选取尚无准确的指导方法; 未采用并行计算, 使得算法时间复杂度较高。【结论】若直接以数据集的距离矩阵作为输入, 本文算法能快速确定聚类中心并完成聚类, 而且具有良好的聚类准确率; 唯一的参数t值对聚类结果影响较大。

服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
罗彦福
钱晓东
关键词 不确定数据截止距离局部密度密度链域    
Abstract

[Objective] This paper proposes a new algorithm to cluster uncertain data, aiming to reduce the shortcomings inherited from the classic ones. [Methods] First, we modified the measurement of uncertain distance and compared the probability differences between two existing uncertain objects. Then, we defined the cluster centers and proposed a new algorithm to group the data into the related clusters based on the concepts of maximum supporting points and density chain regions. [Results] We used two data sets from the UCI machine learning library to examine the proposed algorithm. We found that the F values of the two data sets increased by 13.23% and 23.44% compared to traditional algorithm (UK-Means and FDBSCAN). It took the algorithm longer time to calculate the distance matrix. Therefore, the overall clustering time was only slightly shorter than the traditional algorithm. [Limitations] There was no appropriate method to define the parameter for the proposed algorithm, and the clustering time was complex. [Conclusions] The proposed algorithm could quickly determine the clustering centers and complete the clustering tasks. The value of t (the only parameter) poses much influence to the clustering results.

Key wordsUncertain Data    Cut-off Distance    Local Density    Density Chain Region
收稿日期: 2017-07-24      出版日期: 2017-12-29
ZTFLH:  TP393  
基金资助:*本文系国家自然科学基金项目“基于复杂网络的商务大数据聚类与管理应用研究”(项目编号: 71461017)的研究成果之一
引用本文:   
罗彦福, 钱晓东. 基于局部密度的不确定数据聚类算法*[J]. 数据分析与知识发现, 2017, 1(12): 84-91.
Luo Yanfu,Qian Xiaodong. Uncertain Data Clustering Algorithm Based on Local Density. Data Analysis and Knowledge Discovery, 2017, 1(12): 84-91.
链接本文:  
https://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/10.11925/infotech.2096-3467.2017.0724      或      https://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/Y2017/V1/I12/84
  密度链和密度链域
  Iris数据集聚类中心
簇号 聚类中心(标号) 簇内点的个数 离群点个数
1 28 P: 50; N: 0 2
2 92 P: 50; N: 3
3 148 P: 28; N: 17
  Iris数据集聚类结果
  Connect-4数据集聚类中心
簇号 聚类中心(标号) 簇内点的个数 离群点个数
1 687 P: 4467; N: 0 0
2 829 P: 16635; N: 42
3 29878 P: 44473; N: 1940
  Connect-4数据集聚类结果
算法 F值 运行时间(s)
Iris Connect-4 Iris Connect-4
UK-Means 0.8865 0.8017 0.0261 41.2505
FDBSCAN 0.7983 0.7430 0.0442 47.3241
本文算法 0.9854 0.9085 0.0250 37.9223
  不同算法实验结果对比
[1] 李建中, 王宏志, 高宏. 大数据可用性的研究进展[J]. 软件学报, 2016, 27(7): 1605-1625.
doi: 10.13328/j.cnki.jos.005038
[1] (Li Jianzhong, Wang Hongzhi, Gao Hong.State-of-the-Art of Research on Big Data Usability[J]. Journal of Software, 2016, 27(7): 1605-1625.)
doi: 10.13328/j.cnki.jos.005038
[2] Anagnostopoulos A, Dasgupta A, Kumar R.Approximation Algorithms for Co-Clustering[C]// Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM, 2008:201-210.
[3] Kanagal B, Deshpande A. Online Filtering, Smoothing and Probabilistic Modeling of Streaming Data[C]// Proceedings of the 24th International Conference on Data Engineering. IEEE, 2008:1160-1169.
[4] Ré C, Letchner J, Balazinksa M, et al.Event Queries on Correlated Probabilistic Streams[C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. ACM, 2008:715-728.
[5] Chau M, Cheng R, Kao B, et al.Uncertain Data Mining: An Example in Clustering Location Data [A]// Advances in Knowledge Discovery and Data Mining[M]. Springer Berlin Heidelberg, 2006: 199-204.
[6] 刘位龙. 面向不确定性数据的聚类算法研究[D]. 济南: 山东师范大学, 2011.
[6] (Liu Weilong.Research on Clustering Algorithm for Uncertainty Data[D]. Ji’nan: Shandong Normal University, 2011.)
[7] Gullo F, Ponti G, Tagarelli A.Clustering Uncertain Data via K-Medoids [A]// Scalable Uncertainty Management[M]. Springer Berlin Heidelberg, 2008: 229-242.
[8] Xu H J, Li G H.Density-based Probabilistic Clustering of Uncertain Data[C]//Proceeedings of the 2008 International Conference on Computer Science and Software Engineering. 2008: 474-477.
[9] Kriegel H P, Pfeifle M.Hierarchical Density-Based Clustering of Uncertain Data[C]//Proceedings of the 5th IEEE Conference on Data Mining. 2005:689-692.
[10] 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.
doi: 10.1109/TKDE.2011.221
[11] 潘冬明, 黄德才. 基于相对密度的不确定数据聚类算法[J]. 计算机科学, 2015, 42(11A): 72-74.
[11] (Pan Dongming, Huang Decai.Relative Density-based Clustering Algorithm over Uncertain Data[J]. Computer Science, 2015, 42(11A): 72-74.)
[12] Liu H, Zhang X, Zhang X, et al.Self-adapted Mixture Distance Measure for Clustering Uncertain Data[J]. Knowledge-Based Systems, 2017, 126: 33-47.
doi: 10.1016/j.knosys.2017.04.002
[13] Gullo F, Ponti G, Tagarelli A, et al.An Information-Theoretic Approach to Hierarchical Clustering of Uncertain Data[J]. Information Sciences, 2017,402:199-215.
doi: 10.1016/j.ins.2017.03.030
[14] 迟荣华, 程媛, 朱素霞, 等. 基于快速高斯变换的不确定数据聚类算法[J]. 通信学报, 2017, 38(3): 101-111.
[14] (Chi Ronghua, Cheng Yuan, Zhu Suxia, et al.Uncertain Data Analysis Algorithm Based on Fast Gaussian Transform[J]. Journal of Communications, 2017, 38(3): 101-111)
[15] Rodriguez A, Laio A. Machine Learning.Clustering by Fast Search and Find of Density Peaks[J]. Science, 2014, 344(6191): 1492-1496.
[1] 陈杰,马静,李晓峰. 融合预训练模型文本特征的短文本分类方法*[J]. 数据分析与知识发现, 2021, 5(9): 21-30.
[2] 李文娜,张智雄. 基于置信学习的知识库错误检测方法研究*[J]. 数据分析与知识发现, 2021, 5(9): 1-9.
[3] 孙羽, 裘江南. 基于网络分析和文本挖掘的意见领袖影响力研究 [J]. 数据分析与知识发现, 0, (): 1-.
[4] 王勤洁, 秦春秀, 马续补, 刘怀亮, 徐存真. 基于作者偏好和异构信息网络的科技文献推荐方法研究*[J]. 数据分析与知识发现, 2021, 5(8): 54-64.
[5] 李文娜, 张智雄. 基于联合语义表示的不同知识库中的实体对齐方法研究*[J]. 数据分析与知识发现, 2021, 5(7): 1-9.
[6] 王昊, 林克柔, 孟镇, 李心蕾. 文本表示及其特征生成对法律判决书中多类型实体识别的影响分析[J]. 数据分析与知识发现, 2021, 5(7): 10-25.
[7] 杨晗迅, 周德群, 马静, 罗永聪. 基于不确定性损失函数和任务层级注意力机制的多任务谣言检测研究*[J]. 数据分析与知识发现, 2021, 5(7): 101-110.
[8] 徐月梅, 王子厚, 吴子歆. 一种基于CNN-BiLSTM多特征融合的股票走势预测模型*[J]. 数据分析与知识发现, 2021, 5(7): 126-138.
[9] 黄名选,蒋曹清,卢守东. 基于词嵌入与扩展词交集的查询扩展*[J]. 数据分析与知识发现, 2021, 5(6): 115-125.
[10] 王晰巍,贾若男,韦雅楠,张柳. 多维度社交网络舆情用户群体聚类分析方法研究*[J]. 数据分析与知识发现, 2021, 5(6): 25-35.
[11] 阮小芸,廖健斌,李祥,杨阳,李岱峰. 基于人才知识图谱推理的强化学习可解释推荐研究*[J]. 数据分析与知识发现, 2021, 5(6): 36-50.
[12] 刘彤,刘琛,倪维健. 多层次数据增强的半监督中文情感分析方法*[J]. 数据分析与知识发现, 2021, 5(5): 51-58.
[13] 陈文杰,文奕,杨宁. 基于节点向量表示的模糊重叠社区划分算法*[J]. 数据分析与知识发现, 2021, 5(5): 41-50.
[14] 张国标,李洁. 融合多模态内容语义一致性的社交媒体虚假新闻检测*[J]. 数据分析与知识发现, 2021, 5(5): 21-29.
[15] 闫强,张笑妍,周思敏. 基于义原相似度的关键词抽取方法 *[J]. 数据分析与知识发现, 2021, 5(4): 80-89.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 2015 《数据分析与知识发现》编辑部
地址:北京市海淀区中关村北四环西路33号 邮编:100190
电话/传真:(010)82626611-6626,82624938
E-mail:jishu@mail.las.ac.cn