Clustering based polyhedral conic functions algorithm in classification

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

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 and 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-293. 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-028.
[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-296. doi: 10.1080/10556780512331318263.
[5]	A. M. Bagirov and J. Ugon, Supervised data classification via max-min separability, Applied Optimization, 99 (2005), 175-207. 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-338.
[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-24. ISSN 1134-5764. 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-167.
[9]	R. N. Gasimov and G. Ozturk, Separation via polihedral conic functions, Optimization Methods and Software, 21 (2006), 527-540. 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-18. ISSN 1931-0145. doi: 10.1145/1656274.1656278.
[11]	R. Kasimbeyli, Radial epiderivatives and set-valued optimization, Optimization, 58 (2009), 521-534. 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-1619. ISSN 1052-6234. 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-855. doi: 10.1137/080738106.
[14]	G. Ozturk, A New Mathematical Programming Approach to Solve Classification Problems, PhD thesis, Eskisehir Osmangazi University, Institute of Scince, 6 2007. (in Turkish).
[15]	R. Rosenthal, GAMS: A User's Guide, GAMS Development Corporation, Washington, DC, 2013. URL http://www.gams.com/dd/docs/bigdocs/GAMSUsersGuide.pdf.
[16]	K. Schittkowski, Optimal parameter selection in support vector machines, Journal of Industrial and Management Optimization, 1 (2005), 465-476. 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-293. 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-028.
[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-296. doi: 10.1080/10556780512331318263.
[5]	A. M. Bagirov and J. Ugon, Supervised data classification via max-min separability, Applied Optimization, 99 (2005), 175-207. 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-338.
[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-24. ISSN 1134-5764. 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-167.
[9]	R. N. Gasimov and G. Ozturk, Separation via polihedral conic functions, Optimization Methods and Software, 21 (2006), 527-540. 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-18. ISSN 1931-0145. doi: 10.1145/1656274.1656278.
[11]	R. Kasimbeyli, Radial epiderivatives and set-valued optimization, Optimization, 58 (2009), 521-534. 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-1619. ISSN 1052-6234. 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-855. doi: 10.1137/080738106.
[14]	G. Ozturk, A New Mathematical Programming Approach to Solve Classification Problems, PhD thesis, Eskisehir Osmangazi University, Institute of Scince, 6 2007. (in Turkish).
[15]	R. Rosenthal, GAMS: A User's Guide, GAMS Development Corporation, Washington, DC, 2013. URL http://www.gams.com/dd/docs/bigdocs/GAMSUsersGuide.pdf.
[16]	K. Schittkowski, Optimal parameter selection in support vector machines, Journal of Industrial and Management Optimization, 1 (2005), 465-476. 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 and Imaging, 2011, 5 (2) : 407-429. doi: 10.3934/ipi.2011.5.407
[2]	Müge Acar, Refail Kasimbeyli. A polyhedral conic functions based classification method for noisy data. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3493-3508. doi: 10.3934/jimo.2020129
[3]	Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems and Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022
[4]	Qingsong Duan, Mengwei Xu, Liwei Zhang, Sainan Zhang. Hadamard directional differentiability of the optimal value of a linear second-order conic programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3085-3098. doi: 10.3934/jimo.2020108
[5]	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
[6]	Ziran Yin, Liwei Zhang. Perturbation analysis of a class of conic programming problems under Jacobian uniqueness conditions. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1387-1397. doi: 10.3934/jimo.2018100
[7]	Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial and Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565
[8]	Vladislav Kruglov, Dmitry Malyshev, Olga Pochinka. Topological classification of $Ω$-stable flows on surfaces by means of effectively distinguishable multigraphs. Discrete and Continuous Dynamical Systems, 2018, 38 (9) : 4305-4327. doi: 10.3934/dcds.2018188
[9]	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 and Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779
[10]	Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $ k $-error linear complexity for $ p^n $-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018
[11]	Charles Fefferman. Interpolation by linear programming I. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[12]	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 and Continuous Dynamical Systems, 2015, 35 (5) : 1767-1800. doi: 10.3934/dcds.2015.35.1767
[13]	Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial and Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259
[14]	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
[15]	James Anderson, Antonis Papachristodoulou. Advances in computational Lyapunov analysis using sum-of-squares programming. Discrete and Continuous Dynamical Systems - B, 2015, 20 (8) : 2361-2381. doi: 10.3934/dcdsb.2015.20.2361
[16]	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
[17]	Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $ k $-means problem with penalty. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021067
[18]	Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $ k $-means problem^†. Journal of Industrial and Management Optimization, 2022, 18 (1) : 411-426. doi: 10.3934/jimo.2020160
[19]	Miria Feng, Wenying Feng. Evaluation of parallel and sequential deep learning models for music subgenre classification. Mathematical Foundations of Computing, 2021, 4 (2) : 131-143. doi: 10.3934/mfc.2021008
[20]	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

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Gurkan Ozturk Mehmet Tahir Ciftci
on Google Scholar
Gurkan Ozturk Mehmet Tahir Ciftci

[Back to Top]