机器学习算法-KNN

发布于 2020-09-18  129 次阅读


k-近邻算法(KNN)

KNN的思路

KNN是通过测量不同特征值之间的距离进行分类。如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别,其中K通常是不大于20的整数。可以思考画圈,就是类似画圈的思路,由此也说明了KNN算法的结果很大程度取决于K的选择。
在KNN中,通过计算对象间距离来作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧氏距离或曼哈顿距离:
$$d(x,y)=\sqrt{\sum_{k=1}^{n}\left (x_{k}-y_{k} \right )^{2}}$$
$$d(x,y)=\sqrt{\sum_{k=1}^{n}\left |x_{k}-y_{k} \right |}$$

KNN的注意

  1. 数据要归一化:因为计算距离时某些数字差值过大的数值会主导结果,所以要对数值进行归一化处理,即$data=\frac{data-min}{max-min}$,这样就使数据处在0-1之间,方便处理
  2. K值选取会产生过拟合,正如把圆的半径增大后,圈进去的会更多,尽管训练准确率增加,但是测试准确率不会增加

KNN的代码

部分重要代码

# 返回k范围内与测试值最近的类别
def KNNtest(testdata, testgroup, testlables, k):
    distance = np.array([])
    for i in range(testgroup.shape[0]):
        distance = np.append(distance, (np.linalg.norm(testdata - testgroup[i, :])))
    sort = distance.argsort()
    counttable = {}
    for i in range(k):
        if testlables[sort[i]] in counttable:
            counttable[testlables[sort[i]]] += 1
        else:
            counttable[testlables[sort[i]]] = 1
    return max(counttable.items(), key=lambda x: x[1])[0]
# 归一化处理
def autonorm(data):
    for i in range(data.shape[1]):
        min = np.min(data[:, i])
        max = np.max(data[:, i])
        data[:, i] = (data[:, i] - min) / (max - min)
    pass

全部代码

# KNNtest.py
import numpy as np


def startKNNtest():
    testgroup = np.array([[1, 1, 2], [1, 1.1, 4], [0, 0.1, 1], [0, 0, 5]])
    testlables = ['a', 'b', 'a', 'b']
    return testgroup, testlables


def KNNtest(testdata, testgroup, testlables, k):
    distance = np.array([])
    for i in range(testgroup.shape[0]):
        distance = np.append(distance, (np.linalg.norm(testdata - testgroup[i, :])))
    sort = distance.argsort()
    counttable = {}
    for i in range(k):
        if testlables[sort[i]] in counttable:
            counttable[testlables[sort[i]]] += 1
        else:
            counttable[testlables[sort[i]]] = 1
    return max(counttable.items(), key=lambda x: x[1])[0]


if __name__ == "__main__":
    group, lables = startKNNtest()
    print(KNNtest(np.array([5, 5, 5]), group, lables, 2))

# date.py
# -*- coding:utf-8 -*-
import KNN.KNNtest as KNN
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.pyplot import MultipleLocator


def readfile():
    filename = 'datingTestSet2.txt'  # txt文件和当前脚本在同一目录下,所以不用写具体路径
    pos = []
    Efield = []
    with open(filename, 'r') as file_to_read:
        while True:
            lines = file_to_read.readline()  # 整行读取数据
            if not lines:
                break
                pass
            p1_tmp, p2_tmp, p3_tmp, E_tmp = [float(i) for i in
                                             lines.split()]  # 将整行数据分割处理,如果分割符是空格,括号里就不用传入参数,如果是逗号, 则传入‘,'字符。
            pos.append([p1_tmp, p2_tmp, p3_tmp])  # 添加新读取的数据
            Efield.append(E_tmp)
            pass
    pos = np.array(pos)  # 将数据从list类型转换为array类型。
    Efield = np.array(Efield)
    return pos, Efield


def autonorm(data):
    for i in range(data.shape[1]):
        min = np.min(data[:, i])
        max = np.max(data[:, i])
        data[:, i] = (data[:, i] - min) / (max - min)
    pass


def startKNN(data, lables):
    pltx = []
    plty = []
    autonorm(data)
    k = int(0.7 * (data.shape[0]))
    traindata = data[0:k, :]
    trainlables = lables[0:k]
    testdata = data[k:, :]
    testlables = lables[k:]
    testfalse = testdata.shape[0]
    besttest = 1
    for test in range(1, 20):
        false = 0
        for i in range(testdata.shape[0]):
            if testlables[i] != KNN.KNNtest(testdata[i, :], traindata, trainlables, test):
                false += 1
        pltx.append(test)
        plty.append(false / testdata.shape[0])
        if false <= testfalse:
            testfalse = false
            besttest = test
    plt.plot(pltx, plty, 'g-')  # 绿色折线
    ax = plt.gca()
    # ax为两条坐标轴的实例
    ax.xaxis.set_major_locator(MultipleLocator(1))
    plt.show()
    return testfalse / testdata.shape[0], besttest


data, lables = readfile()
print(startKNN(data, lables))


#数据集以txt形式存储
40920   8.326976    0.953952    3
14488   7.153469    1.673904    2
26052   1.441871    0.805124    1
75136   13.147394   0.428964    1
38344   1.669788    0.134296    1
72993   10.141740   1.032955    1
35948   6.830792    1.213192    3
42666   13.276369   0.543880    3
67497   8.631577    0.749278    1
35483   12.273169   1.508053    3
50242   3.723498    0.831917    1

代码说明

因为自己没有按照书给的代码抄,都是按照自己的理解然后重新写的代码,所以可能会有出入或者性能问题,还希望谅解

总结

因为KNN比较简单而且好理解,所以作为我第一个上手的机器学习的算法,其实它是懒惰学习的代表,它并没有进行迭代等其他算法有的步骤,其唯一可能就是探索最佳的k或者交叉验证的比值而已,而且缺点很明显,因为都需要计算距离,当点数过多时候会很慢,所以决策树算法解决了这个问题,也是下一篇的内容


浪子三唱,不唱悲歌