前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >机器学习(5)——KNNKNNKD Tree

机器学习(5)——KNNKNNKD Tree

作者头像
DC童生
发布2018-04-27 17:45:51
6340
发布2018-04-27 17:45:51
举报
文章被收录于专栏:机器学习原理

前言:KNN算法以一种“物以类聚”为思想的方法,它不同于前面提到的回归算法,没有损失函数,通过判断预测值离的远近来预测结果。主要分为KNN算法和KD-Tree来说明

KNN

  • 算法原理 1.从训练集合中获取K个离待预测样本距离最近的样本数据; 2.根据获取得到的K个样本数据来预测当前待预测样本的目标属性值。 3.KNN在做回归和分类的主要区别在于最后做预测的时侯的决策方式不同。KNN在分类预测时,一般采用多数表决法;而在做回归预测时,一般采用平均值法。
  • KNN三要素 1.K值的选择:对于K值的选择,一般根据样本分布选择—一个较小的值,然后通过交叉验证来选择一个比较合适的最终值;当选择比较小的K值的时候,表示使用较小领域中的样本进行预测,训练误差会减小,但是会导致模型变得复杂,容易过拟合;当选择较大的K值的时候,表示使用较大领域中的样本迸行预测,训练误差会增大,同时会使模型变得简单,容易导致欠拟合; 2.距离的度量:一般使用欧氏距离(欧几里得距离) 代码如下:
代码语言:javascript
复制
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.决策规则:在分类模型中,主要使用多数表决法或者加权多数表决法;在回归模型中,主要使用平均值法或者加权平均值法。 一般采用权重和距离成反比

手写KNN算法:

代码语言:javascript
复制
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作为样本的划分点,对于小于该值的样本划分到左子树,对于大于等于该值的样本划分到右子树,对左右子树采用同样的方式找方差最大的特征作为根节点,递归即可产生 如图:
  • 查找最邻近

最后附上sikit-learn包中的一些参数的含义:

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.03.11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • KNN
  • KD Tree
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档