import numpy as np

def euclideanDist(x1, x2):
    # input x1 and x2 must be numpy arrays
    return np.sqrt(np.sum((x1-x2)**2))

# test the function
x1 = np.array([0, 0, 0])
x2 = np.array([1, 1, 1])
dist = euclideanDist(x1, x2)
dist

"""
Explanation: Implement K-nearest neighbors algorithm (KNN)
KNN is a nonparametric model for classification which doesn't learn a discriminative function from the training data but memorizes the training dataset instead. The model for kNN is the entire training dataset. When a prediction is required for a unseen data instance, the kNN algorithm will search through the training dataset for the k-most similar instances. The similarity measure is dependent on the type of data. For real-valued data, the Euclidean distance is usually used. Other other types of data such as categorical or binary data, Hamming distance can be used. If we are using a Euclidean distance measure, it is also important to standardize the data so that each feature contributes equally to the distance. In the case of regression problems, the average of the predicted attribute is returned. In classification, the most prevalent class is returned.
The main advantage of KNN is that the classifier immediately adapts as we collect new training data. A disadvantage of KNN is that it can be computationally expensive to repeat the same or similar searches over larger training datasets. It is very susceptible to overfitting due to the curse of dimensionality. In addition, storage space can become a challenge if we are working with large datasets.
The algorithm itself is straightforward and can be summarized by the following steps:
    1. Choose the number of k and a distance metric.
    2. Find the k nearest neighbors of the sample that we want to classify.
    3. Assign the class label by majority vote.
In this exercise, I will implement the KNN algorithm from scratch. The implementation will be will be demonstrated using the Iris flowers classification problem.
Define a function to calculate euclidean distance
End of explanation
"""


import operator

def knn(X_train, y_train, x, k):
    """calculating k nearest neighbors of a new point x, predict its label based on majority vote

    Parameters
    ----------
    X_train : array-like, shape = [n_samples, n_features]
        Training vectors, where n_samples is the number of samples and
        n_features is the number of features.
    y_train : array-like, shape = [n_samples]
        Target label
    x : 1-D array, shape = [1, n_feature]
        New point whose label is being assigned
    k : int, the number of neighbors used to determine the label of x

    Returns
    -------
    y : Target label for the new point x

    """
    # calculate distance between x and each sample in training data
    dists = np.array([euclideanDist(t, x) for t in X_train])
    # sort the dists array to find the index of k nearest samples
    sortedDist = np.argsort(dists)
    # count the number of vote for each label existing in the k samples using dictionary
    classVotes = {}
    for i in range(k):
        label = y_train[sortedDist[i]]
        classVotes[label] = classVotes.get(label, 0) + 1
        # the above line is equall to
        # if label in classVotes:
        #    classVotes[label] += 1
        # else:
            #classVotes[label] = 1
    # sort the dictionary classVotes by value and return the major vote
    sortedVotes = sorted(classVotes.items(), key=operator.itemgetter(1), reverse=True)
    return sortedVotes[0][0]


"""
Explanation: Implement knn algorithm
End of explanation
"""


# Load iris dataset from scikit-learn. 
from sklearn import datasets
from sklearn.model_selection import train_test_split

iris = datasets.load_iris()
X = iris.data
y = iris.target

# Splitting data into 70% training and 30% test data:
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=0)

# Test out with a single point in test set
y_pred = knn(X_train, y_train, X_test[0], k=2)
print ('y_pred = %s' % y_pred)
print ('y_true = %s' % y_test[0])

# Apply the knn algorithm to predict the labels of samples in the testset
y_pred = []
for x in X_test:
    y = knn(X_train, y_train, x, k=2)
    y_pred.append(y)

# write a function to calculate classification accuracy of prediction
def getAccuracy(y_pred, y_true):
    return np.sum([y_pred == y_true])/len(y_true)

# calculate classification accuracy on the testset
y_pred = np.array(y_pred)
accuracy = getAccuracy(y_pred, y_test)
print('Accuracy: %.2f' % (accuracy * 100) + '%')

"""
Explanation: Test the knn algorithm with iris dataset
End of explanation
"""


# sample code for standardization
from sklearn.preprocessing import StandardScaler
sc = StandardScaler()
sc.fit(X_train)
X_train_std = sc.transform(X_train)
X_test_std = sc.transform(X_test)

"""
Explanation: Ideas For Extensions


Regression: The knn algorithm can be adapted to work for regression problems (predicting a real-valued attribute). The summarization of the closest instances could involve taking the mean or the median of the predicted attribute


Normalization: When the units of measure differ between attributes, it is possible for attributes to dominate in their contribution to the distance measure. For these types of problems, we need to rescale all data attributes into the range 0-1 (called normalization) before calculating similarity


Alternative Distance Measure: There are many distance measures available. The code can be modify to implement an alternative distance measure, such as Manhattan distance or the vector dot product


Support for distance-weighted contribution for the k-most similar instances to the prediction

More advanced data tree-based structures for searching for similar instances
End of explanation
"""


