KNN算法笔记及python演示

KNN算法又称K近邻算法，属于监督学习。
其中心思想是找到未分类样本附近K个最相近的已分类样本，该样本的分类由附近已分类的样本投票决定。

可通过欧氏距离、曼哈顿距离等计算测试样本与已分类样本之间的距离。

K值的选择会直接影响归类效果。


k太小，分类结果易受噪声点影响；
k太大，近邻中又可能包含太多的其它类别的点。（对距离加权，可以降低k值设定的影响）k值通常是采用交叉检验来确定（以k=1为基准）
经验规则：k一般低于训练样本数的平方根。

算法步骤
1.选择距离公式。
2.计算为分类样本点与其他所有已分类样本之间的距离。
3.针对计算出的距离进行升序排序。
4.选择前K各个距离最短的点。
5.前K个距离最短的点中，未分类的样本点所属分类，由附近已分类的样本投票决定。

缺陷与改进
缺陷一：计算为分类点与所有已分类的点距离，再进行排序，导致计算量大。
改进：使用K-d树数据结构，优化搜索操作，减少计算量。

缺陷二：样本不平衡问题会影响分类结果。
改进：采用权值的方法（距离的倒数）

K-d树数据结构
对数据点在k维空间划分的一种数据结构。
中心思想：K-d树是一种空间划分树，把整个空间划分为特定的几个部分，然后在特定空间的部分内进行相关搜索操作。

K-d树构建

代码演示

import pandas as pd
import numpy as np
df = pd.read_csv("fruit.txt",sep="	")
df.head()

label = np.array(df['fruit_label'])
# train = pd.concat([df['mass'],df['width'],
#                    df['height'],df['color_score']],axis=1)
train = df[['mass','width','height','color_score']]

train = np.array(train)
train

将特征数据标准化并准备好的数据放入train中储存

from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
train = scaler.fit_transform(train)

#分个数据集
#特征train：x_train,x_test
#类别label:y_train,y_test
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import  train_test_split
#train_size:用作训练的数据占总数80%，测试数据20%
x_train,x_test,y_train,y_test = train_test_split(train,label,train_size=0.8,
                                              random_state=1)
#n_neighbors设置K值
knn = KNeighborsClassifier(n_neighbors=5)
#放入训练数据的特征和类别
knn.fit(x_train,y_train)

除了n_neighbors这个参数，还有其他参数可以选择
重点强调下weights（权重）这个参数
weights可以等于
uniform ：统一权重，在每一个邻居区域里的点的权重都是一样的。
distance：权重点等于他们距离的倒数。使用此函数，更近的邻居对于所预测的点的影响更大。
callable：用户自定义的方法，此方法接收一个距离的数组，返回一个相同形状并且包含权重的数组

from sklearn import *
#储存预测数据
y_pred = knn.predict(x_test)
print(metrics.accuracy_score(y_test,y_pred))

尝试修改K值可影响准确度。