Vous souhaitez un nouveau programme qui prend en entrée un ou plusieurs critères, puis affiche une estimation du temps d'exécution ou de l'utilisation de la mémoire. C'est un problème d'apprentissage automatique.
Vos entrées peuvent être répertoriés comme un vecteur de nombres, comme ceci:
input = [ A, B, C, D, E ]
L'un des algorithmes les plus simples pour ce serait un K-nearest neighbor algorithm. L'idée sous-jacente est que vous utiliserez votre vecteur d'entrée de nombres et que vous trouverez dans votre base de données le vecteur de nombres le plus proche de votre vecteur d'entrée.Par exemple, étant donné ce vecteur d'entrées:
input = [ 11, 1.8, 3557, 29, 10 ]
Vous pouvez supposer que le temps d'exécution et de la mémoire devraient être très similaires aux valeurs de cette course (à l'origine dans votre tableau ci-dessus):
R0001 12 2 3556 27 9
Il existe plusieurs algorithmes pour calculer la similitude entre ces deux vecteurs, un tel algorithme simple et intuitive est le Euclidean distance. À titre d'exemple, la distance euclidienne entre le vecteur d'entrée et le vecteur de la table est la suivante:
dist = sqrt((11-12)^2 + (1.8-2)^2 + (3557-3556)^2 + (27-29)^2 + (9-10)^2)
dist = 2.6533
Il devrait être intuitivement évident que les points avec une distance inférieure devraient être meilleures estimations pour temps de fonctionnement et l'utilisation de la mémoire, comme la distance devrait décrire la similarité entre deux ensembles de critères. En supposant que vos critères sont informatifs et bien sélectionnés, les points ayant des critères similaires devraient avoir un temps d'exécution et une utilisation de la mémoire similaires.
Voici quelques exemples de code de la façon de le faire en R:
r1 = c(11,1.8,3557,29,10)
r2 = c(12,2.0,3556,27, 9)
print(r1)
print(r2)
dist_r1_r2 = sqrt((11-12)^2 + (1.8-2)^2 + (3557-3556)^2 + (27-29)^2 + (9-10)^2)
print(dist_r1_r2)
smarter_dist_r1_r2 = sqrt(sum((r1 - r2)^2))
print(smarter_dist_r1_r2)
Prendre le temps de fonctionnement et l'utilisation de la mémoire de votre rangée la plus proche est l'algorithme KNN pour K = 1. Cette approche peut être étendue pour inclure des données provenant de plusieurs lignes en prenant une combinaison pondérée de plusieurs lignes de la base de données, avec des lignes avec des distances inférieures à votre vecteur d'entrée contribuant davantage aux estimations. Lisez la page Wikipedia sur KNN pour plus d'informations, en particulier en ce qui concerne la normalisation des données, y compris les contributions de plusieurs points, et les distances de calcul. Lorsque vous calculez la différence entre ces listes de vecteurs d'entrée, vous devriez envisager de normaliser vos données. La raison pour cela est qu'une différence de 1 unité entre 3557 et 3556 pour le critère C peut ne pas être équivalente à une différence de 1 entre 11 et 12 pour le critère A. Si vos données sont normalement distribuées, vous pouvez les convertir toutes en standard scores (or Z-scores) en utilisant cette formule:
N_trans = (N - mean(N))/sdev(N)
il n'y a pas de solution générale sur la « bonne » pour normaliser les données car il dépend du type et la gamme de données que vous avez, mais Z-scores sont faciles à calculer et un bon méthode à essayer en premier.
Il existe de nombreuses techniques plus sophistiquées pour construire des estimations telles que celle-ci, y compris la régression linéaire, la régression du vecteur de support et la modélisation non linéaire. L'idée derrière certaines des méthodes les plus sophistiquées est que vous essayez de développer une équation qui décrit la relation de vos variables avec le temps ou la mémoire. Par exemple, une application simple pourrait juste avoir un critère et vous pouvez essayer de distinguer entre les modèles tels que:
running_time = s1 * A + s0
running_time = s2 * A^2 + s1 * A + s0
running_time = s3 * log(A) + s2 * A^2 + s1 * A + s0
L'idée est que A est vos critères fixes et sN sont une liste de paramètres libres que vous pouvez tweak jusqu'à ce que vous obteniez un modèle qui fonctionne bien. Un problème avec cette approche est qu'il y a beaucoup de différents modèles possibles qui ont différents nombres de paramètres. La distinction entre les modèles qui ont un nombre différent de paramètres est un problème difficile dans les statistiques, et je ne recommande pas de l'aborder lors de votre première incursion dans l'apprentissage automatique.
Quelques questions que vous devriez vous poser sont les suivantes:
- Est-ce que tous mes critères affectent à la fois le temps en cours d'exécution et utilisation de la mémoire? Est-ce que certains affectent seulement l'un ou l'autre et sont inutiles d'un point de vue prédictif? Répondre à cette question est appelé feature selection, et est un problème en suspens dans machine learning.
- Avez-vous des estimations a priori de la façon dont vos variables devraient influencer le temps de fonctionnement ou l'utilisation de la mémoire? Par exemple, vous savez peut-être que votre application utilise un algorithme de tri N * log (N) dans le temps, ce qui signifie que vous connaissez explicitement la relation entre un critère et votre temps de fonctionnement.
- Vos rangées de critères d'entrée mesurés associées à la durée et à l'utilisation de la mémoire couvrent-elles tous les cas d'utilisation plausibles pour votre application? Si c'est le cas, vos estimations seront meilleures car l'apprentissage automatique peut avoir des difficultés avec des données qui ne lui sont pas familières.
- La durée et la mémoire de votre programme dépendent-elles de critères que vous n'indiquez pas dans votre stratégie d'estimation? Par exemple, si vous dépendez d'une ressource externe telle qu'une Web Spider, des problèmes avec votre réseau peuvent influencer le temps d'exécution et l'utilisation de la mémoire d'une manière difficile à prévoir. Si c'est le cas, vos estimations auront beaucoup plus de variance.
Donc, pour chaque 'RUN', connaissez-vous également l'heure et l'utilisation de la mémoire? – unutbu
oui. Les temps de fonctionnement et l'utilisation de la mémoire sont conservés dans la table. Ils sont des milliers d'entre eux. – user369861