Abstract: Clustering algorithms are a useful tool to explore data structures and have been employed in many disciplines. The focus of this paper is the partitioning clustering problem with a special interest in two recent approaches: kernel and spectral methods. The aim of this paper is to present a survey of kernel and spectral clustering methods, two approaches able to produce nonlinear separating hypersurfaces between clusters. The presented kernel clustering methods are the kernel version of many classical clustering algorithms, e.g., K-means, SOM and neural gas. Spectral clustering arise from concepts in spectral graph theory and the clustering problem is configured as a graph cut problem where an appropriate objective function has to be optimized. An explicit proof of the fact that these two paradigms have the same objective is reported since it has been proven that these two seemingly different approaches have the same mathematical foundation. Besides, fuzzy kernel clustering methods are presented as extensions of kernel K-means clustering algorithm. (C) 2007 Pattem Recognition Society. Published by Elsevier Ltd. All rights reserved.
Abstract: The problem of clustering is often addressed with techniques based on a Voronoi partition of the data space. Vector quantization is based on a similar principle, but it is a different technical problem. We analyze some approaches to the synthesis of a vector quantization codebook, and their similarities with corresponding clustering algorithms. We outline the role of fuzzy concepts in these algorithms, both in data representation and in training. Then we propose an alternative way to use fuzzy concepts as a modeling tool for physical vector quantization systems, Neural Gas with a fuzzy rank function. We apply this method to the problem of quality enhancement in lossy compression and reconstruction of images with vector quantization. (c) 2006 Elsevier B.V. All rights reserved.
Abstract: Linear fuzzy clustering is a useful tool for knowledge discoverv in databases (KDD), and several modifications have been proposed in order to analyze real world data. This paper proposes a new approach for estimating local linear models, in which linear fuzzy clustering is performed by selecting variables that are useful for extracting correlation structure in each cluster. The new clustering model uses two types of memberships. One is the conventional membership that represents the degree of membership of each sample in each cluster. The other is the additional parameter that represents the relative responsibility of each variable for estimation of local linear models. The additional membership takes large values when the variable has close relationship with local principal components, and is calculated by using the graded possibilistic approach. Numerical experiments demonstrate that the proposed method is useful for identifying local linear model taking typicality of each variable into account.
Abstract: The pattern recognition problem in Ring Imaging CHerenkov (RICH) Counters concerns the identification of art unknown number of rings whose centers and radii are assumed to be unknown. In this paper we present art algorithm based oil the possibilistic approach to Clustering that automatically finds both the number of rings and their position without any a priori knowledge. The algorithm has been tested oil realistic Monte Carlo LHCb simulated events and it has been shown very powerful in detecting complex images full of rings. The tracking-independent algorithm Could be usefully employed after a track based approach to identify remaining trackless rings. (C) 2005 Elsevier Inc. All rights reserved.
Abstract: Vector quantization and clustering are two different problems for which similar techniques are used. We analyze some approaches to the synthesis of a vector quantization codebook, and their similarities with corresponding clustering algorithms. We outline the role of fuzzy concepts in the performance of these algorithms, and propose an alternative way to use fuzzy concepts as a modeling tool for physical vector quantization systems, Neural Gas with a fuzzy rank function.
Abstract: In the fuzzy clustering literature, two main types of membership are usually considered: A relative type, termed probabilistic, and an absolute or possibilistic type, indicating the strength of the attribution to any cluster independent from the-rest. There are works addressing the unification of the two schemes. Here, we focus on providing a model for the transition from one schema to the other, to exploit the dual information given by the two schemes, and to add flexibility for the interpretation of results. We apply an uncertainty model based on interval values to memberships in the clustering framework, obtaining a framework that we term graded possibility. We outline a basic example of graded possibilistic clustering algorithm and add some practical remarks about its implementation. The experimental demonstrations presented highlight the different properties attainable through appropriate implementation of a suitable graded possibilistic model. An interesting application is found in automated segmentation of diagnostic medical images, where the model provides an interactive visualization tool for this task.
Abstract: Clustering algorithms are routinely used in biomedical disciplines, and are a basic tool in bioinformatics. Depending on the task at hand, there are two most popular options, the central partitional techniques and the agglomerative hierarchical clustering techniques and their derivatives. These methods are well studied and well established. However, both categories have some drawbacks related to data dimensionality (for partitional algorithms) and to the bottom-up structure (for hierarchical agglomerative algorithms). To overcome these limitations, motivated by the problem of gene expression analysis with DNA microarrays, we present a hierarchical clustering algorithm based on a completely different principle, which is the analysis of shared farthest neighbors. We present a framework for clustering using ranks and indexes, and introduce the shared farthest neighbors (SFN) clustering criterion. We illustrate the properties of the method and present experimental results on different data sets, using the strategy of evaluating data clustering by extrinsic knowledge given by class labels. (c) 2006 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.
Abstract: Clustering methods provide an useful tool to tackle the problem of exploring large-dimensional data. However many common approaches suffer from being applied in high-dimensional spaces. Building on a dissimilarity-based representation of data, we propose a dimensionality reduction technique which preserves the clustering structure of the data. The technique is designed for cases in which data dimensionality is large compared to the number of available observations. In these cases, we represent data in the space of soft D-ranks, by applying the concept of fuzzy ranking. A clustering procedure is then applied. Experimental results show that the method is able to retain the necessary information, while considerably reducing dimensionality.
Abstract: When applied to genomic data, many popular unsupervised explorative data analysis tools based on clustering algorithms often fail due to their small cardinality and high dimensionality. In this paper we propose a wrapper method for gene selection based on simulated annealing and unsupervised clustering. The proposed approach, even if computationally intensive, permits to select the most relevant features (genes), and to rank their relevance, allowing to improve the results of clustering algorithms.
Abstract: The important research objective of identifying genes with similar behavior with respect to different conditions has recently been tackled with biclustering techniques. In this paper we introduce a new approach to the biclustering problem using the Possibilistic Clustering paradigm. The proposed Possibilistic Biclustering algorithm finds one bicluster at a time, assigning a membership to the bicluster for each gene and for each condition. The biclustering problem, in which one would maximize the size of the bicluster and minimizing the residual, is faced as the optimization of a proper functional. We applied the algorithm to the Yeast database, obtaining fast convergence and good quality solutions. We discuss the effects of parameter tuning and the sensitivity of the method to parameter values. Comparisons with other methods from the literature are also presented.
Abstract: The human leukocyte antigen (HLA) region is a part of genome which spans over 4 Mbases of DNA. The HLA system is strongly connected to immunological response and its compatibility between tissues is critical in transplantation. We have developed an application of oligonucleotide microarrays to HLA typing. In this paper, we present a method based on a fuzzy system which interactively supports the user in analyzing the hybridization results, speeding-up the decision process moving from raw array data obtained from the scanner to their interpretation (genotyping). The two-level procedure starts with evaluation of spot activity, then it estimates probe hybridization levels from activity levels. The method is designed for being readily usable by the biologist, by adopting fuzzy linguistic variables which are familiar to the user and by featuring a standard and complete graphical interface. (c) 2004 Elsevier B.V. All rights reserved.
Abstract: The lack of large, semantically annotated corpora is one of the main drawbacks of Word Sense Disambiguation systems. Unsupervised systems do not need such corpora and rely on the information of the WordNet ontology. In order to improve their performance, the use of other lexical resources need to be investigated. This paper describes the effort to integrate the Conceptual Density approach with sources of lexical information different from WordNet, particularly the WordNet Domains and the Cambridge Advanced Learner's Dictionary. Unfortunately, enriching WordNet glosses with samples of another lexical resource did not provide the expected results.
Abstract: This paper explores a fully automatic knowledge-based method which performs the noun sense disambiguation relying only on the WordNet ontology. The basis of the method is the idea of conceptual density, that is, the correlation between the sense of a given word and its context. A new formula for calculating the conceptual density was proposed and was evaluated on the SemCor corpus.
Abstract: The graded possibilistic clustering paradigm includes as the two extreme cases the "probabilistic" assumption and the "possibilistic" assumption adopted by many clustering algorithms. We propose an implementation of a graded possibilistic clustering algorithm based on an interval equality constraint enforcing both the normality condition and the required graded possibilistic condition. Experimental results highlight the different properties attainable through appropriate implementation of a suitable graded possibilistic model.
Abstract: In this paper we propose a flexible method for analyzing the relevance of input variables in high dimensional problems with respect to a given dichotomic classification problem. Both linear and non-linear cases are considered. In the linear case, the application of derivative-based saliency yields a commonly adopted ranking criterion. In the non-linear case, the method is extended by introducing a resampling technique and by clustering the obtained results for stability of the estimate. The method was preliminarly validated on the data published by T.R. Golub et al. on a study, at the molecular level, of two kinds of leukemia: Acute Myeloid Leukemia and Acute Lymphoblastic Leukemia (Science 5439-286, 531 537, 1999). Our technique indicates that, among the top 20 genes found by the final cluster analysis, 8 of the 50 genes listed in the original work feature a stronger discriminating power.
Abstract: Error Correcting Output Coding (ECOC) methods for multiclass classification present several open problems ranging from the trade-off between their error recovering capabilities and the learnability of the induced dichotomies to the selection of proper base learners and to the design of well-separated codes for a given multiclass problem. We experimentally analyse some of the main factors affecting the effectiveness of ECOC methods. We show that the architecture of ECOC learning machines influences the accuracy of the ECOC classifier, highlighting that ensembles of parallel and independent dichotomic Multi-Layer Perceptrons are well-suited to implement ECOC methods. We quantitatively evaluate the dependence among codeword bit errors using mutual information based measures, experimentally showing that a low dependence enhances the generalisation capabilities of ECOC. Moreover we show that the proper selection of the base learner and the decoding function of the reconstruction stage significantly affects the performance of the ECOC ensemble. The analysis of the relationships between the error recovering power, the accuracy of the base learners, and the dependence among codeword bits show that all these factors concur to the effectiveness of ECOC methods in a not straightforward way, very likely dependent on the distribution and complexity of the data.
Abstract: The paper addresses the issue of assessing the importance of input variables with respect to a given dichotomic classification problem. Both linear and non-linear cases are considered. In the linear case, the application of derivative-based saliency yields a commonly adopted ranking criterion. In the non-linear case, the method is extended by introducing a resampling technique and by clustering the obtained results for stability of the estimate. (C) 2003 Elsevier B.V. All rights reserved.
Abstract: In previous work, we have proposed a constructive methodology for temporal data learning supported by results and prescriptions related to the embedding theorem, and using the singular spectrum analysis both in order to reduce the effects of the possible discontinuity of the signal and to implement an efficient ensemble method. In this paper we present new results concerning the application of this approach to the forecasting of the individual rain-fall intensities series collected by 135 stations distributed in the Tiber basin. The average RMS error of the obtained forecasting is less than 3 mm of rain. (C) 2003 Elsevier Science Ltd. All rights reserved.
Abstract: In previous work, we have proposed a constructive methodology for temporal data learning supported by results and prescriptions related to the embedding theorem, and using the singular spectrum analysis both in order to reduce the effects of the possible discontinuity of the signal and to implement an efficient ensemble method. In this paper we present new results concerning the application of this approach to the forecasting of the individual rain-fall intensities series collected by 135 stations distributed in the Tiber basin. The average RMS error of the obtained forecasting is less than 3mm of rain.
Abstract: We consider a popular approach to multicategory classification tasks: a two-stage system based on a first (global) classifier with rejection followed by a (local) nearest-neighbor classifier. Patterns which are not rejected by the first classifier are classified according to its output. Rejected patterns are passed to the nearest-neighbor classifier together with the top-it ranking classes returned by the first classifier. The nearest-neighbor classifier, looking at patterns in the top-h classes, classifies the rejected pattern. An editing strategy for the nearest-neighbor reference database, controlled by the first classifier, is also considered. We analyze this system, showing that even if the first level and nearest-neighbor classifiers are not optimal in a Bayes sense, the system as a whole may be optimal. Moreover, we formally relate the response time of the system to the rejection rate of the first classifier and to the other system parameters. The error-response time trade-off is also discussed. Finally, we experimentally study two instances of the system applied to the recognition of handwritten digits. In one system, the first classifier is a fuzzy basis functions network, while in the second system it is a feed-forward neural network. Classification results as well as response times for different settings of the system parameters are reported for both systems.
Abstract: Ensembles of learning machines constitute one of the main current directions in machine learning research, and have been applied to a wide range of real problems. Despite of the absence of an unified theory on ensembles, there are many theoretical reasons for combining multiple learners, and an empirical evidence of the effectiveness of this approach. In this paper we present a brief overview of ensemble methods, explaining the main reasons why they are able to outperform any single classifier within the ensemble, and proposing a taxonomy based on the main ways base classifiers can be generated or combined together.
Abstract: NEURObjects is a set of C++ library classes for neural network development, exploiting the potentialities of object-oriented design and programming. The main goal of the library consists in supporting experimental research in neural networks and fast prototyping of inductive machine learning applications. We present NEURObjects design issues, its main functionalities, and programming examples, showing how to map neural network concepts into the design of library classes. (C) 2002 Elsevier Science B.V. All rights reserved.
Abstract: Boosting methods are known to improve generalization performances of learning algorithms reducing both bias and variance or enlarging the margin of the resulting multi-classifier system. In this contribution we applied Adaboost to the discrimination of different types of coffee using data produced with an Electronic Nose. Two groups of coffees (blends and monovarieties), consisting of seven classes each, have been analyzed. The boosted ensemble of Multi-Layer Perceptrons was able to halve the classification error for the blends data and to diminish it from 21% to 18% for the more difficult monovarieties data set.
Abstract: The classification of 242 measurements in 14 classes is attempted using two different classification approaches. Measurements have been performed with a commercial electronic nose (EN) comprising 11 chemical sensors on extra-virgin olive oils of 14 different geographical provenances. As we deal with a relatively small data set and a big number of classes, the classification task is quite demanding. We first tackled the global classification task using a single multilayer perceptron (MLP), which gave a misclassification rate of 25%. In order to improve the performance, we studied two different approaches based on ensembles of learning machines, which decompose the classification in subtasks. In the first approach, a classification tree was constructed using a priori knowledge (geographical origin) for the formation of sensible superclasses (union of single classes). At each classification node we both used MLPs and SIMCA (soft independent modeling of class analogy). The second approach applies a learning machine called parallel nonlinear dichotomizers (PND) that is based on the decomposition of a K-class classification problem in a set of two-class tasks. A binary codeword is assigned to each class and each bit is learned by a dichotomizer (implemented by a dedicated MLP). In the reconstruction stage, a pattern is assigned to the class whose codeword is most similar (e.g. in L(1)norm) to the output of the set of dichotomizers. We achieved the best results (misclassification error rate of about 10%) using a decomposition based on error correcting output codes (ECOC). (C) 2001 Elsevier Science B.V. All rights reserved.
Abstract: The problem of quantifying the concentrations of CO and NO2 present in a mixture starting from the electrical response of a sensors array is addressed. A comparison between a traditional approach based on the steady state conductance and one using a time delay neural network is drawn. (C) 2000 Elsevier Science S.A. All rights reserved.
Abstract: In the framework of decomposition methods for multiclass classification problems, error correcting output codes (ECOC) can be fruitfully used as codewords for coding classes in order to enhance the generalization capability of learning machines. The effectiveness of error correcting output codes depends mainly on the independence of code-word bits and on the accuracy by which each dichotomy is learned. Separated and non-linear dichotomizers can improve the independence among computed codeword bits, thus fully exploiting the error recovering capabilities of ECOC. In the experimentation presented in this paper we compare ECOC decomposition methods implemented through monolithic multi-layer perceptrons and sets of linear and non-linear independent dichotomizers. The most effectiveness of ECOC decomposition scheme is obtained by Parallel Non-linear Dichotomizers (PND), a learning machine based on decomposition of polychotomies into dichotomics, using non linear independent dichotomizers.
Abstract: The correlation between the responses of five semiconductor thin films sensors to GO-NO, mixtures is exploited to detect a possible malfunctioning of one of the sensors during operation. To this end, at every time instant, the current flowing in each single sensor is estimated as a function of the current flowing in the remaining ones. With multiple linear regression, we obtain, in the case of the worst sensor, a regression coefficient of 0.89. The estimation is then accomplished using the regression ability of five artificial neural networks (ANN), one for each sensor, obtaining at worst a mean estimation error on the test set of 6 X 10(-3) mu A(2). the signal being of the order of the microampere (mu A). In the case of a simulated transient malfunctioning, we show how it is possible to detect on-line which is the sensor that is not working properly. Further, after a fault has been detected, the estimation replaces the damaged sensor response. In this way, the concentration prediction - performed by other ANNs that need the responses of all the sensors - can proceed until the damaged sensor has been replaced. (C) 2000 Elsevier Science S.A. All rights reserved.
Abstract: Three different clustering algorithms have been implemented to reconstruct the response of a segmented BGO calorimeter to electromagnetic showers and hadrons. The ability of each algorithm to identify the number of interacting particles and to attribute to each particle the appropriate energy, has been assessed by comparison to various reactions simulated with the GEANT code. General considerations on the calorimeter response are made. A few significant reaction channels are discussed in detail as regards cluster identification and background reduction with each clustering technique. (C) 1999 Elsevier Science B.V. All rights reserved.
Abstract: In medical imaging uncertainty is widely present in data, because of the noise in acquisition and of the partial volume effects originating from the low resolution of sensors. In particular, borders between tissues are not exactly defined and memberships in the boundary regions are intrinsically fuzzy. Therefore, computer assisted unsupervised fuzzy clustering methods turn out to be particularly suitable for handling a decision making process concerning segmentation of multimodal medical images. By using the possibilistic c-means algorithm as a refinement of a neural network based clustering algorithm named capture effect neural network, we developed the possibilistic neuro fuzzy c-means algorithm (PNFCM). In this paper the PNFCM has been applied to two different multimodal data sets and the results have been compared to those obtained by using the classical fuzzy c-means algorithm. Furthermore, a discussion is presented about the role of fuzzy clustering as a support to diagnosis in medical imaging.
Abstract: In medical imaging uncertainty is widely present in data, because of the noise in acquisition and of the partial volume effects originating from the low resolution of sensors. In particular, borders between tissues are not exactly defined and memberships in the boundary regions are intrinsically fuzzy. Therefore, computer assisted unsupervised fuzzy clustering methods turn out to be particularly suitable for handling a decision making process concerning segmentation of multimodal medical images. By using the possibilistic c-means algorithm as a refinement of a neural network based clustering algorithm named capture effect neural network, we developed the possibilistic neuro fuzzy c-means algorithm (PNFCM). In this paper the PNFCM has been applied to two different multimodal data sets and the results have been compared to those obtained by using the classical fuzzy c-means algorithm. Furthermore, a discussion is presented about the role of fuzzy clustering as a support to diagnosis in medical imaging. (C) 1999 Elsevier Science BV. All rights reserved.
Abstract: To accomplish analyses on the properties of neuronal populations it is mandatory that each unit activity is identified within the overall noise background and the other unit signals merged in the same trace. The problem, addressed as a clustering one, is particularly difficult as no assumption can be made on the prior data distribution. We propose an algorithm that achieves this goal by a two-phase agglomerative hierarchical clustering. First, an inflated estimation (overly) of the number of clusters is cast down and, by a maximum entropy principle (MEP) approach, is made to collapse towards an arrangement near natural ones. In the second step consecutive partitions are created by merging, two at time previously aggregated partitions, according to similarity criteria, in order to reveal a cluster solution. The procedure makes no assumptions about data distributions and guarantees high robustness with respect to noise. An application on real data out of multiple unit recordings from spinal cord neurons of mixed gas-anaesthetized rats is presented.
Abstract: To accomplish analyses on the properties of neuronal populations it is mandatory that each unit activity is identified within the overall noise background and the other unit signals merged in the same trace. The problem, addressed as a clustering one, is particularly difficult as no assumption can be made on the prior data distribution. We propose an algorithm that achieves this goal by a two-phase agglomerative hierarchical clustering. First, an inflated estimation (overly) of the number of clusters is cast down and, by a maximum entropy principle (MEP) approach, is made to collapse towards an arrangement near natural ones. In the second step consecutive partitions are created by merging, two at time previously aggregated partitions, according to similarity criteria, in order to reveal a cluster solution. The procedure makes no assumptions about data distributions and guarantees high robustness with respect to noise. An application on real data out of multiple unit recordings from spinal cord neurons of mixed gas-anaesthetized rats is presented. (C) 1998 Elsevier Science B.V. All rights reserved.
Abstract: The structure identification of adaptive fuzzy logic systems, realized as networks of Fuzzy Basis Functions (FBF's) and trained on numerical data, is studied for a handwritten character recognition problem. An FBF network with fewer rules than classes to be discriminated is unable to recognize some classes, while, when the number of rules is increased up to the number of classes to be discriminated, a sharp increase in the performance is observed. Experimental results point out that the behavior of the FBF network is closer to that of a competitive model showing a strong specialization of the fuzzy rules.
Abstract: In this paper we show which elements have to be extracted from a chaotic time series in order to define the architecture of a forecaster. The forecaster chosen here is a Neuro-Fuzzy System (NFS). This NFS is trained by a supervised gradient descent algorithm. The NFS is made of a layer of singleton inputs, a hidden layer of Gaussian membership functions and one output unit. Product is used for rule inference and sum for rule composition. Output is given by a height defuzzifier. Test cases based on Mackey-Glass time series are presented.
Abstract: The need for quantitative information is becoming increasingly important in the clinical field. In this paper we present an interactive X11 based system, devoted to segmentation of multivariate medical images, including an unsupervised neural network approach to clustering. The following steps are considered in the analysis sequence: feature extraction, reduction of dimensionality, unsupervised data clustering, voxel classification, interactive postprocessing refinement. The environment turns out to be extremely interactive, thus making the user able to display and modify data during processing, to set parameters, to choose different methods and different tools for each step, and to define online the whole analysis sequence. Copyright (C) 1996 Elsevier Science Ltd.
Abstract: The need for quantitative information is becoming increasingly important in the clinical field. In this paper we present an interactive X11 based system, devoted to segmentation of multivariate medical images, including an unsupervised neural network approach to clustering. The following steps are considered in the analysis sequence: feature extraction, reduction of dimensionality, unsupervised data clustering, voxel classification, interactive post-processing refinement. The environment turns out to be extremely interactive, thus making the user able to display and modify data during processing, to set parameters, to choose different methods and different tools for each step, and to define online the whole analysis sequence.
Abstract: The perspective reversals elicited by a set of drawings based on the Mach truncated pyramid are examined. We obtained each pattern of the set from the previous one by adding to it some graphic cues, which were easily integrated into one of the two competing interpretations, thus reducing step by step the ambiguity of the basic pattern. The phenomenological model, proposed to link the mean times of both alternative interpretations with their complexities, is in close agreement with our experimental data. Furthermore, different aspects of such data are well described by the model equations: The measure of the prevalence of the supported interpretation is well correlated with the difference in complexity between the two alternative interpretations; the two different trends of the mean time of the unfavored interpretation, found in the data obtained from different observers as a function of the various patterns of the set, are well fitted by the model without the need for any specific additional hypothesis.
