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 ( 2
输出: 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.
链接本文:  
http://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/10.11925/infotech.2096-3467.2017.0724      或      http://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]. 数据分析与知识发现, 0, (): 1-.
[2] 沈志宏,赵子豪,王海波. 以图为中心的新型大数据技术栈研究 *[J]. 数据分析与知识发现, 2020, 4(7): 50-65.
[3] 陈东,王建冬,李慧颖,蔡思航,黄倩倩,易成岐,曹攀. 融合机器学习算法和多因素的禽肉交易量预测方法研究 *[J]. 数据分析与知识发现, 2020, 4(7): 18-27.
[4] 徐以聪,田学东,李新福,杨芳,史青宣. 基于犹豫模糊权重的数学表达式检索 *[J]. 数据分析与知识发现, 2020, 4(7): 118-126.
[5] 梁野,李小元,许航,胡伊然. CLOpin:一种面向舆情分析与预警领域的跨语言知识图谱架构*[J]. 数据分析与知识发现, 2020, 4(6): 1-14.
[6] 刘伟江,魏海,运天鹤. 基于卷积神经网络的客户信用评估模型研究*[J]. 数据分析与知识发现, 2020, 4(6): 80-90.
[7] 于丰畅,陆伟. 一种学术文献图表位置标注数据集构建方法[J]. 数据分析与知识发现, 2020, 4(6): 35-42.
[8] 刘倩, 李晨亮. 基于社交媒体的话题演变研究综述 [J]. 数据分析与知识发现, 0, (): 1-.
[9] 沈喆, 王毅, 姚毅凡, 成颖. 面向学术文献的作者名消歧方法研究综述 [J]. 数据分析与知识发现, 0, (): 1-.
[10] 赵平,孙连英,涂帅,卞建玲,万莹. 改进的知识迁移景点实体识别算法研究及应用*[J]. 数据分析与知识发现, 2020, 4(5): 118-126.
[11] 李成梁,赵中英,李超,亓亮,温彦. 基于依存关系嵌入与条件随机场的商品属性抽取方法*[J]. 数据分析与知识发现, 2020, 4(5): 54-65.
[12] 朱路,田晓梦,曹赛男,刘媛媛. 基于高阶语义相关的子空间跨模态检索方法研究*[J]. 数据分析与知识发现, 2020, 4(5): 84-91.
[13] 叶光辉,曾杰妍,胡婧岚,毕崇武. 城市画像视角下的社会公众情感演化研究*[J]. 数据分析与知识发现, 2020, 4(4): 15-26.
[14] 余传明,原赛,朱星宇,林虹君,张普亮,安璐. 基于深度学习的热点事件主题表示研究*[J]. 数据分析与知识发现, 2020, 4(4): 1-14.
[15] 曾桢, 李纲, 毛进, 陈璟浩. 区域公共安全数据治理与业务领域本体研究 [J]. 数据分析与知识发现, 0, (): 1-.
Viewed
Full text


Abstract

Cited

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