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
- Tez No: 266035
- Danışmanlar: DOÇ. DR. EMRE ALPER YILDIRIM
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2010
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 122
Ö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
- Bir dişli pompa grubunun imalatında eşzamanlı mühendislik ve grup teknolojisi
The carrying out of group technology in the concurrent engineering concept on a factory which is manufacturing gear pomp
ALPER ASLAN
Yüksek Lisans
Türkçe
1997
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. TEOMAN KURTAY
- Automatic distribution of serialized programs and distributed system evaluation
Seri programların otomatik dağıtımı ve dağıtık sistemin değerlendirilmesi
VAHID AKRAM
Yüksek Lisans
Farsça
2005
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolIslamic Azad UniversityBilgisayar Mühendisliği Ana Bilim Dalı
DR. SAEED PARSA
- Automatic distribution of serialized programs and distributed system evaluation
Seri programların otomatik dağıtımı ve dağıtık sistemin değerlendirilmesi
VAHİD AKRAM
Yüksek Lisans
Türkçe
2005
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolIslamic Azad UniversityYazılım Mühendisliği Ana Bilim Dalı
DR. SAEED PARSA
DR. ABOLFAZL HAGİGAT
- Design and implementation of an autonomous vehicle enhanced by advanced driver assistance systems (ADAS) using ML
ML kullanarak gelişmiş sürücü destek sistemleri (ADAS) ile geliştirilmiş otonom bir aracın tasarımı ve uygulanması
MUSTAFA OUDAH HANI ALSAEDI
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAltınbaş ÜniversitesiElektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÇAĞDAŞ A TİLLA
- GPU üzerinde yazılım tabanlı anten gerçeklenmesi
Realization of software-defined antenna on GPU
ABDULLAH BAKIRTAŞ
Yüksek Lisans
Türkçe
2015
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. SELÇUK PAKER