#<GRADED>
import numpy as np
import sys
import matplotlib
matplotlib.use('PDF')
import matplotlib.pyplot as plt
from scipy.io import loadmat
import time
from sklearn.model_selection import train_test_split
from sklearn.metrics import zero_one_loss
import scipy.stats as stats
from collections import defaultdict
import random
#</GRADED>

%matplotlib inline

print('You\'re running python %s' % sys.version.split(' ')[0])

def loaddata(filename):
    """
    Returns xTr,yTr,xTe,yTe
    xTr, xTe are in the form nxd
    yTr, yTe are in the form nx1
    """
    data = loadmat(filename)
    xTr = data["xTr"]; # load in Training data
    yTr = np.round(data["yTr"]); # load in Training labels
    xTe = data["xTe"]; # load in Testing data
    yTe = np.round(data["yTe"]); # load in Testing labels
    return xTr.T,yTr.T,xTe.T,yTe.T

xTr,yTr,xTe,yTe=loaddata("faces.mat")

def plotfaces(X, xdim=38, ydim=31, ):
    n, d = X.shape
    f, axarr = plt.subplots(1, n, sharey=True)
    f.set_figwidth(10 * n)
    f.set_figheight(n)
    
    if n > 1:
        for i in range(n):
            axarr[i].imshow(X[i, :].reshape(ydim, xdim).T, cmap=plt.cm.binary_r)
    else:
        axarr.imshow(X[0, :].reshape(ydim, xdim).T, cmap=plt.cm.binary_r)
plotfaces(xTr[:10, :])

#<GRADED>
def innerproduct(X,Z=None):
    # function innerproduct(X,Z)
    #
    # Computes the inner-product matrix.
    # Syntax:
    # D=innerproduct(X,Z)
    # Input:
    # X: nxd data matrix with n vectors (rows) of dimensionality d
    # Z: mxd data matrix with m vectors (rows) of dimensionality d
    #
    # Output:
    # Matrix G of size nxm
    # G[i,j] is the inner-product between vectors X[i,:] and Z[j,:]
    #
    # call with only one input:
    # innerproduct(X)=innerproduct(X,X)
    #
    if Z is None: # case when there is only one input (X)
        G = np.dot(X, X.transpose())
    else:  # case when there are two inputs (X,Z)
        Z = Z.transpose()
        if X.shape[1] != Z.shape[0]:
            raise ValueError("Invalid Matricies")
        G = np.dot(X, Z)
    return G

def l2distance(X,Z=None):
    # function D=l2distance(X,Z)
    #
    # Computes the Euclidean distance matrix.
    # Syntax:
    # D=l2distance(X,Z)
    # Input:
    # X: nxd data matrix with n vectors (rows) of dimensionality d
    # Z: mxd data matrix with m vectors (rows) of dimensionality d
    #
    # Output:
    # Matrix D of size nxm
    # D(i,j) is the Euclidean distance of X(i,:) and Z(j,:)
    #
    # call with only one input:
    # l2distance(X)=l2distance(X,X)
    #

    if Z is None:
        return l2distance(X, X)
    else:  # case when there are two inputs (X,Z)
        S = (X*X).sum(axis=1).reshape(-1, 1)
        R = (Z*Z).sum(axis=1)
        G = innerproduct(X, Z)
        D_2 = S -2*G + R
        # print(D[D < 0])
        if X is Z:
            np.fill_diagonal(D_2, 0.0)
        D_2 =  np.sqrt(D_2)
        return D_2
#</GRADED>

eu_dist_matrix = l2distance(xTr, xTe)

xTr.shape

xTe.shape

eu_dist_matrix.shape

def old_findknn(xTr,xTe,k):
    """
    function [indices,dists]=findknn(xTr,xTe,k);
    
    Finds the k nearest neighbors of xTe in xTr.
    
    Input:
    xTr = nxd input matrix with n row-vectors of dimensionality d
    xTe = mxd input matrix with m row-vectors of dimensionality d
    k = number of nearest neighbors to be found
    
    Output:
    indices = kxm matrix, where indices(i,j) is the i^th nearest neighbor of xTe(j,:)
    dists = Euclidean distances to the respective nearest neighbors
    """
    
    eu_dist_matrix = l2distance(xTr, xTe)
    
    
    min_matrix = list()
    index_matrix = list()
    for point in eu_dist_matrix.T: # Transpose here to loop over the **Test** point distances rather than tr
        #Each test point
        index_list = list()
        min_list = list()
        point = list(point)
        for i in range(len(point)):
            #Each distance for the test point
            if k == 0:
                continue
            if len(min_list) < k:
                min_list.append(point[i])
                if len(min_list) is k:
                    min_list.sort()
            else:
                try:
                    if point[i] < min_list[k - 1]:
                        min_list[k - 1] = point[i]
                        min_list.sort()
                except IndexError:
                    print("Index at: " + str(i))
                    print("K is " + str(k))
                    print("Point shape: " + str(len(point)))
                    print("min_list shape: " + str(len(min_list)))
                    raise IndexError("Ooops")
        for num in min_list:
            index_list.append(point.index(num))
        min_matrix.append(min_list)
        index_matrix.append(index_list)
    
    return np.asarray(index_matrix).T, np.asarray(min_matrix).T

a = np.array([1,4,2,3,1,4,5,3]).reshape(2,4)
idx = np.array([1,3])
a[1,(idx)]

#<GRADED>
def findknn(xTr, xTe, k):
    """
    function [indices,dists]=findknn(xTr,xTe,k);
    
    Finds the k nearest neighbors of xTe in xTr.
    
    Input:
    xTr = nxd input matrix with n row-vectors of dimensionality d
    xTe = mxd input matrix with m row-vectors of dimensionality d
    k = number of nearest neighbors to be found
    
    Output:
    indices = kxm matrix, where indices(i,j) is the i^th nearest neighbor of xTe(j,:)
    dists = Euclidean distances to the respective nearest neighbors
    """
    
    dists = l2distance(xTr, xTe).T # Transpose here to loop over the **Test** point distances rather than tr

    min_matrix = np.zeros((k, xTe.shape[0])) # init as 0s
    index_matrix = np.zeros((k, xTe.shape[0]), dtype=int) # needs to be int for slicing below! defaults to float
    
    if k > 0:
        for i in range(len(dists)): 
            index_matrix[:,i] = dists[i].argsort()[:k] # find idxs of smallests dists
            min_matrix[:,i] = dists[i,(index_matrix[:,i])] # find corresponding dists

    return index_matrix, min_matrix
#</GRADED>

def opt_findknn(xTr, xTe, k):
    """
    function [indices,dists]=findknn(xTr,xTe,k);
    
    Finds the k nearest neighbors of xTe in xTr.
    
    Input:
    xTr = nxd input matrix with n row-vectors of dimensionality d
    xTe = mxd input matrix with m row-vectors of dimensionality d
    k = number of nearest neighbors to be found
    
    Output:
    indices = kxm matrix, where indices(i,j) is the i^th nearest neighbor of xTe(j,:)
    dists = Euclidean distances to the respective nearest neighbors
    """
    
    dists = l2distance(xTr, xTe)

    min_matrix = np.zeros((k, xTe.shape[0])) # init as 0s
    index_matrix = np.zeros((k, xTe.shape[0]), dtype=int) # needs to be int for slicing below! defaults to float
    
    if k > 0:
        index_matrix = np.argsort
        
        for i in range(len(dists)): 
            index_matrix[:,i] = dists[i].argsort()[:k] # find idxs of smallests dists
            min_matrix[:,i] = dists[i,(index_matrix[:,i])] # find corresponding dists

    return index_matrix, min_matrix

a = np.array([1,8,93,4,5,6,5,4,45,12,3,0]).reshape(3,4)
a

a.argsort(axis=0)

tuple(a.argsort(axis=0))

a.take(a.argsort(axis=0))

np.take(a,tuple(a.argsort(axis=0)), axis=1)

np.where?

np.take(a,a.argsort(axis=0), axis=1)

np.take?

who = 4
k = 10
indices, dists = findknn(xTr,np.array(xTe[who,:], ndmin=2), k)
print (dists.shape)
print(indices.shape)

plotfaces(xTe[who,:].reshape(1,-1))

plotfaces(xTr[indices[:,0], :])

def old_analyze(kind,truth,preds):
    """
    function output=analyze(kind,truth,preds)         
    Analyses the accuracy of a prediction
    Input:
    kind='acc' classification error
    kind='abs' absolute loss
    (other values of 'kind' will follow later)
    """
    
    truth = truth.flatten()
    preds = preds.flatten()
    
    if len(truth) > len(preds):
        truth = truth[:len(preds)] 
    else:
        preds = preds[:len(truth)]
    
    if kind == 'abs':
        # compute the absolute difference between truth and predictions
        loss = int()
        for i in range(len(truth)):
            if preds[i] != truth[i]:
                loss += abs(truth[i] - preds[i])
    elif kind == 'acc':
        loss = int()
        for i in range(len(truth)):
            if truth[i] != preds[i]:
                loss +=1
        truthScore = zero_one_loss(truth, preds)
        if truthScore != (loss/len(truth)):
            raise Exception("True: " + str(truthScore) + " Ours: " + str(loss/len(truth)))
    return loss/len(truth)

#<GRADED>
def analyze(kind,truth,preds):
    """
    function output=analyze(kind,truth,preds)         
    Analyzes the accuracy of a prediction
    Input:
    kind='acc' classification error
    kind='abs' absolute loss
    (other values of 'kind' will follow later)
    """
    #this function only operates under the assumption that truth and preds are numpy arrays
    
    try:
        truth = truth.flatten()
        preds = preds.flatten()
    except:
        pass
    
    if len(truth) != len(preds):
        raise RuntimeError('len(trush) != len(preds)')
    
    if kind == 'abs':
        # compute the absolute difference between truth and predictions
        a = float(np.abs(truth - preds).sum())
    elif kind == 'acc':
        a = float(np.equal(truth, preds).sum())
    else:
        raise ValueError('choose either "acc" or "abs" for kind')
    return a/float(len(truth))
#</GRADED>

a = np.array([1,2,3,4,3,5,6])
b = np.array([1,2,3,1,3,5,4])

idxs = np.argwhere(a == 3)
idxs.T[0]

np.power(a-b,2)

(~np.equal(a,b)).sum()

(~np.equal(a,b)).sum()/len(a)

#<GRADED>
def knnclassifier(xTr,yTr,xTe,k):
    """
    function preds=knnclassifier(xTr,yTr,xTe,k);
    
    k-nn classifier 
    
    Input:
    xTr = nxd input matrix with n row-vectors of dimensionality d
    xTe = mxd input matrix with m row-vectors of dimensionality d
    k = number of nearest neighbors to be found
    
    Output:
    
    preds = predicted labels, ie preds(i) is the predicted label of xTe(i,:)
    """
    yTr = np.asanyarray(yTr).flatten()
    xTr = np.asanyarray(xTr)
    xTe = np.asanyarray(xTe)
    indicies_matrix, dist_matrx = findknn(xTr, xTe, k)
    labels = np.zeros(indicies_matrix.shape)
    for i in range(len(indicies_matrix.T)):
        labels[:,i] = yTr[(indicies_matrix.T[i])].T
    preds = mode(labels)[0] # simple mode calc, if tie, takes least (maybe consider different k val in this case)
    
    return preds
#</GRADED>

#<GRADED>
def new_knnclassifier(xTr,yTr,xTe,k):
    """
    function preds=knnclassifier(xTr,yTr,xTe,k);
    
    k-nn classifier 
    
    Input:
    xTr = nxd input matrix with n row-vectors of dimensionality d
    xTe = mxd input matrix with m row-vectors of dimensionality d
    k = number of nearest neighbors to be found
    
    Output:
    
    preds = predicted labels, ie preds(i) is the predicted label of xTe(i,:)
    """
    indicies_matrix, dist_matrx = findknn(xTr, xTe, k)
    preds = np.zeros(indicies_matrix.shape[1])
    for i in range(len(indicies_matrix.T)):
        class_un = np.unique(yTr[(indicies_matrix.T[i])].T)
        labels = yTr[(indicies_matrix.T[i])].T 
        scores = np.zeros(class_un.shape[0])
        for j in range(class_un.shape[0]):
            idxs = np.argwhere(labels == class_un[j])[:,1]
            for idx in idxs:
                scores[j] += (1 / dist_matrx.T[i,idx]**2)
        preds[i] = class_un[np.argmax(scores)]
    return preds
#</GRADED>

# testing weighting system

indicies_matrix, dist_matrx = findknn(xTr, xTe, 10)
preds = np.zeros(indicies_matrix.shape[1])
for i in range(len(indicies_matrix.T)):
    class_un = np.unique(yTr[(indicies_matrix.T[i])].T)
    labels = yTr[(indicies_matrix.T[i])].T 
    scores = np.zeros(class_un.shape[0])
    for j in range(class_un.shape[0]):
        idxs = np.argwhere(labels == class_un[j])[:,1]
        for idx in idxs:
            scores[j] += (1 / dist_matrx.T[i,idx]**2)
    preds[i] = class_un[np.argmax(scores)]
        
preds_1 = preds

indicies_matrix, dist_matrx = findknn(xTr, xTe, k)
labels = np.zeros(indicies_matrix.shape)
for i in range(len(indicies_matrix.T)):
    labels[:,i] = yTr[(indicies_matrix.T[i])].T
preds = stats.mode(labels)[0][0] # simple mode calc, if tie, takes least (maybe consider different k val in this case)

wrong_new = 0
wrong_old = 0
for i in range(len(preds)):
    if preds_1[i] != yTe[i]:
        wrong_new +=1
    if preds[i] != yTe[i]:
        wrong_old +=1
print('wrong_new: ',wrong_new,', wrong_old: ',wrong_old)
    

indicies_matrix, dist_matrx = findknn(xTr, xTe, 10)
preds = np.zeros(indicies_matrix.shape[1])
for i in range(len(indicies_matrix.T)):
    class_un = np.unique(yTr[(indicies_matrix.T[i])].T)
    labels = yTr[(indicies_matrix.T[i])].T 
    scores = np.zeros(class_un.shape[0])
    for j in range(class_un.shape[0]):
        idxs = np.argwhere(labels == class_un[j])[:,1]
        for idx in idxs:
            scores[j] += (1 / dist_matrx.T[i,idx])
    preds[i] = class_un[np.argmax(scores)]
    
preds

a = np.array([1,45,5,4,5,5,4,3,2,1,1,1,1,1]).reshape(2,7)
b = np.random.randint(2,45,size=200)

def mode(a, axis=0):
    """
    Returns the mode/s (most frequent element/s) of a
    
    Note:
        - This mode function uses a quicksort, which may be inefficient for large arrays
        - Returns None if len(a) <= 0 

    Args:
        a: array_like
            will find the mode (most frequent element) of a
        axis: int
            if nxm array, axis for mode calculation
            defaults to 0

    Returns:
        m: float or array_like
            mode (most frequent element) of a
        frequency: float or array_like
            the frequency (number of occurrences) of the mode
    """
    a = np.asanyarray(a.copy())
    if a.shape[0] == a.size: # is 1xn or nx1
        if a.size == 0:
            return None
        else:
            max_freq = 1
            a.sort()
            m = a[0]
            curr_freq = 1
            for i in range(1, len(a)):
                if a[i] == a[i-1]:
                    curr_freq += 1
                if curr_freq > max_freq:
                    max_freq = curr_freq
                    m = a[i-1]
                if a[i] != a[i-1]:
                    curr_freq = 1
            return m, max_freq
    else: # nxm array
        if axis == 0:
            a = a.T
        l = len(a)
        m = np.zeros(l)
        f = np.zeros(l)
        for i in range(l):
            m[i], f[i] = mode(a[i])
        return m, f
                

def test_mode(a, axis=0):
    """
    Returns the mode/s (most frequent element/s) of a
    
    Note:
        - This mode function uses a quicksort, which may be inefficient for large arrays
        - Returns None if len(a) <= 0 

    Args:
        a: array_like
            will find the mode (most frequent element) of a
        axis: int
            if nxm array, axis for mode calculation
            defaults to 0

    Returns:
        m: float or array_like
            mode (most frequent element) of a
        frequency: float or array_like
            the frequency (number of occurrences) of the mode
    """
    a = np.asanyarray(a.copy())
    if a.shape[0] == a.size: # is 1xn or nx1
        if a.size == 0:
            return None
        else:
            print(a) ##================================Remove
            max_freq = 1
            a.sort()
            m = a[0]
            curr_freq = 1
            for i in range(1, len(a)):
                if a[i] == a[i-1]:
                    curr_freq += 1
                    print(curr_freq) ##================================Remove
                elif:
                    if curr_freq > max_freq:
                        max_freq = curr_freq
                        
                        m = a[i-1]
                    curr_freq = 1
            return m, max_freq
    else: # nxm array
        if axis == 0:
            a = a.T
        l = len(a)
        m = np.zeros(l)
        f = np.zeros(l)
        for i in range(l):
            m[i], f[i] = mode(a[i])
        return m, f
                

test_1 = np.random.randint(3,10,size=300).reshape(10,30)

test_1

myResult = mode(test_1)[0]
myResult

stats.mode(test_1)[0] == mode(test_1)[0]

scipy_result = stats.mode(test_1)

test_1[:,14]

np.zeros(4)
print(test_1.T[14])
print(mode(test_1.T[14].T))

stats.mode(a)

mode(a)[0]

mode(a)

a

a = np.array([1,2,3,4,3,4,3,2,3,2,1,3])
idx = np.array([1,2,1,3,1,3,3,4]).reshape(2,4)
b = a[(idx)]
b

stats.mode(b, axis=1)[0]

print("Face Recognition: (1-nn)")
xTr,yTr,xTe,yTe=loaddata("faces.mat") # load the data
t0 = time.time()
preds = knnclassifier(xTr,yTr,xTe,1)
result=analyze("acc",yTe,preds)
t1 = time.time()
print("You obtained %.2f%% classification acccuracy in %.4f seconds\n" % (result*100.0,t1-t0))

print("Handwritten digits Recognition: (3-nn)")
xTr,yTr,xTe,yTe=loaddata("digits.mat"); # load the data
t0 = time.time()
preds = knnclassifier(xTr,yTr,xTe,5)
result=analyze("acc",yTe,preds)
t1 = time.time()
print("You obtained %.2f%% classification acccuracy in %.4f seconds\n" % (result*100.0,t1-t0))

X_train, X_test, y_train, y_test = train_test_split(xTr, yTr, test_size=0.66, random_state=42)

def old_train_test_splitter(x_train, y_train, train_size = 0.66, prng_seed=42):
    x_train = np.asanyarray(x_train)
    y_train = np.asanyarray(y_train)
    n = len(x_train)
    indices = np.arange(0, n)
    
    np.random.seed(seed=prng_seed)
    np.random.shuffle(indices) # shuffles inplace

    x_train_shuff = x_train[(indices), :]
    y_train_shuff = y_train[(indices)]
    
    num_trains = int(n*train_size)
    
    x_train_new = x_train_shuff[:num_trains, :]
    x_test_new = x_train_shuff[num_trains:, :]
    y_train_new = y_train_shuff[:num_trains]
    y_test_new = y_train_shuff[num_trains:]
    
    return x_train_new, x_test_new, y_train_new, y_test_new

class train_test_splitter:
    
    def __init__(self, x_train, y_train):
        self.x = np.asanyarray(x_train)
        self.y = np.asanyarray(y_train.flatten())
        
        self.y_args = self.y.argsort()
        self.y_sorted = self.y[(self.y_args)]
        self.x_sorted = self.x[(self.y_args), :]
        
        self.data_dict = defaultdict(list)
        [self.data_dict[self.y_sorted[i]].append(self.x_sorted[i]) for i in range(len(self.x_sorted))]
        
    def get_sample(self, training_percent=0.33):
        shuffled_keys = list(self.data_dict.keys())
        random.shuffle(shuffled_keys)
        tr_shuffle_y = shuffled_keys[:int(len(shuffled_keys) * training_percent)]
        te_shuffle_y = shuffled_keys[int(len(shuffled_keys) * training_percent):]
        training_x = []
        training_y = []
        for key in tr_shuffle_y:
            training_x.extend(self.data_dict[key])
            training_y.extend([key] * len(self.data_dict[key]))
        test_x = []
        test_y = []
        for key in te_shuffle_y:
            test_x.extend(self.data_dict[key])
            test_y.extend([key] * len(self.data_dict[key]))
                
        #[training_x.extend(self.data_dict[key]) for key in training_y]
        #test_x = []
        #test_x.extend(self.data_dict[key]) for key in test_y]
        return np.asanyarray(training_x), np.asanyarray(training_y), np.asanyarray(test_x), np.asanyarray(test_y)
        

test_y = np.random.choice(self.data_dict.keys(), size=int(len(self.data_dict.keys())*self.test_percent), replace=False)
train_y = [y for y in data_dict.keys() if y not in test_y]

tt_split = train_test_splitter(c, c_labels)

tr_x, tr_y, te_x, te_y = tt_split.get_sample()
print(te_y)
print(tr_y)

c = np.random.randint(0,20,size=200).reshape(40,5)

c[:7,:]

d = {1:4, 3:5}

d.keys()

list(d.keys())

c_labels = np.random.randint(4,19, size=40)

np.c_labels

c[:2,:]

c[2:,:]

c_a = np.arange(0, len(c))

np.random.shuffle(c_a)

c_a

c[(c_a),:]

d = np.random.randint(1,4,size=4)
d

d[(c_a)]

#<GRADED>
def competition(xTr,yTr,xTe):
    """
    function preds=competition(xTr,yTr,xTe);
    
    A classifier that outputs predictions for the data set xTe based on 
    what it has learned from xTr,yTr
    
    Input:
    xTr = nxd input matrix with n column-vectors of dimensionality d
    xTe = mxd input matrix with n column-vectors of dimensionality d
    
    Output:
    
    preds = predicted labels, ie preds(i) is the predicted label of xTe(i,:)
    """
    #Split Test data into train and test
    X_train, X_test, y_train, y_test = train_test_splitter(xTr, yTr, train_size=0.66, prng_seed=42)
    
    #we can argmax on k evaluated by our loss percentage
    best_k = (0, 0)
    print(y_train)
    for k_curr in range(1, 40):
        preds = knnclassifier(X_train, y_train, X_test, k_curr)
        result = analyze("acc",y_test,preds)
        if result > best_k[1]:
            best_k = (k_curr, result)
    preds = knnclassifier(xTr, yTr, xTe, best_k[0])
    
    return preds
#</GRADED>

predictions = competition(xTr, yTr, xTe)

analyze(kind='acc', truth=yTe, preds=predictions)

def testing_tt_splitter(xTr,yTr,xTe, yTe):
    """
    function preds=competition(xTr,yTr,xTe);
    
    A classifier that outputs predictions for the data set xTe based on 
    what it has learned from xTr,yTr
    
    Input:
    xTr = nxd input matrix with n column-vectors of dimensionality d
    xTe = mxd input matrix with n column-vectors of dimensionality d
    
    Output:
    
    preds = predicted labels, ie preds(i) is the predicted label of xTe(i,:)
    """
    #Split Test data into train and test
    tt_splitter = train_test_splitter(xTr, yTr)
    
    X_train, y_train, X_test, y_test = tt_splitter.get_sample()
    
    #we can argmax on k evaluated by our loss percentage
    best_k = (0, 0)
    for k_curr in range(1, 40):
        preds = knnclassifier(X_train, y_train, X_test, k_curr)
        result = analyze("acc",y_test,preds)
        print()
        if result > best_k[1]:
            best_k = (k_curr, result)
    print(yTr.flatten())
    preds = knnclassifier(xTr, yTr.flatten(), xTe, best_k[0])
    
    
    pct_wrong = (~np.equal(preds, yTe)).sum() / float(len(preds))
    return pct_wrong