Information mutuelle ajustée - Adjusted mutual information

En théorie des probabilités et la théorie de l' information , l' information mutuelle ajustée , une variation d' information mutuelle peut être utilisé pour comparer clusterings . Il corrige l'effet de l'accord uniquement dû au hasard entre les regroupements, de la même manière que l' indice de rand ajusté corrige l' indice de Rand . Elle est étroitement liée à la variation de l'information : lorsqu'un ajustement similaire est apporté à l'indice VI, il devient équivalent à l'AMI. La mesure ajustée n'est cependant plus métrique.

Information mutuelle de deux partitions

Étant donné un ensemble S de N éléments , considérons deux partitions de S , à savoir avec R clusters, et avec C clusters. On suppose ici que les partitions sont des clusters dits durs ; les partitions sont deux à deux disjointes : ${\displaystyle S=\{s_{1},s_{2},\ldots s_{N}\}}$${\displaystyle U=\{U_{1},U_{2},\ldots ,U_{R}\}}$${\displaystyle V=\{V_{1},V_{2},\ldots ,V_{C}\}}$

${\displaystyle U_{i}\cap U_{j}=\varnothing =V_{i}\cap V_{j}}$

pour tous et complétez : ${\style d'affichage i\neq j}$

${\displaystyle \cup _{i=1}^{R}U_{i}=\cup _{j=1}^{C}V_{j}=S}$

Les informations mutuelles sur le chevauchement des clusters entre U et V peuvent être résumées sous la forme d'un tableau de contingence R x C , où désigne le nombre d'objets communs aux clusters et . C'est-à-dire, ${\displaystyle M=[n_{ij}]_{j=1\ldots C}^{i=1\ldots R}}$${\style d'affichage n_{ij}}$${\displaystyle U_{i}}$${\style d'affichage V_{j}}$

${\displaystyle n_{ij}=\left|U_{i}\cap V_{j}\right|}$

Supposons qu'un objet soit choisi au hasard dans S ; la probabilité que l'objet tombe dans le cluster est : ${\displaystyle U_{i}}$

${\displaystyle P_{U}(i)={\frac {|U_{i}|}{N}}}$

L' entropie associée au partitionnement U est :

${\displaystyle H(U)=-\sum _{i=1}^{R}P_{U}(i)\log P_{U}(i)}$

H(U) est non négatif et prend la valeur 0 uniquement lorsqu'il n'y a pas d'incertitude déterminant l'appartenance à un cluster d'un objet, c'est -à- dire lorsqu'il n'y a qu'un seul cluster. De même, l'entropie du clustering V peut être calculée comme :

${\displaystyle H(V)=-\sum _{j=1}^{C}P_{V}(j)\log P_{V}(j)}$

où . L' information mutuelle (MI) entre deux partitions : ${\style d'affichage P_{V}(j)={|V_{j}|}/{N}}$

${\displaystyle MI(U,V)=\sum _{i=1}^{R}\sum _{j=1}^{C}P_{UV}(i,j)\log {\frac {P_ {UV}(i,j)}{P_{U}(i)P_{V}(j)}}}$

où désigne la probabilité qu'un point appartienne à la fois à l'amas de U et à l'amas de V : ${\style d'affichage P_{UV}(i,j)}$${\displaystyle U_{i}}$${\style d'affichage V_{j}}$

${\displaystyle P_{UV}(i,j)={\frac {|U_{i}\cap V_{j}|}{N}}}$

MI est une quantité non négative majorée par les entropies H ( U ) et H ( V ). Il quantifie les informations partagées par les deux regroupements et peut donc être utilisé comme mesure de similarité de regroupement .

Ajustement au hasard

Comme l' indice Rand , la valeur de base de l'information mutuelle entre deux clusters aléatoires ne prend pas une valeur constante et tend à être plus grande lorsque les deux partitions ont un plus grand nombre de clusters (avec un nombre fixe d'éléments d'ensemble N ). En adoptant un modèle hypergéométrique d'aléatoire, on peut montrer que l'information mutuelle attendue entre deux regroupements aléatoires est :

${\displaystyle {\begin{aligned}E\{MI(U,V)\}=&\sum _{i=1}^{R}\sum _{j=1}^{C}\sum _{ n_{ij}=(a_{i}+b_{j}-N)^{+}}^{\min(a_{i},b_{j})}{\frac {n_{ij}}{N }}\log \left({\frac {N\cdot n_{ij}}{a_{i}b_{j}}}\right)\times \\&{\frac {a_{i}!b_{j }!(N-a_{i})!(N-b_{j})!}{N!n_{ij}!(a_{i}-n_{ij})!(b_{j}-n_{ij })!(N-a_{i}-b_{j}+n_{ij})!}}\\\end{aligned}}}$

où désigne . Les variables et sont des sommes partielles du tableau de contingence ; C'est, ${\style d'affichage (a_{i}+b_{j}-N)^{+}}$${\displaystyle \max(1,a_{i}+b_{j}-N)}$${\style d'affichage a_{i}}$${\style d'affichage b_{j}}$

${\displaystyle a_{i}=\sum _{j=1}^{C}n_{ij}}$

et

${\displaystyle b_{j}=\sum _{i=1}^{R}n_{ij}}$

La mesure ajustée de l'information mutuelle peut alors être définie comme :

${\style d'affichage AMI(U,V)={\frac {MI(U,V)-E\{MI(U,V)\}}{\max {\{H(U),H(V)\} }-E\{MI(U,V)\}}}}$.

L'AMI prend la valeur 1 lorsque les deux partitions sont identiques et 0 lorsque le MI entre deux partitions est égal à la valeur attendue du seul fait du hasard.

Les références

Liens externes

• Code Matlab pour le calcul de l'information mutuelle ajustée
• Code R pour le calcul rapide et parallèle des informations mutuelles ajustées
• Code Python pour le calcul des informations mutuelles ajustées