Geri Dön

Implementation of a specialized algorithm for clustering using minimum enclosing balls

En küçük kürelerle demetleme problemi için özgün bir algorithmanın geliştirilmesi

PDF İndir

  1. Tez No: 266035
  2. Yazar: UTKU GURUŞÇU
  3. Danışmanlar: DOÇ. DR. EMRE ALPER YILDIRIM
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Algoritmalar, Kümeleme, Optimizasyon problemi, Yaklaşık çözüm, Algorithms, Clustering, Optimization problem, Approximate solution
  7. Yıl: 2010
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

Nesnelerin belirli yakınlık kıstaslarına göre gruplara ayrılmaları sürecine literatürde ?demetleme? (clustering) adı verilmektedir. Burada temel amaç, verilen nesne kümesindeki yapıyı ve örüntüleri (pattern) doğru bir şekilde tanımlayabilmektir. Dolayısıyla, kümeleme süreci sonucunda ortaya çıkacak olan gruplarda aranan nitelik, aynı gruba ait olan nesneler arasındaki yakınlık ilişkisinin farklı gruplara ait olan nesneler arasındakine göre daha yüksek olmasıdır. Kümeleme probleminin tesis yerleşimi, büyük ölçekli verilerin tasnifi ve pazarlama gibi çok değişik alanlarda uygulamaları bulunmaktadır. Bu uygulamalarda büyük ölçekli kümeleme probleminin etkin çözümüne gereksinim duyulmaktadır. Bu tez çerçevesinde kümeleme probleminde verilen nesneleri temsil eden ve yüksek boyutlu bir uzayda yer alan m tane vektörü kapsayan, yarıçapları toplamı veya en büyüğünün yarıçapı en küçük olan k tane kürenin hesaplanması problemleri ele alınmıştır. Bu problemlerin çözümleri sonucunda problemlerde verilen nesneler, birbirlerine olan yakınlık ilişkisine göre k tane gruba ayrılmaktadır. Sözü edilen matematiksel problemler, evrensel olarak en zor problemler sınıfında yer almaktadır (NP-zor). Literatürde, problemlerin sadece en iyi çözümlerini hesaplamanın değil, iyi bir yaklaşık çözümlerini hesaplamanın bile evrensel olarak zorluğu gösterilmiştir. Bu tezde problemlerin özgün yapıları kullanılarak özel çözüm yöntemleri geliştirilmiştir. Bu çözüm yöntemleri, dal-sınır yöntemi kullanılarak en iyi çözümün sistemli ve etkin bir şekilde aranması üzerine kurgulanmıştır. Bu çözüm sürecinde verilen vektörleri kapsayan tek bir kürenin hesaplanması, sürekli çözülmesi gereken bir alt problem olarak ortaya çıkmaktadır. Bu alt problemlerin çözümü için son zamanlarda geliştirilen etkin çözüm yöntemlerinden faydalanılmıştır. Geliştirilen çözüm yöntemleri, bir yazılıma dönüştürülerek uygulamada kullanılmaları sağlanmıştır. Geniş çevrelerin kullanımını sağlayabilmek amacıyla yazılımda kullanılabilirlik artırılmıştır. Yapılan kapsamlı deneysel hesaplama çalışmaları sonucunda geliştirilen yöntemlerin büyük ölçekli problemleri etkin bir şekilde çözebildikleri ortaya çıkarılmıştır. Geliştirilen yazılım, diğer pek çok geometrik eniyileme problemlerine de uygulanabilecek şekilde esnek ve modüler bir yapıda tasarlandığı için gelecekteki benzeri akademik çalışmalar için önemli bir alt yapı teşkil etmektedir.

Özet (Çeviri)

Clustering is the process of organizing objects into groups whose members are similar in some ways. The main objective is to identify the underlying structures and patterns among the objects correctly. Therefore, a cluster is a collection of objects which are more similar to each other than to the objects belonging to other clusters. The clustering problem has applications in wide-ranging areas including facility location, classification of massive data, and marketing. Many of these applications call for the solutions of the large-scale clustering problems. The main problem of focus in this thesis is the computation of k spheres that enclose a given set of m vectors, which represent the set of objects, in such a way that the radius of the largest sphere or the sum of the radii of spheres is as small as possible. The solutions of these problems allow one to divide the set of objects into k groups based on the level of similarity among them. Both of the aforementioned mathematical problems belong to the hardest class of optimization problems (i.e., they are NP-hard). Furthermore, as indicated by previous results in the literature, it is not only hard to find an optimal solution to these problems but also to find a good approximation to each one of them. In this thesis, specialized algorithms have been designed and implemented by taking into account the special underlying structures of the studied problems. These algorithms are based on an efficient and systematic search of an optimal solution using a Branch-and-Bound framework. In the course of the algorithms, the problem of computing the smallest sphere that encloses a given set of vectors appears as a sequence of sub problems that need to be solved. Our algorithms heavily rely on the recently developed efficient algorithms for this sub problem. A software has been developed that can implement the proposed algorithms in order to use them in practice. A user-friendly interface has been designed for the software. Extensive computational results reveal that our algorithms are capable of solving large-scale instances of the problems efficiently. Since the architecture of the software has been designed in a flexible and modular fashion, it serves as a solid foundation for further studies in this area.

Benzer Tezler

  1. Tez No

    33

    New algorithms and techniques for microprocessor-controlled PWM induction drives

    Başlık çevirisi yok

    OSMAN KÜKRER

    Doktora

    İngilizce

    İngilizce

    1987

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. H. BÜLENT ERTAN

  2. Tez No

    42

    A Decision support system for planning standby garbage collection trucks

    Yedek çöp toplama kamyonlarının planlanması için bir karar destek sistemi

    GÜLSER HACISALİHOĞLU

    Yüksek Lisans

    İngilizce

    İngilizce

    1987

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

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

    PROF. DR. HALİM DOĞRUSÖZ

  3. Tez No

    1305

    Stuctured development of a departmental information system

    Başlık çevirisi yok

    EKREM AZİMLİ

    Yüksek Lisans

    İngilizce

    İngilizce

    1987

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    PROF. DR. ZİYA AKTAŞ

  4. Tez No

    1259

    Design and implementation of concurrency on IBM PC XT

    Başlık çevirisi yok

    AHMET ALİ COKER

    Yüksek Lisans

    İngilizce

    İngilizce

    1987

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    PROF. DR. ZİYA AKTAŞ

  5. Tez No

    1309

    Design and implementation of an automated examination system

    Başlık çevirisi yok

    MUSTAFA TÜTÜNCÜ

    Yüksek Lisans

    İngilizce

    İngilizce

    1987

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    Y.DOÇ.DR. BÜLENT EPİR

Geri Dön