Geçtiğimiz makalelerimde
Metin Madenciliğinin temellerinden bahsetmiş, joker yöntemi denilen ve Türkçe
metinlerde uygulanabilecek olan bir ön işleme yönteminden bahsetmiştim.
Bu makalemizde
ise Metin Sınıflandırma algoritmalarından KNN algoritmasını inceleyeceğiz.
K-NN Algoritması
K en yakın
komşuluk algoritması sorgu vektörünün en yakın k komşuluktaki vektör ile sınıflandırılmasının
bir sonucu olan denetlemeli öğrenme algoritmasıdır. Bu algoritma ile yeni bir
vektörü sınıflandırabilmek için doküman vektörü ve eğitim dokümanları vektörleri
kullanılır. Bir sorgu örneği verilir, bu sorgu noktasına en yakın k tane eğitim
noktası bulunur. Sınıflandırma ise bu k tane nesnenin en fazla olanı ile yapılır.
K en yakın komşuluk uygulaması yeni sorgu örneğinin sınıflandırmak için kullanılan
bir komşuluk sınıflandırma algoritmasıdır.
K en yakın komşuluk
algoritması çok kolaydır. K en yakın komşulukları bulmak için sorgu örneği ile
eğitim dokümanları arasındaki en küçük uzaklıklar dikkate alınır. En yakın komşuları
bulduktan sonra bu komşulardan kategorisi en çok olanın kategorisi dokümanın
kategorisini tahmin etmekte kullanılır.
Avantajları
-Uygulanabilirliği
basit bir algoritmadır.
-Gürültülü
eğitim dokümanlarına karşı dirençlidir.
-Eğitim dokümanları
sayısı fazla ise etkilidir.
Dezavantajları
-K parametreye
ihtiyaç duyar.
-Uzaklık
bazlı öğrenme algoritması, en iyi sonuçları elde etmek için, hangi uzaklık tipinin
ve hangi niteliğin kullanılacağı konusunda açık değildir.
-Hesaplama
maliyeti gerçekten çok yüksektir çünkü her bir sorgu örneğinin tüm eğitim örneklerine
olan uzaklığını hesaplamak gerekmektedir. Bazı indeksleme metodları ile (örneğin
K-D ağacı), bu maliyet azaltılabilir.
-En yakın
komşuluk prensibine dayanır. Tüm dokümanlar vektörel olarak temsil edilir. Sorgu
dokümanı ile diğer dokümanlar arasındaki cosinüs benzerliği hesaplanır. Similarty
oranı 1’e en yakın olan n tane vektörün kategorisinden çok olanı dokümana atanır.
wij terimin doküman
içerisindeki ağırlığı, di eğitim dokümanı vektörüdür. q ise kategorisi bulunması
istenen vektördür.
sim(d,q)=1 =>
d=q
sim(d,q)=0 ise
terim paylaşımı yoktur.
Tüm dokümanlar
ve kategorisi bulunması istenen doküman önceki makalelerde açıklanan kurallar
doğrultusunda vektörel olarak ifade edilirler. Her bir boyut aslında kelimelere
karşılık gelmektedir.
Vektör uzay modelinde dokümanların gösterimi
Burada d1, d2 ve d3 eğitim dokümanlarımızdan oluşan vektörler, q ise sınıfını
bulmak istediğimiz vektördür.
K-NN
algoritmasında terim ağırlıklandırma için 3 çeşit yöntem kullanılabilir.
1-Bit
2-Frekans
3-Tf-IDF
1-K-NN Algoritması
Bit Ağırlıklandırma Yöntemi
Bu yöntemde vektörün ağırlıkları dokümanda bulunma veya bulunmamasına
göre belirlenir. Yani bir kelimenin bir dokümanda 2 kere bulunması ağırlığını
değiştirmeyecektir. Kelimenin dokümanda olması 1, olmaması 0 ile ifade edilmelidir.
Sözlükteki her bir kelime (Kelimeler tablosu) için dokümanda geçip geçmediği
kontrol edilir, ağırlıklar bulunur.
Vektörü
Bitsel İfadenin Sözde Kodu
For i=0 to
TumKelimeler.Count-1
‘Sözlükteki her bir kelimeye bakılıyor ve sırasıyla dokümanımızdan oluşturduğumuz
kelime dizisi ile karşılaştırılıyor
for j=0 to DokumandakiKelimeler.count-1
if TumKelimeler(i)=DokumandakiKelimeler(j) “Dökümandaki kelimeleri bir diziye
attığımızı düşünelim.
‘İlgili i boyutunu 1’e eşitle, 2.döngüden çık 1’e devam et.
Else
‘Sözlükteki kelimemize eşit değilse bir de o kelimemizin jokerlerine bakalım.
For k=0 to Jokerler(i).Count-1
İf Jokeler(i)=Dokumandakikelimeler(j)
‘İlgili i boyutunu 1’e eşitle
exit for
endif
Next
Next
Next
Ön işleme aşamasında
eğitim vektörlerimizi ve sorgu vektörünü ağırlıklandırmıştık. Önceki makalede
kullandığımız eğitim dokümanlarını kullanarak bit ağırlıklandırma yöntemi ile
kelimelerin dokümanda geçip geçmediğine göre vektörler aşağıdaki gibi oluşturulmalıdır.
D1=(0,1,0,1,0,0)
D2=(0,0,0,1,0,0)
D3=(1,0,0,0,0,0)
D4=(0,0,0,0,0,1)
D5=(0,0,1,0,0,0)
D6=(0,0,0,1,1,0)
DS=(0,0,1,0,1,0)
Bitsel olarak uzayda
ifade ettiğimiz her vektörün sorgu vektörümüze (DS) olan uzaklığını hesaplamalıyız.
Aşağıdaki
eşitlik yardımı ile aşağıdaki değerler hesaplanmalıdır.
sim(d1,q)=0
sim(d2,q)=0
sim(d3,q)=0
sim(d4,q)=0
sim(d5,q)=  =0.707
sim(d6,q)=
=0.5
Similarty’si 1’e
en yakın olanı alacağız. Beş ve altıncı dokümanımız similarty değerleri 1’e
en yakın olan dokümanlarımız oldukları için ve bu dokümanlarımızın kategorileri
spor olduğu için doküman spor kategorisindedir diyebiliriz.
2-K-NN
Algoritması Frekans Ağırlıklandırma Yöntemi
Bu yöntemle vektörlerin
ağırlıkları dokümanda kelimenin bulunma sayısına göre hesaplanır. Örneğin bir
kelime bir dokümanda 2 kere bulunuyorsa ağırlığı 2 alınmalıdır.
Vektörü
Frekans Olarak İfadenin Sözde Kodu
For i=0 to
TumKelimeler.Count-1
‘Sözlükteki her bir kelimeye bakılıyor ve sırasıyla dokümanımızdan oluşturduğumuz
kelime dizisi ile karşılaştırılıyor
for j=0 to DokumandakiKelimeler.count-1
if TumKelimeler(i)=DokumandakiKelimeler(j)
‘İlgili i boyutunu 1 arttır, 2.döngüden çık 1’e devam et.
else
‘Sözlükteki kelimemize eşit değilse bir de o kelimemizin jokerlerine bakalım.
For k=0 to Jokerler(i).Count-1
İf Jokeler(i)=Dokumandakikelimeler(j)
‘İlgili i boyutunu 1 arttır
exit for
endif
Next
‘Jokerlerde varsa boyutu 1 arttırıp 1.döngüden devam edelim.
end if
Next
Next
Ön işleme aşamasında eğitim vektörlerimizi ve sorgu vektörünü ağırlıklandırmıştık.
Önceki makalede kullandığımız eğitim dokümanlarını kullanarak frekans ağırlıklandırma
yöntemi ile kelimelerin dokümanda geçme sayılarına göre vektörler aşağıdaki
gibi oluşturulmalıdır.
D1=(0,2,0,1,0,0)
D2=(0,0,0,1,0,0)
D3=(1,0,0,0,0,0)
D4=(0,0,0,0,0,2)
D5=(0,0,2,0,0,0)
D6=(0,0,0,1,2,0)
DS=(0,0,2,0,1,0)
Tekrarlama frekansını
baz alarak uzayda ifade ettiğimiz her vektörün sorgu vektörümüze olan uzaklığını
hesaplamalıyız.
Eşitlik yardımı
ile aşağıdaki değerler hesaplanmalıdır.
sim(d1,q)=0
sim(d2,q)=0
sim(d3,q)=0
sim(d4,q)=0
sim(d5,q)=
=0.8944
sim(d6,q)=
=0.4
Similarty’si 1’e
en yakın olan dokümanlar üzerinden yorum yapmamız doğru olacağından beş ve altıncı
dokümanlar 1’e en yakın olan dokümanlar oldukları için ve bu dokümanlarımızın
kategorileri spor olduğu için doküman spor kategorisindedir diyebiliriz.
3-K-NN
Algoritması Tf-Idf Ağırlıklandırma Yöntemi
Tf-idf, dokümanları
vektör uzay modelinde tanımlayabilmemiz için kullanılan en önemli ağırlıklandırma
metodlarından biridir. Metin kategorizasyonunda tf-idf ağırlıklandırma metodu
2 önemli öğrenme metodu ile ilişkilidir. Bunlar K-NN ve SVM’dir. Tf-idf ağırlıklandırmasında
her bir dokümandaki kelimelerin frekansı rol oynamaktadır. Böylece dokümanda
daha fazla görülen kelimeler varsa (TF, terim frekansı yüksek) o doküman için
daha değerli olduğu anlaşılır. Ayrıca IDF tüm dokümanlarda seyrek görülen kelimeler
ile ilgili bir ölçü verir. Bu değer tüm eğitim dokümanlarından hesaplanılır.
Bu yüzden eğer bir kelime dokümanlarda sık geçiyorsa doküman için belirleyici
olmadığı düşünülebilir (stop words). Eğer kelime dokümanlarda çok sık geçmiyorsa
o kelimenin o doküman için belirleyici özelliği vardır diyebiliriz. Tf-idf genel
olarak sorgu vektörü ile eğitim dokümanı vektörü arasındaki benzerlik oranını
bulmak için kullanılır. Tf-idf fonksiyonunun çeşitli versiyonları mevcuttur.
tf (Dokümanda bulunan
kelimenin dokümandaki görülme sıklığı)
D (Eğitim dokümanı
sayısı)
dft (Dokuman Frekansı(Kaç
eğitim dokümanında ilgili kelime geçmiş))
Sistemimizde eğitim
dokümanlarımızın tf-idf ağırlıkları eğitim dokümanları sisteme eklendikten sonra
oluşturulmalı ve bir tabloda ya da text dökümanında tutulmalıdır. (Run time
sırasında bu hesaplamaları yaptırmak performans kaybına yol açar) Programın
çalışması esnasında tf-idf ile yapılabilecek bir kategorilendirme işlemindeki
sorgu vektörünün ağırlığı ise programın çalışma zamanında hesaplanır.
Tüm bu ağırlıklandırma
formüllerinden biri kullanılarak ağırlıklar belirlenir. Similarty formülünden
hesaplamalar yapılır. Similartysi 1’e en yakın olan n tane vektörün kategorisinden
çok olanın kategorisi dokümana atanır.
Önceki makalede
kullandığımız eğitim dokümanlarını kullanarak tf-idf ağırlıklandırma yöntemine
örnek vermek gerekirse öncelikle dokümanların frekans vektörleri bulunur.
D1=(0,2,0,1,0,0)
D2=(0,0,0,1,0,0)
D3=(1,0,0,0,0,0)
D4=(0,0,0,0,0,2)
D5=(0,0,2,0,0,0)
D6=(0,0,0,1,2,0)
DS=(0,0,2,0,1,0)
Şimdi D1 dokümanının
tf-idf ağırlığını hesaplayalım (Örnek olarak 2. kelimenin (grip) ağırlığını
bulalım).
Tf(grip)=2
D=6
dft=1
IDF=log(D/dft)=log(6/1)=0.778
Eşitlik yardımı
ile tf-idf değeri aşağıdaki incelikte hesaplanabilir.
Tf*IDF=2*0,778=1,556
W1=(..,1.556,...)
Böylece grip boyutunun
D1 dokümanındaki ağırlığını bulmuş olduk. Benzer şekilde diğer ağırlıkları da
hesaplayıp vektörün tüm eksenleri için ağırlıklar bulunur. Tüm dokümanlar için
bu işlem yapılır. Her doküman sorgu ile karşılaştırılır. Similarity’si 1’e en
yakın olan dokümanlardan n tanesinden en çok olanının kategorisi sorgu dokümanının
kategorisine atanır.
NOT:
Sözlükteki kelime ile dökümandaki kelimeler karşılaştırılırken joker mantığına
dikkat edilmelidir. Örneğin sözlüğümüzde “tarım*” olarak geçen bir kelime ile
doküman dizimizdeki “tarımdaki*” kelimesi karşılaştırılırken aynı kelimeymiş gibi
işlem yapılmalıdır. Algoritmaya bu aşamada gerekli kodlar eklenmelidir.
NOT:
Sisteme yeni bir eğitim dökümanı ekleneceği zaman bu işlemin eski eğitim dökümanlarının
tfidf ağırlıklarını etkileyeceği unutulmamalıdır. Bu yüzden böyle bir işlem
yapılacaksa bu ağırlıklar tekrar güncellenmeli ve veritabanında ya da bir config
dosyasında tutulmalıdır.
Şüphesiz tüm sözlük
elemanları ile dökümandaki kelimelerden oluşan dizimizi karşılaştırmak performans
açısından bize sorun yaratabilir. Bu sebeple bu aşamada indeksleme algoritmalarından
faydalanılabilir. Ayrıca eğitim dökümanlarımız sadece 1 kere tanımlanacağı ve
değişmeyeceği için bunların uzay vektörleri 1 kere oluşturulup bir text dosyasında
veya veritabanında tutulabilir. Böylece programın çalışması esnasında eğitim
dökümanları ile ilgili olan hesaplamalar minimuma indirgenmiş olur.
Ayrıca makaledeki
örnekler sadece kolay anlaşılması bakımından küçük boyutlu bir uzay kullanılarak
yapılmıştır. Normalde sağlıklı bir sınıflandırma için en az binlerce kelimelerden
oluşan sözlükler kullanılmalıdır.
Bir sonraki makalemde
Naive Bayes algoritması üzerinde duracağım. Herkese
iyi çalışmalar dilerim.
Makale:
Metin Madenciliği ile Metin Sınıflandırma(KNN Algoritması) - 3 Yazılım Mühendisliği İsmail Pilavcılar
|