Article Preview
Top1. Introduction
In text analytics (Srivastava & Sahami 2009), document clustering refers to the problem of automatically grouping documents into different groups (known as clusters), such that documents in one cluster are similar to each other while being dissimilar from the ones in a different cluster. Typically, the dataset is represented using the vector model in which a set of m documents with n unique words form an m x n document-word matrix (Baeza-Yates & Ribeiro-Neto, 2011). An entry ij in the matrix denotes the frequency of the word j in document i.
Document clustering methods can be categorized into two approaches, viz., partitional and hierarchical clustering. Partitional or flat clustering directly divides the set of documents into different clusters. Hierarchical clustering on the other hand creates a tree-like structure from the documents. Nodes at different levels of the tree constitute clustering at that level. The hierarchical agglomerative clustering (HAC) combines clusters from lower levels into clusters at higher levels (Croft, 1977, Willett, 1988). For example, four clusters at a level are combined to get two clusters at a level above it. The similarity between clusters is first computed to decide which clusters should be combined together. Variants of HAC based on how the cluster similarity is computed have been proposed such as the ones based on single-linkage, complete-linkage, and group average linkage. The top-most level of the tree has one cluster consisting of all documents while the lower-most level comprises of each document belonging to a cluster of its own. Document clustering with a desired number of clusters can be obtained by extracting the clusters from an appropriate level in the tree.
Amongst the partitional document clustering approaches, one of the most popular methods is to apply k-means clustering (Jain, 2010) to the set of documents, which minimizes the sum of squared distances between documents and cluster centroids. Other approaches such as Naive Bayes or Gaussian mixture model define a probabilistic model over the document corpus and attempt to fit the model using maximum likelihood (Baker & McCallum, 1998, Liu et al., 2002). The problem with these approaches is that they make a strong assumption about the documents. For instance, k-means assumes compactness of data, Naive Bayes assumes independence of words, while Gaussian model assumes that the underlying data distribution is normal. These assumptions might not necessarily hold true and hence limit the applicability of these approaches. There have also been methods proposed based on non-negative matrix factorization (NMF) (Xu et al., 2003, Huang et al., 2011) where the given data matrix is factorized into other matrices to yield document clusters. NMF based methods are iterative in nature, need to be run many times, and might not be applicable to realistic datasets.
As can be seen from the above brief discussion, although a lot of attention has been devoted to document clustering, all of these methods are completely unsupervised in nature. That is, they are unable to incorporate any domain knowledge that might be available to guide the clustering process. A publishing company interested in clustering of books might have information on a few books that should always be clustered together (e.g. two children’s books), and some other books that should never be clustered together (e.g. a book for mature audience and children’s book) regardless of the similarity measure. An unsupervised document clustering algorithm clusters documents purely based on the similarity between them as defined by the previously mentioned vector model. Two documents meant for different kinds of audience may get clustered together as they might have common set of words. Similarly, two documents that are meant to be clustered together might never get clustered together due to dissimilarity between words appearing in them. From a text analytics perspective, it is very important for a document clustering algorithm to incorporate any domain knowledge that might be available from the experts.