• Features:

First, "spkmeans" is a fast clustering C++ program that fully exploits the sparsity of the data set. At the heart of the program is the (spherical) K-means clustering algorithm, which is enhanced by a technique for significantly reducing the number of  similarity computations required. It ever clustered about 114,000 NSF award abstracts with about 5 minutes on a Sun Ultra10 workstation. And the clustering result is illustrated by a sequence of web pages generated by a Java program called "ClusterBrowser". "spkmeans" clusters both documents and words.

"spkmeans" can also reduce the dimensionality of  the the original word-document matrix through concept decomposition or QR decompostion of the concept vectors. This may be useful for classification and query retrieval.

• Input: Word-document matrix in CCS format. (NOT the documents themselves!!! See how to get the matrix from documents here.)
• Output: The clusters of both documents and words as well as matrices after dimension reduction.

• Example (for just clustering):

Here are the examples of the input files: classic3_col_ccs, classic3_dim, classic3_docs, classic3_row_ccs, classic3_tfn_nz.
And the output looks like: classic3_tfn_doctoclus.3, classic3_tfn_wordtoclus.3

• Code:

The code is released under the GNU Public License (GPL). README.
This program compiles on UNIX, Linux, and Solaris.
The hierarchical version of this program is here.

 
You are welcome to use the code under the terms of the licence for research or commercial purposes, however please acknowledge its use with a citation:

Dhillon, I. S. and Modha, D. M., "Concept Decompositions for Large Sparse Text Data using Clustering", Machine Learning, 42:1, pages 143-175, Jan, 2001.

Dhillon, I. S. and Fan, J. and Guan, Y.,   "Efficient Clustering of Very Large Document Collections", 2000, invited book chapter in Data Mining for Scientific and Engineering Applications, Kluwer Academic Publishers, 2001.

Here is a BiBTeX entry:

@ARTICLE{dhillon:modha:mlj01,
      AUTHOR = {Dhillon, I. S. and Modha, D. S.},
      TITLE = { Concept decompositions for large sparse text data using clustering},
      JOURNAL = {Machine Learning},
      YEAR = {2001},
      MONTH = {Jan},
      VOLUME = {42},
      NUMBER = {1},
      PAGES = {143--175} }

@INCOLLECTION{dhillon:fan:guan00,
      AUTHOR = {Dhillon, I. S. and Fan, J. and Guan, Y.},
      TITLE = {Efficient Clustering of Very Large Document Collections},
      BOOKTITLE = {Data Mining for Scientific and Engineering Applications},
      PUBLISHER = {Kluwer Academic Publishers},
      EDITOR = {R. Grossman, C. Kamath, V. Kumar and R. Namburu},
      YEAR = {2001},
      PAGES = {},
      NOTE = {Invited book chapter}}

Bug reports and comments are appreciated!