KNN

概述

简单的说,K-近邻算法采用测量不同特征值之间的距离方法进行分类.

工作原理: 存在一个样本数据集合, 也称作训练样本集, 并且样本集中的每个数据都存在标签(即我们知道样本集中每一数据与所属分类的对应关系),输入没有标签的新数据后.将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)的分类标签.

特性:

优点: 精度高,对异常值不敏感,无数据输入假设
缺点,计算复杂度高,空间复杂度高
使用数据范围: 数值型和标称型.

举例

使用KNN 分类爱情片和动作片.基于电影中出现的亲吻,打斗出现的次数,使用k-近邻构造程序.

训练样本集:

A 打斗镜头: 3 接吻镜头: 104 电影类型 : 爱情片
B 打斗镜头: 2 接吻镜头: 100 电影类型 : 爱情片
C 打斗镜头: 1 接吻镜头: 81 电影类型 : 爱情片
D 打斗镜头: 101 接吻镜头: 10 电影类型 : 动作片
E 打斗镜头: 99 接吻镜头: 5 电影类型 : 动作片
F 打斗镜头: 98 接吻镜头: 2 电影类型 : 动作片
G 打斗镜头: 18 接吻镜头: 90 电影类型 : ?

已知类型电影 (A,B,C,D,E,F) 与未知类型电影(G) 的距离如下. 距离怎么定义的?? (二维空间的绝对距离?)

A 与 G 的距离 : 20.5
B 与 G 的距离 : 18.7
C 与 G 的距离 : 19.2
D 与 G 的距离 : 115.3
E 与 G 的距离 : 117.4
F 与 G 的距离 : 118.9

现在得到了样本集中所有电影与未知电影的距离,按照距离递增排序, 可以找到k个距离最近的电影.
假设k=3, 则最近的三个电影依次为: F,E,D. 而这三个都是爱情片, 因此我们判断未知电影为爱情片.

算法实现

收集数据
准备数据: 距离计算所需要的数值,最好是结构化的数据格式
分析数据
训练算法: k近邻不适用
测试算法: 计算错误率
使用算法

这里只介绍最后的算法使用步骤:实施KNN分类算法.

主要函数功能为: 使用k-近邻算法将每组数据划分到某个类别中.步骤如下

对未知类别属性的数据集中的每个点依次执行以下操作:
1. 计算已知类别数据集中的点与当前点之间的距离
2. 按照距离递增次序排序
3. 选取与当前点距离最小的k个点
4. 确定前k个点所在类别的出现频率 
5. 返回前k个点出现频率最高的类别作为当前点的预测分类.

python函数如下:

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    // 距离计算
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    disstances = sqDistances.argsort()
    classCount={}
    // 选择距离最小的k个点
    for i in rang(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

其它代码见:https://github.com/quantumcs/Machine-Learning-In-Action

算法测试

有关数据收集

文本数据的转换及处理
etc.

其它的一些应用

约会网站的配对
手写识别系统

问题

1. 一个简单的模型,存在的问题

现有一个模型, 针对每个新的句子,使用相似度算出与已知样本集中每个句子的相似度. 而已知样本集只有一个类别(也就是说都是负样本). 取最大的相似度值,和阈值比较,大于阈值的定义同一个类别,小于阈值的定为不同类别.

存在的问题: 1. 没有考虑正样本,这个策略效果肯定存在提升. 2. 另外的提升思路: 对句子做预处理,去除变化较大的实体,降低对相似性的影响.