@misc{WeberRungsarityotinSchliep, author = {Weber, Marcus and Rungsarityotin, Wasinee and Schliep, Alexander}, title = {Perron Cluster Analysis and Its Connection to Graph Partitioning for Noisy Data}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8140}, number = {04-39}, abstract = {The problem of clustering data can be formulated as a graph partitioning problem. Spectral methods for obtaining optimal solutions have reveceived a lot of attention recently. We describe Perron Cluster Cluster Analysis (PCCA) and, for the first time, establish a connection to spectral graph partitioning. We show that in our approach a clustering can be efficiently computed using a simple linear map of the eigenvector data. To deal with the prevalent problem of noisy and possibly overlapping data we introduce the min Chi indicator which helps in selecting the number of clusters and confirming the existence of a partition of the data. This gives a non-probabilistic alternative to statistical mixture-models. We close with showing favorable results on the analysis of gene expressi on data for two different cancer types.}, language = {en} } @misc{DeuflhardWeber, author = {Deuflhard, Peter and Weber, Marcus}, title = {Robust Perron Cluster Analysis in Conformation Dynamics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7415}, number = {03-19}, abstract = {The key to molecular conformation dynamics is the direct identification of metastable conformations, which are almost invariant sets of molecular dynamical systems. Once some reversible Markov operator has been discretized, a generalized symmetric stochastic matrix arises. This matrix can be treated by Perron cluster analysis, a rather recent method involving a Perron cluster eigenproblem. The paper presents an improved Perron cluster analysis algorithm, which is more robust than earlier suggestions. Numerical examples are included.}, language = {en} } @misc{Weber, author = {Weber, Marcus}, title = {Clustering by using a simplex structure}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7782}, number = {04-03}, abstract = {In this paper we interpret clustering as a mapping of data into a simplex. If the data itself has simplicial struture this mapping becomes linear. Spectral analysis is an often used tool for clustering data. We will show that corresponding singular vectors or eigenvectors comprise simplicial structure. Therefore they lead to a cluster algorithm, which consists of a simple linear mapping. An example for this kind of algorithms is the Perron cluster analysis (PCCA). We have applied it in practice to identify metastable sets of molecular dynamical systems. In contrast to other algorithms, this kind of approach provides an a priori criterion to determine the number of clusters. In this paper we extend the ideas to more general problems like clustering of bipartite graphs.}, language = {en} } @phdthesis{Galliat, author = {Galliat, Tobias}, title = {Adaptive Multilevel Cluster Analysis by Self-Organizing Box Maps}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:188-2002001258}, 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{\"u}glich eines gegebenen Maßes maximal homogen sind. Die Homogenit{\"a}t der Objekte h{\"a}ngt dabei direkt oder indirekt von den Auspr{\"a}gungen ab, die sie f{\"u}r eine Anzahl festgelegter Attribute besitzen. Die Suche nach Clustern l{\"a}ß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{\"o}tigt entweder heuristische Optimierungsverfahren oder Methoden zur Reduktion der Komplexit{\"a}t. In der Vergangenheit wurden in der Forschung fast ausschließlich Verfahren f{\"u}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{\"a}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{\"u}len von zentraler Bedeutung sind, nicht auf einer geometrischen, sondern einer dynamischen {\"A}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{\"a}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{\"o}rt, wenn die Komprimierung fein genug ist. Mittels selbstorganisierter neuronaler Netze lassen sich geeignete Komprimierungen berechnen. Um eine signifikante Komplexit{\"a}tsreduktion ohne Zerst{\"o}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{\"o}glicht die einfache Generierung von regelbasierten Clusterbeschreibungen. F{\"u}r einen speziellen Typ von Homogenit{\"a}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{\"o}mmlichen Verfahren, nicht mehr als Eingabeparameter ben{\"o}tigt. Mit dem entwickelten Clusterverfahren kann erstmalig eine computergest{\"u}tzte Konformationsanalyse großer, f{\"u}r die Praxis relevanter Biomolek{\"u}le durchgef{\"u}hrt werden. Am Beispiel des HIV Protease Inhibitors VX-478 wird dies detailliert beschrieben.}, language = {en} }