Arama Tabanlı Kısa Metin Sınıflandırma Algoritması-AET Araştırması
0 Önsöz
Metin Sınıflandırma, belirli bir sınıflandırma sistemi altında belirli bir sınıflandırma algoritması aracılığıyla bir bilgisayar tarafından bilinmeyen metin kategorilerinin otomatik olarak kategorize edilmesi sürecini ifade eder. Son on yılda, metin sınıflandırması hızla gelişti ve dijital kitaplıklar, web sayfası sınıflandırması, spam e-posta filtreleme vb. Dahil olmak üzere birçok alanda yaygın olarak kullanıldı. Şimdiye kadar, Karar Ağacı, Bayes Yöntemi, KNN, Sinir Ağı, Destek Vektör Makinesi (SVM) gibi istatistiksel teori ve makine öğrenimine dayalı birçok metin sınıflandırma yöntemi olmuştur. Bununla birlikte, bu sınıflandırma yöntemlerinin araştırılması ve uygulanmasının tamamı uzun metinlere dayanmaktadır ve kısa metinler İnternette giderek daha yaygın hale gelmektedir. Yeni ortaya çıkan mikro blogların en büyük özelliği "mikro" dir ve genellikle yalnızca birkaç kelime gönderilebilir. Tanınmış trafik istatistikleri sitesi ALEXA'dan elde edilen veriler, Twitter'ın yaklaşık 20 milyon kişinin günlük ortalama ziyaret hacmine sahip olduğunu ve Amerika Birleşik Devletleri, Birleşik Krallık, Kanada ve diğer yerlerdeki en iyi 15 web sitesi arasında yer aldığını gösteriyor. Profesyonel veya dikey araştırma alanında, kaynak kısıtlamaları nedeniyle tam metnin işlenmesi imkansızdır, bunun yerine makale başlıklarına veya makale özetlerine göre sınıflandırılır. Bu uygulamalar kısa metin sınıflandırma teknolojisi gerektirir. Gerçek ihtiyaçları ve geleneksel yöntemlerin eksikliklerini hedefleyen bu makale, benzer NaiveBayes'e dayalı bir metin sınıflandırma yöntemi uygulamak için aramayı kullanan yeni bir sınıflandırma yöntemi önermektedir. Karşılaştırmalı deneyler, kısa metinlerin sınıflandırılmasında, bu yöntemin geleneksel sınıflandırma yöntemlerine kıyasla sınıflandırmanın doğruluğunu ve hızını artırdığını göstermektedir.
1 İlgili işe giriş
Son kırk yılda, Salton tarafından önerilen vektör uzayı modeli (VSM) etrafında metin sınıflandırması üzerine birçok araştırma yapılmıştır.Vektör uzayı modelinin temel fikri, metni vektör ile temsil etmektir: (W1, W2, , Wn), ilk olarak metni segmentlere ayırın, bu kelimeleri vektörün boyutu olarak kullanın ve özellik öğesine karşılık gelen vektör bileşenini temsil etmek için kelime frekansını kullanın Kelime frekansı hesaplama yöntemi esas olarak TF-IDF formülünü kullanır. Vektör uzayı yöntemi üzerine yapılan araştırma çalışmaları, esas olarak sınıflandırma performansını iyileştirmek için özellik seçimi ve özellik ağırlık ayarlamasına odaklanmıştır.Örneğin, Bay Lu Yuchang, ağırlık ayarlaması için özellik seçiminde TF-IDF formülünü değiştirmek için değerlendirme işlevini kullandı.
Metin sınıflandırmasında sinir ağı öğrenme algoritmalarının araştırılması ve uygulanması da çok kapsamlıdır.En popüler sinir ağı algoritması, 1986'da RUMELHARD DE ve MCCLELLAND J L tarafından önerilen geriye doğru yayılma algoritmasıdır (kısaca BP algoritması). BP algoritmasının yavaş yakınsama hızı ve yerel minimumlara düşmesi kolay gibi sorunları olduğu için, sonraki nesiller BP algoritmasında birçok iyileştirme yaptı.Örneğin, Li Xiaofeng bir BP sinir ağı dinamik tam parametre otomatik ayarlama öğrenme algoritması önerdi. Sinir ağları, gürültülü verileri ve metin sınıflandırma yeteneklerini taşıma konusunda iyi bir yeteneğe sahiptir, ancak genellikle deneyimle belirlenen çok sayıda parametre gerektirir. Ek olarak, sinir ağı uzun bir eğitim süresi gerektirir, bu nedenle yeterli eğitim süresine sahip uygulamalar için uygundur.
Wang Jianhui ve arkadaşları, karşılıklı bağımlılık ve eşdeğer yarıçapa dayalı basit ama verimli bir sınıflandırma algoritması SECTILE önerdi.Bu yöntem, karşılıklı bağımlılık (Karşılıklı Bağımlılık, MD) modeli önerdi ve bunu, özellik özellik seçimi için N-gram ile birleştirdi, Öznitelik seçiminin doğruluğu, etkili boyut azaltımı sağlar. Eşdeğer Yarıçap (ER) kavramı tanıtıldı ve geleneksel Öklid uzaklığı, eşdeğer yarıçapa dayalı göreceli mesafe ile değiştirildi, bu da sınıflandırma doğruluğunu artırıyor. SECTILE sınıflandırma algoritmasının hesaplama karmaşıklığı düşüktür ve büyük ölçekli bilgi örneği sınıflandırması için uygun olan sınıflandırma modelinin güncellenmesi kolaydır.
Shi Zhiwei ve arkadaşları, vektör uzayı yöntemi ve k-en yakın komşu için birleşik bir sınıflandırma yöntemi önerdi.Bu yöntem, tüm örnek uzayını üç bölüme ayırır: pozitif örnek, negatif örnek ve karma örnek ve farklı bölgelere düşen sorgu örneğine göre farklı sınıflandırma algoritmaları çağırır. Bu yöntem, vektör uzayı yönteminin hızlı sınıflandırma hızından ve k-en yakın komşu yönteminin yüksek sınıflandırma doğruluğundan tam olarak yararlanır.
Yukarıda belirtilen çeşitli sınıflandırma yöntemleri, uzun metinlerin sınıflandırılmasına uygulanabilir.Kısa metinler uzun metinlerden çok daha kısa olduğundan, metinlerde az sayıda özellik vardır ve metinler nadiren aynı özellikleri içerir, bu nedenle geleneksel Metin sınıflandırma yöntemleri, kısa metin sınıflandırması için uygun değildir. Şu anda, kısa metin sınıflandırmasına adanmış, kabaca iki araştırma yönüne ayrılabilecek az sayıda çalışma vardır: Birincisi, metinler arasında paylaşılan özellikleri harici kaynaklar aracılığıyla artırmak ve metin bağlamını zenginleştirmek.Örneğin, Wikipedia, kısa metin sınıflandırmasını tanıtmak için harici bir kaynak olarak kullanılmaktadır. Bu şekilde, geleneksel metin sınıflandırma yöntemleri kullanılabilir; diğeri, kısa metinleri önceden işlemek için bu seyrek özelliklerden tam olarak yararlanmaktır. Aşağıda, kısa metin sınıflandırması üzerine bazı araştırma çalışmaları sunulmaktadır.
Pu Qiang ve diğerleri, Bağımsız Bileşen Analizi (ICA) ve Gizli Anlamsal Analiz (LSA) 'ye dayalı kısa bir metin sınıflandırma yöntemi önermiştir.Bu yöntem önce metni LSA aracılığıyla önişler ve ardından sonuçlar üzerinde bağımsız işlemler gerçekleştirir. Bileşen analizi. LSA, bilgi çıkarma ve gürültü gidermeyi sağlamak için Tekil Değer Ayrıştırma (SVD) sıra azaltma yöntemini kullanır ve belgenin yüksek boyutlu temsilini düşük boyutlu gizli anlamsal alana yansıtır, böylece gizli anlamsal yapıyı sunar. Bununla birlikte, orijinal kelime-belge matrisi üzerinde SVD gerçekleştirilir ve en büyük tekil değerlere karşılık gelen özellikler gizli anlamsal uzay olarak seçilir.Şu anda, en büyük tekil değerlere sahip özelliklerin en iyi sınıflandırma yeteneğine sahip olduğunu kanıtlayacak bir teori yoktur, bu nedenle gizli anlamsal uzay Metin sınıflandırması için, sınıflandırma etkisi iyileştirilmemiştir.
Teng Shaohua ve diğerleri, Koşullu Rastgele Alanlara (CRF'ler) dayalı kısa bir metin sınıflandırma yöntemi önermişlerdir.Bu yöntem, kısa metinlerin genellikle tek bir konu üzerinde yoğunlaştığına ve böylece metindeki özelliklerin de oldukça alakalı olduğuna inanmaktadır. Bu doğaya göre, bu yöntem, kısa metin sınıflandırma problemini bir dizi etiketleme problemine dönüştürmek için Çince kelime segmentasyonunda kelime etiketleme yöntemini kullanır, böylece CRF'ler kısa metin sınıflandırma problemini çözmek için kullanılabilir. Bununla birlikte, CRF'ler, kolaylıkla kelime bölümleme hatalarına yol açabilen, parazite de yol açabilen yüksek güvenilirlik özelliklerine güvenirler Bu zorluğun CRF'lerin kendileri tarafından çözülmesi zordur. Sorun, CRF'lere dayalı kelime bölütleme sonuçlarının sonradan işlenmesiyle çözülebilmesine rağmen, bu yöntemin sınırlamaları vardır ve sadece CRF'lere dayalı Çince kelime bölütlemesini kullanabilir.
Özetlemek gerekirse, mevcut kısa metin sınıflandırma yöntemleri, iyi sınıflandırma kabiliyetine sahip bu özellikleri etkili bir şekilde seçemez, sınıflandırma doğruluğu düşüktür ve sınıflandırma hızı yavaştır; veya Çince kelime segmentasyon sistemine güvenirler ve zayıf ölçeklenebilirliğe sahiptirler. Bu makalede önerilen arama tabanlı NaïveBayes metin sınıflandırma yöntemi, bu yönleri geliştirmektedir.
Aramaya dayalı 2 Naive Bayes sınıflandırma algoritması
Arama tabanlı naif Bayes metin sınıflandırması, metin sınıflandırmasına arama teknolojisi uygulayarak ve naif Bayes sınıflandırma algoritmasını geliştirerek kısa metin sınıflandırmasına uygun bir sınıflandırma yöntemidir. Sınıflandırma algoritması aşağıdaki gibidir:
C = {c1, c2, ..., cm} önceden tanımlanmış bir kategori kümesi olsun, D = {d1, d2, ..., dn} sınıflandırılacak bir belge kümesi ve d = {w1, w2, ..., wn} bir Belgenin özellik vektörü, belge di'nin cj kategorisine ait olma olasılığı koşullu olasılık P (cj | di) ile temsil edilebilir. Bayesçi formüle göre:
Formül (2) ve (4) 'te, | c | metin kategorilerinin sayısıdır ve paydaki 1, sıfır olasılığın oluşmasını önlemek için bir ağırlıklandırma işlemidir.
Hesaplamayı basitleştirmek için, eğitim verilerini seçerken her kategoride aynı sayıda metin belirtmek daha iyidir. Bu şekilde, her bir metin kategorisi için, önceki olasılık eşittir ve P (cj) hesaplama süreci de göz ardı edilebilir. Bayes olasılığının hesaplanması, cj kategorisine ait olan belgenin arka olasılığının hesaplanmasıyla basitleştirilmiştir:
Formül (5) 'de, her kategori için payda kısmı N (cj) + | c | eşittir, yani, her bir kategoriye ait olma olasılığının karşılaştırmasını etkilemez, bu nedenle doğrudan hesaplayın:
Negatif sonsuz ve sıfırın oluşmasını önlemek için, yalnızca her bir özniteliğin (sözcüğün) belirtilen kategoride göründüğü belge sayısını, yani N (wi | cj) bilmeniz gerekir.
Yukarıdaki formül türetme ile birleştirildiğinde, arama tabanlı NaiveBayes metin sınıflandırma algoritması şu şekilde açıklanabilir:
(1) C1, C2, ..., Cm kategorilerinin m olduğunu varsayalım. Her kategorideki veri örnekleri üzerinde Çince kelime segmentasyonu gerçekleştirin ve CIndex1, CIndex2, ..., CIndexm dizinlerini oluşturun;
(2) Sınıf etiketi olmayan bir veri örneği X verildiğinde, üzerinde Çince kelime segmentasyonu gerçekleştirin (kelime segmentasyon sistemi, adım (1) 'de kullanılan kelime segmentasyon sistemi ile tutarlı olmalıdır), her kelime bir W1, W2 özelliğine karşılık gelir, , Wn;
(3) Veri örneği X'i Cj kategorisine atama olasılığını bulun, yani:
Başka bir deyişle, X, P (w | ci) 'yi maksimize eden Ci kategorisine atanır.
Not: Adım (1), bir sınıflandırma modelinin oluşturulması olarak da kabul edilebilir.Bu adım, sınıflandırma modelinin oluşturulması metin sınıflandırmasından önce yapıldığı için sınıflandırma hızını etkilemez. Arama tabanlı NaiveBayes sınıflandırıcı modeli, bilinen sınıf etiketleri ile eğitim veri kümesi üzerine kurulmuş bir dizindir ve her kategorideki eğitim veri metinlerinin sayısı eşittir. Bu aynı zamanda, arama tabanlı NaiveBayes sınıflandırıcı ile diğer sınıflandırıcılar arasındaki farktır. Hızı artırmak için bu makale Lucene.Net arama teknolojisini kullanır. Lucene.Net ile birlikte gelen StandardAnalyzer belirteç, kelime birimleriyle indekslenir. Çince metin sınıflandırması için, tek karakterli belirteç oluşturma, sınıflandırmanın doğruluğunu etkileyeceğinden, bu makale KTDictSeg sözcük bölümleme sistemini kullanır. KTDictSeg, KaiToo tarafından geliştirilen bir aramadır. Sözlük tabanlı açık kaynak Çince ve İngilizce kelime bölümleme sistemi. KTDictSeg Çince isimleri tanıyabilir ve aynı zamanda Lucene.net'i destekler.Lucene.net'e KTDictSegAnalyzer sağlar.
Sınıflandırma doğruluğu, hız ve ölçeklenebilirlik gibi sınıflandırıcı verimliliğinin çeşitli değerlendirme sonuçları olabilir. Birçok değerlendirme yöntemi vardır, en basit olanı sınıflandırıcıyı test etmek için bilinen sınıf etiketleriyle birlikte verileri kullanan Holdout yöntemidir. Sınıflandırıcının doğruluğu kabul edilebilir kabul edildiğinde, sınıflandırıcı bilinmeyen sınıf etiketleriyle verileri sınıflandırmak ve tahmin etmek için kullanılabilir.
3 Deney ve sonuç analizi
Çince metin sınıflandırması için, şu anda mevcut standart bir külliyat yoktur. Bu nedenle, bu makale Sogou Lab tarafından derlenen külliyatı (SogouC.reduced.20061127) kullanır. Bu külliyat, finans, BT, sağlık, spor, turizm, eğitim, işe alım, kültür ve askeri olmak üzere dokuz kategori içerir. 1990 makale. Bu külliyatın basit bir sıralamasını yapın, her kategoriden rastgele olarak test verisi olarak 160 makale seçin ve kalan 1.830 makaleyi bir sınıflandırma modeli oluşturmak için eğitim verisi olarak kullanın. Arama tabanlı NaiveBayes metin sınıflandırıcısını ve Weka'nın NaiveBayes metin sınıflandırıcısını test etmek için hazırlanan test verilerini kullanın Test sonuçları Tablo 1'de gösterilmektedir.
Tablo 1'den görülebileceği gibi, arama tabanlı NaiveBayes sınıflandırıcısı, Weka'nın NaiveBayes sınıflandırıcısı ile karşılaştırılabilir. Bununla birlikte, arama tabanlı NaiveBayes sınıflandırıcısının kısa metin sınıflandırmasına üstünlüğünü yansıtmak için, 1.440 test verisi kısaca işlenir ve sonra tekrar test edilir, yani her kategori 50 kelimede 50 metin içerir, 200 kelimelik 50 metin, 200 ila 1.000 kelimelik 50 metin ve 1.000 kelimeden fazla 50 metin. Böylelikle test verileri, metin kelime sayısına göre farklı seviyelere bölünmüş ve test veri metinlerinin sayısı da 1.800'e çıkmıştır. Sonra iki sınıflandırıcıyı test etmek için harmanlanmış test verilerini kullanın ve test sonuçları Tablo 2'de gösterilmektedir.
Tablo 2'deki verilere göre, Şekil 1'de gösterildiği gibi bir sınıflandırma doğruluğu grafiği çizin.
100 kelimelik kısa metinlerin sınıflandırılması için arama tabanlı NaiveBayes sınıflandırıcısının sınıflandırma doğruluğunda üstün performans gösterdiği Şekil 1'den açıkça görülmektedir. Tablo 2 ve Tablo 1'in karşılaştırmasından, 1.440 uzun metnin sınıflandırılması için arama tabanlı NaiveBayes sınıflandırıcısının 12.5875 sn sürdüğünü bulmak zor değil; 1.800 metnin kısa metinlerle sınıflandırılması için sınıflandırma aramaya dayalıdır NaiveBayes sınıflandırıcı 13.0062 sn sürmüştür. Kısa metin sınıflandırması için arama tabanlı NaiveBayes sınıflandırıcısının sınıflandırma hızını da önemli ölçüde iyileştirdiği şekillerden görülebilmektedir.
Bu durum, arama tabanlı NaiveBayes sınıflandırma yönteminin kısa metin işleme üzerinde iyi bir sınıflandırma etkisine sahip olduğunu ve tüm metin özelliklerinin seçilmesi nedeniyle sınıflandırma hızını düşürmediğini, aksine arama teknolojisinin devreye girmesi ile bir ölçüde iyileştiğini göstermektedir. Metin sınıflandırmanın hızı.
4. Sonuç
Kısa metin sınıflandırması için geleneksel metin sınıflandırma yöntemlerinin eksikliklerini hedefleyen bu makale, arama tabanlı bir NaiveBayes metin sınıflandırma yöntemi önermektedir. Bu yöntem ile geleneksel metin sınıflandırma yöntemi arasındaki fark, arama motoru teknolojisini metin sınıflandırmasına uygulaması ve saf Bayes sınıflandırma algoritmasını geliştirmesidir. Deneysel sonuçlar, kısa metinlerin sınıflandırılması için, aramaya dayalı NaiveBayes sınıflandırma yönteminin yalnızca sınıflandırmanın doğruluğunu büyük ölçüde iyileştirmekle kalmayıp aynı zamanda zaman karmaşıklığını da azalttığını göstermektedir. Ek olarak, metin özelliği çıkarma ve Çince metin durdurma kelimelerinin işlenmesi açısından, farklı uygulama arka planları için daha fazla araştırmaya ihtiyaç vardır. Deneyde kullanılan külliyat, yalnızca 17.910 makaleden oluşan standart bir külliyat değil, bu nedenle deney ölçeğinin daha da genişletilmesi gerekiyor. Uygulama olanakları açısından, iletişim teknolojisi ve İnternetin gelişmesiyle birlikte, e-postalar, kısa mesajlar ve Weibo mesajları gibi çeşitli kısa metin mesajları hızla artmıştır.Arama tabanlı NaiveBayes metin sınıflandırıcı kesinlikle yaygın olarak kullanılacaktır.
Referanslar
Wu Xindong, KUMAR V, QUINLAN J R, ve diğerleri .Veri madenciliğinde en iyi 10 algoritma. Knowl. Inf. Syst., 2008 (14): 24-27.
Lu Yuchang, Lu Mingyu, Li Fan, vb. Vektör Uzay Yönteminde Kelime Ağırlık Fonksiyonunun Analizi ve İnşası Bilgisayar Araştırma ve Geliştirme, 2002, 39 (10): 1205-1210.
RUMELHART D E, MCCLELLAND J L. Paralel dağıtılmış işleme: kognisyonun mikro yapısında keşifler, Cilt 1: Temeller Cambridge: MIT Press, 1986: 318-364.
Li Xiaofeng Dinamik tam parametreli kendinden ayarlı BP sinir ağı tahmin modelinin kurulması Tahmin, 2001, 20 (3): 69-71.
Wang Jianhui, Wang Hongwei, Shen Zhan, vb. Pratik ve verimli bir metin sınıflandırma algoritması Bilgisayar Araştırma ve Geliştirme, 2005, 42 (1): 85-93.
Shi Zhiwei, Liu Tao, Wu Gongyi. Hızlı ve verimli bir metin sınıflandırma yöntemi Bilgisayar Mühendisliği ve Uygulamaları, 2005, 41 (29): 180-183.
SCHONHOFEN P. Wikipedia kategori ağını kullanarak belge konularının belirlenmesi. IEEE / WIC / ACM Uluslararası Web Zekası Konferansı, 2006: 456-462.
Pu Qiang, Yang Guowei. ICA ve LSA'ya dayalı kısa metin sınıflandırması Berlin: Springer-Verlag Berlin / Heidelberg, 2006: 265-270.
Teng Shaohua. Çince kelime bölümleme ve CRF'lere dayalı kısa metin sınıflandırma teknolojisi. Pekin: Tsinghua Üniversitesi, 2009.
yazar bilgileri:
Kang Wei1, Qiu Hongzhe2, Jiao Dongdong1, Fang Zhiqi1, Yu Yinhu1
(1. Kuzey Çin Bilgisayar Sistem Mühendisliği Enstitüsü, Pekin 100083; 2. Pekin Havacılık ve Uzay Uçuş Kontrol Merkezi, Pekin 100094)
