Optimization based polyhedral region approach for multi-class data classification problem

Çok gruplu veri sınıflandırması, verinin çoklu gruplara atanmasını içeren gözetimli bir makina öğrenmesi problemidir. Veri sınıflandırması problemleri için eğitim kümesinin hiperkutu, hiperdüzlem ve çokyüzlü bölgeler aracılığıyla ayrılmasına dayalı çeşitli yöntemler bulunmaktadır. Çokyüzlü yaklaşımlar ya ikili sınıflandırma problemi için tasarlanmıştır ya da global en iyi çözüm üstüne odaklanmamıştır. Hiperkutu yöntemleri modelin veriye uydurulması açısından kısıtlayıcıdır. Bununla birlikte, eğitim modelleri en iyi sınıflandırıcıların kurulması için karmaşıktırlar ve belli büyüklüğe kadar olan örneklere uygulanabilirler. Çok gruplu veri sınıflandırması problemini bir karma tamsayılı doğrusal programlama (KTDP) modeli kullanarak ele almaktayız. Her bir grubun veri kümesini, farklı grupların altkümeleri bir hiperdüzlemle ayrılabilecek şekilde altkümelere bölüyoruz. Bir altkümeyi ayıran hiperdüzlemler çokyüzlü bir bölge oluşturmaktadır ve farklı grupların bölgeleri ayrıktır. En iyi ayrışmayı bulmak için bölge sayısı ve yanlış sınıflandırılan veri noktalarının toplamını en azlayan bir KTDP modeli kullanılmaktadır. Çizge teorisine dayanan bir ön işleme aşaması, grupların çiftli ayrımını dikkate akarak problemi ayrıştırmak ya da basitleştirmek amacıyla önerilmektedir. Her bir veri kümesi için grup çiftlerinin doğrusal ayrıştırılabilirlik ilişkisini temsil eden bir yönsüz çizge olduğunu gösterdik. Çizgenin bağlı bileşenleri oluşturulur ve düğüm kümesinde birden fazla eleman olan her bir bağlı bileşen için KTDP modeli çözülür. Bağlı bileşenlerin en iyi çözümlerinin bütününden yola çıkarak ana KTDP modeli için eşdeğer bir en iyi çözüm bulunduğunu gösterdik. Bununla birlikte, doğrusal ayrılabilir altkümeleri oluşturmak için KTDP tabanlı yeni bir algoritma sunmaktayız. Her bir özyinelemede, yeni altkümenin eleman sayısını enbüyüten bir KTDP modeli kullanarak atanmamış örnek kümesinden örnek altkümesi oluşturmaktayız. Diğer grupların altkümelerinden doğrusal ayrılabilir olan yeni oluşturulan altküme atanmamış örnek kümesinden kaldırılır. Geriye kalan örnekler yeni altkümeler oluşturmak için kullanılır ve algoritma örneklerin tamamı atandığında sonlanır. Algoritma tarafından üretilen farklı grupların altkümelerinin doğrusal ayrılabilir olduğunu ve genel KTDP için uygun çözüm oluşturmak için kullanılabileceğini gösterdik. Buna ek olarak, algoritma birkaç özyinelemeyle veri kümesini eksiltmek için kullanılabilir, böylelikle KTDP modeli sadeleştirilmiş olur. Test aşaması için altkümelerin dışbükey zarflarını ve hiperdüzlemlerle tanımlanan çokyüzlü bölgeleri temel alan sınıflandırıcılar kurduk. Hiperdüzlemler destek vektör makinelerindeki gibi ayıracın genişliğinin enbüyütülmesiyle oluşturulur. Yaklaşımımızı 15 yapay veri kümesi ve 52 denektaşı problem üzerinde değerlendirdik ve literatürdeki yöntemlerle karşılaştırdık. Önerilen sınıflandırıcılarla tamamlanan eniyileme tabanlı yaklaşımımızın tahmin ölçüsü açısından rekabet eden sonuçlar verdiği neticesine vardık.