Multi-Objective Search Results Clustering

Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 99–108, Dublin, Ireland, August 23-29 2014. Multi-Objective Search Results Clustering Sudipta Acharya Sriparna Saha Indian Institute of Technology Patna Kurji, Patna, Bihar, India {sudipta.pcs13,sriparna}@iitp.ac.in Jose G. Moreno Ga¨el Dias Normandie University - CNRS GREYC Caen, France first.last@unicaen.fr Abstract Most web search results clustering (SRC) strategies have predominantly studied the definition of adapted representation spaces to the detriment of new clustering techniques to improve perfor- mance. In this paper, we define SRC as a multi-objective optimization (MOO) problem to take advantage of most recent works in clustering. In particular, we define two objective functions (compactness and separability), which are simultaneously optimized using a MOO-based simu- lated annealing technique called AMOSA. The proposed algorithm is able to automatically detect the number of clusters for any query and outperforms all state-of-the-art text-based solutions in terms of Fβ-measure and Fb3-measure over two gold standard data sets. 1 Introduction Web search results clustering (SRC), also known as post-retrieval clustering or ephemeral clustering has received much attention for the past twenty years for easing up user’s effort in web browsing. The key idea behind SRC systems is to return some meaningful labeled clusters from a set of web documents (or web snippets) retrieved from a search engine for a given query. Recently, SRC strategies have been focusing on the introduction of external (exogenous) knowledge to better capture semantics between documents (Scaiella et al., 2012; Marco and Navigli, 2013). Although this research direction has evidenced competitive results, the proposed clustering techniques are based on a single cluster quality measure, which must reflect alone the goodness of a given partitioning. These techniques are usually referred to as single objective optimizations (SOO). In this paper, we hypothesize that improved clustering can be achieved by defining different objective functions over well-known data representations. As such, our study aims to focus on new clustering issues for SRC instead of defining new representation spaces. Recent studies (Maulik et al., 2011) have shown that clustering can be defined as a multi-objective optimization (MOO) problem. Within the context of SRC, we propose to define two objective functions (compactness and separability), which are simultaneously optimized using a MOO-based simulated an- nealing technique called AMOSA (Bandyopadhyay et al., 2008). In order to draw conclusive remarks, we present an exhaustive evaluation where our MOO algorithm (MOO-clus) is compared to the most competitive text-based (endogenous) SRC algorithms: STC (Zamir and Etzioni, 1998), LINGO (Osinski and Weiss, 2005), OPTIMSRC (Carpineto and Romano, 2010) and GK-means (Moreno et al., 2013). Experiments are run over two different gold standard data sets (ODP- 239 and MORESQUE) for two clustering evaluation metrics (Fβ-measure and Fb3-measure). Results show that MOO-clus outperforms all text-based solutions and approaches performances of knowledge driven strategies (Scaiella et al., 2012). In this paper, our main contributions are: • The first1 attempt to solve SRC by defining multiple objective functions, • A new MOO clustering algorithm for SRC, which automatically determines the number of clusters, This …

Content truncated to 500 words