toBeTheLight.github.io 荒原

阅读:《算法图解》(6)k最近邻算法

2018-02-04
toBeTheLight

k最近邻算法(KNN,K-NearestNeighbor)————所谓K最近邻,就是K个最近的邻居的意思,说的是每个样本都可以用它最接近的K个邻居来代表。
最近邻居法采用向量空间模型来分类,概念为相同类别的案例,彼此的相似度高,而可以借由计算与已知类别案例之相似度,来评估未知类别案例可能的分类。

第十章 k最近邻算法

橙子还是柚子

我们将橙子和柚子使用颜色和个头特征进行图表建模,将待判断水果放入此模型中,查找距离它最近的几个邻居,根据橙子和柚子个数的多少来判断此水果更可能是什么,这就是KNN算法分类的使用。

要对物品进行分类时可使用这种算法。

创建推荐系统

根据模型将目标用户喜好相似用户的爱好推荐给目标用户,这也是KNN算法的应用。

特征抽取

我们进行建模的时候应该有一定的标准,这个时候就涉及到特征提取了。
在橙子还是柚子部分我们可使用颜色和个头进行二维(空间)数据的建模(x, y)。然后用毕达哥拉斯公式求取距离,即: √ ̄(x1-x2)^2 + (y1-y2)^2 // 同维数据差的平方和开平方

那么对于较为复杂的建模我们可以使用多维(空间)数据进行建模(v, w, x, y, z),同样可使用毕达哥拉斯公式求取距离,来比较相似度。

我们还有余弦相似度的比较方式,一种以角度而非距离进行比较的公式(比如用来比较爱好相同,但打分规则权重不同的用户,都喜欢A,但是一个打4分,一个打5分,使用距离公式可能不是邻居)。

回归

KNN可以做两项基本工作:分类和回归。

  • 分类就是编组
  • 回归就是预测结果

应用:

  • 我们在推荐系统中找到目标的最近邻居之后,根据这些邻居的分值就可以预测出目标可能打出的分值。
  • 我们可以对餐厅之前的出餐数据进行根据天气、工作日、是否由活动进行建模来预测明天的出餐量(找k个最近邻,计算出餐量的平均值),来准备原料。

我们选择目标的最近邻居时的个数就是(KNN的)K值,这也是名字的由来。

机器学习

应用简介

  • OCR:光学字符识别
    1. 浏览大量的文字图像,将这些文字的特征提取出来。
    2. 遇到新图像时,提起该图像的特征,找出它最邻近的邻居都是谁。
  • 垃圾邮件过滤
  • 预测股市
    • 涉及的变数太多的数据是几乎不可能完成预测的。 大多数机器学习算法都包含训练的步骤,提取特征的过程就是训练的过程。

小结

  • KNN用于分类和回归,需要考虑最近的邻居。
  • 分类就是编组。
  • 回归就是预测结果。
  • 特征抽取意味着将物品转换为一系列可比较的数组。
  • 能否挑选合适的特征事关KNN算法的成败。
  • 如果有N位用户,应考虑sqrt(N)个邻居。

相关文章

Content