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.

Subclass problem-dependent design for error-correcting output codes

A common way to model multiclass classification problems is by means of Error-Correcting Output Codes (ECOCs). Given a multiclass problem, the ECOC technique designs a code word for each class, where each position of the code identifies the membership of the class for a given binary problem. A classification decision is obtained by assigning the label of the class with the closest code. One of the main requirements of the ECOC design is that the base classifier is capable of splitting each subgroup of classes from each binary problem. However, we cannot guarantee that a linear classifier model convex regions. Furthermore, nonlinear classifiers also fail to manage some type of surfaces. In this paper, we present a novel strategy to model multiclass classification problems using subclass information in the ECOC framework. Complex problems are solved by splitting the original set of classes into subclasses and embedding the binary problems in a problem-dependent ECOC design. Experimental results show that the proposed splitting procedure yields a better performance when the class overlap or the distribution of the training objects conceal the decision boundaries for the base classifier. The results are even more significant when one has a sufficiently large training size.

Equidistribution of Fekete Points on the Sphere

Fekete points are the points that maximize a Vandermonde-type determinant that appears in the polynomial Lagrange interpolation formula. They are well suited points for interpolation formulas and numerical integration. We prove the asymptotic equidistribution of Fekete points in the sphere. The way we proceed is by showing their connection to other arrays of points, the so-called Marcinkiewicz-Zygmund arrays and interpolating arrays, that have been studied recently.

Metabolic syndrome according to different definitions in a rapidly developing country of the African region

Rapport de synthèseLe syndrome métabolique représente un ensemble de facteurs de risque métaboliques souvent présents simultanément et il est associé à un risque accru de développer des maladies cardiovasculaires. La prevalence du syndrome métabolique est à la hausse au niveau mondial comme cela a souvent été documenté, en particulier dans les pays développés. Pourtant, les données concernant le syndrome métabolique dans les pays de la région sub-saharienne restent rares.Au cours des dernières années, plusieurs définitions du syndrome métabolique ont été formulées, dont celle du 'National Cholesterol Education Program Adult Treatment Panel III', celle de 1 Organisation Mondiale de la Santé et celle du 'International Diabetes Federation'. Parmi les controverses au sujet du syndrome métabolique persiste la question de l'utilité de rechercher la présence du syndrome métabolique chez les patients diabétiques, étant donné que la présence d'un diabète en soit suffit pour identifier un individu à haut risque de faire un événement cardiovasculaire.L'objectif de ce travail de thèse a été de déterminer la prévalence du syndrome métabolique selon les trois définitions majeures mentionnées ci-dessus, grâce à une étude de population transversale, réalisée aux Seychelles en 2004 dans un échantillon représentatif de la population âgée de 24-65 ans (n=1255, taux de participation de 80.3%). L'intérêt d'examiner cette question dans ce pays était d'obtenir des informations dans un pays en transition épidémiologique.Les résultats de ce travail montrent que la prévalence du syndrome métabolique aux Seychelles est élevée, quelque soit la définition utilisée. Selon la définition utilisée, cette prévalence était d'environ 25% chez les hommes et variant entre 25 et 35% chez les femmes.Cependant, malgré des prévalences semblables selon ces trois définitions, la concordance entre ces définitions n'était pas bonne, impliquant que ces différentes définitions classifient, à un certain degré, des individus différents comme étant porteurs du syndrome métabolique.En outre, la plupart (environ 80%) des individus diabétiques avaient un syndrome métabolique. Après exclusion des individus diabétiques, la prévalence du syndrome métabolique dans la population est réduite d'environ un tiers, à environ 20-25%.Ces résultats montrent que, d'une part, le fardeau de maladie dû au syndrome métabolique aux Seychelles, un pays en voie de développement, est considérable. Cette observation peut potentiellement s'appliquer à d'autres pays à un stade de développement semblable. Cela renforce le besoin de mettre en oeuvre des stratégies de santé publique afin de cibler les causes de ces désordres métaboliques, tels que le surpoids et la sédentarité. D'un point de vue du diagnostic, les trois définitions du syndrome métabolique semblent classifier un nombre semblable de personnes atteints du syndrome métabolique dans cette population. Par contre, la relativement mauvaise concordance entre ces définitions - certaines personnes identifiés comme porteurs du syndrome métabolique selon une définition ne le sont pas selon une autre - confirme la nécessité de clarifier la signification de ces différentes définitions et/ou éventuellement de développer une définition unifiée et fiable du syndrome métabolique.

Drinking Patterns and Their Predictive Factors in CONTROL: a 12-Month Prospective Study in a Sample of Alcohol-Dependent Patients Initiating Treatment.

Aims: To describe the drinking patterns and their baseline predictive factors during a 12-month period after an initial evaluation for alcohol treatment. Methods CONTROL is a single-center, prospective, observational study evaluating consecutive alcohol-dependent patients. Using a curve clustering methodology based on a polynomial regression mixture model, we identified three clusters of patients with dominant alcohol use patterns described as mostly abstainers, mostly moderate drinkers and mostly heavy drinkers. Multinomial logistic regression analysis was used to identify baseline factors (socio-demographic, alcohol dependence consequences and related factors) predictive of belonging to each drinking cluster. ResultsThe sample included 143 alcohol-dependent adults (63.6% males), mean age 44.6 ± 11.8 years. The clustering method identified 47 (32.9%) mostly abstainers, 56 (39.2%) mostly moderate drinkers and 40 (28.0%) mostly heavy drinkers. Multivariate analyses indicated that mild or severe depression at baseline predicted belonging to the mostly moderate drinkers cluster during follow-up (relative risk ratio (RRR) 2.42, CI [1.02-5.73, P = 0.045] P = 0.045), while living alone (RRR 2.78, CI [1.03-7.50], P = 0.044) and reporting more alcohol-related consequences (RRR 1.03, CI [1.01-1.05], P = 0.004) predicted belonging to the mostly heavy drinkers cluster during follow-up. Conclusion In this sample, the drinking patterns of alcohol-dependent patients were predicted by baseline factors, i.e. depression, living alone or alcohol-related consequences and findings that may inform clinicians about the likely drinking patterns of their alcohol-dependent patient over the year following the initial evaluation for alcohol treatment.

Reproducibility of Fatmax and Fat Oxidation Rates during Exercise in Recreationally Trained Males.

Aerobic exercise training performed at the intensity eliciting maximal fat oxidation (Fatmax) has been shown to improve the metabolic profile of obese patients. However, limited information is available on the reproducibility of Fatmax and related physiological measures. The aim of this study was to assess the intra-individual variability of: a) Fatmax measurements determined using three different data analysis approaches and b) fat and carbohydrate oxidation rates at rest and at each stage of an individualized graded test. Fifteen healthy males [body mass index 23.1±0.6 kg/m2, maximal oxygen consumption ([Formula: see text]) 52.0±2.0 ml/kg/min] completed a maximal test and two identical submaximal incremental tests on ergocycle (30-min rest followed by 5-min stages with increments of 7.5% of the maximal power output). Fat and carbohydrate oxidation rates were determined using indirect calorimetry. Fatmax was determined with three approaches: the sine model (SIN), measured values (MV) and 3rd polynomial curve (P3). Intra-individual coefficients of variation (CVs) and limits of agreement were calculated. CV for Fatmax determined with SIN was 16.4% and tended to be lower than with P3 and MV (18.6% and 20.8%, respectively). Limits of agreement for Fatmax were -2±27% of [Formula: see text] with SIN, -4±32 with P3 and -4±28 with MV. CVs of oxygen uptake, carbon dioxide production and respiratory exchange rate were <10% at rest and <5% during exercise. Conversely, CVs of fat oxidation rates (20% at rest and 24-49% during exercise) and carbohydrate oxidation rates (33.5% at rest, 8.5-12.9% during exercise) were higher. The intra-individual variability of Fatmax and fat oxidation rates was high (CV>15%), regardless of the data analysis approach employed. Further research on the determinants of the variability of Fatmax and fat oxidation rates is required.

How early can we predict Alzheimer's disease using computational anatomy?

Computational anatomy with magnetic resonance imaging (MRI) is well established as a noninvasive biomarker of Alzheimer's disease (AD); however, there is less certainty about its dependency on the staging of AD. We use classical group analyses and automated machine learning classification of standard structural MRI scans to investigate AD diagnostic accuracy from the preclinical phase to clinical dementia. Longitudinal data from the Alzheimer's Disease Neuroimaging Initiative were stratified into 4 groups according to the clinical status-(1) AD patients; (2) mild cognitive impairment (MCI) converters; (3) MCI nonconverters; and (4) healthy controls-and submitted to a support vector machine. The obtained classifier was significantly above the chance level (62%) for detecting AD already 4 years before conversion from MCI. Voxel-based univariate tests confirmed the plausibility of our findings detecting a distributed network of hippocampal-temporoparietal atrophy in AD patients. We also identified a subgroup of control subjects with brain structure and cognitive changes highly similar to those observed in AD. Our results indicate that computational anatomy can detect AD substantially earlier than suggested by current models. The demonstrated differential spatial pattern of atrophy between correctly and incorrectly classified AD patients challenges the assumption of a uniform pathophysiological process underlying clinically identified AD.

Width and serialization of classical planning problems

We introduce a width parameter that bounds the complexity of classical planning problems and domains, along with a simple but effective blind-search procedure that runs in time that is exponential in the problem width. We show that many benchmark domains have a bounded and small width provided thatgoals are restricted to single atoms, and hence that such problems are provably solvable in low polynomial time. We then focus on the practical value of these ideas over the existing benchmarks which feature conjunctive goals. We show that the blind-search procedure can be used for both serializing the goal into subgoals and for solving the resulting problems, resulting in a ‘blind’ planner that competes well with a best-first search planner guided by state-of-the-art heuristics. In addition, ideas like helpful actions and landmarks can be integrated as well, producing a planner with state-of-the-art performance.

Computational problems in perfect phylogeny haplotyping: Typing without calling the allele

A haplotype is an m-long binary vector. The XOR-genotype of two haplotypes is the m-vector of their coordinate-wise XOR. We study the following problem: Given a set of XOR-genotypes, reconstruct their haplotypes so that the set of resulting haplotypes can be mapped onto a perfect phylogeny (PP) tree. The question is motivated by studying population evolution in human genetics and is a variant of the PP haplotyping problem that has received intensive attention recently. Unlike the latter problem, in which the input is '' full '' genotypes, here, we assume less informative input and so may be more economical to obtain experimentally. Building on ideas of Gusfield, we show how to solve the problem in polynomial time by a reduction to the graph realization problem. The actual haplotypes are not uniquely determined by the tree they map onto and the tree itself may or may not be unique. We show that tree uniqueness implies uniquely determined haplotypes, up to inherent degrees of freedom, and give a sufficient condition for the uniqueness. To actually determine the haplotypes given the tree, additional information is necessary. We show that two or three full genotypes suffice to reconstruct all the haplotypes and present a linear algorithm for identifying those genotypes.

Maximum likelihood Linear Programming Data Fusion for Speaker Recognition

Biometric system performance can be improved by means of data fusion. Several kinds of information can be fused in order to obtain a more accurate classification (identification or verification) of an input sample. In this paper we present a method for computing the weights in a weighted sum fusion for score combinations, by means of a likelihood model. The maximum likelihood estimation is set as a linear programming problem. The scores are derived from a GMM classifier working on a different feature extractor. Our experimental results assesed the robustness of the system in front a changes on time (different sessions) and robustness in front a change of microphone. The improvements obtained were significantly better (error bars of two standard deviations) than a uniform weighted sum or a uniform weighted product or the best single classifier. The proposed method scales computationaly with the number of scores to be fussioned as the simplex method for linear programming.

Parametric Approach to Blind Deconvolution of Nonlinear Channels

A parametric procedure for the blind inversion of nonlinear channels is proposed, based on a recent method of blind source separation in nonlinear mixtures. Experiments show that the proposed algorithms perform efficiently, even in the presence of hard distortion. The method, based on the minimization of the output mutual information, needs the knowledge of log-derivative of input distribution (the so-called score function). Each algorithm consists of three adaptive blocks: one devoted to adaptive estimation of the score function, and two other blocks estimating the inverses of the linear and nonlinear parts of the channel, (quasi-)optimally adapted using the estimated score functions. This paper is mainly concerned by the nonlinear part, for which we propose two parametric models, the first based on a polynomial model and the second on a neural network, while [14, 15] proposed non-parametric approaches.

Generation of symmetric periodic orbits by a heteroclinic loop formed by two singular points and their invariant manifolds of dimension 1 and 2 in R3

In this paper we will find a continuous of periodic orbits passing near infinity for a class of polynomial vector fields in R3. We consider polynomial vector fields that are invariant under a symmetry with respect to a plane and that possess a “generalized heteroclinic loop” formed by two singular points e+ and e− at infinity and their invariant manifolds � and . � is an invariant manifold of dimension 1 formed by an orbit going from e− to e+, � is contained in R3 and is transversal to . is an invariant manifold of dimension 2 at infinity. In fact, is the 2–dimensional sphere at infinity in the Poincar´e compactification minus the singular points e+ and e−. The main tool for proving the existence of such periodic orbits is the construction of a Poincar´e map along the generalized heteroclinic loop together with the symmetry with respect to .

Symmetric periodic orbits near a heteroclinic loop in R3 formed by two singular points, a semistable periodic orbit and their invariant manifolds

In this paper we consider C1 vector fields X in R3 having a “generalized heteroclinic loop” L which is topologically homeomorphic to the union of a 2–dimensional sphere S2 and a diameter connecting the north with the south pole. The north pole is an attractor on S2 and a repeller on . The equator of the sphere is a periodic orbit unstable in the north hemisphere and stable in the south one. The full space is topologically homeomorphic to the closed ball having as boundary the sphere S2. We also assume that the flow of X is invariant under a topological straight line symmetry on the equator plane of the ball. For each n ∈ N, by means of a convenient Poincar´e map, we prove the existence of infinitely many symmetric periodic orbits of X near L that gives n turns around L in a period. We also exhibit a class of polynomial vector fields of degree 4 in R3 satisfying this dynamics.

Symmetric periodic orbits near a heteroclinic loop formed by two singular points and their invariant manifolds of dimension 1 and 2

In this paper we consider vector fields in R3 that are invariant under a suitable symmetry and that posses a “generalized heteroclinic loop” L formed by two singular points (e+ and e −) and their invariant manifolds: one of dimension 2 (a sphere minus the points e+ and e −) and one of dimension 1 (the open diameter of the sphere having endpoints e+ and e −). In particular, we analyze the dynamics of the vector field near the heteroclinic loop L by means of a convenient Poincar´e map, and we prove the existence of infinitely many symmetric periodic orbits near L. We also study two families of vector fields satisfying this dynamics. The first one is a class of quadratic polynomial vector fields in R3, and the second one is the charged rhomboidal four body problem.

A(-infinity)-interpolation in the ball

We give a necessary and sufficient condition for a sequence [ak}k in the unit ball of C° to be interpolating for the class A~°° of holomorphic functions with polynomial growth. The condition, which goes along the lines of the ones given by Berenstein and Li for some weighted spaces of entire functions and by Amar for H°° functions in the ball, is given in terms of the derivatives of m > n functions F Fm e A~°° vanishing on {ak)k.