K最邻近算法

一颗蔬菜 2019-09-14 AM 74℃ 0条

概述

K最临近算法(K-nearest neighbours, KNN)通过计算样本与样本集中其他样本的距离来确定样本的属性。

K最邻近算法主要用于分类(推荐)和回归(预测)。

K的值和特征抽取对KNN算法影响很大。

距离计算

  1. 余弦相似度
  2. 欧拉算法
  3. 曼哈顿算法
  4. 明可夫斯基算法

特征抽取

K最邻近算法需要抽取样本的特征。

分类

确定样本的属性。

分类的应用

推荐系统,例如购物软件会针对用户推荐物品。

购物软件会记录用户的浏览和购买记录,我们可以分析出用户喜欢不同物品的程度。

我们将喜欢程度分为5个等级。现在我,需要根据已有样本集(A、B、C、D)来给样本E推荐物品。

用户衣服美食电子产品运动
A用户2541
B用户1542
C用户5124
D用户4214
E用户5225

使用毕达哥拉斯公式来计算样本E和其他样本之间的距离:

$$ \sqrt{(x_1-x_2)^2+(y_1-y_2)^2+...+(z_1-z_2)^2} $$

A与E之间的距离:

$$ \sqrt{38} $$

B与E之间的距离:

$$ \sqrt{38} $$

C与E之间的距离:

$$ \sqrt{2} $$

D与E之间的距离:

$$ \sqrt{3} $$

从距离来看,可以把E用户和C、D用户划为一类。将C、D用户最近浏览和购买的物品推荐给D。

回归

回归就是根据已知的样本数据预测未知样本数据。

示例

预测系统,饭店在购买食材时会预测需求量,根据预测的需求量去购买相应的食材。

饭店的生意受天气、节假日的影响较大,我们可以将这个两个指标作为特征。

天气用1到5来表示,数值越大天气越好。

节假日用0和1来表示,0表示非节假日,1表示节假日。

日期天气节假日需求量
151100
23180
35060
43040
51020
640?

现在,我们来预测日期6的需求量。

使用毕达哥拉斯公式来计算与日期6距离最邻近的日期。

日期1和日期6之间的距离:

$$ \sqrt{2} $$

日期2与日期6之间的距离:

$$ \sqrt{2} $$

日期3与日期6之间的距离:

$$ \sqrt{1} $$

日期4与日期6之间的距离:

$$ \sqrt{1} $$

日期5与日期6之间的距离:

$$ \sqrt{9} $$

日期3和日期4与日期6的距离最小,K值为2,因此我们预测日期6的需求量为50。

标签: 算法

非特殊说明,本博所有文章均为博主原创。