锐客网

  1. 首页 > 睿知 > it技术 > >

KNN算法

IT知识KNN算法

亦余心之所善兮，虽九死其犹未悔。这篇文章主要讲述KNN算法相关的知识，希望能为你提供帮助。
KNN算法 问题提出【KNN算法】依旧是分类问题，现在有了一数据集，数据集中的每个数据都有一个标签，那么多对于一个新的数据，他应该是属于哪个集合，也就是说他的标签应该是什么？
例子比如当前这个图，红色的点具有标签A，蓝色的点具有标签B，现在来了一个新的点黑色点，那么这个黑色的点应该属于那一类？
直观的来看，黑色的点应该是属于红色标记的点。也就是标签应该是A，因为一个很直观的感受就是它距离红色的点近，根据物以类聚，人以群分的概念它应该是红色点集合内的。
算法的提出为了解决上述分类的问题，提出了KNN（k-NearestNeighbor）算法，也就是k近邻算法。算法的核心思想就是找距离当前点最近的k个点，这个距离可以有多种定义，一般都是在n维空间的欧几里得距离，当然也可以被定义为其他形式下的距离。然后统计这k个点里面哪种标记最多，就把该点归类为最多的标记点
算法实现步骤根据上面的描述，首先第一步就是要确定k，确定选取多少个点来做参考。那么这个k最好不要是标记种类数的倍数。什么意思？举个例子，就像刚才上面的那个图，k最好选取奇数，因为当前数据集中存在两个标签，如果k选取偶数，那么一旦发现计算得到的k个数据中两种标签数量相等，那么就很难说把这个点分给谁了。确定k之后，就计算每个点到该该点的距离，然后排序，统计这k个中标签数量最多的是哪一个。这样就完成了
代码实现

"""
x_test:测试数据
x_data:训练集的x向量
y_data:训练集的结果
k:选取的邻居的个数
"""
def knn(x_test,x_data,y_data,k):
x_data_size = x_data.shape[0]# numpy的行数
# print(x_data_size)
x_copy = np.tile(x_test, (x_data_size, 1))
diffMat = x_copy - x_data# 差值的数据
sqDiffMat = diffMat ** 2
# print(sqDiffMat)
sqDisstance = sqDiffMat.sum(axis=1)
distance = sqDisstance ** 0.5
# print(distance)
sortedDistance = distance.argsort()# 得到的是distacne的索引
classCount =
k = 5
# 统计每种标签各出现了多少次
for i in range(k):
votelabel = y_data[sortedDistance[i]]
classCount[votelabel] = classCount.get(votelabel, 0) + 1# 如果这个键不存在，就赋值为0
# print(classCount)
# 从小到大排序
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
# print(sortedClassCount)
knnclass = sortedClassCount[0][0]# 取到出现最多的标签
return knnclass

使用knn，做一下iris数据集的分类
# coding=utf-8
import numpy as np
from sklearn import datasets
from sklearn.metrics import classification_report,confusion_matrix
import operator
import random
"""
x_test:测试数据
x_data:训练集的x向量
y_data:训练集的结果
k:选取的邻居的个数
"""
def knn(x_test,x_data,y_data,k):
x_data_size = x_data.shape[0]# numpy的行数
# print(x_data_size)
x_copy = np.tile(x_test, (x_data_size, 1))
diffMat = x_copy - x_data# 差值的数据
sqDiffMat = diffMat ** 2
# print(sqDiffMat)
sqDisstance = sqDiffMat.sum(axis=1)
distance = sqDisstance ** 0.5
# print(distance)
sortedDistance = distance.argsort()# 得到的是distacne的索引
classCount =
k = 5
# 统计每种标签各出现了多少次
for i in range(k):
votelabel = y_data[sortedDistance[i]]
classCount[votelabel] = classCount.get(votelabel, 0) + 1# 如果这个键不存在，就赋值为0
# print(classCount)
# 从小到大排序
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
# print(sortedClassCount)
knnclass = sortedClassCount[0][0]# 取到出现最多的标签
return knnclass
# print(knnclass)
iris=datasets.load_iris() #load进来的是一个字典
# print(iris.data)
datasize=iris.data.shape[0]
index=[i for i in range(datasize)] #生成一个索引列表
# print(index)
random.shuffle(index) #随机打乱
iris.data=https://www.songbingjia.com/android/iris.data[index]
iris.target=iris.target[index]

test_size=40
x_train=iris.data[test_size:]
x_test=iris.data[:test_size]
y_train=iris.target[test_size:]
y_test=iris.target[:test_size]
predictions=[]
for i in range(x_test.shape[0]):
predictions.append(knn(x_test[i],x_train,y_train,5))
print(classification_report(y_test,predictions))
print(confusion_matrix(y_test,predictions))

实现的缺点其实这样实现的knn并不完善，因为时间复杂度太高，只是做了一个示范，真正的knn应该采用KD Tree实现。KD tree是一种查询k近邻的强有力的数据结构，是一种二叉查找树，每个节点存了一个数组，查找的时候按照某个关键字搜索，时间复杂度n*logn.速度很快。
Sklearn解决上述问题Sklearn里面也封装了knn算法，可以看一下内部实现

这是sklearn关于KNeighborsClassifier的描述，算法采用了四种实现方式，auto，ball_tree,kd_tree,brute.会根据数据量来自动选择。
采用sklearn提供的接口，那么就很easy。使用哦个sklearn做iris的分类：
# coding=utf-8
from sklearn import datasets

    推荐阅读


    上一篇：WebpackTypeError: Cannot read property ‘tap‘ of undefined at HtmlWebpackPlugin.

    下一篇：BZOJ 4001[TJOI2015]概率论