KNN Nearest Neighbor K近邻的Python写

Training的时间复杂度： O(1)

Testing的时间复杂度： O(N)

K近邻的优点在于，training过程仅仅是存储了所有的training data，且高效，算法简单

缺点在于，testing时间过长

下面是Python代码：

import numpyas np

class NearestNeighbor:

def __init__(self):

pass

    def train(self, X, y):

"""X is N by D where each row is an example. Y is 1-dimension of size N"""

# The nearest neighbor classifier simply remembers all the training data.

        self.Xtr = X

self.ytr = y

def predict(self, X):

"""X is N by D which each is an example we wish to predict lable for."""

        num_test = X.shape[0]

# let make sure that the output type matches the input type.

        Ypred = np.zeros(num_test,dtypr =self.ytr.dtype)

# loop over all test rows

        for iin xrange(num_test):

# find the nearest training image to the i'th test image

# Using the L1 distance(sum of absolute value distance)

            distances = np.sum(np.abs(self.Xtr - X[i, :]),axis =1)

           min_index = np.argmin(distances)# get the index with the smallest distance

            Ypred[i] =self.ytr[min_index]# predict the label of the nearest example

        return Ypred