算法图解阅读笔记——第五曲（动态规划和K最近邻算法）

灰太狼 2021-05-12 11:50 421阅读 0赞

#### 目录结构 ####

第9章 动态规划

第10章 K最近邻算法

--------------------

#### 正文 ####

## 动态规划 ##

### 动态规划思想 ###

*  动态规划先将问题分成小问题，先解决这些小问题，在逐步解决大问题。

### 动态规划的使用条件 ###

1.  动态规划不适合处理商品的部分问题：**使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而没发判断该不该拿走商品的一部分。**
2.  动态规划不适合处理相互依赖的情况：**仅当每个子问题都是离散的，动态规划才管用。**

### 使用动态规划计算背包问题的最优解 ###

*  之前使用贪婪算法无法求得背包问题的最优解，只能计算出近似解。【必须在背包容量给定的情况下，偷到价值最高的商品】而使用动态规划可以快速计算出背包问题的最优解。（可根据书本中例子，一步步画网格）

## k最近邻算法 ##

### 什么是K最近邻算法 ###

*  K最近邻算法，就是常说的KNN算法，不管是分类也好，回归也好，假设现在有一个点，我们不知道它的情况，可以根据离这个点最近的K个邻居判断它的情况，正所谓近朱者赤，近墨者黑。

### 使用K最近邻可以创建推荐系统 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center]

*  假设你现在是O，将你和其他用户放入创建的图表中，现在需要给你推荐电影，那么我们先采用KNN算法找出和O最近的K个邻居，现在 k = 5 k=5 k=5，我们找出了和O最近的5位邻居，分别为②、③、⑤、⑦、⑧。
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 1]
 *  因为②、③、⑤、⑦、⑧和O很相似，那么我们将他们喜欢的电影推荐给O即可。

**特征抽取**

因为需要对上述对象放入表中，并计算他们的距离，判断是否相近，那么需要将原本使用文字描述的量转为数字量【**将物品描述转换为一系列可靠的数字**】

**特征选择**

*  假设我们是做一个关于电影的推荐系统，那么我们挑选的特征：
    
     *  与推荐的电影密切相关的特征；
     *  不偏不倚的特征（如，只让用户给喜剧片打分，就无法判断他们是否喜欢动作片）

### KNN的使用场景 ###

*  分类：就是分组（编组）
 *  回归：预测结果（预测具体数字）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20210511/ac26965c01d44bef9eaec9a46615bc6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210511/f0d82648093b482988f216de4e9109d9.png