Globally Optimal Parsimoniously Lifting a Fuzzy Query Set Over a Taxonomy Tree

P. 779–789.

Frolov D., Mirkin B., Nascimento S., Fenner T.

This paper presents a relatively rare case of an optimization problem in data analysis to admit a globally optimal solution by a recursive algorithm. We are concerned with finding a most specific generalization of a fuzzy set of topics assigned to leaves of domain taxonomy represented by a rooted tree. The idea is to “lift” the set to its “head subject” in the higher ranks of the taxonomy tree. The head subject is supposed to “tightly” cover the query set, possibly bringing in some errors, either “gaps” or “offshoots” or both. Our method globally minimizes a penalty function combining the numbers of head subjects and gaps and offshoots, differently weighted. We apply this to a collection of 17645 research papers on Data Science published in 17 Springer journals for the past 20 years. We extract a taxonomy of Data Science (TDS) from the international Association for Computing Machinery Computing Classification System 2012. We find fuzzy clusters of leaf topics over the text collection, optimally lift them to head subjects in TDS, and comment on the tendencies of current research following from the lifting results.

Keywords: additive fuzzy clustering, parsimony, annotated suffix tree, hierarchical taxonomy, Generalization, Spectral clustering

Publication based on the results of: Разработка методов структуризации и концептуализации текстовых данных на основе таксономии предметной области (2019)

In book

Optimization of Complex Systems: Theory, Models, Algorithms and Applications

Switzerland: Springer Publishing Company, 2020.