This paper describes the participation of DAEDALUS team at the WebPS-3 Task 1, regarding Web People Search. The focus of our research is to evaluate and compare the computational requirements and results achieved by different solutions based on the minimization of cost functions applied to clustering algorithms. Our clustering technique is based on an implementation of k-Medoids algorithm, run over a sparse term-document matrix built with the terms of the pages that are associated to each of the person names. We define an empty-cluster that holds all the individuals that are not part of any other cluster. Based on the results obtained, we can conclude that although clustering techniques play a very relevant role in the resolution of the problem of name homonymy in a set of web pages, there is a previous challenge still to solve: how to determine which contents are relevant for describing the person in that webpage, thus which are not part of the other navigational information contained in the webpage.
The Web People Search (WePS) [
Our research group is led by and named after DAEDALUS, a small private company in the field of Information and Telecommunication Technologies and a leading provider of language-based solutions in Spain, and research groups of two universities, Universidad Politécnica de Madrid and Universidad Carlos III de Madrid. We have taken part in CLEF since 2003 in many different tracks and tasks, as part of the MIRACLE team till last year. This paper describes our participation at the WebPS Web People Search (Task 1).
Traditionally, the solutions to solve the problem of name disambiguation have been
typically based on techniques such as Hierarchical Agglomerative Clustering (HAC)
or Incremental Vector Space clustering algorithm, or some of their variants. The idea
behind the set of experiments that we have carried out this year is to evaluate the
computational cost and the precision values that are achieved when another type of
solution based on the minimization of cost function is applied. Specifically, our
research has focused on the clustering algorithm based on k-Medoids [
Our system is modular and built from of a set of small components that are easily
combined in different configurations and executed sequentially to build the final
result set. A common baseline algorithm was used in all experiments to process the
data collection, following these steps:
1. Text Extraction: Ad-hoc scripts are run on web pages to extract the relevant
information.
2. Tokenization: This process extracts basic textual components. Some basic entities
are also detected, such as numbers, initials, abbreviations, and years. So far,
compounds, proper nouns, acronyms or other types of entity are not specifically
considered. The outcomes of this process are single words, multi-words and years
in numbers.
3. Conversion to lowercase: All document terms are normalized by changing all
letters to lowercase.
4. Filtering: All words recognized as stopwords are filtered out. Stopwords in the
target languages were initially obtained from the University of Neuchatel’s
resources page [
As mentioned before, the objective of our experiments was to make an exhaustive
evaluation and comparison of the computational costs and results achieved when
solutions based on the minimization of cost functions are used as a basic clustering
algorithm. For our experiments, we have specifically focused on an implementation of
k-Medoids clustering algorithm [
In our settings, we use k as the result of the minimization of the cost function (see Equation 1).
+ ∗ # + ∗ ∗ ∗ ln (1) where: k: number of clusters (2 – R/8). cIntraCluster: summation of the intra-cluster distances. cInterCluster: summation of the inter-cluster distances.
#UnaryCluster: number of clusters with only one element (the medoid).
R: size of the simple space once removed the vectors without significant components.
α: dispersion coefficient (0.1 - 0.9).
This algorithm is continuously run over the sparse term-document matrix that was built with the terms of the pages that are associated to each person name. The maximum number of epochs has been set to 10. The algorithm was designed allowing no cluster overlapping, i.e., the membership function returns just one value for each individual, or, in other words, each individual belongs to one cluster maximum.
Different experiments have been defined, using different combinations of the textual information present in different components of the web pages with different values of the dispersion coefficient in the cost function to minimize in Equation 1. After studying some strategies, we finally decided to define a cluster (empty-cluster) that groups all those individuals that have no significant term after the linguistic processing. Finally we submitted 4 experiments to be evaluated, listed in Table 1. daedalus_1 daedalus_2 daedalus_3 daedalus_4
Body Metadata + Title Metadata + Title + Body Metadata + Title + Body
Dispersion coefficient (α) 0.3 0.3 0.3 0.6
Table 4 shows the evaluation results using B-Cubed measures. As inferred from that metric, the achieved results present, in general, a behaviour closer to all_in_one_baseline than to one_in_one_baseline. This result is consistent and agrees with the figures shown in Table 2. This may be explained that, although some clusters have been identified, the main set of individuals are assigned to a medoid and the rest of the individuals (a few of them) are distributed along clusters whose population is only one or two individuals. Run Identifier all_in_one daedalus_1 daedalus_2 daedalus_3 daedalus_4 one_in_one Based on the results obtained, we can conclude that although clustering techniques play a very relevant role in the resolution of the problem of name homonymy in a set of web pages, there is a previous challenge still to solve before studying whether it is better to generate one cluster with all the individuals that have nothing in common with the others, rather than creating one cluster for each of them.
This challenge has a greater impact in the success of the experiments, and it is related to the extraction of relevant information: given a web page whose structure is unknown, it is essential to determine which contents in this page are useful for the resolution of the problem (i.e., are relevant for describing the person to whom the page is assumed to refer) and which contents should be filtered out (such as navigational information, titles, headers and footers, disclaimers, etc.). And moreover, regarding the first ones, it is necessary to determine if those contents refer exactly to the expected person or else is referring to other different entities or concepts (such as lists of similar authors, for instance). In our humble opinion, these should be the challenges on which we should focus in future editions of WebPS.
This work has been partially supported by the Spanish Center for Industry Technological Development (CDTI, Ministry of Industry, Tourism and Trade), through the CONTENIDOS A LA CARTA Project, INGENIO 2010 Programme, AVANZA I+D 2008. Other partners in the project are Agencia EFE, Germinus XXI, 11870.com and Universidad Politécnica de Madrid.