Multivariate decision trees for machine learning
|
|  Yüklə 5.57 Mb.
|
|
MULTIVARIATE DECISION TREES FOR MACHINE LEARNING by Olcay Taner Yıldız B.S. in CmpE., Boğaziçi University, 1997 Submitted to the Institute for Graduate Studies in Science and Engineering in partial fulfillment of The requirements for the degree of Master of Science In Computer Engineering Boğaziçi University 2000
MULTIVARIATE DECISION TREES FOR MACHINE LEARNING APPROVED BY: Assoc Prof. Dr. Ethem Alpaydın ……….. (Thesis Supervisor) Assoc Prof. Dr. H. Levent Akın ……….. Prof. Dr. Aytül Erçil ……….. DATE OF APPROVAL: ACKNOWLEDGMENTSI would like to thank Assoc. Prof. Ethem Alpaydın for his supervision in this MS study and for his support and advises. I am also grateful to all my friends, my family, my teachers and my love. Without their support, this thesis would have not been accomplished. ABSTRACTIn this thesis, we detail and compare univariate, linear and nonlinear decision tree methods using a set of simulations on twenty standard data sets. For univariate decision tree methods, we have used the ID3 algorithm and for multivariate decision tree methods, we have used the CART algorithm. For linear and nonlinear methods, we have used neural networks at each decision node. We also propose to use the LDA algorithm in constructing linear multivariate decision trees. Univariate decision trees at each decision node consider the value of only one feature leading to axis-aligned splits. In a linear multivariate decision tree, each decision node divides the input space into two with an arbitrary hyperplane leading to oblique splits. In a nonlinear one, a multilayer perceptron at each node divides the input space arbitrarily, at the expense of increased complexity. We propose hybrid trees where the decision node may be linear or nonlinear depending on the outcome of a statistical test on accuracy. We also propose to use linear discriminant analysis at each decision node. Our results indicate that if the data set is small and has few classes, then a univariate technique does not overfit and can be sufficient and the univariate ID3 has better performance than multivariate linear methods. ID3 learns fast, learns simple and interpretable rules. If the variables are highly correlated, then the univariate method is not sufficient and we may resort to multivariate methods. We have shown that ID-LDA has better performance than CART in terms of accuracy, node size and very significantly in learning time. It has also smaller learning time than ID-LP and the same accuracy. ID-LDA generates smaller trees than ID3 and CART. This shows that to generate a linear multivariate tree, using ID-LDA is preferable over CART, and may be preferable over ID-LP if learning time is critical. ÖZETBu tezde, tek değişkenli, doğrusal, ve doğrusal olmayan çok değişkenli karar ağaç kurma metodları karşılaştırıldı. Tek değişkenli karar ağaçları için örnek olarak ID3, çok değişkenli karar ağaçları için CART yöntemi kullanıldı. Doğrusal ve doğrusal olmayan metodlar içinse karar düğümünde değişik sinir ağları yapılarından faydalanıldı. Ayrıca Fisher’in doğrusal ayırma analizinin çok değişkenli karar ağacı oluşturulmasında kullanılması önerildi. Tek değişkenli karar ağaçları her karar düğümünde tek değişkenin değerine bakarak eksenlere dik bölmeler yaparlar. Doğrusal karar ağaçlarında ise her dalda giriş uzayı rasgele bir düzlemle bölünür. Doğrusal olmayan karar ağaçlarında ise çok katmanlı sinir ağları giriş uzayını rasgele böler. Bu tezde melez ağaçlar önerildi. Bu ağaçlarda karar düğümü doğrusal veya değildir. Kararın doğrusal olup olmamasına ise bir istatistik testinin sonucuna bakılarak karar verilmektedir. Doğrusal ayırma analizi ile doğrusal çok değişkenli karar ağaçları yapay sinir ağı temelli karar ağaçlarından çok daha hızlı öğrenilir. Sonuçlarımız gösteriyor ki, eğer veri kümesi küçük ve bu kümede az sınıf varsa, tek değişkenli metod yeterli olabilir ve ID3 çok değişkenli metodlardan daha iyi performans gösterir. ID3 hızlı ve kolay öğrenir, kuralları da kolayca yorumlanabilir. Eğer değişkenler birbiriyle çok ilişkiliyse, tek değişkenli metod yeterli olmayabilir ve çok değişkenli metodları kullanabiliriz. Bu tezde gösterildi ki ID-LDA metodu CART’tan daha başarılı, daha küçük ağaçlar üretmekte ve daha az zaman harcamaktadır. Aynı zamanda ID-LP den daha hızlı ve eşit başarılıdır. ID-LDA ID3 ve CART’tan daha küçük ağaçlar üretir. Bu da gösteriyor ki çok değişkenli ağaç üretmek için ID-LDA CART’a göre tercih edilebilir ve eğer zaman önemli ise ID-LP’ye gore de tercih edilebilir. TABLE OF CONTENTSPage ACKNOWLEDGMENTS iii ÖZET v TABLE OF CONTENTS vi LIST OF FIGURES viii LIST OF SYMBOLS xiii 1. INTRODUCTION 1 2. DECISION TREE LEARNING 3 2.1. Algorithm for Tree Construction 6 2.2. Identification Trees (ID3) 7 2.3. Partition-Merit Criteria 8 2.3.1. Weak Theory Learning Measure 9 2.3.2. Information Gain 10 2.3.3. Gini Index 11 2.4. Multiple Splits 11 2.5. Filling in Missing Values 13 2.6. Avoiding Overfitting 13 2.6.1. Pre-pruning 14 2.6.2. Post-pruning 15 3. MULTIVARIATE DECISION TREES 17 3.1. Univariate vs. Multivariate Splits 17 3.2. Symbolic and Numeric Features 20 3.3. Feature Selection 21 3.4. Classification and Regression Trees (CART) 22 4. NEURAL NETWORK MODELS FOR TREE CONSTRUCTION 25 4.1. Training Neural Networks 26 4.1.1. Linear Perceptron Model 26 4.1.2. Multilayer Perceptron Model 28 4.1.3. The Hybrid Model 30 4.2. Class Separation by Selection Method 31 4.3. Class Separation by Exchange Method 32 5. THE STATISTICAL MODEL FOR TREE CONSTRUCTION 33 6. RESULTS 36 6.1. Results for Identification Trees 37 6.1.1. Comparison of Different Kinds of Learning Measures 37 6.1.2. Comparison of Pruning Techniques 46 6.1.3. Comparison of Multiple Splits 55 6.2. Results for Classification and Regression Trees 62 6.3. Results for Neural Network Methods 70 6.3.1. Comparison of Class Separation Techniques 70 6.3.2. Comparison of Hybrid Tests in Decision Nodes for Neural Networks 77 6.3.3. Comparison of the Network Structures in Decision Nodes 86 6.4. Results for LDA 95 6.4.1. Effects of PCA on the Results 95 6.4.2. Effects of PCA Percentage on the Results 101 6.4.3. Comparison of Different Linear Multivariate Techniques 108 7. CONCLUSIONS 118 APPENDIX A 127 APPENDIX B 131 REFERENCES 133 REFERENCES NOT CITED 136 |