Algorithme pour noter la similarité d'ensembles de nombres

Question

Qu'est-ce qu'un algorithme permettant de comparer plusieurs ensembles de nombres à un ensemble cible afin de déterminer ceux qui sont les plus "similaires"?

L’une des utilisations de cet algorithme serait de comparer les prévisions météorologiques horaires actuelles aux enregistrements météorologiques historiques afin de trouver un jour avec une météo similaire.

La similitude de deux ensembles étant un peu subjective, l’algorithme doit en réalité simplement différencier les bons résultats des mauvais résultats. Nous avons beaucoup de données historiques, je voudrais donc essayer de réduire le nombre de jours que les utilisateurs doivent parcourir en jetant automatiquement les ensembles qui ne sont pas proches et en essayant de classer les "meilleurs" résultats. correspond en haut de la liste.

Modifier : Idéalement, le résultat de l'algorithme serait comparable aux résultats obtenus avec différents ensembles de données. Par exemple, en utilisant l’erreur quadratique moyenne suggérée par Niles produit de très bons résultats, mais les nombres générés lors de la comparaison de la température ne peuvent pas être comparés à ceux générés avec d'autres données telles que la vitesse du vent ou les précipitations, car l'échelle des données est différente. Certaines des données non météorologiques étant très volumineuses, l’algorithme d’erreur quadratique moyenne génère des nombres de centaines de milliers par rapport aux dizaines ou centaines générées par l’utilisation de la température.

Answer 1

Je pense que la mesure d'erreur quadratique moyenne pourrait fonctionner pour des applications telles que la météo. Il est facile à calculer et donne des chiffres qui ont du sens.

Puisque vous souhaitez comparer les mesures au fil du temps, vous pouvez simplement omettre les valeurs manquantes du calcul.

Pour les valeurs qui ne sont pas liées dans le temps ou même non triées, les données de dispersion multidimensionnelles sont un peu plus difficiles. Le choix d'une métrique de bonne distance fait partie de l'art d'analyser de telles données.

Answer 2

Utilisez le coefficient de corrélation de pearson. J'ai compris comment le calculer dans une requête SQL qui peut être trouvée ici: http://vanheusden.com /misc/pearson.php

Answer 3

En finance, ils utilisent Beta pour mesurer la corrélation de 2 séries de nombres. Par exemple, Beta pourrait répondre à la question "Au cours de la dernière année, de combien le prix d’IBM augmenterait-il le jour où le prix de l’indice S & P 500 a augmenté de 5%?" Il traite du pourcentage du déménagement, de sorte que les 2 séries peuvent avoir des échelles différentes.

Dans mon exemple, le bêta est Covariance (IBM, S & P 500) / Variance (S & P 500).

Wikipedia a des pages expliquant Covariance , Variance , et bêta: http://en.wikipedia.org/wiki/Beta_ (finance)

Answer 4

Regardez les sites statistiques. Je pense que vous recherchez une corrélation.

Answer 5

Par exemple, je suppose que vous mesurez la température, le vent et les précipitations. Nous appellerons ces éléments "fonctionnalités". Les valeurs valides peuvent donc être:

• Temp: -50 à 100F (je suis dans le Minnesota, États-Unis)
• Vent: 0 à 120 milles / heure (je ne sais pas si cela est réaliste, mais gardez-moi avec moi)
• Précip: 0 à 100

Commencez par normaliser vos données. Temp a une plage de 150 unités, Wind 120 unités et Precip 100 unités. Multipliez vos unités de vent par 1,25 et votre précipité par 1,5 pour obtenir à peu près la même "échelle". comme ton temp. Ici, vous pouvez avoir l’imagination et créer des règles qui valorisent une caractéristique plus valable que d’autres. Dans cet exemple, le vent peut avoir une plage très étendue mais reste généralement dans une plage plus petite. Vous souhaitez donc le peser moins pour l'empêcher de fausser vos résultats.

Maintenant, imaginez chaque mesure comme un point dans un espace multidimensionnel. Cet exemple mesure l’espace 3D (temp, vent, précip). La bonne chose est que, si nous ajoutons plus de fonctionnalités, nous augmentons simplement la dimensionnalité de notre espace mais les calculs restent les mêmes. Quoi qu'il en soit, nous voulons trouver les points historiques les plus proches de notre point actuel. Le moyen le plus simple de le faire est la la distance euclidienne . Alors, mesurez la distance entre notre point actuel et chaque point historique et gardez les correspondances les plus proches:

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

Il s’agit d’une approche fondée sur la force brute. Si vous avez le temps, vous pourriez devenir beaucoup plus sophistiqué. Les données multidimensionnelles peuvent être représentées sous forme d'arborescences telles que kd-trees ou r-trees . Si vous avez beaucoup de données, comparer votre observation actuelle avec chaque observation historique serait trop lent. Les arbres accélèrent votre recherche. Vous voudrez peut-être consulter le clustering de données et Recherche de voisin le plus proche .

A bientôt.

Answer 6

Parlez à un statisticien.

Sérieusement.

Ils font ce genre de chose pour gagner leur vie.

Vous écrivez que la "similitude de deux ensembles est un peu subjective" ", mais ce n'est pas du tout subjectif - il s'agit de déterminer les critères de similitude appropriés pour votre domaine de problèmes.

C’est l’une des situations dans lesquelles vous feriez mieux de parler à un professionnel que de demander à un groupe de programmeurs.

Answer 7

Tout d'abord, demandez-vous s'il s'agit d'ensembles ou de collections ordonnées.

Je suppose que ce sont des collections ordonnées avec des doublons. L’algorithme le plus évident consiste à sélectionner une tolérance dans laquelle les nombres sont considérés comme identiques et à compter le nombre d’emplacements où les nombres sont identiques sous cette mesure.

Answer 8

J'ai une solution implémentée pour cela dans mon application, mais je cherche à savoir s'il y a quelque chose qui est meilleur ou plus "correct". Pour chaque jour historique, je fais ce qui suit:

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;
}

Je trie ensuite tous les résultats de haut en bas.

Étant donné que la corrélation est une valeur de -1 à 1 indiquant si les chiffres diminuent ou augmentent ensemble, je "pénalise" alors qu'avec la différence en pourcentage, les moyennes des deux séries de chiffres.

Answer 9

Vous avez mentionné à quelques reprises que vous ne connaissiez pas la distribution des données, ce qui est bien sûr vrai. Je veux dire, demain il pourrait y avoir un jour qui ferait 150 degrés F avec des vents de 2000 km / h, mais cela semble assez improbable.

Je dirais que vous avez une très bonne idée de la distribution, car vous avez un long historique. Cela dit, vous pouvez tout définir en termes de quantiles de la distribution historique et faire quelque chose avec une différence absolue ou quadratique des quantiles sur toutes les mesures. C'est une autre méthode de normalisation, mais qui prend en compte les non-linéarités dans les données.

La normalisation dans n'importe quel style devrait rendre toutes les variables comparables.

Par exemple, disons qu'un jour est venteux et chaud: cela pourrait avoir un quantile temporaire de 0,75 et un quantile de vent de 0,75. Le quantile 0,76 pour la chaleur peut être éloigné de 1 degré et celui du vent, de 3 km / h.

Cet accent mis sur la distribution empirique est également facile à comprendre et pourrait être plus robuste que l’estimation normale (comme l’erreur moyenne).

Answer 10

Les deux ensembles de données sont-ils ordonnés ou non?

Si ordonné, les indices sont-ils les mêmes? Espacé équitablement?

Si les indices sont communs (températures mesurées les mêmes jours (mais à des endroits différents)), par exemple, vous pouvez régresser le premier jeu de données par rapport au second, puis testez que la pente est égale à 1 et que l'interception est égale à 0.
http://stattrek.com/AP-Statistics-4/ Test-Slope.aspx? Tutorial = AP

Sinon, vous pouvez faire deux régressions, des valeurs y = par rapport à leurs indices. http://fr.wikipedia.org/wiki/Correlation . Vous voudriez toujours comparer les pentes et les interceptions.

====

Si non ordonné, je pense que vous voulez regarder les fonctions de distribution cumulative http://fr.wikipedia.org/wiki/Cumulative_distribution_function

Un test pertinent est celui de Kolmogorov-Smirnov: http://fr.wikipedia.org/wiki/Kolmogorov-Smirnov_test

Vous pouvez également consulter

test t de l'étudiant, http://en.wikipedia.org/wiki/Student%27s_t-test

ou un test de classement signé Wilcoxon http://en.wikipedia.org/wiki/ Wilcoxon_signed-rank_test

pour tester l’égalité des moyennes entre les deux échantillons.

Et vous pouvez tester l'égalité des variances avec un test de Levene http://www.itl.nist.gov/div898/handbook/eda/section3/eda35a.htm

Remarque: il est possible que des ensembles de données différents aient la même moyenne et la même variance - en fonction de la rigueur avec laquelle vous souhaitez être (et de la quantité de données dont vous disposez), vous pourriez envisager de tester. pour l'égalité des moments les plus élevés, ainsi.

Answer 11

Vous pouvez peut-être voir votre ensemble de chiffres sous forme de vecteur (chaque numéro de l'ensemble étant un composant du vecteur).

Ensuite, vous pouvez simplement utiliser le produit scalaire pour calculer la similarité de 2 vecteurs donnés (c'est-à-dire un ensemble de nombres).

Vous devrez peut-être normaliser vos vecteurs.

Plus: Similarité de cosinus