机器学习(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.距离的度量:一般使用欧氏距离(欧几里得距离) 代码如下：

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算法：

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作为样本的划分点,对于小于该值的样本划分到左子树,对于大于等于该值的样本划分到右子树,对左右子树采用同样的方式找方差最大的特征作为根节点,递归即可产生如图：