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

Die Vision des "Ubiquotous Computing" verspricht schon lange eine Welt, in der jeder Dienst zu jeder Zeit an jedem Ort verfügbar ist. Darüber hinaus soll die Alltagswelt mit Rechnern durchsetzt sein, ohne dass die Benutzer diese als solche bewusst wahrnehmen. Durch Kooperation und Informationsaustausch sollen die Benutzer unaufdringlich bei ihren Aufgaben unterstützt werden, genau abgestimmt auf ihre jeweilige Situation. Dafür bedarf es kontextsensitiver Dienste. Kontextsensitive Dienste sind nicht neu: Das Licht im Auto wird automatisch angeschaltet, sobald es draußen dunkler wird. Hierzu sind Sensoren und Aktuatoren fest verknüpft. Um der Vision von ubiquitären Computersystemen näher zu kommen, ist es wichtig, dass Kontextinformationen auch in spontanen, dynamischen Konfigurationen bereitgestellt, gefunden, ausgetauscht und verstanden werden können. Dies ist die Ausgangssituation dieser Arbeit: Kontextbereitstellung in offenen, ubiquitären Systemen. Dazu werden mehrere Beiträge geliefert: Eine Modellierung für Kontextinformationen, eine darauf aufbauende, dynamische Beschreibung für Kontextinformationsdienste und die Einführung von Kontextkonstruktionsbäumen, mit denen auf nicht-verfügbare Kontextinformationen geschlossen werden kann, oder mit denen diese wenigstens abgeschätzt werden können.

Innovative technologies in the area of multimedia and mechanical engineering as well as novel methods for data acquisition in different scientific subareas, including geo-science, environmental science, medicine, biology and astronomy, enable a more exact representation of the data, and thus, a more precise data analysis. The resulting quantitative and qualitative growth of specifically spatial and temporal data leads to new challenges for the management and processing of complex structured objects and requires the

employment of efficient and effective methods for data analysis.

Spatial data denote the description of objects in space by a well-defined extension, a specific location and by their

relationships to the other objects. Classical representatives of complex structured spatial objects are three-dimensional CAD data from the sector "mechanical engineering" and two-dimensional bounded regions from the area "geography". For industrial applications, efficient collision and intersection queries are of great

importance.

Temporal data denote data describing time dependent processes, as for instance the duration of specific events or the description of time varying attributes of objects. Time series belong to one of the

most popular and complex type of temporal data and are the most important form of description for time varying processes. An

elementary type of query in time series databases is the similarity query which serves as basic query for data mining applications.

The main target of this thesis is to develop an effective and efficient algorithm supporting collision queries on spatial data as well as similarity queries on temporal data, in particular, time

series. The presented concepts are based on the efficient management of interval sequences which are suitable for spatial and temporal data. The effective analysis of the underlying objects will be

efficiently supported by adequate access methods.

First, this thesis deals with collision queries on complex spatial objects which can be reduced to intersection queries on interval sequences. We introduce statistical methods for the grouping of

subsequences. Involving the concept of multi-step query processing, these methods enable the user to accelerate the query process drastically. Furthermore, in this thesis we will develop a cost

model for the multi-step query process of interval sequences in distributed systems. The proposed approach successfully supports a cost based query strategy.

Second, we introduce a novel similarity measure for time series. It allows the user to focus specific time series amplitudes for the similarity measurement. The new similarity model defines two time series to be similar iff they show similar temporal behavior w.r.t. being below or above a specific threshold. This type of query is

primarily required in natural science applications. The main goal of this new query method is the detection of anomalies and the adaptation to new claims in the area of data mining in time series

databases. In addition, a semi-supervised cluster analysis method will be presented which is based on the introduced similarity model for time series.

The efficiency and effectiveness of the proposed techniques will be extensively discussed and the advantages against existing methods experimentally proofed by means of datasets derived from real-world

applications.

The Extensible Markup Language (XML) is extremely popular as a generic markup language for text documents with an explicit hierarchical structure. The different types of XML data found in today’s document repositories, digital libraries, intranets and on the web range from flat text with little meaningful structure to be queried, over truly semistructured data with a

rich and often irregular structure, to rather rigidly structured documents with little text that would also fit a relational database system (RDBS). Not surprisingly, various ways of storing and retrieving XML data have been investigated, including native XML systems, relational engines based on RDBSs, and hybrid combinations thereof. Over the years a number of native XML indexing techniques have emerged, the most important ones being structure indices and labelling schemes. Structure indices represent the document schema (i.e., the hierarchy of nested tags that occur in the documents) in a compact

central data structure so that structural query constraints (e.g., path or tree patterns) can be efficiently matched without accessing the documents. Labelling schemes specify ways to assign unique identifiers, or labels, to the document nodes so that specific relations (e.g., parent/child) between individual nodes can be inferred from their labels alone in a decentralized manner,

again without accessing the documents themselves. Since both structure indices and labelling schemes provide compact approximate views on the document structure, we collectively refer to them as structural summaries. This work presents new structural summaries that enable highly efficient and scalable XML retrieval in native, relational and hybrid systems. The key contribution of our approach is threefold. (1) We introduce BIRD, a very efficient and expressive labelling scheme for XML, and the CADG, a combined text and structure index, and combine them as two complementary building blocks of the same XML retrieval system. (2) We propose a purely relational variant of BIRD and the CADG, called RCADG, that is extremely fast and scales up to large document collections. (3) We present the RCADG Cache, a hybrid system that enhances the RCADG with incremental query evaluation based on cached results of earlier queries. The RCADG Cache exploits schema information in the RCADG to detect cached query results that can supply some or all matches to a new query with little or no computational and I/O effort. A main-memory cache index ensures that reusable query results are quickly retrieved even in a huge cache. Our work shows that structural summaries significantly improve the efficiency and scalability of XML retrieval systems in several ways. Former relational approaches have largely ignored structural summaries. The RCADG shows that these native indexing techniques are equally effective for XML retrieval in RDBSs. BIRD, unlike some other labelling schemes, achieves high retrieval performance with a fairly modest storage overhead. To the best of our

knowledge, the RCADG Cache is the only approach to take advantage of structural summaries for effectively detecting query containment or overlap. Moreover, no other XML cache we know of exploits intermediate results that are produced as a by-product during the evaluation from scratch. These are valuable cache contents that increase the effectiveness of the cache at no extra computational cost. Extensive experiments quantify the practical benefit of all of the proposed techniques, which amounts to a performance gain of several orders of magnitude compared to various other approaches.

Probabilistic modeling for data mining and machine learning problems is a fundamental research area. The general approach is to assume a generative model underlying the observed data, and estimate model parameters via likelihood maximization. It has the deep probability theory as the mathematical background, and enjoys a large amount of methods from statistical learning, sampling theory and Bayesian statistics. In this thesis we study several advanced probabilistic models for data clustering and feature projection, which are the two important unsupervised learning problems.

The goal of clustering is to group similar data points together to uncover the data clusters. While numerous methods exist for various clustering tasks, one important question still remains, i.e., how to automatically determine the number of clusters. The first part of the thesis answers this question from a mixture modeling perspective. A finite mixture model is first introduced for clustering, in which each mixture component is assumed to be an exponential family distribution for generality. The model is then extended to an infinite mixture model, and its strong connection to Dirichlet process (DP) is uncovered which is a non-parametric Bayesian framework. A variational Bayesian algorithm called VBDMA is derived from this new insight to learn the number of clusters automatically, and empirical studies on some 2D data sets and an image data set verify the effectiveness of this algorithm.

In feature projection, we are interested in dimensionality reduction and aim to find a low-dimensional feature representation for the data. We first review the well-known principal component analysis (PCA) and its probabilistic interpretation (PPCA), and then generalize PPCA to a novel probabilistic model which is able to handle non-linear projection known as kernel PCA. An expectation-maximization (EM) algorithm is derived for kernel PCA such that it is fast and applicable to large data sets. Then we propose a novel supervised projection method called MORP, which can take the output information into account in a supervised learning context. Empirical studies on various data sets show much better results compared to unsupervised projection and other supervised projection methods. At the end we generalize MORP probabilistically to propose SPPCA for supervised projection, and we can also naturally extend the model to S2PPCA which is a semi-supervised projection method. This allows us to incorporate both the label information and the unlabeled data into the projection process.

In the third part of the thesis, we introduce a unified probabilistic model which can handle data clustering and feature projection jointly. The model can be viewed as a clustering model with projected features, and a projection model with structured documents. A variational Bayesian learning algorithm can be derived, and it turns out to iterate the clustering operations and projection operations until convergence. Superior performance can be obtained for both clustering and projection.

The conservation of continuous symmetries in two-dimensional systems with interaction is a classical subject of statistical mechanics. Here we establish such a result for internal transformations and spatial translations of Gibbsian systems of marked particles with two body-interaction, where the interesting cases of of singular, hard-core and discontinuous interaction are included.

As measurement of gene expression using microarrays has become a standard high throughput

method in molecular biology, the analysis of gene expression data is still a very active

area of research in bioinformatics and statistics. Despite some issues in quality and reproducibility

of microarray and derived data, they are

still considered as one of the most promising experimental techniques for the understanding

of complex molecular mechanisms.

This work approaches the problem of expression data analysis using contextual information.

While all analyses must be based on sound statistical data processing, it is also

important to include biological knowledge to arrive at biologically interpretable results.

After giving an introduction and some biological background, in chapter 2 some standard

methods for the analysis of microarray data including normalization, computation

of differentially expressed genes, and clustering are reviewed. The first source of context

information that is used to aid in the interpretation of the data, is functional annotation

of genes. Such information is often represented using ontologies such as gene ontology. GO annotations are provided by many gene and

protein databases and have been used to find functional groups that are significantly enriched

in differentially expressed, or otherwise conspicuous genes. In gene clustering approaches,

functional annotations have been used to find enriched functional classes within

each cluster. In chapter 3, a clustering method for the samples of an expression data set

is described that uses GO annotations during the clustering process in order to find functional

classes that imply a particularly strong separation of the samples. The resulting

clusters can be interpreted more easily in terms of GO classes. The clustering method was

developed in joint work with Henning Redestig.

More complex biological information that covers interactions between biological objects

is contained in networks. Such networks can be obtained from public databases of metabolic

pathways, signaling cascades, transcription factor binding sites, or high-throughput measurements

for the detection of protein-protein interactions such as yeast two hybrid experiments.

Furthermore, networks can be inferred using literature mining approaches or

network inference from expression data. The information contained in such networks is

very heterogenous with respect to the type, the quality and the completeness of the contained

data. ToPNet, a software tool for the interactive analysis of networks and gene

expression data has been developed in cooperation with Daniel Hanisch. The basic analysis and visualization methods as well as some important concepts

of this tool are described in chapter 4.

In order to access the heterogeneous data represented as networks with annotated experimental

data and functions, it is important to provide advanced querying functionality.

Pathway queries allow the formulation of

network templates that can include functional annotations as well as expression data. The

pathway search algorithm finds all instances of the template in a given network. In order

to do so, a special case of the well known subgraph isomorphism problem has to be

solved. Although the algorithm has exponential running time in the worst case, some implementation

tricks make it run fast enough for practical purposes. Often, a pathway query

has many matching instances, and it is important to assess the statistical significance of

the individual instances with respect to expression data or other criteria. In chapter 5

the pathway query language and the pathway search algorithm are described in detail and

some theoretical properties are derived. Furthermore, some scoring methods that have

been implemented are described. The possibility of combining different scoring schemes

for different parts of the query result in very flexible scoring capabilities.

In chapter 6, some applications of the methods are described, us

Many areas of applied statistics have become aware of the problem of measurement error-prone variables and their appropriate analysis. Simply ignoring the error in the analysis usually leads to biased estimates, like e.g. in the regression with error-prone covariates. While this problem has been discussed at length for parametric regression, only few methods exist to handle nonparametric regression under error, which are usually either computer intensive or little effective. This thesis develops new methods achieving the correction quality of state of the art methods while demanding only a trickle of their computing time.

These new methods use the so-called relevance vector machine (RVM) for nonparametric regression - now enhanced by correction methods based on the ideas of regression calibration, the so-called SIMEX and Markov Chain Monte Carlo (MCMC) correction. All methods are compared in simulation studies regarding Gaussian, binary and Poisson responses. This thesis also discusses the case of multiple error-prone covariates.

Furthermore, a MCMC based correction method for nonparametric regression of binary longitudinal data with covariate measurement error is introduced. This data scenario is often encountered, e.g. in epidemiological applications.