Introduction

Article

Inferring Hierarchical Descriptions

E. Glover, D. M. Pennock, S. Lawrence, R. Krovetz

• NEC, Princeton
• Présenté à la conférence CIKM 2002
• Cité 89 fois depuis

But

Identifier l'ontologie de termes sur le web

• Concepts Parent / Self / Child exemple: "animal", "félin" et "chat"
• A partir d'une collection de documents web

Applications

• Nommage automatique

  • Identifier une thématique
  • Nommer un groupe de documents

• Recherche d'information

  • Proposer des résultats liés
  • Suggérer des requêtes liées

État de l'art

Sur ce sujet

• Pas de travaux précédents pour cette approche
• Objectif de "découverte" et non d'amélioration
• Utilisation de méthodes venant d'autres approches

Résumé automatique

• Radev et Fan (2000) Identification de thèmes lors de l'analyse de documents web
• Hearst (1998) et Caraballo (1999) Recherche de relations lexicales en utilisant des motifs
• Sanderson et Croft (1999) Analyse statistique pour identifier l'inclusion sémantique

Dans chacun des cas, pas de distinction entre "concept parent" et "concept enfant"

Regroupement de documents

• Kumar (1999) Construction de groupes de docs pour l'identification de communautés
• Hofmann et Puzicha (1998) Modèles statistiques pour la hierarchisation de documents (RI)

Travail présenté

Idée

On compare la fréquence d'un terme t dans le document d et dans la collection C

• Si t est très présent dans d et rare dans C : self
• Si t est assez présent dans d et présent dans C : parent
• Si t est assez présent dans d et très rare dans C : child

Fréquences et relations

Corpus

Documents provenant de Open Directory (www.dmoz.org)

Corpus

• On considère les catégories et leurs sous-catégories comme référence pour les ontologies
• Pour chaque catégorie, 500 documents sont retenus
• On conserve 20 000 documents d'autres catégories (bruit)

Expériences : texte complet

Catégories

• Parents : "Science", "Computers" et "Sports"
• Enfants : 41 catégories ("Agriculture", "Internet", "Tennis"...)

Prétraitements

• Pas de stemming
• Pas d'utilisation de stopwords
• Enfants séparés au niveau des "ou", "et" et de la ponctuation

Première distribution

Problèmes

• Catégories mal définies sans informations sur leur contexte
• Faible utilisation de "Computers" au pluriel

Correctifs

• Suppression des catégories mal définies
• Renommage de "Computers" en "Computer"

Seconde distribution

Problèmes

• Les documents ne contiennent pas toujours les mots décrivant leurs catégories ("Multimédia" apparaît dans 13% des documents positifs)
• Pages d'accueil sans contenu textuel (circa 2002)

Expériences :Extended Anchortext

Extended Anchortext

Extended Anchortext (EA) fait référence au texte qui apparaît autour des hyperliens. Au lieu d'utiliser les textes complets, on va maintenant passer par des documents virtuels composés de ces EA.

• 25 mots avant et après le texte du lien (inclus)
• 15 EA par document virtuel
• Entre 36 et 82 documents virtuels par catégorie

Troisième distribution

Quatrième distribution

Extraction des descriptions hiérarchiques

Résultats du "training"

Chaque document de la collection sera classé

Algorithme

1. On assigne un label à chaque feature :

if      (f.neg > maxParentNegative) { Label = "N" }

elseif  (f.neg > maxSelfNegative)   { Label = "P" }

elseif  (f.pos > minSelfPositive)   { Label = "S" }

elseif ((f.pos < maxChildPositive)
    and (f.neg < maxChildNegative)) { Label = "C" }

else
        { Label = "N" }

2. Pour chaque label, (P,S,C) on trie chaque feature par sa fréquence dans les documents positifs

Résultats : échantillon

Résultats : scores

• Le parent assigné à chaque catégorie par l'Open Directory se trouve toujours dans le top 5
• Environ 80% des selfs les mieux classés sont soit identiques, soit des synonymes, soit partagent une racine avec ceux assignés par l'Open Directory
• Les children sont durs à évaluer puisqu'un grand nombre de candidats raisonnables ne sont pas listés

Remarques

Points positifs

• Le principe a l'air de fonctionner
• Extrêmement simpliste

Limitations

• L'algorithme ne propose pas de solution pour déterminer automatiquement les régions
• Les régions varient en fonction des catégories
• Les groupes nominaux ont des occurrences positives inférieures aux simples mots
• Pas de stemming ou de stopwords (e.g. "University of", "Computers" ...)
• Les catégories ne sont pas uniformément distribuées dans l'Open Directory
• L'Open Directory circa 2002 n'est pas représentatif du web actuel
• Beaucoup d'opérations manuelles (suppression et renommage de catégories, définition des frontières...)

Conclusion

Points importants

• Une méthode simple qui semble donner des résultats
• Expériences inconcluantes
• Changements fondamentaux de la structure des pages web depuis 2002