algorithm - learning - Algoritmo para anotar la similitud de conjuntos de números

regression algorithms

Question

¿Qué es un algoritmo para comparar múltiples conjuntos de números contra un conjunto de objetivos para determinar cuáles son los más "similares"?

Un uso de este algoritmo sería comparar el pronóstico del tiempo por hora de hoy con las grabaciones históricas del clima para encontrar un día que tuviera un clima similar.

La similitud de dos conjuntos es un poco subjetiva, por lo que el algoritmo realmente necesita diferenciar entre las buenas coincidencias y las malas. Tenemos una gran cantidad de datos históricos, por lo que me gustaría tratar de reducir la cantidad de días que los usuarios deben revisar tirando automáticamente conjuntos que no están cerca y tratando de poner las "mejores" coincidencias en la parte superior de la lista.

Editar : Idealmente, el resultado del algoritmo sería comparable a los resultados que usan diferentes conjuntos de datos. Por ejemplo, usar el error cuadrático medio como sugiere Niles produce resultados bastante buenos, pero los números generados al comparar la temperatura no se pueden comparar con los números generados con otros datos como la velocidad del viento o la precipitación porque la escala de los datos es diferente. Algunos de los datos no meteorológicos son muy grandes, por lo que el algoritmo de error cuadrático medio genera números en cientos de miles en comparación con las decenas o cientos que se generan al usar la temperatura.

Answer 1

Como ejemplo, supongo que estás midiendo la temperatura, el viento y la precipitación. Llamaremos a estos elementos "características". Entonces los valores válidos pueden ser:

• Temp: -50 a 100F (estoy en Minnesota, EE. UU.)
• Viento: de 0 a 120 millas por hora (no estoy seguro de si esto es realista, pero tenga paciencia)
• Precip: 0 a 100

Comience por normalizar sus datos. La temperatura tiene un rango de 150 unidades, Wind 120 unidades y Precip 100 unidades. Multiplique sus unidades de viento por 1.25 y Precip por 1.5 para hacerlas más o menos la misma "escala" que su temperatura. Puede hacerse elegante aquí y establecer reglas que consideren que una característica es más valiosa que otras. En este ejemplo, el viento puede tener un gran alcance, pero por lo general se mantiene en un rango menor, por lo que debe pesarlo menos para evitar que sesgue los resultados.

Ahora, imagine cada medida como un punto en el espacio multidimensional. Este ejemplo mide el espacio en 3D (temperatura, viento, precipitación). Lo bueno es que si agregamos más funciones, simplemente aumentamos la dimensionalidad de nuestro espacio, pero las matemáticas siguen siendo las mismas. De todos modos, queremos encontrar los puntos históricos que están más cerca de nuestro punto actual. La forma más fácil de hacerlo es la distancia euclidiana . Así que mida la distancia desde nuestro punto actual a cada punto histórico y mantenga las coincidencias más cercanas:

for each historicalpoint

    distance = sqrt(
        pow(currentpoint.temp - historicalpoint.temp, 2) + 
        pow(currentpoint.wind - historicalpoint.wind, 2) +
        pow(currentpoint.precip - historicalpoint.precip, 2))

    if distance is smaller than the largest distance in our match collection
        add historicalpoint to our match collection
        remove the match with the largest distance from our match collection

next

Este es un enfoque de fuerza bruta. Si tienes tiempo, podrías ser mucho más elegante. Los datos multidimensionales se pueden representar como árboles como kd-trees o r-trees . Si tiene muchos datos, comparar su observación actual con cada observación histórica sería demasiado lento. Los árboles aceleran tu búsqueda. Es posible que desee echar un vistazo a la Agrupación de datos y la Búsqueda de vecinos más cercanos .

Aclamaciones.

Answer 2

Creo que la métrica de error cuadrático medio podría funcionar para aplicaciones como el clima se compara. Es fácil de calcular y da números que tienen sentido.

Como quiera comparar las medidas a lo largo del tiempo, puede omitir los valores perdidos del cálculo.

Para los valores que no están limitados en el tiempo o incluso no ordenados, los datos de dispersión multidimensional son un poco más difíciles. Elegir una buena métrica de distancia se convierte en parte del arte de analizar dichos datos.

Answer 3

En finanzas, usan Beta para medir la correlación de 2 series de números. Por ejemplo, Beta podría responder la pregunta "Durante el último año, ¿cuánto subiría el precio de IBM en un día en que el precio del índice S & P 500 subió un 5%?" Se trata del porcentaje del movimiento, por lo que las 2 series pueden tener diferentes escalas.

En mi ejemplo, la Beta es Covarianza (IBM, S & P 500) / Varianza (S & P 500).

Wikipedia tiene páginas que explican Covarianza , Varianza y Beta: http://en.wikipedia.org/wiki/Beta_(finance)

Answer 4

En primer lugar, pregúntese si se trata de conjuntos o colecciones ordenadas.

Supongo que estas son colecciones ordenadas con duplicados. El algoritmo más obvio es seleccionar una tolerancia dentro de la cual los números se consideran iguales, y contar el número de ranuras donde los números son iguales bajo esa medida.

Answer 5

Mira los sitios estadísticos. Creo que estás buscando una correlación.

Answer 6

Tengo una solución implementada para esto en mi aplicación, pero estoy buscando si hay algo mejor o más "correcto". Para cada día histórico hago lo siguiente:

function calculate_score(historical_set, forecast_set)
{
    double c = correlation(historical_set, forecast_set);
    double avg_history = average(historical_set);
    double avg_forecast = average(forecast_set);
    double penalty = abs(avg_history - avg_forecast) / avg_forecast
    return c - penalty;
}

Luego clasifico todos los resultados de mayor a menor.

Como la correlación es un valor de -1 a 1 que dice si los números caen o suben juntos, entonces "penalizo" con la diferencia porcentual los promedios de los dos conjuntos de números.

Answer 7

En un par de ocasiones, mencionó que no conoce la distribución de los datos, lo cual es cierto. Quiero decir, mañana podría haber un día que sea de 150 grados F, con vientos de 2000 km / h, pero parece bastante improbable.

Yo diría que tiene una muy buena idea de la distribución, ya que tiene un largo historial histórico. Dado eso, puede poner todo en términos de cuantiles de la distribución histórica, y hacer algo con la diferencia absoluta o cuadrada de los cuantiles en todas las medidas. Este es otro método de normalización, pero uno que da cuenta de las no linealidades en los datos.

La normalización en cualquier estilo debe hacer que todas las variables sean comparables.

Como ejemplo, digamos que un día es ventoso y caluroso: podría tener un cuantil de temperatura de .75 y un cuantil de viento de .75. El cuantil .76 para el calor puede estar a 1 grado de distancia, y el del viento puede estar a 3 kmh de distancia.

Este enfoque en la distribución empírica también es fácil de entender y podría ser más sólido que la estimación normal (como Mean-square-error).

Answer 8

Habla con un estadístico.

Seriamente.

Hacen este tipo de cosas para ganarse la vida.

Usted escribe que la "similitud de dos conjuntos es un poco subjetiva" , pero no es subjetiva en absoluto; se trata de determinar los criterios apropiados para la similitud del dominio de su problema.

Esta es una de esas situaciones en las que es mucho mejor hablar con un profesional que preguntarle a un grupo de programadores.

Answer 9

Use el coeficiente de correlación de Pearson. Descubrí cómo calcularlo en una consulta SQL que se puede encontrar aquí: http://vanheusden.com/misc/pearson.php

Answer 10

¿Los dos conjuntos de datos están ordenados o no?

Si se ordena, ¿son los índices iguales? igualmente espaciado?

Si los índices son comunes (temperaturas medidas en los mismos días (pero diferentes ubicaciones), por ejemplo, puede hacer retroceder el primer conjunto de datos contra el segundo, y luego probar que la pendiente es igual a 1, y que la intersección es 0.
http://stattrek.com/AP-Statistics-4/Test-Slope.aspx?Tutorial=AP

De lo contrario, puede hacer dos regresiones, de los valores y = contra sus índices. http://en.wikipedia.org/wiki/Correlation . Aún querrás comparar pendientes e intersecciones.

====

Si no está ordenado, creo que desea consultar las funciones de distribución acumulativa http://en.wikipedia.org/wiki/Cumulative_distribution_function

Una prueba relevante es Kolmogorov-Smirnov: http://en.wikipedia.org/wiki/Kolmogorov-Smirnov_test

También podrías mirar

Prueba t de Student, http://en.wikipedia.org/wiki/Student%27s_t-test

o una prueba de rango con signo de Wilcoxon http://en.wikipedia.org/wiki/Wilcoxon_signed-rank_test

para probar la igualdad de medias entre las dos muestras.

Y podría probar la igualdad de varianzas con una prueba de Levene http://www.itl.nist.gov/div898/handbook/eda/section3/eda35a.htm

Nota: es posible que diferentes conjuntos de datos tengan la misma media y varianza; según la rigurosidad que desee tener (y la cantidad de datos que tenga), también podría considerar probar la igualdad de los momentos superiores.

Answer 11

Tal vez puedas ver tu conjunto de números como un vector (cada número del conjunto es un componente del vector).

Entonces, simplemente puede usar el producto de puntos para calcular la similitud de 2 vectores dados (es decir, un conjunto de números).

Es posible que necesite normalizar sus vectores.

Más: similitud coseno