Çoklu bölümlenmelerin birleştirilmesinde yeni verimli ve ölçeklenebilir yöntemler

Abstract

Bölümlenme, benzer veri nesnelerinin yarı denetimli veya denetimsiz şekilde gruplanması işlemidir. Verinin anlaşılması ve indirgenmesinde sıkça kullanılır. Çoklu bölümlenmelerin birleştirilmesi, bölümlenme araştırmalarında önemli bir eğilim olup, tek bir bölümlenme algoritması ile tipik olarak elde edilenden daha ileriye gitmektedir. Temel fikir, aynı veriden farklı bakış açılarıyla değişik bölümlenmelerin yaratılabilmesidir. Bu bölümlenmeler birleştirilerek daha iyi bir nihai bölümlenme elde etmek veya verinin daha evvelden saklı kalmış bazı özelliklerini keşfetmek mümkündür. Çoklu bölümlenmeler farklı bölümlenme algoritmalarının değişken giriş parametreleri ile koşturulmasıyla elde edilebilir. Alanının uzmanları, özel mülkiyete tabi yöntemler veya dağıtık bir hesaplama ortamı bölümlenmeler sağlayabilir. Veri kümesinin rastlantısal izdüşümleri veya verinin örneklemeleri üzerinde yapılan az maliyetli hesaplamalar da bölümlenmeler sağlayabilir. Diğerleri yanında özellikle Biyobilişim, Bilgisayarlı Görme ve Metin Madenciliği çoklu bölümlenmelerin birleştirilmesi algoritmalarını kullanmaktadır.Bu tez bir literatür taraması sağlamakta ve üç yeni ve verimli yöntem ile çoklu bölümlenmelerin birleştirilmesi araştırmalarına katkıda bulunmaktadır. İlk olarak, bölüt iç uyumu ve ayrılığını veri nesnelerinin bölümlenmelerdeki birlikteliklerine göre ölçen bir hedef fonksiyon, FastFit' in hızlı hesaplanması için yeni ikili bir yöntem önerilmektedir. Bu hesaplama yöntemi hem zaman hem de yer karmaşıklığı açısından verimlidir. İkinci olarak, çizge kuramından klikler kullanılarak çoklu bölümlenmelerin birleştirilmesi için yeni hassas ve ölçeklenebilir bir yöntem olan CLICOM önerilmektedir. CLICOM büyük çizgeler üzerinde çalışan ve kısa zamanda sonuç üreten yeni çıktı duyarlı bir klik bulma algoritması da barındırmaktadır. Son olarak, ikili bir veri kümesinin yaklaşık uzaklık matrisini hesaplamak için bir grup paralel algoritma önerilmektedir. Bu algoritmalar, ortak ve dağıtık bellekli hesaplama ortamlarında, rastlantısal olarak çırpı fonksiyonundan geçirilmiş veri nesnelerinin oluşturduğu zayıf bölümlenmeleri kullanarak uzaklıkları hesaplamaktadır.Önerilen yöntemlerin deneysel sonuçları sentetik ve gerçek veriler üzerinde gösterilmiştir. Yöntemler özellikle verimlilik ve ölçeklenebilirliğin başlıca endişe olduğu büyük verilere uygundur.

Clustering is a semi- or unsupervised process of grouping similar objects together.It is widely used for data understanding and data reduction. Combining Multiple Clusterings is an important research trend in clustering that goes beyond what is typically achieved by a single clustering algorithm. The basic idea is that by taking multiple looks at the same data, one can generate a diverse set of clusterings. By combining these clusterings, it is possible to obtain a better Final Clustering or discover some otherwise hidden aspects of the data set. Multiple clusterings may be produced by running different clustering algorithms with varying input parameters. Domain experts, proprietary methods, or a distributed computing environment may provide clusterings. Computationally cheap operations e.g. on random projections or random samplings of a data set may also provide multiple clusterings. A range of applications in Bioinformatics, Computer Vision, and Text Mining, among others, employ algorithms for combining multiple clusterings.This thesis provides a literature survey and contributes three novel and efficient methods to Combining Multiple Clusterings research. First, we propose a novel binary method for fast computation of an objective function, FastFit, which measures cluster cohesion and separation with respect to object co-associations. This computation method is very efficient in terms of both time and space complexity. Secondly, a novel accurate and scalable consensus method, CLICOM, is proposed to combine multiple clusterings using graph-theoretic cliques. CLICOM employs, as well, a novel output-sensitive clique finding algorithm which works on larger graphs and produces output in a short amount of time. Finally, a set of parallel algorithms is proposed to calculate an approximate distance matrix of a binary data set. These algorithms compute distances by utilizing weak clusterings of randomly hashed objects in shared and distributed memory computing environments.Experimental results of the proposed methods are shown on synthetic and real data sets. The methods are especially suited to large data sets where efficiency and scalability is a major concern.