This paper presents the results of classifying Serbian text documents using the byte-level n-gram based frequency statistics technique, employing four different dissimilarity measures. Results show that the byte-level n-grams text categorization, although very simple and language independent, achieves very good accuracy.
Text categorization is the task of classifying unlabelled
natural language documents into a predefined set of
categories. The increasing volume of available documents in the
World Wide Web has turned the document indexing and
searching more and more complex. This issue has motivated
the development of automated text and document
categorization techniques that are capable of automatically
organizing and classifying documents. There are many
different techniques for solving text categorization problem with
very good results, including Naive Bayes classifier,
Decision trees, Decision rule classifiers, Regression methods,
Rocchio’s method, Neural networks, K nearest neighbors,
Support vector machines etc.[
Serbian language has several properties that significantly
influence text categorization: the use of two alphabets
(Cyrillic or Latin alphabet), phonologically based orthography, the
rich morphological system, free word order of the subject,
predicate, object and other sentence constituents, special
placement of enclitics and complex agreement system.[
This paper presents the results of Serbian text
categorization using a technique which is language independent
and very simple, that overcomes the above difficulties. This
technique is based on byte-level n-gram frequency statistics
method for documents representation and K nearest
neighbors machine learning algorithm for categorization process.
It is derived from Keˇselj’s[
Given a sequence of tokens S = (s1, s2, ..., sN+(n−1)) over
the token alphabet A, where N and n are positive integers,
an n-gram of the sequence S is any n-long subsequence of
consecutive tokens. The ith n-gram of S is the sequence
(si, si+1, ..., si+n−1).[
For example, if A is the English alphabet, and l string
on alphabet A, l = ”life is a miracle” then 1-grams are:
l,i,f,e, ,s,a,m,r,c; 2-grams are: li,if, fe, e , i, is, s , a, ...;
3-grams are: lif, ife, fe , e i, ...; 4-grams are: life, ife , fe i,
... and so on. The underscore character (” ”) is used here to
represent blanks. For n ≤ 5 Latin names are commonly used
for n-grams (e.g., trigrams) and for n > 5 numeric prefixes
are common (e.g., 6-grams).[
The use of n-gram models and techniques based on
ngram probability distribution in natural language
processing is a relatively simple idea, but it turned out to be
effective in many applications.[
The term n-gram could be defined on word, character or
byte level. In the case of Latin-alphabet languages,
characterlevel and byte-level n-gram models are quite similar
according to the fact that one character is usually represented by
one byte. The only difference is that character-level n-grams
use letters only and typically ignore digits, punctuation, and
whitespace while byte-level n-grams use all printing and
nonprinting characters.[
The technique used in this paper is based on calculating
and comparing profiles of N-gram frequencies. First, profiles
on training set data that represent the various categories are
computed. Then the profile for a particular testing
document that is to be classified is computed. Finally, a
dissimilarity measure between the document’s profile and each of
the category profiles is computed. The category whose
profile has the smallest value of dissimilarity measure with the
document’s profile is selected. Detailed text categorization
procedure is presented in [
Dissimilarity measures: Dissimilarity measure d is a
function that maps the Cartesian product of two sets of
sequences P1 and P2 (defining specific profiles) into the set
of positive real numbers. It should reflect the dissimilarity
between these two profiles and it should meet the following
conditions:[
The last two conditions are informal as the notion of similarity (and thus the dissimilarity) is not strictly defined.
In this paper is used four dissimilarity measures. First
of them is measure used by Keˇselj[
X n∈profile 2 · (f1(n) − f2(n)) 2 f1(n) + f2(n) where f1(n) and f2(n) are frequencies of an n-gram n in the author profile P1 and the document profile P2.
Other three measures are measures from [
X n∈profile 2 · (f1(n) − f2(n)) f1(n) + f2(n) (1) (2) √ √ (3) (4) d2(P1, P2) =
X n∈profile 2 · |f1(n) − f2(n)| 2 pf1(n)2 + f2(n)2 d3(P1, P2) =
X n∈profile 2 · |f1(n) − f2(n)| pf1(n)2 + f2(n)2
In this paper is presented categorization of text documents
in Serbian. For this purpose, Ebart corpus is used.
Ebart: Ebart1 is the largest digital media corpus in
Serbia with almost one million news articles from daily and
weekly newspapers archived by early 2003 onwards. The
current archive is classified into thematic sections following
the model of regular newspaper columns. In this paper a
subset of the Ebart corpus is taken into consideration -
articles from the Serbian daily newspaper ”Politika” that belong
to columns Sport, Economics, Politics, Chronicle & Crime
and Culture & Entertainment published from 2003 to 2006.
There are 5235 such articles. This data set was split into
the training and testing set in the ratio 2 : 1. Fig. 1 shows
the distribution of this corpus.2
Performance evaluation: The standard metrics for the
categorization performance evaluation is considered, namely
micro- and macro-averaged F1 measures. As usual,
microaveraged F1 measure is computed for all documents over
all document categories. Macro-averaged F1 measure
represents the averaged value determined from F1 values
computed for each classification category separately. The
standard definition of these measures and measures of precision
and recall can be found, e.g., in [
This section presents the experimental results of text
categorization obtained for Ebart corpus on five categories:
Sport, Economics, Politics, Chronicle & Crime and Culture
& Entertainment. No preprocessing is done on texts, and
a simple byte n-grams representation is used, treating text
documents simply as byte sequences. Only the measures
selected from [
8 1 gedF .865 a r e v a − o r c aM .860 0 . 8 8 1deF .578 g a r e v coa− .870 ir M 1 F d raege .865 v a − o r c aM .60 8 the process of separating testing from training documents and in the process of categorization, the software package NgramsClassification3 is used.
One of the most important question in the byte n-gram categorization is what are the values of n and L that produce the best results. To give an answer to this question, the accuracy (micro- and macro-averaged F1) of the technique was tested for all values of n-gram size n and the profile length L that makes sense to do.
Fig. 2 and 3 shows graphical representation of this extensive set of experiments taking into account only a few values of n for which the highest accuracy is achieved and only dissimilarity measure d (all other measures achieve the maximum accuracy for the same value of n as d). It can be seen that the maximum values for micro- and macro-averaged F1 measures are reached for n = 7. For that particulary value 3Source code can be obtained on request from the author. of n, comparison between measures d, d1, d2 and d3 is performed. The results of these experiments are shown in Fig. 4 and 5.
Additionally, Fig. 6 presents micro- and macro-averaged F1 values for the best results for each measure. All these results show that the all introduced measures achieves comparable results.
Quality of classification is assessed also using a confusion matrix, i.e., records of correctly and incorrectly recognized documents for each category. Table 1 give the confusion matrix for the experiments using the 70000 most frequent 7-grams and dissimilarity measure d. It shows the information about actual and predicted categorizations done by our system. Each column of the matrix represents the number of documents in a predicted class, while each row represents the number of documents in an actual class. The diagonal elements show the number of correct classified documents, and the off-diagonal elements show the number of wrongly classified documents. The main reason for some wrongly classified documents comes from the similarities between categories in real world. For example, the category ”Chronicle & Crime” and the category ”Politics” are close to each other. The same stands for ”Politics” and ”Economy”. In the Table 1, the numbers with a label of ”*” are the numbers of documents wrongly classified in a category that is close to the correct category. 5.
In this paper is presented the results of classifying Serbian data set using a new variant of a document categorization approach based on byte-level n-grams, including all printing and non-printing characters. The approach relies on a profile document representation of restricted size and a very simple algorithm for comparing profiles. It provides an inexpensive and effective way of classifying documents.
Dissimilarity measures are subject to further investigation and improvement, as well as categorization methods themselves. The plan is to compare the results obtained by presented method with results of other supervised methods on the same data sets. This method, being based on a sequence of bytes, is applicable to different domains and problems and will be further tested on specific corpora such as bioinformatics and multi-lingual corpora and on tuning Internet search engines.
The work presented has been financially supported by the Ministry of Science and Technological Development, Republic of Serbia, through Projects No. III47003 and No. 174021. The author is grateful to prof. Gordana Pavlovi´c-Laˇzeti´c for her unfailing support and supervision of my research.