Text Clustering

General
Hierarchical Text Clustering
Clustering Theory
Visualization Using Clustering
Feature Selection for Clustering



General

Larson, Ray R. 1998. Content Analysis. <http://www.sims.berkeley.edu/courses/is202/f98/Lecture15/index.htm>. <http://www.sims.berkeley.edu/courses/is202/f98/Lecture16/index.htm>.
Aslam, J., K. Pelekhov, and Daniela Rus. 1997. Generating, Visualizing and Evaluating High Quality Clusters for Information Organization. Technical report Dartmouth PCS-TR97-319. <http://www.cs.dartmouth.edu/reports/abstracts/TR97-319/>.

[abstract] We present and analyze the star clustering algorithm. We discuss an implementation of this algorithm that supports browsing and document retrieval through information organization. We define three parameters for evaluating a clustering algorithm to measure the topic separation and topic aggregation achieved by the algorithm. In the absence of benchmarks, we present a method for randomly generating clustering data. Data from our user study shows evidence that the star algorithm is effective for organizing information.
Aslam, J., K. Pelekhov, and Daniela Rus. 1997. Computing Dense Clusters On-line for Information Organization. Technical report Dartmouth PCS-TR97-324. <http://www.cs.dartmouth.edu/reports/abstracts/TR97-324/>.

[abstract] We present and analyze the off-line star algorithm for clustering static information systems and the on-line star algorithm for clustering dynamic information systems. These algorithms partition a document collection into a number of clusters that is naturally induced by the collection. We show a lower bound on the accuracy of the clusters produced by these algorithms. We use the random graph model to show that both star algorithms produce correct clusters in time Theta(V + E). Finally, we provide data from extensive experiments.
Boley, Daniel, Maria Gini, Robert Gross, Eui-Hong (Sam) Han, Kyle Hastings, George Karypis, Vipin Kumar, Bamshad Mobasher, and Jerome Moore. 1999. "Partitioning-Based Clustering for Web Document Categorization", To appear in Decision Support Systems Journal. <ftp://ftp.cs.umn.edu/dept/users/kumar/dss-agent.ps>.

[abstract] Clustering techniques have been used by many intelligent software agents in order to retrieve, filter, and categorize documents available on the World Wide Web. Clustering is also useful in extracting salient features of related web documents to automatically formulate queries and search for other similar documents on the Web. Traditional clustering algorithms either use a priori knowledge of document structures to define a distance or similarity among these documents, or use probabilistic techniques such as Bayesian classification. Many of these traditional algorithms, however, falter when the dimensionality of the feature space becomes high relative to the size of the document space. In this paper, we introduce two new clustering algorithms that can effectively cluster documents, even in the presence of a very high dimensional feature space. These clustering techniques, which are based on generalizations of graph partitioning, do not require pre-specified ad hoc distance functions, and are capable of automatically discovering document similarities or associations. We conduct several experiments on real Web data using various feature selection heuristics, and compare our clustering schemes to standard distance-based techniques, such as hierarchical agglomeration clustering, and Bayesian classification methods, such as AutoClass.
Goldszmidt, Moises, and Mehran Sahami. 1998. A Probabilistic Approach to Full-Text Document Clustering. Technical Report ITAD-433-MS-98-044, SRI International. <http://robotics.stanford.edu/users/sahami/papers-dir/gm-clustering.ps> or <http://www-diglib.stanford.edu/cgi-bin/WP/get/SIDL-WP-1998-0091>.

[abstract] In addressing the issue of text document clustering, a suitable function for measuring the distance between documents is needed. In this paper we explore a function for scoring document similarity based on probabilistic considerations: similarity is scored according to the expectation of the same words appearing in two documents. This score enables the investigation of different smoothing methods for estimating the probability of a word appearing in a document for purposes of clustering. Our experimental results show that these different smoothing methods may be more or less effective depending on the degree of separability between the clusters. Furthermore, we show that the cosine coefficient widely used in information retrieval can be associated with a particular form of probabilistic smoothing in our model. We also introduce a specific scoring function that outperforms the cosine coefficient and its extensions such as TFIDF weighting in our experiments with document clustering tasks. This new scoring is based on normalizing (in the probabilistic sense) the cosine similarity score and adding a scaling factor based on the characteristics of the corpus being clustered. Finally our experiments indicate that our model, which assumes an asymmetry between positive (word appearance) and negative (word non-appearance) information in the document clustering task, outperforms standard mixture models that weight such information equally.
Han, Eui-Hong (Sam), Daniel Boley, Maria Gini, Robert Gross, Kyle Hastings, George Karypis, Vipin Kumar, Bamshad Mobasher, and Jerome Moore. 1998. "WebACE: A Web Agent for Document Categorization and Exploartion", Proceedings of the 2nd International Conference on Autonomous Agents (Agents'98). <ftp://ftp.cs.umn.edu/dept/users/kumar/webace.ps>.

[abstract] We present WebACE, an agent for exploring and categorizing documents on the World Wide Web based on a user profile. The heart of the agent is an unsupervised categorization of a set of documents, combined with a process for generating new queries that is used to search for new related documents and for filtering the resulting documents to extract the ones most closely related to the starting set. The document categories are not given a priori. We present the overall architecture and describe two novel algorithms which provide significant improvement over Hierarchical Agglomeration Clustering and AutoClass algorithms and form the basis for the query generation and search component of the agent. We report on the results of our experiments comparing these new algorithms with more traditional clustering algorithms and we show that our algorithms are fast and scalable.
Han, Eui-Hong (Sam), George Karypis, Vipin Kumar, and Bamshad Mobasher. 1998. "Hypergraph Based Clustering in High-Dimensional Data Sets: A Summary of Results", Bulletin of the Technical Committee on Data Engineering, 21(1). <ftp://ftp.cs.umn.edu/dept/users/kumar/cluster-hyper-dim.ps>.

[abstract] Clustering of data in a large dimension space is of a great interest in many data mining applications. In this paper, we propose a method for clustering of data in a high dimensional space based on a hypergraph model. In this method, the relationship present in the original data in high dimensional space are mapped into a hypergraph. A hyperedge represents a relationship (affinity) among subsets of data and the weight of the hyperedge reflects the strength of this affinity. A hypergraph partitioning algorithm is used to find a partitioning of the vertices such that the corresponding data items in each partition are highly related and the weight of the hyperedges cut by the partitioning is minimized. We present results of experiments on two different data sets: S&P500 stock data for the period of 1994-1996 and protein coding data. These experiments demonstrate that our approach is applicable and effective in high dimensional datasets.
Han, Eui-Hong (Sam), George Karypis, Vipin Kumar, and Bamshad Mobasher. 1997. Clustering In A High-Dimensional Space Using Hypergraph Models. Technical Report # 97-019, Department of Computer Science and Engineering, University of Minnesota. <ftp://ftp.cs.umn.edu/dept/users/kumar/cluster-hyper-dim.ps>.

[abstract] Clustering of data in a large dimension space is of a great interest in many data mining applications. Most of the traditional algorithms such as K-means or AutoClass fail to produce meaningful clusters in such data sets even when they are used with well known dimensionality reduction techniques such as Principal Component Analysis and Latent Semantic Indexing. In this paper, we propose a method for clustering of data in a high dimensional space based on a hypergraph model. The hypergraph model maps the relationship present in the original data in high dimensional space into a hypergraph. A hyperedge represents a relationship (affinity) among subsets of data and the weight of the hyperedge reflects the strength of this affinity. A hypergraph partitioning algorithm is used to find a partitioning of the vertices such that the corresponding data items in each partition are highly related and the weight of the hyperedges cut by the partitioning is minimized. We present results of experiments on three different data sets: S&P500 stock data for the period of 1994-1996, protein coding data, and Web document data. Wherever applicable, we compared our results with those of AutoClass and K-means clustering algorithm on original data as well as on the reduced dimensionality data obtained via Principal Component Analysis or Latent Semantic Indexing scheme. These experiments demonstrate that our approach is applicable and effective in a wide range of domains. More specifically, our approach performed much better than traditional schemes for high dimensional data sets in terms of quality of clusters and runtime. Our approach was also able to filter out noise data from the clusters very effectively without compromising the quality of the clusters.
Moore, Jerome, Han, Eui-Hong (Sam), Daniel Boley, Maria Gini, Robert Gross, Kyle Hastings, George Karypis, Vipin Kumar, and Bamshad Mobasher. 1997. "Web Page Categorization and Feature Selection Using Association Rule and Principal Component Clustering", Workshop on Information Technologies and Systems. <ftp://ftp.cs.umn.edu/dept/users/kumar/web-wits.ps>.

[abstract] Clustering techniques have been used by many intelligent software agents in order to retrieve, filter, and categorize documents available on the World Wide Web. Clustering is also useful in extracting salient features of related web documents to automatically formulate queries and search for other similar documents on the Web. Traditional clustering algorithms either use a priori knowledge of document structures to define a distance or similarity among these documents, or use probabilistic techniques such as Bayesian classification. Many of these traditional algorithms, however, falter when the dimensionality of the feature space becomes high relative to the size of the document space. In this paper, we introduce two new clustering algorithms that can effectively cluster documents, even in the presence of a very high dimensional feature space. These clustering techniques, which are based on generalizations of graph partitioning, do not require pre-specified ad hoc distance functions, and are capable of automatically discovering document similarities or associations. We conduct several experiments on real Web data using various feature selection heuristics, and compare our clustering schemes to standard distance-based techniques, such as hierarchical agglomeration clustering, and Bayesian classification methods, AutoClass.
Han, Eui-Hong (Sam), George Karypis, Vipin Kumar, and Bamshad Mobasher. 1997. "Clustering Based On Association Rule Hypergraphs", SIGMOD'97 Workshop on Research Issues on Data Mining and Knowledge Discovery. <ftp://ftp.cs.umn.edu/dept/users/kumar/cluster-hyper-pos.ps>.

[abstract] Clustering of data in a large dimension space is of a great interest in many data mining applications. Most of the traditional algorithms such as K-means or AutoClass fail to produce meaningful clusters in such data sets even when they are used with well known dimensionality reduction techniques such as Principal Component Analysis and Latent Semantic Indexing. In this paper, we propose a method for clustering of data in a high dimensional space based on a hypergraph model. The hypergraph model maps the relationship present in the original data in high dimensional space into a hypergraph. A hyperedge represents a relationship (affinity) among subsets of data and the weight of the hyperedge reflects the strength of this affinity. A hypergraph partitioning algorithm is used to find a partitioning of the vertices such that the corresponding data items in each partition are highly related and the weight of the hyperedges cut by the partitioning is minimized. We present results of experiments on three different data sets: S&P500 stock data for the period of 1994-1996, protein coding data, and Web document data. Wherever applicable, we compared our results with those of AutoClass and K-means clustering algorithm on original data as well as on the reduced dimensionality data obtained via Principal Component Analysis or Latent Semantic Indexing scheme. These experiments demonstrate that our approach is applicable and effective in a wide range of domains. More specifically, our approach performed much better than traditional schemes for high dimensional data sets in terms of quality of clusters and runtime. Our approach was also able to filter out noise data from the clusters very effectively without compromising the quality of the clusters.
Joachims, T. 1997. "A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization", Proceedings of the Fourteenth International Conference on Machine Learning (ICML'97). <http://www-ai.cs.uni-dortmund.de/DOKUMENTE/joachims_97a.pdf>.
[abstract] The Rocchio relevance feedback algorithm is one of the most popular and widely applied learning methods from information retrieval. Here, a probabilistic analysis of this algorithm is presented in a text categorization framework. The analysis gives theoretical insight into the heuristics used in the Rocchio algorithm, particularly the word weighting scheme and the similarity metric. It also suggests improvements which lead to a probabilistic variant of the Rocchio classifier. The Rocchio classifier, its probabilistic variant, and a naive Bayes classifier are compared on six text categorization tasks. The results show that the probabilistic algorithms are preferable to the heuristic Rocchio classifier not only because they are more well-founded, but also because they achieve better performance.
Martin, J. 1995. "Clustering Full Text Documents", Proceedings of the IJCAI-95 Workshop on Data Engineering for Inductive Learning. <http://ai.iit.nrc.ca/DEIL/martin.ps.Z>.

[abstract] An index or topic hierarchy of full-text documents can organize a domain and speed information retrieval. Traditional indexes, like the Library of Congress system or Dewey Decimal system, are generated by hand, updated infrequently, and applied inconsistently. With machine learning, they can be generated automatically, updated as new documents arrive, and applied consistently. Despite the appeal of automatic indexing, organizing natural language documents is a difficult balance between what we want to do and what we can do. This paper describes an application of clustering to full-text databases, presents a new clustering method, and discusses the data engineering necessary to use clustering for this application. In particular, the paper deals with engineering the feature set to permit learning and otherwise engineering the data to match assumptions underlying the learning algorithm.
Sch?tze, H., and C. Silverstein. 1997. "A Comparison of Projections for Efficient Document Clustering", Proceedings of the Twentieth Annual ACM SIGIR Conference on Research and Development in Information Retrieval: 74-81. <http://www-cs-students.stanford.edu/~csilvers/papers/metrics-sigir.ps>.

[abstract] Clustering is increasing in importance, but linear- and even constant-time clustering algorithms are often too slow for real-time applications. A simple way to speed up clustering is to speed up the distance calculations at the heart of clustering routines. We study two techniques for improving the cost of distance calculations, LSI and truncation, and determine both how much these techniques speed up clustering and how much they affect the quality of the resulting clusters. We find that the speed increase is significant while -- surprisingly -- the quality of clustering is not adversely affected. We conclude that truncation yields clusters as good as those produced by full-profile clustering while offering a significant speed advantage.
Pedersen, J., and C. Silverstein. 1997. "Almost-Constant-Time Clustering of Arbitrary Corpus Subsets", Proceedings of the Twentieth Annual ACM SIGIR Conference on Research and Development in Information Retrieval: 60-66. <http://www-cs-students.stanford.edu/~csilvers/papers/sm-sigir.ps>.

[abstract] Methods exist for constant-time clustering of corpus subsets selected via Scatter/Gather browsing [Cutting et al., 1993]. In this paper we expand on those techniques, giving an algorithm for almost-constant-time clustering of arbitrary corpus subsets. This algorithm is never slower than clustering the document set from scratch, and for medium-sized and large sets it is significantly faster. This algorithm is useful for clustering arbitrary subsets of large corpora -- obtained, for instance, by a boolean search -- quickly enough to be useful in an interactive setting.
Ungar, L.H., and D.P. Foster. 1998. "Clustering Methods for Collaborative Filtering", Proceedings of the AAAI Workshop on Recommendation Systems. <http://www.cis.upenn.edu/~ungar/papers/clust.ps>.

[abstract] Grouping people into clusters based on the items they have purchased allows accurate recommendations of new items for purchase: if you and I have liked many of the same movies, then I will probably enjoy other movies that you like. Recommending items based on similarity of interest (a.k.a. collaborative filtering) is attractive for many domains: books, CDs, movies, etc., but does not always work well. Because data are always sparse -- any given person has seen only a small fraction of all movies -- much more accurate predictions can be made by grouping people into clusters with similar movies and grouping movies into clusters which tend to be liked by the same people. Finding optimal clusters is tricky because the movie groups should be used to help determine the people groups and visa versa. We present a formal statistical model of collaborative filtering, and compare different algorithms for estimating the model parameters including variations of K-means clustering and Gibbs Sampling. This formal model is easily extended to handle clustering of objects with multiple attributes.



Hierarchical Text Clustering

Hofmann, T.. 1999. "The Cluster-Abstraction Model: Unsupervised Learning of Topic Hierarchies from Text Data", Proceedings of the IJCAI'99. <http://www.icsi.berkeley.edu/~hofmann/Papers/Hofmann-IJCAI99.pdf>.

[abstract] This paper presents a novel statistical latent class model for text mining and interactive information access. The described learning architecture, called Cluster-Abstraction Model (CAM), is purely data driven and utilizes context-specific word occurrence statistics. In an intertwined fashion, the CAM extracts hierarchical relations between groups of documents as well as an abstractive organization of keywords. An annealed version of the Expectation-Maximization (EM) algorithm for maximum likelihood estimation of the model parameters is derived. The benefits of the CAM for interactive retrieval and automated cluster summarization are investigated experimentally.
Karypis, George, Eui-Hong (Sam) Han, and Vipin Kumar. 1999. "CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling", IEEE Computer: Special Issue on Data Analysis and Mining, 32(8), 68-75. <ftp://ftp.cs.umn.edu/dept/users/kumar/chameleon.ps>.

[abstract] Clustering in data mining is a discovery process that groups a set of data such that the intracluster similarity is maximized and the intercluster similarity is minimized. Existing clustering algorithms, such as K-means, PAM, CLARANS, DBSCAN, CURE, and ROCK are designed to find clusters that fit some static models. These algorithms can breakdown if the choice of parameters in the static model is incorrect with respect to the data set being clustered, or if the model is not adequate to capture the characteristics of clusters. Furthermore, most of these algorithms breakdown when the data consists of clusters that are of diverse shapes, densities, and sizes. In this paper, we present a novel hierarchical clustering algorithm called CHAMELEON that measures the similarity of two clusters based on a dynamic model. In the clustering process, two clusters are merged only if the inter-connectivity and closeness (proximity) between two clusters are high relative to the internal inter-connectivity of the clusters and closeness of items within the clusters. The merging process using the dynamic model presented in this paper facilitates discovery of natural and homogeneous clusters. The methodology of dynamic modeling of clusters used in CHAMELEON is applicable to all types of data as long as a similarity matrix can be constructed. We demonstrate the effectiveness of CHAMELEON in a number of data sets that contain points in 2D space, and contain clusters of different shapes, densities, sizes, noise, and artifacts. Experimental results on these data sets show that CHAMELEON can discover natural clusters that many existing state-of-the art clustering algorithms fail to find.
Karypis, George, Eui-Hong (Sam) Han, and Vipin Kumar. 1999. Multilevel Refinement for Hierarchical Clustering. Technical Report # 99-020, Department of Computer Science and Engineering, University of Minnesota. <ftp://ftp.cs.umn.edu/dept/users/kumar/cluster-multi-refine.ps>.

[abstract] Clustering in data mining is a discovery process that groups a set of data such that the intracluster similarity is maximized and the intercluster similarity is minimized. Existing clustering algorithms, such as K-means, PAM, CLARANS, DBSCAN, CURE, and ROCK are designed to find clusters that fit some static models. These algorithms can breakdown if the choice of parameters in the static model is incorrect with respect to the data set being clustered, or if the model is not adequate to capture the characteristics of clusters. Furthermore, most of these algorithms breakdown when the data consists of clusters that are of diverse shapes, densities, and sizes. In this paper, we present a novel hierarchical clustering algorithm called CHAMELEON that measures the similarity of two clusters based on a dynamic model. In the clustering process, two clusters are merged only if the inter-connectivity and closeness (proximity) between two clusters are high relative to the internal inter-connectivity of the clusters and closeness of items within the clusters. The merging process using the dynamic model presented in this paper facilitates discovery of natural and homogeneous clusters. The methodology of dynamic modeling of clusters used in CHAMELEON is applicable to all types of data as long as a similarity matrix can be constructed. We demonstrate the effectiveness of CHAMELEON in a number of data sets that contain points in 2D space, and contain clusters of different shapes, densities, sizes, noise, and artifacts. Experimental results on these data sets show that CHAMELEON can discover natural clusters that many existing state-of-the art clustering algorithms fail to find.
Sahami, M., Yusufali, S., and Baldonado, M.Q.W. 1998. "SONIA: A Service for Organizing Networked Information Autonomously", Digital Libraries 98: Proceedings of the Third ACM Conference on Digital Libraries, 200-209. <http://robotics.stanford.edu/users/sahami/papers-dir/dl98-sonia.ps>.

[abstract] The recent explosion of on-line information in Digital Libraries and on the World Wide Web has given rise to a number of query-based search engines and manually constructed topical hierarchies. However, these tools are quickly becoming inadequate as query results grow incomprehensibily large and manual classification in topic hierarchies creates an immense bottleneck. We address these problems with a system for topical information space navigation that combines query-based and taxonomic systems. We employ machine learning techniques to create dynamic document categorizations based on the full-text of articles that are retrieved by users' queries. Our system, name SONIA (Service for Organizing Networked Information Autonomously), has been implemented as part of the Stanford Digital Libraries Testbed. It employs a combination of technologies that take the results of queries to networked information sources and, in real-time, automatically retrieve, parse and organize these documents into coherent categories for presentation to the user. Moreover, the system can then save such document organizations in user profiles which can then be used to help classify future query results by the same user. SONIA uses a multi-tier approach to extracting relevant terms from documents as well as statistical clustering methods to determine potential topics within a document collection. It also makes use of Bayesian classification techniques to classify new documents within an existing categorization scheme. In this way, it allows navigate the results of a query at a more topical level than having to examine each document text separately.



Clustering Theory

Bhatia, S.K., and Deogun, J.S. 1998. "Conceptual clustering in information retrieval", IEEE Transactions on Systems, Man and Cybernetics, Part B, 427-436.

[abstract] Clustering is used in information retrieval systems to enhance the efficiency and effectiveness of the retrieval process. Clustering is achieved by partitioning the documents in a collection into classes such that documents that are associated with each other are assigned to the same cluster. This association is generally determined by examining the index term representation of documents or by capturing user feedback on queries on the system. In cluster-oriented systems, the retrieval process can be enhanced by employing characterization of clusters. In this paper, we present the techniques to develop clusters and cluster characterizations by employing user viewpoint. The user viewpoint is elicited through a structured interview based on a knowledge acquisition technique, namely personal construct theory. It is demonstrated that the application of personal construct theory results in a cluster representation that can be used during query as well as to assign new documents to the appropriate clusters.
Buhmann, J, and T. Hofmann. 1996. Pairwise data clustering by deterministic Annealing. Technical Report IAI-TR-95-7, Institut f? Informatik III, University of Bonn. <http://www-dbv.cs.uni-bonn.de/abstracts/buhmann.IAI-TR-95-7.html>.

[abstract] Partitioning a data set and extracting hidden structure from the data arises in different application areas of pattern recognition and image processing. Pairwise data clustering is a combinatorial optimisation method for data grouping which extracts structure from proximity data. We descibe a deterministic annealing approach to pairwise data clustering which shares the robustness properties of maximum entropy inference. The resulting Gibbs probability distributions are estimated by meanfield approximation, a well-known technique from statistical physics. A new algorithm to group dissimilarity data and to simultanously embed these data in a Euclidian vector space is discussed which can be used for dimension reduction and data visualisation. The suggested algorithms have been implemented to analyse dissimilarity data from protein analysis and from linguistics. Furthermore, pairwise data clustering is used to segment textured images.
Hofmann, T., and Jan Puzicha. 1998. Statistical Models for Co-occurrence Data. AI Memo 1625, CBCL Memo 159, Artificial Intelligence Laboratory and Center for Biological and Computational Learning, MIT. <http://www.icsi.berkeley.edu/~hofmann/Papers/HofmannPuzicha-AIM-1625.pdf>.

[abstract] Modeling and predicting co-occurrences of events is a fundamental problem of unsupervised learning. In this contribution we develop a statistical framework for analyzing co-occurrence data in a general setting where elementary observations are joint occurrences of pairs of abstract objects from two finite sets. The main challenge for statistical models in this context is to overcome the inherent data sparseness and to estimate the probabilities for pairs which were rarely observed or even unobserved in a given sample set. Moreover, it is often of considerable interest to extract grouping structure or to find a hierarchical data organization. Anovel family of mixture models is proposed which explain the observed data by a finite number of shared aspects or clusters. Thisprovides a common framework for statistical inference and structure discovery and also includes several recently proposed models as special cases. Adopting the maximum likelihood principle, EM algorithms are derived to fit the model parameters. We develop improved versions of EM which largely avoid over-fitting problems and overcome the inherent locality of EM{based optimization. Among the broad variety of possible applications, e.g., in information retrieval, natural language processing, data mining, and computer vision, we have chosen document retrieval, the statistical analysis of noun/adjective co-occurrence and the unsupervised segmentation of textured images to test and evaluate the proposed algorithms.
Kaski, S. 1998. "Dimensionality reduction by random mapping: fast similarity computation for clustering", Proceedings of the 1998 IEEE International Joint Conference on Neural Networks Proceedings, 413-418.

[abstract] When the data vectors are high-dimensional it is computationally infeasible to use data analysis or pattern recognition algorithms which repeatedly compute similarities or distances in the original data space. It is therefore necessary to reduce the dimensionality before, for example, clustering the data. If the dimensionality is very high, like in the WEBSOM method which organizes textual document collections on a self-organizing map, then even the commonly used dimensionality reduction methods like the principal component analysis may be too costly. It is demonstrated that the document classification accuracy obtained after the dimensionality has been reduced using a random mapping method will be almost as good as the original accuracy if the final dimensionality is sufficiently large (about 100 out of 6000). In fact, it can be shown that the inner product (similarity) between the mapped vectors follows closely the inner product of the original vectors.
Miyamoto, M. 1998. "An Overview and New Methods in Fuzzy Clustering", Knowledge-Based Intelligent Electronic Systems 1998: Proceedings of the Second International Conference on Knowledge-Based Intelligent Electronic Systems (KES'98), 33-40.

[abstract] Principal methods in nonhierarchical and hierarchical fuzzy clustering are overviewed. In particular, the method of fuzzy c-means is focused upon and recent algorithms in fuzzy c-means are described. It is shown that the concept of regularization plays an important role in the fuzzy c-means. Classification functions induced from fuzzy clustering are discussed and variations of the standard fuzzy c-means are introduced. The hierarchical classification based on the transitive closure is equivalent to the single link method of agglomerative clustering. The roles of the concept of fuzziness in nonhierarchical and hierarchical methods are thus contrasted.



Visualization Using Clustering

Song, Min. 1998. "BiblioMapper: a cluster-based information visualization technique", Proceedings of the IEEE Symposium on Information Visualization, 1998, 130-136.

[abstract] The purpose of the paper is to develop a visualization system of a document space, called BiblioMapper, for CISI collections, one of the bibliographic databases available on the Internet. The major function of BiblioMapper is to visualize the document space with a cluster-based visualization technique. The cluster-based visualization technique assembles a set of documents according to semantic similarities. One advantage of this technique is that users are able to focus on and assess each cluster and the documents which the cluster comprises according to their information needs.
Zamir, Oren, and Oren Etzioni. 1999. "Grouper: A dynamic clustering interface to web search results", Proceedings of the WWW8 Conference. <http://www8.org/w8-papers/3a-search-query/dynamic/dynamic.html>.

[abstract] Users of Web search engines are often forced to sift through the long ordered list of document "snippets" returned by the engines. The IR community has explored document clustering as an alternative method of organizing retrieval results, but clustering has yet to be deployed on most major search engines. The NorthernLight search engine organizes its output into "custom folders" based on pre-computed document labels, but does not reveal how the folders are generated or how well they correspond to users' interests. In this paper, we introduce Grouper – an interface to the results of the HuskySearch meta-search engine, which dynamically groups the search results into clusters labeled by phrases extracted from the snippets. In addition, we report on the first empirical comparison of user Web search behavior on a standard ranked-list presentation versus a clustered presentation. By analyzing HuskySearch logs, we are able to demonstrate substantial differences in the number of documents followed, and in the amount of time and effort expended by users accessing search results through these two interfaces.



Feature Selection for Clustering

Devaney, M., and Ram, A. 1997. "Efficient feature selection in conceptual clustering", In Proceedings of the Fourteenth International Conference on Machine Learning (ICML-97). <http://www.cc.gatech.edu/aimosaic/students/markd/papers/icml-97/icml-97.html>.

[abstract] Feature selection has proven to be a valuable technique in supervised learning for improving predictive accuracy while reducing the number of attributes considered in a task. We investigate the potential for similar benefits in an unsupervised learning task, conceptual clustering. The issues raised in feature selection by the absence of class labels are discussed and an implementation of a sequential feature selection algorithm based on an existing conceptual clustering system is described. Additionally, we present a second implementation which employs a technique for improving the efficiency of the search for an optimal description and compare the performance of both algorithms.
Smith, J.E., Fogarty, T.C., and Johnson, I.R. 1994. "Genetic Feature Selection for Clustering and Classification", Proceedings of the IEE Colloquium on Genetic Algorithms in Image Processing & Vision, London 1994, 130-136. <http://docs.dcs.napier.ac.uk/DOCS/GET/sharpe94a/document.html>.