Ontology learning from semi-structured Web documents [Elektronische Ressource] / von Marko Brunzel

Sujets

• Wissenschaft

Informations

• Publié par: otto-von-guericke-universitat_magdeburg
• Publié le: 01 janvier 2010
• Nombre de lectures: 16
• Poids de l'ouvrage: 4 Mo

Extrait

Ontology Learning from
semi-structured Web Documents
Dissertation
zur Erlangung des akademischen Grades
Doktoringenieur (Dr.-Ing.)
angenommen durch die Fakultat fur Informatik
der Otto-von-Guericke-Universitat Magdeburg
von Dipl. Wirt.-Ing. (FH) Marko Brunzel
geb. am 21. Januar 1977 in Meerane
Gutachter:
Prof. Dr. Ste en Staab
Prof. Dr. Myra Spiliopoulou
Prof. Dr. Andreas Dengel
Magdeburg, den 17. Februar 2010Contents
List of Figures vii
List of Tables xi
List of Algorithms xiii
1 Introduction 5
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Using the Web for Ontology Learning . . . . . . . . . . . . . . . . . 5
1.3 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Foundations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 Introductory Examples . . . . . . . . . . . . . . . . . . . . . 10
1.4.2 Notions of Sibling Relations . . . . . . . . . . . . . . . . . . 12
1.4.3 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.4 Sibling Relations beyond Ontologies . . . . . . . . . . . . . . 15
1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Related Work 21
2.1 Learning from the Web . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Learning from HTML Documents . . . . . . . . . . . . . . . . . . . 23
2.2.1 Markup in General . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.2 Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.3 Headings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.4 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Learning Sibling Relations . . . . . . . . . . . . . . . . . . . . . . . 26
3 Group-By-Path 31
3.1 Web Document Structures . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Group-By-Path Algorithm . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Real World Example and Application Outlook . . . . . . . . . . . . 38
3.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4.1 Wrapper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.2 XPath - Siblings . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4.3 XML Document Similarity . . . . . . . . . . . . . . . . . . . 46
3.4.4 Further Path based Approaches . . . . . . . . . . . . . . . . 46
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
iContents
4 Learning Sibling Groups - XTREEM-SG 49
4.1 XTREEM-SG Procedure . . . . . . . . . . . . . . . . . . . . . . . . 49
4.1.1 Step 1 - Querying & Retrieving: . . . . . . . . . . . . . . . . 51
4.1.2 Step 2 - Group-By-Path: . . . . . . . . . . . . . . . . . . . . 52
4.1.3 Step 3 - Filtering: . . . . . . . . . . . . . . . . . . . . . . . . 52
4.1.4 Step 4 - Vectorization: . . . . . . . . . . . . . . . . . . . . . 53
4.1.5 Step 5 - Clustering . . . . . . . . . . . . . . . . . . . . . . . 53
4.1.6 Step 6 - Cluster Labelling . . . . . . . . . . . . . . . . . . . 55
4.2 Evaluation Methodology . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2.1 Evaluation Criteria: Sibling Group Overlap . . . . . . . . . 56
4.2.2 Evaluation Reference . . . . . . . . . . . . . . . . . . . . . . 58
4.2.3 Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.2.4 Variations on Procedure and Parameters . . . . . . . . . . . 59
4.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.3.1 Experiment 1: Sibling Relations from Group-By-Path in
contrast to alternative Methods . . . . . . . . . . . . . . . . 62
4.3.2 Experiment 2: Sibling Relations from Labelled Clusters . . . 63
4.3.3 Experiment 3: Varying the Cluster Labelling Threshold . . . 66
4.3.4 Experiment 4: Varying the Number of Clusters . . . . . . . 68
4.3.5 Experiment 5: Varying the Topic Bias . . . . . . . . . . . . 70
4.3.6 Experiment 6: Variations on the Minimum Support . . . . . 72
4.3.7 Experiment 7: Sampling on Tagpath Clustering . . . . . . . 74
4.3.8 Experiment 8: Frequent Itemsets in Comparison to Clusters 76
4.3.9 Experiment 9: Tagpath Clustering in Comparison to Term
Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3.10 Experiment 10: Sampling on Term Clustering . . . . . . . . 80
4.3.11 Results from Term Clustering . . . . . . . . . . . . . . . . . 82
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5 Learning Sibling Groups Hierarchies - XTREEM-SGH 87
5.1 Hierarchical clustering for Sibling Groups Hierarchies . . . . . . . . 88
5.1.1 Hierarchical Term Clustering . . . . . . . . . . . . . . . . . . 88
5.1.2 Hierarchical Tagpath Clustering . . . . . . . . . . . . . . . . 93
5.1.3 XTREEM-SGH Procedure . . . . . . . . . . . . . . . . . . . 94
5.2 Evaluation Methodology . . . . . . . . . . . . . . . . . . . . . . . . 95
5.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.3.1 Experiment 1: K-Means in Comparison to Bi-Secting-K-Means 96
5.3.2 Experiment 2: Di erent Observation Strategies on the
Cluster Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.3 Experiment 3: Best Matching Hierarchy Levels . . . . . . . 100
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6 Learning Sibling Pairs - XTREEM-SP 103
6.1 XTREEM-SP Procedure . . . . . . . . . . . . . . . . . . . . . . . . 104
iiContents
6.1.1 Step 4 - Co-Occurrence Counting . . . . . . . . . . . . . . . 106
6.1.2 Step 5 - Computing Association Scores . . . . . . . . . . . . 106
6.2 Evaluation Methodology . . . . . . . . . . . . . . . . . . . . . . . . 108
6.2.1 Evaluation Criteria: Precision and Recall . . . . . . . . . . . 108
6.2.2 Evaluation Reference . . . . . . . . . . . . . . . . . . . . . . 109
6.2.3 Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.2.4 Variations on Procedure and Parameters . . . . . . . . . . . 109
6.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.3.1 Experiment 1: Sibling Relations from Group-By-Path in
contrast to alternative Methods . . . . . . . . . . . . . . . . 110
6.3.2 Experiment 2: Association Measures in Comparison . . . . . 114
6.3.3 Experiment 3: Varying the Topic Bias . . . . . . . . . . . . 116
6.3.4 Experiment 4: Variations on the Minimum Support . . . . . 118
6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7 Vocabulary Extraction with XTREEM-T 121
7.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.2 XTREEM-T Procedure . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.2.1 Step 1 - Querying & Retrieving: . . . . . . . . . . . . . . . . 125
7.2.2 Step 2 - Markup Exploitation: . . . . . . . . . . . . . . . . . 125
7.2.3 Step 3 - Text span Counting: . . . . . . . . . . . . . . . . . 126
7.2.4 Step 4 - Order By Frequency: . . . . . . . . . . . . . . . . . 126
7.3 Evaluation Methodology . . . . . . . . . . . . . . . . . . . . . . . . 127
7.3.1 Evaluation Criteria: Precision . . . . . . . . . . . . . . . . . 127
7.3.2 Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.4.1 Experiment 1: Human Vocabulary Evaluation . . . . . . . . 128
7.4.2 Experiment 2: N-Gram Level Distribution . . . . . . . . . . 130
7.4.3 Experiment 3: POS Patterns . . . . . . . . . . . . . . . . . 133
7.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
8 Finding Synonyms with XTREEM-S 135
8.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
8.2 XTREEM-S Procedure . . . . . . . . . . . . . . . . . . . . . . . . . 136
8.2.1 Step 1 - Querying & Retrieving: . . . . . . . . . . . . . . . . 139
8.2.2 Step 2 - Group-By-Path: . . . . . . . . . . . . . . . . . . . . 139
8.2.3 Step 3 - Filtering: . . . . . . . . . . . . . . . . . . . . . . . . 139
8.2.4 Step 4 - Vectorization: . . . . . . . . . . . . . . . . . . . . . 139
8.2.5 Step 5 - First Order Association Computation: . . . . . . . . 139
8.2.6 Step 6 - Second Order Association Computation: . . . . . . 140
8.3 Evaluation Methodology . . . . . . . . . . . . . . . . . . . . . . . . 140
8.3.1 Evaluation Criteria: Precision and Recall . . . . . . . . . . . 141
8.3.2 Evaluation Reference . . . . . . . . . . . . . . . . . . . . . . 141
8.4 Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
iiiContents
8.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
9 Domain Relevance enhanced Term Weighting for Learning Sibling
Groups - XTREEM-SG 145T;DR
9.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
9.1.1 Distorted Occurrence Distributions . . . . . . . . . . . . . . 146
9.1.2 Interest towards Domain Relevant Terms . . . . . . . . . . . 146
9.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
9.2.1 Term Weighting . . . . . . . . . . . . . . . . . . . . . . . . . 147
9.2.2 Domain Relevance . . . . . . . . . . . . . . . . . . . . . . . 148
9.3 XTREEM-SG Procedure . . . . . . . . . . . . . . . . . . . . . 150T;DR
9.4 Evaluation Methodology . . . . . . . . . . . . . . . . . . . . . . . . 152