机器学习算法汇总与个人理解_计算标签值和特征值的内积和,即正样本的数量。

一直断断续续的学习机器学习的算法，现在希望将已经学习到的机器学习的算法做一个总结，将来有需要的时候可以直接回来查看。

一、K最近邻（kNN）

KNN一般被认为是最简单的机器学习算法，它是指如果一个样本在特征空间中的k个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。

比如上图中这幅图，如果k=3，则绿色的圆圈属于三角类，因为三角的个数(2)大于方块的个数(1)，如果k=5，则绿色的圆圈属于方块。
该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。
总的来说就是我们已经存在了一个带标签的数据库，然后输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似（最近邻）的分类标签。一般来说，只选择样本数据库中前k个最相似的数据。最后，选择k个最相似数据中出现次数最多的分类。其算法描述如下：

1）计算已知类别数据集中的点与当前点之间的距离；

2）按照距离递增次序排序；

3）选取与当前点距离最小的k个点；

4）确定前k个点所在类别的出现频率；

5）返回前k个点出现频率最高的类别作为当前点的预测分类。
其python实现可参考这篇大佬的博客，也给出了详细的注释：knn算法实现

二、支持向量机(SVM)

1、简介

对于用于分类的支持向量机，它是个二分类的分类模型。也就是说，给定一个包含正例和反例（正样本点和负样本点）的样本集合，支持向量机的目的是寻找一个超平面来对样本进行分割，把样本中的正例和反例用超平面分开，但是不是简单地分看，其原则是使正例和反例之间的间隔最大。学习的目标是在特征空间中找到一个分类超平面wx+b=0，分类面由法向量w和截距b决定。分类超平面将特征空间划分两部分，一部分是正类，一部分是负类。法向量指向的一侧是正类，另一侧为负类。

如上图，可以在两个类别中画出无数条线来进行分类，但是哪条线最好呢，无疑时黑色那条，对于分类来说，我们需要确定一个分类的线，如果新的一个样本到来，如果落在线的左边，那么这个样本就归为class1类，如果落在线的右边，就归为class2这一类。黑色这条对新的样本的划分结果我们认为最可信，也就是最好了。
在二维空间，分类的就是线，如果是三维的，分类的就是面了，更高维，也有个霸气的名字叫超平面。因为它霸气，所以一般将任何维的分类边界都统称为超平面。在二维或者三维划分的线和面我们是能够看到的，但是对于更高维度我们就没办法再观察到其划分。

2、SVM

线性可分SVM与硬间隔最大化

其实上面这种分类思想就是SVM的思想。可以表达为：SVM试图寻找一个超平面来对样本进行分割，把样本中的正例和反例用超平面分开，但是不是很敷衍地简单的分开，而是尽最大的努力使正例和反例之间的间隔margin最大。这样它的分类结果才更加可信，而且对于未知的新样本才有很好的分类预测能力。所以整个问题就可以用下图来进行表示。
g(x) =wTx + b=0就是我们要寻找的分类超平面，我们需要这个超平面最大的分隔这两类。也就是这个分类面到这两个类的最近的那个样本的距离相同，而且最大。为了更好的说明，我们在上图中找到两个和这个超平面平行和距离相等的超平面：H1: y = wTx + b=+1 和 H2: y = wTx + b=-1。（之所以方程右边时+1和-1是因为归一化了系数向量w），我们需要满足两个条件：1）没有任何样本在这两个平面之间；（2）这两个平面的距离需要最大。对于条件2也就是：H1和H2的距离就是|1+1|/ sqrt(w12+w12)=2/||w||。也就是w的模的倒数的两倍。也就是说，我们需要最大化margin=2/||w||，为了最大化这个距离，我们应该最小化||w||。对于条件1，也就是，对于任何一个正样本yi=+1，它都要处于H1的右边，也就是要保证：y= wTx + b>=+1。对于任何一个负样本yi=-1，它都要处于H2的左边，也就是要保证：y = wTx + b<=-1。这两个约束，其实可以合并成同一个式子：yi (wTxi + b)>=1。

所以我们的问题就变成：

相关知识补充：对偶理论**
对偶理论是将有约束的优化问题通过拉格朗日乘子法变为无约束的优化问题。具体而言，假设我们的优化问题是：

min f(x) s.t. hi(x) = 0, i=1, 2, …,n 我们引入拉格朗日乘子，得到拉格朗日函数为： L(x, α)=f(x)+α1h1(x)+ α2h2(x)+…+αnhn(x)

然后我们将拉格朗日函数对x求极值，也就是对x求导，导数为0，就可以得到α关于x的函数，然后再代入拉格朗日函数就变成：

max W(α) = L(x(α), α) 这时候，带等式约束的优化问题就变成只有一个变量α（多个约束条件就是向量）的优化问题，这时候的求解就很简单了。同样是求导另其等于0，解出α即可。需要注意的是，原始问题是最小化，转化为对偶问题后就变成了求最大值了。 对于带有不等式约束的条件，需要使用KKT条件

KKT条件
不等式约束的第一步是将不等式写成<0的形式，具体到上面就是先写成了10-x1-x2，而且必须满足条件（3）。所以对于svm，其问题就转变为
得到上面的对偶问题
所以最后的问题变为：

又因为满足kkt条件，也就是
aigi=0，ai>=0，所以要么是ai=0，然后gi<=0,要么是ai>=0,gi=0,对于第一种情况，

后新来的要分类的样本首先根据w和b做一次线性运算，然后看求的结果是大于0还是小于0来判断正例还是负例。

现在有了αi，我们不需要求出w，只需将新来的样本和训练数据中的所有样本做内积和即可。那有人会说，与前面所有的样本都做运算是不是太耗时了？其实不然，我们从KKT条件中得到，只有支持向量（其gi=0）的αi不为0，其他情况αi都是0。因此，我们只需求新来的样本和支持向量的内积，然后运算即可。

松弛向量与软间隔最大化

如果出现上图中的情况，我们不可能为了一些特殊点就去对分割平面委曲求全，所以为了处理这种情况，我们允许数据点在一定程度上偏离超平面。也就是允许一些点跑到H1和H2之间，也就是他们到分类面的间隔会小于1。如下图：具体来说，原来的约束条件就变为：

最优化问题是在最大化间隔，但是现在允许SVM犯一定的错误也就是允许数据点落在直线跟虚线之间，值得注意的是每个样本都有一个对应的松弛变量，用于表征该样本不满足约束条件的程度希望的是SVM具有一定的容错空间，但是又不希望这个容错空间太大。则需将目标函数变为

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200722201305731.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N1cnJ5X3hpbg==,size_16,color_FFFFFF,t_70

经过求解，可以得到，式11的对偶问题为：
此时，我们发现没有了参数ξi，与之前模型唯一不同在于αi又多了αi<=C的限制条件。

核函数

如果数据像上图一样不能够线性可分，则可以把我们的原始样本点通过一个变换，变换到另一个特征空间，在这个特征空间上是线性可分的，那么上面的SVM就可以轻易工作了。也就是说，对于不可分的数据，现在我们要做两个工作：

1）首先使用一个非线性映射Φ(x)将全部原始数据x变换到另一个特征空间，在这个空间中，样本变得线性可分了；

2）然后在特征空间中使用SVM进行学习分类。

我们再看上面的svm问题：

可以看到，对样本x的利用，只是计算第i和第j两个样本的内积就可以了。

对于分类决策函数，也是计算两个样本的内积。也就是说，训练SVM和使用SVM都用到了样本间的内积，而且只用到内积。那如果我们可以找到一种方法来计算两个样本映射到高维空间后的内积的值就可以了。核函数就是完成这伟大的使命的：K(xi, xj)=Φ(xi)T Φ(xj)

这时候，我们的优化的对偶问题就变成了：

和之前的优化问题唯一的不同只是样本的内积需要用核函数替代而已。优化过程没有任何差别。而决策函数变成了：

也就是新来的样本x和我们的所有训练样本计算核函数即可。需要注意的是，因为大部分样本的拉格朗日因子αi都是0，所以其实我们只需要计算少量的训练样本和新来的样本的核函数，然后求和取符号即可完成对新来样本x的分类了。支持向量机的决策过程也可以看做一种相似性比较的过程。首先，输入样本与一系列模板样本进行相似性比较，模板样本就是训练过程决定的支持向量，而采用的相似性度量就是核函数。样本与各支持向量比较后的得分进行加权后求和，权值就是训练时得到的各支持向量的系数αi和类别标号的成绩。最后根据加权求和值大小来进行决策。而采用不同的核函数，就相当于采用不同的相似度的衡量方法。

到这里，和支持向量机相关的东西就介绍完了。总结一下：支持向量机的基本思想可以概括为，首先通过非线性变换将输入空间变换到一个高维的空间，然后在这个新的空间求最优分类面即最大间隔分类面，而这种非线性变换是通过定义适当的内积核函数来实现的。

支持向量的部分参考两篇博客：
https://blog.csdn.net/zouxy09/article/details/17291805
https://blog.csdn.net/weixin_39881922/article/details/80244660?utm_source=blogxgwz0

三、 k-means聚类

k-means算法其实就是用到了EM算法，两个变量交替固定，然后轮流更新。
它的基本思想是：通过迭代寻找k个聚类的一种划分方案，使得用这k个聚类的均值来代表相应各类样本时所得的总体误差最小。
下图展示了对n个样本点进行K-means聚类的效果，这里k取2。
其伪代码如下：

---

创建k个点作为初始的质心点（随机选择）

当任意一个点的簇分配结果发生改变时

对数据集中的每一个数据点

对每一个质心

计算质心与数据点的距离

将数据点分配到距离最近的簇

对每一个簇，计算簇中所有点的均值，并将均值作为质心

---

四、逻辑回归

在线性回归里，如果因为一些特殊点就需要重新更改我们的分类边界，之后就会达到一个不好的效果，使用线性的函数来拟合规律后取阈值的办法是行不通的,行不通的原因在于拟合的函数太直,离群值(也叫异常值)对结果的影响过大,但是我们的整体思路是没有错的,错的是用了太"直"的拟合函数,如果我们用来拟合的函数是非线性的,不这么直,是不是就好一些呢?这时候就需要用到逻辑回归。
逻辑回归不仅可以将线性回归掰弯，而且能够将负无穷到正无穷上的值整个映射为0-1的值，恰好就可以表示为概率， 所以说，LogisticRegression 就是一个被logistic方程归一化后的线性回归。具体的可见下面笔记中的逻辑回归部分。

关于对逻辑回归的cost可以从三方面进行理解。
1、就是第一幅图中标出来的两个cost图像，分别为在样例为1和0时候的损失，比如我们希望在真是为1的时候，如果我们的预测也就是概率h越接近1那么我们的损失就越小，越接近0我们的损失就越大，然后画出这样的图像来进行惩罚，所以最后能够得到逻辑回归的cost。
2、从最大似然的角度去理解，最大似然也就是找到能够最大化模型产生真实观测数据可能性的那一组参数，反应的是在不同的参数取值下，取得当前这个样本集的可能性。
假设我们有n个独立的训练样本{(x1, y1) ,(x2, y2),…, (xn, yn)}，y={0, 1}。那每一个观察到的样本(xi, yi)出现的概率是：

上面为什么是这样呢？当y=1的时候，后面那一项是不是没有了，那就只剩下x属于1类的概率，当y=0的时候，第一项是不是没有了，那就只剩下后面那个x属于0的概率（1减去x属于1的概率）。所以不管y是0还是1，上面得到的数，都是(x, y)出现的概率。那我们的整个样本集，也就是n个独立的样本出现的似然函数为（因为每个样本都是独立的，所以n个样本出现的概率就是他们各自出现的概率相乘）：

那最大似然法就是求模型中使得似然函数最大的系数取值θ*。这个最大似然就是我们的代价函数（cost function）了。
3、从交叉熵的角度去理解，已经写在了第二张图片里。

本文的很理解参考自此博客：https://blog.csdn.net/zouxy09/article/details/14222605