I'll try anything once

人生苦短,何妨一试

k-NN(k近邻模型)

简介

k-NN是一个分类算法,在给定一个已经做好分类的数据集之后,k-NN可以学习其中的分类信息,并自动给尚未分类的类似数据进行分类。
分类是一种常见的问题,譬如将电影分为好看和不好看,将个人分为高信用、低信用,酒店分为一二三四五星等。分类问题部分也可变相的通过线性回归进行解决,由于线性回归返回的连续的实数值,所以可以设定具体的阀值,然后将连续的数值离散化即可。
其中主要的思想为

先验信息-数据的标准化

对于数据的标准化可以有效的降低一些一些特征的数值过大导致对整体决策的影响。
表一

(姓名) (年龄) (收入)
A 35 75000
B 52 55000
C 27 45000
D 37 115000

表二

(姓名) (年龄) (收入)
E 53 70000
F 25 105000
G 35 69000
H 48 43000

单单目测的话,若是给表一中的A推荐的话,那么表二中的G最为适合,但是计算距离的话,反而E最为接近,两者年龄差过多,这样的推荐肯定是不可行的。

  • 将数值投射到0-1

    • 拿整个数据组的最大值和最小值的到范围差,所有的数据减去最小值,然后除以范围差即可。如上两个表中最大值为11500,最小值为4300,得到范围差为7200,则A的标准化结果为(7500-4300)/7200 = 0.444
  • 标准分(方差)

    • 计算平均分,之后计算标准差(方差),之后将对应的单个数据减去平均分,然后除以标准差即可
    • 如上两表的平均值为72125,计算出的标准差为24543.01,则A的标准分为(75000-72125)/24543.01=0.117
    • 但是对于标准分(方差)也有一些问题,譬如若是对于一整条数据集,单个数据过大,这样这单条数据就会对结果有很大的导向,譬如若是使用标准分来标准化整个公司所有人的收入,那么CEO的收入会应为过高而使得平局值没有太大的意义。由此可见如何处理品均值成为了问题
  • 修正标准分
    将标准分中的平均值改为中位数,标准差改为绝对偏差。

(姓名) (薪资)
A 43000
B 45000
C 55000
D 69000
E 70000
F 75000
G 105000
H 115000

中位数: (69000+70000)/2 = 69500
绝对偏差: {(|43000-69500|)+(|45000-69500|)+…+(115000-69500)}/8 = 19125
A的修正标准分 (75000-69500)/19125=0.2876

整体步骤

  • 确定相似性的定义(距离)
    • 欧式距离
      • 即欧拉距离,两者对应数字差的平方和开根号
    • 余弦相似度
      • 度量两个实数向量之间的相似程度,其结果[-1, 1]之间,其中-1表示完全不同,1表示完全相同,0表示两个向量完全独立。
    • Jaccard相似度
      • 其通常用于衡量两个集合之间的相似度。譬如wkk的朋友集合表示为A={Mike, Judy, Jone, Jan},kww的朋友集合表示为B={Mike, Judy, Army, Lambda},则两个朋友集合的Jaccard相似度为J(A∩B) = |A∩B|/|A∪B|
    • Mahalanobis距离
      • 也称为马氏距离,同样适用于两个实数向量,
    • Hamming距离
      • 主要用来衡量两个字符串,字组或者具有相同长度的DNA序列之间的相似程度。譬如oliveocean的Hamming距离为4,因为除了第一个字母相同,其他的字母均不相同。又如shoehose的Hamming距离为3,其计算方法简单,按照位置顺序,依次两两对比字母是否相同,若相同,Hamming距离+1,由此可以推断其约束条件为比较字符串需要等长
    • Manhattaan距离
      • 曼哈顿距离,其用来测量两个k维实数向量之间的距离,即对应的i维相减,然后求和取绝对值即可
    • 关于距离的选择
      • 如果数据存在分数膨胀 可以使用皮尔逊相关系数
      • 如果数据比较密集 变量之间存在公有值,且这些距离数据都非常重要,可以使用曼哈顿 欧几里得距离
      • 如果数据比较稀疏 可以使用余弦相似度
  • 将数据划分为训练集和测试集
  • 选择一个模型评价标准
  • 选择不同的k值应用于模型, 观察那个模型效果好
  • 基于定好的模型评价标准,选取k值
  • 进行样本外的测试

k-NN算法

k-NN算法的主要思想是根据所给的一条数据的特征,计算出与其相近的k条数据,然后根据着k条数据对应的分类结果来判断该条数据应该属于哪一个分类。
当然其也可以预测数值型的数据,譬如,预测A对歌手林俊杰的喜爱程度,目前已经计算出来了其3个近邻,分别为B C D,他们对林俊杰的评分分别为如下

用户 距离 评分
B 5 4
C 10 5
D 20 5

如果要预测出A对林俊杰的评分,可以计算B、C、D给出分数的加权平均,首先取倒数,得到对应的数据如下

用户 距离倒数 评分
B 0.2 4
C 0.1 5
D 0.05 5

然后对距离倒数进行统一标准化,sum=(0.2+0.1+0.05=0.35),然后得到结果如下

用户 权重 评分
B 0.57 4
C 0.29 5
D 0.14 5

所以最后得到的结果为0.57×4+0.29×5+0.14×5=4.43

  • 是否需要标准化
    是否需要标准化取决于特征数据分布

    • 需要根据数据的特征计算距离
    • 不同的特征之间尺度相差很大

确定相似性

获取中位数与绝对偏差

标准化数据

k-NN核心

预测分类结果

reference

  • 数据科学实战
  • 面向程序员的数据挖掘指南
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

11 − 9 =