{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T09:27:22Z","timestamp":1775381242647,"version":"3.50.1"},"reference-count":36,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2020,4,24]],"date-time":"2020-04-24T00:00:00Z","timestamp":1587686400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2013\/07467-1"],"award-info":[{"award-number":["2013\/07467-1"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2015\/01587-0"],"award-info":[{"award-number":["2015\/01587-0"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2016\/25959-7"],"award-info":[{"award-number":["2016\/25959-7"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In Machine Learning, feature selection is an important step in classifier design. It consists of finding a subset of features that is optimum for a given cost function. One possibility to solve feature selection is to organize all possible feature subsets into a Boolean lattice and to exploit the fact that the costs of chains in that lattice describe U-shaped curves. Minimization of such cost function is known as the U-curve problem. Recently, a study proposed U-Curve Search (UCS), an optimal algorithm for that problem, which was successfully used for feature selection. However, despite of the algorithm optimality, the UCS required time in computational assays was exponential on the number of features. Here, we report that such scalability issue arises due to the fact that the U-curve problem is NP-hard. In the sequence, we introduce the Parallel U-Curve Search (PUCS), a new algorithm for the U-curve problem. In PUCS, we present a novel way to partition the search space into smaller Boolean lattices, thus rendering the algorithm highly parallelizable. We also provide computational assays with both synthetic data and Machine Learning datasets, where the PUCS performance was assessed against UCS and other golden standard algorithms in feature selection.<\/jats:p>","DOI":"10.3390\/e22040492","type":"journal-article","created":{"date-parts":[[2020,4,24]],"date-time":"2020-04-24T11:42:14Z","timestamp":1587728534000},"page":"492","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["An Efficient, Parallelized Algorithm for Optimal Conditional Entropy-Based Feature Selection"],"prefix":"10.3390","volume":"22","author":[{"given":"Gustavo","family":"Estrela","sequence":"first","affiliation":[{"name":"Center of Toxins, Immune-Response and Cell Signaling (CeTICS), Laborat\u00f3rio de Ciclo Celular, Instituto Butantan, Butant\u00e3, S\u00e3o Paulo-SP 05503-900, Brazil"},{"name":"Instituto de Matem\u00e1tica e Estat\u00edstica, Universidade de S\u00e3o Paulo, S\u00e3o Paulo-SP 05503-900, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8334-9651","authenticated-orcid":false,"given":"Marco Dimas","family":"Gubitoso","sequence":"additional","affiliation":[{"name":"Instituto de Matem\u00e1tica e Estat\u00edstica, Universidade de S\u00e3o Paulo, S\u00e3o Paulo-SP 05503-900, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlos Eduardo","family":"Ferreira","sequence":"additional","affiliation":[{"name":"Instituto de Matem\u00e1tica e Estat\u00edstica, Universidade de S\u00e3o Paulo, S\u00e3o Paulo-SP 05503-900, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junior","family":"Barrera","sequence":"additional","affiliation":[{"name":"Instituto de Matem\u00e1tica e Estat\u00edstica, Universidade de S\u00e3o Paulo, S\u00e3o Paulo-SP 05503-900, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3754-9115","authenticated-orcid":false,"given":"Marcelo S.","family":"Reis","sequence":"additional","affiliation":[{"name":"Center of Toxins, Immune-Response and Cell Signaling (CeTICS), Laborat\u00f3rio de Ciclo Celular, Instituto Butantan, Butant\u00e3, S\u00e3o Paulo-SP 05503-900, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,4,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1038\/427297a","article-title":"A meeting with Enrico Fermi","volume":"427","author":"Dyson","year":"2004","journal-title":"Nature"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s10044-006-0031-0","article-title":"W-operator window design by minimization of mean conditional entropy","volume":"9","author":"Martins","year":"2006","journal-title":"Pattern Anal. Appl."},{"key":"ref_3","unstructured":"Hall, M.A. (2000). Correlation-Based Feature Selection of Discrete and Numeric Class Machine Learning, University of Waikato. Technical Report."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1226","DOI":"10.1109\/TPAMI.2005.159","article-title":"Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy","volume":"27","author":"Hanchuan","year":"2005","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Kalai, A.T., Mansour, Y., and Verbin, E. (2008, January 17\u201320). On Agnostic Boosting and Parity Learning. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, British Columbia, BC, Canada.","DOI":"10.1145\/1374376.1374466"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1109\/JSTSP.2008.923841","article-title":"Intrinsically Multivariate Predictive Genes","volume":"2","author":"Martins","year":"2008","journal-title":"IEEE J. Sel. Topics Signal Process."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1016\/j.patrec.2009.10.013","article-title":"A rough set approach to feature selection based on ant colony optimization","volume":"31","author":"Chen","year":"2010","journal-title":"Pattern Recognit. Lett."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Jovi\u0107, A., Brki\u0107, K., and Bogunovi\u0107, N. (2015, January 25\u201329). A review of feature selection methods with applications. Proceedings of the 2015 38th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), Opatija, Croatia.","DOI":"10.1109\/MIPRO.2015.7160458"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.compeleceng.2013.11.024","article-title":"A survey on feature selection methods","volume":"40","author":"Chandrashekar","year":"2014","journal-title":"Comput. Electr. Eng."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1109\/TIT.1963.1057810","article-title":"On the effectiveness of receptors in recognition systems","volume":"9","author":"Marill","year":"1963","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1016\/0167-8655(94)90127-9","article-title":"Floating search methods in feature selection","volume":"15","author":"Pudil","year":"1994","journal-title":"Pattern Recognit. Lett."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1100","DOI":"10.1109\/T-C.1971.223410","article-title":"A Direct Method of Nonparametric Measurement Selection","volume":"20","author":"Whitney","year":"1971","journal-title":"IEEE Trans. Comp."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1109\/TEVC.2015.2504420","article-title":"A Survey on Evolutionary Computation Approaches to Feature Selection","volume":"20","author":"Xue","year":"2016","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_14","first-page":"265","article-title":"The CHC adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination","volume":"Volume 1","author":"Eshelman","year":"1991","journal-title":"Foundations of Genetic Algorithms"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2479","DOI":"10.1093\/bioinformatics\/bth261","article-title":"Data mining in bioinformatics using Weka","volume":"20","author":"Frank","year":"2004","journal-title":"Bioinformatics"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/j.patcog.2009.08.018","article-title":"U-curve: A branch-and-bound optimization algorithm for U-shaped cost functions on Boolean lattices applied to the feature selection problem","volume":"43","author":"Ris","year":"2010","journal-title":"Pattern Recognit."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.patcog.2017.08.013","article-title":"A fast Branch-and-Bound algorithm for U-curve feature selection","volume":"73","author":"Reis","year":"2018","journal-title":"Pattern Recognit."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.ins.2018.08.060","article-title":"Optimal Boolean lattice-based algorithms for the U-curve optimization problem","volume":"471","author":"Reis","year":"2019","journal-title":"Inf. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1782","DOI":"10.1137\/0151091","article-title":"Minimal Representations for Translation-Invariant Set Mappings by Mathematical Morphology","volume":"51","author":"Banon","year":"1991","journal-title":"SIAM J. Appl. Math."},{"key":"ref_20","unstructured":"Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (2001). Introduction to Algorithms, MIT Press."},{"key":"ref_21","unstructured":"Dua, D., and Graff, C. (2020, February 20). UCI Machine Learning Repository. Available online: mlr.cs.umass.edu\/ml."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.softx.2017.07.005","article-title":"featsel: A framework for benchmarking of feature selection algorithms and cost functions","volume":"6","author":"Reis","year":"2017","journal-title":"SoftwareX"},{"key":"ref_23","first-page":"46","article-title":"OpenMP: An industry-standard API for shared-memory programming","volume":"1","author":"Dagum","year":"1998","journal-title":"Comput. Sci. Eng."},{"key":"ref_24","first-page":"229","article-title":"Automatic programming of morphological machines by PAC learning","volume":"41","author":"Barrera","year":"2000","journal-title":"Fund. Inform."},{"key":"ref_25","unstructured":"Reis, M.S. (2020, March 05). W-Operator Filter: A Set of Programs to Design and Apply W-Operator Filters on Noisy Binary Images. Available online: github.com\/msreis\/W-operator-filter."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF00994018","article-title":"Support-vector networks","volume":"20","author":"Cortes","year":"1995","journal-title":"Mach. Learn."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Chang, C.C., and Lin, C.J. (2011). LIBSVM: A Library for Support Vector Machines. ACM Trans. Intell. Syst. Technol., 2.","DOI":"10.1145\/1961189.1961199"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"9193","DOI":"10.1073\/pnas.87.23.9193","article-title":"Multisurface method of pattern separation for medical diagnosis applied to breast cytology","volume":"87","author":"Wolberg","year":"1990","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1016\/0031-3203(94)90145-7","article-title":"Comparative analysis of statistical pattern recognition methods in high dimensional settings","volume":"27","author":"Aeberhard","year":"1994","journal-title":"Pattern Recognit."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.bbr.2011.03.031","article-title":"Time-course gait analysis of hemiparkinsonian rats following 6-hydroxydopamine lesion","volume":"222","author":"Hsieh","year":"2011","journal-title":"Behav. Brain Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0031-3203(91)90074-F","article-title":"Optimal discriminant plane for a small number of samples and design method of classifier on the plane","volume":"24","author":"Hong","year":"1991","journal-title":"Pattern Recognit."},{"key":"ref_32","unstructured":"Reis, M.S. (2012). Minimization of Decomposable in U-shaped Curves Functions Defined on Poset Chains\u2013Algorithms and Applications. [Ph.D. Thesis, Instituto de Matem\u00e1tica e Estat\u00edstica, Universidade de S\u00e3o Paulo]. (In Portuguese)."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Liu, C., Yin, F., Wang, D., and Wang, Q. (2011, January 18\u201321). CASIA Online and Offline Chinese Handwriting Databases. Proceedings of the 2011 International Conference on Document Analysis and Recognition, Beijing, China.","DOI":"10.1109\/ICDAR.2011.17"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"3315","DOI":"10.1016\/j.patcog.2013.04.021","article-title":"Mutual information-based method for selecting informative feature sets","volume":"46","author":"Herman","year":"2013","journal-title":"Pattern Recognit."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Nguyen, X.V., Chan, J., Romano, S., and Bailey, J. (2014, January 24\u201327). Effective Global Approaches for Mutual Information Based Feature Selection. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA.","DOI":"10.1145\/2623330.2623611"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","article-title":"Graph-Based Algorithms for Boolean Function Manipulation","volume":"C-35","author":"Bryant","year":"1986","journal-title":"IEEE Trans. Comput."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/4\/492\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T13:23:42Z","timestamp":1760361822000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/4\/492"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,24]]},"references-count":36,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2020,4]]}},"alternative-id":["e22040492"],"URL":"https:\/\/doi.org\/10.3390\/e22040492","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,24]]}}}