# American Institute of Mathematical Sciences

February  2019, 2(1): 11-28. doi: 10.3934/mfc.2019002

## Comparisons of different methods for balanced data classification under the discrete non-local total variational framework

 1 College of Computer Science and Technology, Qingdao University, Qingdao 266071, China 2 College of Business, Qingdao University, Qingdao 266071, China

* Corresponding author: Zhenkuan Pan

Published  March 2019

Because balanced constraints can overcome the problems of trivial solutions of data classification via minimum cut method, many techniques with different balanced strategies have been proposed to improve data classification accuracy. However, their performances have not been compared comprehensively so far. In this paper, we investigate seven balanced classification methods under the discrete non-local total variational framework and compare their accuracy performances on graph. The two-class classification problem with equality constraints, inequality constraints and Ratio Cut, Normalized Cut, Cheeger Cut models are investigated. For cases of equality constraint, we firstly compare the Penalty Function Method (PFM) and the Augmented Lagrangian Method (ALM), which can transform the constrained problems into unconstrained ones, to show the advantages of ALM. The other cases are all solved using the ALM also. In order to make the comparison fairly, we solve all models using ALM method and using the same proportion of fidelity points and the same neighborhood size on graph. Experimental results demonstrate ALM with the equality balanced constraint has the best classification accuracy compared with other six constraints. 200 words.

Citation: Shixiu Zheng, Zhilei Xu, Huan Yang, Jintao Song, Zhenkuan Pan. Comparisons of different methods for balanced data classification under the discrete non-local total variational framework. Mathematical Foundations of Computing, 2019, 2 (1) : 11-28. doi: 10.3934/mfc.2019002
##### References:

show all references

##### References:
Reference basis of three data sets
Reference basis of three data sets
Different results for two-moon dataset classification
Different results for handwritten digits classification of 3 & 8 dataset
Different results for handwritten digit classification of 4 & 9 dataset
Different algorithm's parameters
 EC-PFM EC-ALM SDIC DDIC RC CC NC $\mu_0$ 0.01 0.005 $\frac{3k}{n}$ $\frac{3k}{n}\cdot n$ 0.01 $\mu_1$ 15 25 20 15 15 12 15
 EC-PFM EC-ALM SDIC DDIC RC CC NC $\mu_0$ 0.01 0.005 $\frac{3k}{n}$ $\frac{3k}{n}\cdot n$ 0.01 $\mu_1$ 15 25 20 15 15 12 15
Accuracy comparisons ofdifferent algorithms for two-moon dataset classification
 Method $V_1$.class $V_2$.class Error Ranking Solution 1000 1000 EC-PFM 1014 986 1.7$\%$ 5 EC-ALM 1005 995 1.25$\%$ 1 SDIC 1016 984 1.50$\%$ 2 DDIC 1015 985 1.55$\%$ 3 RC 1030 970 1.70$\%$ 5 CC 1021 979 1.65$\%$ 4 NC 986 1014 1.90$\%$ 7
 Method $V_1$.class $V_2$.class Error Ranking Solution 1000 1000 EC-PFM 1014 986 1.7$\%$ 5 EC-ALM 1005 995 1.25$\%$ 1 SDIC 1016 984 1.50$\%$ 2 DDIC 1015 985 1.55$\%$ 3 RC 1030 970 1.70$\%$ 5 CC 1021 979 1.65$\%$ 4 NC 986 1014 1.90$\%$ 7
Accuracy comparisons of different algorithms for handwritten digit classification of 3 & 8 dataset
 Method $V_1$.class $V_2$.class Error Ranking Solution 7141 6825 EC-PFM 7165 6801 1.2745$\%$ 6 EC-ALM 7139 6827 1.1385$\%$ 1 SDIC 7128 6838 1.1671$\%$ 3 DDIC 7161 6805 1.2244$\%$ 4 RC 7173 6793 1.2387$\%$ 5 CC 7134 6832 1.1600$\%$ 2 NC 7167 6799 1.5538$\%$ 7
 Method $V_1$.class $V_2$.class Error Ranking Solution 7141 6825 EC-PFM 7165 6801 1.2745$\%$ 6 EC-ALM 7139 6827 1.1385$\%$ 1 SDIC 7128 6838 1.1671$\%$ 3 DDIC 7161 6805 1.2244$\%$ 4 RC 7173 6793 1.2387$\%$ 5 CC 7134 6832 1.1600$\%$ 2 NC 7167 6799 1.5538$\%$ 7
Accuracy comparisons of different algorithms for handwritten digit classification of 4 & 9 dataset
 Method $V_1$.class $V_2$.class Error Ranking Solution 6824 6958 EC-PFM 6814 6968 1.2988$\%$ 4 EC-ALM 6818 6964 1.2335$\%$ 1 SDIC 6799 6983 1.3133$\%$ 5 DDIC 6811 6971 1.3206$\%$ 6 RC 6836 6946 1.2698$\%$ 3 CC 6787 6995 1.2407$\%$ 2 NC 6807 6975 1.4729$\%$ 7
 Method $V_1$.class $V_2$.class Error Ranking Solution 6824 6958 EC-PFM 6814 6968 1.2988$\%$ 4 EC-ALM 6818 6964 1.2335$\%$ 1 SDIC 6799 6983 1.3133$\%$ 5 DDIC 6811 6971 1.3206$\%$ 6 RC 6836 6946 1.2698$\%$ 3 CC 6787 6995 1.2407$\%$ 2 NC 6807 6975 1.4729$\%$ 7
The dependences of error rate on fidelity set size
 Two-moons 3&8 Fidelity set size(per class) Error rate Fidelity set size(per class) Error rate 100 1.20$\%$ 350 1.1287$\%$ 50 1.25$\%$ 300 1.1385 $\%$ 40 1.65$\%$ 250 1.2888$\%$ 30 1.80$\%$ 200 1.3604$\%$ 26 1.85$\%$ 150 1.6397$\%$ 20 2.45$\%$ 100 3.8665$\%$ 16 2.55$\%$ 90 4.1386$\%$ 10 3.25$\%$ 70 9.8597$\%$ 6 4.20$\%$ 50 11.2201$\%$
 Two-moons 3&8 Fidelity set size(per class) Error rate Fidelity set size(per class) Error rate 100 1.20$\%$ 350 1.1287$\%$ 50 1.25$\%$ 300 1.1385 $\%$ 40 1.65$\%$ 250 1.2888$\%$ 30 1.80$\%$ 200 1.3604$\%$ 26 1.85$\%$ 150 1.6397$\%$ 20 2.45$\%$ 100 3.8665$\%$ 16 2.55$\%$ 90 4.1386$\%$ 10 3.25$\%$ 70 9.8597$\%$ 6 4.20$\%$ 50 11.2201$\%$
Dependence of error rate on DDIC range parameter
 $\varepsilon$value $V_1$.class $V_2$.class Error rate 5 7153 6813 1.2316$\%$ 10 7160 6806 1.2387$\%$ 15 7121 6845 1.2459$\%$ 20 7159 6807 1.2602$\%$ 30 7160 6806 1.2576$\%$ 50 7161 6805 1.2724$\%$
 $\varepsilon$value $V_1$.class $V_2$.class Error rate 5 7153 6813 1.2316$\%$ 10 7160 6806 1.2387$\%$ 15 7121 6845 1.2459$\%$ 20 7159 6807 1.2602$\%$ 30 7160 6806 1.2576$\%$ 50 7161 6805 1.2724$\%$
 [1] G. A. Swarup. On the cut point conjecture. Electronic Research Announcements, 1996, 2: 98-100. [2] Robert M. Strain. Optimal time decay of the non cut-off Boltzmann equation in the whole space. Kinetic & Related Models, 2012, 5 (3) : 583-613. doi: 10.3934/krm.2012.5.583 [3] Blaine Keetch, Yves Van Gennip. A Max-Cut approximation using a graph based MBO scheme. Discrete & Continuous Dynamical Systems - B, 2019, 24 (11) : 6091-6139. doi: 10.3934/dcdsb.2019132 [4] Cédric Villani. Regularity of optimal transport and cut locus: From nonsmooth analysis to geometry to smooth analysis. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 559-571. doi: 10.3934/dcds.2011.30.559 [5] Takeshi Fukao. Variational inequality for the Stokes equations with constraint. Conference Publications, 2011, 2011 (Special) : 437-446. doi: 10.3934/proc.2011.2011.437 [6] Walter Allegretto, Yanping Lin, Shuqing Ma. On the box method for a non-local parabolic variational inequality. Discrete & Continuous Dynamical Systems - B, 2001, 1 (1) : 71-88. doi: 10.3934/dcdsb.2001.1.71 [7] Anouar Bahrouni. Trudinger-Moser type inequality and existence of solution for perturbed non-local elliptic operators with exponential nonlinearity. Communications on Pure & Applied Analysis, 2017, 16 (1) : 243-252. doi: 10.3934/cpaa.2017011 [8] Yunho Kim, Paul M. Thompson, Luminita A. Vese. HARDI data denoising using vectorial total variation and logarithmic barrier. Inverse Problems & Imaging, 2010, 4 (2) : 273-310. doi: 10.3934/ipi.2010.4.273 [9] Juan Carlos De los Reyes, Estefanía Loayza-Romero. Total generalized variation regularization in data assimilation for Burgers' equation. Inverse Problems & Imaging, 2019, 13 (4) : 755-786. doi: 10.3934/ipi.2019035 [10] Takeshi Fukao, Nobuyuki Kenmochi. Quasi-variational inequality approach to heat convection problems with temperature dependent velocity constraint. Discrete & Continuous Dynamical Systems - A, 2015, 35 (6) : 2523-2538. doi: 10.3934/dcds.2015.35.2523 [11] Liping Pang, Fanyun Meng, Jinhe Wang. Asymptotic convergence of stationary points of stochastic multiobjective programs with parametric variational inequality constraint via SAA approach. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1653-1675. doi: 10.3934/jimo.2018116 [12] Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237 [13] Qiyu Jin, Ion Grama, Quansheng Liu. Convergence theorems for the Non-Local Means filter. Inverse Problems & Imaging, 2018, 12 (4) : 853-881. doi: 10.3934/ipi.2018036 [14] Gabriel Peyré, Sébastien Bougleux, Laurent Cohen. Non-local regularization of inverse problems. Inverse Problems & Imaging, 2011, 5 (2) : 511-530. doi: 10.3934/ipi.2011.5.511 [15] Olivier Bonnefon, Jérôme Coville, Guillaume Legendre. Concentration phenomenon in some non-local equation. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 763-781. doi: 10.3934/dcdsb.2017037 [16] Henri Berestycki, Nancy Rodríguez. A non-local bistable reaction-diffusion equation with a gap. Discrete & Continuous Dynamical Systems - A, 2017, 37 (2) : 685-723. doi: 10.3934/dcds.2017029 [17] Chiu-Yen Kao, Yuan Lou, Wenxian Shen. Random dispersal vs. non-local dispersal. Discrete & Continuous Dynamical Systems - A, 2010, 26 (2) : 551-596. doi: 10.3934/dcds.2010.26.551 [18] Hongjie Dong, Doyoon Kim. Schauder estimates for a class of non-local elliptic equations. Discrete & Continuous Dynamical Systems - A, 2013, 33 (6) : 2319-2347. doi: 10.3934/dcds.2013.33.2319 [19] Matteo Focardi. Vector-valued obstacle problems for non-local energies. Discrete & Continuous Dynamical Systems - B, 2012, 17 (2) : 487-507. doi: 10.3934/dcdsb.2012.17.487 [20] Tao Wang. Global dynamics of a non-local delayed differential equation in the half plane. Communications on Pure & Applied Analysis, 2014, 13 (6) : 2475-2492. doi: 10.3934/cpaa.2014.13.2475

Impact Factor: