机器学习-kNN算法

2019/03/27 机器学习 机器学习 KNN 邻近算法
  本文为「原创」内容,如需转载请注明出处!             
本文共 2945 字,需 36 分钟阅读

  邻近算法,或者说K最近邻(kNN,k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表。kNN 算法是一个分类算法,通过判断待测试样本与训练样本的距离来确定测试样本的类别。

准备

本文的样例和代码均来自于《机器学习实战》

https://pan.baidu.com/s/1Gc7BDmNyBfGQlfVvhzyZFw 提取码:ywuh

给定样本

序号 特征1 特征2 特征3 分类
1 0.8 400 0.5 1
2 12 134000 0.9 3
3 0 20000 1.1 2
4 67 32000 0.1 2

欧氏距离

\(N\) 维欧氏空间中两点 \((x_1,x_2)\) 两点的距离公式

\[\sqrt{\sum_{i=1}^{N}({x_1 - x_2})^2}\]

当 \(N=2\) 时,欧式距离即为标准差:

\[\sqrt{({x_1 - x_2})^2}\]

比如 样本3 和 样本4 之间的欧氏距离:

\[\sqrt{(0 - 67)^2 + (20000 - 32000)^2 +(1.1 - 0.1)^2}\]

数据归一化

由于样本的某些特征值数据范围过大(比如示例中的特征2)其对欧式距离的影响将会特别大,所以要将其归一化,数据归一的化的原理是将样本中的所有特征值的数据都变成 \([0,1]\) 范围内的数据,即

\[\acute{x_i} = \frac{x_i - min_i}{max_i - min_i}\]

其中 \(x_i\) 为样本 \(x\) 的第 \(i\) 个特征值,\(min_i\) 为所有样本中第 \(i\) 个特征值中的最小值,\(max_i\) 为样本中第 \(i\) 个特征值的最大值

算法思想

  1. 将特征数据归一化
  2. 计算测试数据与训练的每一个样本数据的距离
  3. 将距离有小到大排序取出前 k 个对应的样本数据
  4. 统计这 k 个样本里面频率最高的分类信息,该分类就是测试数据的分类

算法实现

数据归一化

    def autoNorm(dataSet):
        minVals = dataSet.min(0)
        maxVals = dataSet.max(0)
        ranges = maxVals - minVals
        normSet = zeros(shape(dataSet))
        m = dataSet.shape[0]
        normSet = dataSet - tile(minVals,(m,1))
        normSet = normSet / tile(ranges,(m,1))
        return normSet,ranges,minVals

kNN 实现

    # intX 为待测试的样本
    # dataSet 是归一化之后的数据
    # labels 为 dataSet 每一行的分类信息
    # k 要取得小距离样本的个数
    def classify0(intX,dataSet,labels,k):
        # 行数量
        size = dataSet.shape[0]
        # 样本 intX,重复 size 行 形成一个与 dataSet 维数一样的矩阵,然后做差
        diffMat = tile(intX,(size,1)) - dataSet
        # 每个差值取平方
        sqDiffMat = diffMat ** 2
        # aixs=1 表明对差方矩阵的行求和
        # 一行数据变成 1 个,相当于算出输入样本和训练样本每行的距离
        sqDistance = sqDiffMat.sum(axis=1)
        distance = sqDistance ** 0.5
        # argSort 返回的是索引,其对应的值从小到大
        sortIndicies = distance.argsort()
        classCount = {}
        # 取出前 k 个小距离对应的标签
        for i in range(k):
            voteLabel = labels[sortIndicies[i]]
            classCount[voteLabel] = classCount.get(voteLabel,0) +1
        # 取出所有标签中频率最高的标签
        sortedClassCount = sorted(classCount.items(),
             key=operator.itemgetter(1), reverse=True)
        return sortedClassCount[0][0]

测试算法

    # 注:用到的datingTestSet2.txt 为《机器学习实战》的示例数据
    def datingClassTest():
        matrix,labels = KNN.file2matrix("Ch02/datingTestSet2.txt")
        hoRatio = 0.10
        normMat,ranges,minVals = KNN.autoNorm(matrix)
        m = normMat.shape[0]
        numTestVecs = int(m * hoRatio)
        errorCount = 0
        for i in range(numTestVecs):
            result = KNN.classify0(normMat[i,:],normMat[numTestVecs:m,:],
                        labels[numTestVecs:m],3)
            if(result != labels[i]):
                errorCount += 1.0
            print("train: %d, real: %d",(result,labels[i]))
        print("error count: %f",errorCount / float(numTestVecs))
        return

knn-test

搜索

    文章目录