导航菜单

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

PDF (PC)

74

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: Graph, Nonlocal means, Ratio Cut, Data classification

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] CHEN Xiao-jun, XIANG Yang. STransH:A Revised Translation-based Model for Knowledge Representation [J]. Computer Science, 2019, 46(9): 184-189.
[2] CHEN Jin-yin, HUANG Guo-han, WU Yang-yang, JIA Cheng-yu. Double Cycle Graph Based Fraud Review Detection Algorithm [J]. Computer Science, 2019, 46(9): 229-236.
[3] ZHAN Yue, FANG Xian-wen, WANG Li-li. Analysis of Interactive Process Change Propagation Based on Configuration [J]. Computer Science, 2019, 46(9): 303-309.
[4] ZHU De-li, YANG De-gang, HU Rong, WAN Hui. Adaptive Multi-level Threshold Binaryzation Method for Optical Character Recognition in Mobile Environment [J]. Computer Science, 2019, 46(8): 315-320.
[5] SU Qing,LIN Hao,HUANG Jian-feng,HE Fan,LIN Zhi-yi. Study on Dynamic-graph Watermarking Based on Petri Net Coding [J]. Computer Science, 2019, 46(7): 120-125.
[6] LI Xiao-guang, SHAO Chao. Density Peak Clustering Algorithm Based on Grid Data Center [J]. Computer Science, 2019, 46(6A): 457-460.
[7] ZHANG Xin, HU Xiao-dong, WEI Jia-wei. Cloud Computing Based Geographical Information Service Technologies [J]. Computer Science, 2019, 46(6A): 532-536.
[8] XIANG Ying-zhuo, WEI Qiang, YOU Ling, SHI Hao. Improved Genetic Algorithm for Subgraph Isomorphism Problem [J]. Computer Science, 2019, 46(6A): 98-101.
[9] WANG Chen-yang, LIN Hui. Three-dimensional Geographic Opportunistic Routing Based on Energy Harvesting Wireless Sensor Networks [J]. Computer Science, 2019, 46(6A): 305-308.
[10] GUO Peng, LI Ren-fa, HU Hui. Clustering Method Based on Hypergraph Morkov Relaxation [J]. Computer Science, 2019, 46(6A): 452-456.
[11] YANG Xue-fei, ZHENG Dong, REN Fang. Digital Signature Algorithm Based on QC-LDPC Code [J]. Computer Science, 2019, 46(6): 162-167.
[12] QIU Ya-qiong, HU Yong-hua, LI Yang, TANG Zhen, SHI Lin. Optimization Algorithm of Complementary Register Usage Between Two Register Classesin Register Spilling for DSP Register Allocation [J]. Computer Science, 2019, 46(6): 196-200.
[13] ZHOU Wei-xing, SHI Hai-he. Survey on Sequence Assembly Algorithms in High-throughput Sequencing [J]. Computer Science, 2019, 46(5): 36-43.
[14] CAO Ya-xi, HUANG Hai-yan. Imbalanced Data Classification Algorithm Based on Probability Sampling and Ensemble Learning [J]. Computer Science, 2019, 46(5): 203-208.
[15] XU Wen, SONG Wen-ai, FU Li-zhen, LV Wei. Distributed Subgraph Matching Algorithm for Large Scale Graph Data [J]. Computer Science, 2019, 46(4): 28-35.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[3] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[4] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[5] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[6] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[7] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[8] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[9] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[10] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
渝ICP备16013121号-4
Copyright © 2019 Editorial Office of Computer Science
Add:18# Honghu West Rd., Yubei District,Chongqing,China    Zip Code: 401121
Editorial Office: 023-63500828    E-mail: jsjkx12@163.com    jsjkx_bianwu@163.com(Finance)