def distance(p0, p1):
    return np.sum((p0 - p1)**2)

import numpy as np
p0 = np.array([1,2])
p1 = np.array([0,0])

def nn_classify(training_set, training_labels, new_example):
    dists = np.array([distance(t, new_example) for t in training_set])
    nearest = dists.argmin()
    return training_labels[nearest]

def load_dataset(dataset_name):
    '''
    data,labels = load_dataset(dataset_name)

    Load a given dataset

    Returns
    -------
    data : numpy ndarray
    labels : list of str
    '''
    data = []
    labels = []
    with open('{0}.tsv'.format(dataset_name)) as ifile:
        for line in ifile:
            tokens = line.strip().split('\t')
            data.append([float(tk) for tk in tokens[:-1]])
            labels.append(tokens[-1])
    data = np.array(data)
    labels = np.array(labels)
    return data, labels

def fit_model(k, features, labels):
    '''Learn a k-nn model'''
    # There is no model in k-nn, just a copy of the inputs
    return k, features.copy(), labels.copy()


def plurality(xs):
    '''Find the most common element in a collection'''
    from collections import defaultdict
    counts = defaultdict(int)
    for x in xs:
        counts[x] += 1
    maxv = max(counts.values())
    for k in counts.keys():
        if counts[k] == maxv:
            return k
# 这里的K 就是选出离点最近的k个点
def predict(features, model):
    """Apply k-nn model"""
    # according to testing features to predict
    # model中包含的是training features and training labels
    k, train_feats, labels = model
    results = []
    for f in features: #这里的features是testing features
        label_dist = []
        # compute all distance
        for t, ell in zip(train_feats, labels):
            # 用向量范数来替代距离
            # 使用范数可以测量两个函数、向量或矩阵之间的距离。
            # 这里的f和t都包含七个数，代表七个feature
            label_dist.append((np.linalg.norm(f - t), ell))
        label_dist.sort(key=lambda d_ell:d_ell[0])
        #这里找到最近的K个点
        label_dist = label_dist[:k]
        #在这K个点之中，出现最多次的label被加入到results之中
        results.append(plurality([ell for _, ell in label_dist]))
    return np.array(results)
        
def accuracy(features, labels, model):
    #这里放入的是 testing features 和 testing labels
    preds = predict(features, model)
    return np.mean(preds == labels)

features, labels = load_dataset('seeds')
def cross_validate(features, labels):
    error = 0.0
    for fold in range(10):
        training = np.ones(len(features), bool)
        training[fold::10] = 0 #使得fold位置和fold + 10, fold+20...位置变为0
        testing = ~training
        model = fit_model(1, features[training], labels[training])
        test_error = accuracy(features[testing], labels[testing], model)
        error += test_error
    
    return error / 10.0

error = cross_validate(features, labels)
error

z_score_features = features.copy()
z_score_features -= features.mean(0)
z_score_features /= z_score_features.std(0)
z_score_error = cross_validate(z_score_features, labels)
z_score_error

from sklearn.cross_validation import KFold
from sklearn.neighbors import KNeighborsClassifier
features, labels = load_dataset('seeds')
classifier = KNeighborsClassifier(n_neighbors=1)
kf = KFold(len(features), n_folds=5, shuffle = True)
means = []
for training ,testing in kf:
    # we fit a model for this fold, then apply it to the testing data with 'predict'
    classifier.fit(features[training], labels[training])
    prediction = classifier.predict(features[testing])
    
    # np.mean on an array of booleans return fraction of correct decisions of this fold
    curmean = np.mean(prediction == labels[testing])
    means.append(curmean)
# 估计这里答案会变化的原因是 cut the fold是随机选第一个位置的，而不是固定从第一个[0::10]
res = np.mean(means)
print '{:.1%}'.format(res)

n = len(features)
correct = 0.0
for ei in range(n):
    training = np.ones(n, bool)
    training[ei] = 0
    testing = ~training
    classifier.fit(features[training], labels[training])
    pred = classifier.predict(features[testing])
    correct += (pred == labels[testing])
    
correct = correct / n
print '{:.1%}'.format(correct[0])

# z-score 
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
classifier = KNeighborsClassifier(n_neighbors=1)
classifier = Pipeline([('norm', StandardScaler()), ('knn', classifier)])
# The Pipeline constructor takes a list of pairs (str,clf). Each pair corresponds to a step in
# the pipeline: the first element is a string naming the step, while the second element is the
# object that performs the transformation.

kf = KFold(len(features), n_folds=5, shuffle = True)
means = []
for training ,testing in kf:
    # we fit a model for this fold, then apply it to the testing data with 'predict'
    classifier.fit(features[training], labels[training])
    prediction = classifier.predict(features[testing])
    
    # np.mean on an array of booleans return fraction of correct decisions of this fold
    curmean = np.mean(prediction == labels[testing])
    means.append(curmean)
res = np.mean(means)
print '{:.1%}'.format(res)