## Supervised algorithm KNN/K nearest neighbor

## 1: Principle

1. Calculate the Euclidean distance from o point to all points

Oh
Surname
distance
leave
:
d
=
(
x
a
−
x
b
)
2
+
(
y
a
−
y
b
)
2
Euclidean distance: d = \sqrt{(x_a-x_b)^2+(y_a-y_b)^2}
Euclidean distance: d=(xa − xb) 2+(ya − yb) 2

2. Assuming K = 4, select the K points with the smallest distance

3. What categories do K points belong to

4. Find the maximum number of classes in K points, then divide point O into this class

## 2: The advantages and disadvantages of the algorithm are extremely variable

###### 2.1 advantages and disadvantages

The value of algorithm parameter K affects the effect of the model, so the value of K needs to be determined through the learning curve

Note: the parameters passed artificially are called super parameters, so the parameter adjustment of the model generally refers to the adjustment of super parameters

1. When the K value is larger, the deviation is larger, and under fitting may occur

2. When the K value is smaller, the variance is larger, and over fitting may occur

###### 2.2 algorithm variants

Reason: the value of K may cause the same number of classes, which makes it impossible to classify (because the weight of each point is the same by default)

Variant 1: specify different distance weights for different neighbors. For example, the closer the distance, the greater the weight

Implementation: by specifying the weights parameter in the algorithm

Variant 2: use points within a certain radius to replace the nearest K points

In scikit learn, the RadiusNeighborsClassifier implements a variant of this algorithm

The algorithm is more suitable for the case of uneven data sampling

## 3: Implementation of KNN Algorithm in python

#All lines can be output from IPython.core.interactiveshell import InteractiveShell InteractiveShell.ast_node_interactivity = "all" import numpy as np import pandas as pd import matplotlib.pyplot as plt # Solve the confusion of negative sign of coordinate axis scale plt.rcParams['axes.unicode_minus'] = False # Solve the problem of Chinese garbled code plt.rcParams['font.sans-serif'] = ['Simhei'] plt.style.use('ggplot') #Building data sets data1 = { 'height':[170,189,178,165,166,160,156,158,160,155], 'weight':[110,120,126,112,108,100,98,95,110,85], 'Gender':[1,1,1,1,1,0,0,0,0,0] } data = pd.DataFrame( data1 ) print(data) # Drawing x = np.array(data.iloc[:,0:2]) #Put the characteristic values such as height and weight in the x array y = np.array(data.iloc[:,-1])#Put gender in y array print(x) print(y) #1. Draw the male dot first x_nan = x[y==1,0] y_nan = x[y==1,1] plt.scatter(x=x_nan,y=y_nan,color='red',label='male') #2. Painting women x_nv = x[y==0,0] y_nv = x[y==0,1] plt.scatter(x=x_nv,y=y_nv,color='green',label='female') #3. Give the points to be determined new_data = np.array([162,99]) plt.scatter(x=new_data[0],y=new_data[1],color='blue',label='unknown') #4. Painting axis plt.xlabel('height') plt.ylabel('weight') plt.legend(loc='lower right') #Calculate Euclidean distance #1. Calculate the distance from each point to the unknown point. Because the data of x and Y axes of each point are in the x array, calculate the Euclidean distance directly with the x array from math import sqrt distict = [ sqrt(np.sum((i-new_data)**2)) for i in x ] print(distict) #2. Ascending sorting by Euclidean distance sort = np.argsort(distict) print(sort) #[5 7 6 4 8 3 0 9 2 1] so the point with index=5 is the closest #Determine classification #Determine K value k = 4 top_k = [y[i] for i in sort[0:k]] # The result is the gender corresponding to index=[5,7,6,4] top_k #[0, 0, 0, 1], so there are three women and one man in the category #Count result = pd.Series(top_k).value_counts().index[0] if result==1: print('Male') else: print('female sex')

## 4: sklean implementation of KNN algorithm

Scikit learn, or sklearn for short, supports four machine learning algorithms including classification, regression, dimensionality reduction and clustering, as well as three modules: feature extraction, data preprocessing and model evaluation

Official website: http://scikit-learn.org/stable/index.html

Main design principles:

- uniformity

All objects share a simple and consistent interface (Interface).

Estimator: fit() method. For any object that estimates parameters based on data, the parameter used is a data set (corresponding to X, supervised algorithm)

A y) is also required, and any other parameters that guide the estimation process are called super parameters, which must be set as instance variables.

Converter: transform() method. The data set is transformed using an estimator, and the transformation process depends on learning parameters. You can use the convenient party

Where: fit_transform() is equivalent to first fit() and then transform(). (fit_transform is sometimes optimized and faster)

Predictor: predict() method. Use the estimator to predict new data, return the data containing the prediction results, and the score() method: use

It is used to measure the prediction effect of a given test set. (R square is used for continuous y, and accuracy is used for classification y) - monitor

Check all parameters. The super parameters of all estimators can be accessed through public instance variables, and the learning parameters of all estimators can be accessed through

Public instance variable access for underscore suffixes. - Prevent class proliferation

The object type is fixed, the data set is represented as a Numpy array or a Scipy sparse matrix, and the hyperparameters are ordinary Python characters or numbers. - synthesis

Existing components can be reused as much as possible, and a Pipeline can be easily created. - Reasonable default

Most parameters provide reasonable default values, which can easily build a basic working system

###### sklean code block

#data set #Building data sets import pandas as pd import numpy as np data1 = { 'height':[170,189,178,165,166,160,156,158,160,155], 'weight':[110,120,126,112,108,100,98,95,110,85], 'Gender':[1,1,1,1,1,0,0,0,0,0] } data = pd.DataFrame( data1 ) print(data) #sklean implementation of KNN algorithm #1. Guide Package from sklearn.neighbors import KNeighborsClassifier #2. Set the value of K, which is 5 by default knn = KNeighborsClassifier(n_neighbors=3) #3. Add eigenvalues and classification values x_tezheng = data.loc[:,'height':'weight'] print(x_tezheng) y_fenlei = data.loc[:,'Gender'] print(y_fenlei) knn = knn.fit(X=x_tezheng,y=y_fenlei) #4. Prediction results result = knn.predict([[170,100]]) print(result) #5. Evaluate the model and look at the returned scores # X represents the predicted data # y represents the actual classification, and multiple can be placed here to judge the accuracy # score represents the accuracy of the predicted classification score=knn.score(X=[[156,80]],y=[1]) #This is the prediction of men, and the accuracy score = 0, because it should actually be women print(score) #6. Predicted probability value knn.predict_proba([[170,100]]) #The return value of array([[0.33333333, 0.6667]]) represents array ([[probability of 0, probability of 1]])

## 5: Divide training set and test set

General training set = 80%

Test set = 20%

#1. Prepare data set import pandas as pd import numpy as np data1 = pd.DataFrame( data=np.random.randint(0,100,size=(100,3)), columns=['A','B','C'] ) data2 = pd.DataFrame( data=np.random.randint(0,2,size=(100,1)), columns=['sex'] ) data1['y']=data2 print(data1) #2. Divide training set and test set #2.1 Guide Package from sklearn.neighbors import KNeighborsClassifier from sklearn.model_selection import train_test_split #2.2 divide the data set, 30% as the test set and 70% as the training set X = data1.iloc[:,0:-1] #Characteristic data y = data1.iloc[:,-1] #Label data #The function returns 4 values: training feature, test feature, training tag and test tag Xtrain,Xtest,ytrain,ytest = train_test_split(X,y,test_size=0.3,random_state=420) #test_size represents the size of the test set, random_state is similar to random Seed random seed #2.3 modeling KNN = KNeighborsClassifier(n_neighbors=4) #2.4 classifier / training model KNN = KNN.fit(Xtrain,ytrain) #2.5 test accuracy using test sets score = KNN.score(Xtest,ytest) print(score) #Accuracy = 0.433335

## 6: Find the optimal K value

##### 6.1 parameter learning curve

k in KNN is a super parameter. The so-called "super parameter" is a parameter that needs human input and cannot be calculated directly by the algorithm.

The parameter learning curve is a curve with different parameter values as abscissa and the model results under different parameter values as ordinate. We often choose the parameter value of the best performance point of the model as the value of this parameter.

#Prepare dataset import pandas as pd import numpy as np data1 = pd.DataFrame( data=np.random.randint(0,100,size=(100,3)), columns=['A','B','C'] ) data2 = pd.DataFrame( data=np.random.randint(0,2,size=(100,1)), columns=['sex'] ) data1['y']=data2 print(data1) #2.1 Guide Package from sklearn.neighbors import KNeighborsClassifier from sklearn.model_selection import train_test_split #2.2 divide the data set, 30% as the test set and 70% as the training set X = data1.iloc[:,0:-1] #Characteristic data y = data1.iloc[:,-1] #Label data #The function returns 4 values: training feature, test feature, training tag and test tag Xtrain,Xtest,ytrain,ytest = train_test_split(X,y,test_size=0.3,random_state=420) #test_size represents the size of the test set, random_state is similar to random Seed random seed #2.3 modeling KNN = KNeighborsClassifier(n_neighbors=22) #2.4 classifier / training model KNN = KNN.fit(Xtrain,ytrain) #2.5 test accuracy using test sets score = KNN.score(Xtest,ytest) print(score) #Accuracy = 0.433335 print('========================================') ############################################################################################################ #Draw learning curve #Value of x-axis K #y-axis accuracy x = [] y = [] for k in range(1,21): # x.append(k) clf = KNeighborsClassifier(n_neighbors=k) clf = clf.fit(Xtrain,ytrain) sc = clf.score(Xtest,ytest) y.append(sc) print(x) print(y) #Drawing import matplotlib.pyplot as plt plt.plot(x,y) plt.xticks(range(1,21)) plt.show()

##### 6.2 cross validation

The model needs to consider two issues:

1. Accuracy, depending on K value

2. Stability, depending on the high scores in different data sets (if the scores in different data sets differ greatly, it indicates instability)

Unstable performance: when changing the random seed, the highest score K value of the model will change

###### K-fold cross validation

The most commonly used cross validation is k-fold cross validation. We know that the division of training set and test set will interfere with the results of the model, so we use cross test

The mean value obtained from the results of n times is a better measure of the effect of the model.

schematic diagram:

##### 6.3 parameter learning curve with cross validation

Objective: to find the K value with high score and small variance (both accuracy and stability)

###### K-fold cross validation code implementation:

#Prepare dataset import pandas as pd import numpy as np data1 = pd.DataFrame( data=np.random.randint(0,100,size=(100,3)), columns=['A','B','C'] ) data2 = pd.DataFrame( data=np.random.randint(0,2,size=(100,1)), columns=['sex'] ) data1['y']=data2 print(data1) #2.1 Guide Package from sklearn.neighbors import KNeighborsClassifier from sklearn.model_selection import train_test_split from sklearn.model_selection import cross_val_score #2.2 divide the data set, 30% as the test set and 70% as the training set X = data1.iloc[:,0:-1] #Characteristic data y = data1.iloc[:,-1] #Label data #The function returns 4 values: training feature, test feature, training tag and test tag Xtrain,Xtest,ytrain,ytest = train_test_split(X,y,test_size=0.3,random_state=420) #test_size represents the size of the test set, random_state is similar to random Seed random seed #3. Modeling score=[] #Used to store the average score of each K-fold var=[] #Used to store the fractional variance of each K-fold K = [] #Value of stored K value for i in range(1,21): KNN = KNeighborsClassifier(n_neighbors=i) #Cross validation result = cross_val_score(KNN,Xtrain,ytrain,cv=8) # cv=8 represents the number of K-turns K.append(i) score.append(result.mean()) var.append(result.var()) print('K value',K) print('mean value',score) print('variance',var) #4. Drawing import matplotlib.pyplot as plt #Convert the list into an array to perform mathematical operations score = np.array(score) var= np.array(var) plt.plot(K,score,color='k') plt.plot(K,score+var,color='r',linestyle='--') plt.plot(K,score-var,color='b',linestyle='--') plt.xticks(range(1,21))

###### Model interpretation:

###### Test set validation:

#Test set validation KNN_18 = KNeighborsClassifier(n_neighbors=18) #Training model fit = KNN_18.fit(Xtrain,ytrain) #Test set verification score sc = fit.score(Xtest,ytest) sc #0.43333333333333335

be careful:

1. Do not set the K value too large, otherwise under fitting will occur, and too small will be over fitting

2.cv, that is, the number of folds of K cannot be too large or too small. In the function, the default = 5 folds, and the empirical value = 5 / 6 folds

Excessive discount:

Computational efficiency slows down.

The variance of prediction rate becomes larger, so it is difficult to ensure the expected prediction rate in the new data set.

###### Other cross validation:

All cross validation is based on the segmentation of training set and test set, but focuses on different directions

"k-fold" is to take the training set and test set in order

ShuffleSplit focuses on Distributing the test set in all directions of the data

Structured kfold believes that training data and test data must occupy the same proportion in each label classification

## 7: Normalization

When the data (x) is centered according to the minimum value and then scaled according to the range (maximum - Minimum), the data moves by the minimum value units and will be received

Converge to [0,1], and this process is called data Normalization (also known as min max scaling).

Objective: to eliminate the influence of dimension

Especially in the calculation of distance (such as PCA, such as KNN, such as kmeans, etc.), it is either normalized or standardized

Formula:

The first
one
species
square
type
:
(
X
i
−
X
m
i
n
)
/
(
X
m
a
x
−
X
m
i
n
)
The first
two
species
square
type
:
y
=
l
o
g
10
(
x
)
The first method: (X_i-X_min) / (X_max - X_min) \ \ the second method: y = log10(x)
The first method: (Xi − Xm in)/(Xm ax − Xm in) the second method: y=log10(x)

###### When to do normalization???

- First divided into training set and test set, and then normalized!

###### Normalization code implementation:

#Prepare dataset import pandas as pd import numpy as np data1 = pd.DataFrame( data=np.random.randint(0,100,size=(100,3)), columns=['A','B','C'] ) data2 = pd.DataFrame( data=np.random.randint(0,2,size=(100,1)), columns=['sex'] ) data1['y']=data2 print(data1) #2.1 Guide Package from sklearn.neighbors import KNeighborsClassifier from sklearn.model_selection import train_test_split from sklearn.model_selection import cross_val_score #2.2 divide the data set, 30% as the test set and 70% as the training set X = data1.iloc[:,0:-1] #Characteristic data y = data1.iloc[:,-1] #Label data #The function returns 4 values: training feature, test feature, training tag and test tag Xtrain,Xtest,ytrain,ytest = train_test_split(X,y,test_size=0.3,random_state=420) #test_size represents the size of the test set, random_state is similar to random Seed random seed #3. Normalization (first divide the data set, then normalize, and finally model) from sklearn.preprocessing import MinMaxScaler as mms Xtrain = mms().fit(Xtrain).transform(Xtrain)#Training set normalization Xtest = mms().fit(Xtest).transform(Xtest)#Test set normalization print(Xtrain_mms) #3. Modeling score=[] #Used to store the average score of each K-fold var=[] #Used to store the fractional variance of each K-fold K = [] #Value of stored K value for i in range(1,21): KNN = KNeighborsClassifier(n_neighbors=i) #Cross validation result = cross_val_score(KNN,Xtrain,ytrain,cv=8) # cv=8 represents the number of K-turns K.append(i) score.append(result.mean()) var.append(result.var()) print('K value',K) print('mean value',score) print('variance',var) #4. Drawing import matplotlib.pyplot as plt #Convert the list into an array to perform mathematical operations score = np.array(score) var= np.array(var) plt.plot(K,score,color='k') plt.plot(K,score+var,color='r',linestyle='--') plt.plot(K,score-var,color='b',linestyle='--') plt.xticks(range(1,21))

## 8: Punishment of distance

Usage scenario: when the sample distribution is uneven

That is, set the weight according to the distance

It should be noted here that the optimization method of the model is only in theory, and the optimization will improve the discrimination effectiveness of the model, but in practical application

Whether the process can play a role ultimately depends essentially on the fit between the optimization method and the actual data. If the data itself exists

If there are a large number of outliers, using distance as the punishment factor will have a better effect, otherwise.

###### Code implementation:

- Kneigborsclassifier (n_neighbors = I, weights = 'distance') # weights = 'distance' stands for distance penalty

#Prepare dataset import pandas as pd import numpy as np data1 = pd.DataFrame( data=np.random.randint(0,100,size=(100,3)), columns=['A','B','C'] ) data2 = pd.DataFrame( data=np.random.randint(0,2,size=(100,1)), columns=['sex'] ) data1['y']=data2 print(data1) #2.1 Guide Package from sklearn.neighbors import KNeighborsClassifier from sklearn.model_selection import train_test_split from sklearn.model_selection import cross_val_score #2.2 divide the data set, 30% as the test set and 70% as the training set X = data1.iloc[:,0:-1] #Characteristic data y = data1.iloc[:,-1] #Label data #The function returns 4 values: training feature, test feature, training tag and test tag Xtrain,Xtest,ytrain,ytest = train_test_split(X,y,test_size=0.3,random_state=420) #test_size represents the size of the test set, random_state is similar to random Seed random seed #3. Normalization from sklearn.preprocessing import MinMaxScaler as mms Xtrain = mms().fit(Xtrain).transform(Xtrain)#Training set normalization Xtest = mms().fit(Xtest).transform(Xtest)#Test set normalization print(Xtrain_mms) #3. Modeling + distance penalty score=[] #Used to store the average score of each K-fold var=[] #Used to store the fractional variance of each K-fold K = [] #Value of stored K value for i in range(1,21): KNN = KNeighborsClassifier(n_neighbors=i,weights='distance') # weights='distance 'stands for distance penalty #Cross validation result = cross_val_score(KNN,Xtrain,ytrain,cv=8) # cv=8 represents the number of K-turns K.append(i) score.append(result.mean()) var.append(result.var()) print('K value',K) print('mean value',score) print('variance',var) #4. Drawing import matplotlib.pyplot as plt #Convert the list into an array to perform mathematical operations score = np.array(score) var= np.array(var) plt.plot(K,score,color='k') plt.plot(K,score+var,color='r',linestyle='--') plt.plot(K,score-var,color='b',linestyle='--') plt.xticks(range(1,21))

N = kneigborsclassifier (n_neighbors = I, weights = 'distance') # weights = 'distance' stands for distance penalty

#Cross validation

result = cross_val_score(KNN,Xtrain,ytrain,cv=8) # cv=8 represents the number of K-turns

K.append(i)

score.append(result.mean())

var.append(result.var())

print('k value ', K)

print('mean ', score)

print('variance ', var)

#4. Drawing

import matplotlib.pyplot as plt

#Convert the list into an array to perform mathematical operations

score = np.array(score)

var= np.array(var)

plt.plot(K,score,color='k')

plt.plot(K,score+var,color='r',linestyle='–')

plt.plot(K,score-var,color='b',linestyle='–')

plt.xticks(range(1,21))