cómo identificar el conjunto mínimo de parámetros que describen un conjunto de datos

Question

Tengo un montón de datos de pruebas de regresión. Cada prueba es solo una lista de mensajes (matrices asociativas), asignando nombres de campos de mensaje a valores. Hay mucha repetición dentro de estos datos.

Por ejemplo

test1 = [ 
     { sender => 'client', msg => '123', arg => '900', foo => 'bar', ... }, 
     { sender => 'server', msg => '456', arg => '800', foo => 'bar', ... }, 
     { sender => 'client', msg => '789', arg => '900', foo => 'bar', ... }, 
    ] 

me gustaría para representar los datos de campo (como un árbol de decisión mínima profundidad?) De manera que cada mensaje puede ser regenerado mediante programación utilizando un número mínimo de parámetros. Por ejemplo, en el anterior

• foo es siempre 'bar', por lo que no necesito mencionar que
• remitente y el cliente están correlacionados, por lo que sólo es necesario mencionar uno u otro
• msg y es diferente cada vez

así que me gustaría ser capaz de regenerar estos mensajes con un programa a lo largo de las líneas de

write_msg('client', '123') 
write_msg('server', '456') 
write_msg('client', '789') 

donde la función write_msg estaría compuesta por sentencias if anidadas o llamadas a subfunciones utilizando los parámetros.

Según mis datos originales, ¿cómo puedo determinar el conjunto de parámetros "más importantes", es decir, los que me permitirán recrear mi conjunto de datos utilizando la menor cantidad de argumentos?

Answer 1

Los siguientes artículos describen algortithms para descubrir dependencias funcionales:

Y. Huhtala, J. Kärkkäinen, P. Porkka, y H. Toivonen. TANE: un algoritmo eficiente para descubrir funcional y dependencias aproximadas. El Computer Journal, 42 (2): 100-111, 1999, doi:10.1093/comjnl/42.2.100.

I. Savnik y P. A. Flach. Bottom-up inducción de dependencias funcionales de las relaciones. En Proc. AAAI-93 Taller: Descubrimiento de Conocimiento en Bases de Datos, páginas 174-185, Washington, DC, EE.UU., 1993.

C. Wyss, C. Giannella, y E. Robertson. FastFDs: A Dirigido por Heurística, Profundidad-Primero Algoritmo para Minería Funcional Dependencias de las Instancias de Relación. En Proc. Data Warehousing y Knowledge Discovery, páginas 101-110, Munich, Alemania, 2001, doi:10.1007/3-540-44801-2.

Hong Yao y Howard J. Hamilton. "Minería de dependencias funcionales de datos". Minería de datos y descubrimiento de conocimiento, 2008, doi:10.1007/s10618-007-0083-9.

También ha habido algún trabajo en el descubrimiento de dependencias multivalor:

I. Savnik y P. A. Flach. "Discovery de Mutlivalued Dependencias de Relaciones". análisis inteligente de datos Diario, 4 (3): 195-211, IOS Press, 2000.

Answer 2

Esto se ve muy similar a Database Normalization.

Tiene una relación (su conjunto de datos de prueba) y algunas dependencias funcionales conocidas ({sender} => arg, {} => foo y posiblemente {msg} => remitente. Si el orden de las pruebas es importante, entonces agregue {testNr} => msg.) y desea eliminar redundancias.

Trate su conjunto de prueba como una tabla de base de datos, aplique las reglas de normalización y cree funciones equivalentes (getArgFromSender (remitente) etc.) para cada unión.

Answer 3

Si el número de campos y registros es pequeño:

fuerza bruta por bucle a través de todas las combinaciones de campos, y para cada combinación de detectar si hay varios elementos de la lista, que se correlacionan con el mismo valor .

Si se puede vivir con una bastante buena selección de campos:

Comience suponiendo que necesita todos los campos. Luego, seleccione un campo al azar y vea si se puede eliminar; si puede, tacharlo del conjunto de campos. De lo contrario, elija otro campo al azar y vuelva a intentarlo. Si encuentra que no se pueden eliminar campos, entonces ha encontrado un conjunto razonable de campos. Si eligió otros campos primero, puede encontrar una mejor solución. Puede repetir todo el procedimiento varias veces y elegir la mejor solución si lo desea. Este tipo de enfoque se llama hill climbing.

(sospecho que este problema es NP complete, es decir, es probable que no sepamos de una solución eficiente y poderosa, por lo que no vale la pena perder el sueño tratando de imaginar una solución perfecta.)