Synchronization Inspired Data Mining [Elektronische Ressource] / Junming Shao. Betreuer: Christian Böhm

Shao Junming

Sujets

• Informatik

Informations

• Publié par: ludwig-maximilians-universitat_munchen
• Publié le: 01 janvier 2011
• Nombre de lectures: 37
• Langue: English
• Poids de l'ouvrage: 10 Mo

Extrait

Synchronization Inspired Data
Mining
Junming Shao
Munchen 2011Synchronization Inspired Data
Mining
Junming Shao
Dissertation
an der Fakult at fur Mathematik, Informatik und
Statistik
der Ludwig{Maximilians{Universit at
Munc hen
vorgelegt von
Junming Shao
aus Neijiang, China
Munc hen, den August 5, 2011Erstgutachter: Prof. Dr. Christian B ohm
Zweitgutachter: Prof. Dr. Ira Assent
Tag der mundlic hen Prufung: November 10, 2011Contents
Acknowledgement xxii
Abstract xxiv
Zusammenfassung xxvii
I Preliminaries 1
1 Introduction 3
1.1 Knowledge Discovery in Databases . . . . . . . . . . . . . . . 4
1.2 Challenges in Clustering . . . . . . . . . . . . . . . . . . . . . 7
1.3 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . 9
2 Clustering and Outlier Detection 13
2.1 Cluster Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Clustering Algorithms . . . . . . . . . . . . . . . . . . 15
2.1.2 Validation of Clustering Results . . . . . . . . . . . . . 22
2.2 Outlier Detection . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28vi CONTENTS
II Synchronization-based Data Mining 29
3 Synchronization 31
3.1 The Concept of Synchronization . . . . . . . . . . . . . . . . . 31
3.2 The Kuramoto model . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Clustering by Synchronization 37
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.1.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3 Clustering by Synchronization . . . . . . . . . . . . . . . . . . 46
4.3.1 Kuramoto Model . . . . . . . . . . . . . . . . . . . . . 46
4.3.2 Reformulation of the Kuramoto Model for Clustering . 47
4.3.3 The Sync Algorithm . . . . . . . . . . . . . . . . . . . 49
4.3.4 Runtime Complexity . . . . . . . . . . . . . . . . . . . 57
4.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . 57
4.4.1 Synthetic Data . . . . . . . . . . . . . . . . . . . . . . 58
4.4.2 Real-world Data . . . . . . . . . . . . . . . . . . . . . 63
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5 Exploring Natural Hierarchies of Synchronized Cluster 69
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.3 hSync: Discovering Interpretable Cluster Hierarchies . . . . . 76CONTENTS vii
5.3.1 Key Observation . . . . . . . . . . . . . . . . . . . . . 76
5.3.2 Exploring the Hierarchical Cluster Structure . . . . . . 78
5.3.3 Parameter Selection . . . . . . . . . . . . . . . . . . . . 79
5.3.4 Runtime Complexity . . . . . . . . . . . . . . . . . . . 83
5.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . 83
5.4.1 Synthetic Data . . . . . . . . . . . . . . . . . . . . . . 83
5.4.2 Real-world Data . . . . . . . . . . . . . . . . . . . . . 85
5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6 Finding Synchronized Subspace Clusters 91
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.1.1 Synchronized Subspace Cluster . . . . . . . . . . . . . 96
6.1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . 96
6.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.3 The Algorithm ORSC . . . . . . . . . . . . . . . . . . . . . . 99
6.3.1 A Novel Perspective of Subspace Clustering . . . . . . 99
6.3.2 Interaction Model . . . . . . . . . . . . . . . . . . . . . 100
6.3.3 Simulation of the Object Dynamics . . . . . . . . . . . 105
6.3.4 Synchronized Clusters Search . . . . . . . . . . . . . . 108
6.3.5 Parameter Setting . . . . . . . . . . . . . . . . . . . . 110
6.3.6 Complexity Analysis . . . . . . . . . . . . . . . . . . . 113
6.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . 114
6.4.1 E ectiveness . . . . . . . . . . . . . . . . . . . . . . . . 114
6.4.2 E ciency . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121viii CONTENTS
7 Robust Synchronization-based Graph Clustering 125
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.3 Synchronization-based Graph Clustering . . . . . . . . . . . . 131
7.3.1 Vertex Feature Representation . . . . . . . . . . . . . . 132
7.3.2 Interaction Model . . . . . . . . . . . . . . . . . . . . . 135
7.3.3 The RSGC Algorithm . . . . . . . . . . . . . . . . . . 138
7.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
7.4.1 Evaluation Criteria . . . . . . . . . . . . . . . . . . . . 142
7.4.2 Proof of Concept . . . . . . . . . . . . . . . . . . . . . 142
7.4.3 Real-world Data . . . . . . . . . . . . . . . . . . . . . 144
7.4.4 Runtime Complexity . . . . . . . . . . . . . . . . . . . 149
7.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
8 Outlier Detection: \Out of Synchronization" 151
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
8.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
8.3 Synchronization-Based Outlier Detection . . . . . . . . . . . . 155
8.3.1 Basic idea . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.3.2 The SOD Algorithm . . . . . . . . . . . . . . . . . . . 158
8.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . 164
8.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
III Brain Network Mining 173
9 Background on Di usion Tensor Imaging and Analysis 175CONTENTS ix
9.1 Water Di usion in White Matter . . . . . . . . . . . . . . . . 176
9.2 Di usion Weighted MRI . . . . . . . . . . . . . . . . . . . . . 177
9.3 Di usion Tensor MRI . . . . . . . . . . . . . . . . . . . . . . . 179
9.3.1 Mean Di usivity . . . . . . . . . . . . . . . . . . . . . 180
9.3.2 Anisotropy Measures . . . . . . . . . . . . . . . . . . . 181
9.3.3 Geometrical Anisotropy Measures . . . . . . . . . . . . 181
9.4 White Matter Tractography . . . . . . . . . . . . . . . . . . . 182
9.4.1 Deterministic Tractography . . . . . . . . . . . . . . . 183
9.4.2 Probabilistic Ty . . . . . . . . . . . . . . . . 185
9.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
10 Fiber Clustering based on Dynamic Time warping. 187
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
10.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
10.2.1 Fiber Similarity Measure . . . . . . . . . . . . . . . . . 191
10.2.2 Fiber Clustering . . . . . . . . . . . . . . . . . . . . . . 193
10.3 Fiber Warping . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
10.3.1 Dynamic Time Warping . . . . . . . . . . . . . . . . . 195
10.3.2 Fiber Similarity Measure with DTW . . . . . . . . . . 198
10.3.3 Lower Bounding Distance . . . . . . . . . . . . . . . . 200
10.4 Fiber Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . 203
10.4.1 Density-based clustering ber tracts . . . . . . . . . . . 203
10.5 Experimental result and analysis . . . . . . . . . . . . . . . . 207
10.5.1 Cluster Validation Measure . . . . . . . . . . . . . . . 207
10.5.2 Fiber Data . . . . . . . . . . . . . . . . . . . . . . . . 208
10.5.3 Experiments on Fiber Similarity Measure . . . . . . . . 209x CONTENTS
10.5.4 Experiments on Fiber Clustering . . . . . . . . . . . . 211
10.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
11 Hierarchical Clustering of White Matter Tracts 219
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
11.2 Hierarchical Density-based Fiber Clustering . . . . . . . . . . 222
11.2.1 Hierarchical Density-Based . . . . . . . . . 222
11.2.2 Fiber Cluster Extraction . . . . . . . . . . . . . . . . . 226
11.3 Experimental Result and Analysis . . . . . . . . . . . . . . . . 231
11.3.1 Experiments on Fiber Clustering . . . . . . . . . . . . 231
11.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
11.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
12 Automated Prediction of Alzheimer’s disease 241
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
12.2 Materials and Methods . . . . . . . . . . . . . . . . . . . . . . 245
12.2.1 Subjects . . . . . . . . . . . . . . . . . . . . . . . . . . 245
12.2.2 Data Acquisition . . . . . . . . . . . . . . . . . . . . . 246
12.2.3 Construction of Individual Structural Connectivity Net-
works (ISCNs) . . . . . . . . . . . . . . . . . . . . . . . 248
12.2.4 Pattern Classi cation of ISCNs . . . . . . . . . . . . . 250
12.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
12.4 Discussion and Conclusion . . . . . . . . . . . . . . . . . . . . 258
12.5 Supplemental Information . . . . . . . . . . . . . . . . . .