Rolling look-ahead approaches for optimal classification trees

Abstract

Classification trees have gained tremendous attention in machine learning applications due to their inherently interpretable nature. Current state-of-the-art formulations for learning optimal binary classification trees suffer from scalability for larger depths or larger instances. Moreover, they mostly fail to prove optimality after long run times and fit perfectly to the training data while minimizing misclassification error which is likely fail to generalize to the test data. We present a simple but powerful new formulation which we call rolling look-ahead learning approach. By dropping tractability variables which are dependent on instance size, we present a novel two-depth optimal binary classification tree formulation with the objective to minimize gini impurity or misclassification error. The approach can be thought of as a middle ground between myopic and global optimization methods. For larger depths, we developed a hybrid approach which learns by looking ahead 2-steps rolling horizon. It is much faster than the fastest known global optimization methods which can solve an instance with around 50K rows & 135 features in less than 4 minutes, for depth 8. Also, in majority of cases, the proposed approach outperforms global optimization methods & CART in terms of win count tested for 7 depths, 10 Fold and 19 benchmark datasets, and increase in out-of-sample accuracy up to 16.8% and 11.9% with respect to global optimization methods and CART, respectively.

Son zamanlardaki ikili sınıflandırma karar ağacı ̈oğrenim en iyileme formülasyonları, büyük derinliklerde veya büyük verisetlerinde ̈olçeklenebilirlikle ilgili sorunlar yaşamaktadır. Uzun saatler süren ̧calışma sürelerine rağmen, en iyi değeri kanıtlamakta sorun yaşamaktadırlar. Ayrıca, eğitim sürecinde amaç fonksiyonu olarak yanlış sınıflandırma metriği sonucu, test setinde yanlı bir sonuç ̧cıkabilmekte, iyi sınıflandırma yapmakta sorun yaşamaktadır. Bu ̧calışmada, ̈onceki ̧calışmaların veri boyutuna bağlı olan ve takip eden değişkenlerinden kurtulup, CART gibi algoritmalardan da esinlenerek, 2 derinlikli ağaçlar için yenilikçi bir formülasyon sunuyoruz. Algoritma açgözlü yaklaşımlar ve global optimizasyon yöntemleri arasında kalan spektrumdan faydalanıyor. Daha büyük derinlikli ağaçlar için ise, 2 seviye ileri görerek öğrenen hibrit bir algoritma geliştirdik. Bu algoritma, yaklaşık 50 bin satırlı, 135 ̈ozellikli bir veride 8 derinlikli bir ağacı 4 dakikadan daha kısa sürede çözebilir ve gelişime açıktır. Ayrıca, mevcutta bulunan en iyi global optimizasyon ve CART yaklaşımını skor sayısıyla geçebilirken, global optimizasyon modellerine göre test setinde %16.8'e kadar bir artış, CART'a göre ise %11.9'a kadar bir artış gözlemlenmiştir. Gözlemler 19 veri seti, 7 farklı derinlik ve 10 katlamalı veri grubunda test edilmiştir. v