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ı: 52
Ö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
- Application of large-scale optimization methods in scheduling and routing problems
Çizelgeleme ve yönlendirme problemlerinde büyük ölçekli optimizasyon yöntemlerinin uygulanması
MILAD ELYASI
Doktora
İngilizce
2022
Endüstri ve Endüstri MühendisliğiÖzyeğin ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. OKAN ÖRSAN ÖZENER
- A Column generation approach to coalition formation in multi-agent systems
Çok ajanlı sistemlerde koalisyon kurma probleminin sütun üretme yöntemi ile çözümü
ÖNDER TOMBUŞ
Yüksek Lisans
İngilizce
2001
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. TANER BİLGİÇ
- Electric bus fleet composition and scheduling
Elektrikli otobüs filo kompozisyonu ve çizelgelemesi
ŞULE YILDIRIM
Yüksek Lisans
İngilizce
2021
UlaşımKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BARIŞ YILDIZ
- Büyük ölçekli havayolu ekip eşleme problemlerinin çözümü için bir kolon türetme stratejisi
A column generation strategy for large scale airline crew pairing problems
BAHADIR ZEREN
Doktora
Türkçe
2017
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. İBRAHİM OZKOL