基于贝叶斯距离的K-modes聚类算法

计算机工程与科学

基于贝叶斯距离的K-modes聚类算法

赵亮1,刘建辉2,张昭昭2

(1.辽宁工程技术大学研究生院,辽宁阜新 123000;2.辽宁工程技术大学电子与信息工程学院,辽宁葫芦岛 125000)

收稿日期:2015-06-05 修回日期:2015-11-27 出版日期:2017-01-25 发布日期:2017-01-25
基金资助:
国家自然基金(61440059)；辽宁省自然基金(LS2013129)

A K-modes clustering algorithm
based on Bayes distance measure

ZHAO Liang1,LIU Jianhui2,ZHANG Zhaozhao2

(1.Institute of Graduate,Liaoning Technical University,Fuxin 123000;

2.School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125000,China)

Received:2015-06-05 Revised:2015-11-27 Online:2017-01-25 Published:2017-01-25

摘要/Abstract

摘要：

K-modes算法中原有的分类变量间距离度量方法无法体现属性值之间差异，对此提出了一种基于朴素贝叶斯分类器中间运算结果的距离度量。该度量构建代表分类变量的特征向量并计算向量间的欧氏距离作为变量间的距离。将提出的距离度量代入Kmodes聚类算法并在多个UCI公共数据集上与其他度量方法进行比较，实验结果表明该距离度量更加有效。

关键词: K-modes聚类算法, 分类变量, 朴素贝叶斯分类器, 距离度量

Abstract:

The original distance measure of Kmodes clustering algorithm cannot reflect the difference between categorical variables. To overcome this drawback, we propose a new distance measure algorithm based on the intermediate result of Nave Bayes classifier. This algorithm constructs feature vectors to present categorical variables and uses the Euclidean distance of the feature vectors as distance between variables. We implement the Kmodes algorithm with the new derived measure and the experiments on extensive UCI data sets show that the proposal is more effective in comparison with other measure algorithms.

Key words: K-modes clustering algorithm, categorical variables, Nave Bayes classifier, distance measure

赵亮1,刘建辉2,张昭昭2. 基于贝叶斯距离的K-modes聚类算法[J]. 计算机工程与科学.

ZHAO Liang1,LIU Jianhui2,ZHANG Zhaozhao2. A K-modes clustering algorithm

based on Bayes distance measure

[J]. Computer Engineering & Science.

参考文献［12］

［1］	Han Jiawei,Kamber M,Pei Jian.Data mining:Concepts and
	techniques ［M］.California:Morgan Kaufmann,2006:211220.
［2］	Gan Guojun,Ma Chaoqun,Wu Jianhong.Data clustering:Theory,algorithms,and applications［M］.Philadelphia:Siam,2007.
［3］	Huang Zhexue. A fast clustering algorithm to cluster very large categorical data sets in data mining［C］∥Proc of ACM SIGMOD Workshop on Data Mining and Knowledge Discovery,1998:146151.
［4］	Boriash S,Chandola V,Kumar V.Similarity measures for categorical data:A comparative evaluation ［C］∥Proc of the 2008 SIAM International Conference on Data Mining,2008:243254.
［5］	Ng M K,Li M J,Huang J Z,et al.On the impact of dissimilarity measure in kmodes clustering algorithm ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(3):503507.
［6］	San O M,Huynh V N,Nakamori Y.An alternative extension of the kmeans algorithm for clustering categorical data ［J］.International Journal of Applied Mathematics and Computer Science,2004,14(2):241248.
［7］	Stanfill C,Waltz D.Toward memorybased reasoning ［J］.
	Communications of the ACM,1986,29(12):12131228.
［8］	Cost S,Salzberg S.A weighted nearest neighbor algorithm for learning with symbolic features ［J］.Machine Learning,1993,10(1):5778.
［9］	Wilson D R,Martinez T R.Improved heterogeneous distance functions ［J］.Journal of Artificial Intelligence Research,1997,6(1):134.
［10］	Ahmad A,Dey L.A kmean clustering algorithm for mixed numeric and categorical data［J］.Data & Knowledge Engineering,2007,63(2):503527.
［11］	Wang C,Cao L,Wang M,et al.Coupled nominal similarity in unsupervised learning［C］∥Proc of the 20th ACM International Conference on Information and Knowledge Management,2011:973978.
［12］	Liang Jiye,Bai Liang,Cao Fuyuan.Kmodes clustering algorithm based on a new distance measure［J］.Journal of Computer Research and Development,2010,47(10):17491755.(in Chinese)
	附中文参考文献：
	梁吉业,白亮,曹付元.基于新的距离度量的 Kmodes 聚类算法［J］.计算机研究与发展,2010,47(10):17491755.

[1]	黄浩淼, 张江, 张晶, 保峻嵘. 融合TLD框架的DSST实时目标跟踪改进算法[J]. 计算机工程与科学, 2020, 42(09): 1587-1598.
[2]	马慧, 魏立力. 加权犹豫三角模糊距离度量及其在群决策中的应用[J]. 计算机工程与科学, 2020, 42(08): 1430-1439.
[3]	邵俊健，王士同. 高维数据的增量式聚类算法的距离度量选择研究[J]. 计算机工程与科学, 2019, 41(02): 214-223.
[4]	张新红1，张帆2，张军亮2. 一种改进的二值图像质量评价方法[J]. J4, 2010, 32(6): 52-54.