New cluster ensemble algorithm with automatic cluster number and new pruning technique for fast detection of neighbors on binary data
No Thumbnail Available
Files
Date
2011-06
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Bahçeşehir Üniversitesi Fen Bilimleri Enstitüsü
Abstract
Cluster analysis is to group similar, real or abstract data objects together in an unsupervised
way. Cluster analysis, or clustering is a very important tool for data analysis
and widely-used in almost every scientific field including data mining, machine learning,
bioinformatics, and social network analysis. Unsupervised nature of clustering comes
with unique opportunities and challenges. Applying the optimum clustering algorithm
with correct parameters is not straight forward. Moreover, unlike classification algorithms
which use the provided labels, clustering algorithms extract the information from the data
itself, therefore most of the algorithms suffer from long execution times.
Combining multiple clusterings methods emerge as a promising solution that not only
ease the algorithm and parameter selection for cluster analysis but also solve some unique
clustering problems. In this theses we discuss the methods that combine multiple clusterings
to obtain a better overall clustering of the data, including a recent method: Di-
CLENS. DiCLENS does not take any input arguments and finds the number of clusters
automatically using objective measures. Although finding the co-associations between
objects is a computationally expensive task, it is one of the strongest similarities in the
field. DiCLENS utilizes a recent method to compute the similarities in an efficient way.
Our experiments show that DiCLENS produces a better final clustering at almost all of
the scenarios. Moreover execution time of the DiCLENS is very good compared to other
methods.
We also discuss DBSCAN BV, a novel method that improves the execution time performance
of DBSCAN clustering algorithm by utilizing a pruning method on binary data
and Hamming distance. DBSCAN is a well-known density-based algorithm. Even though
space indexing techniques are widely used with DBSCAN, they do not perform well on
categorical and binary data sets. Extensive tests show that DBSCAN BV works up to
40 times faster than DBSCAN while keeping the same clustering accuracy. Tests also
show that the new pruning method allows the application of DBSCAN to resource limited
environments.
Kümeleme, birbirine benzeyen gerçek ya da soyut nesnelerin denetimsiz bir biçimde bir araya gruplanmasıdır. Küme analizi ya da kümeleme, veri analizi için çok önemli bir araçtır ve veri madenciliği, makina öğrenmesi, bioinformatik ve sosyal ağ analizi de dahil olmak üzere neredeyse bütün bilimsel alanlarda sıklıkla kullanılır. Kümelemenin denetimsiz doğası özgün fırsatlara ve sorunlara neden olur. Doğru kümeleme algoritmasını veriye uyacak parametreler ile uygulamak kolay değildir. Dahası, sağlanan etiketleri kullanan sınıflama algoritmalarının aksine kümeleme algoritmaları bilgiyi verinin kendisinden çıkarttığı için çoğu algoritmanın çalışması uzun sürer. Çoklu kümelemeleri birleştiren metodlar yalnızca algoritma ve parametre seçimini kolaylaştıran değil aynı zamanda bazı özgün kümeleme sorunlarını da çözen, umut vadeden çözümler olarak belirmiştir. Bu tezde daha iyi bir kümeleme elde etmek için eldeki çoklu kümelemeleri birleştiren metodları ve bunlardan biri olan DiCLENS’i gösteriyoruz. Di- CLENS hiç bir argüman almadan çalışır ve nesnel ölçümler kullanarak kümelerin sayısını otomatik olarak bulur. Nesneler arasında es¸-atamaların bulunması fazla hesaplama gerektirse de, eş-atamalar alandaki en güçlü benzerliklerden biridir. DiCLENS benzerlikleri etkin bir biçimde hesaplamak için yeni bir metod kullanmaktadır. Deneylerimiz Di- CLENS’in neredeyse bütün senaryolarda daha iyi bir sonuç kümelemesi ürettiğini göstermiştir. Dahası diğer metodlar ile karşılaştırıldığında DiCLENS’in çalışma zamanı oldukça iyidir. Aynı zamanda, ikili veri ve Hamming uzaklığı üzerinde bir budama yöntemi kullanarak DBSCAN kümeleme algoritmasının çalışma hızı performasını artıran DBSCAN BV’yi de gösteriyoruz. DBSCAN oldukça iyi bilinen bir yoğunluk temelli kümeleme algoritv masıdır. Uzam dizinleme teknikleri DBSCAN ile birlikte yaygın olarak kullanılsa da, bu teknikler kategorik ve ikili veri setlerinde düşük performans gösterirler. Yoğun testler, kümeleme doğruluğu aynı kalmakla birlikte DBSCAN BV’nin DBSCAN’den 40 kata kadar daha hızlı çalıştığını göstermiştir. Testler aynı zamanda yeni budama metodunun DBSCAN’in kaynağı sınırlı olan ortamlarda da kullanımının yolunu açtığını göstermektedir.
Kümeleme, birbirine benzeyen gerçek ya da soyut nesnelerin denetimsiz bir biçimde bir araya gruplanmasıdır. Küme analizi ya da kümeleme, veri analizi için çok önemli bir araçtır ve veri madenciliği, makina öğrenmesi, bioinformatik ve sosyal ağ analizi de dahil olmak üzere neredeyse bütün bilimsel alanlarda sıklıkla kullanılır. Kümelemenin denetimsiz doğası özgün fırsatlara ve sorunlara neden olur. Doğru kümeleme algoritmasını veriye uyacak parametreler ile uygulamak kolay değildir. Dahası, sağlanan etiketleri kullanan sınıflama algoritmalarının aksine kümeleme algoritmaları bilgiyi verinin kendisinden çıkarttığı için çoğu algoritmanın çalışması uzun sürer. Çoklu kümelemeleri birleştiren metodlar yalnızca algoritma ve parametre seçimini kolaylaştıran değil aynı zamanda bazı özgün kümeleme sorunlarını da çözen, umut vadeden çözümler olarak belirmiştir. Bu tezde daha iyi bir kümeleme elde etmek için eldeki çoklu kümelemeleri birleştiren metodları ve bunlardan biri olan DiCLENS’i gösteriyoruz. Di- CLENS hiç bir argüman almadan çalışır ve nesnel ölçümler kullanarak kümelerin sayısını otomatik olarak bulur. Nesneler arasında es¸-atamaların bulunması fazla hesaplama gerektirse de, eş-atamalar alandaki en güçlü benzerliklerden biridir. DiCLENS benzerlikleri etkin bir biçimde hesaplamak için yeni bir metod kullanmaktadır. Deneylerimiz Di- CLENS’in neredeyse bütün senaryolarda daha iyi bir sonuç kümelemesi ürettiğini göstermiştir. Dahası diğer metodlar ile karşılaştırıldığında DiCLENS’in çalışma zamanı oldukça iyidir. Aynı zamanda, ikili veri ve Hamming uzaklığı üzerinde bir budama yöntemi kullanarak DBSCAN kümeleme algoritmasının çalışma hızı performasını artıran DBSCAN BV’yi de gösteriyoruz. DBSCAN oldukça iyi bilinen bir yoğunluk temelli kümeleme algoritv masıdır. Uzam dizinleme teknikleri DBSCAN ile birlikte yaygın olarak kullanılsa da, bu teknikler kategorik ve ikili veri setlerinde düşük performans gösterirler. Yoğun testler, kümeleme doğruluğu aynı kalmakla birlikte DBSCAN BV’nin DBSCAN’den 40 kata kadar daha hızlı çalıştığını göstermiştir. Testler aynı zamanda yeni budama metodunun DBSCAN’in kaynağı sınırlı olan ortamlarda da kullanımının yolunu açtığını göstermektedir.
Description
Keywords
Clustering, Combining multiple clusterings, Clustering ensemble, DBSCAN, DiCLENS, Kümeleme, Çoklu kümelemelerin birleştirilmesi, Kümeleme topluluğu