dc.contributor.author
Galliat, Tobias
dc.date.accessioned
2018-06-07T23:55:44Z
dc.date.available
2002-07-18T00:00:00.649Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/11198
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-15396
dc.description
Title and table of contents 1
Introduction 3
1\. Cluster Analysis in High-Dimensional Data 7
1.1 Modeling 8
1.2 Problem reduction via representative clustering 13
1.3 Efficient cluster description 16
1.4 How many clusters? 21
2\. Decomposition 23
2.1 General Definition 23
2.2 Approximate box decomposition 25
2.3 Decomposition based representative clustering 27
2.4 Efficient cluster description via approximate box decomposition 34
3\. Adaptive Decomposition by Self-Organized Neural Networks 41
3.1 Self-Organizing Maps (SOM) 42
3.2 Self-Organizing Box Maps (SOBM) 44
3.3 Comparison SOM-SOBM 53
3.4 Computational complexity 56
3.5 Practical extensions 57
4\. Multilevel Representative Clustering 59
4.1 General approach 59
4.2 Adaptive decomposition refinement 60
4.3 Approach based on Perron Cluster analysis 61
5\. Applications 73
5.1 Conformational Analysis of biomolecules 73
5.2 Cluster analysis of insurance customers 87
Conclusion 91
Appendix 93
Symbols 95
Bibliography 97
dc.description.abstract
The aim of this thesis is a fruitful combination of Perron Cluster analysis
and self-organized neural networks within an adaptive multilevel clustering
approach that allows a fast and robust identification and an efficient
description of clusters in high-dimensional data. In a general variant that
needs a correct number of clusters k as an input, this new approach is
relevant for a great number of cluster problems since it uses a cluster model
that covers geometrically, but also dynamically based clusters. Its essential
part is a method called representative clustering that guarantees the
applicability to large cluster problems: Based on an adaptive decomposition of
the object space via self-organized neural networks, the original problem is
reduced to a smaller cluster problem. The general clustering approach can be
extended by Perron Cluster analysis so that it can be used for large
reversible dynamic cluster problems, even if a correct number of clusters k is
unknown a priori. The basic application of the extended clustering approach is
the conformational analysis of biomolecules, with great impact in the field of
Drug Design. Here, for the first time the analysis of practically relevant and
large molecules like an HIV protease inhibitor becomes possible.
de
dc.description.abstract
Als Cluster Analyse bezeichnet man den Prozess der Suche und Beschreibung von
Gruppen (Clustern) von Objekten, so daß die Objekte innerhalb eines Clusters
bezüglich eines gegebenen Maßes maximal homogen sind. Die Homogenität der
Objekte hängt dabei direkt oder indirekt von den Ausprägungen ab, die sie für
eine Anzahl festgelegter Attribute besitzen. Die Suche nach Clustern läßt sich
somit als Optimierungsproblem auffassen, wobei die Anzahl der Cluster vorher
bekannt sein muß. Wenn die Anzahl der Objekte und der Attribute groß ist,
spricht man von komplexen, hoch-dimensionalen Cluster Problemen. In diesem
Fall ist eine direkte Optimierung zu aufwendig, und man benötigt entweder
heuristische Optimierungsverfahren oder Methoden zur Reduktion der
Komplexität. In der Vergangenheit wurden in der Forschung fast ausschließlich
Verfahren für geometrisch basierte Clusterprobleme entwickelt. Bei diesen
Problemen lassen sich die Objekte als Punkte in einem von den Attributen
aufgespannten metrischen Raum modellieren; das verwendete Homogenitätsmaß
basiert auf der geometrischen Distanz der den Objekten zugeordneten Punkte.
Insbesondere zur Bestimmung sogenannter metastabiler Cluster sind solche
Verfahren aber offensichtlich nicht geeignet, da metastabile Cluster, die z.B.
in der Konformationsanalyse von Biomolekülen von zentraler Bedeutung sind,
nicht auf einer geometrischen, sondern einer dynamischen Ähnlichkeit beruhen.
In der vorliegenden Arbeit wird ein allgemeines Clustermodell vorgeschlagen,
das zur Modellierung geometrischer, wie auch dynamischer Clusterprobleme
geeignet ist. Es wird eine Methode zur Komplexitätsreduktion von
Clusterproblemen vorgestellt, die auf einer zuvor generierten Komprimierung
der Objekte innerhalb des Datenraumes basiert. Dabei wird bewiesen, daß eine
solche Reduktion die Clusterstruktur nicht zerstört, wenn die Komprimierung
fein genug ist. Mittels selbstorganisierter neuronaler Netze lassen sich
geeignete Komprimierungen berechnen. Um eine signifikante
Komplexitätsreduktion ohne Zerstörung der Clusterstruktur zu erzielen, werden
die genannten Methoden in ein mehrstufiges Verfahren eingebettet. Da neben der
Identifizierung der Cluster auch deren effiziente Beschreibung notwendig ist,
wird ferner eine spezielle Art der Komprimierung vorgestellt, der eine
Boxdiskretisierung des Datenraumes zugrunde liegt. Diese ermöglicht die
einfache Generierung von regelbasierten Clusterbeschreibungen. Für einen
speziellen Typ von Homogenitätsfunktionen, die eine stochastische Eigenschaft
besitzen, wird das mehrstufige Clusterverfahren um eine Perroncluster Analyse
erweitert. Dadurch wird die Anzahl der Cluster, im Gegensatz zu herkömmlichen
Verfahren, nicht mehr als Eingabeparameter benötigt. Mit dem entwickelten
Clusterverfahren kann erstmalig eine computergestützte Konformationsanalyse
großer, für die Praxis relevanter Biomoleküle durchgeführt werden. Am Beispiel
des HIV Protease Inhibitors VX-478 wird dies detailliert beschrieben.
de
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject
cluster analysis
dc.subject
self-organizing maps
dc.subject
molecular dynamics
dc.subject.ddc
000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik
dc.title
Adaptive Multilevel Cluster Analysis by Self-Organizing Box Maps
dc.contributor.firstReferee
Prof. Dr. Dr. h.c. Peter Deuflhard
dc.contributor.furtherReferee
Prof. Dr. Peter Rentrop
dc.date.accepted
2002-07-10
dc.date.embargoEnd
2002-07-19
dc.identifier.urn
urn:nbn:de:kobv:188-2002001258
dc.title.translated
Adaptive Multilevel Cluster Analysis by Self-Organizing Box Maps
de
refubium.affiliation
Mathematik und Informatik
de
refubium.mycore.fudocsId
FUDISS_thesis_000000000679
refubium.mycore.transfer
http://www.diss.fu-berlin.de/2002/125/
refubium.mycore.derivateId
FUDISS_derivate_000000000679
dcterms.accessRights.dnb
free
dcterms.accessRights.openaire
open access