-There is arguably more research done on clustering of English texts than of any other language. In this article, the process of clustering Lithuanian news articles is studied. For text preprocessing, the effect of stemming, term frequency metrics and feature filtering is investigated. In addition, following clustering algorithms are compared: k-means, bisecting kmeans, and three linkage method variations of hierarchical clustering. The results show that k-means algorithm gives best overall results and that only one of the three hierarchical algorithms produces comparably good results. Term frequencyinverse document frequency (TF-IDF) with stemming significantly increased clustering quality compared to not doing stemming and/or using TF. Feature filtering by IDF helped to optimize the k-means algorithm, but reduced the quality when using hierarchical clustering.
I. INTRODUCTION
The way people transfer information has changed drastically throughout the history. The initial methods were slow and had low capacity, e.g. a messenger carrying as many scrolls as he is physically able to carry. Throughout the centuries new ways to store and transfer information were invented. Nowadays information travels at the speed of light in amounts so large that humans can hardly comprehend them.
While the amounts of information transferred increased, human capabilities to consume this information did not improve as much. This only increases the need for automated means to process information: group, categorize, find duplicates, etc. One of such means is document clustering.
This work studies clustering process of Lithuanian news
articles. The purpose of this study is to examine how different
text preprocessing steps and clustering algorithms affect the
quality of the clustering produced. This article describes the
work done and the results of it. Similar previous work includes
[
This document is divided into several sections. Section II introduces reader to feature selection and clustering of textual data. Section III describes the data set used in this study. Section IV lists the metrics used to evaluate results. In sections V and VI it is described how features were selected and what experiments were performed. Sections VII and VIII provide analysis of results and conclusions.
II. A BRIEF INTRODUCTION TO DOCUMENT CLUSTERING
Document clustering is an application of cluster analysis to
textual documents. It is unsupervised learning and can be used
for finding similar documents, organizing large document
collections, detecting duplicate content and search optimization
[
Document clustering process can be separated into three stages: feature selection, feature extraction and an application of clustering algorithm. A more detailed description of these stages is given in the following paragraphs.
Feature selection is a process of creating feature vectors from the text of the documents. It includes various text processing steps such as splitting text into tokens, stemming and lemmatization, removing stop words, and calculating term frequency values.
Text data has a few properties, which requires different
approach than clustering other kinds of data [
Stemming and lemmatization can be used to reduce the problem of high dimensionality. Multiple forms of the same word induce multiple dimensions in a feature vector. By stemming words multiple dimensions would be joined to a single dimension corresponding to a base form of the word. In addition to decreasing dimensionality this would also reduce noise caused by the grammar of a language (which is especially true for Lithuanian language, in which a word can have many different forms).
There are multiple ways to control the input of a term to a
clustering process. A simple stop words list can be used to
remove stop words from the text. Other statistical techniques
can be used for less significant term removal, such as term
strength, entropy-based ranking and term contribution [
There are multiple variants of TF–IDF formula. In this work fallowing formula is used: (1) where ft,d is the number of times term t appears in document d, N is the number of documents in D, and nt is the number of documents in D containing term t.
While feature selection is a process of filtering relevant features of a text, feature extraction uses the original feature set to build new features. This includes methods for dimensionality reduction, such as Principal Component
Semantic Indexing [
The importance of feature extraction comes from a fact that
words tend to correlate with one another. This means that the
feature space is bigger than the number of concepts [
There are many different approaches how to cluster textual
data [
K–means is a simple algorithm, producing flat clustering. During initialization, algorithm selects k means, which corresponds to k clusters. Then two steps are repeated: (1) for every data point choose the nearest mean and assign the point to the corresponding cluster; (2) recalculate means by averaging data points assigned to the corresponding cluster. The algorithm terminates, when assignment of the data points doesn’t change after successive iterations.
The clustering produced by k–means algorithm highly
depends on the initial means chosen. A common approach is to
run algorithm multiple times with randomly chosen initial
means. In [
Bisecting k-means algorithm is a variation of k–means algorithm. This algorithm takes top–down approach. It starts with single cluster containing all the data points. Iteratively the biggest cluster is chosen and split into two parts by running inner k–means on the data points of the cluster. The algorithm terminates when the chosen number of clusters is reached.
Hierarchical agglomerative clustering is another wellknown technique for clustering. Algorithm starts by assigning every data point to a separate cluster. Then iteratively two closest together clusters are joined into a single cluster. This step is repeated until single cluster is left. The output of the algorithm is a tree which describes how the clusters were joined.
There are multiple ways to describe the distance between two clusters in terms of distances between data points in those clusters:
Single linkage. The distance between two clusters is equal to smallest distance between two data point crossing these clusters (i.e. closest pair of points across clusters). This resembles Kruskal’s minimum spanning tree algorithm.
Group average linkage (also known as Unweighted
In this method, the distance between clusters is an average of distances between every pair of data points across clusters.
Complete linkage. This is similar to single linkage method, but instead of smallest distance the largest distance between a pair of data points is taken (i.e. the most distant pair of points across clusters).
The distance–based clustering algorithms requires a metric
to evaluate the distance between data points. In this work a
cosine distance was chosen:
(2)
where , are feature vectors, n is dimensionality of the
vectors. Cosine distance is a commonly used distance metric
and gives good results for textual data [
The articles for the experiments were taken from the three major Lithuanian news websites: delfi.lt, alfa.lt and 15min.lt. A week’s worth of articles were retrieved, starting from January 1st to January 7th, 2016, total of 3572 articles.
The news sites contain different sub-sections, e.g. “news from Lithuania”, “crime”, “business”, etc. Every article is published in one of these sub-sections. To label the data the names of the sub-sections were used. One problem of such labeling is that different websites have different number of categories, some of which are more abstract than others (e.g. one website has a single sub-section “sports”, while other has multiple sub-sections for “basketball”, “football” and so on). To avoid labels being mismatched, they were normalized across the websites by grouping them to several categories. By investigating the websites, a common set of categories was noticed:
Other (187 articles, which doesn’t fall into previous categories).
This division to categories shows that some categories are more popular than others. For example, 1/6th of the articles fall into “sports” category. The standard deviation of such composition is 173.6, and median absolute deviation is 135 (these metrics are also used for comparison of clustering algorithms further in this article).
Fig. 1 shows the article categories mapped to 2 dimensions using PCA. While the “sports” category lies in top right quadrant clearly separated from other categories, other categories are much more intermixed. This is probably caused by the fact that sports articles have a distinctive vocabulary and that “sports” category takes up a big part of the data set.
To measure the quality of the clustering several evaluation metrics were used: precision, recall, F1 score, purity and entropy.
Precision and recall are well known measures in information retrieval. Both measures deal with notions of true positive, false positive, true negative and false negative. In case of clustering, every pair of documents are taken in account. If a pair of documents have same label and appear in the same cluster, then it is a true positive. The rest of the notions are where C is a set of clusters ci, k is the number of clusters, and N is the number of items.
Precision and recall range from 0 to 1 and are defined as: (3) (4) (5) (6) (7) (8)
Precision and recall tend to introduce bias when the number of clusters reaches extremes (e.g. recall equals 1 when every item falls into a single cluster). F1 score reduces bias by combining both measures:
Because F1 score doesn’t tend to favor high or low number of clusters as much as other metrics, a preference is given to this metric throughout the article.
Purity describes the homogeneity of clusters. Purity of a clustering ranges from 0 to 1 and is defined as where N is the number of items, k is the number of clusters, ci is a chosen cluster, and gj is a category which has the maximum number of items in ci.
Purity has a bias for high number of clusters. For example, when every cluster consists of a single item, purity equals to 1.
Entropy, same as purity, describes the homogeneity of the clusters. However, while purity only considers the number of items from dominating category, entropy considers the whole composition of the cluster. For a single cluster, entropy is defined as where ci is a chosen cluster, m is the number of categories, and gj is a category which has items in cluster ci. To calculate then entropy for a whole clustering, weighted average is used: Entropy, same as purity, is biased towards high number of clusters (e.g. entropy of a single item cluster is 0).
Text preprocessing and conversion to feature vectors consisted of the following steps: 1) 2) 3) 4) 5) 6)
Filtering a specific percentage of terms which are rarest according to IDF (skipped in some experiments);
More details about what feature selection steps were used in which experiments are given in the experiment descriptions.
In this experiment, it was studied how stemming and different term frequencies affected the clustering. 4 different configurations were used: (1) TF without stemming, (2) TF with stemming, (3) TF–IDF without stemming, and (4) TF– IDF with stemming. No term filtering was applied.
For clustering, k-means algorithm was used. Each stemming/term frequency configuration was tested by making multiple runs, trying out different numbers of clusters k[9;13] and with 5 randomly generated initial mean sets (in total, 25 runs per stemming/term frequency configuration).
In this experiment, multiple clustering algorithms were tested. In every test the same feature selection procedure was used. The text preprocessing matched the steps mentioned in section “Feature Selection Procedure”, except without any term filtering applied.
Below is the list of clustering algorithms tested:
In case of k-means algorithms, previously mentioned configuration was used: 5 randomly generated initial mean set for each k[9;13]. The results of multiple tests were averaged.
Contrary to k-means, hierarchical clustering doesn’t depend on a random factor. However, to extract flat clustering
HDBSCAN extraction method [
In term filtering experiment, it was studied how clustering quality changes in response to increasing the number of terms removed from feature vectors. Filtering was done by sorting terms by IDF and removing the ones which appear in the least number of documents. The percentage of terms remaining after filtering ranged from 100% to 10%. K-means and group average linkage hierarchical algorithms were used, configured as in clustering algorithms experiment.
The average F1 scores of different stemming and term frequency combinations are displayed in Fig. 2. The worst results are produced by TF ( without stemming and with stemming). While TF–IDF without stemming provides only a small increase ( ), the F1 score improves by more than 50% when applying stemming ( ).
The results confirm the intuition that TF–IDF and stemming improves clustering by disregarding stop words and reducing noise caused by language grammar. It is worth noting that stemming was much more effective when combined with TF–IDF. This shows that when selecting features, one misconfigured step can greatly diminish effect of other steps.
In Fig. 3 there are displayed average and maximum values of F1 score. The best results (both average and maximum) were shown by k–means and bisecting k–means algorithms (latter achieving the absolute maximum across all algorithms with no term filtering applied). Close results were shown by group average linkage hierarchical algorithm. Complete linkage and single linkage versions performed significantly worse, by value being closer to random clustering than to previously mentioned algorithms.
More quality measures are given in Table II. Different algorithms lead according to different metrics, but two of them stands out: k–means algorithm has the highest mean value of F1 score and purity, while group average linkage hierarchical clustering leads by precision and entropy.
Among all the algorithms, single linkage hierarchical clustering has the best recall value. This is probably caused by the fact that recall is biased to favor big clusters. In many cases this algorithm produced single cluster containing more than a half of articles along with multiple small clusters. The cluster size statistics confirms that—single linkage hierarchical clustering has the highest standard deviation, but lowest median absolute deviation (MAD). High standard deviation is caused by cluster sizes being distant from the mean. In case of MAD, a small number of outliers are irrelevant, so low MAD value means that the sizes of most of the clusters are close to each other.
When comparing cluster size statistics, group average hierarchical algorithm produces clusters which are close to each other in size. This observation is backed up by relatively low values of standard deviation and median absolute deviation. The cluster size distribution is not as equal in case of both k–means algorithms. While the k–means has lower standard deviation, bisecting k–means has lower MAD. In other words, the majority of clusters produced by bisecting k– means are more similar in size than those produced by k– means, but the outliers are more extreme too.
Fig. 4 displays the relation between number of clusters and the F1 score of hierarchical clustering algorithms. Group average clustering tends to show higher values when the number of clusters is close to the number of categories. This signals that the underlying concepts found by the algorithm are similar to the categories of the documents. In case of single and complete linkage methods, there is no such correlation.
For filtering tests, k-means and group average linkage hierarchical algorithms were chosen. There were multiple runs starting with full feature space of 41 thousand dimensions to only 10% of terms which are most common across the documents. The F1 scores are displayed in Fig. 5.
Of the two algorithms, k–means shows less sensitivity to changes of feature space. While there is a small decrease in F1 score moving from 100% to 50% of the dimensionality (minimum at ), the F1 score of 10% rises slightly above the full feature space with versus
.386.
Similar results were shown in [
The results of group average linkage hierarchical clustering differ from the k-means ones. The variance of F1 score is significantly greater. At the beginning the score increases from to . Later values drop reaching and after a temporal increase eventually drops to .
The pruning of 10% of features might have reduced the noise in the feature space. This would explain the sudden rise of the F1 score. The further pruning might have started removing relevant features. However, this does not explain the increase in F1 score at 30–20% of feature space. Cluster 143 size variklio šalčio aktorė rungtynių karinių policijos bendrovės dakaro jums šulinį dyzelinių temperatūra dainininkė ekipa partijos ugniagesiai barelį ruožas organizmą saviečių gamintojų laipsnių muzikinę žaidėjų sąjungininkų vpk indeksas ralio vitaminų tragedijos automobilių kritulių prodiuseris turnyro nimro neblaivus brent ekipažas astrologė smurto Relevant elektromobilių rajoniniai eurovizijos taškų šiitų ambulatoriškai įmonės vanagas cukraus mažamečius words tesla sniego koncertinį pergalę obama prom valiutos juknevičius horoskopas smurtaudamas motors provėžoti meninės kamuolį narystės patrulių wti lenktynininkai riebalų sugyventinę fiat hidrometeorologijos žanro treneris referendumas komisariato holding trasos jus sumetė volkswagen plikledis scenoje rezultatyvaus sirijos girtumas akcininkų lenktynių mitybos nužudė lg prispausto režisierius įvartį nato vairuojamas aplinkosaugos benediktas ožiaragis ekspertizė When comparing both clustering algorithms, k-means seems to intrinsically diminish the value of rare terms. In case of group average hierarchical clustering, the impact of such terms to the clustering results is significantly higher.
During this study, several hundred runs were made of various clustering configurations. From the top 50 tests sorted by the F1 score, every single one was done using one of the two k–means algorithms, only several of them being bisecting k–means. Most of these tests came from the filtering experiment, over a half having 40% or less features remaining.
In order to have a better idea if the methods actually produce meaningful clusters, a metric was proposed to measure which terms are more relevant to the cluster. It is a combination of two inverse document frequencies and is defined as where t is a term, c is a set of documents in a cluster, and D is the documents in the data set. In other words, term relevance is high if the term is (1) relatively rare across the documents in the data set and (2) relatively common in the documents of the cluster.
The test with the highest F1 score came from the filtering experiment: k–means algorithm and 20% of remaining features. The most relevant terms of this test are displayed in Table III. As expected, the clusters don’t seem to identically map to the categories in the data set. However, the themes of the clusters are easily noticeable (in Table III, some of the themes are “cars”, “sports”, “Dakar rally”, “business”, “foreign politics” and “crime”). Despite that, a deeper look at the (9) clusters reveals that it is not uncommon for other themes to appear in the clusters, sometimes not very related to the relevant words.
In this work, several different experiments were performed studying feature selection process and clustering algorithms. Term frequency and stemming experiment proved that TF–IDF with stemming is superior to other configurations. In addition, this experiment showed that one misconfigured step in the process can greatly diminish the effects of other steps. In the clustering algorithms experiment only 3 of 5 algorithms tested produced acceptable results, k–means performing arguably the best overall. In case of filtering experiment, k–means algorithm seemed mostly unaffected by removal of major part of the features, while the results of group average linkage hierarchical clustering varied more and was less predictable.