cas particulier de la dimension 2
Lorsque le critère de découpe est binaire, on constitue exactement deux groupes tels que le premier est composé des p éléments possédant une propriété et l'autre des a éléments ne la possédant pas. On note toujours p+a = j et on va montrer une méthode permettant de calculer entropy({p,a}, u) = entropy(u,{p,a}) où u={u_1, u_2, ..., u_n} est un uplet d'entiers non nuls tel que n<=j et sum(k=1, k=n, u_k) = j.
On commence par construire un tableau t de p+1 lignes (a+1 colonnes respectivement) numérotées de 0 à p (0 à a), et on met en évidence les n diagonales correspondant à u dans une numérotation arbitraire dont la seule contraintes est que la suite des distances de deux diagonales consécutives doit reprendre un à un tous les u_k de u : on aura besoin de n+1 diagonales et seules les cases mises en évidence seront calculées dans le tableau.
La case t_{p,a} est symboliquement initialisée à 1 et représente une diagonale. Voici une initialisation possible avec p=7, a=11 et u={7,6,3,1,1}:
.
L'idée est alors d'imaginer un vecteur ((0,0),(11,7)) qu'on doit annuler pour aboutir à ((0,0),(0,0)) et compter de combien de manières cela est possible en ne jouant que sur le point initialement à (11,7) : chaque élément (i_a,i_p) d'une diagonale est calculé en sommant tous les termes possédant un indice ligne >= i_p ET un indice colonne >= i_a de la diagonale précédente. Ainsi la première "vraie" diagonale est toujours composée de 1 ( la première diagonale conventionnelle est un unique élément et est posée égale à 1 ) :
Le résultat est le dernier élément calculé :
entropy({11,7},{7,6,3,1,1}) = entropy({7,6,3,1,1},{11,7}) = t_{0,0} = 87.
On peut vérifier que le résultat ne dépend pas du choix de l'ordre des diagonales dont se sert cette méthode qui pourrait d'ailleurs être généralisée à plus de 2 dimensions mais en perdant bien sûr son caractère représentable.
On commence par construire un tableau t de p+1 lignes (a+1 colonnes respectivement) numérotées de 0 à p (0 à a), et on met en évidence les n diagonales correspondant à u dans une numérotation arbitraire dont la seule contraintes est que la suite des distances de deux diagonales consécutives doit reprendre un à un tous les u_k de u : on aura besoin de n+1 diagonales et seules les cases mises en évidence seront calculées dans le tableau.
La case t_{p,a} est symboliquement initialisée à 1 et représente une diagonale. Voici une initialisation possible avec p=7, a=11 et u={7,6,3,1,1}:
| 7 | 1 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 6 | ||||||||||||
| 5 | ||||||||||||
| 4 | ||||||||||||
| 3 | ||||||||||||
| 2 | ||||||||||||
| 1 | ||||||||||||
| 0 | ||||||||||||
| i_p/i_a | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
L'idée est alors d'imaginer un vecteur ((0,0),(11,7)) qu'on doit annuler pour aboutir à ((0,0),(0,0)) et compter de combien de manières cela est possible en ne jouant que sur le point initialement à (11,7) : chaque élément (i_a,i_p) d'une diagonale est calculé en sommant tous les termes possédant un indice ligne >= i_p ET un indice colonne >= i_a de la diagonale précédente. Ainsi la première "vraie" diagonale est toujours composée de 1 ( la première diagonale conventionnelle est un unique élément et est posée égale à 1 ) :
| 7 | 1 | 1 | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 6 | 1 | |||||||||||
| 5 | 3 | 1 | ||||||||||
| 4 | 4 | 1 | ||||||||||
| 3 | 5 | 1 | ||||||||||
| 2 | 18 | 6 | 1 | |||||||||
| 1 | 40 | 22 | 7 | 1 | ||||||||
| 0 | 87 | 47 | 25 | 7 | 1 | |||||||
| i_p/i_a | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
Le résultat est le dernier élément calculé :
entropy({11,7},{7,6,3,1,1}) = entropy({7,6,3,1,1},{11,7}) = t_{0,0} = 87.
On peut vérifier que le résultat ne dépend pas du choix de l'ordre des diagonales dont se sert cette méthode qui pourrait d'ailleurs être généralisée à plus de 2 dimensions mais en perdant bien sûr son caractère représentable.
Publicité