前言：KNN算法以一种“物以类聚”为思想的方法，它不同于前面提到的回归算法，没有损失函数，通过判断预测值离的远近来预测结果。主要分为KNN算法和KD-Tree来说明
KNN
- 算法原理
1.从训练集合中获取K个离待预测样本距离最近的样本数据;
2.根据获取得到的K个样本数据来预测当前待预测样本的目标属性值。
3.KNN在做回归和分类的主要区别在于最后做预测的时侯的决策方式不同。KNN在分类预测时,一般采用多数表决法;而在做回归预测时,一般采用平均值法。 - KNN三要素
1.K值的选择:对于K值的选择,一般根据样本分布选择—一个较小的值,然后通过交叉验证来选择一个比较合适的最终值;当选择比较小的K值的时候,表示使用较小领域中的样本进行预测,训练误差会减小,但是会导致模型变得复杂,容易过拟合;当选择较大的K值的时候,表示使用较大领域中的样本迸行预测,训练误差会增大,同时会使模型变得简单,容易导致欠拟合;
2.距离的度量:一般使用欧氏距离(欧几里得距离)
代码如下：
def point_Distance(x1,y1,x2,y2):
d = math.sqrt(math.pow((x1-x2),2)+math.pow((y1-y2),2))
return d
a_d = point_Distance(18,90,3,104)
print(a_d)
3.决策规则:在分类模型中,主要使用多数表决法或者加权多数表决法;在回归模型中,主要使用平均值法或者加权平均值法。
一般采用权重和距离成反比
image.png
手写KNN算法：
import math
import csv
import operator
import random
def loadDataset(fileName,split,trainingSet=[],textSet=[]):
with open(fileName, "r") as f:
reader = csv.reader(f)
data = list(reader)
for x in range(len(data) - 1):
for y in range(4):
data[x][y] = float(data[x][y])
if random.random() < split:
trainingSet.append(data[x])
else:
textSet.append(data[x])
return trainingSet,textSet
# print(trainingSet)
# print(textSet)
# trainingSet,textSet=loadDataset("irisdata.csv",0.7)
# print(trainingSet)
# print(textSet)
def euclideanDistence(instance1,instence2,length):
distance = 0
for x in range(length):
distance += pow(instance1[x]-instence2[x],2)
return math.sqrt(distance)
# s = euclideanDistence([1,2,3],[4,5,6],3)
# print(s)
'''
去测试集一个数据，放到训练集中，给定一个k，返回k个训练集（这k个训练集的值就是离这个测试集最近的k个点）
'''
def getNeighbors(trainingSet,textInstance,k):
distane = []
length = len(textInstance)-1
for x in range(len(trainingSet)):
dist = euclideanDistence(trainingSet[x], textInstance, length)
distane.append((trainingSet[x],dist))#append只能传一个参数，用括号括起来
distane1 = sorted(distane,key=operator.itemgetter(1))#排序
neighbors = []
for x in range(k):
neighbors.append(distane1[x][0])
return neighbors
# print(neighbors)
'''
对返回的结果进行分类累加
对返回的最近的数进行判断，是不是和textinstance相符
'''
def getResponse(neighbors):
classVators = {}
for x in range(len(neighbors)):
response = neighbors[x][-1]
if response in classVators:
classVators[response] +=1
else:
classVators[response]=1
sortVators = sorted(classVators.items(),key=operator.itemgetter(1),reverse=True)
# print(classVators)
return sortVators[0][0]
'''
计算正确率
'''
def getAccuracy(textSet,predictions):
corret = 0
for x in range(len(textSet)):
if textSet[x][-1] == predictions[x]:
corret += 1
return (corret/len(textSet))*100
#判断正确率的主函数
def main1():
trainingSet,textSet=loadDataset("irisdata.csv",0.8)
predictions = []
for x in range(len(textSet)):
neighbors=getNeighbors(trainingSet,textSet[x],6)
sortVators = getResponse(neighbors)
predictions.append(sortVators)
re = getAccuracy(textSet,predictions)
print(re)
main1()
当然引入sikit-learn包更加简单
KD Tree
KD Tree是KNN算法中用于计算最近邻的快速、便捷构建方式。当样本数据量少的时候,我们可以使用 brute这种暴力的方式进行求解最近邻即计算到所有样本的距离。但是当样本量比较大的时候,直接计算所有样本的距离,工作量有点大,所以在这种情况下,我们可以使用 kd tree来快速的计算。
-
KD Tree的构建
KD树采用从m个样本的n维特征中,分别计算n个特征取值的方差,用方差最大的第k维特征n作为根节点。对于这个特征,选择取值的中位数n作为样本的划分点,对于小于该值的样本划分到左子树,对于大于等于该值的样本划分到右子树,对左右子树采用同样的方式找方差最大的特征作为根节点,递归即可产生
如图：
image.png -
查找最邻近
image.png
最后附上sikit-learn包中的一些参数的含义：
image.png
