Algorithm Introduction

k-nearest neighbor method belongs to supervised learning and does not need training model (lazy learning). Algorithm flow: for the test samples, find k training samples from the given training set according to some distance measurement (Minkowski distance, Euclidean distance, Manhattan distance, Chebyshev distance, etc.), and predict according to the k training sample information. For the classification task, according to the voting method, the category that appears most in the k training samples can be used as the prediction result; For the regression task, the average value of the actual output of k training samples can be taken as the prediction result according to the average method, or the weighted average can be used. For the training samples from the test samples, a larger weight can be taken.

python code implementation

The iris data set is classified and divided into training set and test set

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
import pandas as pd
import numpy as np
from collections import Counter
iris_data = load_iris()
data = pd.DataFrame(iris_data.data,columns=iris_data.feature_names)
data['target'] = iris_data.target
X,y = data.iloc[:,:-1].values,data.iloc[:,-1].values
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.3,stratify=y)
data.head()

	sepal length (cm)	sepal width (cm)	petal length (cm)	petal width (cm)	target
0	5.1	3.5	1.4	0.2	0
1	4.9	3.0	1.4	0.2	0
2	4.7	3.2	1.3	0.2	0
3	4.6	3.1	1.5	0.2	0
4	5.0	3.6	1.4	0.2	0

Build model

class knn:
    def __init__(self,X_train,y_train,neighbors,ord):
        self.X = X_train
        self.y = y_train
        self.k = neighbors
        self.ord = ord  #Distance metric type, ord is equal to the parameter p in Minkowski distance
    def predict(self,x):
        knn_list = []  #Store the information of k training set sample points, including the distance and category from the test sample
        for i in range(self.k):
            dist = np.linalg.norm(x-self.X[i],ord=self.ord)
            knn_list.append((dist,self.y[i]))

        for i in range(self.k,len(self.X)):
            dist = np.linalg.norm(x-self.X[i],ord=self.ord)  #Find norm
            max_index = knn_list.index(max(knn_list,key=lambda x:x[0]))
            if dist<knn_list[max_index][0]:
                knn_list[max_index] = (dist,self.y[i])

        knn_y = [k[-1] for k in knn_list] #Category label of the first k training samples adjacent to the test sample
        #Count the categories of k training samples and the number of training samples in each category
        counter_y = Counter(knn_y)  #Return dictionary data type
        max_y = sorted(counter_y.items(),key=lambda x:x[1])[-1][0]
        return max_y

    def score(self,X_test,y_test):
        count = 0
        for x,y in zip(X_test,y_test):
            if y==self.predict(x):
                count += 1
        return count/len(X_test)
knn_model = knn(X_train,y_train,15,2)
test_accuracy = knn_model.score(X_test,y_test)
print('The accuracy of the test set is;',test_accuracy)

The accuracy of the test set is; 0.9777777777777777

sklearn implementation

from sklearn.neighbors import KNeighborsClassifier
knn_model = KNeighborsClassifier(n_neighbors=10)
knn_model.fit(X_train,y_train)
score = knn_model.score(X_test,y_test)
print(score)

0.977777777778

Construction and search of kd tree

kd tree is a binary tree, which represents the division of k-dimensional space. It is used to store and quickly retrieve k-dimensional instance points. Its structure is very suitable for finding nearest neighbors and collision detection.
Build process:
First, build the root node. It is divided according to a dimension of the instance point. Generally, the dimension with the largest variance value is selected for division; Sort the instance points according to the value of the dimension, take the instance point corresponding to the median as the root node, place the instance point with the value less than the median on the left of the tree to generate the left child node, and place the instance point greater than the median on the right of the tree to generate the right child node; Then, the left and right child nodes continue to be divided into dimensions; Repeat the above process until it cannot be divided to generate leaf nodes.
Search process:
First, find the leaf node containing the target point X in the kd tree, start from the root node and recursively access the kd tree. If x is less than the value of the current node's division dimension, move to the left child node, otherwise vice versa; Take the found leaf node as the current closest point, access the parent node of the current closest point upward in turn and update the closest point. If the value of the parent node in the division dimension and the target point x is less than the current closest distance, you also need to access another child node of this parent node; Until the end of access to the root node.
If the training set is [[7,2], [4,7], [5,4], [2,3], [8,1], [9,6], find the nearest training sample of the target point [3,4.5].

from collections import namedtuple
import numpy as np
from time import process_time

#Define kd tree node class
class KdNode(object):
    def __init__(self,dom_elt,split,left,right):   #Including data point, dimension division, left child node and right child node
        self.dom_elt = dom_elt
        self.split = split
        self.left = left
        self.right = right

#Define kd tree
class KdTree(object):
    def __init__(self,data):   #Attributes include: data dimension and root node
        self.k = len(data[0])
        self.root = self.createNode(data,0)

    def createNode(self,data,split):  #The tree is constructed by iterative algorithm, and split is the divided dimension
        if not data:  #No data, return empty node
            return None
        splitPos = len(data)>>2
        dataSort = sorted(data,key=lambda x:x[split])
        medianNode = dataSort[splitPos]
        splitNext = (split+1) % self.k   #The dimension with the largest variance can also be obtained by dividing the dimensions in order
        return KdNode(medianNode,split,self.createNode(dataSort[:splitPos],splitNext),self.createNode(dataSort[splitPos+1:],splitNext))

    def search_nearest(self,point):  #The iterative algorithm is used to traverse the tree and find the nearest neighbor
        self.result = namedtuple('nearestInf','point distance')  #Store nearest neighbor information
        self.nearestPoint = None
        self.nearestDis = 0
        def travel(node,depth):
            if node != None:
                axis = node.split
                if point[axis]<node.dom_elt[axis]:
                    travel(node.left,depth+1)
                else:
                    travel(node.right,depth+1)
                distance = np.sqrt(np.sum((np.array(point) - np.array(node.dom_elt))**2))
                if self.nearestPoint == None:
                    self.nearestPoint = node.dom_elt
                    self.nearestDis = distance
                elif self.nearestDis > distance:
                    self.nearestPoint = node.dom_elt
                    self.nearestDis = distance
                if abs(point[axis]-node.dom_elt[axis]) < self.nearestDis:
                    if point[axis] < node.dom_elt[axis]:
                        travel(node.right, depth + 1)
                    else:
                        travel(node.left, depth + 1)
        travel(self.root,0)
        return self.result(self.nearestPoint,self.nearestDis)

data = [[7,2],[4,7],[5,4],[2,3],[8,1],[9,6]]  #data set
tree1 = KdTree(data)
result = tree1.search_nearest([3,4.5])
print(result)

nearestInf(point=[2, 3], distance=1.8027756377319946)
0.0

The result is points (2, 3) and the distance is 1.803