Michel Grabisch
Université de Paris I, France
Ivan Kojadinovic
Ecole polytechnique de l'Université de Nantes, France
Patrick Meyer
University of Luxembourg, Luxembourg
Abstract
Kappalab, which stands for “laboratory for capacities”, is a package for the GNU R statistical system. It is a toolbox for capacity (or non-additive measure, fuzzy measure) and integral manipulation on a finite setting which can be used in the framework of decision making or cooperative game theory.
The use of capacities (or fuzzy measures) and non-additive integrals in Multiple Criteria Decision Aiding (MCDA) is not anecdotal anymore. The use of the Choquet integral [CH53] for instance as an aggregation function is now commonly accepted among many MCDA researchers. It appears therefore more and more necessary to have tools which enable an easy manipulation of capacities and related integrals.
The Kappalab[1] package for the GNU R statistical system[2] is an answer to this shortage. It provides a set of high-level routines for the manipulation of capacities and associated non-additive integrals on a finite setting. In particular, it can be useful in MCDA when it comes to the development of new methods or simply to the use of existing capacities identification procedures.
The Kappalab package contains several routines for handling various types of set functions such as games or capacities. It can be used to compute non-additive integrals such as the Choquet integral or the Sugeno integral. The analysis of capacities in terms of decision behavior can be performed through the computation of various numerical indices such as the Shapley value [SH53], the interaction index, the orness degree, etc. The well-known Möbius transform [RO64], as well as other equivalent representations of set functions can also be computed. Furthermore, Kappalab contains four routines for the identification of capacities from (preferential) data : two least squares based approaches, a maximum entropy-like method based on variance minimization and an unsupervised approach grounded on parametric entropies. The three first methods are of particular interest for MCDA.
GNU R is a free software environment for statistical computing and graphics. It compiles and runs on a wide variety of UNIX platforms, Windows and MacOS. It includes a suite of operators for calculations on matrices, a large, coherent, integrated collection of intermediate tools for data analysis and graphical display, and especially a well-developed, simple and effective high-level programming language.
Roughly speaking, one can think of GNU R as a free, Matlab-like software for statistical analysis grounded on an effective high-level language.
Kappalab being a package for GNU R, it follows that before being able to use it, a basic knowledge of the R language is necessary.
Let us consider a simple example showing how Kappalab can be used for capacity manipulation. Note that we hereafter assume that the reader is familiar with the basic concepts arising from the use of non-additive measures and integrals in the framework of multicriteria decision making and cooperative game theory. If not, a good starting point may be [GMS00]. One may also download the numerous articles available from the Kappalab web page.
Let us first define a capacity for a fictitious problem with 3 criteria :
mu<-capacity(c(0,0.07,0.15,0.23,0.28,0.48,0.56,1))
This capacity can then be visualized :
mu
{} 0.00 {12} 0.28
{1} 0.07 {13} 0.48
{2} 0.15 {23} 0.56
{3} 0.23 {123} 1.00
The Shapley value of the capacity can be computed :
Shapley.value(mu)
1 0.2333
2 0.3133
3 0.4533
The Möbius transform of the capacity can be easily obtained :
m <- Mobius(mu)
And then visualized :
m
{} 0.00 {12} 0.06
{1} 0.07 {13} 0.18
{2} 0.15 {23} 0.18
{3} 0.23 {123} 0.13
Finally, given a vector of partial evaluations, one can compute its Choquet integral with respect to the capacity:
x <- c(0.1,0.2,0.8)
Choquet.integral(mu,x)
0.294
Alternatively, the Möbius transform of the capacity can be used:
Choquet.integral(m,x)
0.294
There are more than 40 high-level functions in Kappalab. These can be mainly grouped into two categories : functions for capacity manipulation and functions for capacity identification from (preferential) data. For instance, in the framework of MCDA, a natural way of using Kappalab would be first to use a function from the latter group to identify a capacity and then, functions from the former group to analyze the capacity and the related integral in terms of decision behavior.
We consider the simple example presented in [MR00] to illustrate how Kappalab can be used in the framework of Choquet integral based MCDA.
Four cooks a, b, c, and d are evaluated according to their ability to prepare three dishes : frogs' legs (FL), steak tartare (ST) and stuffed clams (SC). Their evaluations on a [0,20] scale are given in Table 1.
Table SEQ "Table" \*ARABIC 1: Partial evaluations of the four cooks
|
cooks |
FL |
ST |
SC |
|
a |
18 |
15 |
19 |
|
b |
15 |
18 |
19 |
|
c |
15 |
18 |
11 |
|
d |
18 |
15 |
11 |
The decision maker adopts the following reasoning: when a cook is renowned for his stuffed clams, it is preferable that he/she is also better in cooking frogs' legs than steak tartare, which implies that a is preferred to b. However, when a cook badly prepares stuffed clams, it is more important that he/she is better in preparing steak tartare than frogs' legs, which leads to c is preferred to d. Of course, we also immediately have that a is preferred to d and b is preferred to c. Nevertheless these preferences do not contribute to anything since they naturally follow from the monotonicity of the Choquet integral [MA00].
Marichal and Roubens showed that there are no additive model that can lead to this partial ranking [MR00].
Using Kappalab and the above preferential information, it is for instance possible to obtain the “least specific” capacity [KO05] such that the Choquet integral with respect to this capacity preserves the decision maker's preferences.
Define four vectors representing the profiles of the cooks :
a <- c(18,15,19)
b<-c(15,18,19)
c <- c(15,18,11)
d <- c(18,15,11)
Indicate that if an alternative is preferred to another, then their difference in terms of global evaluation should be at least equal to one :
delta.C <- 1
Encode the preferential information “a is preferred to b” and “c is preferred to d” in an R matrix :
Acp <- rbind(c(a,b,delta.C),c(c,d,delta.C))
Use a maximum entropy like method [KO05] to determine the “least specific” capacity compatible with the provided preferential information :
s <-mini.var.capa.ident (3,3,A.Choquet.preorder = Acp)
Display the solution :
mu <- zeta(s$solution)
{} 0.00 {12} 0.67
{1} 0.17 {13} 0.84
{2} 0.50 {23} 0.50
{3} 0.34 {123} 1.00
And compute the global evaluations of the cooks :
Choquet.integral(mu,a)
17.83334
Choquet.integral(mu,b)
16.83334
Choquet.integral(mu,c)
15.16666
Choquet.integral(mu,d)
14.16666
They are in accordance with the decision maker's preferences.This short example illustrates how Kappalab can be used in the framework of Choquet integral based MCDA.
[CH53] G. Choquet. Theory of capacities. Annales de l’Institut Fourier, 5:131-295, 1953.
[MA00] J.-L. Marichal, An axiomatic approach of the discrete Choquet integral as a tool to aggregate interacting criteria, IEEE Transactions on Fuzzy Systems, 8(6):800-807, 2000.
[MR00] J.-L. Marichal, M. Roubens. Determination of weights of interacting criteria from a reference set. European Journal of Operational Research, 124:641-650, 2000.
[SH53] L.S. Shapley. A value for n-person games. In H.W. Kuhn and A.W. Tucker, editors, Contributions to the Theory of Games, Vol. II, volume 28 of Annals of Mathematics Studies, 307 – 317, Princeton University Press, Princeton, NJ, 1953.
[RO64] G-C. Rota, On the foundations of combinatorial theory: Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2, 340—368, 1964.
[GMS00] M. Grabisch and T. Murofushi and M. Sugeno Editors, Fuzzy Measures and Integrals: Theory and Applications, Physica-Verlag, 2000.
[KO05] I. Kojadinovic, Identification of Choquet integral models by means of a minimum variance principle, 3rd International Summer School on Aggregation Operators (AGOP 2005), Lugano, Switzerland, 61-65, 2005.