×

A mixed-integer programming approach to multi-class data classification problem. (English) Zbl 1131.90435

Summary: A new data classification method based on mixed-integer programming. Traditional approaches that are based on partitioning the data sets into two groups perform poorly for multi-class data classification problems. The proposed approach is based on the use of hyper-boxes for defining boundaries of the classes that include all or some of the points in that set. A mixed-integer programming model is developed for representing existence of hyper-boxes and their boundaries. In addition, the relationships among the discrete decisions in the model are represented using propositional logic and then converted to their equivalent integer constraints using Boolean algebra. The proposed approach for multi-class data classification is illustrated on an example problem. The efficiency of the proposed method is tested on the well-known IRIS data set. The computational results on the illustrative example and the IRIS data set show that the proposed method is accurate and efficient on multi-class data classification problems.

MSC:

90C11 Mixed integer programming
62H30 Classification and discrimination; cluster analysis (statistical aspects)
68T05 Learning and adaptive systems in artificial intelligence

Software:

GAMS; CPLEX
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Adem, J.; Gochet, W., Mathematical programming based heuristics for improving LP-generated classifiers for the multi-class supervised classification problem, European journal of operational research, 168, 1, 181-199, (2006) · Zbl 1078.90067
[2] Anthony, M., On data classification by iterative linear partitioning, Discrete applied mathematics, 144, 2-16, (2004) · Zbl 1099.68083
[3] Bajgier, S.M.; Hill, A.V., An experimental comparison of statistical and linear programming approaches to the discriminant problem, Decision sciences, 13, 604-618, (1982)
[4] B. Bay, The UCI KDD Archive, Department of Information and Computer Science, University of California, Irvine, CA, 1999. Available from: <http://kdd.ics.uci.edu>.
[5] J. Banzan, H. Nguyen, A. Skowron, J. Stepaniuk, Some logic and rough set applications for classifying objects, ICS Research Report No. 34, Warsaw University of Technology, 1994.
[6] Boros, E.; Hammer, P.L.; Ibaraki, T.; Kogan, A., Logical analysis of numerical data, Mathematical programming, 79, 163-190, (1997) · Zbl 0887.90179
[7] A. Brooke, D. Kendrick, A. Meeraus, R. Raman, GAMS: A User’s Guide, GAMS Development Co., Washington, DC, 1998.
[8] Carpenter, G.; Grossberg, S., A massively parallel architecture for a self-organizing neural pattern recognition machine, Computer vision and graphics image understanding, 37, 2, 54-115, (1987) · Zbl 0634.68089
[9] Cavalier, T.M.; Pardalos, P.M.; Soyster, A.L., Modeling and integer programming techniques applied to propositional calculus, Computers and operational research, 17, 6, 561-570, (1990) · Zbl 0707.03009
[10] Chang, Y.; Han, C.; Jou, F.; Fan, K.; Chen, K.S.; Chang, J., A modular eigen subspace scheme for high-dimensional data classification, Future generation computer systems, 20, 1131-1143, (2004)
[11] Cortes, C.; Vapnik, V., Support vector network, Machine learning, 20, 273-297, (1995) · Zbl 0831.68098
[12] Erenguc, S.S.; Koehler, G.J., Survey of mathematical programming models and experimental results for linear discriminant analysis, Managerial and decision economics, 11, 215-225, (1990)
[13] Fisher, R., The use of multiple measurements in taxonomic problems, Annals of eugenics, 7, 2, 179-188, (1936)
[14] Gehrlein, W.V., General mathematical programming formulations for the statistical classification problem, Operations research letters, 5, 6, 299-304, (1986)
[15] Ilog, 2003. ILOG CPLEX 9.0 User’s Manual.
[16] Kim, D., Data classification based on tolerant rough set, Pattern recognition, 34, 1613-1624, (2001) · Zbl 0984.68520
[17] Kim, H.; Pang, S.; Je, H.; Kim, D.; Bang, S.Y., Constructing support vector machine ensemble, Pattern recognition, 36, 2757-2767, (2003) · Zbl 1059.68091
[18] Littschwager, J.M.; Wang, C., Integer programming solution of a classification problem, Management science, 24, 14, 1515-1525, (1978) · Zbl 0491.90056
[19] Lin, C.T.; Lee, C.S.G., Neural-network-based fuzzy logic control and decision system, IEEE transactions on computers, 40, 12, 1320-1336, (1991) · Zbl 1395.93324
[20] Nguyen, H.; Skowron, A.; Synak, P., Discovery of data patterns with applications to decomposition and classification problems, rough sets in knowledge discovery, (1998), Physica-Verlag Wurzburg
[21] Pawlak, Z., Rough set, International journal foundations of computer science, 11, 341-356, (1982) · Zbl 0501.68053
[22] Raman, R.; Grossmann, I.E., Relation between MILP modeling and logical inference for chemical process synthesis, Computers and chemical engineering, 15, 2, 73-84, (1991)
[23] B. Schölkopf, C. Burges, V. Vapnik, Extracting support data for a given task, in: Proceedings of the First International Conference on Knowledge Discovery and Data Mining, Montreal, Canada, 1995.
[24] Simpson, P., Fuzzy min – max neural networks—part 1: classification, IEEE transactions neural networks, 3, 5, 776-786, (1992)
[25] Stam, A.; Joachimsthaler, E.A., A comparison of a robust mixed-integer approach to existing methods for establishing classification rules for the discriminant problem, European journal of operations research, 46, 1, 113-122, (1990) · Zbl 0702.90062
[26] Turkay, M.; Grossman, I.E., Disjunctive programming techniques for the optimization of process systems with discontinuous investment costs-multiple size regions, Industrial and engineering chemistry research, 35, 2611-2623, (1996)
[27] Yajima, Y., Linear programming approaches for multi category support vector machines, European journal of operational research, 162, 2, 514-531, (2005) · Zbl 1176.90406
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.