Bu site emekli olmuştur. Arşiv amaçlı olarak BT AKADEMİ sponsorluğunda yayın hayatına devam etmektedir.




C#nedir?com
 
YAZAR HAKKINDA
İsmail  Pilavcılar
İsmail Pilavcılar
http://www.csharpnedir.com/
İletişme geçmek için tıklayın.
3 Makalesi yayınlanmakta.
Yazar hakkında detaylı bilgi için tıklayın.
Yayınlanan diğer makaleleri için tıklayın.
İlgili etiketler: ‘ilgili agirligini agirliklar agirliklari algoritmasi boyutunu egitim frekans isleme kategorisi kelime kelimenin komsuluk siniflandirma yapilir. Yazılım Müh. İsmail Pilavcılar
 
YAZI HAKKINDA
Türü : Makale
Serbest Köşede C#nedir?com üyelerinin hazırladıkları yazılar yayınlanır. Bu yazılar editör incelemesine girmeden yayınlanır.
Seviyesi : İleri
Kategori : Yazılım Müh.
Yayınlanma Tarihi : 8.12.2007
Okunma Sayısı : 40996
Yorum Sayısı : 0     yorum yaz
Site İçi AramaSİTE İÇİ ARAMA
Üye Girişini AçÜye GİRİŞİ
Üye girişi için tıklayın.
Kullanıcı Adı
Şifre
 
Beni her zaman hatırla
Bir hafta boyunca kullanıcı bilgilerinizi kullanıcı çıkışı yapana kadar hatırlar. (Paylaşılan bilgisayarlarda önerilmez.)
 
Şifremi / Kullanıcı Adımı unuttum.
 
.net TV RSS Serbest KÖŞE (?)
Serbest Köşede C#nedir?com üyelerinin hazırladıkları yazılar yayınlanır. Bu yazılar editör incelemesine girmeden yayınlanır.
emre TAŞ
Silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
Makale Gönder Bende Yazmak İstiyorum
.net TV RSSBlogroll
Turhal Temizer
Conda install environment.yml Package 28.3.2024
Turhal Temizer
Mac OS/X Removing CUDA 28.3.2024
Burak Selim Şenyurt
Kurumsal Yazılımcının Oyun Geliştirme ile İmtihanı 28.3.2024
Burak Selim Şenyurt
Matematik ve Oyun Programlama - Missile Command - Final 28.3.2024
  Diğer Herşey
Sponsorlar
BT Akademi
Medya Portakal
Video Hosting Sponsoru
Csharpnedir.com bir Ineta üyesidir
Uzman Abi
Her Yönüyle C# - Sefer Algan
Metin Madenciliği ile Metin Sınıflandırma(KNN Algoritması) - 3
 
Kapat
Sayfayı Yazdır Sık Kullanılanlara Ekle Arkadaşıma Gönder MySpace Del.Ico.Us Digg Facebook Google Mixx Reddit StumbleUpon
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
  • Yazılan Yorumlar
  • Yorum Yaz
Bu konu hakkında yayınlanan yorum bulunmamaktadır.
"Yorum Yaz" tabını kullanarak sizde yorumlarınızı yazabilirsiniz.
Yorum yazabilmek için üye girişi yapmalısınız. Üye girişi için tıklayın.
Üye değilseniz Üyel Ol linkine tıklayarak üyeliğinizi hemen başlatabilirisniz.
 
  • Bu Konuda Son 10
  • Eklenen Son 10
  • Bu Konuda Geçmiş 10
Bu Konuda Yazılmış Yazılmış 10 Makale Yükleniyor
Son Eklenen 10 Makale Yükleniyor
Bu Konuda Yazılmış Geçmiş Makaleler Yükleniyor