2011 年新书 , 348 pages
<<Mining of Data with Complex Structures>>

by Fedja Hadzic,Henry Tan, and Tharam S.Dillon

CONTENTS:
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 DataMining Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Data Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Application of DataMiningAlgorithms . . . . . . . . . . . . . . . . 3
1.2.3 Pattern Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.4 KnowledgeRepresentation . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Different Types of Data Representations . . . . . . . . . . . . . . . . . . . . . . 4
1.3.1 Relational Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.2 SequentialData. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.3 Semi-structuredData . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.4 Unstructured Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Different Types of KnowledgeMined . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.1 Type of InformationMined . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.2 Representing theMined Knowledge . . . . . . . . . . . . . . . . . . . 7
1.5 CommonDataMining Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 AssociationMining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.2 Classification and Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.3 Cluster Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.4 Outlier Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6 Sources of Data with Complex Structures . . . . . . . . . . . . . . . . . . . . . 12
1.6.1 Online Information. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.2 Chemical Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6.3 Bioinformatics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6.4 Ontologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7 Complex Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.8 Emergence of Semi-structuredData Sources . . . . . . . . . . . . . . . . . . . 14
1.9 Challenges ofMining Data with Complex Structures . . . . . . . . . . . . 16
1.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 Tree Mining Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Problemof Association RuleMining . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.1 Association Rule Framework . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.2 Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.3 Confidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Emerging Field of TreeMining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.1 XML and AssociationMining . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2 The Parallel betweenXML and Tree Structure . . . . . . . . . . . 29
2.3.3 Problemof XML DocumentAssociationMining . . . . . . . . . 29
2.4 General Tree Concepts and Definitions. . . . . . . . . . . . . . . . . . . . . . . . 30
2.5 Frequent SubtreeMining Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.1 Subtree Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.2 Support Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.6 Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6.1 Issue with Pseudo Frequent Subtrees . . . . . . . . . . . . . . . . . . . 36
2.7 Canonical Form of a Subtree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3 Algorithm Development Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4 Tree Model Guided Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5 TMG Framework for Mining Ordered Subtrees . . . . . . . . . . . . . . . . . . 87
6 TMG Framework for Mining Unordered Subtrees . . . . . . . . . . . . . . . . 139
7 Mining Distance-Constrained Embedded Subtrees . . . . . . . . . . . . . . . . 175
8 Mining Maximal and Closed Frequent Subtrees . . . . . . . . . . . . . . . . . . 191
9 Tree Mining Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
10 Extension of TMG Framework for Mining Frequent Subsequences . . . . . . 249

11 Graph Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
12 New Research Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301