Using lagrangian relaxation and column generation for data clustering
Lagrange gevşetme ve sütun üretme kullanarak veri öbekleme
- Tez No: 246285
- Danışmanlar: PROF. İ. KUBAN ALTINEL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2009
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
- Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Sayfa Sayısı: 67
Özet
Veri öbekleme temel olarak benzer özellikleri olan ögeleri, kesişimleri boş olan verilen sayıda altkümelerde toplamayı amaçlar. Böylece her altküme tek bir temsilciyle ilişkilendirilebilir ve temsilcilerin belirlenmesi gündeme gelir. Her öge, her bileşeni sayısal değerler taşıyan bir özellik vektörü olarak gösterilir ve ögeler arası benzemezlik metrikler yardımıyla ölçülür. Veri öbekleme, amaç altkümeyi oluşturan özellik vektörleri ile temsilcileri arasındaki toplam benzemezliği enküçüklemek olan bir matematiksel eniyileme modeli olarak gösterilebilir.Bu çalışmada, ilk olarak veri öbekleme problemini, benzemezliğin koordinatlara göre ayrılabilen bir metrik ile ölçüldüğünü varsayarak, özellik vektörleriyle temsilcileri arasındaki toplam beklenen uzaklığı enküçüklemek amacıyla gösterimliyoruz. Sonra ortaya çıkan karma tamsayılı doğrusal programlama problemini çözmek için bir Lagrange gevşetme yöntemi öneriyoruz. Ikinci gösterimimiz ise herhangi bir benzemezlik metriği için kullanılabilmekte ve birçok yönden çok tesisli Weber problemine benzemektedir. Sonuçta oluşan dışbükey olmayan eniyileme problemini, düşey üretme ve d.c. programlama teknikleri ile çözüyoruz. Sayısal deneylerimize göre, ilk yöntemin düşük başarıya sahip olmasına rağmen ikinci yöntemin k-ortalama algoritmasından çok daha başarılı olduğunu söyleyebiliriz.
Özet (Çeviri)
Clustering is the organization of patterns, which are usually represented as vectors in multidimensional spaces, into a given number of groups with similar characteristics. It can be formulated as a mathematical optimization model whose objective is to locate cluster representatives so that the sum of dissimilarities with the representative and given data vectors is minimized. In this work, we first formulate clustering problem for the minimization of the total expected distances between cluster representatives and data vectors, assuming that dissimilarities are measured using a metric separable with respect to the coordinates. We then propose a Lagrangian relaxation scheme for the solution of the resulting mixed integer linear programming problem. Our second formulation is for any distance metric and is analogous to the formulation of the multi-facilityWeber problem in many dimensions. The resulting nonconvex optimization problem is solved using column generation and d.c. programming techniques. According to our computational experiments we say that although the first one has low accuracy, the second one overperforms k-means algorithm.
Benzer Tezler
- Solving the capacitated multifacility Weber problem approximately
Sınırlı sığalı çok tesisli Weber problemi için yaklaşık çözüm yöntemleri
BURAK BOYACI
Yüksek Lisans
İngilizce
2009
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Bölümü
PROF. İ. KUBAN ALTINEL
- Lagrange Gevşetmesi ile küçük portföylerin elde edilmesi ve İMKB'ye uygulanması
Using Lagrangian Relaxation to obtain small portfolios and the implementation of the İstanbul Stock Exchange
GÖKHAN TURAN
Doktora
Türkçe
2013
Endüstri ve Endüstri Mühendisliğiİstanbul Üniversitesiİşletme Ana Bilim Dalı
PROF. DR. ERHAN ÖZDEMİR
- Integration of fuzzy optimization and stochastic programming in multi-commodity network flow problems
Bulanık eniyileme ve rassal programlamanın birden fazla ürünlü ağ akış problemlerinde birleştirilmesi
YASEMİN ARDA
Yüksek Lisans
İngilizce
2001
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. GÜLAY BARBAROSOĞLU
- An Object-oriented graphical user interface for a production scheduling problem in air supply and maintenance centers
Hava İkmal Bakım merkezlerinde üretim programlama problemi için nesneye yönelimli grafiksel kullanıcı arabirimi
MURAT ERMİŞ
Yüksek Lisans
İngilizce
1997
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ÖMER KIRCA