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 is 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, but neither reduces the complexity of monotonicity constraints. In this paper we explore various approaches to further reduce the complexity of learning fuzzy measures. We introduce the concept of k-interactivity, which reduces both the number of variables and constraints, and also the complexity of each constraint. The learning problem is set as a linear programming problem, and its numerical efficiency is illustrated on numerical experiments. The proposed methods allow efficient learning of fuzzy measures in up to 30 variables, which is significantly higher than using k-additive and k-maxitive fuzzy measures.