Implementation of a specialized algorithm for clustering using minimum enclosing balls

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.