MILP based hyper-box enclosure approach to multi-class data classification

Abstract

Veri Sınıflandırma, farklı özelliklere sahip örneklerin bilinen sınıflara olan üyeliğini belirlemeye çalışan önemli bir veri madenciliği problemidir. Veri setini iki gruba ayıran geleneksel yöntemleri çok sınıflı veri sınıflandırma problemlerine uygulayabilmek için bazı düzenlemelere gerek vardır. Yapılan bu değişiklikler kullanılan yöntemin verimliliğini etkilemekte ve modeli daha karmaşık bir hale getirmektedir. Bu tezde çok gruplu veri sınıflandırma problemi için geliştirilmiş tamsayı karışık programlamaya dayalı yeni çok boyutlu kutu yaklaşımı anlatılmaktadır. Büyük veri kümeleri ile çalışabilmek için çok boyutlu kutu yaklaşımının eğitici bölümünde kullanılmak üzere üç aşamalı matematiksel programlamaya dayalı bir yöntem geliştirilmiştir. Birinci aşamada, eğitici kümedeki sınıflandırması zor olan örnekler belirlenerek, tohum bulma ve alt küme oluşturma algoritmaları uygulanmaktadır. Daha sonra edinilen bu gözlem ve tohumlar kullanılarak eniyileme modeli çözülmektedir. Son olarak da problemsiz örneklerin kutulara atanması, kesişme engelleme ve kutu birleştirme algoritmaları uygulanmaktadır. Bu üç aşamalı eğitici çalışmalar sonrasında, metodun verimliliği uzaklığa dayalı basit bir test algoritması ile ölçülmüştür. Bu üç aşamalı modelin verimliliği veri sınıflandırılmasında çok bilinen ve çok kullanılan veri setleri üzerinde test edilmiştir. Bunlar protein katlanma tahmin problemi ve UCI veri havuzu problemleridir. Örnek problem ve bilenen veri setleri kullanılarak elde edilen sonuçlar önerilen yöntemin çok sınıflı veri sınıflandırma problemine önemli bir katkıda bulunduğunu kanıtlamaktadır.

Data classification is an important data mining problem that aims to determine the membership of different instances to a number of different sets. Traditional approaches that are based on partitioning the data sets into two groups need some modifications for multi-class data classification problems. These modifications affect the efficiency and make the models more complex. In this thesis, a novel mixed integer programming based hyper-box enclosure approach is presented for multi-class data classification problems. In order to deal with large data sets, a three-stage mathematical programming based approach is developed for training part analysis of hyper-box enclosure method. Training set is preprocessed to identify the observations that are more difficult to classify, and seed finding and sub grouping algorithms are applied in the first stage. Then, optimization model is formulated considering these observations and seeds. Finally, assignments of non-problematic instances, intersection elimination and box combination algorithms are carried out. After training analysis with this three stage approach, the efficiency of the method is tested by the simple distance based testing algorithm. The efficiency of the proposed three-stage method is tested on two separate benchmark problems; the protein folding type prediction problem and the UCI Repository data sets. The computational results on the illustrative example and the benchmark problems show the accuracy of the proposed method.