U-curve: A branch-and-bound optimization algorithm for U-shaped cost functions on Boolean lattices applied to the feature selection problem

This paper presents the formulation of a combinatorial optimization problem with the following characteristics: (i) the search space is the power set of a finite set structured as a Boolean lattice; (ii) the cost function forms a U-shaped curve when applied to any lattice chain. This formulation applies for feature selection in the context of pattern recognition. The known approaches for this problem are branch-and-bound algorithms and heuristics that explore partially the search space. Branch-and-bound algorithms are equivalent to the full search, while heuristics are not. This paper presents a branch-and-bound algorithm that differs from the others known by exploring the lattice structure and the U-shaped chain curves of the search space. The main contribution of this paper is the architecture of this algorithm that is based on the representation and exploration of the search space by new lattice properties proven here. Several experiments, with well known public data, indicate the superiority of the proposed method to the sequential floating forward selection (SFFS), which is a popular heuristic that gives good results in very short computational time. In all experiments, the proposed method got better or equal results in similar or even smaller computational time. (C) 2009 Elsevier Ltd. All rights reserved.

PAIN IN FIBROMYALGIA AND DISCRIMINATIVE POWER OF THE INSTRUMENTS: VISUAL ANALOG SCALE, DOLORIMETRY AND THE MCGILL PAIN QUESTIONNAIRE

Objective: The aim of this study was to verify the discriminative power of the most widely used pain assessment instruments. Methods: The sample consisted of 279 subjects divided into Fibromyalgia Group (FM- 205 patients with fibromyalgia) and Control Group (CG-74 healthy subjects), mean age 49.29 +/- 10.76 years. Only 9 subjects were male, 6 in FM and 3 in CG. FM were outpatients from the Rheumatology Clinic of the University of Sao Paulo - Hospital das Clinicas (HCFMUSP); the CG included people accompanying patients and hospital staff with similar socio-demographic characteristics. Three instruments were used to assess pain: the McGill Pain Questionnaire (MPQ), the Visual Analog Scale (VAS), and the Dolorimetry, to measure pain threshold on tender points (generating the TP index). In order to assess the discriminative power of the instruments, the measurements obtained were submitted to descriptive analysis and inferential analysis using ROC Curve - sensibility (S), specificity (S I) and area under the curve (AUC) - and Contingence tables with Chi-square Test and odds ratio. Significance level was 0.05. Results: Higher sensibility, specificity and area under the curve was obtained by VAS (80%, 80% and 0.864, respectively), followed by Dolorimetry (S 77%, S177% and AUC 0.851), McGill Sensory (S 72%, S167% and AUC 0.765) and McGill Affective (S 69%, S1 67% and AUC 0.753). Conclusions: VAS presented the higher sensibility, specificity and AUC, showing the greatest discriminative power among the instruments. However, these values are considerably similar to those of Dolorimetry.