Geri Dön

Using lagrangian relaxation and column generation for data clustering

Lagrange gevşetme ve sütun üretme kullanarak veri öbekleme

  1. Tez No: 246285
  2. Yazar: MEHMET AYRANCI
  3. Danışmanlar: PROF. İ. KUBAN ALTINEL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2009
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
  12. Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  13. 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

  1. 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

    İngilizce

    2009

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    Endüstri Mühendisliği Bölümü

    PROF. İ. KUBAN ALTINEL

  2. Termik konveksiyon öngörüsü

    Başlık çevirisi yok

    ELİF ŞEN

    Yüksek Lisans

    Türkçe

    Türkçe

    1996

    Meteorolojiİstanbul Teknik Üniversitesi

    PROF.DR. ZAFER ASLAN

  3. 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

    Türkçe

    2013

    Endüstri ve Endüstri Mühendisliğiİstanbul Üniversitesi

    İşletme Ana Bilim Dalı

    PROF. DR. ERHAN ÖZDEMİR

  4. 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

    İngilizce

    2001

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. GÜLAY BARBAROSOĞLU

  5. 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

    İngilizce

    1997

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. ÖMER KIRCA