【学习】数据挖掘—集体智慧编程

先做一个目录吧，不然实在太长了，连我自己都记不清楚

第二章 提供推荐
　　2.1 算法流程
　　2.2 基于用户进行过滤
　　　　2.2.1 搜集偏好
　　　　2.2.2 相似性度量方法
　　　　2.2.3 用户相似度计算
　　　　2.2.4 加权法构建推荐物品序列
　　2.3 基于物品进行过滤
　　　　2.3.1 提前构造物品字典相似矩阵
　　　　2.3.2 根据用户历史信息加权平均法构建推荐物品列表
　　2.4 其他概念
第三章 发现群组
　　3.1 算法流程
　　3.2 聚类的可视化
　　　　3.2.1 绘制树状图
　　　　3.2.2 多维缩放
　　3.3 其他概念
第四章 搜索与排名
　　4.1 算法流程
　　4.2 基于内容排名和PageRank算法
　　　　4.2.1 基于内容排名
　　　　4.2.2 PageRank算法
　　　　4.2.3 简单神经网络
第五章 优化
　　5.1 算法流程
　　　　5.1.1 随机搜索法
　　　　5.1.2 爬坡法
　　　　5.1.3 模拟退火法
　　　　5.1.4 遗传算法
　　5.2 有约束优化问题的建模理论
　　5.3 网络可视化问题的建模理论
第六章 文档过滤
　　6.1 算法流程
　　6.2 朴素贝叶斯分类器
　　　　6.2.1 合理推测
　　　　6.2.2 条件概率训练
　　　　6.2.3 朴素贝叶斯分类器
　　　　6.2.4 基于阈值比率和分类概率来选择分类
　　6.3 费舍尔分类器
　　　　6.3.1 合理推测
　　　　6.3.2 分类概率训练
　　　　6.3.3 费舍尔分类器
　　　　6.3.4 基于分类限值和分类概率来选择分类
　　6.4 特征值改进
第七章 决策树建模
　　7.1 算法流程
　　7.2 信息增益和增益率
　　　　7.2.1 熵和基尼不纯度
　　　　7.2.2 信息增益
　　　　7.2.3 增益率
　　7.3 根据增益率最大原则划分构造树
　　7.4 剪枝处理
　　　　7.4.1 预剪枝
　　　　7.4.2 后剪枝
　　7.5 连续值和缺失值的处理
　　　　7.5.1 连续值处理
　　　　7.5.2 缺失值处理
　　7.6 决策树可视化
第八章 构建价格模型
　　8.1 算法流程
　　8.2 相似度定义
　　　　8.2.1 参数缩放
　　　　8.2.2 参数优选
　　8.3 加权KNN初模型
　　　　8.3.1 反函数
　　　　8.3.2 减法函数（负斜率函数）
　　　　8.3.3 高斯函数（正态分布）
　　8.4 交叉验证
　　8.5 其他
第九章 高阶分类：核方法和SVM
　　9.1 算法流程
　　9.2 数据预操作
　　　　9.2.1 特征数据化
　　　　9.2.2 数据缩放处理
　　9.3 SVM模型
　　　　9.3.1 内积理论
　　　　9.3.2 核函数和核技巧
　　　　9.3.3 参数选择问题
　　9.4 预测分类
　　9.5 SVM划分多类问题
第十章 寻找独立特征（非负矩阵因式分解）
　　10.1 算法流程
　　10.2 构建数据矩阵
　　10.3 非负矩阵因式分解 NMF
　　10.4 结果呈现
第十一章 智能进化
　　11.1 算法流程
　　11.2 构造程序树
　　11.3 优化目标
　　11.4 遗传优化
　　11.5 确定最优程序
　　11.6 alpha go程序
第十二章 算法总结

第二章 提供推荐

2.1 算法流程

• 基于用户进行过滤：
  搜集偏好→确定相似性度量方法→用户相似度计算→加权平均法构建推荐物品列表
• 基于物品进行过滤：
  在小样本时，提前构造物品字典相似矩阵→获取用户历史信息→根据用户历史信息加权平均法构建推荐物品列表

2.2 基于用户进行过滤

2.2.1 搜集偏好

用户对历史影片的评价可以构建为：

image.png

2.2.2 相似性度量方法：

• 欧几里得距离评价：直接距离评价，经变换后，0~1之间
• 皮尔逊相关度评价：-1~1之间，协方差/标准差
  https://blog.csdn.net/u010095372/article/details/53932077
  https://blog.csdn.net/huangfei711/article/details/78456165
  以及其他相似性度量方法。
  （ps，皮尔逊相关度评价方法在数据不是很规范时，会得到更好的结果）

2.2.3 用户相似度计算

即采用度量方法进行计算。

2.2.4 加权法构建推荐物品序列

经相似度计算后，得到如下的权重列表：

image.png

影片D的预测评分为：（0.5 * 3+0.3 * 6）/(0.5+0.3)=4.125分
影片E的预测评分为：(0.5 * 5+0.3 * 4)/(0.5+0.3)=4.625分
最终推荐序列为：
（E，4.625分；D，4.125分）

2.3 基于物品进行过滤

2.3.1 提前构造物品字典相似矩阵

image.png

可以得到各个物品之间的相似度

2.3.2 根据用户历史信息加权平均法构建推荐物品列表

用户历史信息：

image.png

最终得出物品推荐：
（E，3.8；C，3.28；D，0.5；）

(ps,基于物品的推荐可以快速提供推荐列表，从而避免了临时的大规模计算，但是推荐的精准性依赖于前置的物品相似度计算。所以需要及时对物品相似度进行更新。）

2.4 其他概念：

协作型过滤：对一大群人进行信息搜索，并对其中各类人的偏爱进行考察和排名，从而确定哪些人具备相近的品味。

第三章 发现群组

对博客用户进行聚类：根据单词出现的频度对博客进行聚类，可以帮助我们分析出是否存在这样一类博客用户，这些人经常撰写相似的主题，或者在写作风格上十分相似。这样的分析结果对于搜索、分类和挖掘当前大量的在线博客而言是非常有价值的。

3.1 算法流程

• 分级聚类
  构建博客-单词矩阵（行为博客，列为单词在该博客中出现次数）→计算紧密度（相似度）→将最紧密的一组博客聚为一类，将单词出现次数的均值更新为新的单词频次（聚类中心更新）→反复聚类，直至所有聚类完成
• 列聚类
  构建单词-博客矩阵（行为单词，列为博客中该单词出现次数）→计算紧密度（相似度）→将最紧密的一组单词聚为一类，将单词出现次数的均值更新为新的单词频次（聚类中心更新）→反复聚类，直至所有聚类完成
• k均值聚类
  确定k的数目→随机生成k个聚类中心→数据寻找距离最近的中心点→聚类完成后，更新生成新的聚类中心→反复聚类，直至迭代完成

ps：1、分级聚类和列聚类都是层次聚类，由于每次都要重新计算紧密度，所以数据量很大。层次聚类和k聚类的用途其实是截然不同的。2、如果以博客单词做聚类分析，通常要进行单词处理，出现频次过低或过高的单词都没有太大意义，可以被剔除掉。

3.2 聚类的可视化

3.2.1 绘制树状图

适用于层次聚类的展示
https://blog.csdn.net/fengchi863/article/details/80537733
scipy包里面的dendrogram模块

3.2.2 多维缩放

适用于二维展示各个变量之间的距离
https://www.cnblogs.com/douza/p/5882065.html
需要注意的是，多维缩放无法完全展示紧密性，当最终无法再通过移动节点来减少总体误差的时候，变停止迭代了。

3.3 其他概念：

监督学习和无监督学习：神经网络、决策树、向量机、贝叶斯过滤都是监督学习，聚类、非负矩阵因式分解是无监督学习。

第四章 搜索与排名

介绍了一种全文的搜索引擎，允许人们在大量的文档中搜索出来一系列单词，并根据文档与单词的相关度对结果进行排名。

4.1 算法流程

• 基于内容的排名（传统算法）：
  对网址及其内容（文档中的单词）建立数据库和索引→针对搜索关键词的内容排名（单词频度/文档位置/单词距离）→评价值的归一化→输出排名

• PageRank算法：
  对网址及其内容（文档中的单词）建立数据库和索引→确定含有搜索关键词的网址→寻找指向该网址的外链，并利用外链计算PageRank值→输出排名（未归一化，PageRank值本身是一个无具体范围的数，但是如果要进行加权的话，也可以对最后的排名值进行归一化，而不是对PageRank值归一化）

• 基于外部回指连接的PageRank算法：
  对网址及其内容（文档中的单词）建立数据库和索引→确定含有搜索关键词的链接→寻找该网址指向的外链，并计算指向外链的PageRank值→输出排名

• 简单神经网络算法（不具备通用性）：
  设置输入层为全部搜索关键词的组合，3个单词的组合一共7组；隐藏层个数由单词组合决定（当有新的单词组合时，增加一个新的隐藏层，所以最多有7个）；输出层为全部网址及其对应排名值→选定输入到隐藏以及隐藏到输出均为S型函数（反双曲正切变换函数，-1~1），默认权重设置为：输入层到隐藏层1/len(wordids)，隐藏层到输出层0.1→比较输出值和期望值（选中某一网页即为1，未选中即为0），按照梯度为0.5更新两层的权重→完了（没有迭代！！所以相当于每次输入一组进去，然后就对应只更改一次权重。。。。。。）

PS：以上几种算法，可以各自设置权重并返回一个加权后的结果

4.2 基于内容排名和PageRank算法

4.2.1 基于内容排名

• 数据库和索引
  内容排名和PageRank算法会创建5张表，内容排名会用到3张表（剩下两张表之后说）：含有网址的表；含有word的表；含有网址、word以及word在网址中位置的表。

  
  image.png

加入索引是为了提高效率。

• 基于内容排名
  单词频度：最简单的思想，搜索的单词在网页中出现频率较高，则也有可能是我们要的页面。
  文档位置：文档的主题有可能会出现在靠近文档的开始处，统计单词在文档中出现的位置信息，位置越往前的就越有可能是我们想要的结果。
  单词距离：如果查询条件中有多个单词，则他们在文档中出现的位置应该很靠近。

4.2.2 PageRank算法

• 数据库和索引
  用到后面两张表：内容中指向有外链的网址以及外链网址的link表；表明link中外链网址含有的linkwords表。

• PageRank排名
  用到link表，PageRank的意义是表明某个人在任意次点击后到达某一网页的可能性（不存在范围限制），有一个0.85的阻尼引子，表示大多数用户在浏览一段时间后会停止点击。
  算法流程：先确定含有搜索关键词的网址A，再通过计算指向A的网址的加权PageRank（加权的意义在于有的网址如果同时指向了多个外链，则贡献会被分散）来获得A的PageRank值。

  
  image.png
  

  如何在一开始对PageRank值进行计算？解决方法是，为所有PageRank都设置一个任意的初始值，然后反复计算，迭代若干次。在每次迭代中，每个网页的PageRank值将会越来越接近真实值。迭代所需要次数要视网络数量而定。

• 基于外部回指链接的PageRank算法
  用到linkwords表和link表，现在linkwords表中寻找含有搜索关键词的link，再去link表中寻找被指向网址，以及其PageRank。

• 比较说明
  PageRank的本质是看中网页的热度，热度越高，则被引用的概率会越大，但是网页本身的热度却不一定是因为关键词造成，有可能是因为网页中的其他关键词。
  外部回指链接则看中搜索的精准性，一般情况下，从指向该网页的链接中所得到的信息会更有价值。

ps：PageRank的本质虽然与热度有关，但实际上可以构建其他维度来反映点击次数、页面停留时间等等，并且这种维度是可以轻松转化为内容排名的。

4.2.3 简单神经网络

在上面的算法其实已经说得差不多了，不具备通用性的原因有几点：

• 输入层不是数值，而是限定的组合？？
• 隐藏层的个数是遇到新组合就增加一个？？
• 权重不是反复迭代终止的，而是每次只更新一次？？
• 整体局限性太大了，甚至不知道从何说起。。。

首先看一下数值型的神经网络怎么求解的：
https://blog.csdn.net/dare_kz/article/details/77603522
当然其中也有缺陷，因为针对输入输出为（x1,x2→y）的情况，是需要计算很多组数据的整体误差的，以整体误差最小进行权重更新，所以最后求得的模型，有可能进行输入后得到的输出与准确值有差异。文中只输入了一组数据，得到的模型是完全准确的，而实际上模型的准确性与神经层个数有关，有点像如果数据很多，但是用一个二次多项式进行拟合，肯定是很难完全拟合的，但是如果用一个N次多项式拟合，绝对能够完全拟合。

最后再说一下如果真的要构建神经网络的搜索引擎：

• 输入值比起是海量的限定组合，还不如考虑成单词的叠加（有就为1，无就为0，两个都有就是1，1），虽然也是海量，但是至少输入层很清晰；
• 神经层个数海量；
• 输出层的期望值记为当输入某一关键词时，该网页被点击选中的概率（由海量数据统计得出），0~1之间，可以持续更新。最关键的一点是，概率是确定的，因此可以进行迭代求解，最后给用户提供的是稳定的且符合期望的模型，而不是每输入一次新的组合，都会重新更新权重，而且权重还不一定符合期望。。。

第五章 优化

用三种场景来说明优化算法，分别是

• 无约束优化：组团旅游问题，来自美国各地的家庭成员要在同一天乘坐飞机到达同一个地方，并且在同一天离开，设计一个合理的方案。
• 有约束优化：学生宿舍优化问题，拜托那个学生有宿舍首选和次选方案，需要寻找合理方案尽量满足需求。
• 网络可视化优化：用一个尽量不存在交叉线的网络图来描述人与人之间的网络联系。

5.1 算法流程

确定成本函数→随机搜索/爬坡法/模拟退火/遗传算法等优化算法求解

5.1.1 随机搜索法

随机搜索就是一种随机尝试的方法，在实现过程中随机的产生一定数量的解，并且对这些解一一进行成本值的计算，取最小值。

5.1.2 爬坡法

https://www.cnblogs.com/gongxijun/p/5873643.html
爬坡法通常指最陡爬坡算法，每次选定具有最优结果的解进行爬坡。
爬坡算法的关键是需要设定好爬坡间隔方向，比如链接中：

这样的邻近点选择是没有问题的。但是书中针对组团旅游问题，成本函数是实现总费用最低，但是邻近点选择是选择相邻的航班，我认为是存在问题的，主要是自己在构造输入的时候，是按航班时间进行排序，而如果是按成本排序的话，相邻的输入就变成了成本相近的航班，这样会更合理一些。
所以爬坡法一定要注意邻近点选择。

5.1.3 模拟退火法

https://www.cnblogs.com/gongxijun/p/5873643.html

image.png
即，在早起温度更高时，非最优点也有较大概率会被选择，温度降低后，越来越大的概率选择最优点作为新一轮起点。
模拟退火法实际是爬坡法的一种。

5.1.4 遗传算法

随机生成一组解，成为一个种群
（1）直接遗传
将当前种群中代价最小的一部分解，如 40% 进行直接遗传，传入下一代种群。
（2）变异
从题解中随机选取一个数字，对其进行微小的，简单的改变。
（3）交叉
选取最优解中的两个解，将他们按照某种方式进行结合
通过上述三种方法，从上一代种群中构建出了下一代种群。而后，这一过程重复进行，知道达到了指定的迭代次数，或者连续数代都没有改善种群，则整个过程就结束了。

5.2 有约束优化问题的建模理论

有约束优化问题有两种解决方法：将约束条件作为成本函数中的惩罚函数，匹配一个很大的惩罚因子，但是在很多实际问题上并不是一个理想的方法。
另一种思路是在生成初始题解的时候，便将约束条件考虑进去，保证生成的初始题解便是完全满足约束条件的。

5.3 网络可视化问题的建模理论

不深入研究，主要是指借助质点弹簧算法来确定成本函数，最后利用绘图模块将网络图绘制出来。
质点弹簧算法：各结点彼此向对方施以推力并试图分离，而节点间的联结则试图将关联节点彼此拉近。

第六章 文档过滤

对邮件进行文档分类，将其分为垃圾邮件、非垃圾邮件或者更多种类。介绍的算法可以解决更为一般性的问题。

6.1 算法流程

• 朴素贝叶斯分类器
  构建特征值（文中是以文档中的单词为特征值）→基于合理推测基础上进行条件概率训练（监督算法）→建立朴素分类器，可以输出组合单词的不同种类的概率（非真实）→基于阈值比率和分类概率来选择分类
• 费舍尔分类器
  构建特征值→基于合理推测基础上进行分类概率训练（监督算法）→建立费舍尔分类器，可以输出组合单词的不同种类的概率（真实概率，但是会经过对数卡方分布变换）→基于分类限值和分类概率来选择分类

PS：费舍尔分类器就是最正常的分类器，朴素贝叶斯理论上求解条件概率后适合费舍尔一致的，这里不一致的点在于他没有求解精准概率（省去了一个概率环节），而费舍尔求解的是精准概率。所以两者分开其实没有什么意义，我要是选的话肯定直接采用费舍尔了。

6.2 朴素贝叶斯分类器

6.2.1 合理推测

针对没有出现过的单词，我们可以设定其初始概率为0.5，同时赋予其一定的权重。一个更通用的理解是，如果准备对垃圾信息过滤器进行训练时，可以利用他人训练过的垃圾过滤器，则将其概率引用过来，并设定一定的权重，避免欠缺训练导致的数据不准。

6.2.2 条件概率训练

即监督算法进行训练的时候，每次训练结果得到的都是条件概率（比如，出现好的分类中出现单词A的概率是0.5，坏的分类中出现单词A的概率是0.3），所以之后才需要进行贝叶斯变换。

6.2.3 朴素贝叶斯分类器

• 贝叶斯变换：将条件概率变换为特征概率

贝叶斯定理：Pr(A|B)=Pr(B|A)Pr(A)/Pr(B)
在本例中：Pr(Category | Document )=Pr(Document | Category)Pr(Category) / Pr(Document)
关键就在于，如果采用上述公式得到的特征概率是完全准确的，但实际上贝叶斯没有计算Pr(Document)，得到的结果是：

Pr(Category A | Document )=Pr(Document | Category A)*Pr(Category A)     
Pr(Category B | Document )=Pr(Document | Category B)*Pr(Category B) 

所以计算结果并不是真实概率值

• 朴素的含义
  针对单词组合，认为是独立条件概率，直接相乘

6.2.4 基于阈值比率和分类概率来选择分类

为了避免将好的邮件判定为垃圾邮件，可以设定阈值比率为3，当Pr(Category 坏 | Document )>3 * Pr(Category 好 | Document ) 的时候才将其分类为垃圾邮件。

6.3 费舍尔分类器

6.3.1 合理推测

同上

6.3.2 分类概率训练

贝叶斯是得到条件概率Pr(Document | Category A)和Pr(Document | Category B)，费舍尔是直接得到特征概率 Pr(Category A | Document )和Pr(Category B | Document )

6.3.3 费舍尔分类器

• 概率组合
  也认为是独立条件概率，进行相乘
• 对数卡方分布
  所有概率相乘后，取自然对数，再乘以-2。
  费舍尔方法认为，如果概率彼此独立且随机分布，则这一计算结果将满足对数卡方分布（0~1）之间。
  但是个人认为不用变换啊，最后概率还是会在0~1之间。

6.3.4 基于分类限值和分类概率来选择分类

因为是精准概率，所以在为分类选择临界值时允许更大的灵活性。可以不再采用阈值比率，而是直接设定概率值的上下限，例如将认为是垃圾邮件的下限值设得很高，比如0.6，这样可以灵活控制分类。

6.4 特征值改进

例子只是简单把单词全部变换成小写，而且直接进行非字母非数字类字符的分割，实际上处理过程中还有很多特征需要辨别。例如，如果邮件中出现存在大量大写字母的情况，实际很有可能是反应了某种特征，而不能全部转化为小写字母进行分类。在实际分类过程中都需要考虑这些情况。

第七章 决策树建模

跟踪用户的网站访问信息，有“来源网址”、“用户位置”、“是否阅读过FAQ”、“浏览网页数”、“选择服务类型（是否成为会员）”等信息，利用决策树建模分析各个特征值影响，从而预测以为用户成为付费顾客的可能性有多大。
这篇文档的算例足够清晰：https://blog.csdn.net/asd20172016/article/details/81488259

7.1 算法流程

利用基尼不纯度/熵等方法计算信息增益和增益率→根据增益率最大原则划分构造树→递归方法反复构造树→对树进行剪枝→有必要的话实现决策树的可视化

7.2 信息增益和增益率

决策树的本质是持续选取最优特征，将数据进行分类，让分类后的两组或多组数据组件的特征尽量相似。也就是原数据组间比较混乱→分类后变得没那么混乱，一般采用熵或基尼不纯度来判断混乱值。

7.2.1 熵和基尼不纯度

• 熵
  https://blog.csdn.net/datawhale/article/details/95874780
  熵最直观的一个例子就是32支球队，最多判断6次就可以知道哪只球队赢了，所以最混乱的情况下熵为5。熵本身是一个无范围限制的数，越小越好（最好的情况就是只用一次就知道哪一支球队赢了，因为那支球队胜率100%）。
  image.png
  所以用熵公式得到分类后每个组别的熵后，还需要进行加权来反映整体的熵。

• 基尼不纯度

  
  image.png
  

  物理含义是随即从数据集中抽取两个样本，其类别不一致的概率，所以某个组如果有4个不同的样本，基尼指数是75%。基尼指数也是要进行信息增益的（加权），但是一般都是采用的熵进行计算的，下文中也只讨论熵。

7.2.2 信息增益

image.png

信息增益公式中的第二项就是加权后的整体熵，而信息增益表示如果按照这个特征分类后熵的减少情况。谁减少得越多，那么就选择这个特征进行继续分类。

7.2.3 增益率

如果按照某一特征进行分类后，有特别多的组别，实际上会导致这个组别的整体熵天然小！一个很好理解的例子是如果分类后每一个分组是一个编号，那么每个组件的熵为0，整体加权后的熵也为0，但这个是没有意义的，因为你如果都细分到编号去了，那肯定是每个组特征都一样啊。所以如果你分类越多，熵自然会变小，我们要避免分类过多的情况。

image.png

所以入引进了增益率后，按照增益率最大来进行特征选择。（书中的例子没有引进增益率，用的是信息增益进行选择）

7.3 根据增益率最大原则划分构造树

递归函数反复构造就行了。只是涉及到要不要构造到最底层的问题，构造到最底层容易导致模型过拟合。

7.4 剪枝处理

剪枝的目的是为了避免决策树模型的过拟合。因为决策树算法在学习的过程中为了尽可能的正确的分类训练样本，不停地对结点进行划分，因此这会导致整棵树的分支过多，也就导致了过拟合。决策树的剪枝策略最基本的有两种：预剪枝和后剪枝。

7.4.1 预剪枝

当继续分类时，只有到信息增益大于某个值，才继续创建分支，如果小于该值，则不再进行分支创建。

7.4.2 后剪枝

先构建好完整的整棵树，再尝试消除多余的节点：对具有相同父节点的一组节点进行检查，判断如果将其合并，熵的增加量（信息增益的负值）是否会小于某个阈值，如果成立，则合并节点，避免过拟合。

ps，对于两种剪枝方式，后剪枝更像是全局寻优，全部的路线都有了，看看哪个更好，预剪枝更像是局部寻优，一步一步的走，可能为了局优而屏蔽了全优，所以预剪枝欠拟合的风险大，但是后剪枝的计算量更大。

7.5 连续值和缺失值的处理

7.5.1 连续值处理

针对连续值的处理，本质上是寻找分割点，将连续值分为几类。书中提供的可行策略是寻找一个分割点，使得两组数据分割后的整体方差最小。之后再计算分割后的熵和信息增益。
方差本身就和熵有很强的关系（熵是反映混乱程度最准确的，方差在一些特殊情况下并不能准确反映），因此还不如直接寻找一个分割点，来使得两组数据分割后的熵最小呢- -。（后来思考了一下，好像还是方差可行，因为有很多变量，方差计算的是整体的差异程度，而熵的话智能计算最终类的分类情况，好像不太实际）
反正基本理论都是一致的，方法很多。

7.5.2 缺失值处理

书中的意思是，对于缺失值，可以假设他两个分支都走，因此可以计算分类后每个组别的熵，但是求信息增益的加权上，不考虑缺失值的权重，而只用数据来进行加权，最终求一个信息增益。

网页的案例：

image.png
image.png

先用非缺失值计算组别熵以及加权熵，最后得到的是非缺失数据的信息增益，再乘上一个比率就是整体的信息增益。这里存疑，因为没有计算两种方法的实际结果是不是一样。但我感觉第二种的逻辑更好理解。

7.6 决策树可视化

一种是文字可视化，遍历整棵树进行输出就行了。
一种是用第三章的方法，来绘制树状图。。。

总结：什么时候适用于选择决策树：决策树最适合用来处理的，是那些带分界点的、由大量分类数据和数值数据共同组成的数据结构。同时，决策树也可以帮助理解决策过程！但是，如果输出结果很多（底层分类很多），决策树就不适用了！

第八章 构建价格模型

利用一个葡萄酒数据集，进行葡萄酒价格预测。葡萄酒的价格根据酒的等级及其储藏的年代（rating和age两个参数）共同决定，并假设葡萄酒有“峰值年”现象。

8.1 算法流程

基于参数定义相似度→加权KNN初模型→交叉验证确定KNN模型

knn模型其实是理论相对很简单的模型，本质是基于输入参数进行预测时，希望根据相似的一组数据进行预测，特征越相似，则结果也是相似的。

8.2 相似度定义

即距离计算方法，欧几里得距离算法、皮尔逊都可以。

8.2.1 参数缩放

如果参数的量纲相差很大，理论上是要进行一定的归一化或者缩放操作的。如果人工对参数有良好的判断，可以进行人工缩放，不然的话可以进行自动优选。

8.2.2 参数优选

参数优选跟之后的交叉验证是相关的。即把原始数据氛围训练集和测试集，通过构造成本函数（这里就是误差率），来寻找最优的缩放参数。寻优方法也是爬坡法、遗传算法、模拟退火都可以。。。

8.3 加权KNN初模型

KNN模型首先是基于输入参数进行排序，然后选择最近的k个元素，并进行预测。单纯的平均可能不准确，更希望的是加权平均（跟第一张的概念是一样的，越相似，则占比要越高）。一般来说近邻分配权重的方法有反函数、减法函数、高斯等等。

8.3.1 反函数

反函数（Inverse Function）：对距离求倒数并在其之前加一个小小的常量。

8.3.2 减法函数（负斜率函数）

减法函数（Subtraction Function）：用一个常量值减去距离。如果相减结果大于0，则权重为相减的结果；否则，结果为0。

8.3.3 高斯函数（正态分布）

高斯函数（Gaussian Function）：通过高斯公式计算出权重值。

8.4 交叉验证

交叉验证的目的是为了寻找到一个最优的K值，来保证KNN模型具有的误差最小。计算误差的步骤：

• 随机分配训练集和测试集（一般是95%和5%的比例）
• 计算该K值下的误差（误差计算公式可以多样）
• 重复N此，求取平均误差（这个才是交叉验证的精髓，不能只验证一次就是误差）

ps：其实交叉验证和上面的参数优选没有什么区别，也可以用成本函数的方法寻求K的优值，也可以用交叉验证的方式，寻求参数缩放的优值，或者两者联合起来寻优也可以。觉得并没有什么限制。

8.5 其他

文章提到了绘制概率分布：例如，如果当评分为95，年份为20（数据只有这两个参数）的情况下，如果价格分布有很大的差异，可以选择绘制该组数据的离散概率或者累积概率（概率分布函数）。

ps，KNN最好的一点是模型训练好了之后，可以随时加入新的观测数据而不增加计算量（如果你要重新更新K值或者优选参数的话，才需要训练）。KNN的难点在于，如果参量很多，可能很难确定合理的权重值和缩放参数，而这两点也恰恰是影响KNN误差的关键因素。。。

第九章 高阶分类：核方法和SVM

利用约会网站的历史配对数据，进行配对成功可能性的预测。数据包括：年龄、是否吸烟、是否想要孩子、兴趣列表等等。。

9.1 算法流程

数据预操作→构建SVM模型→预测分类

9.2 数据预操作

9.2.1 特征数据化

比如讲是否问题，转化为0/1问题；将多文本问题，转化为多值问题；

9.2.2 数据缩放处理

对SVM而言，数据缩放处理也是必须的，因为SVM本质判断输入值与分类中心点的距离（向量内积），如果不进行缩放的话，距离可能完全由某一参量决定，而其他参量不能起到作用。
一个简单的缩放方法时，按最大最小值缩放，将数据范围统一调整为0~1区间。

9.3 SVM模型

https://www.cnblogs.com/volcao/p/9465214.html

9.3.1 内积理论

SVM是想一找一个分类线/面，具有最大的margin，来保证将两类数据最大化的分开。

image.png

所以边界的两条线是wx+b=±1，中间的那条分界线是wx+b=0。y代表的是输入点所在的类别（正为1，负为-1）。所以问题转化为求w和b，在满足y(wx+b)≥1的约束下，使得2/||w||最大（这个就是margin，正负就是两倍）。
含约束优化问题转化为拉格朗日函数求解，最后变成了求解对偶问题Ld最大

image.png
解对偶问题会求解到很多α的值（大部分α为0，不为0代表对应的向量才是支持向量，影响着分界线的选择！）→把α带回去求解w（就在上图，有w和α的关系表达式的）→把w带回wx+b=0求解b，最后分界线和margin都可以解出来。

但是如果找不到一个完美分界面分割呢？那就放宽分类要求，加上一个ξ值后实现大于0，同时优化目标加上一个惩罚系数C：

image.png

最后也就是求w,ξ，C，α，μ使得Lp最小！

image.png
最后再转化，目标函数并没有区别，只是原本的0≤α，变味了0≤α≤C了
所以最后也只用求α和C。

9.3.2 核函数和核技巧

当线性不可分的时候，把数据映射到高维空间去。而且理论上，所有的数据在某一高维上肯定是线性可分的。

常见的核函数 image.png
利用核技巧，可以将高维核函数的内积，转化为低维的运算。

多项式核需要确定展开的维数。
高斯核（RBF）是将正态分布函数泰勒展开到无穷维，不需要确定维数，但是需要确定gamma。

image.png

https://blog.csdn.net/qq_15295565/article/details/80888607
现在再回看一下目标函数：

image.png
这个MAX的其实就是Ld，然后xixj→φ（xi）φ（xj）=k(xi,xj)，所以已经升维了，当然里面示一个含有所有x的大矩阵的内积，所有的x都会遍历相乘。
最后就是求α→确定w和b，得到wφ（x）+b的公式（ξ已经不重要了）
，要判断新的输入x是属于哪一类，就看wφ（x）+b是大于0还是小于0咯，大于0就表示趋于wφ（x）+b=1，小于0就表示趋于wφ（x）+b=-1，所以就可以分类了！

9.3.3 参数选择问题

https://blog.csdn.net/wn314/article/details/79972988
RBF实际上有两个参数需要选择，一个是gamma，一个是C。
gamma的意义是在训练集的基础上，确定一个范围（这个范围肯定是大于等于训练集的），认为数据的存在范围：https://blog.csdn.net/ITpfzl/article/details/82831301
这里面的图形展示的比较清楚，gamma越大，高斯分布则越瘦高，则支持向量的样本更少，容易过拟合。
C是惩罚系数，意义是在分类时候允许误差存在，避免过拟合：
https://www.zhihu.com/question/40217487

image.png
可以看出，C越大，则不允许误差存在，容易导致过拟合。

PS，文中的SVM模型。。umm，有点脱离实际理论，所以思路可以借鉴，但是实际不能用。

9.4 预测分类

根据训练好的模型，输入值，会告诉你是A类还是B类。

9.5 SVM划分多类问题

https://blog.csdn.net/u012762305/article/details/37908601
首先，SVM是解决分类问题，一般情况不能预测连续值，那能不能预测多个分类？
最简单的方法是：一对其余法

• 一类对余类法(One versus rest，OVR)是最早出现也是目前应用最为广泛的方法之一，其步骤是构造k个两类分类机(设共有志个类别)，其中第i个分类机把第i类同余下的各类划分开，训练时第i个分类机取训练集中第i类为正类，其余类别点为负类进行训练。判别时，输入信号分别经过k个分类机共得到k个输出值fi(x)=sgn(gi(x))，若只有一个+1出现，则其对应类别为输入信号类别；实际情况下构造的决策函数总是有误差的，若输出不只一个+1(不只一类声称它属于自己)，或者没有一个输出为+1(即没有一个类声称它属于自己)，则比较g(x)输出值，最大者对应类别为输入的类别。
  这种方法的优点是，对k类问题，只需要训练k个两类分类支持向量机，故其所得到的分类函数的个数(k个)较少，其分类速度相对较快。

第十章 寻找独立特征（非负矩阵因式分解）

一个典型应用是“鸡尾酒宴会”问题：在人声鼎沸的屋子，还是能够辨别出某人的声音。
文中的问题是：构造一个新闻系统，并从一组报道中识别出关键主题来。相当于是：
输入某一篇文章，可以返回其几个特征权重以及特征构成（关键单词，因为每个特征中各个单词也有不同权重，所以权重高的是关键单次），同理，也可以返回具有相近的特征的一组文章，可以认为这些文章都是一个主题（具备相近的特征及权重）。

鸡尾酒宴会中能够辨别某人声音，就是因为该声音针对某特征有较大的权重，大脑可以识别该特征的构成（声音频率、尾音等等）。

10.1 算法流程

构建数据矩阵→非负矩阵因式分解→结果呈现

10.2 构建数据矩阵

• 目标矩阵
  一个列表保存文章名，一个列表保存单词名，一个矩阵保存每个单词在每篇文章中出现的频次，行为文章，列为单词。

  
  image.png

• 预处理
  为了缩减矩阵的大小，可以去掉几个只在少数几篇文章中出现的单词，或去掉在过多文章中出现的单词。（基本上各种算法都会进行预处理）

  
  image.png

10.3 非负矩阵因式分解 NMF

非负矩阵因式分解的理论其实很符合人类思维中“局部构成整体”的概念。
理论可以参考：https://blog.csdn.net/google19890102/article/details/51190313
将原始的数据矩阵分解（特征的）权重矩阵*特征矩阵的方式，直观上很容易理解。

比如HURRICANE的文章。主要是由特征1构成，而特征1是指HURRICANE和FLORIDA单词出现批次较高，但其他频次较低的一个特征。对应于鸡尾酒问题的话就是，如果一个人音调很高很尖，那么有一个反映“音调很高很尖”的特征上，这个人具有很大的权重，人脑对这样一个具有较大权重且特征明显的特征反映就很灵敏。

非负矩阵饮食分解的难点在于求解权重矩阵和特征矩阵。有两个关键因素：

• 特征数目
  人为设定的，特征数目越多，越容易过拟合。因为NMF本身是非监督算法，所以也没有办法用成本函数寻求来确定特征数目的最优值。（因为你自己都不知道划多少个特征数目最合适，所以没有标准值，无法构建成本函数的）
• 迭代求解
  需要注意的一点是，非负矩阵因式分解是利用反复迭代求解的，所以最后只是求到了两个比较接近的矩阵！并不是完全精确（完全精确的话，不就是实现100%拟合了么）

https://blog.csdn.net/pipisorry/article/details/52098864网站中给出了NMF 在图像处理方面的应用，比较容易理解，因为NMF本身寻求特征的方法，很符合人类思维对图像各个特征的识别，比如人脸识别，肯定是脸轮廓+五官的特征组合。。。。（没有深究）

10.4 结果呈现：
最后的结果可以有两种呈现形式：

• 返回最典型的特征（特征权重会比较大）的关键词，以及符合这个特征的前几篇文章；
• 返回某篇特征的几个典型特征（以关键词形式展现），以及特征权重。

ps，NMF差不多是最新的算法，然后也是最为复杂的技术之一。

第十一章 智能进化

遗传编程（GP）是遗传算法（GA）的特例，遗传算法一般是解决优化问题，参数是全部转化为数字编码的。但是遗传编程一般是为了构造AI程序，参量一般是以程序树的格式展示。
本文的案例就是构造一个下棋的AI。（不具备参考性，真正的AI要参考alpha go）

11.1 算法流程

构造程序树（编码）→确定优化目标→创建初始种类、遗传交叉变异→确定最优值（最优程序）

11.2 构造程序树

• 求拟合函数

  
  image.png
  

  如果是给定的一堆XY数据集，要求找到一个拟合函数，能够拟合XY的值。那么这个函数可以用程序树的方式展现。一个函数可以包含判断语句、运算语句等等（比如上面那个）。需要注意的是，一个程序出了函数节点、常量节点、还有子节点（用以实现递归，子节点又是一个封装好的函数块），然后整体要进行封装。

• 下棋的程序
  程序树下面的函数，需要构造成上下左右走（比如用1234代替），也需要加入一些判断条件（比如判断对手在哪个位置），同时会含有很多个模块（函数），一个模块对应一步，进入到下一步，就调下一个模块。

11.3 优化目标

优化目标就是下棋的目标，不能死了。（如果是拟合函数，就是误差最小啊）

11.4 遗传优化

针对程序的遗传优化，就涉及到支干以及子节点的交叉变异了，理论都是一样的。

11.5 确定最优程序

文章的例子就太浅了，确定最优程序的方法是，模拟竞赛，最后胜出次数最多的那一个程序作为最优程序。可以理解为，那个程序每一步怎么走都写好了（如果有判断语句的话，就自己进行判断），无论对手怎么走棋，他都是按程序走的，所以这就是不具备参考性的原因。

11.6 alpha go程序

https://my.oschina.net/u/876354/blog/1594849
https://blog.csdn.net/zchang81/article/details/78349269
主要是：

image.png
（1）监督学习（学习别人的棋谱）
首先，policy net是一个模型。它的输入是当前的棋局（19*19的棋盘，每个位置有3种状态，黑、白、空），输出是最可能（最优）的着法，每个空位都有一个概率（可能性）。着法并非无迹可寻，人类已经下了千年的棋了。policy net先向职业选手学习，她从KGS围棋服务器，学习了3000万个局面的下一步怎么走。也就是说，大概职业选手怎么走， AlphaGo已经了然于胸。学习的目的是，不是单纯的记住这个局面，而是相似的局面也会了。当学习的局面足够多时，几乎所有局面都会了。这种学习叫做“监督学习”（supervised learning）。
（2）深度学习（提升准确性）
AlphaGo强的原因之一是policy net这个模型是通过深度学习（deep learning）完成的，深度学习是近几年兴起的模拟人脑（神经网络）的机器学习方法，它使AlphaGo学习到的policy更加准确。
（3）增强学习（自己跟自己学，生成很多未知的棋局）
AlphaGo从职业棋手学完后，感觉没什么可以从职业棋手学的了，为了超越老师和自己，只能自己左右互搏，通过自己跟自己下，找到更好的policy。比如说，她从监督学习学到了一个policy：P0。AlphaGo会例外做一个模型P1。P1一开始和P0一样（模型参数相同）。稍微改变P1的参数，然后让P1和P0下，比如，黑用P1，白用P0选点，直到下完（终局）。模拟多次后，如果P1比P0强（赢的多），则P1就用新参数，否则，重新在原来基础上改变参数，我们会得到比P0强一点点的P1。注意，选点是按照policy的概率的，所以每次模拟是不同的。多次学习后AlphaGo会不断超越自己，越来越强。这种学习我们叫做增强学习（reinforcement learning）。它没有直接的监督信息，而是把模型放在环境中（下棋），通过和环境的互相作用，环境对模型完成任务的好坏给于反馈（赢了还是输了），从而模型自行改变自己（更新参数），更好地完成任务（赢棋）。增强学习之后，AlphaGo在80%的棋局中战胜以前的自己。
（有空在研究吧）

其他:

• 马尔科夫链
  https://blog.csdn.net/FnqTyr45/article/details/82598649
  这里面有比较清晰的解释，表征的是处在当下状态的时候，向其他集中状态转化的概率，最简单的理解是“如果某一天是晴天，那么第二天也很可能是晴天”。
  google pagerank的算法也用到了马尔科夫链的，那个引用文章的指向加权，好像就是一种马尔科夫链的解释，暂时不研究了。

第十二章 算法总结

集体编程智慧总结.png