Graph-Theoretic Techniques for Web Content Mining by Adam Schenker A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy Department of Computer Science and Engineering College of Engineering University of South Florida Major Professor: Abraham Kandel, Ph.D. Dewey Rundus, Ph.D. Horst Bunke, Ph.D. Ken Christensen, Ph.D. Carlos Smith, Ph.D. Date of Approval: September 16, 2003 Keywords: graph similarity, graph distance, machine learning, clustering, classification © Copyright 2003 , Adam Schenker Dedication For my parents. Acknowledgements There are many people who helped contribute to the successful completion of this dissertation. First I would like to thank Dr. Abraham Kandel for supporting me with not only his scientific and monetary resources, but with his wisdom and kindness. Dr. Mark Last provided invaluable assistance in performing my research; his feedback always served to improve the work in meaningful ways. Dr. Horst Bunke was a tremendous help and source of knowledge; without his constant support and vision this dissertation would not have been possible. Dr. Dewey Rundus, Dr. Ken Christensen, Dr. Carlos Smith and Dr. José Zayas-Castro all provided useful comments and advice for improving the dissertation and their help is greatly appreciated. Finally, it is necessary for me to mention the staff and my fellow graduate students at the Department of Computer Science and Engineering each of whom has enabled me reach my goal: Ms. Judy Hyde, Dr. Scott Dick, Dr. Lawrence Hall, Dr. Rafael Perez, Ms. Sarah Burton and Mr. Daniel Prieto. Table of Contents List of Tables iv List of Figures vi Abstract x Chapter One: Introduction 1 Chapter Two: A Review of Web Mining Techniques 6 2.1!Overview of Web Mining Methodologies 6 2.2!Traditional Information Retrieval Techniques for Plain-Text Documents 7 2.3!Web Search Clustering 9 2.4!Summary 11 Chapter Three: A Review of Graph Similarity Techniques 12 3.1 Introduction 12 3.2 Graph and Subgraph Isomorphism 13 3.3 Graph Edit Distance 15 3.4!Maximum Common Subgraph / Minimum Common Supergraph Approach 16 3.5 State Space Search Approach 18 3.6 Probabilistic Approach 18 3.7 Distance Preservation Approach 20 3.8 Relaxation Approaches 21 3.9 Mean and Median of Graphs 23 3.10 Remarks 24 Chapter Four: Graph Models for Web Documents 26 4.1 Pre-Processing 26 4.2 Graph Representations of Web Documents 27 4.3 Complexity Analysis 31 Chapter!Five:!The Graph Hierarchy Construction Algorithm for Organizing Web Search Results 32 5.1 Introduction 32 5.2 Cluster Hierarchy Construction Algorithm (CHCA) 33 5.2.1 A Review of Inheritance 33 i 5.2.2 Brief Overview of CHCA 34 5.2.3 CHCA in Detail 35 5.2.4 CHCA: an Example 39 5.2.5 Examination of CHCA as a Clustering Method 40 5.3 Application of CHCA to Search Results Processing 43 5.3.1 Asynchronous Search 43 5.3.2 Implementation, Input Preparation and Pre-processing 44 5.3.3 Selection of Parameters for Web Search 44 5.4 Examples of Results 46 5.4.1 Comparison with Grouper 46 5.4.2 Comparison with Vivísimo 50 5.5 Graph Hierarchy Construction Algorithm (GHCA) 52 5.5.1 Parameters 53 5.5.2 Graph Creation and Pre-processing 54 5.5.3 Graph Hierarchy Construction Algorithm (GHCA) 55 5.5.4 GHCA Examples 57 5.6 Comments 58 Chapter!Six:!A Graph-Theoretical Extension of the k-Means Clustering Algorithm 61 6.1 Introduction 61 6.2 The Extended k-Means Clustering Algorithm 62 6.3 Web Document Data Sets 63 6.4 Clustering Performance Measures 64 6.5 Comparison with Published Results 65 6.6 Remarks 68 Chapter!Seven:!Comparison of Different Graph-Theoretical Distance Measures and Graph Representations for Graph-Theoretic Clustering 70 7.1 Introduction 70 7.2 Comparison of Distance Measures 73 7.3 Comparison of Graph Representations 77 7.4!Visualization of Graph Clustering 79 Chapter Eight: The Graph-Theoretic Global k-Means Algorithm 82 8.1 Introduction 82 8.2 Global k-Means vs. Random Initialization 83 8.3 Optimum Number of Clusters 85 Chapter!Nine:!A!Graph-Theoretical Extension of the k-Nearest Neighbors Classification Algorithm 89 91 9.1 Introduction 89 9.2 k-Nearest Neighbors with Graphs 89 9.3 Experimental Results 90 9.4 Remarks 98 ii Chapter Ten: Conclusions and Future Work 100 References 103 Appendices 113 Appendix A: Examples of Documents Used in Experiments 114 Appendix B: Graphs Created from Example Documents of Appendix A 120 Appendix C: Nearest Neighbors of Example Documents 123 Appendix D: Graphs of Nearest Neighbors 129 About the Author End Page iii List of Tables Table!5.1 Simple Example to Illustrate Concepts of CHCA 39 Table!5.2 Results of the Grouper Custom System for the Query “Soft Computing” 48 Table!5.3 Results of the Grouper Custom System for the Query “Data Compression” 50 Table!5.4 List of Query Strings Used for Comparison 51 Table!5.5 Summary of Comparison for 10 Searches (C: CHCA, V: Vivísimo) 51 Table!6.1 Results of Our Experiments Compared with Results from Strehl et al. 66 Table!7.1 Clustering Performance Comparison for K-Series 71 Table!7.2 Distance Measure Comparison for K-Series 72 Table!7.3 Graph Representation Comparison for K-Series 75 Table!8.1 Results for F-Series (Rand Index) 84 Table!8.2 Results for F-Series (Mutual Information) 84 Table!8.3 Results for J-Series (Rand Index) 84 Table!8.4 Results for J-Series (Mutual Information) 85 Table!8.5 Execution Times Using Random Initialization (in Seconds) 85 Table!8.6 Execution Times Using Global k-Means (in Minutes) 85 Table!8.7 Results for F-Series Using Global k-Means 87 Table!8.8 Results for F-Series Using Random Initializations 88 iv Table!8.9 Results for J-Series Using Global k-Means 88 Table!8.10 Results for J-Series Using Random Initializations 88 Table!9.1 Average Times to Classify One K-Series Document for Each Method 93 v List of Figures Figure!3.1 A Graph G and its Compliment G May be Isomorphic 14 Figure!4.1 Example of a Standard Graph Representation of a Document 29 Figure!4.2 Example of a Simple Graph Representation of a Document 29 Figure!4.3 Example of an n-Distance Graph Representation of a Document 29 Figure 5.1 Summary of Notation Used in CHCA 34 Figure!5.2 Cluster Hierarchy Created from the Example in Table 5.1 40 Figure!5.3 Average Number of Clusters Created as a Function of Maximum Cluster Threshold (MCT) for Three Queries 45 Figure!5.4 Average Number of Clusters Created as a Function of Minimum Pages Threshold (MPT) for Three Queries 45 Figure!5.5 Cluster Hierarchy Created by CHCA for the Query “Soft Computing” 47 Figure!5.6 Cluster Hierarchy Created by CHCA for the Query “Data compression” 49 Figure!5.7 Pre-processing Phase of GHCA 53 Figure 5.8 Initial Hierarchy Construction Phase of GHCA 55 Figure 5.9 Document Assignment Phase of GHCA 55 Figure 5.10 Cluster Pruning Phase of GHCA 56 Figure!5.11 Results Display Methodology for GHCA 56 Figure!5.12 Examples of Cluster Hierarchies Generated by GHCA 58 Figure!6.1 The Traditional k-Means Clustering Algorithm 62 vi Figure!6.2 The Graph-Theoretic k-Means Clustering Algorithm 62 Figure!6.3 Mutual Information as a Function of the Maximum Number of Vertices per Graph 67 Figure!6.4 Clustering Time as a Function of the Maximum Number of Vertices per Graph 67 Figure!7.1 Distance Measure Comparison for the F-Series Data Set (Rand Index) 71 Figure!7.2 Distance Measure Comparison for the F-Series Data Set (Mutual Information) 72 Figure!7.3 Distance Measure Comparison for the F-Series Data Set (Dunn Index) 72 Figure!7.4 Distance Measure Comparison for the J-Series Data Set (Rand Index) 73 Figure!7.5 Distance Measure Comparison for the J-Series Data Set (Mutual Information) 74 Figure!7.6 Distance Measure Comparison for the J-Series data set (Dunn index) 74 Figure!7.7 Graph Representation Comparison for the F-Series Data Set (Rand Index) 75 Figure!7.8 Graph Representation Comparison for the F-Series Data Set (Mutual Information) 76 Figure!7.9 Graph Representation Comparison for the F-Series Data Set (Dunn Index) 76 Figure!7.10 Graph Representation Comparison for the J-Series Data Set (Rand Index) 77 Figure!7.11 Graph Representation Comparison for the J-Series Data Set (Mutual Information) 78 Figure!7.12 Graph Representation Comparison for the J-Series Data Set (Dunn Index) 78 vii