Metin sınıflama için yeni bir özellik çıkarım yöntemi
A new method on feature extraction for text classification
Yazar: GÖKSEL BİRİCİK
Danışman: PROF. DR. A. COŞKUN SÖNMEZ
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2011
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Bilgi erişim = Information access ; Boyut indirgeme = Reduction of dimensionality ; Metin sınıflandırma = Text categorization

Özet:
Metin tipindeki bilgiye erişim, verinin yapısı ve doğası gereği zorlu bir iştir. Bu sebeple bilgiye erişimi kolaylaştırmak için metnin özelliklerine göre kategorizasyon çözümleri geliştirilmiştir. Ancak metin verisi çok sayıda özellik içerdiği için kategorizasyon yöntemleri ile çalışmak da güçtür. Bu problemin çözümü için özellikleri azaltan boyut indirgeme yöntemleri ortaya atılmıştır. Boyut indirgemede ilk yaklaşım özellik seçimidir ve başarımı en az düşürecek ve efektif çalışmayı arttıracak şekilde, özelliklerin sayısının azaltılması hedeflenir. İkinci yaklaşım olan özellik çıkarımında ise amaç az sayıda yeni özellikle verinin yeniden tanımlanmasıdır.Özellik seçim yöntemleri ile belgeleri diğerlerinden daha iyi tanımlayan terimler seçilmeye çalışılır. Bunun için çeşitli deneyler yaparak diğerlerinden daha iyi sonuç veren terim alt kümesini arayan yöntemler olduğu gibi, çeşitli değerlendirme ve dizme yöntemleriyle terimleri sıralayıp belirli bir eşik değerinin üzerinde değer alan terimleri seçen yöntemler de mevcuttur. Metin işleme uygulamalarında boyut indirgeme için genellikle özellik seçim yöntemleri tercih edilmektedir.Özellik çıkarım yöntemleri, belgeleri terimlerin bileşkesini alarak daha düşük boyutlu yeni bir uzayda kaynaştırılmış yeni özelliklerle ifade eder. Bu sayede veri, sayıca daha az ve orijinallerinden bağımsız özelliklerle ifade edilmiş olur. Çıkarılan özellikler belgelerin karakteristikleri hakkında gözlenebilir bilgi de sunmaz.Bu tez çalışması kapsamında, metin işleme alanı için yeni bir özellik çıkarım yöntemi geliştirilmiştir. Bir veri kümesinde yer alan terimlerin belgelerdeki dağılımları, belgelerin kategorilere ait olmasında etki sahibidir. Özellik seçiminde de terimlerin ayırt ediciliklerine bakarak seçim yapan yöntemler mevcuttur. Bu sebeple çalışmada ilk olarak terimlerin ayırt edicilikleri ağırlıklandırılarak ortaya çıkarılmıştır. Daha sonra belgeler her bir sınıf için etki değerlerinin bileşkesinden oluşan, yeni bir uzayda yer alan özelliklerle ifade edilmiştir. Çıkarılan özelliklere, belgelerdeki orijinal terimlerin her bir sınıfa olan etkisinin bileşkesini temsil ettiği için soyut özellikler adı verilmiştir. Kısaca, soyut özellik çıkarım yöntemi ile belgelerdeki terimlerin içerdiği ayırt edicilik değerleri kullanılarak terimlerin sınıflara olan etkilerinin bileşkesi yeni bir uzayda soyut olarak ifade edilmiştir.Soyut özellik çıkarım yönteminin başarımını test etmek ve diğer yöntemlerle karşılaştırmak üzere metin tipinde veri kümeleri üzerinde sınıflandırma testleri gerçekleştirilmiştir. Türkçe veri kümesi olarak DMOZ dizininden taranan örün sayfaları ile bir veri kümesi oluşturulmuştur. Sonuçları doğrulamak üzere bağımsız bir DMOZ test veri kümesi de hazırlanıp kontrol testleri yapılmıştır. Standart veri kümeleri olarak Reuters-21578 ve 20-Newsgroups seçilmiş ve kullanılmıştır. Bağımsız eğitim-test kümeleri ile test yapabilmek için, ModApte-10 veri kümesi ile de testler tekrarlanmıştır. Karşılaştırma için özellik seçim yöntemleri olarak chi-kare, korelasyon katsayısı ve karşılıklı bilgi, özellik çıkarım yöntemleri olarak da PCA, LSA ve LDA testlere dahil edilmiştir. Sınıflandırma testleri için değişik tasarım yaklaşımlarına sahip algoritmalar tercih edilmiştir. İstatistiki sınıflandırıcı olarak Naive Bayes, karar ağacı olarak C4.5, kural tabanlı sınıflandırıcı olarak RIPPER, örnek temelli yöntem olarak 10 en yakın komşu, kontrollü varyasyonlara sahip karar ağaçları koleksiyonu için rastgele orman, çekirdek tabanlı sınıflandırıcı olarak destek vektör makineleri, doğrusal sınıflandırıcı olarak LINEAR kullanılmıştır. Ayrıca sınıflandırma algoritmalarının parametrelerinin başarıma olan etkisini ölçmek üzere destek vektör makineleri sınıflandırma algoritması farklı çekirdek alternatifleriyle denenerek sınanmıştır. Sınıflandırma deneylerinde doğrulama için standart eğitim ve test kümesi ayırımı olan veri kümeleri haricinde 10 kere çapraz doğrulama kullanılmıştır.Yapılan testlerin sonuçlarına göre soyut özellik çıkarım yöntemi diğer yöntemlerden daha yüksek başarım sağlamıştır. Yöntem bazında testlerin ortalama sonuçları incelendiğinde de soyut özellik çıkarım yönteminin başarımı diğerlerinden yüksektir. Bu sonuçlardan anlaşılacağı üzere soyut özellik çıkarım yöntemi veri kümelerini metin işleme uygulamalarına efektif olarak hazırlamak için kullanılabilir. Bunun yanında yöntem sınıfların ayrılabilirliği hakkında da bilgi vermektedir. Yöntem ile ortaya çıkarılan soyut özellikler, örneklerin kendi sınıfına ve diğer sınıflara ait olma olasılıkları olarak da değerlendirilebilir. Örneklerdeki soyut özelliklerin değerleri birbirine yakın olduğunda sınıfların ayrılabilirliği az olmaktadır. Soyut özelliklerin değerleri arasındaki farklar büyüdükçe sınıfları bağımsız olarak ayırt etmek daha kolaydır.

Abstract:
Textual information retrieval is a challenging task due to complex structure and nature. Categorization solutions based on the features of textual data are presented in order to overcome challenges and simplify information retrieval process. Since textual data contains vast amount of features that causes the curse of dimensionality, implementing categorization becomes an arduous task. Dimension reduction techniques are introduced to overcome this problem. There are two approaches for reducing dimensions of the feature space. The first approach, feature selection, selects a subset of the original features as the new features, which is expected to increase affectivity and minimally decrease performance. The second approach, feature extraction, reduces dimension by creating new features that redefines data. This is achieved by combining or projecting the original features.Feature selection methods try to find the features that explain data better than others, and output a smaller subset of features. Selection procedure is based on either evaluation of features on a specific classifier to find the best subset, or ranking of features by a metric and eliminating the ones that are below the threshold value. Feature selections methods have a broader usage than feature extraction for dimension reduction in text processing.Feature extraction algorithms map the multidimensional feature space to a lower dimensional space. This is achieved by combining features to form a new description for the data with sufficient accuracy. Since the projected features are transformed into a new space, they no longer resemble the original feature set, but extract relevant information from the input set.In this thesis, we introduce a novel feature extraction method for text classification. The distribution of terms on documents affects the membership in classes. We also know that there are feature selection methods which evaluate the worthiness of features regarding to their distinctiveness?s. Based on this fact, we weigh and reveal the distinctiveness of the features as the first step. Then the documents are represented with new extracted features that consist of the combination of their weights, in a lower dimensional space. Since the new features resemble the combined effect of original features to each class, we name the extracted features as abstract features. Briefly, we project high dimensional features of documents onto a new feature space having dimensions equal to the number of classes in order to form the abstract features.We execute classification tasks on text datasets in order to test the performance of abstract feature extraction and compare with other methods. The first dataset is built up of Turkish web pages crawled from DMOZ directory. A separate test dataset is also prepared for validation by crawling unseen web pages from DMOZ again. Reuters-21578 and 20-Newsgroups datasets are used as standard text datasets. Tests are repeated using ModApte-10 dataset for observing the results with separate train and test samples. We select chi-squared, correlation coefficient and mutual information as feature selection and PCA, LSA and LDA as feature extraction methods for comparing the classification and clustering performances with abstract feature extractor. We use Naïve Bayes as a simple probabilistic classifier. We choose C4.5 decision tree algorithm for a basic tree based classifier, and a random forest with 10 trees to construct a collection of decision trees with controlled variations. We choose 10-nearest neighbour algorithm to test instance-based and RIPPER to test rule based classifiers. We use SVM for kernel based classifier and LINEAR as a linear classifier. In order to test the impact of classifier parameters on performance, we compare different kernel alternatives for SVM classifier. Instead of train-test split datasets, we use 10 fold cross validation to evaluate the tests.Test results show that abstract feature extraction leads to higher performance results than the other methods. If we look at average results on method basis, abstract feature extraction is ahead of the compared methods again. These results prove that abstract feature extraction algorithm can be used to effectively prepare datasets to text processing tasks. Not only abstract feature extraction makes it possible to prepare datasets in an effective way, but also gives information about class separability. The extracted abstract features can be seen as the membership probabilities of samples to the classes. These features also describe the likelihood of a sample to other classes. We can infer that if the values of abstract features are close to each other, class separability is low. As the distances between the abstract features increase, it becomes easier to distinguish the classes.