Data-driven clustering : new methods and applications

Abstract : This work is concerned with the development and application of novel unsupervised learning methods, having in mind two target applications: the analysis of forensic case data and the classification of remote sensing images. First, a method based on a symbolic optimization of the inter-sample distance measure is proposed to improve the flexibility of spectral clustering algorithms, and applied to the problem of forensic case data. This distance is optimized using a loss function related to the preservation of neighborhood structure between the input space and the space of principal components, and solutions are found using genetic programming. Results are compared to a variety of state-of--the-art clustering algorithms. Subsequently, a new large-scale clustering method based on a joint optimization of feature extraction and classification is proposed and applied to various databases, including two hyperspectral remote sensing images. The algorithm makes uses of a functional model (e.g., a neural network) for clustering which is trained by stochastic gradient descent. Results indicate that such a technique can easily scale to huge databases, can avoid the so-called out-of-sample problem, and can compete with or even outperform existing clustering algorithms on both artificial data and real remote sensing images. This is verified on small databases as well as very large problems. Résumé : Ce travail de recherche porte sur le développement et l'application de méthodes d'apprentissage dites non supervisées. Les applications visées par ces méthodes sont l'analyse de données forensiques et la classification d'images hyperspectrales en télédétection. Dans un premier temps, une méthodologie de classification non supervisée fondée sur l'optimisation symbolique d'une mesure de distance inter-échantillons est proposée. Cette mesure est obtenue en optimisant une fonction de coût reliée à la préservation de la structure de voisinage d'un point entre l'espace des variables initiales et l'espace des composantes principales. Cette méthode est appliquée à l'analyse de données forensiques et comparée à un éventail de méthodes déjà existantes. En second lieu, une méthode fondée sur une optimisation conjointe des tâches de sélection de variables et de classification est implémentée dans un réseau de neurones et appliquée à diverses bases de données, dont deux images hyperspectrales. Le réseau de neurones est entraîné à l'aide d'un algorithme de gradient stochastique, ce qui rend cette technique applicable à des images de très haute résolution. Les résultats de l'application de cette dernière montrent que l'utilisation d'une telle technique permet de classifier de très grandes bases de données sans difficulté et donne des résultats avantageusement comparables aux méthodes existantes.

Learning spatial filters for multispectral image segmentation

We present a novel filtering method for multispectral satellite image classification. The proposed method learns a set of spatial filters that maximize class separability of binary support vector machine (SVM) through a gradient descent approach. Regularization issues are discussed in detail and a Frobenius-norm regularization is proposed to efficiently exclude uninformative filters coefficients. Experiments carried out on multiclass one-against-all classification and target detection show the capabilities of the learned spatial filters.

Large-scale clustering through functional embedding

We present a new framework for large-scale data clustering. The main idea is to modify functional dimensionality reduction techniques to directly optimize over discrete labels using stochastic gradient descent. Compared to methods like spectral clustering our approach solves a single optimization problem, rather than an ad-hoc two-stage optimization approach, does not require a matrix inversion, can easily encode prior knowledge in the set of implementable functions, and does not have an ?out-of-sample? problem. Experimental results on both artificial and real-world datasets show the usefulness of our approach.

Some solutions to obtain very efficient separations in isocratic and gradient modes using small particles size and ultra-high pressure.

The UHPLC strategy which combines sub-2 microm porous particles and ultra-high pressure (>1000 bar) was investigated considering very high resolution criteria in both isocratic and gradient modes, with mobile phase temperatures between 30 and 90 degrees C. In isocratic mode, experimental conditions to reach the maximal efficiency were determined using the kinetic plot representation for DeltaP(max)=1000 bar. It has been first confirmed that the molecular weight of the compounds (MW) was a critical parameter which should be considered in the construction of such curves. With a MW around 1000 g mol(-1), efficiencies as high as 300,000 plates could be theoretically attained using UHPLC at 30 degrees C. By limiting the column length to 450 mm, the maximal plate count was around 100,000. In gradient mode, the longest column does not provide the maximal peak capacity for a given analysis time in UHPLC. This was attributed to the fact that peak capacity is not only related to the plate number but also to column dead time. Therefore, a compromise should be found and a 150 mm column should be preferentially selected for gradient lengths up to 60 min at 30 degrees C, while the columns coupled in series (3x 150 mm) were attractive only for t(grad)>250 min. Compared to 30 degrees C, peak capacities were increased by about 20-30% for a constant gradient length at 90 degrees C and gradient time decreased by 2-fold for an identical peak capacity.

Formation of the long range Dpp morphogen gradient.

The TGF-β homolog Decapentaplegic (Dpp) acts as a secreted morphogen in the Drosophila wing disc, and spreads through the target tissue in order to form a long range concentration gradient. Despite extensive studies, the mechanism by which the Dpp gradient is formed remains controversial. Two opposing mechanisms have been proposed: receptor-mediated transcytosis (RMT) and restricted extracellular diffusion (RED). In these scenarios the receptor for Dpp plays different roles. In the RMT model it is essential for endocytosis, re-secretion, and thus transport of Dpp, whereas in the RED model it merely modulates Dpp distribution by binding it at the cell surface for internalization and subsequent degradation. Here we analyzed the effect of receptor mutant clones on the Dpp profile in quantitative mathematical models representing transport by either RMT or RED. We then, using novel genetic tools, experimentally monitored the actual Dpp gradient in wing discs containing receptor gain-of-function and loss-of-function clones. Gain-of-function clones reveal that Dpp binds in vivo strongly to the type I receptor Thick veins, but not to the type II receptor Punt. Importantly, results with the loss-of-function clones then refute the RMT model for Dpp gradient formation, while supporting the RED model in which the majority of Dpp is not bound to Thick veins. Together our results show that receptor-mediated transcytosis cannot account for Dpp gradient formation, and support restricted extracellular diffusion as the main mechanism for Dpp dispersal. The properties of this mechanism, in which only a minority of Dpp is receptor-bound, may facilitate long-range distribution.

Minimization of Nyquist ghosting for echo-planar imaging at ultra-high fields based on a "negative readout gradient" strategy.

PURPOSE: To improve the traditional Nyquist ghost correction approach in echo planar imaging (EPI) at high fields, via schemes based on the reversal of the EPI readout gradient polarity for every other volume throughout a functional magnetic resonance imaging (fMRI) acquisition train. MATERIALS AND METHODS: An EPI sequence in which the readout gradient was inverted every other volume was implemented on two ultrahigh-field systems. Phantom images and fMRI data were acquired to evaluate ghost intensities and the presence of false-positive blood oxygenation level-dependent (BOLD) signal with and without ghost correction. Three different algorithms for ghost correction of alternating readout EPI were compared. RESULTS: Irrespective of the chosen processing approach, ghosting was significantly reduced (up to 70% lower intensity) in both rat brain images acquired on a 9.4T animal scanner and human brain images acquired at 7T, resulting in a reduction of sources of false-positive activation in fMRI data. CONCLUSION: It is concluded that at high B(0) fields, substantial gains in Nyquist ghost correction of echo planar time series are possible by alternating the readout gradient every other volume.

Improved SNR efficiency in gradient echo coronary MRA with high temporal resolution using parallel imaging.

Contemporary coronary magnetic resonance angiography techniques suffer from signal-to-noise ratio (SNR) constraints. We propose a method to enhance SNR in gradient echo coronary magnetic resonance angiography by using sensitivity encoding (SENSE). While the use of sensitivity encoding to improve SNR seems counterintuitive, it can be exploited by reducing the number of radiofrequency excitations during the acquisition window while lowering the signal readout bandwidth, therefore improving the radiofrequency receive to radiofrequency transmit duty cycle. Under certain conditions, this leads to improved SNR. The use of sensitivity encoding for improved SNR in three-dimensional coronary magnetic resonance angiography is investigated using numerical simulations and an in vitro and an in vivo study. A maximum 55% SNR enhancement for coronary magnetic resonance angiography was found both in vitro and in vivo, which is well consistent with the numerical simulations. This method is most suitable for spoiled gradient echo coronary magnetic resonance angiography in which a high temporal and spatial resolution is required.

Pom1 gradient buffering through intermolecular auto-phosphorylation.

Concentration gradients provide spatial information for tissue patterning and cell organization, and their robustness under natural fluctuations is an evolutionary advantage. In rod-shaped Schizosaccharomyces pombe cells, the DYRK-family kinase Pom1 gradients control cell division timing and placement. Upon dephosphorylation by a Tea4-phosphatase complex, Pom1 associates with the plasma membrane at cell poles, where it diffuses and detaches upon auto-phosphorylation. Here, we demonstrate that Pom1 auto-phosphorylates intermolecularly, both in vitro and in vivo, which confers robustness to the gradient. Quantitative imaging reveals this robustness through two system's properties: The Pom1 gradient amplitude is inversely correlated with its decay length and is buffered against fluctuations in Tea4 levels. A theoretical model of Pom1 gradient formation through intermolecular auto-phosphorylation predicts both properties qualitatively and quantitatively. This provides a telling example where gradient robustness through super-linear decay, a principle hypothesized a decade ago, is achieved through autocatalysis. Concentration-dependent autocatalysis may be a widely used simple feedback to buffer biological activities.

Multi-scale support vector algorithms for hot spot detection and modelling

The algorithmic approach to data modelling has developed rapidly these last years, in particular methods based on data mining and machine learning have been used in a growing number of applications. These methods follow a data-driven methodology, aiming at providing the best possible generalization and predictive abilities instead of concentrating on the properties of the data model. One of the most successful groups of such methods is known as Support Vector algorithms. Following the fruitful developments in applying Support Vector algorithms to spatial data, this paper introduces a new extension of the traditional support vector regression (SVR) algorithm. This extension allows for the simultaneous modelling of environmental data at several spatial scales. The joint influence of environmental processes presenting different patterns at different scales is here learned automatically from data, providing the optimum mixture of short and large-scale models. The method is adaptive to the spatial scale of the data. With this advantage, it can provide efficient means to model local anomalies that may typically arise in situations at an early phase of an environmental emergency. However, the proposed approach still requires some prior knowledge on the possible existence of such short-scale patterns. This is a possible limitation of the method for its implementation in early warning systems. The purpose of this paper is to present the multi-scale SVR model and to illustrate its use with an application to the mapping of Cs137 activity given the measurements taken in the region of Briansk following the Chernobyl accident.

A Survey of Active Learning Algorithms for Supervised Remote Sensing Image Classification

Defining an efficient training set is one of the most delicate phases for the success of remote sensing image classification routines. The complexity of the problem, the limited temporal and financial resources, as well as the high intraclass variance can make an algorithm fail if it is trained with a suboptimal dataset. Active learning aims at building efficient training sets by iteratively improving the model performance through sampling. A user-defined heuristic ranks the unlabeled pixels according to a function of the uncertainty of their class membership and then the user is asked to provide labels for the most uncertain pixels. This paper reviews and tests the main families of active learning algorithms: committee, large margin, and posterior probability-based. For each of them, the most recent advances in the remote sensing community are discussed and some heuristics are detailed and tested. Several challenging remote sensing scenarios are considered, including very high spatial resolution and hyperspectral image classification. Finally, guidelines for choosing the good architecture are provided for new and/or unexperienced user.

Wnt secretion and gradient formation.

Concentration gradients formed by the lipid-modified morphogens of the Wnt family are known for their pivotal roles during embryogenesis and adult tissue homeostasis. Wnt morphogens are also implicated in a variety of human diseases, especially cancer. Therefore, the signaling cascades triggered by Wnts have received considerable attention during recent decades. However, how Wnts are secreted and how concentration gradients are formed remains poorly understood. The use of model organisms such as Drosophila melanogaster has provided important advances in this area. For instance, we have previously shown that the lipid raft-associated reggie/flotillin proteins influence Wnt secretion and spreading in Drosophila. Our work supports the notion that producing cells secrete Wnt molecules in at least two pools: a poorly diffusible one and a reggie/flotillin-dependent highly diffusible pool which allows morphogen spreading over long distances away from its source of production. Here we revise the current views of Wnt secretion and spreading, and propose two models for the role of the reggie/flotillin proteins in these processes: (i) reggies/flotillins regulate the basolateral endocytosis of the poorly diffusible, membrane-bound Wnt pool, which is then sorted and secreted to apical compartments for long-range diffusion, and (ii) lipid rafts organized by reggies/flotillins serve as "dating points" where extracellular Wnt transiently interacts with lipoprotein receptors to allow its capture and further spreading via lipoprotein particles. We further discuss these processes in the context of human breast cancer. A better understanding of these phenomena may be relevant for identification of novel drug targets and therapeutic strategies.

Liquid line of descent of a basanitic liquid at 1.5 GPa: Constraints for metasomatic vein formation

The metasomatism observed in the oceanic and continental lithosphere is generally interpreted to represent a continuous differentiation process forming anhydrous and hydrous veins plus a cryptic enrichment in the surrounding peridotite. In order to constrain the mechanisms of vein formation and potentially clarify the nature and origin of the initial metasomatic agent, we performed a series of high-pressure experiments simulating the liquid line of descent of a basanitic magma differentiating within continental or mature oceanic lithosphere. This series of experiments has been conducted in an end-loaded piston cylinder apparatus starting from an initial hydrous ne-normative basanite at 1.5 GPa and temperature varying between 1,250 and 980°C. Near-pure fractional crystallization process was achieved in a stepwise manner in 30°C temperature steps and starting compositions corresponding to the liquid composition of the previous, higher-temperature glass composition. Liquids evolve progressively from basanite to peralkaline, aluminum-rich compositions without significant SiO2 variation. The resulting cumulates are characterized by an anhydrous clinopyroxene + olivine assemblage at high temperature (1,250-1,160°C), while at lower temperature (1,130-980°C), hydrous cumulates with dominantly amphibole + minor clinopyroxene, spinel, ilmenite, titanomagnetite and apatite (1,130-980°C) are formed. This new data set supports the interpretation that anhydrous and hydrous metasomatic veins could be produced during continuous differentiation processes of primary, hydrous alkaline magmas at high pressure. However, the comparison between the cumulates generated by the fractional crystallization from an initial ne-normative liquid or from hy-normative initial compositions (hawaiite or picrobasalt) indicates that for all hydrous liquids, the different phases formed upon differentiation are mostly similar even though the proportions of hydrous versus anhydrous minerals could vary significantly. This suggests that the formation of amphibole-bearing metasomatic veins observed in the lithospheric mantle could be linked to the differentiation of initial liquids ranging from ne-normative to hy-normative in composition. The present study does not resolve the question whether the metasomatism observed in lithospheric mantle is a precursor or a consequence of alkaline magmatism; however, it confirms that the percolation and differentiation of a liquid produced by a low degree of partial melting of a source similar or slightly more enriched than depleted MORB mantle could generate hydrous metasomatic veins interpreted as a potential source for alkaline magmatism by various authors.