Büyük Veri Kümelerinin Sınıflandırılmasında Yaklaşık Spektral Öbekleme Birleşimi Yöntemleri

Abstract

Öbekleme, eğitmensiz bir yöntem olarak, herhangi veri sınıflandırmasında veya verinin gerçek öbeklerinin bulunmasında kullanılmaktadır. Örneğin, gözlem, veri, özellik vektörü gibi örüntüleri sınıflara ayırmak için bilinen yöntemdir. Eğitmensiz özelliği sayesinde, özellikle büyük veri setlerinden bilgi ediniminde yaygın bir araçtır. Örüntülerin farklı yapıları olan, düzenli sınırları ve homojen dağılımları olmayan öbekler içermesi nedeniyle, öbekleme için bir çok farklı algoritmalar ve çözümler geliştirilmiştir. Çok başarılı ve tutulan öbekleme algoritmalarından biri spektral öbekleme (SÖ) dir. SÖ, veri örneklerinin ikili benzerliklerinden elde edilen Laplace matrisinin özvektör ayrışımına dayalı, veri manifold öğrenme yaklaşımıdır. Veri noktaları bu ikili benzerliklerine göre aynı veya farklı öbeklere atanırlar. Bu şekilde öbek içi benzerlik en yüksek, öbekler arası benzerlik ise en düşük hale getirilmeye çalışılır. Öbeklere ayırma işlemi verilerin benzerliğine göre yapıldığı için kullanılan benzerlik ölçütleri büyük önem taşımaktadır. Veriler arası benzerlik ne kadar iyi olursa öbekleme başarısı o kadar iyi olacaktır. Farklı nitelikte olan öbekleri bulabilme becerisi, kolay uygulanabilirlik ve parametrik modele dayanmaması, SÖ için büyük avantajlar sağlamaktadır. Bu nedenle SÖ bir çok alanda, örneğin görüntü işleme, bilgisayarda görü ve bilgi geri çatılım gibi alanlarda yaygın kullanılmaktadır. Özvektör ayrışım aşaması, SÖ için daha başarılı ve kesin sonuçlar üretmekteyken, hesaplama ve bellek kullanımı yükünden dolayı, SÖ’nin büyük veri setlerinde doğrudan kullanımını imkansız hale getirir. Bu sorunu çözmek için, büyük veri setlerinde SÖ doğrudan değil, ister örnekleme ister nicemleme ile, veriden elde edilmiş temsilciler üzerinde uygulanır. Buna yaklaşık spektral öbekleme (YSÖ) denir. Yaklaşık spektral öbekleme iki aşamalı bir yöntemdir. İlk aşamasında çeşitli örnekleme veya nicemleme yöntemleriyle veri temsilcileri elde edilirler. Örnekleme yöntemleri veri setinde var olan veri noktalarının bir kısmını veri temsilcileri olarak seçerken, nicemleme yöntemlerinde veri temsilcileri esasında veri setinde var olmayan yeni noktaları oluşturarak elde edilirler. YSÖ, büyük veriler için SÖ’nin kullanımını sağlaması yanında, temsilcilerin taşıdığı bazı bilgileri, ikili benzerlik matrisinin elde edilmesinde kullanmasına imkan sağlar. Bu bilgiler, yerel yoğunluk dağılımı ve veri topologisidir. YSÖ için, uygun örnekleme/nicemleme (ÖN) ve de benzerlik ölçütleri gerekmektedir. TÜBİTAK 112E195 nolu projeyle desteklenen bu çalışmada, seçimli örnekleme, k-means++ ve sinir gazı nicemleme yöntemleri ÖN algoritmaları olarak kullanılmıştır. Bu algoritmalar son zamanlardaki YSÖ çalışmalarında en başarılı ÖN yöntemleri olarak gösterilmiştir. Seçimli örnekleme, ilk olarak veri setini kullanıcının belirlediği sayıda alt öbeğe ayırır (alt öbek sayısı genelde var olan öbek sayısının üç katı olarak seçilir). Bu ayırma işlemi için ilk önce alt öbek sayısı kadar öbek merkezi en uzak en yakın uzaklık algoritmasıyla seçilir. Tüm veri noktaları için öklid uzaklığı kullanılarak en yakın öbek bulunur ve veri noktası alt öbeğe atanır. Bu şekilde bütün alt öbekler oluşturulduktan sonra her öbekten öbek büyüklüğüyle orantılı olarak veri temsilcileri seçilir. Böylece hem veri setindeki bütün öbeklerden veri temsilcisi seçilmesi sağlanmış hem de veri temsilcilerinin büyük öbekten daha çok küçük öbekten daha az sayıda olacak şekilde dengeli seçilmesi sağlanmış olur. Sinir gazı ise yinelemeli ve sinir öğrenmesi tabanlı bir nicemleme yöntemidir. Bütün veri noktaları için en iyi eşleşen sinir birimi bulunur ve güncellenerek en uygun hale getirilir. Veri temsilcileri olarak sinir birimleri kullanılır. Bu çalışmada kullanılan diğer nicemleme yöntemi k-ortalama++ ise k-ortalama öbekleme algoritması gibi çalışır, tek fark ilk merkezlerini bir olasılık yoğunluk fonksiyonuna göre seçmesidir. Yaklaşık spektral öbeklemenin ikinci aşamasında ise veri temsilcileri üzerinden spektral öbekleme yapılır ve veri temsilcileri ile ilişkili olarak tüm veri noktaları için öbek etiketleri bulunur. Spektral öbekleme yapılırken çeşitli benzerlik ölçütleri kullanılarak veri temsilcilerinin (veri noktaları) ikili benzerliklerini gösteren benzerlik matrisi elde edilir. Bu matrisin veriler arası benzerliği en iyi ifade edecek sekilde elde edilmesi öbekleme performansı açısından oldukça önemlidir. Temsilcilerin sağladığı tüm bilgilerden yararlanmamız için, bu çalışmada çeşitli benzerlik ölçütleri, örneğin Öklit uzaklık, yerel yoğunluk dağılımı bilgisi, jeodezik uzaklık ve bunları harmanlayarak elde edilen hibrit ölçütler kullanılmıştır. Benzerlik ölçütleri kullanılarak benzerlik matrisi oluşturulduktan sonra bu matris üzerinden öz değer ayrışımı yapılır ve k öbek sayısı için en büyük k öz değerle ilişkili öz vektör bulunur ve bu şekilde veri temsilcilerinin k öz vektörle gösterildiği matris elde edilir. Bu matris üzerinden basit bir öbekleme algoritması (k-ortalama gibi) kullanılarak veri temsilcileri k öbeğe ayrılır. Veri noktaları kendilerini temsil eden veri temsilcilerinin bulunduğu öbeğe atanırlar ve bu şekilde tüm veri seti için öbekleme işlemi gerçekleştirilmiş olur. Kullanılmış ÖN algoritması ve benzerlik ölçütüne bağlı, bir veri için elde edilen öbekleme sonuçları değişiklik göstermektedir. Bunun nedeni her yöntemin ve benzerlik ölçütünün, farklı izlemi ve bilgileri kullanmasıdır. Ayrıca, YSÖ’nin temeli olan SÖ algoritmasında ve ÖN yöntemlerinde de bulunan rassallık, farklı sonuçlara neden olabilir. Bazen bir algoritma ve yöntem için, değerlendirilmesi ve öğrenilmesi gereken parametreler de olabilir. Bu parametreler için deneysel uygulamalarla en uygun değer ya da değerlerin bulunması gerekir. Bu gibi sorunları ortadan kaldırmak, en uygun yöntem ve parametre değerlerini bulmak veya karar vermekten kurtulmak ve elde olan tüm yöntemler ve algoritmaların avantajlarından yararlanmak için, bu çalışmada YSÖ için farklı iki öbekleme birleşim yöntemleri öneriyoruz. İlk yöntem, elde edilmiş çeşitli öbeklerin, yaygın yöntem olan oy çokluğu ile birleştirilmesidir. Bu yöntem farkılı öbek etiketlerinden her veri örneği için, oy çokluğu kavramın izleyerek, o veri örneğin en çok atanmış olduğu sınıfa atıyor. Kolay uygulanması, düşük hesaplama yükü ve güçlü sonuçlar üretme becerisi, bu yöntemin en büyük avantajlarıdır. Alternatif olarak, iki aşamalı matris tabanlı bir birleşim yöntemi olarak tasarlanan ikinci yöntem de amaç, farklı sınıf etiketlerinden yola çıkarak, temsilciler arası yeni bir benzerlik matrisi oluşturup SÖ yi tekrarlamaktır. Bu süreçte, iki temsilci arası birleşim aşamasındaki benzerlik, tüm sonuçlarda o iki temsilcinin kaç defa aynı sınıfa atanmasıdır. Sonra bu matrisi normalize edip, tekrar SÖ uygulanır. Bu yöntem de kolay uygulanabilir, temsilciler seviyesinde uygulandığı için düşük hesaplama yükü ve daha dürüst sonçlara sahiptir. Önerilen birleşim yöntemleri ile, uygun ÖN ve benzerlik ölçütüne karar sorunundan kurtulmaktan ziyade, tüm avantajları bir araya getirerek daha kesin sonuçlar üretebildik. Birleşimden elde edilen tek ve variyans olmayan daha az hatalı bir sonuçtur. Önerilen yöntemleri uygulama ve sınamak için, çeşitli veri kümeleri kullandık. Üç farklı yapay veri seti, UCI makine öğrenme kaynağından beş veri seti, altı tane farklı nitelikteki biyomedikal veri kümesi ve dört uzaktan algılama görüntüsü kullandık. Bu veri setleri küçük, orta ve çok büyük veri setleri olarak, yöntemlerin her boyutta sınaması için seçildi. Buna ilave, bu veri setleri farklı alanlar ve kullanımlara ait oldukları için, çeşitli niteliklere sahip verilerdir ve yine yöntemlerin farklı alanlarda başarı ölçümünü sağlıyor. ÖN tabanlı YSÖ ile farklı benzerlik ölçütleri kullanarak her veri setinden çeşitli öbekler elde ettik ve elde edilen öbekleri önerilen birleşim yöntemleri ile birleştirdik. Tüm yöntemlerin sonuçlarını ve onların birleşiminden elde edilen sonuçların başarısını, doğruluk (accuracy), öbek geçerlilik kriterleri (cluster validity indice) ve ARI (adjusted rand index) ölçütü ile değerlendirdik. Başarı ölçütlerinin değerlendirmesi, nicemleme tabanlı YSÖ’nin örnekleme tabanlı YSÖ den daha başarılı ama daha hesaplama yüklü olduğunu gösterir. Buna ilave olarak, yeni geliştirilmiş jeodezik tabanlı benzerlik ölçütlerinin YSÖ de üstün başarısı ve de önerilen birleşim yöntemleriyle ek başarı artışı gösterilmiştir.

Clustering as an unsupervised approach is used to group or extract the natural taxonomy (clusters) of any data or entities. Thanks to its unsupervised nature, it is popular in knowledge extraction from large datasets. Various methods of clustering have been proposed in different fields. Among them, spectral clustering (SC) is one of the most favored and successful algorithms. SC is a manifold learning method based on eigendecomposition of graph Laplacian matrix constructed from pairwise similarities of data samples. It has advantages such as, significant ability in extracting irregularly shaped clusters, nonparametric modality and easy implementation. Therefore SC is commonly used in various areas such as image processing, computer vision and information retrieval. Although the eigendecomposition stage produces more accurate results, it causes high computational and memory costs which make the direct use of SC infeasible for large datasets. To address this challenge, approximate spectral clustering (ASC), which applies spectral clustering on a reduced set of data points (data representatives) selected either by sampling or quantization (SOVQ), has been proposed. The ASC not only makes spectral clustering feasible for large datasets but also provides some useful information like local density distribution of data points around representatives and sub-manifolds information to measure the similarity between representatives. However, ASC requires selection of sampling/quantization (SOVQ) methods together with an optimal similarity definition. In this study (supported by TUBITAK career grant no 112E195) we use selective sampling as sampling method, k-means++ and neural gas as quantization methods to obtain the representatives, since these methods outperformed other approaches for ASC in recent works. To utilize all available information for accurate similarity definition, this study uses various similarity measures such as Euclidean distance, local density distribution, geodesic distance and their hybrid variants. Based on SOVQ method or similarity criteria, the resulting clusters may differ since each method utilizes a different information. In addition, randomness in SOVQ and SC may also produce different partitionings. Moreover, these methods have parameters which must be set optimally through experiments. To adress these challenges we propose ensemble methods which merge the advantages of all methods. In this study, we propose two ensemble algorithms for ASC. The first method is to use the traditional majority voting among all ASC partitionings. Alternatively the second approach is a two-level graph based ensemble depending on similarity matrix which is defined by the number of samples extracted in the same clusters among all partitionings. We use three artificial benchmark datasets with five datasets from the UCI machine-learning repository, six medical datasets consisting of several diseases, patients’ data and brain tumor images, as well as four remote sensing images for performance evaluation. We applied the SOVQ based ASC with various similarity criteria on these datasets. Then we merged all individual results with our proposed ensemble methods to reach a consensus and optimal clustering. We evaluated the individual and ensemble results by accuracy, cluster validity indices (CVI) and adjusted rand index (ARI). Thanks to exploitation of all possible information types, ensemble of clustering results demonstrates considerable improvement on accuracy while removing the need of selection the optimum similarity criterion or related parameters.