A mixed-integer programming approach to multi-class data classification problem

Abstract

Veri Sınıflandırma, farklı özelliklere sahip örneklerin bilinen sınıflara olan üyeliğinibelirlemeye çalışan veri madenciliğinin önemli bir problemidir. Veri setini iki gruba ayırangeleneksel yöntemler çok sınıflı veri sınıflandırma problemlerinde beklenen iyi sonuçlarıgöstermemektedir. Bu tezde veri sınıflandırma problemi için geliştirilmiş tamsayı karışıkprogramlamaya dayalı yeni bir yöntemi anlatmaktadır. Önerilen yeni yöntemde sınıflarınsınırlarını belirlemek amacıyla çok boyutlu kutular kullanılmaktadır. Bu çok boyutlu kutularınvarlığını ve sınırlarını temsil etmek için tamsayı karışık programlama modeli geliştirilmiştir.Ayrıca, soyut karar değişkenleri arasındaki ilişkiler Önermeler Mantığı kullanılarak ifadeedildikten sonra Mantıksal Cebir kullanılarak tamsayı kısıtlamalara dönüştürülmüştür. Buyeni yöntem bir örnek üzerinde ayrıntılı olarak açıklanmıştır. Bu modelin verimliliği verisınıflandırılmasında çok bilinen ve çok kullanılan veri setleri üzerinde test edilmiştir. Örnekproblem ve bilenen veri setleri kullanılarak elde edilen sonuçlar önerilen yöntemin oldukçadoğru ve verimli olduğunu ispatlamaktadır.

Data classification is an important data mining problem that aims todetermine the membership of different data points to a number of different sets.Traditional approaches that are based on partitioning the data sets into two groupsperform poorly for multi-class data classification problems. A new dataclassification method based on mixed-integer programming is presented in thisthesis. The proposed approach is based on the use of hyper-boxes for definingboundaries of the classes that include all or some of the points in that set. A mixed-integer programming model is developed for representing existence of hyper-boxesand their boundaries. In addition, the relationships among the discrete decisions inthe model are represented using propositional logic and then converted to theirequivalent integer constraints using Boolean algebra. The proposed approach formulti-class data classification is illustrated on an example problem. The efficiencyof the proposed method is tested on two separate data sets; the well-known IRISdata set and the protein folding type data set. The computational results on theillustrative example and the benchmark problems show that the simplicity andaccuracy of the proposed method provides scientific insight into the multi-classdata classification problems.