机器学习笔记:k-近邻算法

By on 2018-01-25

开篇在这《机器学习笔记:开始》

一、k-近邻算法简介

k-近邻算法是用来测量多个特征值之间的距离方法进行分类。不懂是吧,先举个例子: 你是如何区分一部电影是爱情片,还是动作片(还是爱情动作片【/坏笑】)我们通过计算打斗次数和亲吻次数来对这两类电影做个区分。先找出几部历史有明确区分的电影来。

电影名称 打斗次数 亲吻次数 分类
速度与激情8 35 5 动作片
尖峰时刻3 45 6 动作片
泰坦尼克号 2 23 爱情片
美丽人生 0 11 爱情片

那么,电影A,其中打斗30次,亲吻8次,那么它应该属于哪一类电影呢?让计算机如何判断呢? 思路:把每一步已分类电影想象成坐标轴上的点,横轴上打斗次数,纵轴是亲吻次数。计算电影A在坐标轴上,与各点的距离,并取与其距离最近的k个点(这里假设k=2),看k个点中,哪一类电影多。则判断电影A为哪一类。

二、k-近邻算法概述

k-近邻(kNN)算法的工作原理:存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据与所属分类都对应关系。输入没有标签都新数据后,将新数据的每个特征与样本集中数据对应都特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)都分类标签,作为新数据的分类
+ 优点:精度高、对异常值不敏感、无数据输入假定
缺点:计算复杂度高、空间复杂度高
* 适用数据范围:数值型 和 标称型

三、k-近邻算法实现

第一部分适用于小白,这部分就是给懂python的老白了。先给出算法的逻辑:
1. 计算已知类别数据集中的点与当前点之间的距离
2. 按照距离递增次序排序
3. 选取与当前点距离最近的k个点
4. 确定前k个点所在类别的出现频率
5. 返回前k个点出现频率最高点类别作为当前点点预测分类

Python函数代码如下:

#参数说明
# inX:需要判断的点(即电影A)
# dataSet: 已分类的点集合(即已经分类点电影集合)
# labels: dataSet点中,每一个点对应的类型
# k: 取前k个与inX距离最近的点,通常k不大于10
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]

    #计算距离, 求两个点之间点距离,大家还记得不?求两个向量点距离呢?
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5

    sortedDistIndicies = distances.argsort()

    #选择距离最小的k个点
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1

    #排序
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

后面心情好了再补代码解读及数理知识的内容,我先去学下一课了————“决策树算法”