Algorithmie: comment trouver la 2eme valeur la plus élevée d'une liste

 Lors des entretiens d'embauche d'un développeur, il est possible de rencontrer cette question: 

 Comment  trouver le la 2eme valeur la plus élevée d'une liste ? .

Bien qu'anodine, cette question ouvre vers de nombreuses déclinaisons et soulève des nouvelles questions.

Est ce que la liste est finie ?, de taille compatible avec la mémoire du serveur ? etc..

Première réponse qui vient spontanément: trier la liste et prendre le 2eme élément.

Démonstration en Python

Commençons par générer une liste aléatoire de 1000000 éléments de 1 à 50.

 

import random
randomlist = []
for i in range(0,1000000):
    n = random.randint(1,50)
    randomlist.append(n)

Puis récupérons le deuxième élément après le tri.

 

%%time
listetriee = sorted(randomlist,reverse =1)
print(listetriee[1])

50
Wall time: 210 ms

Erreur, on devrait retourner vraisemblablement la valeur 49 et non pas 50.

En examinant le début de la liste triée:

print(listetriee[:20])

[50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50]

On n'a pas traité le cas des valeurs identiques... Pour rendre unique les éléments d'une liste, le plus simple est de passer par un 'set'.

 

%%time
unique = set(randomlist)
print('taille de la liste:', len(unique))
listetriee =sorted(unique, reverse = 1)
print(listetriee[1])

taille de la liste: 50
49
Wall time: 48 ms

La taille finale de la liste fait 50 (ce qui est normal) Le temps d exécution est plus petit en raison de cette diminution de la taille. Le résultat est à présent correct.

Cette méthode ne fonctionnerait pas avec une liste issue d'un flux où d'un fichier de plusieurs Go. Elle ne pourrait pas tenir en mémoire centrale.

Il faut dissocier la recherche des deux éléments les plus élevés et l'alimentation au fils de l'eau.

Pour la recherche du 2eme élément, le tri de toute la collection est inutile: on ne désire que le premier et le deuxième élément. La connaissance du premier élément ne sert qu'à ordonner le deuxième (celui qui vient juste après le premier).

%%time
unmax = 0
deuxmax = 0
for i in randomlist:
    if i > unmax:
        deuxmax = unmax
        unmax = i
    else:
        if i > deuxmax and i < unmax:
            deuxmax =i
            
print(deuxmax)        

49
Wall time: 73.5 ms

Ici, on va parcourir la liste sans la trier, juste sélectionner les deux plus fortes valeurs.

Le temps d'exécution donnée par %%time dans jupyter est plus important que le tri sur la liste sans doublon mais plus rapide que le tri complet de la liste.

A présent on peut s'attaquer au problème de l'alimentation à la volée de ce filtre, à partir par exemple de la lecture d'un fichier.

Nous allons tout d abord fabriquer un fichier de nombre à partir d'une compréhension de liste.

maliste = [ random.randint(1,50) for i in range(10000000)]
with open('grosfichier.txt', 'a') as the_file:
    for i in maliste:
        the_file.write(f"{i}\n")
        

Puis on va lire le fichier et le filtrer à la volée.

%%time
unmax = 0
deuxmax = 0
with open('grosfichier.txt', 'r')  as file:
    for ligne in file:
        i = int(ligne[:-1])
        if i > unmax:
            deuxmax = unmax
            unmax = i
    else:
        if i > deuxmax and i < unmax:
            deuxmax =i
print(deuxmax)


49
Wall time: 3.65 s
        

Et voila, traitement sera plus long du fait de la lecture du fichier mais le filtre sera capable de traiter plusieurs giga de données sans risque de saturer la mémoire.

Good hacking ! with http://hilite.me/ pour la mise en forme du code

Guide de survie pour pandas et Numpy

 

Les librairies Pandas et Numpy sont deux piliers de l’outillage Python pour l’apprentissage automatique. Aussi faut-il connaitre quelques subtilités pour éviter de perdre du temps à la recherche d’erreur.

 Par expérience, je réserve l’utilisation de Pandas au chargement des données et à leur transformation pour ensuite les exporter vers les frameworks comme Tensorflow ou Pytorch.

La phase d’export d’une colonne vers un array Numpy doit s’accompagner d’une vérification des dimensions de l’export. Car Pandas l’exporte vers un tableau qui est à plutôt les caractéristiques d’une liste.

Exemple : Création d'un dataFrame et export vers Numpy d'une colonne.

 

Une dimension unique comme (3,) est le propre d’une série au sens Dataframe ou d’un type liste en Python : ce n’est pas une vrai matrice (array) Numpy.

Dans numpy on peut repérer 3 structures particulières :

Les listes

La matrice sur 1 seule ligne mais bien de dimension 2

La matrice d’une colonne mais bien de dimension 2 (un vecteur)

Il est possible de passer d’une structure à une autre par une opération de ‘reshape’

 Illustration ci-dessous:

Une structure a 1 dimension peut provoquer des erreurs dans des fonctions d'apprentissage automatique et surtout être la cause d'erreur de broadcasting.

Le broadcasting dans numpy.

C'est un mécanisme puissant mais qui peut provoquer des erreurs en cascade.

Les opérations  entre matrice imposent de respecter des contraintes sur les dimensions des matrices:

Le broadcasting permet des opérations hybrides à mi chemin entre les opérations  entre des matrices ou des opérations avec des scalaires.

Exemple : création de 3 matrices: une de 3X3 , une de 1X3 et enfin une de 3X1:

Si on réalise la multiplication scalaire de la matrice a par le 'scalaire' 2 on obtiendra: 

Que ce passe-t-il si je souhaite multiplier la matrice a (3X3) par b (1X3) ? Comme on pourrait le faire avec un scalaire ?  Cette opération hybride n'est pas autorisée et c'est là qu'intervient le broadcasting. Numpy va étendre sous certaines conditions les matrices. 

Les conditions sont les suivantes:

• Dimensions identiques
• Une des deux dimensions est égale à 1 

 

Numpy va prendre la ligne de la matrice b et la dupliquer vers le bas afin d'avoir une matrice 3X3.

 

Erreurs de broadcasting.

Prenons maintenant un cas qui va générer des erreurs en cascade.

Soit deux matrice de dimension 5X1 

Leur multiplication 'scalaire' va donner une matrice 5X1

 Si on prend la matrice 'c' qui n'a qu'une seule dimension: le résultat sera différent : une matrice de 5X5

Ainsi la règle d'or est de toujours vérifier la forme de la matrice (shape) avant une opération.

 

Régression linéaire avec Pytorch (deep learning)

 Après  avoir exposé différentes manières de mettre en œuvre des ajustements par régressions linéaires en Python, je terminerai par le framework de l'apprentissage automatique ou profond Python. Pytorch est soutenu par facebook. Son approche est différente que celle de Keras/Tensorflow , elle se veut plus programmatique et moins 'boite noire'.

Comme dans les autres billets, je vais commencer par préparer Jupyter pour Pytorch.

Les opérations sont les mêmes que pour tensorflow.

• Création d'un environnement virtuel Python (voir billet )
•  Ajout d'un noyau à Jupyter

Installation de Pytoch 

Il suffit de sélectionner  les bonnes options sur la grille et en retour , il vous générera la ligne de commande pour PIP

Apres l'installation il suffira d'ajouter un noyau Pytorch à Jupyter (voir billet).

Sur mon PC cela donne: 

Premier essai de résolution de regression linéaire avec Pytorch

En reprenant le même jeu de donnée que dans les billets précédents:

import torch
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from torch.autograd import Variable
class linearRegression(torch.nn.Module):
    def __init__(self, inputSize, outputSize):
        super(linearRegression, self).__init__()
        self.linear = torch.nn.Linear(inputSize, outputSize)

    def forward(self, x):
        out = self.linear(x)
        return out

On importe les modules de base.

Et on déclare une classe qui doit fournir l'initialisation d'une classe de regression linéaire et comment propager le modèle.

Après initialisation des variables (nombre de tenseur) 

inputDim = 1        # takes variable 'x' 
outputDim = 1       # takes variable 'y'
learningRate = 0.01 
epochs = 150

model = linearRegression(inputDim, outputDim)
criterion = torch.nn.MSELoss() 
optimizer = torch.optim.SGD(model.parameters(), lr=learningRate)

Il faut définir comment le modèle va évaluer l'ecart (loss function)  et comment arriver à un optimum.

On revient ensuite à une recherche de solution conventionnelle dans une boucle:

history = []

for epoch in range(epochs):
    # Converting inputs and labels to Variable
    inputs = Variable(torch.from_numpy(X_train))
    labels = Variable(torch.from_numpy(y_train))
    # Clear gradient buffers because we don't want any gradient from previous epoch to carry forward, dont want to cummulate gradients
    optimizer.zero_grad()

    # get output from the model, given the inputs
    outputs = model(inputs)

    # get loss for the predicted output
    loss = criterion(outputs, labels)
   # print(loss.item())
    history.append(loss.item())
    # get gradients w.r.t to parameters
    loss.backward()

    # update parameters
    optimizer.step()
   
   # print('epoch {}, loss {}'.format(epoch, loss.item()))
[w, b] = model.parameters()
print(w)
print(b)
print('intercept :' ,0 - model.linear.bias.data.numpy()[0])
print('slope :' , model.linear.weight.data.numpy()[0][0])

Il est possible de visualiser l'évolution de la fonction de perte : 

Avec un résultat final semblable à nos autres méthodes : 

Il est possible d'obtenir des évaluations: 

ww = -model.linear.bias.data.numpy()[0]
with torch.no_grad(): # we don't need gradients in the testing phase
    v =  torch.tensor([3.5])
    w = torch.tensor([7.0])
    orig = torch.tensor([ww ])
    test1 = model(v) 
    test2 = model(w)
    test3 = model(orig)
print(test1*10000,test2*10000, test3 * 10000)    

A noter qu'il n'a pas été nécessaire de normaliser ou de remettre à l'échelle des données. 

Pytorch propose un mix entre tensorflow (apprentissage profond) et l'approche en apprentissage automatique.

Le notebook est disponible ici sur github 

Les sites consultés et sources sont:

https://www.kaggle.com/aakashns/pytorch-basics-linear-regression-from-scratch

et

https://towardsdatascience.com/linear-regression-with-pytorch-eb6dedead817

Régression linéaire en deep learning avec Keras et tensorflow

Dans des billets précédents, j'avais montré différentes manières de trouver une droite qui s'ajuste au mieux à une série de point. essayons maintenant avec de l'apprentissage profond. Les données seront les mêmes.

L'environnement d 'exécution est un notebook sous Jupyter (voir ici sa préparation) .

Un réseau simple.

Pour monter notre dispositif nous avons besoin de:

• Un réseau avec des couches et des fonctions d'activation
• Une fonction d'évaluation de coût (ou de perte) 
• Un optimiseur :dispositif qui met à jour les paramètres afin d'atteindre une solution optimum

Et en option

• Un indicateur de performance à surveiller

Le réseau sera très simple pour un premier essai: une couche en entrée et une en sortie: (utilisation de http://hilite.me/)

model = Sequential()
model.add(Dense(1, input_dim= 1, kernel_initializer =initializers.RandomNormal(seed= 1), activation='linear'))
model.add(Dense(1, input_dim= 1, kernel_initializer =initializers.random_normal(seed= 1)))
model.compile(loss="mean_squared_error", optimizer ='sgd')

Ici , l'optimisateur est  de  type SGD  "Gradient descent (with momentum) optimizer".

Une préparation des données.

Ici, pas question d'utiliser des données brutes. Il est nécessaire de les mettre à l'echelle ou de les normaliser. 

Ci dessous la fonction de normalisation :

def normalise(dataf):
    mu    = 0
    sigma = 0
    mu = dataf.mean()
    sigma = dataf.std( ddof=0)
    snorm = dataf
    snorm.columns = ['normalised']
    snorm =(snorm - mu )/ sigma
    dtnorm = pd.concat([dataf,snorm],  axis =1)
    dtnorm.columns = ['x', 'nx']
    print(mu, sigma)
    print(snorm.head(5))
    return dtnorm , mu , sigma

Lancement.

Pour l'exécution, on peut jouer sur deux paramètres: le nombre cycle d'apprentissage (epochs) et la taille de chaque lot de donnée (batch size) 

Si on fixe à 10 la taille des lots pour un jeu de 100 données, il faut 10 passages pour faire un cycle complet(epochs) 

history =model.fit(X,y, epochs =  epoch,  batch_size = bz,verbose  = 0)

Résultats.

J'ai essayé avec 10 cycles et des tailles de lot différentes (taille totale = 97 lignes)

les résultats sont les suivants:

Les 3 premières tailles sont les plus rapides à converger: 

Passons maintenant aux estimations  pour les 2 valeurs : 3500 et 70000

(voir le billet sur la régression linéaire en apprentissage automatique)

pour une taille de 1
écart de

[1952.696]  
[3562.5508]
pour une taille de 10
écart de
[1271.1694]

[1076.8672]

pour une taille de 15

écart de
[589.0293]
[125.20703]

Une taille de 15 semble la bonne valeur, elle correspond à une proportion de 10 à 20% de la taille totale des données d'apprentissage.

Explication des écarts: on a utilisé une fonction qui normalise les données et qui va avoir une action d'écrasement des données. Une mise à l'échelle aurait été peut être plus fidèle.

Recommandation: pour faire plusieurs essais, il est nécessaire de redémarrer le noyau Jupyter. Tensorflow stocke des résultats en cache et cela peut avoir un impact. Pour ma part, je stocke les résultats intermédiaires dans un fichier python (pickle).

Les deux notebook  (réseau et affichage des résultats) sont sur github .

• Reseau
• affiche_resultat

Jupyter pour le deep learning

 A l'occasion de la sortie en Français du livre de François Chollet: 

J'ai préparé mon environnement pour utiliser Keras et Tensorflow dans un notebook Jupyter.

Le prérequis est d'avoir les notebook Jupyter installés.

Création d'un environnement Python spécifique à Keras et Tensorflow.

Utiliser le module Python natif venv  pour créer un espace propre à vos programmes et  librairies Python.

python -m venv --system-site-packages <env_a_creer>

Activer l'environnement virtuel par la commande suivante exécutée depuis le répertoire crée: 

source bin/activate

Installer dans cet environnement Keras et Tensorflow avec la commande 'pip'

(suivre les instruction du site Tensorflow)

Vérifier la bonne installation par une tentative d'import de keras depuis l'invite python (exemple)

from keras.models import Sequential

Vérifier le fichier de configuration keras.json situé sous le répertoire '.keras' du répertoire de l'utilisateur.

Ce fichier renseigne sur le backend à utiliser : ici tensorflow.

Installer un nouveau noyau  (kernel) à Jupyter.

Toujours depuis votre répertoire <venv>, lancer la commande:

python -m ipykernel install --user --name=<venv> --display-name 'keras'

 Pour vérifier les kernels installés :

jupyter kernelspec list

Le kernel ajouté doit figurer dans la liste.

Pour le supprimer: 

jupyter kernelspec remove <venv>

Pour tester:

Lancer Jupyter et vérifier la presence d'un kernel supplémentaire (ici keras)

Puis tester l'import des librairies Keras

 Accéder à distance à l'instance Jupyter.

option utile  comme dans mon cas où Jupyter est installé sur un ultramini-portable  

Lancer Jupyter sur le mini-portable: 

 jupyter notebook --ip=0.0.0.0 --NotebookApp.token=''

L'option 'ip' permet de demander à Jupyter d'écouter sur toutes les interfaces réseaux.

La dernière option évite d'avoir à rentrer un token à rallonge dans le navigateur distant.

Il suffit alors de faire pointer son navigateur distant sur http://192.168.1.xx:8888/

Mon ultramini-portable Chuwi: grand comme ma main mais très puissant. 

En bonus: changer l'aspect de Jupyter

Dans le répertoire  .jupyter de l'utilisateur 

Créer l'arborescence suivante: 

/home/<user>/.jupyter/custom

Puis éditer un nouveau fichier custom.css

Le mien contient les lignes suivantes:

egerman@egerman-MiniBook:~/.jupyter/custom$ cat custom.css
#ipython_notebook::before{
 content:"Jupyter sur Chuwi"
}
#ipython_notebook img{
 display:none;
}
body > #header {
    background: #78abd2;
}
div.cell {
    transition: all 0.25s;
    border: none;
    position: relative;
    top: 0;
}
div.cell.selected, div.cell.selected.jupyter-soft-selected {
    border: none;
    background: transparent;
    box-shadow: 0 6px 18px #aaa;
    z-index: 10;
    top: -10px;
}

Avec comme résultat: 

• Un titre personnalisé
• Un mise en avant de la cellule active
  
  
  

Régression linéaire en Python : 3 méthodes

 La régression linéaire est un des piliers du machine learning.

Je vais présenter 3 méthodes pour trouver l'équation de la droite qui résume au plus près un nuage de point..

Le chargement des données. 

Les données sont issues d'un jeu de donnée des valeurs foncières en opendata (disponible sur github) . 

Les données seront chargées dans un dataframe de Pandas.

import pandas as pd
data = pd.read_csv('parcelles_ext.csv', sep=';')
import numpy as np

data.replace('None',np.nan , inplace = True )
data2 = data[['valeur_fonciere','surface_reelle_bati','adresse_code_voie', 'nombre_pieces_principales']]
data2 = data2.dropna()
y= data2['valeur_fonciere'].to_numpy()
X=data2['surface_reelle_bati'].to_numpy()
X = np.reshape(X,(-1,1))
y = np.reshape(y,(-1,1))


Seules deux colonnes seront utilisées.

Méthode par un batch de descente en gradient.

Deux fonctions sont nécessaires: une qui calcule le 'coût' (l'erreur)  et une autre qui va répéter autant de fois que necessaire le calcul de cout puis le gradient et va se rapprocher petit à petit du minimum de la fonction de coût.

def  cost_function(theta,X,y):   
    m = len(y)
    predictions = X.dot(theta)
    cost = (1/2*m) * np.sum(np.square(predictions-y))
    return cost

Le batch

def gradient_descent(X,y,theta, alpha=0.01,iterations=100):
    m = len(y)
    cost_history = np.zeros(iterations)
    theta_history = np.zeros((iterations,2))
    for it in range(iterations):   
        prediction = np.dot(X,theta)
        theta = theta -(1/m)*alpha*( X.T.dot(prediction - y))
        theta_history[it,:] =theta.T
        cost_history[it]  = cost_function(theta,X,y)     
    return theta, cost_history, theta_history

Pour maintenant activer le batch , on a besoin d'ajouter une colonne  'biais' aux données en entrée.

Et de choisir un taux d'apprentissage et un nombre d'itération.

lr =0.0001
n_iter = 100000*8
theta = np.random.randn(2,1)
initial_theta = theta
X_b = np.c_[np.ones((len(X),1)),X]

Le 'alpha' (learn rate) est ici très bas et le nombre d'itération très élevés.

La raison principale est l'ordre de grandeur des données: 

 [  1. 113.]
 [  1.  91.]
 [  1.  61.]
 [  1. 150.]]

113 , 150 etc , les données ne sont pas à l'echelle (voir la suite) mais on arrive à un résultat.

Méthode par une fonction de recherche de minimum.

au lieu de devoir faire un batch à la main, il est possible d'utiliser une fonction intégrée qui va se charger de trouver le minimum d'une fonction en optimisant les itérations par l'emploi de transformation. 

On va individualiser la fonction gradient:

def gradient(theta,X,y):
    #print(X.shape)
    #print(theta.shape)
    prediction = np.dot(X,theta)
    t_gradient = 1/len(y)*(X.T.dot(prediction-y))
    return t_gradient

Et appeler la fonction de recherche de minimum (fmin_tnc de scipy) en lui passant le nom des fonctions de cout et de gradient.

Les deux méthodes arrivent à des résultats comparables.

Méthode par l'équation  normale.

Il est possible de trouver directement l'équation de la droite normale mais avec un niveau de complexité qui explose avec le nombre de donnée.

 

A retenir : toujours normaliser ou mettre à l'echelle les données. 

On peut utiliser des méthodes intégrées:

ou le faire à la main:

L'avantage est d'avoir en retour les valeurs de mu et sigma pour l'appliquer aux prévisions.

Le learn rate et le  nombre d'itération  seront moins extrêmes.

Le code est sous forme de notebook pour jupyter à retrouver sur mon github.

Régression logistique en Python : cours du professeur ng Andrew

Dans l'article précédent  (lien ici), je traduisais en Python le premier TP de la formation Machine learning de ng Andrew. Le TP introduisait les problèmes de régression linéaire. 

La deuxième semaine avait comme  objectif de présenter la régression logistique.

Cette notion est un prolongement de la régression linéaire. Le résultat est une probabilité qui permet de dresser une ligne de démarcation (deux clusters) entre 2 régions : oui ou non. Le jeu de données propose les notes d'examen pour  2 épreuves et le résultat de l'admission finale.

Il est demandé de tracer une droite qui partage au mieux les étudiants reçus et les recalés. 

Le gros point bleu en haut à droite est la visualisation de la probabilité estimée pour un cas de test.

	x1_test =45
	x2_test = 85
	plt.scatter(x1_test, x2_test, c = 'lightblue', s = 400 )
	plt.pause(40)
	plt.show(block=False)
	propa = thc[0] + thc[1] * 45 + thc[2] * 85
	#print(propa)
	print('estimation probabilite recu 45 ep1 et 85 ep2:',sigmoid(propa))

On utilise les principes de la régression linéaire pour ensuite appliquer une fonction (sigmoïde) qui ventile les résultats entre la valeur 0 et 1.

Autant pour le TP1 il était possible d'effectuer la descente en gradient par itération en étant sur de converger vers un résultat, dans ce cas de figure,  il  est nécessaire de faire appel à une fonction de calcul de minima.  

Avec octave ça donne ceci:

%  Run fminunc to obtain the optimal theta
%  This function will return theta and the cost 
[theta, cost] = ...
	fminunc(@(t)(costFunction(t, X, y)), initial_theta, options);

Avec Python , j'utilise  la fonction fmin_tnc de scipy

from scipy.optimize import fmin_tnc

Cette fonction à la signature suivante:

scipy.optimize.fmin_tnc(func, x0, fprime=None, args=(), approx_grad=0, bounds=None, epsilon=1e-08, scale=None, offset=None, messages=15, maxCGit=- 1, maxfun=None, eta=- 1, stepmx=0, accuracy=0, fmin=0, ftol=- 1, xtol=- 1, pgtol=- 1, rescale=- 1, disp=None, callback=None)
Minimize a function with variables subject to bounds, using gradient information in a truncated Newton algorithm. This method wraps a C implementation of the algorithm.

D'une manière  simple, il faut lui fournir la fonction de coût à minimiser, la fonction de gradient, les jeux de données et les résultats attendus.

essai = fmin_tnc(func = costFunction2, x0 = initial_theta.flatten(), fprime = None , args = (XX , yy.flatten() ) )

Le code est disponible ici.

J'ai ajouté le calcul de la matrice de confusion importé de la librairie sklearn:

	from sklearn.metrics import confusion_matrix confusion = confusion_matrix(pr,cible,[0,1])
	print('matrice de confusion',confusion)
	total = np.sum(confusion)
	prec = (confusion[0][0] + confusion[1][1]) / total
	effic = confusion[1][1]/np.sum(confusion, axis = 0)[1]
	print('precision',prec)
	print('pertinence', effic)

;

Le code n'est pas fameux en raison des contraintes sur le format des paramètres en entrée. C'est cette partie qu'il faudra améliorer.