A clustering technique for news articles using WordNet

Abstract

The Web is overcrowded with news articles, an overwhelming information source both with its amount and diversity. Document clustering is a powerful technique that has been widely used for organizing data into smaller and manageable information kernels. Several approaches have been proposed which, however, suffer from problems like synonymy, ambiguity and lack of a descriptive content marking of the generated clusters. In this work, we are investigating the application of a great spectrum of clustering algorithms, as well as similarity measures, to news articles that originate from the Web. Also, we are proposing the enhancement of standard k-means algorithm using the external knowledge from WordNet hypernyms in a twofold manner: enriching the “bag of words” used prior to the clustering process and assisting the label generation procedure following it. Furthermore, we are examining the effect that text preprocessing has on clustering. Operating on a corpus of news articles derived from major news portals, our comparison of the existing clustering methodologies revealed that k-means, gives better aggregate results when it comes to efficiency. This is amplified when the algorithm is accompanied with preliminary steps for data cleaning and normalizing, despite its simple nature. Moreover, the proposed WordNet-enabled W-k means clustering algorithm significantly improves standard k-means generating also useful and high quality cluster tags by using the presented cluster labeling process.

Introduction

News articles flood the Web every day from an extreme amount of major or minor news portals from around the globe. It is utterly impossible for a single individual to be able to keep track of an event, or a series of related events, from an unbiased and truly informative point of view. While the amount of online information sources is rapidly increasing, so does the available online news content. One of the most common approaches for organizing this immense amount of data is the use of clustering techniques. Object clustering refers to the process of partitioning a collection of objects into several sub-collections based on their similarity of contents. For the case of user clustering, each sub-collection is called a user cluster and includes users that have revealed similar appeals in their selections of text articles while browsing through a document collection. Clustering has been proven to be a useful technique for information retrieval by discovering interesting information kernels and distributions in the underlying data. In general, it helps constructing meaningful partitions of large sets of objects based on various methodologies and heuristics. It plays a crucial role in organizing large collections. For example (a) it can be used to structure query results, (b) form the basis for further processing of the organized topical groups using other information retrieval techniques such as summarization, or (c) within the scope of recommendation systems by affecting their performance as far as suggestions made towards the end users are concerned. Clustering has also been exploited within the scope of machine learning [2], as a time series mining task [17] which uses frequent itemsets to find association rules of items in large transactional databases.

Clustering of news articles can help by depicting the underneath content hierarchy of a huge amount of articles within the reach of a single individual. Consequently, it can provide information retrieval (IR) systems with the potential to alleviate users while browsing and detecting quickly the needed information.

However, there are several challenges that clustering techniques normally have to overcome. Among them is efficiency: generated clusters have to be well connected from a notional point of view, despite the diversity in content and size that the original documents might have. For example, it is frequent for some news articles to belong to the same notional cluster, even though they do not share common words. The vice-versa is also possible: news articles sharing common words, while being completely unrelated to each other. Ambiguity and synonymy are thus two of the major problems that document clustering techniques regularly fail to tackle with. Furthermore, having IR systems simply generate clusters of documents is not enough per se. The reason is that it is virtually impossible for humans to conceptualize information by merely browsing through hundreds of documents belonging to the same cluster. However, assigning meaningful labels to the generated clusters can help users conveniently recognize the content of each generated set and thus easily analyze the results.

In this manuscript, we are describing a variety of document clustering techniques and evaluating their application on our data set: news articles originating from the Web. Our aim is to compare the resulting clusters and determine which technique is best fitted for the extreme amount and diversity of news articles that an indexing system needs to address. Furthermore we are presenting a novel methodological approach towards document clustering, and in particular, clustering of news articles deriving from the Web, that combines regular k-means with external information extracted from the WordNet database. Our approach combines keyword extraction and several information retrieval techniques. We are also incorporating the proposed algorithm in our existing system [5], evaluating the clustering results compared to regular k-means using a large pool of Web news articles existing in the system’s database.

The rest of the manuscript is organized as follows: Section 2 gives a background of the related work regarding clustering methodologies as well as the use of the WordNet database on this field. In Section 3, we give a brief overview of our system which we are enhancing with clustering techniques. In Section 4 we describe the various clustering methodologies explored in this work, while in Section 5 we present the algorithmic approach of W-k means. In Section 6 we outline our experimental approach towards the clustering methodologies used and present our evaluation results. Section 7 concludes this manuscript with some remarks about the future work that is currently underway.