Veri Madenciliği: Boyutun Laneti

Bu yazıda “Curse of Dimensionality” olarak bilenen boyutun laneti ve bu laneti bertaraf edebilecek tekniklerden bahsedeceğiz. Sonrasında boyut değil de verinin kendisini nasıl azaltabiliriz bundan bahsedelim.

Curse of Dimensionality – Yüksek Boyut Laneti

Veri analizinde bir çok şeye lanet ederiz aslında ama o lanetlerden en derinden olanı da boyuta gelir. Biz verilerimizi temsil ederken nitelikler belirliyoruz. Diyoruz ki metinleri tek tek kelimeler ile ifade ediyoruz. Resimleri tek tek pikseller ile ifade ediyoruz. Bu durumda nitelikler örneklerden fazlaca olmakta ve bu da bu laneti getirmekte.

20×20 alana el yazısıyla yazılmış sayıları düşünelim. 20×20 alanı temsil edebilmek için toplam 400 piksel olmalı ve bu piksellerin herbiri bir boyuttur. Biraz dikkatli düşünürsek, aslında sayıları 20×20 ‘lik alana el yazısıyla yazmak için 400 pikselin çok az bir kısmını kullanıyoruz. Genelde hep aynı kısımlar beyaz kalıyor. Eğer ki 20×20’lik alan üzerinde random bir resim üretilse soldaki şekil gibi bir şekil elde ederiz, ki random üretilen resimler arasında bir sayı ihtimali oldukça azdır. Aslında 400 pikselin bu 20×20 alanda sayıları temsil etmesi çok da etkili bir kullanım değildir yani verinin bu kadar boyutlu olmasına gerek yoktur.

pca1

Örneğin bir boyutlu ve 3 farklı sınıf içeren veri, 1 boyutlu uzayda ise uzay 3 bölgeye ayrılarak bölgeye düşen veri miktarı ölçülür. 2 boyutlu uzayda ise uzay 9 bölgeye ayrılarak bölgeye düşen veri miktarı ölçülür. 3 boyutlu uzayda 27 bölgeye ayrılarak bölgeye düşen veri miktarı ölçülür. Veri miktarı az ve boyutta yüksek ise çoğu bölgeye hiç veri düşmez. Bir çıkarım da yapılamaz. İşte bu da boyutun lanetidir.

pca2

 

 

 

Curse of Dimensionality ile Başa çıkma yöntemleri:

  1. Verinin konu alanı göz önüne alınarak bazı niteliklerden önemli olanları özellik olarak belirlenebilir ve veriyi temsilen o özellikler (feature) kullanılır.
  2. Boyutlar üzerinde bazı kabuller kurabiliriz.

AMAÇ: Veriyi daha az değişkenle temsil edebilmek tabiki verinin yapısını bozmadan.

İki temel yöntem var:

  1. Özellik Seçme (Feature Selection): verinin sınıfını iyi tahmin eden özellikleri seçmek. Örneğin, Information Gain iyi bir değerdir özellik seçmek için.
  2. Özelik Çıkartma (Feature Extraction): Tamamen yeni bir özellik seti oluşturmak demektir. Bu özellik seti, tüm verilerin bir fonksiyonudur. Özellik seti içerisindeki özelliklerin lineer kombinasyonu diğer verileri elde etmek için kullanılır.

Özellik Seçme (Feature Selection) Teknikleri

  1. Nitelik Altkümesi Seçimi (Attribute Subset Selection): Verilerin dağılımını çok bozmadan genel gereksiz niteliklerin atılmasıdır. İstatistiksel yöntemler kullanılır.
  •  Best-Single Attribute: En iyi nitelik seçilir diğerlerinden bağımsız olarak. Örneğin karar ağacında “önemlilik (significance)” değerine göre information gain hesaplanır ve iyi nitelik olarak alma kararı verilir.
  • Best Step-Wise: Önce en iyi nitelik seçilir. Sonra diğerleri buna bağlı seçilir.Ör: Karar ağacı
  • Setp-wise: tekrarlı olarak en kötü niteliği siler. Ör: Karar ağacı prunning.
  • Diğer bazı heuristic metotlar: Forward Selection, Backward Selection, Decision Tree Induction gibi.

2- Regresyon ve Log-Linear Model: Veriye yaklaşmayı sağlar.

  • Regresyon : Veri düz bir doğru üzerinde modellenir. y= mx+b . m ve b least square method denilen en küçük kareler yöntemi ile bulunur.
  • Log-Lineer
  • Dağınık veride kullanılabilir.
  • Regresyon çarpık veride daha iyi sonuç verir. Fakat fazla boyutlu veride uygulamak pahalidır.

3-  Histogram

  • Eşit aralıklı
  • Eşit sıklıklı yöntemlerini kullanarak veriyi parçalara bölerek ayrıştırır.

4- Kümeleme (Clustering): Kümelenmiş veriler için, küme içinden bir temsilci gerçek veriler yerine kullanılarak boyut azaltımı yapılabilir.

5- Örnekleme (Sampling)

 

Eğer verideki özellikler istatistiksel olarak birbirinden bağımsız ise, özellik seçme yöntemleri ile en az ayırıcı (discriminative) olan özellikler elenerek boyut azaltılabilir. Ama gerçek hayattabu pek de mümkğn değildir, genelde bir özellik birden fazla değişkene bağlı olabilir ve onlardan birinin elenmesi, ciddi veri kaybına neden olabilir. Buna çözüm olarak verilerin yapısını bozmadan özellik çıkartma teknikleri tercih edilebilir.

Özellik Çıkartma (Feature Extraction) Teknikleri – Boyut Azaltma (Dimensionality Reduction) Teknikleri

  1. Wavelet Transformation : Wavelet transformation X vektörünü alır Wavelet baş katsayıları ile sayısal olarak başka bir vektöre dönüştürür. Vektörün güçlü olan Wavelet katsayılarını içeren kısmı alınıp diğerleri atılabilir, böylece boyut azaltılabilir.
  2. Principle Component Analysis (PCA): n boyutlu veri içinde k <n olacak şekilde ortagonal vektorler arar ve bunları veriyi temsil etmek için kullanır. Diğer vektörler ortagonal vektörlerin lineer kombinasyonu şekilde yazılabileceğinden bu vektorlere “temel bileşen (principle components)” denir. Bu komponentler önem sırasına göre sıralanıp, en zayıf olanlardan elenerek boyut azaltımına gidilebililir. Önem sırası, verinin vektörler üzerine izdüşümünün varyansı göz önüne alınarak bulunur. Varyans ne kadar yüksekse vektör o kadar güçlüdür. Kovaryans matrisi PCA bulmak için kullanılır. Kovaryans’ın anlamı: iki değişkenin birlikte ne kadar değiştiğinin ölçümüdür. Kovaryans matrisi ile verideki herhangi bir vektörü çarptığımızda, belli bir vektöre doğru yakınlaşır ve belli bir noktadan sonra sabit kalır. İşte o yakınlaşılan vektör aslında veri izdüşümlerinin varyansının en fazla olduğu vektördür, bu bir eigenvektördür. Eigendeğeri en yüksek olan vektör PCA’lardan bir tanesidir. det(E-&I)=0  ile eigendegerler (&) bulunur. Ee=&e ‘den ile de e (eigenvektor) bulunur. Eigenvektörler bulunduktan sonra veriyi bu vektörler üzerine izdüşümünü alınır. Eigendegerler, baglı oldugu eigenvektorlerin varyansın ne kadarını açıkladığının büyüklüğüdür. en büyük eigendegere sahip olan ilk m Eigenvektor, total varyansın %…sını acıklayacak şekilde şeçilir. (genelde %90 veya %95).

PCA yöntemi

  • Sıralı veya sırasız veriye uygulanabilir.
  • Dağınık ve çarpık veride kullanılabilir.
  • Dağınık veri de Wavelet yönteminden daha iyidir.

Yöntemi kısaca tekrar edersek: Birbiriyle ilişkili (correlated hi-data) var diyelim. Bu veri origin’e çekilir. (0,0) noktası orta noktası olacak şekilde. Varyansın en yüksek olduğu boyut bulunur. Burdan kovaryans matrisi bulunur ve bunun yardımıyla eigendeger ve vektorler bulunur. varyansı belirlenen kesim noktası (threshold) kadar açıklayacak ilk m eigenvektor seçilir. Bu eigenvektörler üzerine verinin izdüşümüm alınır. böylece veri daha az boyutlu veri haline gelmiş olur.
pca_example

pca

 

 

 

 

 

 

 

 

 

 

PCpca4A dağılımların lineer düzlemlerde olduğunu varsayar. Non-linear dağılımlarda başarılı olamaz. Veri düz bir çizgi boyunca ve ya bir düzlem boyunca dağılmıyor ise, PCA çalışmaz.

 Sınıflandırma için PCA ve LDA (Linear Discriminant Analysis)

PCpca5A sınıf etiketini göz önüne almaz. Veriyi daha fazla temsil edebilmek için varyans çok olacak şekilde boyutunu azaltmaya çalışır. Başka bir doğru üzerine izdüşüm alındığında sınıfları ayrıştırmak daha kolay olabilir. Bu yönteme de LDA (Linear Disciriminant Analysis) denir. Mantık olarak çok PCA ile benzerdir. Öyle bir doğru bulunur ki iz düşümdeki sınıf ayrımı en yüksek olur. Sınıflandırmayı kolaylaştıracak şekilde veri boyutunu düşürmeye çalışır. Yandaki resimde kırmızı çizgi üzerine olan izdüşüm sınıfların ayırımı kolaylaştırmıştır.

pca6Ortalamaları farklı olan sınıflar için yukardaki şekil gibi izdüşümde ayrılma gerçekleşebilir. Fakat varyanları farklı ise LDA iyi sonuç veremez. Yani ortalamaları aynı olan iki farklı sınıf verileri için LDA doğrusu sınıflandırma için yardımcı olmaz. PCA daha iyi sonuç verir.  Ayrıca LDA dağılımları normal dağılım olarak varsayar.

Kaynaklar:

http://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/

258,621 total views, 398 views today

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir