## 1

from random import *
from math import *
from matplotlib.pyplot import *

def distance(p1,p2):
    d = len(p1)
    s = 0
    for k in range(d):
        s += (p1[k] - p2[k])**2
    return sqrt(s)

def liste_voisins(p,k,L):
    def f(p2):
        return distance(p,p2[0])
    return sorted(L, key=f)[:k]

def etiquette_maj(V):
    D = {}
    for (_,e) in V:
        if e in D:
            D[e] += 1
        else:
            D[e] = 1
    max_occ = 0
    for e in D:
        if D[e] > max_occ:
            e_maj = e
            max_occ = D[e]
    return e_maj

def knn(p,k,L):
    V = liste_voisins(p,k,L)
    return etiquette_maj(V)

##2

from sklearn.datasets import load_digits

digits = load_digits()
X = digits.data
Y = digits.target

# Construction de la liste de points annotés
L = []
n = len(X)
for i in range(n):
    L.append((X[i], Y[i]))

shuffle(L)

n = len(L)
n_train = int(0.8 * n)

Ltrain = L[:n_train]
Ltest  = L[n_train:]

def taux_erreur(k, Ltrain, Ltest):
    erreurs = 0
    for (p,e) in Ltest:
        ep = knn(p, k, Ltrain)
        if ep != e:
            erreurs += 1
    return erreurs / len(Ltest)

for k in range(1,16):
    print("k =", k, " taux d'erreur =", taux_erreur(k, Ltrain, Ltest))

def matrice_confusion(k, Ltrain, Ltest):
    M = []
    for i in range(10):
        M.append([0]*10)

    for (p,e) in Ltest:
        ep = knn(p, k, Ltrain)
        M[e][ep] += 1

    return M

for k in range(1,16):
    print("\nk =", k)
    print("Taux d'erreur :", taux_erreur(k, Ltrain, Ltest))
    M = matrice_confusion(k, Ltrain, Ltest)
    for ligne in M:
        print(ligne)

def erreur_absolue(k, Ltrain, Ltest):
    s = 0
    for (p,e) in Ltest:
        ep = knn(p, k, Ltrain)
        s += abs(e - ep)
    return s

for k in range(1,16):
    print("k =", k, " somme |ec - ep| =", erreur_absolue(k, Ltrain, Ltest))

##3

img = imread("chiffre.png")

imshow(img, cmap="gray")
show()

# Conversion au bon format
p = []
for i in range(8):
    ligne = []
    for j in range(8):
        x = img[i][j][0]      # passage en niveaux de gris
        x = 1 - x             # inversion
        x = 16 * x            # mise à l'échelle
        p.append(x)


print("Chiffre prédit :", knn(p, 5, Ltrain))

##4

def inserer(p,p2,V):
    if V == []:
        V.append(p2)
        return
    pfin = V[-1]
    if distance(p,pfin[0]) <= distance(p,p2[0]):
        V.append(p2)
    else:
        V.pop()
        inserer(p,p2,V)
        V.append(pfin)




def liste_voisins(p,k,L):
    V = []
    for i in range(k):
        inserer(p,L[i], V)
    for i in range(k,len(L)):
        inserer(p,L[i],V)
        V.pop()
    return V

#Cette version est en O(kn), la version précédente était en O(n ln n)

def etiquette_ponderee(p, V):
    D = {}
    for (p2,e) in V:
        d = distance(p,p2)
        if d != 0:
            w = 1/d
        else:
            w = 1000000
        if e in D:
            D[e] += w
        else:
            D[e] = w

    max_val = 0
    for e in D:
        if D[e] > max_val:
            e_maj = e
            max_val = D[e]
    return e_maj

def knn_pondere(p,k,L):
    V = liste_voisins(p,k,L)
    return etiquette_ponderee(p,V)