A column generation approach to solve ranking problems
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye
Tezin Onay Tarihi: 2020
Tezin Dili: İngilizce
Öğrenci: ERHAN CAN ÖZCAN
Danışman: MUSTAFA GÖKÇE BAYDOĞAN
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Özet:Klasik sınıflandırma yöntemleri, yanlış sınıflandırılan gözlemlerin sayısını en azlamayı amaçlar. Ancak; veri kümesindeki gözlemlerin sınıfsal dağılımları eşit olmadığında yanlış sınıflandırma oranına güvenmek çok anlamlı değildir. Bu yüzden; modellerin sıralama kalitelerini de gösteren Alıcı Çalışma Karakteristiği eğrisi altında kalan alanların büyüklüğüne (AUC) bakarak modellerin performansları karşılaştırılır. Karışık Tam Sayılı Lineer Programlama (LP) yöntemleri ile AUC doğrudan optimize edilebilse de, ikili değişkenlerin çokluğu, modelleri çözmeyi zorlaştırır. AUC' yi yaklaşık olarak eniyilemek için Destek Vektör Makinaları (Support Vector Machines) (SVM) modellerinin bir türevi olan ve bir vekil amaç fonksiyonuyla sınıflar arasındaki kenar payını büyütmeyi hedefleyen bazı alternatif yöntemler geliştirilmiştir. Bu yöntemlerde, aşırı öğrenmeyi engellemek ve doğrusal olmayan ilişkileri öğrenmek için çeşitli parametreler kullanılmalıdır. Bu parametreler, modellerin test performansını ciddi bir şekilde etkilediğinden bunları belirlemek için parametre ayarlama işleri uygulanmalıdır. Bu çalışmanın amacı, model parametrelerini seçmek için yapılan tekrarlı deneyleri önlemektir. Sıralama problemleri, sütun oluşturma (CG) tekniğini kullanan, Ranking-CG adında, bir LP modeli ile çözülür. Gözlemlerin özellikleri, modele yinelemeli eklenir ve aşırı öğrenme gözlenmeden CG işlemleri sonlandırılır. Doğrusal olmayan ilişkilerse; gözlemler arası Öklid mesafelerini kullanarak öğrenilmiştir. Yakınsamayı hızlandırmak için model modifiye edilmiştir. Bu kapsamda, her bir adımda doğrusal olmayan bir alt problem çözerek ikili problemin koşullarını en çok bozan vektör, prototip nokta, orijinal özellik uzayında bulunur ve bu nokta ile problem bir kere daha çözülür. Deneylerimize göre, Ranking-CG Prototype adını verdiğimiz yeni yöntem, daha az sayıda özellik kullanarak, kenar payını büyütmeyi amaçlayan modellerle benzer performans gösterir.