Efficient Knowledge Extractionfrom Structured DataBianca WackersreutherMunchen¨ 2011Efficient Knowledge Extractionfrom Structured DataBianca WackersreutherDissertationan der Fakultat¨ fur¨ Mathematik, Informatik und Statistikder Ludwig–Maximilians–Universitat¨¨Munchenvorgelegt vonBianca Wackersreutheraus Fussen¨Munchen,¨ den 24.02.2011Erstgutachter: Prof. Dr. Christian Bohm¨Zweitgutachter: Prof. Dr. Thomas SeidlTag der mundlichen¨ Prufung:¨ 15.12.2011For my children Julius and Simon.viContentsAcknowledgments xiAbstract xiiiZusammenfassung xv1 Preliminaries 11.1 The Classic Definition of KDD . . . . . . . . . . . . . . . . . . . 21.2 Data Mining: The Core Step of Knowledge Extraction . . . . . . 31.3 Clustering: One of the Major Data Mining Tasks . . . . . . . . . 41.4 Information Theory for Clustering . . . . . . . . . . . . . . . . . 61.5 Boosting the Data Mining Process . . . . . . . . . . . . . . . . . 81.6 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . 112 Related Work 132.1 Hierarchical Clustering . . . . . . . . . . . . . . . . . . . . . . . 132.1.1 Agglomerative Hierarchical Clustering . . . . . . . . . . 152.1.2 Linkage methods . . . . . . . . . . . . . . . . . . . . . . 162.1.3 Density-based Hierarchical Clustering . . . . . . . . . . . 172.1.4 Model-based . . . . . . . . . . . 192.2 Mixed Type Attributes Data . . . . . . . . . . . . . . . . . . . . . 202.2.