Aggregating advantages of a set of clusterings into a final clustering using object-wise similarity graph

Abstract

Clustering is the process of grouping objects that are similar, where similarity between objects is usually measured by a distance metric. Clustering is a hard problem since the natural grouping of a data set is unknown. Clustering aims to divide a data set into meaningful groups where each group formed by a clustering method is referred as a cluster. Clustering is a useful starting point for different purposes such as data understanding and summarization. In the literature, there are numerous applications of clustering ranging from biology to economics. Clustering has a long and rich history in a variety of scientific fields. Themain contributing research areas to clusteringmethodology areMachine Learning, DataMining, and Pattern Recognition. Each clustering technique possess some advantages and disadvantages. Some clustering algorithms may even require input parameters which strongly affect the outcome. Some clustering techniques make some assumptions about the properties of the data sets and good quality clusterings are obtained, when the assumption holds. Distance metric also plays an important role in the process of producing a clustering. Especially in high dimensional data sets, it is hard to identify similarity or distance between objects. In most cases, it is not possible to choose the best distance metric, the best clustering method, and the best input parameter values for an input data set. Therefore, multiple clusterings can be obtained on a data set. And, multiple clusterings can be combined into a new and better quality final clustering. In this thesis, we propose a graph based combining multiple clusterings algorithm that is scalable, robust, and intuitive. Combiningmultiple clusterings requires reusing preexisting knowledge and producing a novel final clustering having better overall quality. Our new algorithm, COMUSA, works on an object-wise weighted similarity graph which is constructed by using the evidence accumulated from multiple input clusterings. COMUSA offers good quality final clusterings by working at object level in a short amount of time. Extensive experimental evaluations on some very challenging real, synthetically generated and gene expression data sets from a diverse set of domains establish the usefulness of our methods in terms of both quality and execution time.Kümelenme benzer nesnelerin gruplanması sürecidir, objeler arası benzerlik genellikle bir uzaklık ölçütü ile ölçülür. Kümelenme, veri kümesinin gerçek gruplanması bilinmediği için zor bir problemdir. Kümelenme, verileri anlamlı gruplara bölmeyi amaçlar ve bir kümelenme metoduyla oluşturulmuş grup küme olarak adlandırılır. Kümelenme, verilerin anlaşılması ve özetlenmesi gibi farklı amaçlar için yararlı bir başlangıç noktasıdır. Literatürde kümelenme, biyolojiden ekonomiye kadar çeşitli uygulamalara sahiptir. Kümelenme, çeşitli bilimsel alanlarda uzun ve zengin bir geçmişe sahiptir. Kümelenme metodolojisine katkıda bulunan temel alanlar Makine Öğrenmesi, Veri Madenciliği ve Örüntü Tanımadır. Herbir kümelenme tekniği bazı avantajlar ve dezavantajlar sergiler. Bazı kümelenme algoritmaları sonucu fazlasıyla etkileyecek girdi parametrelerine bile ihtiyaç duyabilirler. Bazı kümeleme teknikleri veri kümesinin özellikleri ile ilgili kabullenmeler yapabilir ve iyi kalitede bir kümelenme yalnızca bu kabullenmeler sağlandığında beklenebilir. Uzaklık ölçütü de kümeleme oluşturma sürecinde önemli bir rol oynar. Özellikle yüksek boyutlu veri kümelerinde nesneler arası benzerliği veya uzaklığı tanımlamak zordur. Bir çok durumda bir girdi veri kümesi için, en iyi uzaklık ölçütünü en iyi kümeleme metodunu ve en iyi girdi argümanlarını seçmek mümkün değildir. Bu yüzden, bir veri kümesi için çoklu kümelemeler elde edilebilir. Ve, çoklu kümelemeler yeni ve daha iyi kaliteye sahip bir sonuç kümelemesinde birleştirilebilir. Bu tezde, çoklu kümelemelerin birleştirilmesi için çizge tabanlı, ölçeklenebilir, güçlü ve sezgisel bir algoritma öneriyoruz. Çoklu kümelemelerin birleştirilmesi, önceki bilgilerin tekrar kullanılmasını ve daha iyi kaliteye sahip yeni bir sonuç kümelemesi oluşturulmasını gerektirir. Yeni algoritmamız, COMUSA, nesnelerden oluşan, ağırlıklı ve girdi kümelenmelerindeki kanıt biriktirilerek oluşturulmuş bir benzerlik çizgesi üzerinde çalışır. COMUSA nesneler seviyesinde çalışarak, kısa bir sürede iyi kaliteye sahip sonuç kümelemesi oluşturmayı önerir. Çok çeşitli alanlardan alınmış gerçek, sanal olarak üretilmiş ve gen ifade eden zorlayıcı veri kümeleri ¨üzerindeki geniş deneysel sonuçlar metodumuzun hem kalite hem de çalışma zamanı olarak kullanışlı olduğunu gösterir.