In this paper we present our system and experiments at the Third Web People Search Workshop (WePS-3) task for clustering web people search documents in English. In our experiments we used a simple approach with three algorithms: Lingo, Hierachical Agglomerative Clustering (HAC), and a 2-step HAC algorithm. We also present the results and initial conclusions in the context of the WePS-3 Task 1 for clustering. We obtained best results with HAC and 2-step HAC algorithms.
1.1
The development data we used for WePS-3 is based on the test data of WePS-2
Clustering Task [
The test data for WePS-3 was composed of 300 person names and 200 web documents for each name. As the WePS organizers did in WePS-2, some person names were obtained from the following sources: US Census (50), Wikipedia (50) and Computer Science Program Committee lists (50). In addition to that, the organizers provided names for which at least one person is an attorney (50), corporate executive (50) or realtor (50). For each name the top 200 web search results from Yahoo! were provided (URL, HTML pages, search snippets and ranking information).
The system architecture has two phases that are performed sequentially: HTML Cleaning and Clustering. The HTML cleaning phase consists in to convert HTML documents into plain text. We used the existing HTMLParser1 (version 1.6) open-source software to perform this task. For Clustering phase we used several algorithms that are described below: Lingo, Hierarchical Agglomerative Clustering (HAC), and 2-steps HAC. 2.1
Lingo is an algorithm that combines Phrase Discovery (detection of topics and
phrases) and Latent Semantic Indexing to organize web search results in groups
based on their content [
Lingo uses the Vector Space Model and Singular Value Decomposition to nd the labels of the clusters. It uses 3 methods of Natural Language Processing: Stemming, stop-words, and textual segmentation heuristics. Using stemming and stop-words according Lingo developers is important when we are working with small textual information and some noise (like working with snippets).
The most used parameters for the tuning of the Lingo algorithm are the Cluster assigment threshold and the Cluster candidate label threshold. The Cluster Assignment Threshold (tcA) controls the assignments of documents to the clusters. This threshold is based on the Cosine similarity between a label and a document and its common range is from 0.15 (default) to 0.3. The Cluster Candidate Label Threshold (tcL) controls the number of clusters (labels created). This threshold is based on the Cosine similarity between a candidate cluster label and the basis vectors of the SVD decomposition. This threshold default value is 0.775 and its common value range is from 0.70 to 0.90. 2.2
The Hierarchical Agglomerative Clustering method used is agglomerative, it
starts at the leaves and successively merges clusters together. HAC can be
stopped by distance criterion and number of clusters criterion. The Lemur3
Information Retrieval software includes an implementation of Hierarchial
Agglomerative Clustering. The clustering algorithms implemented for Lemur and
1 HTMLParser. http://htmlparser.sourceforge.net/
2 Carrot2 Project. http://project.carrot2.org
3 Lemur Project. http://www.lemurproject.org
used in this paper are described in [
This is a two step algorithm that consists to cluster the results of an initial clustering process. The process follows these steps: 1) initial clustering with an agglomerative clustering algorithm that produces a set of clusters, 2) merging the content of each cluster in one new document by merging all the documents that pertain to a cluster into a one representative document for the whole cluster, 3) a second clustering step does agglomerative clustering (centroid or agglomerative con gurations) over the collection of representative documents for the initial clusters. 3
For the WePS-3 trial evaluation we designed a set of several experiments that consist in applying di erent baseline con gurations (see Table 1) to the WePS-3 trial data (WePS-2 test data).
The baseline runs were designed changing the parameters of the algorithms and the Clustering method. We did experiments with the three algorithms described before: Lingo, HAC, and 2-step HAC. We present here a set of these experiments. The experiments with Lingo share the same parameters (tcL=0.15, tcA=0.7), and di er in the kind of input to use as source documents. The following four experiments were done: full documents (1), snippets and title (2), context of the person name with 100 and 500 chars (3) (4). The experiments with agglomerative clustering di er with the type of cluster (agglomerative or centroid), type of scoring (minimum or maximum), and threshold. We did the following experiments: (5) aglomerative (agglo) with maximum score (max) and 0.07 as threshold, (6) centroid (cent) with minimum score (min) and 0.20 as threshold, (7) centroid (cent) with max and 0.05 as threshold. The experiments with 2-step clustering were in four types, i) centroid ( rst step) & centroid (second step) (8), ii) centroid ( rst step) & agglomerative (second step) (9) iii) agglomerative ( rst step) & centroid (second step) (10) and iv) agglomerative ( rst step) & agglomerative (second step): experiments from (11) to (15).
For the WePS-3 evaluation with the test data we designed a set of ve experiments that consist in applying di erent baseline con gurations to the development set data(see Table 2). The rst run (TALP 1) uses agglomerative clustering and the second run (TALP 2) uses a 2-step clustering approach with both Agglomerative clustering algorithms of Lemur. The rst step does agglomerative clustering and the second step does again agglomerative clustering with the output of the rst step. The third run (TALP 3) applies the algorithm Lingo for clustering. The fourth run (TALP 4) uses the centroid algorithm from the Lemur. The fth run (TALP 5) used a 2 step clustering, the rst step applies the centroid algorithm of lemur and the second step applies agglomerative clustering.
This is our rst attempt to deal with Web Person Search Clustering at WePS clustering task. We have used three clustering algorithms (Lingo, HAC, and 2step HAC) to perform the task of clustering web people search in the context of the WePS-3 Task-1. In the preprocessing of documents we detected that HTML ltering is a crucial step to avoid noise. It is convenient to avoid noise from input documents to achieve better results, specially in the Lingo algorithm. Input Noise as broken sentences and random strings could have afected the results of the clustering algorithms, specially Lingo and its cluster labels. We achieved best results with the 2-step HAC and Agglomerative Clustering which deliver better performance than Lingo. We used limited NLP processing only in with lingo, the other runs used Porter Stemmer before indexing and clustering. Further improvements include the use of NLP techniques for Part-of-Speech Tagging, Named Entity Recognition and Classi cation, and Information Extraction.
This work has been supported by the Spanish Research Dept. (KNOW 2, TIN200914715-C04-04). Daniel Ferres is supported by the EBW II Project, which is nanced by the European Commission within the framework of the Erasmus Mundus Programme. TALP Research Center is recognized as a Quality Research Group (2001 SGR 00254) by DURSI, the Research Department of the Catalan Government.