Speeding up optimum-path forest training by path-cost propagation

In this paper we present an optimization of the Optimum-Path Forest classifier training procedure, which is based on a theoretical relationship between minimum spanning forest and optimum-path forest for a specific path-cost function. Experiments on public datasets have shown that the proposed approach can obtain similar accuracy to the traditional one but with faster data training. © 2012 ICPR Org Committee.

An iterated sample construction with path relinking method: Application to switch allocation in electrical distribution networks

We present a metaheuristic approach which combines constructive heuristics and local searches based on sampling with path relinking. Its effectiveness is demonstrated by an application to the problem of allocating switches in electrical distribution networks to improve their reliability. Our approach also treats the service restoration problem, which has to be solved as a subproblem, to evaluate the reliability benefit of a given switch allocation proposal. Comparisons with other metaheuristics and with a branch-and-bound procedure evaluate its performance. © 2012 Published by Elsevier Ltd.

ECG arrhythmia classification based on optimum-path forest

An important tool for the heart disease diagnosis is the analysis of electrocardiogram (ECG) signals, since the non-invasive nature and simplicity of the ECG exam. According to the application, ECG data analysis consists of steps such as preprocessing, segmentation, feature extraction and classification aiming to detect cardiac arrhythmias (i.e.; cardiac rhythm abnormalities). Aiming to made a fast and accurate cardiac arrhythmia signal classification process, we apply and analyze a recent and robust supervised graph-based pattern recognition technique, the optimum-path forest (OPF) classifier. To the best of our knowledge, it is the first time that OPF classifier is used to the ECG heartbeat signal classification task. We then compare the performance (in terms of training and testing time, accuracy, specificity, and sensitivity) of the OPF classifier to the ones of other three well-known expert system classifiers, i.e.; support vector machine (SVM), Bayesian and multilayer artificial neural network (MLP), using features extracted from six main approaches considered in literature for ECG arrhythmia analysis. In our experiments, we use the MIT-BIH Arrhythmia Database and the evaluation protocol recommended by The Association for the Advancement of Medical Instrumentation. A discussion on the obtained results shows that OPF classifier presents a robust performance, i.e.; there is no need for parameter setup, as well as a high accuracy at an extremely low computational cost. Moreover, in average, the OPF classifier yielded greater performance than the MLP and SVM classifiers in terms of classification time and accuracy, and to produce quite similar performance to the Bayesian classifier, showing to be a promising technique for ECG signal analysis. © 2012 Elsevier Ltd. All rights reserved.

OPF-MRF: Optimum-path forest and Markov random fields for contextual-based image classification

Some machine learning methods do not exploit contextual information in the process of discovering, describing and recognizing patterns. However, spatial/temporal neighboring samples are likely to have same behavior. Here, we propose an approach which unifies a supervised learning algorithm - namely Optimum-Path Forest - together with a Markov Random Field in order to build a prior model holding a spatial smoothness assumption, which takes into account the contextual information for classification purposes. We show its robustness for brain tissue classification over some images of the well-known dataset IBSR. © 2013 Springer-Verlag.

A wrapper approach for feature selection based on Bat Algorithm and Optimum-Path Forest

Besides optimizing classifier predictive performance and addressing the curse of the dimensionality problem, feature selection techniques support a classification model as simple as possible. In this paper, we present a wrapper feature selection approach based on Bat Algorithm (BA) and Optimum-Path Forest (OPF), in which we model the problem of feature selection as an binary-based optimization technique, guided by BA using the OPF accuracy over a validating set as the fitness function to be maximized. Moreover, we present a methodology to better estimate the quality of the reduced feature set. Experiments conducted over six public datasets demonstrated that the proposed approach provides statistically significant more compact sets and, in some cases, it can indeed improve the classification effectiveness. © 2013 Elsevier Ltd. All rights reserved.

EEG signal classification for epilepsy diagnosis via optimum path forest - A systematic assessment

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

A path- and label-cost propagation approach to speedup the training of the optimum-path forest classifier

In general, pattern recognition techniques require a high computational burden for learning the discriminating functions that are responsible to separate samples from distinct classes. As such, there are several studies that make effort to employ machine learning algorithms in the context of big data classification problems. The research on this area ranges from Graphics Processing Units-based implementations to mathematical optimizations, being the main drawback of the former approaches to be dependent on the graphic video card. Here, we propose an architecture-independent optimization approach for the optimum-path forest (OPF) classifier, that is designed using a theoretical formulation that relates the minimum spanning tree with the minimum spanning forest generated by the OPF over the training dataset. The experiments have shown that the approach proposed can be faster than the traditional one in five public datasets, being also as accurate as the original OPF. (C) 2014 Elsevier B. V. All rights reserved.

A local-global scheme for tracking crack path in three-dimensional solids

This paper aims to contribute to the three-dimensional generalization of numerical prediction of crack propagation through the formulation of finite elements with embedded discontinuities. The analysis of crack propagation in two-dimensional problems yields lines of discontinuity that can be tracked in a relatively simple way through the sequential construction of straight line segments oriented according to the direction of failure within each finite element in the solid. In three-dimensional analysis, the construction of the discontinuity path is more complex because it requires the creation of plane surfaces within each element, which must be continuous between the elements. In the method proposed by Chaves (2003) the crack is determined by solving a problem analogous to the heat conduction problem, established from local failure orientations, based on the stress state of the mechanical problem. To minimize the computational effort, in this paper a new strategy is proposed whereby the analysis for tracking the discontinuity path is restricted to the domain formed by some elements near the crack surface that develops along the loading process. The proposed methodology is validated by performing three-dimensional analyses of basic problems of experimental fractures and comparing their results with those reported in the literature.

Static Video Summarization through Optimum-Path Forest Clustering

This paper introduces the Optimum-Path Forest (OPF) classifier for static video summarization, being its results comparable to the ones obtained by some state-of-the-art video summarization techniques. The experimental section has been conducted using several image descriptors in two public datasets, followed by an analysis of OPF robustness regarding one ad-hoc parameter. Future works are guided to improve OPF effectiveness on each distinct video category.

Optimum-Path Forest Applied for Breast Masses Classification

In Computer-Aided Diagnosis-based schemes in mammography analysis each module is interconnected, which directly affects the system operation as a whole. The identification of mammograms with and without masses is highly needed to reduce the false positive rates regarding the automatic selection of regions of interest for further image segmentation. This study aims to evaluate the performance of three techniques in classifying regions of interest as containing masses or without masses (without clinical findings), as well as the main contribution of this work is to introduce the Optimum-Path Forest (OPF) classifier in this context, which has never been done so far. Thus, we have compared OPF against with two sorts of neural networks in a private dataset composed by 120 images: Radial Basis Function and Multilayer Perceptron (MLP). Texture features have been used for such purpose, and the experiments have demonstrated that MLP networks have been slightly better than OPF, but the former is much faster, which can be a suitable tool for real-time recognition systems.

Toward Satellite-Based Land Cover Classification Through Optimum-Path Forest

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Automatic visual dictionary generation through optimum-path forest clusteringautomatic visual dictionary generation through optimum-path forest clustering

Image categorization by means of bag of visual words has received increasing attention by the image processing and vision communities in the last years. In these approaches, each image is represented by invariant points of interest which are mapped to a Hilbert Space representing a visual dictionary which aims at comprising the most discriminative features in a set of images. Notwithstanding, the main problem of such approaches is to find a compact and representative dictionary. Finding such representative dictionary automatically with no user intervention is an even more difficult task. In this paper, we propose a method to automatically find such dictionary by employing a recent developed graph-based clustering algorithm called Optimum-Path Forest, which does not make any assumption about the visual dictionary's size and is more efficient and effective than the state-of-the-art techniques used for dictionary generation.

A nature-inspired approach to speed up optimum-path forest clustering and its application to intrusion detection in computer networks

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

A simple geometrical path towards hybrid orbitals

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Correlation and path analysis as an indirect selection criterion for sunflower achene productivity

The study was conducted in two different locations in South Brazil, in tillage in the 2009/2010 season on eight sunflower hybrids, aiming to determine the path correlations and coefficients between primary and secondary characters on the main variable of achene productivity. The correlations were similar between environments. The characters of the head diameter and mass of a thousand achenes had a significant influence on sunflower productivity. Based on the magnitude of the direct and indirect effects, we highlighted all primary components on the main variable, beside the good determination coefficient and low residual effect. The secondary component, the number of achenes, despite the significant direct effect on productivity, was indirectly influenced by the primary components, making it an undesirable character for selection.