机器学习基本算法思想和步骤

一、EM算法

EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步（E步），另一个为极大步（M步），所以算法被称为EM算法（Expectation Maximization Algorithm）。其基本思想是：首先根据己经给出的观测数据，估计出模型参数的值；然后再依据上一步估计出的参数值估计缺失数据的值，再根据估计出的缺失数据加上之前己经观测到的数据重新再对参数值进行估计，然后反复迭代，直至最后收敛，迭代结束。
EM就是最大期望算法（Expectation Maximization Algorithm，又译期望最大化算法），是一种迭代算法，用于含有隐变量（latent variable）的概率参数模型的最大似然估计或极大后验概率估计。比如先假定男生身高平均1.7 方差0.1 然后求将ABCDEFG归类，分到1.7左边右边，重新求方差，反复迭代，直到不再变化。

二、 线性回归公式

单变量线性回归
模型假设

代价函数

梯度下降

多变量线性回归
模型假设

代价函数

梯度下降

三、 K-means算法

选取划分数量K值，随机选择集合D中的k个点作为初始的聚簇中心，对于其他样本点，计算其与各个簇中心的距离，将它们划入距离最近的簇；采用迭代重定位技术，重新计算簇的平均值，对样本点进行重新分配，不断重复这个过程，直到簇中心的变化在给定条件的阈值内或者与前一次一样，得到最终的聚类中心和聚类结果。

聚类：一种无监督学习的方法，实质是依据某种距离度量，使得同一聚簇之间的相似性最大化，不同聚簇之间的相似性最小化，即把相似的对象放入同一个聚簇中，把不相似的对象放到不同的聚簇中。聚类和分类不同，聚类的输入对象不需要带有类别标签，最后组成的分类是由使用的算法决定的。

K-means优点：简单、移动、伸缩性良好
k-means的缺陷和解决办法：
1、 对初始聚簇中心位置敏感:随机
2、 对K值的选择敏感：多次运行通过合适的准则从结果中挑选最合适的K值
3、 仅能获得局部最优解：基于不同的聚簇中心多次运行算法；对收敛解进行受限的局部搜索
4、 非凸聚类：对数据进行缩放；选择与数据集更匹配的距离度量；用别的算法与k-means形成配套
5、 对噪声点敏感：预处理和后处理
6、 产生空聚簇：从最大的聚簇中“偷出”一些点来重新初始化空聚簇的聚簇中心

四、正则化

logistic回归模型
我们对图1a所示的数据采用简化的线性logistic回归模型进行两分类，即

（1） 考虑一个正则化的方法，即最大化

注意只有w2被惩罚。则当C很大时，如图1(b)所示的4个决策边界中，哪条线可能是有该正则方法得到的？L2、L3和L4 可以通过正则w2得到吗？
答：
L2不可以。当正则w2时，决策边界对x2的依赖越少，因此决策边界变得更垂直。而图中的L2看起来不正则的结果更水平，因此不可能为惩罚w2得到；
L3可以。w2^2相对w12更小（表现为斜率更大），虽然该决策对训练数据的log概率变小（有被错分的样本）；
L4不可以，当C足够大时，我们会得到完成垂直的决策边界（线x1 = 0或x2轴）L4跑到了x2轴的另一边使得其结果比其对边的结果更差。当中等程度的正则时，我们会得到最佳的结果（w2较小）。图中L4不是最佳结果，因此不可能为惩罚w2得到。

（2）如果我们将正则项给出L1范式，即最大化：

则随着C的增大，下面哪种情形可能出现（单选）：（A）
A， w1将变成0，然后，w2也将变成0.
该数据可以被完全正确分类（训练误差为0），且仅看x2的值（w1=0）就可以得到。虽然最佳分类器w1可能非0，但随着正则量的增大，w1会很快接近于0，L1正则会使得w1完全为0. 随着C的增大，最终W2会变成0.

五、 boosting和bagging

在集成学习中，主要分为bagging算法和boosting算法。我们先看看这两种方法的特点和区别。Bagging和Boosting都是将已有的分类或回归算法通过一定方式组合起来，形成一个性能更加强大的分类器，更准确的说这是一种分类算法的组装方法。即将弱分类器组装成强分类器的方法。Bootstraping，即自助法：它是一种有放回的抽样方法（可能抽到重复的样本）。
1、Bagging (bootstrap aggregating)
Bagging即套袋法，其算法过程如下：
A）从原始样本集中有放回的抽取n个训练样本，共进行k轮抽取，得到k个训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）每个训练集都有n个训练样本。
B）每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（模型是指根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
C）对分类问题：将上步得到的k个模型采用权重投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）
2、Boosting
其主要思想是将弱分类器组装成一个强分类器。在PAC（概率近似正确）学习框架下，则一定可以将弱分类器组装成一个强分类器。
关于Boosting的两个核心问题：
1）在每一轮如何改变训练数据的权值或概率分布？
通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样例的权值，来使得分类器对误分的数据有较好的效果。
2）通过什么方式来组合弱分类器？
通过加法模型将弱分类器进行线性组合。
比如AdaBoost通过加权多数表决的方式，即增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值。而提升树通过拟合残差的方式逐步减小残差，将每一步生成的模型叠加得到最终模型。
3、Bagging，Boosting二者之间的区别
Bagging和Boosting的区别：
1）样本选择上：
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
2）样例权重：
Bagging：使用均匀取样，每个样例的权重相等
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
3）预测函数：
Bagging：所有预测函数的权重相等。
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
4）并行计算：
Bagging：各个预测函数可以并行生成
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果
4、总结
这两种方法都是把若干个分类器整合为一个分类器的方法，只是整合的方式不一样，最终得到不一样的效果，将不同的分类算法套入到此类算法框架中一定程度上会提高了原单一分类器的分类效果，但是也增大了计算量。

六、 深度学习的定义，特征

深度学习的概念源于人工神经网络的研究，含有多隐层的多层感知器就是一种深度学习结构。典型的深度学习模型就是很深层的神经网络。深度学习通过组合低层特征形成更加抽象的高层表示属性类别或特征，以发现数据的分布式特征表示。
深度学习的核心思路如下：
1无监督学习用于每一层网络的预训练；
2每次用无监督学习只训练一层，将其结果作为下一层的输入；
3在预训练完成后，用自顶向下的监督算法去调整所有层“微调”。
深度学习特征：
1分布式表示：观察到的信息是多层次因素的形成
2自动特征工程
3从不同层次的抽象中学习
4需要大数据补充其庞大的网络
5无监督学习
6当用小数据进行训练时，会遭受过度拟合
7需要花费长时间计算很多超参数

七、 生成式和判别式模型

两个分类器的决策边界都是二次函数，复杂度相同。

 SVM可能得到更好的结果。虽然两个分类器复杂度相同，但是SVM对训练误差做优化从而得到更低的或者相同的值。

八、 SVM

特征空间是1维（将任意点x映射成非负数p（x）），因此VC维是2.

分类器1的VC维是3，分类器2的VC维是2，因此分类器1更复杂。当训练误差相同时，分类器1得到的预测误差的界更小，从而其推广性更好。而泛化能力过强会使得分类器变化太大，性能下降，拟合效果差。

九、 SVM概念

建立一个最优决策超平面，使得该平面两侧距离该平面最近的两类样本之间的距离最大化，从而对分类问题提供良好的泛化能力。
超平面方程：wTx+b=0
距离超平面最近的这几个点称为支持向量，两个异类支持向量到超平面的距离之和为：
r=2/||w||
称之为间隔。
想要找到最大间隔的划分超平面，就要找到满足以下公式的w和b
min 1/2* ||w||^2
s.t yi(wTxi+b)>=1, i=1,2,3….m

十、 BP神经网络

神经网络中的最基本成分是神经元模型，神经元接收到来自n个其他神经元传递过来的输入信号，这些输入信号通过带权重的连接传递，神经元接收到的总输入值将与神经元的阈值进行比较，然后通过‘激活函数’处理以产生神经元的输出.
BP网络：采用误差反向传播算法的多层前馈神经网络。其中，神经元的传递函数是S型函数。BP网络的学习规则：梯度下降算法。在网络学习过程中，把输出层节点的期望输出和实际输出的均方误差，逐层向输入层反向传播，分配给各连接节点，并计算出各连接节点的参考误差，在此基础上，调整各连接权值，使得网络的期望输出和实际输出的均方误差达到最小。

十一、 决策树

十二、 stacking

stacked 产生方法是一种截然不同的组合多个模型的方法，它讲的是组合学习器的概念，但是使用的相对于bagging和boosting较少，它不像bagging和boosting，而是组合不同的模型，具体的过程如下：

1. 划分训练数据集为两个不相交的集合。
2. 在第一个集合上训练多个学习器。
3. 在第二个集合上测试这几个学习器
4. 把第三步得到的预测结果作为输入，把正确的回应作为输出，训练一个高层学习器
   这里需要注意的是1-3步使用非线性组合学习器的方法。

十三、 特征选择

从m个特征中选择m1个，m1<m(人为选择、算法选择)。获取尽可能小的特征子集，不显著降低分类精度、不影响类分布以及特征子集应具有稳定适应性强等特点。
前向搜索：给定特征集合{ a1,a2,……，ad},我们可以将每个特征看作一个候选子集，对这d个候选单特征子集进行评价，假定{ a2}最优，于是将{a2}作为第一轮的选定集，然后在上一轮的选定集中加入一个特征，构成包含两个特征的候选子集，假定在这d-1个候选两特征子集中{a2，a4}最优，且优于{a2}，于是将{a2，a4}作为本轮的选定集；……，假定在第k+1轮时，最优的候选（k+1）特征子集不如上一轮的选定集，则停止生成候选子集，并将上一轮选定的k特征集合作为特征选择结果。
后向搜索：类似前向搜索，我们从完整的特征集合开始，每次尝试去掉一个无关特征。
特征提取
（特征变换、特征压缩），将m个特征变为m2个新的特征（二次特征）
（降维）PCA主成分分析法：
一种通过降维技术把多个变量化为少数几个主成分的统计方法，最重要的降维方法之一。主成分通常表示为原始变量的某种线性组合。
PCA算法步骤：
设有m条n维数据，m个样本，对原始数据标准化（减去对应变量的均值，再除以其方差），每个样本对应p个变量， 。
1求出自变量的协方差矩阵（或相关系数矩阵）；
2.求出协方差矩阵（或性关系数矩阵）的特征值及对应的特征向量；
3.将特征向量按对应特征值大小从上到下按行排列成矩阵，取前k行组成矩阵α（为kp维)；
4.Y=αT ∗X （Y 为k1维）即为降维到k维后的数据，此步算出每个样本的主成分得分；（αT是α的转置）
5.可将每个样本的主成分得分画散点图及聚类，或将主成分得分看成新的因变量，对其做线性回归等。

十四、 异常检测18-Lecture15-XV. Anomaly Detection

给定数据集x1……xm,我们假设数据集是正常的，我们希望知道新的数据xtest是不是异常的，即这个测试数据不属于该组数据的几率如何。我们构建的模型应该可以根据测试数据的位置告诉我们其属于一组数据的可能性P（x）。下图中，蓝色圈内的数据属于该组数据的可能性比较高，而越是偏远的数据，其属于该组数据的可能性越低。

这种方法成为密度估计：

应用高斯分布开发异常检测算法：
异常检测算法：
对于给定的数据集x(1)，x(2)，…，x(m)，我们要针对每一个特征计算u和σ2的估计值。

一旦我们获得了平均值和方差的估计值，给定新的一个训练实例，根据模型计算P(x)：

当P(x)<ε时，为异常；当P(x)>ε时预测数据为正常数据。

十五、 推荐系统Recommender Systems

基于内容的推荐算法：

协同滤波推荐算法：
上一节中的基于内容的推荐算法，我们假设电影的特征描述是已知的，但是往往我们得到这个已知量是比较难的，或者是不准确的。而我们这节要介绍的协同滤波推荐算法，可以自动获取电影的特征描述，而不需人工标注。
目标函数：

算法流程：