Computer Science ›› 2018, Vol. 45 ›› Issue (6A): 202-205.

• Pattern Recognition & Image Processing • Previous Articles     Next Articles

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

ZHENG Shi-xiu1,2,PAN Zhen-kuan1,XU Zhi-lei1   

  1. College of Computer Science and Technology,Qingdao University,Qingdao,Shandong 266071,China1
    Business School,Qingdao University,Qingdao,Shandong 266071,China2
  • Online:2018-06-20 Published:2018-08-03

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

CLC Number: 

  • TP391
[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 27th 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.
[1] CHENG Zhang-tao, ZHONG Ting, ZHANG Sheng-ming, ZHOU Fan. Survey of Recommender Systems Based on Graph Learning [J]. Computer Science, 2022, 49(9): 1-13.
[2] ZHOU Fang-quan, CHENG Wei-qing. Sequence Recommendation Based on Global Enhanced Graph Neural Network [J]. Computer Science, 2022, 49(9): 55-63.
[3] SONG Jie, LIANG Mei-yu, XUE Zhe, DU Jun-ping, KOU Fei-fei. Scientific Paper Heterogeneous Graph Node Representation Learning Method Based onUnsupervised Clustering Level [J]. Computer Science, 2022, 49(9): 64-69.
[4] XU Yong-xin, ZHAO Jun-feng, WANG Ya-sha, XIE Bing, YANG Kai. Temporal Knowledge Graph Representation Learning [J]. Computer Science, 2022, 49(9): 162-171.
[5] RAO Zhi-shuang, JIA Zhen, ZHANG Fan, LI Tian-rui. Key-Value Relational Memory Networks for Question Answering over Knowledge Graph [J]. Computer Science, 2022, 49(9): 202-207.
[6] WU Zi-yi, LI Shao-mei, JIANG Meng-han, ZHANG Jian-peng. Ontology Alignment Method Based on Self-attention [J]. Computer Science, 2022, 49(9): 215-220.
[7] KONG Shi-ming, FENG Yong, ZHANG Jia-yun. Multi-level Inheritance Influence Calculation and Generalization Based on Knowledge Graph [J]. Computer Science, 2022, 49(9): 221-227.
[8] NING Han-yang, MA Miao, YANG Bo, LIU Shi-chang. Research Progress and Analysis on Intelligent Cryptology [J]. Computer Science, 2022, 49(9): 288-296.
[9] WANG Ming, PENG Jian, HUANG Fei-hu. Multi-time Scale Spatial-Temporal Graph Neural Network for Traffic Flow Prediction [J]. Computer Science, 2022, 49(8): 40-48.
[10] SHI Dian-xi, ZHAO Chen-ran, ZHANG Yao-wen, YANG Shao-wu, ZHANG Yong-jun. Adaptive Reward Method for End-to-End Cooperation Based on Multi-agent Reinforcement Learning [J]. Computer Science, 2022, 49(8): 247-256.
[11] LI Zong-min, ZHANG Yu-peng, LIU Yu-jie, LI Hua. Deformable Graph Convolutional Networks Based Point Cloud Representation Learning [J]. Computer Science, 2022, 49(8): 273-278.
[12] QIN Qi-qi, ZHANG Yue-qin, WANG Run-ze, ZHANG Ze-hua. Hierarchical Granulation Recommendation Method Based on Knowledge Graph [J]. Computer Science, 2022, 49(8): 64-69.
[13] CHENG Fu-hao, XU Tai-hua, CHEN Jian-jun, SONG Jing-jing, YANG Xi-bei. Strongly Connected Components Mining Algorithm Based on k-step Search of Vertex Granule and Rough Set Theory [J]. Computer Science, 2022, 49(8): 97-107.
[14] TAN Ying-ying, WANG Jun-li, ZHANG Chao-bo. Review of Text Classification Methods Based on Graph Convolutional Network [J]. Computer Science, 2022, 49(8): 205-216.
[15] YAN Jia-dan, JIA Cai-yan. Text Classification Method Based on Information Fusion of Dual-graph Neural Network [J]. Computer Science, 2022, 49(8): 230-236.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!