基于传递距离的谱聚类算法

doi:10.3969/j.issn.1006-2475.2018.12.012

计算机与现代化

基于传递距离的谱聚类算法

(1.中国电信股份有限公司扬州分公司,江苏扬州225002;2.扬州大学信息工程学院,江苏扬州225127)

收稿日期:2018-05-22 出版日期:2019-01-03 发布日期:2019-01-04
作者简介:戴天辰(1993-),男,江苏扬州人,中国电信股份有限公司扬州分公司员工,硕士,研究方向:模式识别; 顾正弘(1985-),男,江苏泰州人,扬州大学信息工程学院讲师,博士,研究方向:模式识别。

Spectral Clustering Algorithm Based on Transitive Distance

(1. Yangzhou Branch, China Telecom, Yangzhou 225002, China;
2.College of Information Engineering, Yangzhou University， Yangzhou 225127, China)

Received:2018-05-22 Online:2019-01-03 Published:2019-01-04

摘要/Abstract

摘要： 谱聚类算法受到度量中尺度因子的影响，同时传统谱聚类算法通过欧氏距离度量样本间相似性也不准确。针对上述问题，提出一种基于传递距离的谱聚类算法。算法首先通过改进传统谱聚类中的度量方式，用基于传递距离的度量方式度量样本间相似性，并构建传递矩阵，接着用传递矩阵做相似度变换构建拉普拉斯矩阵，最终通过求特征值和特征向量完成聚类。基于传递距离的谱聚类算法在人工数据集及UCI数据集上均取得了良好的聚类结果，具有较好的鲁棒性和有效性。

关键词: 谱聚类, 尺度因子, 传递距离, 传递矩阵

Abstract: Spectral clustering algorithms are influenced by the mesoscale factors of metrics, and similarity measured by Euclidean distance is not always accurate. In view of this situation, a spectral clustering algorithm based on transitive distance is proposed. The main idea contains three steps. First, a minimum spanning tree is constructed to do a similarity transformation, as a result a transfer matrix is generated. Second, we construct a Laplacian matrix by the transfer matrix of the first step. Data is projected into the eigen-space of this Laplacian matrix. Lastly, the clustering in the space of the second step is done. The experimental results on artificial data sets and UCI data sets show that the spectral clustering algorithm based on the transitive distance has good robustness and effectiveness.

Key words: spectral clustering, mesoscale factors, transitive distance, transitive matrix

中图分类号:

TP391

戴天辰1,顾正弘2. 基于传递距离的谱聚类算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2018.12.012.

DAI Tian-chen1, GU Zheng-hong2. Spectral Clustering Algorithm Based on Transitive Distance[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2018.12.012.

参考文献

［1］ NG A Y, JORDAN M I, WEISS Y. On spectral clustering: Analysis and an algorithm［C］// International Conference on Neural Information Processing Systems: Natural & Synthetic. 2001:849-856.
［2］ XIA T, CAO J, ZHANG Y D, et al. On defining affinity graph for spectral clustering through ranking on manifolds［J］. Neurocomputing, 2009,72(13-15):3203-3211.
［3］ ZELNIK-MANOR L, PERONA P. Self-tuning spectral clustering［C］// Advances in Neural Information Processing Systems. 2004:1601-1608.
［4］ FISCHER I, POLAND J. Amplifying the Block Matrix Structure for Spectral Clustering［R］. Technical Report No. IDDIA-03-05, Dalle Molle Institute for Artificial Intelligence, Switzerland, 2005.
［5］ KONG W, SUN C, ZHANG J, et al. Spectral clustering based on neighboring adaptive local scale［J］. Journal of Image & Graphics, 2012,17(4):523-529.
［6］ LIU X Y, LI J W, HONG Y U, et al. Adaptive spectral clustering based on shared nearest neighbors［J］. Journal of Chinese Computer Systems, 2011,32(9):1876-1880.
［7］张亚平,杨明. 一种基于密度敏感的自适应谱聚类算法［J］. 数学的实践与认识, 2013,43(20):150-156.
［8］ I〖DD（-*2〗·〖DD）〗NKAYA T. A parameter-free similarity graph for spectral clustering［J］. Expert Systems with Applications, 2015,42(24):9489-9498.
［9］王玲,薄列峰,焦李成. 密度敏感的谱聚类［J］. 电子学报, 2007,35(8):1577-1581.
［10］YU Z, XU C, MENG D, et al. Transitive distance clustering with K-Means duality［C］// 2014 IEEE Conference on Computer Vision and Pattern Recognition. 2014:987-994.
［11］DING C, HE X, XIONG H, et al. Transitive closure and metric inequality of weighted graphs: Detecting protein-interaction modules using cliques［J］. International Journal of Data Mining and Bioinformatics, 2006,1(2):162-177.
［12］FISCHER B, BUHMANN J M. Path-based clustering for grouping of smooth curves and texture segmentation［J］. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2003,25(4):513-518.
［13］FISCHER B, ROTH V, BUHMANN J M. Clustering with the conne ctivity kernel［J］. Nips, 2004.
［14］YEH C C, YANG M S. Evaluation measures for cluster ensembles based on a fuzzy generalized Rand index［J］. Applied Soft Computing, 2017,57:225-234.
［15］{UCI} Machine Learning Repository. 452 Data Sets［EB/OL］. Http: //archive.ics.uci.edu/m /datasets. Html, 2018-05-01.
［16］HAN J, KAMBER M. Data Mining Concept and Techniques［M］. Elsevier, 2001.
［17］DING C H Q, HE X, ZHA H, et al. A Min-max Cut algorithm for graph partitioning and data clustering［C］// Proceedings of 2001 IEEE International Conference on Data Mining. 2001:107-114.
［18］胡文博,黄蔚,胡国超. 基于OPTICS聚类和关联分析的轨迹伴随模式分析［J］. 计算机与现代化, 2017(12): 82-87.
［19］徐聪,黄文准,黄世奇. 基于自组织映射的遗传聚类算法［J］. 计算机与现代化, 2017(4): 38-43.

[1]	邹臣嵩1,刘松2. 基于谱聚类的全局中心快速更新聚类算法[J]. 计算机与现代化, 2018, 0(10): 6-.
[2]	印世乐，曾志勇. 一种改进的Nystrom谱聚类图像分割算法[J]. 计算机与现代化, 2014, 0(4): 20-23.
[3]	王森洪;戴青云;曹江中;朱婧. 基于均值的谱聚类特征向量选择算法[J]. 计算机与现代化, 2013, 1(5): 7-9.

基于传递距离的谱聚类算法

Spectral Clustering Algorithm Based on Transitive Distance

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价