Refinement of Document Clustering by Using NMF

Refinement of Document Clustering by Using NMF* Hiroyuki Shinnou and Minoru Sasaki Department of Computer and Information Sciences, Ibaraki University, 4-12-1 Nakanarusawa, Hitachi, Ibaraki JAPAN 316-8511 {shinnou, msasaki}@mx.ibaraki.ac.jp Abstract. In this paper, we use non-negative matrix factorization (NMF) to refine the document clustering results. NMF is a dimensional reduction method and effective for document clustering, because a term-document matrix is high-dimensional and sparse. The initial matrix of the NMF algorithm is regarded as a clustering result, therefore we can use NMF as a refinement method. First we perform min-max cut (Mcut), which is a powerful spectral clustering method, and then refine the result via NMF. Finally we should obtain an accurate clustering result. However, NMF often fails to improve the given clustering result. To overcome this problem, we use the Mcut object function to stop the iteration of NMF. Keywords: document clustering, Non-negative Matrix Factorization, spectral clustering, initial matrix 1. Introduction In this paper, we use non-negative matrix factorization (NMF) to improve the document clustering result generated by a powerful document clustering method. Using this strategy, we can obtain an accurate document clustering result. Document clustering is a task that divides a given document data set into a number of groups according to document similarity. This is the basic intelligent procedure, and an important factor in text-mining systems, from Berry (2003). Relevant feedback in information retrieval (IR), where retrieved documents are clustered, is a specific application that is actively researched by Hearst et al. (1996), Leuski (2001), Zeng et al. (2001) and Kummamuru (2004). NMF is a dimensional reduction method and an effective document clustering method, because a term-document matrix is high-dimensional and sparse, from Xu et al. (2003). Let X to be a term-document matrix, consisting of m rows (terms) and n columns (documents). If the number of clusters is k, NMF decomposes X to the matrices U and as follows: n m × t V X =UVt where U is , V is and is the transposed matrix of V. The matrix U and V are non- negative. In NMF, each k dimensional column vector in V corresponds to a document. An actual clustering procedure is usually performed using these reduced vectors. However, NMF does not need such a clustering procedure. The reduced vector expresses its cluster by itself, because each column axis of V represents a topic of the cluster. Furthermore, the matrices V and U are m×k n×k t V * This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant- in-Aid for Scientific Research on Priority Areas, “Japanese Corpus”, 19011001, 2007. Copyright 2007 by Hiroyuki Shinnou and Minoru Sasaki. 430 obtained by a simple iteration, from Lee (2000), where the initial matrices and are updated. Therefore, we can regard NMF as a refinement method for a given clustering result, because the matrix V represents a clustering result. U0 0 V In this paper, we use NMF to improve clustering results. Providing NMF with an accurate document clustering result, we can …

Content truncated to 500 words