In reality , Rich people's neighbors may also be rich , Poor people's neighbors may also be poor . If your neighbors are rich , that , You're probably rich too . Based on this , We have it. KNN Algorithm .KNN The full name is K-Nearest Neighbors, namely K The nearest neighbor . He passes through the nearest to the predicted point K Neighbors to predict the predicted point .
As shown in the figure below , The green circle is the predicted point . It's surrounded by red triangles and blue squares . If we take K by 3, that , Its three neighbors are two red triangles and a blue square . Because of its neighbors , Most of all, the red triangle , So we predict it's also the red triangle .
（ Figure 1 ）
First , We load data . Here we have iris Data sets, for example .
import math from collections import Counter import numpy as np import matplotlib.pyplot as plt from matplotlib.colors import ListedColormap # Create color maps cmap_light = ListedColormap(['orange', 'cyan', 'cornflowerblue']) cmap_bold = ListedColormap(['darkorange', 'c', 'darkblue']) from sklearn import neighbors, datasets n_neighbors = 15 # import some data to play with iris = datasets.load_iris() # we only take the first two features. We could avoid this ugly # slicing by using a two-dim dataset X = iris.data[:, :2] y = iris.target
next , Let's write a KNNClassifier class . here , The most important parameter, of course, is k, Or call it n_neighbors. next , Let's write a fit Method . This method is in addition to “ remember ” Out of data , Not doing anything . Because of this feature , Our name is KNN by lazy algorithm. In the prediction method predict_one in , We first calculate the distance between the predicted point and each point in the dataset , We got d i s t a n c e _ a r r a y distance\_array distance_array. We use it numpy Inside argsort function , Sort these distances from small to large , And get their coordinates . Before we take it k A coordinate , Get the corresponding label n e i g h b o u r _ l a b e l s neighbour\_labels neighbour_labels. We use it python Inside Counter Get the number of occurrences of each tag , And pick the most frequent tags m o s t _ f r e q u e n t most\_frequent most_frequent. thus , The prediction of a point is done . We map once predict_one, obtain predict Method .
class KNNClassifier(): X=None y=None n_neighbors=0 def __init__(self, n_neighbors=15): self.n_neighbors=n_neighbors def fit(self, X, y): self.X=np.array(X) self.y=np.array(y) def predict_one(self, p): distance_array=np.array(list(map(lambda o: math.dist(p, o), self.X))) argsorted=np.argsort(distance_array) neighbours = argsorted[:self.n_neighbors] neighbour_labels = y[neighbours] occurence_count = Counter(neighbour_labels) most_frequent = occurence_count.most_common(1) return most_frequent def predict(self, X): y_hat = np.array(list(map(self.predict_one, X))) return y_hat
Words are always pale , Let's make a picture .
knn = KNNClassifier() knn.fit(X, y) x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1 y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1 h = .02 # step size in the mesh xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h)) Z = knn.predict(np.c_[xx.ravel(), yy.ravel()]) # Put the result into a color plot Z = Z.reshape(xx.shape) plt.figure() plt.pcolormesh(xx, yy, Z, cmap=cmap_light) # Plot also the training points plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold, edgecolor='k', s=20) plt.xlim(xx.min(), xx.max()) plt.ylim(yy.min(), yy.max()) plt.title("My KNN (k = %i)" % (n_neighbors)) plt.show()
（ Figure 2 ）
Is our algorithm right ？ Compare the Scikit-learn Well
# we create an instance of Neighbours Classifier and fit the data. clf = neighbors.KNeighborsClassifier(n_neighbors) clf.fit(X, y) # Plot the decision boundary. For that, we will assign a color to each # point in the mesh [x_min, x_max]x[y_min, y_max]. x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1 y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1 h = .02 # step size in the mesh xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h)) Z = clf.predict(np.c_[xx.ravel(), yy.ravel()]) # Put the result into a color plot Z = Z.reshape(xx.shape) plt.pcolormesh(xx, yy, Z, cmap=cmap_light) # Plot also the training points plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold, edgecolor='k', s=20) plt.xlim(xx.min(), xx.max()) plt.ylim(yy.min(), yy.max()) plt.title("Scikit-learn KNN (k = %i)" % (n_neighbors)) plt.show()
（ Figure 3 ）
Visually, the two are almost the same .
K The choice of
From Figure 1, we can see , If we put k from 3 Change to 5, The result has changed . therefore ,k The choice of is very important .k It has to be big enough , Is of reference significance .k And it has to be small enough , Otherwise, it will degenerate to the average .
The European distance we use here . You can also use Manhattan distance , Or write a distance function by yourself . Distance can also be used as weights , The closer you get , The greater the weight .
Some data , With him or without him , It has no effect on the result , Or little impact . such as ,k=5, Yes 100 A collection of data , that , Only the edge points make sense . At this time , You can remove some points , bring knn The speed of prediction is greatly improved . At this time KNN It becomes CNN（Condensed nearest neighbors）
Besides classification , Return to ,KNN It can also be used for anomaly detection . To the furthest neighbor k The distance to k-distance, Compare this value directly , The bigger it is, the more likely it is to be an outlier .