An algorithm for computing the generalized interaction index for k-maxitive fuzzy measures

Abstract

Fuzzy measures are used for modeling interactions between a set of elements. Simplified fuzzy measures, as k -maxitive measures, were proposed in the literature for complexity and semantic considerations. In order to analyze the importance of a coalition in the fuzzy measure, the use of indices is required. This work focuses on the generalized interaction index, gindex . Its computation requires many resources in both time and space. Following the efforts to reduce the complexity of fuzzy measure identification, this work presents two algorithms to compute the gindex for k -maxitive measures. The structure of k -maxitive measures makes possible to compute the gindex considering the coalitions at level k and, for each of them, the number of coalitions sharing the same coefficient (called inheritors). The first algorithm deals with the space complexity and the second one also optimizes the runtime by not generating, but only counting, the number of inheritors. While counting the number of descendants is easy, this is not the case for the number of inheritors due to all the inheritors of previous considered coalitions have to be taken into account. The two proposed algorithms are tested with synthetic k -maxitive measures showing that the second algorithm is around 4 times faster than the first one.