American Institute of Mathematical Sciences

Advanced
  • 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

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.  Google Scholar

[2]

A. Astorino, M. Gaudioso and A. Seeger, Conic separation of finite sets. i: The homogeneous case,, Journal of Convex Analysis, 21 (2014), 001.   Google Scholar

[3]

K. Bache and M. Lichman, UCI machine learning repository, 2013., URL , ().   Google Scholar

[4]

A. M. Bagirov, Max-min separability,, Optimization Methods and Software, 20 (2005), 277.  doi: 10.1080/10556780512331318263.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[8]

C. J. C. Burges, A tutorial on support vector machines for pattern recognition,, Data Mining and Knowledge Discovery, 2 (1998), 121.   Google Scholar

[9]

R. N. Gasimov and G. Ozturk, Separation via polihedral conic functions,, Optimization Methods and Software, 21 (2006), 527.  doi: 10.1080/10556780600723252.  Google Scholar

[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.  Google Scholar

[11]

R. Kasimbeyli, Radial epiderivatives and set-valued optimization,, Optimization, 58 (2009), 521.  doi: 10.1080/02331930902928310.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

G. Ozturk, A New Mathematical Programming Approach to Solve Classification Problems,, PhD thesis, 6 (2007).   Google Scholar

[15]

R. Rosenthal, GAMS: A User's Guide,, GAMS Development Corporation, (2013).   Google Scholar

[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.  Google Scholar

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.  Google Scholar

[2]

A. Astorino, M. Gaudioso and A. Seeger, Conic separation of finite sets. i: The homogeneous case,, Journal of Convex Analysis, 21 (2014), 001.   Google Scholar

[3]

K. Bache and M. Lichman, UCI machine learning repository, 2013., URL , ().   Google Scholar

[4]

A. M. Bagirov, Max-min separability,, Optimization Methods and Software, 20 (2005), 277.  doi: 10.1080/10556780512331318263.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[8]

C. J. C. Burges, A tutorial on support vector machines for pattern recognition,, Data Mining and Knowledge Discovery, 2 (1998), 121.   Google Scholar

[9]

R. N. Gasimov and G. Ozturk, Separation via polihedral conic functions,, Optimization Methods and Software, 21 (2006), 527.  doi: 10.1080/10556780600723252.  Google Scholar

[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.  Google Scholar

[11]

R. Kasimbeyli, Radial epiderivatives and set-valued optimization,, Optimization, 58 (2009), 521.  doi: 10.1080/02331930902928310.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

G. Ozturk, A New Mathematical Programming Approach to Solve Classification Problems,, PhD thesis, 6 (2007).   Google Scholar

[15]

R. Rosenthal, GAMS: A User's Guide,, GAMS Development Corporation, (2013).   Google Scholar

[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.  Google Scholar

[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]

Müge Acar, Refail Kasimbeyli. A polyhedral conic functions based classification method for noisy data. Journal of Industrial & Management Optimization, 2020  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 & 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 & Management Optimization, 2020  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 & 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 & 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 & Continuous Dynamical Systems - A, 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 & 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 & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - A, 2015, 35 (5) : 1767-1800. doi: 10.3934/dcds.2015.35.1767
[13]

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
[14]

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
[15]

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
[16]

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
[17]

Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $ k $-means problem†. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020160
[18]

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
[19]

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
[20]

Navin Keswani. Homotopy invariance of relative eta-invariants and $C^*$-algebra $K$-theory. Electronic Research Announcements, 1998, 4: 18-26.

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (112)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences