数据挖掘-理论与算法 公开课笔记
数据挖掘-理论与算法 公开课笔记
制作：纪元
本提纲遵循CC-BY-NC-SA协议
(署名-非商业性-相同方式共享)文章目录
- 14.5.2.1 Feature Selection 特征选择
- 15.2.6.1 Feature Extraction 特征提取
- 16.2.7.1 The Issue of PCA PCA存在的问题以及解决
- 16.2.7.2 LDA Example 线性判别分析例
- 19.3.1.1 Bayes、Decision Tree 贝叶斯、决策树（概率基础）
- 20.3.2.1 Naive Bayes Classifier 朴素贝叶斯公式
- 21.3.3.1 Decision Tree 决策树
- 22.3.4.1 Decision Tree Framework 决策树的建立策略
- 24.4.1.1 Perceptrons 感知机
- 25.4.2.1 感知机的应用
- 26.4.3.1 Multilayer Perception 多层感知机神经网络
- 27.4.4.1 分类器学习算法
- 28.4.5.1 Beyond BP Networks 其他的神经网络算法
- 30.5.1.1 Support Vector Machine（SVM） 支持向量机
14.5.2.1 Feature Selection 特征选择
在做数据挖掘的时候，要在多个属性中进行挑选，否则会影响算法的效率与资源的消耗，所以属性分好坏
熵-(Entropy)：在数据挖掘中，代表变量/系统的不确定性。
- 此处b一般取2，但也可以为其他值，取2时单位为比特
信息增益-(information gain)：在数据挖掘中代表属性的价值
- 即增加属性前后熵的差值
属性组的优劣并不是单纯的单个属性好坏的叠加，因为属性间可能有影响或者关联。
搜索最优属性-(Subset Seach)：为了在众多属性中挑选最优的属性组，会有众多的排列组合，所以需要通过适当的算法。
Branch and Bound：寻找最优的属性组。建立属性树，如有单调的情况，可以通过剪枝方法加速。启发式、模拟退火等算法同样适用
15.2.6.1 Feature Extraction 特征提取
引例：照片把三维信息压缩（投影）为二维，信息损失很多，人们通过照片的特征，依旧可以识别照片中的物体。
不同的属性有不同的区分度，越重要的属性越能区分物体，更少产生重复。所以属性有好坏
此图（理想情况下）中属性劣于属性（不能更好的区分数据点）我们将数据点向x轴投影，丢失的就是y轴方向的信息
主成分分析技术-PCA(principle components analysis)：把坐标平面的点向坐标轴投影，相当于降维，投影方向（相当于属性）有好坏。最优情况为最大特征向量。
数学工具：拉格朗日数乘法
实际情况下，数据的属性往往有联系，此时要将图像移动、并旋转到理想情况。
16.2.7.1 The Issue of PCA PCA存在的问题以及解决
PCA是一种无监督学习，虽然可以进行降维，但是在分类时，PCA可能无法进行合理的投影方向选择，导致无法进行分类。
举例：如果向1轴投影，可以明显区分两个数据集，但是PCA会向2轴投影，导致两个数据在低维混合，看不出分类。
线性判别分析-LDA(Liner Discriminant Analysis)：相对PCA，LDA在投影的同时保留类的区分信息（指相同组中数据尽可能近，不同组中数据尽可能远）
费舍尔准则-(Fisher Criterion)：用于评估投影效果好坏（整体上越大越好）
- 其中为组中心点位置（越远越好），为各组离散程度（越小越好）
16.2.7.2 LDA Example 线性判别分析例
LDA不仅仅局限于二分类，可以容易的拓展到类的情况，此时的分子为各个组中心点离所有点中心点的距离。此时分类最高可以投影到维上
在一些特殊情况下（两类比较近或者两个分类维互相垂直），LDA的分类可能不如PCA，在使用时要谨慎分析。
19.3.1.1 Bayes、Decision Tree 贝叶斯、决策树（概率基础）
分类是一种有监督学习，会有标签，这也是分类与聚类的差别。
数学工具：贝叶斯公式
20.3.2.1 Naive Bayes Classifier 朴素贝叶斯公式
注意区分：先验后验、相关独立
拉普拉斯平滑-(Laplace Smoothing)：如果出现数据库中从未存储的特殊点，一项为0会导致整个概率公式值为0。
- （加1导致不会为0）
贝叶斯公式的实际应用：
我们可以提取文章中的部分单词，根据出现与否计算文章分类概率，但是这种情况会导致计算量非常大。改进 词袋模型-(Word Bag)，根据单词在文章中出现的频率来计算文章分类概率。
21.3.3.1 Decision Tree 决策树
将不同因素设定规则，分层计算，形成决策树。决策树是可解释的(if…then…)，是决策树的一大优势
根据判断顺序不同，一个数据集可以建立很多树。运用奥卡姆剃刀，我们可以选择同样分类效率下，尽量简单的决策树，
22.3.4.1 Decision Tree Framework 决策树的建立策略
此章有拓展资料
把分类能力强的节点放在靠近根节点的情况可以大大缩小树的规模，于是决策树的建立与属性判断有关
熵-(Entropy)：在变量选择中，代表属性的不确定性。最大值为1，此时最不确定。最小值为0，此时最确定。
- 此处b一般取2，但也可以为其他值，取2时单位为比特
过学习-(Overfitting)：在训练集中a比b效果好，但在测试集中b比a好，此时就发生了过学习（通用概念）
决策树并不是越大越好，也存在过学习(overfitting)的情况。为避免过学习，有两种剪枝策略：
- 限制树的深度
- 进行剪枝（将某些子节点合并到父节点上）
简单的决策树 ID3 建立过程：
- 寻找能把数据集分的最开的属性，进行分割
- 如果子集纯，那么停止分割，如果不纯，继续从1分割（如果没有属性，停止分割，标签少数服从多数）
24.4.1.1 Perceptrons 感知机
神经网络是计算机程序对大脑中神经元的简化抽象模拟。
单个神经元开关速度（0,1互换）相对计算机比较慢，但人脑是多个神经元联合分布式处理的，处理速度很快。
感知机-(Perceptrons)：单个的神经元，n个输入，n+1个权重（，避免所有点都过原点），输出0或1
25.4.2.1 感知机的应用
感知机可以理解为一个线性分类器，对于线性不可分等问题无能为力
梯度下降法-(Gradient Descent)：取权重时不同权重对结果影响不同，所以让误差不断梯度下降
批处理学习-(Batch Learning)：计算一批数据，将更改值保存在中，计算完后统一修改
随机学习-(Stochastic Learning)：一旦出现误差，就修改
26.4.3.1 Multilayer Perception 多层感知机神经网络
多层感知机通过在输入和输出间添加隐层来提升效率
多次感知机解决线性不可分问题：将输入的线性不可分问题转化为线性可分问题，输出到隐层，由隐层解决并输出。
27.4.4.1 分类器学习算法
误差反向传播算法-BP(Backpropagation Rule)：思想类似于感知机，用误差对某个权重的输入求偏导。但在多层感知机网络中，由于隐层的期望值并不知道，所以没法得知隐层的误差，因此输出后根据结果加权反向反馈，修改参数。
在求导时，很容易使参数掉进局部最优点，导致误差不在下降，而神经网络恰恰有很多局部最优点。为了解决这个问题，
- 我们可以尝试多次从不同点、不同方向出发，寻找最优参数。
- 也可以增加“冲量”，相当于“惯性”，让参数点冲过一些比较小的局部最优点。
- 也可以尝试改变学习率，较大的学习率可以直接大踏步跳过一些比较小的局部点，
- 而特殊的学习率会在一些特殊情况产生震荡，左右横跳导致无法收敛，多次学习也是解决办法。
同样，神经网络也有过学习问题。所以我们既要设置训练误差-(Training Error)—–随时间逐步降低，又要设置校验误差-(Validation Error)—–随时加先降后升。在校验误差拐点停止训练即可。
28.4.5.1 Beyond BP Networks 其他的神经网络算法
此章有拓展资料
Elman Network：此算法有一定的记忆性，通过之前的输入推出答案，输出不仅仅取决于当前的输入，还取决于之前的输入。
Hopfield Network：是一个全连接神经网络。类似于人大脑的记忆功能，利用收敛到局部最小值，实现联想记忆。
同样，不存在万能的神经网络，每个网络算法都有自己的适应性，而且神经网络的训练时间很长，但训练完成后反应很快。
神经网络的可解释性很差（只有权重）
30.5.1.1 Support Vector Machine（SVM） 支持向量机
原理：输入维度向高维映射并进行分类（升维），仍然是线性分类器的一种，真正有效的点只有support vector。
边缘-(margin)：训练集中分界面可以上下平移的区域，margin越大，错误越不会影响结果，参数越好。
支持点-(Support Vectors)：导致平移边界的点，决定了分界面能移动的范围。