# coding=utf-8

import numpy as np

import pandas as pd

import time

def Predict(testset, trainset, train_labels):

    predict = []

    count = 0

    for test_vec in testset:

        # 输出当前运行的测试用例坐标，用于测试

        print count

        count += 1

        knn_list = []  # 当前k个最近邻居

        max_index = -1  # 当前k个最近邻居中距离最远点的坐标

        max_dist = 0  # 当前k个最近邻居中距离最远点的距离

        # 先将前k个点放入k个最近邻居中，填充满knn_list

        for i in range(k):

            label = train_labels[i]

            train_vec = trainset[i]

            dist = np.linalg.norm(train_vec - test_vec)  # 计算两个点的欧氏距离

            knn_list.append((dist, label))

        # 剩下的点

        for i in range(k, len(train_labels)):

            label = train_labels[i]

            train_vec = trainset[i]

            dist = np.linalg.norm(train_vec - test_vec)  # 计算两个点的欧氏距离

            # 寻找10个邻近点钟距离最远的点,///应该有一个函数代替循环吧

            if max_index < 0:

                for j in range(k):

                    if max_dist < knn_list[j][0]:

                        max_index = j

                        max_dist = knn_list[max_index][0]

            # 如果当前k个最近邻居中存在点距离比当前点距离远，则替换

            if dist < max_dist:

                knn_list[max_index] = (dist, label)

                max_index = -1

                max_dist = 0

        # 统计选票

        class_total = 10

        class_count = [0 for i in range(class_total)]

        for dist, label in knn_list:

            class_count[label] += 1

        # 找出最大选票

        mmax = max(class_count)

        # 找出最大选票标签

        for i in range(class_total):

            if mmax == class_count[i]:

                predict.append(i)

                break

    return np.array(predict)

k = 10

if __name__ == '__main__':

    time_1 = time.time()

    raw_data = pd.read_csv('D:\\Python27\\yy\\data\\Digit Recognizer\\train.csv')

    raw_test = pd.read_csv('D:\\Python27\\yy\\data\\Digit Recognizer\\test.csv')

    test_features = raw_test.values

    data = raw_data.values

    train_features = data[0::, 1::]

    train_labels = data[::, 0]

    time_2 = time.time()

    print 'read data cost ', time_2 - time_1, ' second', '\n'

    print 'Start predicting'

    test_predict = Predict(test_features, train_features, train_labels)

    time_3 = time.time()

    print 'predicting cost ', time_3 - time_2, ' second', '\n'