Basic principles and examples of KNN algorithm classification

The KNN algorithm is a simple and easy-to-use classification algorithm suitable for small-scale data sets and low-dimensional feature spaces. It performs well in fields such as image classification and text classification, and is popular because of its simplicity of implementation and ease of understanding.

The basic idea of ​​the KNN algorithm is to find the closest K neighbors by comparing the characteristics of the sample to be classified with the characteristics of the training sample, and determine the classification based on the categories of these K neighbors The category of the sample. The KNN algorithm uses a training set with labeled categories and a test set to be classified. The classification process of the KNN algorithm includes the following steps: first, calculate the distance between the sample to be classified and all training samples; second, select the K nearest neighbors; then, vote according to the categories of the K neighbors to obtain the The category of the classified sample; finally, the category of the sample to be classified is determined as the category with the most votes in the voting results. Through these steps, the KNN algorithm can accurately classify the samples to be classified.

1. Calculate distance

For unclassified test samples, it is necessary to calculate the distance between them and all samples in the training set. Commonly used are Euclidean and Manhattan. and other methods.

2. Select K neighbors

Based on the calculated distance, select the K training set samples that are closest to the sample to be classified. These samples are the K neighbors of the sample to be classified.

3. Determine the category

Determine the category of the sample to be classified based on the categories of K neighbors. The "majority voting method" is usually used to determine the category of the sample to be classified, that is, the category that appears most among the K neighbors is selected as the category of the sample to be classified.

The KNN algorithm is relatively simple, but there are some issues that need attention. First of all, the choice of K value has a great impact on the performance of the algorithm, and it is usually necessary to determine the optimal K value through cross-validation and other methods. Secondly, the KNN algorithm is sensitive to the size and dimension of the data set, and there will be efficiency problems when processing large-scale and high-dimensional data sets. In addition, the KNN algorithm also has the problem of "category imbalance", that is, the number of samples in certain categories is small, which may cause the algorithm to have poor classification effect on these categories.

The following is a classification example using Python to implement the KNN algorithm. The code is as follows:

import numpy as np
from collections import Counter

class KNN:
    def __init__(self, k):
        self.k = k

    def fit(self, X, y):
        self.X_train = X
        self.y_train = y

    def predict(self, X_test):
        predictions = []

        for x_test in X_test:
            distances = []
            for x_train in self.X_train:
                distance = np.sqrt(np.sum((x_test - x_train)**2))
                distances.append(distance)
            idx = np.argsort(distances)[:self.k]
            k_nearest_labels = [self.y_train[i] for i in idx]
            most_common = Counter(k_nearest_labels).most_common(1)
            predictions.append(most_common[0][0])

        return np.array(predictions)

The parameter k passed in the constructor of this KNN class indicates how many neighbors to select. to classify. The fit method is used to train the model, accepting a training set X and their corresponding labels y. The predict method is used to classify the test set, accepts a test set X_test, and returns the predicted label.

In the predict method, for each test sample, first calculate its distance from all samples in the training set, and select the k closest samples. Then, the most frequently occurring labels among these k samples are counted and used as the classification labels of the test samples.

The following is an example of using this KNN class for classification. The data set is a point set on a two-dimensional plane, where the red points represent category 1 and the blue points represent category 2:

import matplotlib.pyplot as plt

# 生成数据集
X = np.random.rand(200, 2) * 5 - 2.5
y = np.zeros(200)
y[np.sum(X**2, axis=1) > 2] = 1

# 分割训练集和测试集
train_idx = np.random.choice(200, 150, replace=False)
test_idx = np.array(list(set(range(200)) - set(train_idx)))
X_train, y_train = X[train_idx], y[train_idx]
X_test, y_test = X[test_idx], y[test_idx]

# 训练模型并进行预测
knn = KNN(k=5)
knn.fit(X_train, y_train)
y_pred = knn.predict(X_test)

# 计算准确率并绘制分类结果
accuracy = np.mean(y_pred == y_test)
print("Accuracy:", accuracy)

plt.scatter(X_test[:, 0], X_test[:, 1], c=y_pred)
plt.show()

After running this code, you can see the classification result image. Among them, the color represents the predicted category, red represents category 1, and blue represents category 2. Based on the classification results, the accuracy of the model can be calculated.

This example shows the application of the KNN algorithm on a two-dimensional plane, determining neighbors by calculating distances, and classifying them according to their categories. In practical applications, the KNN algorithm can be used in image classification, text classification and other fields. It is a simple and effective classification algorithm.

The above is the detailed content of Basic principles and examples of KNN algorithm classification. For more information, please follow other related articles on the PHP Chinese website!