Document Clustering with Grouping and Chaining Algorithms

Document Clustering with Grouping and Chaining Algorithms Yllias Chali and Soufiane Noureddine Department of Computer Science, University of Lethbridge Abstract. Document clustering has many uses in natural language tools and applications. For instance, summarizing sets of documents that all describe the same event requires first identifying and grouping those documents talking about the same event. Document clustering involves dividing a set of documents into non-overlapping clusters. In this paper, we present two document clustering algorithms: grouping algorithm, and chaining algorithm. We compared them with k-means and the EM algo- rithms. The evaluation results showed that our two algorithms perform better than the k-means and EM algorithms in different experiments. 1 Introduction Document clustering has many uses in natural language tools and applications. For instance, summarizing sets of documents that all describe the same event requires first identifying and grouping those documents talking about the same event. Document clustering involves dividing a set of texts into non-overlapping clusters, where documents in a cluster are more similar to one another than to documents in other clusters. The term more similar, when applied to clustered documents, usually means closer by some measure of proximity or similarity. According to Manning and Schutze [1], there are two types of structures pro- duced by clustering algorithms, hierarchical clustering and flat or non- hierarchical clustering. Flat clustering are simply groupings of similar objects. Hierarchical clustering is a tree of subclasses which represent the cluster that contains all the objects of its descendants. The leaves of the tree are the individ- ual objects of the clustered set. In our experiments, we used the non-hierarchical clustering k-means and EM [2] and our own clustering algorithms. There are several similarity measures to help find out groups of related doc- uments in a set of documents [3]. We use identical word method and semantic relation method to assign a similarity score to each pair of compared texts. For the identical word method, we use k-means algorithm, the EM algorithm, and our own grouping algorithm to cluster the documents. For the semantic relation method, we use our own grouping algorithm and chaining algorithm to do the clustering job. We choose WordNet 1.6 as our background knowledge. WordNet consists of synsets gathered in a hypernym/hyponym hierarchy [4]. We use it to get word senses and to evaluate the semantic relations between word senses. R. Dale et al. (Eds.): IJCNLP 2005, LNAI 3651, pp. 280–291, 2005. c ⃝ Springer-Verlag Berlin Heidelberg 2005 Document Clustering with Grouping and Chaining Algorithms 281 2 Identical Word Similarity To prepare the texts for the clustering process using identical word similarity, we perform the following steps on each of the selected raw texts: 1. Preprocessing which consists in extracting file contents from the raw texts, stripping special characters and numbers, converting all words to lower cases and removing stopwords, and converting all plural forms to singular forms. 2. Create document word vectors: each document was processed to record the unique words and their frequencies. We built the local word …

Content truncated to 500 words