Clustering based polyhedral conic functions algorithm in classification

Previous Article
Modeling the signaling overhead in Host Identity Protocol-based secure mobile architectures
JIMO Home
This Issue
Next Article
Joint pricing and replenishment decisions for non-instantaneous deteriorating items with partial backlogging, inflation- and selling price-dependent demand and customer returns

July 2015, 11(3): 921-932. doi: 10.3934/jimo.2015.11.921

Clustering based polyhedral conic functions algorithm in classification

Gurkan Ozturk ^1, and Mehmet Tahir Ciftci ^2,

1.	Department of Industrial Engineering, Faculty of Engineering, Anadolu University, Eskisehir, 26555, Turkey
2.	Vitra, Eczacibasi Yapi Gerecleri, 11300 Bilecik, Turkey

Received October 2013 Revised June 2014 Published October 2014

Abstract
Related Papers

In this study, a new algorithm based on polyhedral conic functions (PCFs) is developed to solve multi-class supervised data classification problems. The $k$ PCFs are constructed for each class in order to separate it from the rest of the data set. The $k$-means algorithm is applied to find vertices of PCFs and then a linear programming model is solved to calculate the parameters of each PCF. The separating functions for each class are obtained as a pointwise minimum of the PCFs. A class label is assigned to the test point according to its minimum value over all separating functions. In order to demonstrate the performance of the proposed algorithm, it is applied to solve classification problems in publicly available data sets. The comparative results with some mainstream classifiers are presented.

Keywords: computational learning theory., polyhedral conic cunctions, Classification, linear programming, K-means.

Mathematics Subject Classification: Primary: 68Q32, 46N10; Secondary: 97R5.

Citation: Gurkan Ozturk, Mehmet Tahir Ciftci. Clustering based polyhedral conic functions algorithm in classification. Journal of Industrial & Management Optimization, 2015, 11 (3) : 921-932. doi: 10.3934/jimo.2015.11.921

References:

[1]	A. Astorino and M. Gaudioso, Polyhedral separability through successive LP,, Journal of Optimization Theory and Applications, 112 (2002), 265. doi: 10.1023/A:1013649822153.
[2]	A. Astorino, M. Gaudioso and A. Seeger, Conic separation of finite sets. i: The homogeneous case,, Journal of Convex Analysis, 21 (2014), 001.
[3]	K. Bache and M. Lichman, UCI machine learning repository, 2013., URL , ().
[4]	A. M. Bagirov, Max-min separability,, Optimization Methods and Software, 20 (2005), 277. doi: 10.1080/10556780512331318263.
[5]	A. M. Bagirov and J. Ugon, Supervised data classification via max-min separability,, Applied Optimization, 99 (2005), 175. doi: 10.1007/0-387-26771-9_6.
[6]	A. M. Bagirov, M. Ghosh and D. Webb, A derivative-free method for linearly constrained nonsmooth optimization,, Journal of Industrial and Management Optimization, 2 (2006), 319.
[7]	A. M. Bagirov, J. Ugon, D. Webb, G. Ozturk and R. Kasimbeyli, A novel piecewise linear classifier based on polyhedral conic and max-min separabilities,, TOP, 21 (2013), 3. doi: 10.1007/s11750-011-0241-5.
[8]	C. J. C. Burges, A tutorial on support vector machines for pattern recognition,, Data Mining and Knowledge Discovery, 2 (1998), 121.
[9]	R. N. Gasimov and G. Ozturk, Separation via polihedral conic functions,, Optimization Methods and Software, 21 (2006), 527. doi: 10.1080/10556780600723252.
[10]	M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann and I. H. Witten, The weka data mining software: An update,, SIGKDD Explorations, 11 (2009), 10. doi: 10.1145/1656274.1656278.
[11]	R. Kasimbeyli, Radial epiderivatives and set-valued optimization,, Optimization, 58 (2009), 521. doi: 10.1080/02331930902928310.
[12]	R. Kasimbeyli, A nonlinear cone separation theorem and scalarization in nonconvex vector optimization,, SIAM J. on Optimization, 20 (2009), 1591. doi: 10.1137/070694089.
[13]	R. Kasimbeyli and M. Mammadov, On weak subdifferentials, directional derivatives, and radial epiderivatives for nonconvex functions,, SIAM Journal on Optimization, 20 (2009), 841. doi: 10.1137/080738106.
[14]	G. Ozturk, A New Mathematical Programming Approach to Solve Classification Problems,, PhD thesis, 6 (2007).
[15]	R. Rosenthal, GAMS: A User's Guide,, GAMS Development Corporation, (2013).
[16]	K. Schittkowski, Optimal parameter selection in support vector machines,, Journal of Industrial and Management Optimization, 1 (2005), 465. doi: 10.3934/jimo.2005.1.465.

show all references

References:

[1]	A. Astorino and M. Gaudioso, Polyhedral separability through successive LP,, Journal of Optimization Theory and Applications, 112 (2002), 265. doi: 10.1023/A:1013649822153.
[2]	A. Astorino, M. Gaudioso and A. Seeger, Conic separation of finite sets. i: The homogeneous case,, Journal of Convex Analysis, 21 (2014), 001.
[3]	K. Bache and M. Lichman, UCI machine learning repository, 2013., URL , ().
[4]	A. M. Bagirov, Max-min separability,, Optimization Methods and Software, 20 (2005), 277. doi: 10.1080/10556780512331318263.
[5]	A. M. Bagirov and J. Ugon, Supervised data classification via max-min separability,, Applied Optimization, 99 (2005), 175. doi: 10.1007/0-387-26771-9_6.
[6]	A. M. Bagirov, M. Ghosh and D. Webb, A derivative-free method for linearly constrained nonsmooth optimization,, Journal of Industrial and Management Optimization, 2 (2006), 319.
[7]	A. M. Bagirov, J. Ugon, D. Webb, G. Ozturk and R. Kasimbeyli, A novel piecewise linear classifier based on polyhedral conic and max-min separabilities,, TOP, 21 (2013), 3. doi: 10.1007/s11750-011-0241-5.
[8]	C. J. C. Burges, A tutorial on support vector machines for pattern recognition,, Data Mining and Knowledge Discovery, 2 (1998), 121.
[9]	R. N. Gasimov and G. Ozturk, Separation via polihedral conic functions,, Optimization Methods and Software, 21 (2006), 527. doi: 10.1080/10556780600723252.
[10]	M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann and I. H. Witten, The weka data mining software: An update,, SIGKDD Explorations, 11 (2009), 10. doi: 10.1145/1656274.1656278.
[11]	R. Kasimbeyli, Radial epiderivatives and set-valued optimization,, Optimization, 58 (2009), 521. doi: 10.1080/02331930902928310.
[12]	R. Kasimbeyli, A nonlinear cone separation theorem and scalarization in nonconvex vector optimization,, SIAM J. on Optimization, 20 (2009), 1591. doi: 10.1137/070694089.
[13]	R. Kasimbeyli and M. Mammadov, On weak subdifferentials, directional derivatives, and radial epiderivatives for nonconvex functions,, SIAM Journal on Optimization, 20 (2009), 841. doi: 10.1137/080738106.
[14]	G. Ozturk, A New Mathematical Programming Approach to Solve Classification Problems,, PhD thesis, 6 (2007).
[15]	R. Rosenthal, GAMS: A User's Guide,, GAMS Development Corporation, (2013).
[16]	K. Schittkowski, Optimal parameter selection in support vector machines,, Journal of Industrial and Management Optimization, 1 (2005), 465. doi: 10.3934/jimo.2005.1.465.

[1]	Sung Ha Kang, Berta Sandberg, Andy M. Yip. A regularized k-means and multiphase scale segmentation. Inverse Problems & Imaging, 2011, 5 (2) : 407-429. doi: 10.3934/ipi.2011.5.407
[2]	Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems & Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022
[3]	D. Warren, K Najarian. Learning theory applied to Sigmoid network classification of protein biological function using primary protein structure. Conference Publications, 2003, 2003 (Special) : 898-904. doi: 10.3934/proc.2003.2003.898
[4]	Ziran Yin, Liwei Zhang. Perturbation analysis of a class of conic programming problems under Jacobian uniqueness conditions. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1387-1397. doi: 10.3934/jimo.2018100
[5]	Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial & Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565
[6]	Vladislav Kruglov, Dmitry Malyshev, Olga Pochinka. Topological classification of $Ω$-stable flows on surfaces by means of effectively distinguishable multigraphs. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4305-4327. doi: 10.3934/dcds.2018188
[7]	Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779
[8]	G. Calafiore, M.C. Campi. A learning theory approach to the construction of predictor models. Conference Publications, 2003, 2003 (Special) : 156-166. doi: 10.3934/proc.2003.2003.156
[9]	Primitivo B. Acosta-Humánez, J. Tomás Lázaro, Juan J. Morales-Ruiz, Chara Pantazi. On the integrability of polynomial vector fields in the plane by means of Picard-Vessiot theory. Discrete & Continuous Dynamical Systems - A, 2015, 35 (5) : 1767-1800. doi: 10.3934/dcds.2015.35.1767
[10]	Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[11]	James Anderson, Antonis Papachristodoulou. Advances in computational Lyapunov analysis using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2361-2381. doi: 10.3934/dcdsb.2015.20.2361
[12]	Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259
[13]	Elena K. Kostousova. State estimation for linear impulsive differential systems through polyhedral techniques. Conference Publications, 2009, 2009 (Special) : 466-475. doi: 10.3934/proc.2009.2009.466
[14]	Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323
[15]	Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics & Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013
[16]	Navin Keswani. Homotopy invariance of relative eta-invariants and $C^$-algebra $K$-theory. Electronic Research Announcements*, 1998, 4: 18-26.
[17]	L. Búa, T. Mestdag, M. Salgado. Symmetry reduction, integrability and reconstruction in $k$-symplectic field theory. Journal of Geometric Mechanics, 2015, 7 (4) : 395-429. doi: 10.3934/jgm.2015.7.395
[18]	Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[19]	Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397
[20]	Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences