Detailed introduction to the KNN algorithm (k-nearest neighbor algorithm) in Python (with examples)

This article brings you a detailed introduction to the KNN algorithm (k-nearest neighbor algorithm) in Python (with examples). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. helped.

The KNN algorithm is a data classification algorithm. The category of the k nearest neighbor data from the sample represents the category of the sample, so it is also called the k-nearest neighbor algorithm. The KNN algorithm is one of the simplest methods in data mining and can be roughly divided into the following steps:

• Training data: data of all data categories in the original data set.

• Test data: The data sample we will use for testing.

• Processing data

The test data we get is usually of different dimensions than the training data. At this time, we need to upgrade the test data The dimension is the same as the training data. Python's numpy comes with a tile() function that can help us increase the dimension of the test data.

• Vectorize the data

After the dimensionality of the test data is increased, in order to calculate the distance from the sample point, we need to vectorize the data at this time , the so-called vectorization is very simple, that is, subtracting two data of the same dimension.

• Calculate the Euclidean distance

The Euclidean distance, that is, the Euclidean distance, can be calculated using the Pythagorean theorem. The square and square root of each vector in the vector group obtained by subtracting the test data and training data can be used to obtain a vector group composed of distances.

• Classification based on distance

Select k data with the smallest distance from the sample point, and count which data categories among these k data With the highest frequency of occurrence, the data category of the sample point can be determined.

Algorithm implementation:

1. First we need to introduce numpy and operator, enter from numpy import * and import operator.

2. Next we need to define a knn function. In the knn function we need to introduce four parameters, namely k, training data, test data and data category.

3. Next, we need to perform dimensionality enhancement operation on the data first. We need to use the tile(a,(b,c)) function under numpy. a is the data to be performed on the dimensionality enhancement operation, that is Test data, b is the row data to be upgraded to the test data, and c is the column data to be upgraded to the test data.

4. In the previous operation, we generally need to obtain the number of rows and columns of the training data. In this case, we need to use shape() Function, the shape() function returns a tuple consisting of rows and columns of the training data. If we want to know the number of rows or columns of the training data, we only need to reference it through the array element subscript.

5. After the dimensions of the data are the same, we need to subtract the two data to get a vector, and then calculate the sum of the squares of each value of this vector The square root of is the distance from the test data to the training data, and then calls the argsort() function to sort the distances in ascending order, but this function returns the subscript of the array element.

6. Next, in order to intuitively see the number of occurrences of different data categories, we need to set up an empty dictionary to store the data. After getting After the dictionary, we need to sort the dictionary in descending order according to the number of occurrences of different data categories, and then return the first value of the dictionary to get the data category of the test data.

7. The algorithm code is as follows:

from numpy import *
import operator
def knn(k, test_data, train_data, labels):
    train_size = train_data.shape[0]    #获取训练数据的行数
    test_size = tile(test_data, (train_size, 1))    #将测试数据的行升维
    minus = test_size-train_data    #得到向量
    sq_minus = minus**2
    sum_sq_minus = sq_minus.sum(axis=1)        #得到平方后的每个数组内元素的和
    distc = sum_sq_minus**0.5
    sort_distc = distc.argsort()    #将距离按升序排列
    static = {}
    for i in range(0, k):
        vote = labels[sort_distc[i]]    #获取数据类型
        static[vote] = static.get(vote, 0)+1    #统计每个数据类型的出现次数
    sort_static = sorted(static.items(), key=operator.itemgetter(1), reverse=True)    #将字典中的元素按出现次数降序排列
    return sort_static[0][0]    #返回出现次数最多的数据类型

8. The dictionary needs to be sorted in the algorithm, so the sorted() function needs to be used. The sorted() function has three parameters, namely items. (), operator.itemgetter(), reverse, the default sorting is ascending order. If we want to sort in descending order, we need to set the third parameter to True. Here we are sorting according to the values ​​​​of the dictionary, so we need to enter sorted(static.items(), key=operator.itemgetter(1), reverse=True), when the value in the operator.itemgetter() function is 1, it is sorted according to the values ​​​​of the dictionary, and the value is 0 When, it is sorted according to the key of the dictionary.

9. The way to access elements after sorting is the same as the way to access two-dimensional array elements

The above is the detailed content of Detailed introduction to the KNN algorithm (k-nearest neighbor algorithm) in Python (with examples). For more information, please follow other related articles on the PHP Chinese website!