Improvement of CPU time of Linear Discriminant Function based on MNM criterion by IP
Abstract
Revised IP-OLDF (optimal linear discriminant function by integer programming) is a linear discriminant function to minimize the number of misclassifications (NM) of training samples by integer programming (IP). However, IP requires large computation (CPU) time. In this paper, it is proposed how to reduce CPU time by using linear programming (LP). In the first phase, Revised LP-OLDF is applied to all cases, and all cases are categorized into two groups: those that are classified correctly or those that are not classified by support vectors (SVs). In the second phase, Revised IP-OLDF is applied to the misclassified cases by SVs. This method is called Revised IPLP-OLDF.In this research, it is evaluated whether NM of Revised IPLP-OLDF is good estimate of the minimum number of misclassifications (MNM) by Revised IP-OLDF. Four kinds of the real data—Iris data, Swiss bank note data, student data, and CPD data—are used as training samples. Four kinds of 20,000 re-sampling cases generated from these data are used as the evaluation samples. There are a total of 149 models of all combinations of independent variables by these data. NMs and CPU times of the 149 models are compared with Revised IPLP-OLDF and Revised IP-OLDF. The following results are obtained: 1) Revised IPLP-OLDF significantly improves CPU time. 2) In the case of training samples, all 149 NMs of Revised IPLP-OLDF are equal to the MNM of Revised IP-OLDF. 3) In the case of evaluation samples, most NMs of Revised IPLP-OLDF are equal to NM of Revised IP-OLDF. 4) Generalization abilities of both discriminant functions are concluded to be high, because the difference between the error rates of training and evaluation samples are almost within 2%. Therefore, Revised IPLP-OLDF is recommended for the analysis of big data instead of Revised IP-OLDF. Next, Revised IPLP-OLDF is compared with LDF and logistic regression by 100-fold cross validation using 100 re-sampling samples. Means of error rates of Revised IPLP-OLDF are remarkable fewer than those of LDF and logistic regression.References
Edgar, A. (1935). The irises of the Gaspé Peninsula. Bulletin of the American Iris Society, 59, 2–5.
Fisher, R.A. (1936). The Use of Multiple Measurements in Taxonomic Problems. Annals of Eugenics, 7, 179–188.
Flury, B. & Rieduyl, H. (1988). Multivariate Statistics: A Practical Approach. Cambridge University Press.
Goodnight, J.H. (1978). SAS Technical Report – The Sweep Operator: Its Importance in Statistical Computing – (R-100). SAS Institute Inc.
Liitschwager, J. M. & Wang, C. (1978). Integer programming solution of a classification problem. Management Science, 24/14, 1515-1525.
Sall, J. P. (1981). SAS Regression Applications. SAS Institute Inc. (Japanese version is translated by Shinmura.)
Sall, J. P., Creighton, L. & Lehman, A. (2004). JMP Start Statistics, Third Edition. SAS Institute Inc. (Japanese version is edited by Shinmura.)
Schrage, L. (1991). LINDO－An Optimization Modeling System－. The Scientific Press.
Schrage, L. (2006). Optimization Modeling with LINGO. LINDO Systems Inc.
Shinmura, S. & Miyake, A. (1979). Optimal linear discriminant functions and their application．COMPSAC79, 167-172.
Shinmura, S. (1998). Optimal Linear Discrimrnant Functions using Mathematical Programming. Journal of the Japanese Society of Computer Statistics, 11 / 2 , 89-101.
Shinmura, S. (2000). A new algorithm of the linear discriminant function using integer programming. New Trends in Probability and Statistics，5, 133-142.
Shinmura, S. (2004). New Algorithm of Discriminant Analysis using Integer Programming. IPSI 2004 Pescara VIP Conference CD-ROM, 1-18.
Shinmura, S. (2007). Overviews of Discriminant Function by Mathematical Programming. Journal of the Japanese Society of Computer Statistics, 20/1-2, 59-94.
Shinmura, S. (2009). Improvement of CPU time of Revised IPLP-OLDF using Linear Programming. Journal of the Japanese Society of Computer Statistics, 22/1, 37-57.
Shinmura, S. (2010). The optimal linear discriminant function. Union of Japanese Scientist and Engineer Publishing (in Japanese).
Shinmura, S. (2011a)．Problems of Discriminant Analysis by Mark Sense Test Data．Japanese Society of Applied Statistics，40/3，157-172．
Shuichi, Shinmura. (2011b). Beyond Fisher’s Linear Discriminant Analysis- New World of Discriminant Analysis -. 2011ISI CD-ROM, 1-6.
Shuichi, Shinmura. (2013). Evaluation of Optimal Linear Discriminant Function by 100-fold cross validation. 2013ISI CD-ROM, 1-6.
Shuichi, Shinmura. (2014). End of Discriminant Functions Based on Variance Covariance Matrices. 2014 ICORE, 1-10.
Stam, A., (1997). Nontraditinal approaches to statistical classification: Some perspectives on Lp-norm methods. Annals of Operations Research, 74, 1-36.
Vapnik, V. (1995). The Nature of Statistical Learning Theory．Springer-Verlag,1995.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
