Fakultät für Mathematik, Informatik und Statistik - Digitale Hochschulschriften der LMU - Teil 01/02

Multivariate adaptive regression splines (MARS) are a useful tool to identify

linear and nonlinear effects and interactions between two covariates. In this dissertation a new proposal to model survival type data with MARS is introduced. Martingale and deviance residuals of a Cox PH model are used as response in a common MARS approach to model functional forms of covariate effects as well as possible interactions in a data-driven way. Simulation studies prove that the new method yields a better fit to the data than the traditional Cox PH approach.

The analysis of real data of the German Heart Center on survivors of an acute myocardial infarction also documents the good performance of the method.

As new graph structured data is constantly being generated, learning and data mining on graphs have become a challenge in application areas such as molecular biology, telecommunications, chemoinformatics, and social network analysis. The central algorithmic problem in these areas, measuring similarity of graphs, has therefore received extensive attention in the recent past. Unfortunately, existing approaches are slow, lacking in expressivity, or hard to parameterize.

Graph kernels have recently been proposed as a theoretically sound and promising approach to the problem of graph comparison. Their attractivity stems from the fact that by defining a kernel on graphs, a whole family of data mining and machine learning algorithms becomes applicable to graphs.

These kernels on graphs must respect both the information represented by the topology and the node and edge labels of the graphs, while being efficient to compute. Existing methods fall woefully short; they miss out on important topological information, are plagued by runtime issues, and do not scale to large graphs. Hence the primary goal of this thesis is to make learning and data mining with graph kernels feasible.

In the first half of this thesis, we review and analyze the shortcomings of state-of-the-art graph kernels. We then propose solutions to overcome these weaknesses. As highlights of our research, we

- speed up the classic random walk graph kernel from O(n^6) to O(n^3), where n is the number of nodes in the larger graph, and by a factor of up to 1,000 in CPU runtime, by extending concepts from Linear Algebra to Reproducing Kernel Hilbert Spaces,

- define novel graph kernels based on shortest paths that avoid tottering and outperform random walk kernels in accuracy,

- define novel graph kernels that estimate the frequency of small subgraphs within a large graph and that work on large graphs hitherto not handled by existing graph kernels.

In the second half of this thesis, we present algorithmic solutions to two novel problems in graph mining. First, we define a two-sample test on graphs. Given two sets of graphs, or a pair of graphs, this test lets us decide whether these graphs are likely to originate from the same underlying distribution. To solve this so-called two-sample-problem, we define the first kernel-based two-sample test. Combined with graph kernels, this results in the first two-sample test on graphs described in the literature.

Second, we propose a principled approach to supervised feature selection on graphs. As in feature selection on vectors, feature selection on graphs aims at finding features that are correlated with the class membership of a graph. Towards this goal, we first define a family of supervised feature selection algorithms based on kernels and the Hilbert-Schmidt Independence Criterion. We then show how to extend this principle of feature selection to graphs, and how to combine it with gSpan, the state-of-the-art method for frequent subgraph mining. On several benchmark datasets, our novel procedure manages to select a small subset of dozens of informative features among thousands and millions of subgraphs detected by gSpan. In classification experiments, the features selected by our method outperform those chosen by other feature selectors in terms of classification accuracy.

Along the way, we also solve several problems that can be deemed contributions in their own right:

- We define a unifying framework for describing both variants of random walk graph kernels proposed in the literature.

- We present the first theoretical connection between graph kernels and molecular descriptors from chemoinformatics.

- We show how to determine sample sizes for estimating the frequency of certain subgraphs within a large graph with a given precision and confidence, which promises to be a key to the solution of important problems in data mining and bioinformatics.

Three branches of computer science immediately benefit from our findings:

Model driven software engineering (MDSE) is becoming a widely accepted approach for developing complex applications and it is on its way to be one of the most promising paradigms in software engineering. MDSE advocates the use of models as the key artifacts in all phases of the development process, from analysis to design, implementation and testing. The most promising approach to model driven engineering is the Model Driven Architecture (MDA) defined by the Object Management Group (OMG). Applications are modeled at a platform independent level and are transformed to (possibly several) platform specific implementations. Model driven Web engineering (MDWE) is the application of model driven engineering to the domain of Web application development where it might be particularly helpful because of the continuous evolution of Web technologies and platforms.

However, most current approaches for MDWE provide only a partial application of the MDA pattern. Further, metamodels and transformations are not always made explicit and metamodels are often too general or do not contain sufficient information for the automatic code generation. Thus, the main goal of this work is the complete application of the MDA pattern to the Web application domain from analysis to the generated implementation, with transformations playing an important role at every stage of the development process. Explicit metamodels are defined for the platform independent analysis and design and for the platform specific implementation of dynamic Web applications. Explicit transformations allow the automatic generation of executable code for a broad range of technologies. For pursuing this goal, the following approach was chosen.

A metamodel is defined for the platform independent analysis and for the design of the content, navigation, process and presentation concerns of Web applications as a conservative extension of the UML (Unified Modeling Language) metamodel, together with a cor-responding UML profile as notation. OCL constraints ensure the well-formedness of models and are checked by transformations. Transformations implement the systematic evolution of analysis and design models. A generic platform for Web applications built on an open-source Web platform and a generic runtime environment is proposed that represents a family of platforms supporting the combination of a broad range of technologies. The transformation to the platform specific models for this generic platform is decomposed along the concerns of Web applications to cope in a fine-grained way with technology changes. For each of the concerns a metamodel for the corresponding technology is defined together with the corresponding transformations from the platform independent design models. The resulting models are serialized to code by means of serialization transformations.

Das Ziel der Arbeit ist es, einen Beitrag zur mikroskopischen Begründung der Streutheorie zu liefern, d.h. zu zeigen, inwiefern der asymptotische Formalismus der Streutheorie, mit Objekten wie der $S$-Matrix sowie den ein- und auslaufenden Asymptoten $\psi_{in}$ und $\psi_{out},$ aus einer mikroskopischen Beschreibung des zugrunde liegenden Systems abgeleitet werden kann. Wir konzentrieren uns dabei auf zwei Dinge. Zunächst wird die Austrittsstatistik von einem $N$-Teilchensystem durch weit entfernte Oberflächen abgeleitet. Anschließend beschränken wir uns auf die $1$-Teilchenstreuung und verwenden die Austrittsstatistik, um den Streuquerschnitt aus einer mikroskopischen Beschreibung der Streusituation abzuleiten. Die zugrunde liegende Dynamik ist die Bohmsche Mechanik, eine Theorie über die Bewegung von Punktteilchen, die alle Ergebnisse der nichtrelativistischen Quantenmechanik reproduziert.

In Location-based Community Services (LBCSs) mobile users interchange and correlate their spatial positions, for example, in order to find out which other community members are currently staying nearby.

The so-called position management is responsible for the transmission, analysis, processing and access control of position information, which is directed along a corresponding supply chain. The supply chain spans from the mobile device of the target person, where the position is derived, for example, by GPS, via intermediaries like the location or LBS provider, to the domain of the user.

Community services pose special requirements on position management, which can be coarsely divided into the fields privacy protection and efficiency:

First, the target person must be able to control by who and under which circumstances her position information is accessed.

To guarantee that, it must be possible to anonymize the position data with respect to the location and LBS provider, for which so far no technique exists that is suited for community services. Also, the target person must be able to authorize requests to access her position in an easy and socially acceptable fashion.

Second, concepts for efficiently realizing so-called proactive multi-target LBCSs are needed. These services are automatically triggered as soon as two or more target person have entered into a certain pre-defined spatial constellation. An example is buddy tracking, which automatically detects when two persons have approached each other below a certain proximity distance.

The technical problem to solve is the frequent transmission of position information over the scarce air-interface and the associated energy consumption at the mobile terminal of the target person.

This dissertation develops new concepts in both of the sketched fields and shows their feasibility based on numerous simulations and analytical reflection.

Also the TraX-platform is presented, which practically implements the developed concepts.

Je detaillierter ein Fahrer über den Streckenabschnitt informiert ist, den er in naher Zukunft befahren wird, desto größer ist die Wahrscheinlichkeit, dass er rechtzeitig und angemessen auf komplexe Verkehrssituationen reagiert. Die umfassende Verfügbarkeit von qualitativ hochwertigen Kontextinformationen im Fahrzeug leistet vor diesem Hintergrund einen wichtigen Beitrag zur Erhöhung der Verkehrssicherheit und -effizienz.

Ziel dieser Arbeit ist eine zuverlässige Vorhersage der zukünftigen Fahrsituation auf Basis des gemeinschaftlich bekannten Wissens der Verkehrsteilnehmer. Dabei steht die Verwaltung ortsbezogener Kontextinformationen, die Fusion von verschiedenartigen Informationsquellen, sowie die Problematik der Verteilung der von den Fahrzeugen erzeugten Kontextinformationen über automobile Ad-hoc Netzen im Fokus der Arbeit.

Aufbauend auf einer formalen Lösungsspezifikation beschreibt die Arbeit einen zweistufigen Bewertungsprozess, der es erlaubt, auf Basis verteilter Sensorbeobachtungen unterschiedlicher Fahrzeuge ein Wahrscheinlichkeitsmaß für das Eintreten eines konkreten Zustands eines relevanten Fahrkontexts abzuleiten. Die räumlichen und zeitlichen Eigenschaften des Kontextaspekts werden dabei gewichtet interpoliert. Anschließend werden auf Basis eines Bayesschen Netzes die kausalen Zusammenhänge unterschiedlicher Kontextaspekte quervalidiert.

Zudem wird aufgezeigt, wie Kontextinformationen zwischen Fahrzeugen in einem automobilen Ad-hoc Netzwerk ausgetauscht werden können. Das aus drahtgebundenen Netzen bekannte Konzept der Nutzenmaximierung des Netzwerks wird hierzu auf die speziellen Charakteristika automobiler Netze erweitert. Es wird zudem eine schichtenübergreifende Lösungsarchitektur vorgestellt, die situationsadaptiv sowohl kurze Latenzzeiten für kritische Nachrichten, als auch eine nachhaltige Skalierbarkeit des Netzes in Szenarien mit geringen und hohen Fahrzeugdichten sicherstellt. Der Kanalzugriff und die Verbreitung der Kontextinformationen im Netzwerk basieren dabei auf einer situationsabhängigen Bewertung des Anwendungsnutzens der zu übertragenden Nachrichten. Mit Hilfe von Simulationen wird das Verhalten des Systems bewertet.

Durch eine ontologiebasierte Verwaltung wird auch nichtfahrzeugbezogenen Systemen eine domänenübergreifende Nutzung der Sensorinformationen und kausalen Zusammenhänge ermöglicht.

It is well-known that traditional clustering methods considering all dimensions of the feature space usually fail in terms of efficiency and effectivity when applied to high-dimensional data. This poor behavior is based on the fact that clusters may not be found in the high-dimensional feature space, although clusters exist in subspaces of the feature space. To overcome these limitations of traditional clustering methods, several methods for subspace clustering have been proposed recently. Subspace clustering algorithms aim at automatically identifying lower dimensional subspaces of the feature space in which clusters exist.

There exist two types of subspace clustering algorithms: Algorithms for detecting clusters in axis-parallel subspaces and, as an extension, algorithms for finding clusters in subspaces which are arbitrarily oriented. Generally, the subspace clusters may be hierarchically nested, i.e., several subspace clusters of low dimensionality may form a subspace cluster of higher dimensionality. Since existing subspace clustering methods are not able to detect these complex structures, hierarchical approaches for subspace clustering have to be applied.

The goal of this dissertation is to develop new efficient and effective methods for hierarchical subspace clustering by identifying novel challenges for the hierarchical approach and proposing innovative and solid solutions for these challenges.

The first Part of this work deals with the analysis of hierarchical subspace clusters in axis-parallel subspaces. Two new methods are proposed that search simultaneously for subspace clusters of arbitrary dimensionality in order to detect complex hierarchies of subspace clusters. Furthermore, a new visualization model of the clustering result by means of a graph representation is provided.

In the second Part of this work new methods for hierarchical clustering in arbitrarily oriented subspaces of the feature space are discussed. The so-called correlation clustering can be seen as an extension of axis-parallel subspace clustering. Correlation clustering aims at grouping the data set into subsets, the so-called correlation clusters, such that the objects in the same correlation cluster show uniform attribute correlations. Two new hierarchical approaches are proposed which combine density-based clustering with Principal Component Analysis in order to identify hierarchies of correlation clusters.

The last Part of this work addresses the analysis and interpretation of the results obtained from correlation clustering algorithms. A general method is introduced to extract quantitative information on the linear dependencies between the objects of given correlation clusters. Furthermore, these quantitative models can be used to predict the probability that an object is created by one of these models.

Both, the efficiency and the effectiveness of the presented techniques are thoroughly analyzed. The benefits over traditional approaches are shown by evaluating the new methods on synthetic as well as real-world test data sets.

Magnetic resonance diffusion tensor imaging (DTI) allows to infere the ultrastructure of living tissue. In brain mapping, neural fiber trajectories can be identified by exploiting the anisotropy of diffusion processes. Manifold statistical methods may be linked into the comprehensive processing chain that is spanned between DTI raw images and the reliable visualization of fibers. In this work, a space varying coefficients model (SVCM) using penalized B-splines was developed to integrate diffusion tensor estimation, regularization and interpolation into a unified framework. The implementation challenges originating in multiple 3d space varying coefficient surfaces and the large dimensions of realistic datasets were met by incorporating matrix sparsity and efficient model approximation. Superiority of B-spline based SVCM to the standard approach was demonstrable from simulation studies in terms of the precision and accuracy of the individual tensor elements. The integration with a probabilistic fiber tractography algorithm and application on real brain data revealed that the unified approach is at least equivalent to the serial application of voxelwise estimation, smoothing and interpolation. From the error analysis using boxplots and visual inspection the conclusion was drawn that both the standard approach and the B-spline based SVCM may suffer from low local adaptivity. Therefore, wavelet basis functions were employed for filtering diffusion tensor fields. While excellent local smoothing was indeed achieved by combining voxelwise tensor estimation with wavelet filtering, no immediate improvement was gained for fiber tracking. However, the thresholding strategy needs to be refined and the proposed model of an incorporation of wavelets into an SVCM needs to be implemented to finally assess their utility for DTI data processing.

In summary, an SVCM with specific consideration of the demands of human brain DTI data was developed and implemented, eventually representing a unified postprocessing framework. This represents an experimental and statistical platform to further improve the reliability of tractography.