Sets and set functions

First we configure the notebook so we can use auto-completion.

%config Completer.use_jedi = False

We can then import the functions of the set_functions module.

from mcda.set_functions import *

Hashable Set

Hashable sets are, as they name suggest, python sets with a defined hash method. This enables them to be used as keys in a dictionary.

You can create a HashableSet as you would create a python set:

HashableSet({"c01", "c02", "c03"})

{'c01', 'c02', 'c03'}

As they are a subclass of python sets, they share most of their methods:

HashableSet({"c01", "c02", "c03"}).difference({"c02"})

{'c01', 'c03'}

Note than whenever a set method will return a python set, you can simply put its result in a HashableSet:

HashableSet({"c01", "c02", "c03"}.difference({"c02"}))

{'c01', 'c03'}

As mentionned before, the main purpose of this class is to enable using sets as keys in a dictionary:

d = {
    HashableSet(): 0,
    HashableSet({"c01", "c02"}): 1,
    HashableSet({"c03"}): 2,
    HashableSet({"c03", "c01"}): 3
}
d

{HashableSet(): 0, {'c01', 'c02'}: 1, {'c03'}: 2, {'c01', 'c03'}: 3}

d[HashableSet()]

0

As the keys are sets, they are unordered:

d[HashableSet({"c02", "c01"})]

1

d[HashableSet({"c01", "c02"})]

1

Set functions

Creation

Sets functions are functions defined on a power set. This means they have a value for each possible set in an ensemble. In this package, those functions are represented as classes. They can be initialized by giving them their values for each set using either a dictionary, or directly the list of values in logical order (the same way you read a binary mask w.r.t its integer representation). We can also provide it with the ensemble as a list, to keep the order of elements in the ensemble.

Say we have the following set function:

criteria = ["c01", "c02", "c03"]
f = SetFunction(
    {
        (): 0,
        ("c01",): 0.1,
        ("c02",): 0.2,
        ("c01", "c02"): 0.2,
        ("c03",): 0.1,
        ("c01", "c03"): 0.25,
        ("c03", "c02"): 0.5,
        tuple(criteria): 1
    }
)
f

<class 'mcda.core.set_functions.SetFunction'>({HashableSet(): 0, HashableSet({'c01'}): 0.1, HashableSet({'c02'}): 0.2, HashableSet({'c01', 'c02'}): 0.2, HashableSet({'c03'}): 0.1, HashableSet({'c01', 'c03'}): 0.25, HashableSet({'c03', 'c02'}): 0.5, HashableSet({'c01', 'c03', 'c02'}): 1})

N.B: the internal representation of the class SetFunction uses a dictionary with HashableSet as keys. But as they are more verbose to write, we recommend using tuples as keys when initializing a SetFunction (though any hashable structure could be used).

N.B: we have wrote the set functions values in the logical order, though it is only mandatory if providing the values as a list.

HashableSet.logical_order(criteria)

[HashableSet(),
 {'c01'},
 {'c02'},
 {'c01', 'c02'},
 {'c03'},
 {'c01', 'c03'},
 {'c02', 'c03'},
 {'c01', 'c02', 'c03'}]

We can check the set function ensemble:

f.ensemble

['c03', 'c02', 'c01']

As the constructor infers the ensemble list as the elements in the dictionary keys in the order he meets them, the ensemble could be in a wrong order.

You can provide the ensemble yourself to fix that:

f2 = SetFunction(
    {
        (): 0,
        ("c01",): 0.1,
        ("c01", "c03"): 0.25,
        ("c02",): 0.2,
        ("c03",): 0.1,
        ("c01", "c02"): 0.2,
        ("c03", "c02"): 0.5,
        tuple(criteria): 1
    },
    criteria
)
f2.ensemble

['c01', 'c02', 'c03']

We can also initialize the same set function by giving it the values as a list:

f2 = SetFunction([0, 0.1, 0.2, 0.2, 0.1, 0.2, 0.5, 1], criteria)
f2

<class 'mcda.core.set_functions.SetFunction'>({HashableSet(): 0, HashableSet({'c01'}): 0.1, HashableSet({'c02'}): 0.2, HashableSet({'c01', 'c02'}): 0.2, HashableSet({'c03'}): 0.1, HashableSet({'c01', 'c03'}): 0.2, HashableSet({'c03', 'c02'}): 0.5, HashableSet({'c01', 'c03', 'c02'}): 1})

If we don’t provide an ensemble and a list of values is used, the ensemble of positive integers will be assumed:

f2 = SetFunction([0, 0.1, 0.2, 0.2, 0.1, 0.2, 0.5, 1])
f2.ensemble

[0, 1, 2]

If you want a clearer representation of a set function, you can look at its values dictionary directly:

f2.values

{HashableSet(): 0,
 {0}: 0.1,
 {1}: 0.2,
 {0, 1}: 0.2,
 {2}: 0.1,
 {0, 2}: 0.2,
 {1, 2}: 0.5,
 {0, 1, 2}: 1}

Call set functions

In order to get the values of a set function for a particular set of elements, we simply need to provide the elements as arguments of the set functions called as a regular python function:

f()  # empty set

0

f("c02")

0.2

f("c01", "c03")

0.25

f(*f.ensemble)  # complete set

1

Usage

We have a lot of functions defined for set functions. We can split them in different categories: * Check type constraints of set functions * Analysis of aggregation represented in set functions * Transformations

But before continuing, let’s define a set function that will be our example for the following. It is a normal capacity:

l = [i / 13 for i in range(14)] + [1, 1]
capacity = [0 for _ in range(len(l))]
for i, index in enumerate(HashableSet.cardinal_range(len(l))):
    capacity[index] = l[i]
capacity = SetFunction(capacity)
capacity

<class 'mcda.core.set_functions.SetFunction'>({HashableSet(): 0.0, HashableSet({0}): 0.07692307692307693, HashableSet({1}): 0.15384615384615385, HashableSet({0, 1}): 0.38461538461538464, HashableSet({2}): 0.23076923076923078, HashableSet({0, 2}): 0.46153846153846156, HashableSet({1, 2}): 0.6153846153846154, HashableSet({0, 1, 2}): 0.8461538461538461, HashableSet({3}): 0.3076923076923077, HashableSet({0, 3}): 0.5384615384615384, HashableSet({1, 3}): 0.6923076923076923, HashableSet({0, 1, 3}): 0.9230769230769231, HashableSet({2, 3}): 0.7692307692307693, HashableSet({0, 2, 3}): 1.0, HashableSet({1, 2, 3}): 1, HashableSet({0, 1, 2, 3}): 1})

N.B: We are instanciating the capacity in the natural order

HashableSet.natural_order([0, 1, 2, 3])

[HashableSet(),
 {0},
 {1},
 {2},
 {3},
 {0, 1},
 {0, 2},
 {0, 3},
 {1, 2},
 {1, 3},
 {2, 3},
 {0, 1, 2},
 {0, 1, 3},
 {0, 2, 3},
 {1, 2, 3},
 {0, 1, 2, 3}]

We can also create quickly the uniform capacity of any size:

u_capacity = SetFunction.uniform_capacity([0, 1, 2, 3])
u_capacity

<class 'mcda.core.set_functions.SetFunction'>({HashableSet(): 0.0, HashableSet({0}): 0.25, HashableSet({1}): 0.25, HashableSet({0, 1}): 0.5, HashableSet({2}): 0.25, HashableSet({0, 2}): 0.5, HashableSet({1, 2}): 0.5, HashableSet({0, 1, 2}): 0.75, HashableSet({3}): 0.25, HashableSet({0, 3}): 0.5, HashableSet({1, 3}): 0.5, HashableSet({0, 1, 3}): 0.75, HashableSet({2, 3}): 0.5, HashableSet({0, 2, 3}): 0.75, HashableSet({1, 2, 3}): 0.75, HashableSet({0, 1, 2, 3}): 1.0})

Check function type constraints

The set functions checks if its constraints are valid upon instanciation. We could also check all the other constraints to have a better understanding of the capacity we defined. Some are implicit, any capacity is a game and obviously a set function, but others are more peculiar.

capacity.is_powerset_function

True

capacity.is_game

True

capacity.is_monotonous

True

capacity.is_additive

False

capacity.is_cardinality_based

False

We can use those to verify the uniform capacity is indeed uniform (additive, cardinality-based, normal):

u_capacity.is_additive

True

u_capacity.is_cardinality_based

True

u_capacity.is_normal

True

Analysis of aggregation

This package implements the following metrics (for regular and möbius representation): * shapley values * interaction indexes

capacity.shapley

0    0.134615
1    0.211538
2    0.288462
3    0.365385
dtype: float64

capacity.interaction_index

	0	1	2	3
0	NaN	-0.025641	-0.025641	-0.025641
1	-0.025641	NaN	-0.064103	-0.064103
2	-0.025641	-0.064103	NaN	-0.064103
3	-0.025641	-0.064103	-0.064103	NaN

Transformations

As of today, the package only implements the Möbius transformation and its inverse.

mobius = capacity.mobius
mobius

<class 'mcda.core.set_functions.Mobius'>({HashableSet(): 0.0, HashableSet({0}): 0.07692307692307693, HashableSet({1}): 0.15384615384615385, HashableSet({0, 1}): 0.15384615384615385, HashableSet({2}): 0.23076923076923078, HashableSet({0, 2}): 0.15384615384615385, HashableSet({1, 2}): 0.23076923076923078, HashableSet({0, 1, 2}): -0.15384615384615385, HashableSet({3}): 0.3076923076923077, HashableSet({0, 3}): 0.1538461538461538, HashableSet({1, 3}): 0.23076923076923073, HashableSet({0, 1, 3}): -0.15384615384615374, HashableSet({2, 3}): 0.23076923076923073, HashableSet({0, 2, 3}): -0.15384615384615374, HashableSet({1, 2, 3}): -0.3846153846153846, HashableSet({0, 1, 2, 3}): -0.0769230769230771})

We can quickly look at the accuracy of both transformation and its inverse:

c = mobius.set_function
for k in capacity._values.keys():
    print(f"{capacity(*k)} -> {c(*k)}")

0.0 -> 0.0
0.07692307692307693 -> 0.07692307692307693
0.15384615384615385 -> 0.15384615384615385
0.38461538461538464 -> 0.38461538461538464
0.23076923076923078 -> 0.23076923076923078
0.46153846153846156 -> 0.46153846153846156
0.6153846153846154 -> 0.6153846153846154
0.8461538461538461 -> 0.8461538461538461
0.3076923076923077 -> 0.3076923076923077
0.5384615384615384 -> 0.5384615384615384
0.6923076923076923 -> 0.6923076923076923
0.9230769230769231 -> 0.9230769230769229
0.7692307692307693 -> 0.7692307692307693
1.0 -> 1.0
1 -> 1.0
1 -> 1.0

We can use this representation to compute the aggregation analysis metrics:

mobius.shapley

0    0.134615
1    0.211538
2    0.288462
3    0.365385
dtype: float64

mobius.interaction_index

	0	1	2	3
0	NaN	-0.025641	-0.025641	-0.025641
1	-0.025641	NaN	-0.064103	-0.064103
2	-0.025641	-0.064103	NaN	-0.064103
3	-0.025641	-0.064103	-0.064103	NaN

This representation also has constraints that define the type of its underlying set function:

mobius.is_monotonous

True

mobius.is_normal

True

mobius.is_k_additive(1)

False

u_capacity.mobius.is_k_additive(1)  # equivalent to additivity

True

u_capacity.mobius.is_k_additive(2)

False

Reference

The example used in this notebook corresponds to the R package kappalab example, taken from its documentation at page 15. Below the R code corresponding:

# load library 'kappalab'
library("kappalab")
# a normalized capacity
mu <- capacity(c(0:13/13,1,1))
# compute mobius transform of capacity
m <- Mobius(mu)
# The Shapley values
Shapley.value(mu)
# The interaction index matrix
interaction.indices(mu)