计算机应用 ›› 2018, Vol. 38 ›› Issue (2): 483-490.DOI: 10.11772/j.issn.1001-9081.2017082053

• 数据科学与技术 • 上一篇    下一篇

基于密度峰值的混合型数据聚类算法设计

李晔1,2, 陈奕延1, 张淑芬2   

  1. 1. 中国市场学会 服务质量专业委员会, 北京 100048;
    2. 河北省数据科学与应用重点实验室(华北理工大学), 河北 唐山 063210
  • 收稿日期:2017-08-10 修回日期:2017-09-11 出版日期:2018-02-10 发布日期:2018-02-10
  • 通讯作者: 陈奕延
  • 作者简介:李晔(1992-),女,河北保定人,博士研究生,CCF会员,主要研究方向:机器学习、数据分析;陈奕延(1986-),男,北京人,工程师,经济师,博士研究生,CCF会员,主要研究方向:统计建模、技术经济;张淑芬(1972-),女,河北唐山人,教授,硕士,CCF会员,主要研究方向:云计算、数据安全、隐私保护。
  • 基金资助:
    河北省数据科学与应用重点实验室开放课题资助项目(20170320002)。

Design of mixed data clustering algorithm based on density peak

LI Ye1,2, CHEN Yiyan1, ZHANG Shufen2   

  1. 1. Service Quality Specialty Committee, Chinese Association of Market Development, Beijing 100048, China;
    2. Hebei Key Laboratory of Data Science and Application(North China University of Science and Technology), Tangshan Hebei 063210, China
  • Received:2017-08-10 Revised:2017-09-11 Online:2018-02-10 Published:2018-02-10
  • Supported by:
    This work is partially supported by the Open Project Program of Hebei Key Laboratory of Data Science and Application (20170320002).

摘要: 针对k-prototypes算法无法自动识别簇数以及无法发现任意形状的簇的问题,提出一种针对混合型数据的新方法:寻找密度峰值的聚类算法。首先,把CFSFDP(Clustering by Fast Search and Find of Density Peaks)聚类算法扩展到混合型数据集,定义混合型数据对象之间的距离后利用CFSFDP算法确定出簇中心,这样也就自动确定了簇的个数,然后其余的点按照密度从大到小的顺序进行分配。其次,研究了该算法中阈值(截断距离)及权值的选取问题:对于密度公式中的阈值,通过计算数据场中的势熵来自动提取;对于距离公式中的权值,利用度量数值型数据集和分类型数据集聚类趋势的统计量来定义。最后通过在三个实际混合型数据集上的测试发现:与传统k-prototypes算法相比,寻找密度峰值的聚类算法能有效提高聚类的精度。

关键词: 聚类分析, 混合型数据, 数据场, 聚类趋势, 密度峰值

Abstract: Focusing on the issue that k-prototypes algorithm is incapable of identifying automatically the number of clusters and discovering clusters with arbitrary shape, a mixed data clustering algorithm based on searching for density peaks was proposed. Firstly, CFSFDP (Clustering by fast Search and Find of Density Peaks) clustering algorithm was extended to mixed datasets in which the distances between mixed data objects were calculated to determine the cluster centers by using CFSFDP algorithm, that is, the number of clusters was determined automatically. The rest points were then assigned to the cluster in order of their density from large to small. Secondly, the selection method of threshold and weight in the proposed algorithm was introduced. In the density formula, the threshold (cutoff distance) was extracted automatically by calculating potential entropy of data field; in the distance formula, the weight was defined through certain statistic which can measure clustering tendency of numeric datasets and categorical datasets. Finally, experimental results on three real mixed datasets show that compared with k-prototypes algorithm, the proposed algorithm can effectively improve the accuracy of clustering.

Key words: cluster analysis, mixed data, data field, clustering trendency, density peak

中图分类号: