基于图的高维数据分类Ratio Cut模型及其快速算法

计算机科学 ›› 2018, Vol. 45 ›› Issue (6A): 202-205.

基于图的高维数据分类Ratio Cut模型及其快速算法

郑世秀^1,2,潘振宽¹,徐知磊¹

青岛大学计算机科学技术学院山东青岛266071¹
青岛大学商学院山东青岛266071²

出版日期:2018-06-20 发布日期:2018-08-03
作者简介:郑世秀(1972-),女,博士生,讲师,主要研究方向为数字图像处理、模式识别,E-mail:13697677910@163.com;潘振宽(1966-),男,博士,教授,主要研究方向为数字图像处理、机器学习;徐知磊(1992-),男,硕士生,主要研究方向为数字图像处理、模式识别。
基金资助:
国家自然科学基金(61170106)资助

Graph-based Ratio Cut Model for Classification of High-dimensional Data and Fast Algorithm

ZHENG Shi-xiu^1,2,PAN Zhen-kuan¹,XU Zhi-lei¹

College of Computer Science and Technology,Qingdao University,Qingdao,Shandong 266071,China¹
Business School,Qingdao University,Qingdao,Shandong 266071,China²

Online:2018-06-20 Published:2018-08-03

摘要/Abstract

摘要： 数据分类是数据挖掘研究的重要内容,随着数据量以及数据维度的增加,对大规模、高维数据的处理成为关键问题。为提高数据分类的准确率,受计算机视觉中图像分割算法的启发,针对经典的Ratio Cut分类模型提出一种基于非局部算子的实现算法。引进拉格朗日乘子,建立新的能量泛函,并采用交替优化的策略来求解该能量泛函。数值实验表明,算法的准确率及计算效率与传统分类方法相比都有较大提高。

关键词: Ratio Cut, 非局部方法, 数据分类, 图

Abstract: Data classification is an important part of data mining.With the increase of the amount of data and the dimension of data,the processing of large-scale and high-dimensional data becomes the key problem.In order to improve the accuracy of data classification,inspired by the image segmentation algorithm in computer vision,an algorithm based on nonlocal operator was proposed for the classic Ratio Cut classification model.A new energy functional is modeled by introducing Lagrange multipliers,and the energy functional is solved by the alternating optimization method.Numerical experiments show that the accuracy and computational efficiency of the proposed algorithm are greatly improved compared with the traditional classification method.

Key words: Data classification, Graph, Nonlocal means, Ratio Cut

中图分类号:

TP391

郑世秀,潘振宽,徐知磊. 基于图的高维数据分类Ratio Cut模型及其快速算法[J]. 计算机科学, 2018, 45(6A): 202-205. https://doi.org/

ZHENG Shi-xiu,PAN Zhen-kuan,XU Zhi-lei. Graph-based Ratio Cut Model for Classification of High-dimensional Data and Fast Algorithm[J]. Computer Science, 2018, 45(6A): 202-205. https://doi.org/

参考文献

[1]VON LUXBURG U.A tutorial on spectral clustering.Statistics and Computing,2007,17:395-416.
[2]RUDIN L I,OSHER S,FATEMI E.Nonlinear total variation based noise removal algorithms[J].Physica D:Nonlinear Phenomena,1992,60(1):259-268.
[3]GOLDSTEIN T,OSHER S.The Split Bregman Method for L1-Regularized Problems[J].Siam Journal on Imaging Sciences,2009,2(2):323-343.
[4]GILBOA G,OSHER S.Nonlocal Linear Image Regularization and Supervised Segmentation[J].Siam Journal on Multiscale Modeling & Simulation,2007,6(2):595-630.
[5]GILBOA G,OSHER S.Nonlocal Operators with Applications to Image Processing[J].Siam Journal on Multiscale Modeling & Simulation,2008,7(3):1005-1028.
[6]VESE L A,CHAN T F.A Multiphase Level Set Framework for Image Segmentation Using the Mumford and Shah Model[J].International Journal of Computer Vision,2002,50(3):271-293.
[7]CHAN T,VESE L.An Active Contour Model without Edges [M].Scale-Space Theories in Computer Vision.Springer Berlin Heidelberg,1999:141-151.
[8]潘振宽,李华,魏伟波,等.三维图像多相分割的变分水平集方法[J].计算机学报,2009,32(12):2464-2474.
[9]DUAN J,PAN Z,LIU W,et al.Color Texture Image Inpainting Using the Non Local CTV Model[J].Journal of Signal and Information Processing,2013,4:43-51.
[10]HAGEN L,KAHNG A.New spectral methods for ratio cut par- titioning and clustering[J].IEEE Trans.Comput.-Aided Des.,1992,11(9):1074-1085.
[11]SZLAM A,BRESSON X.Total Variation and Cheeger Cut[C]∥ Proceeding of the 27^th International Conference on Machine Learning.2010:1039-1046.
[12]SHI J,MALIK J.Normalized cuts and image segmentation[J].IEEE Trans.Pattern Anal.Mach.Intell.,2000,22(8):888-905.
[13]SZLAM A,BRESSON X.A total variation-based graph clustering algorithm for Cheeger ratio cuts[C]∥International Conference on Machine Learning.2010:1039-1046.
[14]BRESSON X,LAURENT T,UMINSKY D,et al.Convergence and energy landscape for Cheeger cut clustering[J].Advances in Neural Information Processing Systems,2012:25:1394-1402.
[15]BRESSON X,LAURENT T,UMINSKY D,et al.An adaptive total variation algorithm for computing the balanced cut of a graph[J].arXiv preprint arXiv:1302.2717,2013.
[16]BRESSON X,LAURENT T,UMINSKY D,et al.Multiclass total variation clustering[J].Advances in Neural Information Processing Systems,2013,26:1421-1429.
[17]BRESSON X,TAI X C,CHAN T F,et al.Multi-class transductive learning based on L1 relaxations of Cheeger cut and Mumford-Shah-Potts model[J].Journal of Mathematical Imaging and Vision,2014,49(1):191-201.
[18]Hu H,LAURENT T,PORTER M A,et al.A method based on total variation for network modularity optimization using the MBO scheme[J].SIAM Journal of Applied Mathematics,2013,73(6):2224-2246.

相关文章 15

[1]	饶志双, 贾真, 张凡, 李天瑞. 基于Key-Value关联记忆网络的知识图谱问答方法 Key-Value Relational Memory Networks for Question Answering over Knowledge Graph 计算机科学, 2022, 49(9): 202-207. https://doi.org/10.11896/jsjkx.220300277
[2]	吴子仪, 李邵梅, 姜梦函, 张建朋. 基于自注意力模型的本体对齐方法 Ontology Alignment Method Based on Self-attention 计算机科学, 2022, 49(9): 215-220. https://doi.org/10.11896/jsjkx.210700190
[3]	孔世明, 冯永, 张嘉云. 融合知识图谱的多层次传承影响力计算与泛化研究 Multi-level Inheritance Influence Calculation and Generalization Based on Knowledge Graph 计算机科学, 2022, 49(9): 221-227. https://doi.org/10.11896/jsjkx.210700144
[4]	刘兴光, 周力, 刘琰, 张晓瀛, 谭翔, 魏急波. 基于边缘智能的频谱地图构建与分发方法 Construction and Distribution Method of REM Based on Edge Intelligence 计算机科学, 2022, 49(9): 236-241. https://doi.org/10.11896/jsjkx.220400148
[5]	郝洁, 平萍, 付德银, 赵红泽. 压缩差值后的双直方图平移可逆信息隐藏方法 Bi-histogram Shifting Reversible Data Hiding Method After Compressed Differences 计算机科学, 2022, 49(9): 340-346. https://doi.org/10.11896/jsjkx.220300238
[6]	程章桃, 钟婷, 张晟铭, 周帆. 基于图学习的推荐系统研究综述 Survey of Recommender Systems Based on Graph Learning 计算机科学, 2022, 49(9): 1-13. https://doi.org/10.11896/jsjkx.210900072
[7]	周芳泉, 成卫青. 基于全局增强图神经网络的序列推荐 Sequence Recommendation Based on Global Enhanced Graph Neural Network 计算机科学, 2022, 49(9): 55-63. https://doi.org/10.11896/jsjkx.210700085
[8]	宋杰, 梁美玉, 薛哲, 杜军平, 寇菲菲. 基于无监督集群级的科技论文异质图节点表示学习方法 Scientific Paper Heterogeneous Graph Node Representation Learning Method Based onUnsupervised Clustering Level 计算机科学, 2022, 49(9): 64-69. https://doi.org/10.11896/jsjkx.220500196
[9]	戴禹, 许林峰. 基于文本行匹配的跨图文本阅读方法 Cross-image Text Reading Method Based on Text Line Matching 计算机科学, 2022, 49(9): 139-145. https://doi.org/10.11896/jsjkx.220600032
[10]	徐涌鑫, 赵俊峰, 王亚沙, 谢冰, 杨恺. 时序知识图谱表示学习 Temporal Knowledge Graph Representation Learning 计算机科学, 2022, 49(9): 162-171. https://doi.org/10.11896/jsjkx.220500204
[11]	史殿习, 赵琛然, 张耀文, 杨绍武, 张拥军. 基于多智能体强化学习的端到端合作的自适应奖励方法 Adaptive Reward Method for End-to-End Cooperation Based on Multi-agent Reinforcement Learning 计算机科学, 2022, 49(8): 247-256. https://doi.org/10.11896/jsjkx.210700100
[12]	李宗民, 张玉鹏, 刘玉杰, 李华. 基于可变形图卷积的点云表征学习 Deformable Graph Convolutional Networks Based Point Cloud Representation Learning 计算机科学, 2022, 49(8): 273-278. https://doi.org/10.11896/jsjkx.210900023
[13]	周连兵, 周湘贞, 崔学荣. 基于双重二维混沌映射的压缩图像加密方案 Compressed Image Encryption Scheme Based on Dual Two Dimensional Chaotic Map 计算机科学, 2022, 49(8): 344-349. https://doi.org/10.11896/jsjkx.210700235
[14]	秦琪琦, 张月琴, 王润泽, 张泽华. 基于知识图谱的层次粒化推荐方法 Hierarchical Granulation Recommendation Method Based on Knowledge Graph 计算机科学, 2022, 49(8): 64-69. https://doi.org/10.11896/jsjkx.210600111
[15]	程富豪, 徐泰华, 陈建军, 宋晶晶, 杨习贝. 基于顶点粒k步搜索和粗糙集的强连通分量挖掘算法 Strongly Connected Components Mining Algorithm Based on k-step Search of Vertex Granule and Rough Set Theory 计算机科学, 2022, 49(8): 97-107. https://doi.org/10.11896/jsjkx.210700202

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed