Büyük veri kümelerinin sınıflandırılmasında yaklaşık spektral öbekleme birleşimi yöntemleri

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