臺灣博碩士論文加值系統

區別分類器(Discriminant Classifier)是一種已知既有類別的機器學習技術。主要有費雪區別(Fisher’s Discriminant)及最小平方誤差區別(Minimum-Squared-Error)兩種。一般而言，最小平方誤差區別是用在兩類的資料上。多類別最小平方誤差區別將其延伸到三個類別以上的資料，利用葛蘭-舒密特過程(Gram-Schmidt process)將一組線性獨立的向量轉為一組互相直交且長度為一的類別標籤向量。類別標籤向量必須要直交，以使區別向量之間也互相直交。但是，給予不同的線性獨立向量，多類別最小平方誤差區別會解出不同的類別標籤向量，因而所求出的區別向量也會不同，此方法所求出的解可能並不是最佳解。
本研究發展一個遞迴的演算法，以求得一組區別向量及類別標籤向量來同時使得目標為最佳。此演算法的目標為得到一組區別向量，使得樣本求出的區別分數與其類別標籤越近越好。此演算法由冪法(Power Method)來證明其收斂。本研究所提出的區別方法稱為「多類別遞迴最小平方誤差區別」。
經由上述方法，我們可得到樣本區別分數，要依照其區別分數分類有許多可用的準則。分類準則主要有兩種，一是以距離為基礎，另一是以機率為基礎。此論文中會介紹四種分類準則，鳶尾花(Iris)的資料集將會被用來作為此遞迴演算法及分類準則的範例。
最後，我們會用兩組真實世界中的多類別資料來測試。比較此遞迴演算法搭配不同分類準則的準確度，以及此分類器與費雪區別分類器、多類別最小平方誤差區別分類器的績效。

Discriminant classifier is a type of supervised machine learning technique. There are two approaches to it. One is the Fisher’s discriminant; the other is the Minimum-Squared-Error (MSE) discriminant. The MSE discriminant is usually used to deal with two-class problems. The multi-class MSE approach extends the MSE discriminant to allow problems with more than two classes by providing a set of orthonormal class-label vectors through the Gram-Schmidt process. The resulting class-label vectors are made orthonormal so that the discriminants can be orthogonal as well. However, by giving different linearly independent vectors to the Gram-Schmidt process, the resulting class-label vectors will be different and so do the corresponding discriminants. That is, the solution of multi-class MSE is not unique and may not be the optimal.
This research develops an iterative algorithm to obtain the class-label vectors and the discriminant loadings simultaneously while the objective is achieved. The objective is to make the discriminant scores as close to its corresponding class labels as possible. The iterative process is proven to be converged by the power method. The multi-class discriminants found through this iterative algorithm is called multi-class iterative MSE discriminants (IMSED).
Through discriminant approaches, we will obtain the discriminant score for each instance. To allocate the instances to classes, there are mainly two types of classification rules. One is distance based; the other is probability based. Four classification rules will be discussed in this research and a probabilistic classification rule will be developed. Iris dataset will be used to illustrate the iterative algorithm and the classification rules.
Finally, two real-world data sets with multiple classes are used to compare the IMSED classifier with the Fisher’s discriminant classifier and the multi-class MSE discriminant classifier.

論文摘要 viii
Abstract iii
Contents v
Contents of Figures vii
Contents of Tables ix
Chapter 1: Introduction 1
1.1 Background 1
1.2 Discriminant Classification 2
1.2.1 Fisher Linear Discriminant (FLD) 5
1.2.2 Linear Minimum-Squared-Error (MSE) Discriminant 8
1.2.3 Kernel Tricks 13
1.2.4 Kernel Fisher Discriminants (KFD) 16
1.2.5 Kernel Minimum-Squared-Error (kernel MSE) Discriminant 19
1.2.6 The multi-class MSE Discriminant 23
1.3 Classification Rules 26
1.3.1 Classification Rule Based On Euclidean Distance 26
1.3.2 Classification Rule Based On Mahalanobis Distance 26
1.3.3 Classification Rule Based On Naive Bayesian Classifier 27
1.3.4 Classification Rule Based On Probability Models 28
1.4 Problems of The multi-class MSE Approach and Research Objectives 30
1.5 Thesis Organization 31
Chapter 2: Multi-class Iterative MSE Discriminant (IMSED) Classifier 33
2.1 Problem of multi-class MSE discriminant classifier 33
2.2 Multi-class Iterative MSE Discriminant 36
2.3 Illustration with Iris dataset 45
2.4 Convergence Proof 49
2.5 Illustrate classification rules on IMSED 51
2.5.1 Euclidean distance based classification rules on IMSED 52
2.5.2 Mahalanobis distance based classification rules on IMSED 52
2.5.3 Naive Bayesian Classifier based classification rules on IMSED 52
2.5.4 Probability Models based classification rules on IMSED 53
2.6 IMSED Classification of Independent-Test Data 57
Chapter 3: Case Study 59
3.1 Medline Dataset 59
3.2 Hayes-Roth Dataset 70
Chapter 4: Conclusions and Suggestions on Future Research 75
References 77

[1]W. J. Frawley, G. Piatetsky-Shapiro, and C. J. Matheus, Knowledge discovery in databases: An Overview, in AI Magazine. Fall 1992. p. 213-228.
[2]R. A. Fisher, The use of multiple measurement in taxonomic problems. Annals of Eugenics, 1936. 7: p. 178-188.
[3]R. O. Duda and P. E. Hart, Pattern Classification and Scene Analysis. 1973: John Wiley & Sons.
[4]C.-W. Li, Effective Multi-class Kernel MSE Classifier with Sherman-Woodbury Formula in Institute of Industrial Engineering. 2006, National Taiwan University.
[5]S. Mika, G. Ratsch, J. Weston, and B. Scholkopft. Fisher discriminant analysis with kernels. in Neural Networks for Signal Processing IX. 1999: IEEE Signal Processing Society Workshop.
[6]J. Xu, X. Zhang, and Y. Li. Kernel MSE algorithm: a unified framework for KFD, LS-SVM and KRR. in Processing of 2001 International Joint Conference on Neural Networks. 2001. Washington DC, USA.
[7]B. Schölkopf, A. J. Smola, and C. J. C. Burges, Advances in Kernel Methods: support vector learning 1999: The MIT Press, Cambridge, MA.
[8]C. A. Micchelli, Algebraic aspects of interpolation, in Proceedings of Symposia in Applied Mathematics v.36. 1986. p. 81-102.
[9]G. H. Golub and C. F. v. Loan, Matrix Computations. 3rd ed. 1996, Baltimore, London: John Hopkins University Press.
[10]S. Mika, A. Smola, and B. Schölkopf, An improved training algorithm for kernel fisher discriminants Proceedings AISTATS, 2001.
[11]M. E. Maron, Automatic Indexing: An Experimental Inquiry. Journal of the ACM, 1961. 8(3): p. 404.
[12]R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification and Scene Analysis. 1973, New York: John Wiley and Sons.
[13]W. J. Krzanowski, Principles of Multivariate Analysis: A User''s Perspective. Revised ed. 2000, New York: OXFORD. p.332-349.
[14]H. Wold, Nonlinear estimation by iterative least squares procedures, in Research papers in statistics : festschrift for Jerzy Neyman, F.N. David, Editor. 1966, Wiley: New York. p. 383-407.
[15]H. Wold, Nonlinear iterative Partial least squares (NIPALS) modeling: Some current developments, in Multivariate analysis--III : proceedings, P.R. Krishnaiah, Editor. 1973, Academic Press: New York. p. 383-407.
[16]UCI Machine Learning Repository. Available from: http://www.ics.uci.edu/~mlearn/MLRopositiry.html.
[17]G. Strang, Linear Algebra and Its Applications. 3rd ed. 1998: Thomson Learning, Inc.
[18]Goldstein, Calculus and Its Applications. 8th ed. p.23.
[19]H. Kim, P. Howland, and H. Park, Text classification using support vector machines with dimension reduction. Journal of Machine Learning Research 6, 2005: p. 37-53.
[20]H. Park. Some Text Data. 2003 Available from: http://www.cc.gatech.edu/~hpark/data.html.
[21]C.-W. Hsu, C.-C. Chang, and C.-J. Lin, A Practical Guide to Support Vector Classification.
[22]T. Hastie, R. Tibshirani, and A. Buja, Flexible Discriminant Analysis by Optimal Scoring. Journal of the American Statistical Association, 1994: p. 1255-1270.