1. Introduction to algorithm

The working principle of k-nearest neighbor algorithm is that there is a sample data set, also known as training sample set, and each data in the sample set has a label, that is, we know the corresponding relationship between each data in the sample set and its classification. After entering the new data without labels, each feature of the new data is compared with the corresponding feature of the data in the sample set, and then the algorithm extracts the classification label of the data with the most similar feature (nearest neighbor) in the sample set. Generally speaking, we only select the first k most similar data in the sample data set, which is the source of K in the k-nearest neighbor algorithm. Generally, K is an integer not greater than 20. Finally, select the classification that appears most in the k most similar data as the classification of new data.

Advantages: high precision, insensitive to outliers and no data input assumption. Disadvantages: high computational complexity and space complexity. Applicable data range: numerical type and standard type.

The general flow of k-nearest neighbor algorithm is shown in the book:

2. Examples

Taking film classification as an example, kNN can be used to classify whether a film is a love film or an action film.

The above figure is a data set, that is, a training sample set. Generally speaking, we divide kissing scenes into romantic films. There are many fighting scenes, which are divided into action films. According to the data of the original six films, even if we don't know what type of unknown films belong to, we can judge by calculating the distance from these films.

In the figure above, we get the distance between the film in the sample and the unknown film. Assuming k=3, the three closest to the unknown film are all love films, so we judge the unknown film as a love film.

3. Code implementation

Take improving dating website pairing as an example

Preparing data: parsing data from a text file

Resolver for converting text records to NumPy

def file2matrix(filename): # Open file fr = open(filename) # Read all contents of the file arrayOlines = fr.readlines() # Get the number of file lines numberOfLines = len(arrayOlines) # Returned NumPy matrix numberOfLines row, 3 columns returnMat = np.zeros((numberOfLines, 3)) # Create category label vector classLabelVector = [] # Index value of row index = 0 # Read each line for line in arrayOlines: # Remove the white space at the beginning and end of each line, such as' \ n','\r','\t ',' line = line.strip() # Slice the contents of each row according to the '\ t' symbol. In this example, there are four columns listFromLine = line.split('\t') # The first three columns of data are extracted and stored in the returnMat matrix, that is, the characteristic matrix returnMat[index, :] = listFromLine[0:3] # Put in the index line of returnMat # Classification according to text content 1: dislike; 2: General; 3: Like if listFromLine[-1] == 'didntLike': classLabelVector.append(1) elif listFromLine[-1] == 'smallDoses': classLabelVector.append(2) elif listFromLine[-1] == 'largeDoses': classLabelVector.append(3) index += 1 # Returns the label column vector and the characteristic matrix return returnMat, classLabelVector

Analyzing data: creating scatter charts using Matplotlib

import matplotlib import matplotlib.pyplot as plt fig = plt.figure() ax = fig.add_subplot(111) ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0*array(datingLabels), 15.0*array(datingLabels)) plt.show()

Prepare data: normalized value

Normalized eigenvalue

def autoNorm(dataSet): # Gets the minimum value of the data minVals = dataSet.min(0) # Gets the maximum value of the data maxVals = dataSet.max(0) # Range of maximum and minimum values ranges = maxVals - minVals # shape(dataSet) returns the number of matrix rows and columns of the dataSet normDataSet = np.zeros(np.shape(dataSet)) # numpy function shape[0] returns the number of rows of dataSet m = dataSet.shape[0] # Original value minus minimum value (x-xmin) normDataSet = dataSet - np.tile(minVals, (m, 1)) # Difference divided by the difference between maximum and minimum (x-xmin) / (xmax xmin) normDataSet = normDataSet / np.tile(ranges, (m, 1)) # Normalized data results, data range, minimum return normDataSet, ranges, minVals

Test algorithm: verify the classifier as a complete program

Classifier test code for dating website

def datingClassTest(): # Open file name filename = "datingTestSet.txt" # Store the returned feature matrix and classification vector in datingDataMat and datingLabels respectively datingDataMat, datingLabels = file2matrix(filename) # Take 10% of all data. The smaller the Horatio, the lower the error rate hoRatio = 0.10 # Data normalization, return normalized data result, data range, minimum value normMat, ranges, minVals = autoNorm(datingDataMat) # Gets the number of rows of normMat m = normMat.shape[0] # 10% number of test data numTestVecs = int(m * hoRatio) # Classification error count errorCount = 0.0 for i in range(numTestVecs): # The first numTestVecs data is used as the test set, and the last m-numTestVecs data is used as the training set # k select the number of label s + 1 (the result is better) classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], \ datingLabels[numTestVecs:m], 4) print("Classification results:%d\t Real category:%d" % (classifierResult, datingLabels[i])) if classifierResult != datingLabels[i]: errorCount += 1.0 print("error rate:%f%%" % (errorCount / float(numTestVecs) * 100))

Using algorithms: building complete and usable systems

Dating site prediction function

def classifyPerson(): # Output results resultList = ['Detestable', 'Some like', 'like it very much'] # 3D feature user input percentTats = float(input("Percentage of time spent playing video games:")) ffMiles = float(input("Frequent flyer miles obtained each year:")) iceCream = float(input("Litres of ice cream consumed per week:")) # Open file name filename = "datingTestSet.txt" # Open and process data datingDataMat, datingLabels = file2matrix(filename) # Training set normalization normMat, ranges, minVals = autoNorm(datingDataMat) # Generate NumPy array, test set inArr = np.array([percentTats, ffMiles, iceCream]) # Test set normalization norminArr = (inArr - minVals) / ranges # Return classification results classifierResult = classify0(norminArr, normMat, datingLabels, 4) # Print results print("You may%s this man" % (resultList[classifierResult - 1]))

4. Summary

K-NN is a case-based learning, or local approximation and lazy learning that postpones all calculations until after classification. k-nearest neighbor algorithm is one of the simplest machine learning algorithms.