一、KNN介绍
KNN（K-Nearest Neighbor）算法，意思是K个最近的邻居，从这个名字我们就能看 出一些KNN算法的蛛丝马迹了。K个最近邻居，毫无疑问，K的取值肯定是至关重要 的。那么最近的邻居又是怎么回事呢？其实啊，KNN的原理就是当预测一个新的 值x的时候，根据它距离最近的K个点是什么类别来判断x属于哪个类别。KNN算法可以用于分类和回归，是一种监督学习算法。
思路：如果一个样本在特征空间中的K个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。也就是说，该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
图中绿色的点就是我们要预测的那个点，假设K=3。那么KNN算法就会找到与它距离 最近的三个点（这里用圆圈把它圈起来了），看看哪种类别多一些，比如这个例子中 是蓝色三角形多一些，新来的绿色点就归类到蓝三角了。
但是，当K=5的时候，判定就变成不一样了。这次变成红圆多一些，所以新来的绿 点被归类成红圆。从这个例子中，我们就能看得出K的取值是很重要的。
二、KNN实现步骤
1. 计算距离（欧几里得距离或者马氏距离）
欧几里得距离(二维)：
马氏距离：
2. 升序排列
3. 取前K个
K的取值 K太大：导致分类模糊
K太小：受个例影响，波动较大
三、KNN实战案例应用
KNN算法求病人癌症检测的正确率
import csv
import random
# 读取数据
with open(".\Prostate_Cancer.csv","r") as f:
render = csv.DictReader(f) //转换成字典
datas = [row for row in render]
# 分组，打乱数据
random.shuffle(datas)
n = len(datas)//3
test_data = datas[0:n]
train_data = datas[n:]
# print (train_data[0])
# print (train_data[0]["id"])
# 计算对应的距离
def distance(x, y):
res = 0
for k in
("radius","texture","perimeter","area","smoothness","compactnes
s","symmetry","fractal_dimension"):
res += (float(x[k]) - float(y[k]))**2
return res ** 0.5
# K=6
def knn(data,K):
# 1. 计算距离
res = [
{"result":train["diagnosis_result"],"distance":distance(data,tr
ain)}
for train in train_data
]
# 2. 排序
sorted(res,key=lambda x:x["distance"])
# print(res)
# 3. 取前K个
res2 = res[0:K]
# 4. 加权平均
result = {"B":0,"M":0}
# 4.1 总距离
sum = 0
for r in res2:
sum += r["distance"]
# 4.2 计算权重
for r in res2 :
result[r['result']] += 1-r["distance"]/sum
# 4.3 得出结果
if result['B'] > result['M']:
return "B"
else:
return "M"
# print(distance(train_data[0],train_data[1]))
# 预测结果和真实结果对比，计算准确率
for k in range(1,10):
correct = 0
for test in test_data:
result = test["diagnosis_result"]
result2 = knn(test,k)
if result == result2:
correct += 1
print("k="+str(k)+"时，准确率
{:.2f}%".format(100*correct/len(test_data)))
四、 KNN的优缺点
优点：
1）算法简单，理论成熟，既可以用来做分类也可以用来做回归。
2）可用于非线性分类。
3）没有明显的训练过程，而是在程序开始运行时，把数据集加载到内存后，不需要进行训练，直接进行预测，所以训练时间复杂度为0。
4）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属的类别，因此对于类域的交叉或重叠较多的待分类样本集来说，KNN方法较其他方法更为适合。
5）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量比较小的类域采用这种算法比较容易产生误分类情况。
缺点：
1）需要算每个测试点与训练集的距离，当训练集较大时，计算量相当大，时间复杂度高，特别是特征数量比较大的时候。
2）需要大量的内存，空间复杂度高。
3）样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少），对稀有类别的预测准确度低。
4）是lazy learning方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢。
注意，为了克服降低样本不平衡对预测准确度的影响，我们可以对类别进行加权，例如对样本数量多的类别用较小的权重，而对样本数量少的类别，我们使用较大的权重。 另外，作为KNN算法唯一的一个超参数K,它的设定也会算法产生重要影响。因此，为了降低K值设定的影响，可以对距离加权。为每个点的距离增加一个权重，使得距离近的点可以得到更大的权重。
五. KNN的应用和它的场景
我们用sklearn库来看看如何使用KNN，并会简单介绍一下KNN的场景。
1. 将数据集分割成测试数据集和训练数据集
from sklearn.model_selection import train_test_split
X_train,X_test,y_train,y_test =train_test_split(X,y)
2. 创建一个KNeighborsClassifier 对象
from sklearn.neighbors import KNeighborsClassifier
knn= KNeighborsClassifier()
3 使用KNeighborsClassifier 对象进行fit创建出模型，得出分类准确度
knn.fit(X_train,y_train)
knn.score(X_test,y_test)
4 使用我们的模型预测测试集
y_predict = knn.predict(X_test)
KNN的初始函数(构造函数)的参数和默认参数是：
(n_neighbors=5,weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2,
metric=’minkowski’,metric_params=None, n_jobs=1, **kwargs)
它主要有以下几个参数：
[n_neighbors] 也就是K，默认参数为5。
[weights] str参数，为了降低k值的影响所设置的权重值，即每个拥有投票权的样本是按什么比重投票，'uniform'表示等比重投票，'distance'表示按距离 反比投票，[callable]表示自己定义的一个函数，这个函数接收一个距离数组，返回一个权值数组。默认参数为‘uniform’。
[algorithm] str参数，即内部采用什么数据结构实现。有以下几种选择参：'ball_tree':球树、'kd_tree':kd树、'brute':暴力搜索、'auto':自动根据数据的类型和结构选择合适的算法。默认情况下是‘auto’。暴力搜索就不用说了大家都知道。具体前两种树型数据结构哪种好视情况而定。KD树是依次对K维坐标轴，以中值切分构造的树，每一个节点是一个超矩形，在维数小于20时效率最高。ball tree 是为了克服KD树高维失效而发明的，其构造过程是以质心C和半径r分割样本空间，每一个节点是一个超球体。一般低维数据用kd_tree速度快，用ball_tree相对较慢。超过20维之后的高维数据用kd_tree效果反而不佳，而ball_tree效果要好，具体构造过程及优劣势的理论大家有兴趣可以去具体学习。
[leaf_size] int参数，基于以上介绍的算法，此参数给出了kd_tree或者ball_tree叶节点规模，叶节点的不同规模会影响数的构造和搜索速度，同样会影响用于储存树的内存的大小。具体最优规模是多少视情况而定。
[matric] str或者距离度量对象，即怎样度量距离，前面有具体介绍。默认minkowski。
[p] int参数，就是以上闵氏距离各种不同的距离参数，默认为2，即欧氏距离。p=1代表曼哈顿距离等等。
[metric_params] 距离度量函数的额外关键字参数，一般不用管，默认为None。
[n_jobs] int参数，指并行计算的线程数量，默认为1表示一个线程，为-1的话表示为CPU的内核数，也可以指定为其他数量的线程，这里不是很追求速度的话不用管，需要用到的话去看看多线程。
KNN是一个特别容易理解的模型，因此，当需要一个特别容易解释的模型的时候，比如需要向用户解释原因的推荐算法，我们可以使用KNN。例如，我们可以使用knn算法做到比较通用的现有用户产品推荐，基于用户的最近邻（长得最像的用户）买了什么产品来推荐，是一种基于电子商务和sns的精确营销，只需要定期维护更新最近邻表就可以，基于最近邻表做搜索可以很实时。