Geodesic based hybrid similarity criteria for approximate spectral geodesic based hybrid similarity criteria for approximate spectral clustering of large medical data sets

Ö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.