62 votos

Medición de la entropía / información / patrones de una matriz binaria 2d

Quiero medir la entropía de la información/ densidad/ patrón de semejanza bidimensional de una matriz binaria. Permítanme mostrarles algunas fotos de aclaración:

Esta pantalla debe tener un lugar de alta entropía:

A)

enter image description here

Este debe tener medio de la entropía:

B)

enter image description here

Estas imágenes, por último, deben tener cerca de cero-entropía:

C)

enter image description here

D)

enter image description here

E)

enter image description here

¿Hay algún índice que capta la entropía, resp. el "patrón-semejanza" de estas pantallas?

Por supuesto, cada algoritmo (por ejemplo, los algoritmos de compresión; o el algoritmo de rotación propuesto por ttnphns) es sensible a otras características de la pantalla. Estoy buscando un algoritmo que intenta capturar siguientes propiedades:

  • De rotación y simetría axial
  • La cantidad de agrupación
  • Repeticiones

Tal vez más complicado, el algoritmo podría ser sensible a las propiedades de la psicológicade la Gestalt principio", en particular:

  • La ley de proximidad: law of proximity
  • La ley de la simetría: imágenes Simétricas son percibidas colectivamente, incluso a pesar de la distancia:symmetry

Muestra con estas propiedades deben ser asignados a una "baja entropía valor", muestra con bastante random / no estructurados puntos deben ser asignados a un "alto valor de la entropía".

Soy consciente de que probablemente no solo algoritmo de captura de todas estas características; por lo tanto, las sugerencias para los algoritmos de direcciones a la que sólo algunos o incluso sólo una sola característica son muy bienvenidos también.

En particular, estoy buscando concreto, los algoritmos existentes o específica, aplicable ideas (y me otorgará la recompensa de acuerdo a estos criterios).

44voto

jldugger Puntos 7490

Hay un procedimiento simple que captura toda la intuición, incluyendo los psicológicos y los elementos geométricos. Se basa en el uso de proximidad espacial, que es la base de nuestra percepción y proporciona una manera intrínseca a la captura de lo que es sólo imperfectamente medido por simetrías.

Para ello, es necesario medir la "complejidad" de estas matrices en diferentes escalas locales. Aunque tenemos mucha flexibilidad para elegir esas escalas y elegir el sentido en que medida el "proximidad" es bastante simple y lo suficientemente eficaz como para el uso de una pequeña plaza barrios y a buscar en los promedios (o, de manera equivalente, la suma) dentro de ellos. Para este fin, una secuencia de matrices pueden ser derivados de cualquier $m$ por $$ n de la matriz mediante la formación de mudarse de barrio sumas usando $k=2$ $2$ barrios, luego $3$ por $3$, etc, hasta $\min(n,m)$ $\min(n,m)$ (aunque por entonces generalmente hay muy pocos valores para proporcionar nada fiable).

Para ver cómo funciona esto, vamos a hacer los cálculos de las matrices de la pregunta, que voy a llamar a $a_1$ través $a_5$, de arriba a abajo. Aquí están las parcelas de mover las sumas de $k=1,2,3,4$ ($k=1$ es la matriz original, por supuesto) que se aplica a $a_1$.

Figure 1

Las agujas del reloj desde la parte superior izquierda, $k$ es igual a $1$, $2$, $4$, y $3$. Las matrices son de $5$ por $5$, entonces $4$ por $4$, $2$ $2$ y $3$ por $3$, respectivamente. Todos ellos se ven como una clase de "azar." Vamos a medir esta aleatoriedad con su base-2 de la entropía. Por $a_1$, la secuencia de estos entropías es $(0.97, 0.99, 0.92, 1.5)$. Vamos a llamar a esto el "perfil" de $a_1$.

Aquí, en cambio, son el movimiento de las sumas de $a_4$:

Figure 2

Por $k=2, 3, 4$ que hay poca variación, de donde baja entropía. El perfil es $(1.00, 0, 0.99, 0)$. Sus valores son sistemáticamente inferiores a los valores por $a_1$, lo que confirma la intuición de que existe una fuerte "patrón" presentes en $a_4$.

Necesitamos un marco de referencia para la interpretación de estos perfiles. Un perfectamente aleatoria matriz de valores binarios tendrá sólo la mitad de sus valores igual a $0$ y la otra mitad igual a $1$, para una entropía de $1$. El movimiento de sumas dentro de los $k$ por $k$ barrios tienden a tener distribuciones binomiales, dándoles predecible entropías (al menos para las grandes matrices) que se puede aproximar por $1 + \log_2(k)$:

Entropy plot

Estos resultados son producto de la simulación con las matrices de hasta $m=n=100$. Sin embargo, se rompe para arreglos pequeños (tales como los $5$ por $5$ matrices de aquí), debido a la correlación entre los vecinos de windows (una vez que el tamaño de la ventana es de aproximadamente la mitad de las dimensiones de la matriz), y debido a la pequeña cantidad de datos. Aquí es un perfil de referencia de azar $5$ por $5$ matrices generadas por la simulación junto con las parcelas de algunos perfiles:

Profile plots

En esta parcela el perfil de referencia sólido azul. La matriz de perfiles corresponden a $a_1$: rojo, $a_2$: oro, $a_3$: verde, $a_4$: luz azul. (Incluyendo $a_5$ oscurecería la foto, porque está cerca el perfil de $a_4$.) En general los perfiles corresponden a la ordenación de la pregunta: bajan en la mayoría de los valores de $k$ como la aparente pedidos aumenta. La excepción es de $a_1$: hasta el final, por $k=4$, sus sumas tienden a tener entre los más bajos de entropías. Esto revela una sorprendente regularidad: cada $2$ $2$ vecindario en $a_1$ tiene exactamente $1$ o 2 $de$ cuadrados de color negro, nunca de más o de menos. Es mucho menos "al azar" de lo que uno podría pensar. (Esto es en parte debido a la pérdida de información que acompaña a sumar los valores de cada barrio, un procedimiento en el que se condensa $2^{k^2}$ es posible vecindario configuraciones en sólo $k^2+1$ de diferentes sumas posibles. Si queríamos cuenta específicamente para la agrupación y la orientación en cada barrio, en vez de usar mueve sumas que debemos usar en movimiento concatenaciones. Es decir, de cada $k$ por $k$ el barrio de $2^{k^2}$ posibles configuraciones diferentes; por distinguir todos ellos, podemos obtener una mejor medida de la entropía. Tengo la sospecha de que tal medida podría elevar el perfil de $a_1$ en comparación con el resto de imágenes.)

Esta técnica de creación de un perfil de entropías controlado a través de una amplia gama de escalas, mediante la suma (o la concatenación o de lo contrario, la combinación de valores en movimiento barrios, ha sido utilizada en el análisis de imágenes. Es una de dos dimensiones de la generalización de la conocida idea de analizar el texto por primera vez como una serie de letras, y luego como una serie de bigramas (secuencias de dos letras), entonces, como trigraphs, etc. También tiene algunas evidente de las relaciones de fractal análisis (que estudia las propiedades de la imagen al usar escalas más finas). Si tomamos un poco de cuidado al usar un bloque de suma móvil o bloque de concatenación (por lo que no hay coincidencias entre los de windows), se puede derivar de simples relaciones matemáticas entre las sucesivas entropías; sin embargo, sospecho que el uso de la ventana móvil de un enfoque que puede ser más poderoso y es un poco menos arbitraria (porque no depende de cómo, precisamente, la imagen se divide en bloques).

Varias extensiones son posibles. Por ejemplo, para una rotación invariable perfil, el uso de la circular de los barrios en lugar de cuadrado. Todo lo que se generaliza más allá de matrices binarias, por supuesto. Con suficientemente grande matrices se puede calcular localmente variación de entropía perfiles para detectar la no-estacionariedad.

Si un solo número que se desea, en lugar de un perfil completo, elegir la escala en la que la aleatoriedad espacial (o falta de ella) es de interés. En estos ejemplos, que la escala correspondería mejor a los $3$ por $3$ o $4$ por $4$ mudanza de barrio, debido a que por su patrón de todos ellos dependen de las agrupaciones que abarcan tres a cinco células (y $5$ por $5$ vecindario promedios de distancia toda variación en la matriz y así es inútil). En la última escala, las entropías de $a_1$ través $a_5$ son $1.50$, $0.81$, $0$, $0$, y $0$; a la espera de la entropía en esta escala (para un uniformemente al azar de la matriz) es de $1.34$. Esto justifica el sentido de que $a_1$ "debería haber más alta entropía." Para distinguir los $a_3$, $a_4$, y $a_5$, los cuales están asociados con $0$ entropía en esta escala, mira la siguiente resolución más fina ($3$ por $3$ barrios): sus entropías son $1.39$, $0.99$, $0.92$, respectivamente mientras que un azar de la cuadrícula se espera que tenga un valor de $1.77$). Con estas medidas, la pregunta original pone las matrices exactamente en el orden correcto.

12voto

Uri Puntos 111

En primer lugar, mi sugerencia es puramente intuitiva: yo no sé nada en el patrón de reconocimiento de campo. Segundo, la alternativa docenas de sugerencias como la mía.

Empiezo con la idea de que un regular de configuración (es decir, con baja entropía) debe ser de alguna manera simétrica, isomorfo a este o que su tranformants. Por ejemplo, en las rotaciones.

Usted podría rotar (girar para 90 grados, 180 grados, etc) su matriz hasta la configuración de acuerdo con el original. Siempre de acuerdo a 4 rotaciones (de 360 grados), pero a veces puede concurrir anteriores (como matriz E en la imagen).

En cada rotación, contar el número de celdas no con los mismos valores entre el original y la configuración del girado. Por ejemplo, si se compara la matriz original Una con su rotación de 90 grados descubrirás 10 celdas donde no hay lugar en una matriz en blanco y en la otra matriz. Luego de comparar la matriz original con su giro de 180 grados: 11 estas células se encuentran. 10 células es la discrepancia entre el original de la matriz de Una y 270 grados de rotación. 10+11+10=31 es la "entropía" de la matriz de Una.

Para la matriz B, la "entropía" es de 20, y de la matriz E es de sólo 12. Para las matrices C y D "entropía" es 0 debido a las rotaciones de la parada después de 90 grados: isomorfismo alcanzado ya.

enter image description here

5voto

karatchov Puntos 230

La información se define comúnmente como $h(x) = \log p(x)$. Hay una buena teoría que explica que $\log_2 p(x)$ es la cantidad de bits que necesita para código de $x$ $p$. Si quieres saber más sobre esto, lea la codificación aritmética.

Así que ¿cómo puede resolver su problema? Fácil. Encontrar unos $p$, que representa sus datos y el uso de $-\log p(x)$, donde $x$ es un nuevo ejemplo de como una medida de la sorpresa o la información de encontrarse con él.

Lo difícil es encontrar algún modelo para $p$ y para generar los datos. Tal vez usted puede venir para arriba con un algoritmo que genera las matrices que se consideren "probable".

Algunas ideas para el montaje de $p$.

  1. Si sólo está buscando en matrices 5x5, usted necesita solamente $2^{25}$ bits para almacenar todas las posibles matrices, por lo que sólo puede enumerar todos ellos y asignar una cierta probabilidad a cada uno.
  2. El uso de un restringido de la máquina de Boltzmann para que se ajuste a los datos (a continuación, usted tendría que usar la energía libre como sustituto de la información, pero eso está bien),
  3. Usar zip como un sustituto para $-\log p(x)$ y no se preocupan por toda probabilidad historia anterior. Incluso es formalmente correcto, ya que se usa zip como una aproximación a la complejidad de Kolmogorov y esto ha sido hecho por los teóricos de la información, así que conduce a la compresión normalizada de la distancia,
  4. Tal vez de usar una gráfica de un modelo espacial antes de creencias y el uso de variables de Bernoulli a nivel local.
  5. Para codificar la invariancia traslacional, puede utilizar una energía basada en el modelo mediante un convolucional de la red.

Algunas de las ideas anteriores son bastante pesados y venir de aprendizaje de máquina. En caso de que quieras tener más consejos, sólo tiene que utilizar los comentarios.

4voto

Uri Puntos 111

Mi siguiente propuesta es bastante insighted que deducir, por lo que no puedo probarlo, pero al menos puede ofrecer alguna justificación. El procedimiento de evaluación de la "entropía" de la configuración de puntos incluye:

  1. Digitalizar puntos.
  2. Realizar la comparación de la configuración de la misma permutada, muchos veces, por ortogonal análisis de Procrustes.
  3. Parcela resultados de las comparaciones (coeficiente de identidad) y evaluar jaggedness de la trama.

Digitalizar puntos, es decir, tomar sus coordenadas. Por ejemplo, a continuación se muestra la configuración D con puntos numerados (la numeración de orden puede ser arbitrario) y sus coordenadas. enter image description here

spot x   y
1   1   1
2   3   1
3   5   1
4   2   2
5   4   2
6   1   3
7   3   3
8   5   3
9   2   4
10  4   4
11  1   5
12  3   5
13  5   5

Hacer permutaciones y realizar análisis de Procrustes. Permutar puntos (filas en los datos) al azar y realizar Procrustes comparación de la original (no permutada) con los datos de la permutada uno; registro de la identidad coeficiente (medida de la similitud de las dos configuraciones, la salida por el análisis). Repita permutación - Procrustes de ahorro de coeficiente, muchas veces (por ejemplo, 1000 veces o más).

¿Qué podemos esperar de la identidad de los coeficientes (IDc) que se obtiene después de la operación anterior en un regular de la estructura? Considerar, por ejemplo, la configuración anterior D. Si comparamos las coordenadas originales establece consigo mismo, vamos a obtener IDc=1, por supuesto. Pero si tenemos permutar algunos puntos de la IDc entre la serie original y la permutada será algún valor por debajo de 1. Permítanos permutar, por ejemplo, un par de puntos, marcados como 1 y 4. IDc=.964. Ahora, en cambio, permutar puntos 3 y 5. Curiosamente, IDc será .964 de nuevo. El mismo valor, ¿por qué? Puntos 3 y 5 son simétricas a 1 y 4, de manera que la rotación de 90 grados superponer. Procrustes comparación es insensible a la rotación o reflexión, y por lo tanto dentro de permutación par 1-4 es el "mismo" dentro de permutación par de 5-3, para ella. Para añadir más ejemplo, si usted permutar sólo puntos 4 y 7, IDc será de nuevo .964! Es appeares que para Procrustes, dentro de permutación par de 4-7 es el "mismo" como los dos anteriores en el sentido de que proporciona el mismo grado de similitud (medido por IDc). Obviamente, todo esto es debido a que la configuración D es regular. Para regular la configuración se espera obtener valores discretos en lugar de IDc en nuestra permutación/comparación experimento; mientras que para los irregulares de configuración es de esperar que los valores tienden a ser continua.

Parcela en la grabación de IDc valores. Por ejemplo, ordenar los valores y hacer de línea de parcela. Hice el experimento - 5000 permutaciones - con cada una de sus configuraciones A, B (ambos bastante irregular), D, E (regular) y aquí está la línea de la trama:

enter image description here

Tenga en cuenta cuánto más irregulares son las líneas D y E (D, especialmente). Esto es debido a que de discreto de valores. Los valores de a y B son mucho más continuo. Usted puede recoger a ti mismo algún tipo de estadística que estima el grado de discreto/continuety, en lugar de trazar. Una parece que no hay más continuo que el de B (para usted, la configuración es un poco menos regular, pero mi línea de la parcela no parecen demostrar que lo es) o, si no, tal vez muestra un poco de otro patrón de IDc valores. Lo otro patrón? Esto está más allá del alcance de mi respuesta todavía. La gran pregunta de si Una es de hecho menos regular que la de B: puede ser para el ojo, pero no necesariamente para el análisis de Procrustes o de otra persona en el ojo.

Por cierto, toda la permutación/Procrustes experimento que hice muy rápidamente. He utilizado mi propio análisis de Procrustes macro para el SPSS (que se encuentra en mi página web) y agregar algunas líneas de código para hacer permutaciones.

3voto

Enrico Puntos 289

La información mutua, considerando a cada dimensión de una variable aleatoria, por lo que cada matriz como un conjunto de pares de números, debe ayudar en todos los casos, excepto para el C, donde no estoy seguro del resultado.

Ver la discusión en torno a la figura 8 (a partir de la p24) en la regresión el análisis del rendimiento en el TMVA manual o el correspondiente arxiv entrada.

Different metrics for different distributions

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X