A column generation approach to solve ranking problems
Sıralama problemlerini çözmek için sütun oluşturma yöntemi
- Tez No: 651472
- Danışmanlar: DR. ÖĞR. ÜYESİ MUSTAFA GÖKÇE BAYDOĞAN
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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.
Özet (Çeviri)
Many traditional classification approaches focus on the minimization of misclassification rate. However, this is not a suitable metric in case of imbalance in class distribution and unknown misclassification costs. In such cases, Area under Receiver Operating Characteristics Curve (AUC) is an effective metric, which also quantifies the ranking quality of a classifier. Although this metric can be optimized directly by employing some mixed integer programming models, it is challenging to solve these models due to large number of binary variables. Some alternative formulations such as margin maximizing approaches optimizing surrogate objectives are proposed to solve this problem approximately. These methods extend classical Support Vector Machine (SVM) formulation and aim at minimizing ranking error while penalizing the model coefficients with a cost parameter in the objective. In these approaches, the cost and kernel-related parameters (i.e., type, degree and etc.) must be determined by parameter tuning operations since the test performance is highly reliant on these parameters. Primary aim of this study is to avoid the repetitive experiments to tune the parameters of margin-maximization approaches. We propose a linear programming model and a column generation approach, namely Ranking-CG, to select relevant features in an iterative way to decrease the number of features in the model. Additionally, kernel selection is avoided using the Euclidean distances between points as features to learn the non-linear relations. Ranking-CG is modified slightly to obtain faster convergence by solving a non-linear subproblem at each iteration to find the vector (i.e. prototype) in the feature space that violates dual feasibility the most. Our experiments show that the modified approach, Ranking-CG Prototype, provides competitive results with significantly less number of features compared to margin-maximization approaches.
Benzer Tezler
- Fraktal geometri ve hidrolik pürüzlülük
The Fractal geometry and the hydraulic roughness
SAİT ALANSATAN
- Ovulasyon indüksiyonu tedavisinde folliküler gelişimin ultrasonografik takibi
Başlık çevirisi yok
MERİH BAYRAM
Tıpta Uzmanlık
Türkçe
1987
Kadın Hastalıkları ve DoğumGazi ÜniversitesiKadın Hastalıkları ve Doğum Ana Bilim Dalı
DOÇ. DR. MÜLAZIM YILDIRIM
- Çimentonun sertleşmesi üzerinde kimyasal komponentlerin etkisi
Başlık çevirisi yok
NACİYE TÜRKEL
Yüksek Lisans
Türkçe
1986
Kimya MühendisliğiUludağ ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. MUSTAFA CEBE
- Bazı esterlerin kinetik incelenmesi ve termodinamik parametrelerin belirlenmesi
Kinetic study and detesmination of thermodnamic parameters of some esters
İBRAHİM TAŞ
Yüksek Lisans
Türkçe
1986
Kimya MühendisliğiUludağ ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. MUSTAFA CEBE
- İzmir'de bazı yolların kapatılarak yaya bölgeleri oluşturma da kent peyzajını geliştirme açısından yeniden planlanması üzerinde araştırmalar
Başlık çevirisi yok
BAHAR TÜRKYILMAZ
Yüksek Lisans
Türkçe
1985
Şehircilik ve Bölge PlanlamaEge ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı