Geodesic Based Hybrid Similarity Criteria For Approximate Spectral Clustering Of Large Medical Datasets

Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2015Thesis (M.Sc.) -- İstanbul Technical University, Instıtute of Science and Technology, 2015Öbekleme, gözlem, veri, özellik vektörü gibi örüntüleri sınıflara ayırmak için kullanılan bir öğreticisiz sınıflandırma yöntemidir. Karar verme, kestirim gibi noktalarda etkili ve hızlı bir süreç olmasından dolayı medikal alandaki örüntü öbekleme uygulamaları hızla artmaktadır. Örüntülerin farklı yapıları olan, düzenli sınırları ve homojen dağılımları olmayan öbekler içermesi nedeniyle çeşitli öbekleme yöntemleri geliştirilmiştir. Bu yöntemler arasında spektral öbekleme (SÖ) parametrik model kullanmayan bir yöntem olmasından dolayı hem düzensiz şekilli öbekleri bulabilmekte hem de parametrik modellere uymayan gerçek öbekleri bulmada daha başarılı olmaktadır. Spektral öbekleme, veri noktaları arasındaki ikili benzerliklerin özdeğer ayrışması tabanlı bir öğrenme yöntemidir. 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. Veri noktaları arasındaki ikili benzerliklerin öz değer ayrışımı spektral öbeklemenin başarılı bir yöntem olmasını sağlamasına rağmen yüksek hesaplama yükü ve bellek gereksinimi yüzünden büyük veri setlerine doğrudan uygulanması sorun oluşturmaktadır. Bu sorunun çözümü için geliştirilen yaklaşık spektral öbekleme (YSÖ) yöntemleri tüm veri setini kullanmak yerine, azaltılmış veri temsilcileri olarak adlandırılan temsilciler setini kullanır. Bu şekilde hem spektral öbeklemenin büyük veri setlerinde kullanımını mümkün kılar hem de veri setine ait kullanılmayan ve göz ardı edilen çeşitli bilgilerin benzerlik matrisini oluşturmada kullanılmasını sağlar. 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. Bu tezde, literatürde en iyi örnekleme ve nicemleme yöntemleri olarak bilinen seçimli örnekleme ve sinir gazı nicemleme yöntemleri kullanılmıştır. Bunlara ek olarak, k-ortalama yönteminin rastgelelikten kaynaklanan ilk merkez atama sorununu çözmek için geliştirilen k-ortalama++ yöntemi de YSÖ nicemlemesinde ilk kez kullanılmıştır. 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. Veri temsilcisi seçiminde ise şu şekilde kullanılmıştır. İlk olarak belirlenen veri temsilcisi sayısı kadar öbek merkezi olasılık yoğunluk fonksiyonuna göre seçilir. Daha sonra seçilen bu merkezler için k-ortalama algoritması uygulanır. En son elde edilen merkezler veri temsilcileri olur. 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 şekilde elde edilmesi öbekleme performansı açısından oldukça önemlidir. Bunun için çeşitli benzerlik ölçütleri geliştirilmiştir. Geleneksel olarak Öklid tabanlı Gauss kernel benzerlik işlevi kullanılır. Bu işlev global bir ayrıştırma parametresi kullanır ve bu parametrenin en uygun hali her veri seti için deneysel olarak belirlenir. Alternatif olarak yerel ayrıştırma parametresinin kullanılması da mümkündür. Bu yaklaşımlar YSÖ’ nün ortaya çıkardığı veri topolojisi, yerel yoğunluk dağılımı ve veri manifoldu gibi veri setine ait yeni bilgilerin kullanımını göz ardı ederler. Bu çalışmada benzerlik tanımını en doğru şekilde yapabilmek için veriye dair elde edilen bütün bilgilerin kullanılmasını mümkün kılan jeodezik tabanlı hibrit benzerlik ölçütleri önerilmiştir. 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. Çalışma kapsamında önerilen jeodezik tabanlı hibrit benzerlik ölçütleri yaklaşık spektral öbekleme algoritmasının ikinci aşamasında verilerin ikili benzerliklerini gösteren benzerlik matrisinin elde edilmesi için geliştirilmiştir. Jeodezik uzaklık, iki veri temsilcisi arasındaki uzaklığı komşuluk çizgesindeki en kısa mesafe olarak hesaplar ve bu sebeple komşuluk çizgesi kullanımını gerektirir. Bunun için genelde k en yakın komşuluk çizgesi (k-nn) ve ağırlıklandırılmış Delaunay üçgeni (CONN) kullanılır. K-nn çizgesi kullanıcıdan alınan k parametresi ile komşuluk ilişkisini belirler. Burada verilerin komşu olup olmadığı kararı iki şekilde verilir. İlk yöntemde iki veri noktasından herhangi birisi diğerinin k en yakın komşuluğunda ise veriler bağlanır, diğer yöntemde ise iki veri noktasının her ikisi de birbirlerinin k en yakın komşulukları içerisinde olmaları durumunda bağlanırlar. K-nn çizgesi için temel problem k sayısının kullanıcı tarafından belirlenmesidir. Her veri seti için ve hatta her veri temsilcisi için en uygun k değeri farklıdır ve bütün veri noktaları için aynı k sayısında komşu belirlemek komşuluk çizgesinin doğru oluşturulamamasına sebep olur. CONN ise herhangi bir kullanıcı parametresi kullanmadan yerel veri karakteristikleriyle ilişkili olarak en uygun komşu sayısına karar verir. Bu şekilde her veri noktası ve veri seti için farklı sayıda komşu belirleyerek komşuluk çizgesinin daha doğru oluşmasını sağlar. CONN veri karakteristikleriyle ilişkili olarak komşu sayısını belirleyebilmek için veri topolojisi ve yerel yoğunluk dağılımı bilgilerini benzerlik tanımında kullanır. Önerilen jeodezik uzaklık tabanlı benzerlik ölçütlerinde CONN ve k-nn komşuluk çizgeleri kullanılmıştır. Bu çizgeler üzerinden jeodezik uzaklık hesabı içinse Öklid uzaklığı ve yerel yoğunluk dağılımını gösteren CONN uzaklığı kullanılmıştır. Önerilen yöntemler yaklaşık spektral öbeklemenin ortaya çıkardığı bütün bilgileri komşuluk çizgesi ve uzaklık hesaplarıyla kullanarak daha iyi bir benzerlik sunumu elde edilmesini sağlamıştır. Önerilen yöntemlerin öbekleme performansı deneysel olarak değerlendirilmiştir. Öncelikle bu yöntemin avantajlarını göstermek için farklı öbekleme problemlerine sahip üç yapay veriseti (Lsun, Chainlink ve Wingnut) kullanılmış daha sonra UCI Machine Learning Repository’den alınan ve medikal veri setlerini de içeren on veri seti üzerinde önerilen yöntemlerin klasik Öklid tabanlı benzerlikten daha iyi olduğu gösterilmiştir. Son olarak MICCAI 2012 çok modelli beyin tümörü bölütleme yarışmasında kullanılan 4 adet beyin MR görüntüleri seti kullanılmış ve herhangi bir öğreticili yöntem kullanmadan % 80.06 ortalama başarı elde edilmiştir. Bu başarı geleneksel yöntemlerle elde edilen başarılardan daha iyidir ( k-ortalama başarısı: % 66.55 ve Öklid uzaklığı kullanan benzerlik tabanlı YSÖ başarısı: % 76.52 ). Performans değerlendirmesi sonucunda önerilen jeodezik uzaklık tabanlı hibrit benzerlik ölçütlerinin hem küçük/ orta hem de büyük veri setlerinde başarılı bir yaklaşım olduğu görülmüştür.Clustering is the unsupervised classification to group patterns such as data, observations or feature vectors. Due to its extraction of clusters in a fast manner without supervised information, many different methods have been proposed in various applications. Among them, spectral clustering (SC) has been recently popular and successfully used in various areas such as image processing, computer vision and information retrieval, thanks to its ability to find irregularly shaped clusters and its independence from parametric cluster models. Spectral clustering is a manifold learning algorithm based on eigendecomposition of a graph Laplacian matrix constructed from pairwise similarities of the data points. Although this eigendecomposition produces higher clustering accuracies than the accuracies obtained by traditional methods, it has high computational cost and memory requirement which makes direct use of spectral clustering infeasible for clustering large datasets. To address this challenge, approximate spectral clustering (ASC) methods, which apply spectral clustering on a reduced set of data points (data representatives) selected by sampling or quantization, have been proposed. The ASC not only makes spectral clustering feasible for large datasets but also enables new information types to be used in similarity definition. In this thesis, data representatives are obtained by selective sampling and neural gas as sampling and quantization method respectively because of being the best methods in the literature for sampling and quantization. In addition, k-means++, a clustering algorithm which solves random initialization problem of k-means, is first used to obtain data representatives as a quantization method for ASC. In order to achieve high clustering accuracies with ASC, an important step is to determine the criterion to define the pairwise similarities of the selected data representatives. Traditionally, an Euclidean distance based Gaussian kernel with a global decay parameter (optimally set by experiments) is used. Alternatively local decay parameters are also used. However, this approach ignores new information types such as data topology, local density distribution and data manifold which are provided by ASC. To utilize all the available information for accurate similarity definition, geodesic based hybrid similarity criteria are proposed in this study. The geodesic distance between any two data representatives is their shortest path distance depending on a neighborhood graph. In addition to commonly used k-nearest neighbor graph, which requires a user-set parameter k, a weighted Delaunay triangulation (CONN) is employed to determine the optimal number of neighbors with respect to local data characteristics without any user-set parameter. CONN also indicates data topology and detailed local density distribution to be used in similarity definition. Based on these neighborhood graphs, the proposed geodesic distance based similarities are defined using Euclidean distance, local density distribution by CONN, and their fused approach. Therefore, these proposed similarity criteria represent better pairwise similarities because they use different combination of all available information for ASC. The clustering performance of the proposed criteria is evaluated by an extensive experimental study. Their advantages are first shown on three artificial datasets with different clustering challenges. Then, they are shown more successful than the commonly used Euclidean based similarity, using ten datasets (including medical data as well) from UCI Machine Learning Repository. Finally the proposed geodesic hybrid similarity criteria based ASC is applied on four sets of brain MR images obtained from MICCAI 2012 challenge on multi-modal brain tumor segmentation, achieving an accuracy of up to 80.06% without any supervised information. This accuracy is much successful than traditional clustering methods (compared to 66.55% obtained by k-means and compared to 76.52% obtained by ASC based on similarity using Euclidean distance) and very close to supervised accuracies existing in the literature. The extensive experiments show the outperformance of the proposed criteria and favor them as a successful approach in clustering both large and small/medium datasets.Yüksek LisansM.Sc