Le problème

On a vu que l'analyse cluster ne pouvait pas distinguer de groupes entre les quatre objets du tableau ci-dessous. Et pourtant, on peut noter que les objets O1, O2, O3 forment un groupe particulier. Chaque prédicat est vérifié exactement soit pour deux de ces objets soit pour aucun.

No	P1	P2	P3	P4	P5	P6	P7	P8
O1	1	1	0	0	1	1	0	0
O2	1	1	1	1	0	0	0	0
O3	0	0	1	1	1	1	0	0
O4	1	0	1	0	1	0	1	0

Watanabe (1969) introduit une mesure de la cohésion d'un groupe basé sur l'entropie. Après la présentation de cette notion, elle sera utilisée pour étudier l'exemple ci-dessus.

Calcul de la cohésion d'un groupe et de l'interdépendance de 2 groupes

Entropie d'un groupe d'objets

Soit un groupe X constitué de n objets (O1, O2, O3, O4 dans le cas de l'exemple), et (P_i)_{i = 1, ..., k} des prédicats sur X, i.e. P_i est est une fonction de X dans B = {0, 1}.

On va chercher dans quelle mesure les prédicats "séparent" les éléments de X.

On considère la famille des vecteurs de Bⁿ = {0, 1}ⁿ, c'est-à-dire l'ensemble des colonnes possibles, et des éléments particuliers de cet ensemble: (P_i(x))_{x dans X}.

Pour b Bⁿ, on note n(X,b), le nombre de prédicats tels que b = (P_i(x)). On note p(X,b) la fréquence relative correspondante. Dans le cas de la représentation matricielle, cela revient à chercher le nombre de colonnes identiques au vecteur b.

L'entropie de X est donnée par:

S(X) = - _b p(X,b) log p(X,b)

On sait que cette somme est d'autant plus grande que les probabilités sont égales. Une petite valeur de S(X) s'observe lorsque certaines valeurs de p(b,X) dominent. Plus la valeur de S(X) est petite et plus le groupe est "cohérent".

Interdépendance

L'interdépendance entre r groupes X₁, ..., X_r disjoints est donnée par:

J(X₁, ..., X_r) = S(X_i) - S(X₁ ... X_r)

La cohérence du groupe X = { x₁, ..., x_r } est donnée par:

C(X) = J_tot = J({x₁}, ..., {x_r}) = S({x_i}) - S(X)

Exemples de calcul d'entropie

Les données utilisées sont celles du tableau ci-dessus:

1) X = { O1} groupe constitué de 1 élément, on a:

p(X,0) = p(X,1) = 1/2; donc S(X) = - 2 (1/2) log (1/2) = 1

Le même résultat est obtenu pour les trois autres groupes à un élément.

2) X = { O1, O2} constitué de 2 éléments, on a:

p(X,(1, 0)) = p(X,(0, 1)) = p(X,(1, 1)) = p(X,(0, 0)) = 1/4

Donc: S(X) = - 4 (1/4) log (1/4) = 2

Le même résultat s'observe pour les 3 groupes à deux éléments.

3) X = {O2, O3, O4}

p(X,(1, 0, 1)) = p(X,(1, 0, 0)) = p(X,(1, 1, 1)) = p(X,(1, 1, 0)) = p(X,(0, 1, 1)) = p(X,(0, 1, 0)) = p(X,(0, 0, 1)) = p(X,(0, 0, 0)) = 1/8

S(X) = - 8 (1/8) log (1/8) = 3

4) X = {O1, O2, O3}

p(X,(1, 1, 0)) = p(X,(0, 1, 1)) = p(X,(0, 1, 0)) = p(X,(0, 0, 0)) = 1/4

S(X) = - 4 (1/4) log (1/4) = 2

Ce groupe présente donc une cohésion plus grande que celui de l'exemple 3.

5) X = {O1, O2, O3, O4}

S(X) = -8 (1/8) log (1/8) = 3

Exemples de calcul d'interdépendance

6) De 2) et 5) on en déduit que pour deux groupes à deux éléments X et Y on a: J(X, Y) = 2 * 2 - 1 = 3

Ces groupes ne sont pas indépendants, ce qui explique les résultats de l'analyse cluster standard.

7) C({O1, O2, O3}) = J(O1, O2, O3) = 3 - 2 = 1

8) J( {O2, O3, O4}, O1) = 3 + 1 - 3 = 1

9) J( {O1, O2, O3}, O4) = 2 + 1 - 3 = 0, ce qui met en évidence deux groupes indépendants.

10) J(O1, O2, O3, O4) = 4 - 3 = 1

Conséquences

Cette méthode permet donc de dépasser l'aspect purement métrique d'une analyse cluster en ajoutant un aspect de cohérence de groupes. Le problème est de trouver un algorithme qui la mette en oeuvre de manière efficace.

Référence

Watanabe, S. (1969). Knowing and Guessing. A quantitative study of inference information. New-York: John Wiley and Sons.