En la teoría de la probabilidad y la teoría de la información , la variación de la información o la distancia de la información compartida es una medida de la distancia entre dos agrupaciones ( particiones de elementos ). Está estrechamente relacionado con la información mutua ; de hecho, es una expresión lineal simple que involucra la información mutua. Sin embargo, a diferencia de la información mutua, la variación de la información es una métrica verdadera , ya que obedece a la desigualdad del triángulo . [1] [2] [3]
Definición
Supongamos que tenemos dos particiones y de un conjunto en subconjuntos disjuntos , a saber y .
Dejar:
- y
Entonces la variación de información entre las dos particiones es:
- .
Esto es equivalente a la distancia de información compartida entre las variables aleatorias i y j con respecto a la medida de probabilidad uniforme en definido por por .
Contenido de información explícita
Podemos reescribir esta definición en términos que resalten explícitamente el contenido de información de esta métrica.
El conjunto de todas las particiones de un conjunto forman una celosía compacta donde el orden parcial induce dos operaciones, el encuentro y la unión , donde el máximo es la partición con un solo bloque, es decir, todos los elementos agrupados, y el mínimo es , la partición que consta de todos los elementos como singletons. El encuentro de dos particiones y es fácil de entender ya que la partición formada por todas las intersecciones de pares de un bloque de, , de y uno, , de . Luego se sigue que y .
Definamos la entropía de una partición. como
- ,
dónde . Claramente, y . La entropía de una partición es una función monótona en el entramado de particiones en el sentido de que.
Entonces la distancia VI entre y es dado por
- .
La diferencia es una pseudo-métrica como no implica necesariamente que . De la definición de, es .
Si en el diagrama de Hasse dibujamos un borde de cada partición al máximo y asignarle un peso igual a la distancia VI entre la partición dada y , podemos interpretar la distancia VI como básicamente un promedio de diferencias de pesos de borde al máximo
- .
Para como se definió anteriormente, sostiene que la información conjunta de dos particiones coincide con la entropía de la reunión
y tambien tenemos eso coincide con la entropía condicional del encuentro (intersección) relativo a .
Identidades
La variación de la información satisface
- ,
dónde es la entropía de, y es información mutua entre y con respecto a la medida de probabilidad uniforme en . Esto se puede reescribir como
- ,
dónde es la entropía conjunta de y , o
- ,
dónde y son las respectivas entropías condicionales .
La variación de la información también puede estar acotada, ya sea en función del número de elementos:
- ,
O con respecto a un número máximo de clústeres, :
Referencias
- ^ P. Arabie, SA Boorman, SA, "Escalado multidimensional de medidas de distancia entre particiones", Journal of Mathematical Psychology (1973), vol. 10, 2, págs. 148–203, doi: 10.1016 / 0022-2496 (73) 90012-6
- ^ WH Zurek, Nature, vol 341, p119 (1989); WH Zurek, Physics Review A, vol 40, p4731 (1989)
- ^ Marina Meila, "Comparación de agrupaciones por la variación de la información", Teoría del aprendizaje y máquinas de kernel (2003), vol. 2777, págs. 173–187, doi : 10.1007 / 978-3-540-45167-9_14 , Lecture Notes in Computer Science, ISBN 978-3-540-40720-1
Otras lecturas
- Arabie, P .; Boorman, SA (1973). "Escalado multidimensional de medidas de distancia entre particiones". Revista de Psicología Matemática . 10 (2): 148-203. doi : 10.1016 / 0022-2496 (73) 90012-6 .
- Meila, Marina (2003). "Comparación de agrupaciones por la variación de la información". Teoría del aprendizaje y máquinas de kernel . Apuntes de conferencias en Ciencias de la Computación. 2777 : 173–187. doi : 10.1007 / 978-3-540-45167-9_14 . ISBN 978-3-540-40720-1.
- Meila, M. (2007). "Comparación de agrupaciones: una distancia basada en información". Revista de análisis multivariante . 98 (5): 873–895. doi : 10.1016 / j.jmva.2006.11.013 .
- Kingsford, Carl (2009). "Notas de la teoría de la información" (PDF) . Consultado el 22 de septiembre de 2009 .
- Kraskov, Alexander; Harald Stögbauer; Ralph G. Andrzejak; Peter Grassberger (2003). "Agrupación jerárquica basada en información mutua". arXiv : q-bio / 0311039 .
enlaces externos
- Partanalyzer incluye una implementación C ++ de VI y otras métricas e índices para analizar particiones y agrupaciones
- Implementación de C ++ con archivos MATLAB mex