Clustering Search Results Based on Formal Concept Analysis

摘要

This study propose a new method based on Formal Concept Analysis (FCA) to group and organize search results. After formal concepts are extracted using FCA, the concepts most relevant to the query are selected and extracted and then a two-level hierarchy is built and presented to the user. We refer the proposed algorithm to as CHC (Conceptual and Hierarchical Clustering). Evaluating the quality of the clustering results is a non-trivial task. Two improved objective metrics of clustering quality, ANCE@K and ANCE@K, are proposed based on NMI (normalized mutual information) and NCE (normalized complementary entropy) metrics but eliminating the biases existed in them. We compare CHC with three other Search Results Clustering (SRC) algorithms: Suffix Tree Clustering (STC), Lingo and Vivisimo, using a comprehensive set of documents obtained from the Open Directory Project hierarchy as benchmark. In addition to comparison based on objective measures, we also subjectively analyze the properties of cluster labels produced by different SRC algorithms. The experimental results show that our method outperforms the other three SRC algorithms and is helpful to the user for browsing and locating the results of interests.