Fast and effective text mining using linear-time document clustering
Bjornar Larsen, Chinatsu Aone · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · 1999
Clustering is a powerful technique for large-scale topic discovery from text.It involves two phases: first, feature extraction maps each document or record to a point in high-dimensional space, then clustering algorithms automatically group the points into a hierarchy of clusters.We describe an unsupervised, near-linear time text clustering system that offers a number of algorithm choices for each phase.We introduce a methodology for measuring the quality of a cluster hierarchy in terms of F-Measure, and present the results of experiments comparing different algorithms.The evaluation considers some feature selection parameters (tfidfand feature vector length) but focuses on the clustering algorithms, namely techniques from Scatter/Gather (buckshot, fractionation, and split/join) and kmeans.Our experiments suggest that continuous center adjustment contributes more to cluster quality than seed selection does.It follows that using a simpler seed selection algorithm gives a better time/quality tradeoff.We describe a refinement to center adjustment, "vector average damping," that further improves cluster quality.We also compare the near-linear time algorithms to a group average greedy agglomerative clustering algorithm to demonstrate the time/quality tradeoff quantitatively.
Cited by 857 works. doi:10.1145/312129.312186 Open-access PDF
Authors
References
- Some methods for classification and analysis of multivariate observations
- Automatic text processing: the transformation, analysis, and retrieval of information by computer
- Scatter/Gather
- Scatter/Gather: a cluster-based approach to browsing large document collections
- Reexamining the cluster hypothesis
- A study of retrospective and on-line event detection
- Constant interaction-time scatter/gather browsing of very large document collections
- Scatter/gather browsing communicates the topic structure of a very large text collection
- Fast and intuitive clustering of web documents
- Projections for efficient document clustering