机器学习经典算法总结

敞开成长之旅！这是我参加「日新计划 2 月更文挑战」的第 10 天，点击查看活动概况。

一，机器学习体系分类

一，KNN 算法

K 近邻算法（KNN）是一种根本分类和回归办法。KNN 算法的核心思想是如果一个样本在特征空间中的 k 个最相邻的样本中的大多数归于一个类别，那该样本也归于这个类别，并具有这个类别上样本的特性。该办法在确认分类决议计划上只依据最邻近的一个或者几个样本的类别来决定待分类样本所属的类别。 如下图：

在 KNN 中，通过核算目标间距离来作为各个目标之间的非类似性目标，避免了目标之间的匹配问题，在这里距离一般运用欧氏距离或曼哈顿距离，公式如下：

同时，KNN通过依据 k 个目标中占优的类别进行决议计划，而不是单一的目标类别决议计划，这两点便是KNN算法的优势。

1.1，k 值的选取

• k 值较小，模型会变得复杂，容易发生过拟合
• k 值较大，模型比较简单，容易欠拟合

所以 k 值得选取也是一种调参？

1.2，KNN 算法思路

KNN 思想便是在练习会集数据和标签已知的情况下，输入测试数据，将测试数据的特征与练习会集对应的特征进行相互比较，找到练习会集与之最为类似的前 K 个数据，则该测试数据对应的类别便是K个数据中出现次数最多的那个分类，其算法的描绘为：

1. 核算测试数据与各个练习数据之间的距离；
2. 按照距离的递增关系进行排序；
3. 选取距离最小的 K 个点；
4. 确认前 K 个点所在类别的出现频率；
5. 回来前 K 个点中出现频率最高的类别作为测试数据的预测分类。

二，支撑向量机算法

机器学习中的算法(2)-支撑向量机(SVM)基础

2.1，支撑向量机简述

• 支撑向量机（Support Vector Machines, SVM）是一种二分类模型。它的根本模型是定义在特征空间上的距离最大的线性分类器，距离最大使它有别于感知机；支撑向量机还包含核技巧，这使其成为实质上的非线性分类器。
• SVM 的学习战略是找到最大距离（两个异类支撑向量到超平面的距离之和 =2∣∣w\gamma = \frac{2}{||w}=∣∣w2​ 称为“距离”），可方式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。
• SVM 的最优化算法是求解凸二次规划的最优化算法。

2.2，SVM 根本型

SVM 的最优化算法是一个凸二次规划（convex quadratic programming）问题，对上式运用拉格朗日乘子法可转化为对偶问题，并优化求解。

2.3，对偶问题求解

对 SVM 根本型公式的每条束缚增加拉格朗日乘子 i≥0\alpha_i \geq 0i​≥0，则式子的拉格朗日函数如下：

通过推导（参阅机器学习西瓜书），可得 SVM 根本型的对偶问题：

max⁡∑i=1m−12∑i=1m∑j=1mijyiyjxT_ixj\max\limits_{\alpha} \sum_{i=1}^{m}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m}\alpha_i \alpha_j y_i y_j x^{T}\_{i} x_jmax​∑i=1m​−21​∑i=1m​∑j=1m​i​j​yi​yj​xT_ixj​ s.t.∑i=1m=iyi=0s.t. \sum_{i=1}^{m} = \alpha_{i}y_{i} = 0s.t.∑i=1m​=i​yi​=0 i≥0,i=1,2,…,m\alpha_{i}\geq 0, i=1,2,…,mi​≥0,i=1,2,…,m

持续优化该问题，有 SMO 办法，SMO 的根本思路是先固定 i\alpha_ii​ 之外的的所有参数，然后求 i\alpha_ii​ 上的极值。

三，K-means 聚类算法

3.1，分类与聚类算法

• 分类简单来说，便是根据文本的特征或特点，划分到已有的类别中。也便是说，这些类别是已知的，通过对已知分类的数据进行练习和学习，找到这些不同类的特征，再对未分类的数据进行分类。
• 聚类，便是你压根不知道数据会分为几类，通过聚类分析将数据或者说用户聚合成几个群体，那便是聚类了。聚类不需要对数据进行练习和学习。
• 分类归于监督学习，聚类归于无监督学习。常见的分类比方决议计划树分类算法、贝叶斯分类算法等聚类的算法最根本的有体系聚类，K-means 均值聚类。

3.2，K-means 聚类算法

聚类的目的是找到每个样本 $x$ 潜在的类别 $y$，并将同类别 $y$ 的样本 $x$ 放在一同。在聚类问题中，假定练习样本是 x1,…,xm{x^1,…,x^m}x1,…,xm，每个 xi∈Rnx^i \in R^nxi∈Rn，没有 $y$。K-means 算法是将样本聚类成 $k$ 个簇（cluster），算法进程如下：

1. 随机选取 $k$ 个聚类中心（cluster centroids）为 1,1,…,k∈Rn\mu_1, \mu_1,…,\mu_k \in R^n1​,1​,…,k​∈Rn。
2. 重复下面进程，直到质心不变或者改变很小：
   • 关于每一个样例 $i$ ，核算其所属类别：ci=argminj∣∣xi−j∣∣2c^i = \underset{j}{argmin}||x^i – \mu_j||^2ci=jargmin​∣∣xi−j​∣∣2
   • 关于每一个类 $j$，重新核算该类的质心：j=∑i=1m1ci=jxi∑i=1m1ci=j\mu_j = \frac {\sum_{i=1}^{m} 1{c^i} = jx^{i}} { \sum_{i=1}^{m}1 c^{i} = j}j​=∑i=1m​1ci=j∑i=1m​1ci=jxi​

$K$ 是咱们事先给定的聚类数，cic^ici 代表样例 $i$ 与 $k$ 个类中距离最近的那个类，cic^ici 的值是 $1$ 到 $k$ 中的一个。质心 j\mu_jj​ 代表咱们对归于同一个类的样本中心点的猜测。

参阅资料

K-means聚类算法