Learning k-maxitive fuzzy measures from data by mixed integer programming

© 2020 Elsevier B.V. Fuzzy measures model interactions between the inputs in aggregation problems. Their complexity grows exponentially with the dimensionality of the problem, and elicitation of fuzzy measure coefficients either from domain experts or from empirical data poses a significant challenge. The notions of k-additivity and k-maxitivity simplify the fuzzy measures by limiting interactions to subsets of up to k elements. Learning fuzzy measures from data is an important elicitation technique which relies on solving an optimisation problem. A heuristic learning algorithm to identify k-maxitive fuzzy measures from the data on the basis of HLMS (Heuristic Least Mean Squares) was recently presented in Murillo et al. (2017) [11]. We present an alternative formulation of the fitting problem which delivers a globally optimal solution through the solution of a mixed integer programming (MIP) problem. To deal with high computational cost of MIP in moderate to large dimensions, we also propose a simple MIP relaxation technique which involves solving two related linear programming problems. We also provide a linear programming formulation for fitting k-tolerant fuzzy measures. We discuss implementations of the fitting methods and present the results of numerical experiments.