开发者学习笔记【阿里云人工智能工程师ACA认证（2023版）:机器学习经典算法介绍（二）】
课程地址：https://edu.aliyun.com/course/3112108/lesson/19264
机器学习经典算法介绍（二）
四、K近邻算法介绍与应用
1.K近邻算法介绍
接下来是机器学习经典算法介绍里面的k近邻算法介绍与应用。
K近邻算法是用来分类和回归的一个很有趣的算法，它的定义是k近邻是从训练集找出与新实例最近的k个实例，邻居，近邻就是那个邻居，然后根据k个实例进行预测。
这里的定义比较简单，我们来解释，其实这个算法用作分类时，这个算法的思想就是用我们中国话所物以类聚，人以群分，它靠近什么，那它就是属于哪一个分类，可以这样来理解，这个算法里面这个k是指一个变量，不确定的值，从这个周围找几个数据，这个k是确定这个值。
然后我们来看，比如k近邻分类，我们看左下这个图中间这个圆，亮起的这个圆，这个是我们未知的数据，就是未知它的分类的数据。
我们现在要对它进行分类，我们还不知道它是哪一类，怎么对它进行分类，它应该属于哪一类，就看它的近邻，离它最近有几个实例。
为什么这个是k，这k的这个变量的选择，比如k等于3的情况下，这个圆周围的三个实例是一个方的，两个圆的，如果按照这个来看就是圆的多，这时以新的实例就是这个数据黄色的这个数据应该就属于圆，这是在k等于3的情况下，新的实例是属于圆的。
如果k等于5，我们以它为中心，以这个数据为中心去画圆，这个圆刚好画大一点，能够把5个数据都包括进来，这个时候我们发现这个方块已经多过两个圆，这时它的近邻里面方块会更多，这个时候这个新的实例就属于正方形。
这种分类的方法其实是非常简单，而且是非常直观的，它靠近的周围主要是什么就分类就是什么。这里大家也能看到，在使用k近邻算法的时候，这个k值的选择是比较重要的，如果k值选大，选少了是不一样的，所以使用这个算法时可能也是尝试，比如先试3，然后再试4，然后根据你观察到这个情况，再去做判断。
实际上应用上应该是这样的。这是k近邻对未知的数据进行分类的方式，k近邻也可以做回归。也就是如果我们做的不是分类，而是它的这个实例是周围的这个值，我们希望得到的是一个预测值，我们就可以用k近邻回归，这个k的值的变化，这个含义没有变，有周围几个邻居，周围最近的几个邻居。
我们这个新实例的预测值应该是得到结果不是分类，而是最近几个实例k个实例的平均值。如果k等于3，就是周围最近的3个实例的平均值。如果k等于5，就是周围5个实例的平均值，用这种方式也就可以实现回归。
有时大家能看到这个k近邻算法，或者就看到KNN的时候知道就是 k近邻 算法，即这个后面这个近邻就是NN，怎么 NN 就是nearest， neighbor 最近的邻居，这种算法是简单有效的，理解起来也比较简单，然后计算起来也比较简单。然后有效是已经经过证明的。
我们也能刚才也提到这个 k 的选取是有一定关系，但是这个问题不大，尝试一下就可以。但是它不足的地方是它的计算量比较大，对于分类的每一个数据，每一个实例都要找它最近的，这样就比较不能提前优化，所以它也有一些变种，比如可以增加邻居的权重，计算距离时使用不同的计算的方法等。
2.K近邻算法：距离度量
在 k近邻算法里，当给定这个 k 值时，当给定 k 值的时候，需要找到距离这个新的实例最近的 k 个实例，这个距离就要计算，怎么计算这个距离？就是一个问题，特征空间里面两个实例之间的距离是两个实例的相似度的反应，它们相似的程度，两个实例点距离越是相近，就是两个就越相似。
两个点的距离怎么样去评估，如果在一个二维的空间里，这个还是比较简单，像我们这个图里，看左下角的图，两个点 a 和b， a 和 b 的坐标分别是X0， Y0、X1、Y1，你可能直接的就想到他们两个之间距离，画一条直线，就是最近的就是他们之间的距离，这个运算的方法也很简单，就是 X1 减去 X0 的平方，加上 Y1 减去 Y0 的平方，然后再开一个根号，得到的就是第一的这个距离。这个距离在我们这的说法叫欧式距离，这里它计算两个点的直线距离，是用欧式距离的这个计算公式的，这是一种方式。
曼哈顿距离是两个点在标准坐标系上绝对的轴距之和，就是两个点在坐标系上 x 轴、 y 轴， x 轴上面的距离差， y 轴上面的距离差，这个距离的和是一种计算方式。
第二就在左图里面就是红色的这条有折的，取折的这条线。第二如果用公式来计算，第二就是等于X1。减去X0，加上Y1减Y0，两个都是取绝对值的，就是真实的这个距离，这个是曼哈顿距离。
二维的空间都很好理解，欧式距离也好，曼哈顿距离也好，都是表征他们这个相似度差别差多少。
如果你扩展这两个实例，它是比较复杂，在多维空间里面同样也可以用这种方式去计算，欧式距离和马哈顿距离。在这个示例里，我们很容易会认为这个 a 和 b 之间用欧式距离是更好的，但是实际上不一定。比如你是在这个交通路口上面，比如 a 到 b 本来就是要过一个路口转弯，这时候应该是曼华顿距离。所以实际的应用情况，欧式根据这个应用的情况去选择用哪种距离的计算方式，并不是 欧式距离在这里面看起来更像真实的距离就是正确的，它们是用途不同且是不能互相替代的。
五、支持向量机算法介绍与应用
1.支持向量机算法介绍
先学习向量机的基本概念，这只向量机是一类按照监督学习方式对数据进行二元分类的广义线性分类器，其决策边界是对学习样本求解的最大边距超平面。
它应用非常广泛，在机器学习、机器视觉、数据挖掘中都有广泛的应用，主要它是去解决数据的分类问题，它是按照监督学习对数据进行二元分类，二元分类它是一个广义线型分类器。
分类是把这个数据放在一个空间里，然后这次向量机是进行决策时候，是要找到一个超平面，这个超平面特征就是针对这些学习的样本，就是所给出来的学习的数据，找一个最大边距的超平面，找到这个超平面后，用这个超平面进行分类，只能进行二元分类，就算是有多元的分类，也可以把这个多元分类分解成为多个二元分类的问题，然后再进行分类。
支持向量计算法，有时候会看到它的缩写是SVM， SVM 这个 S 就是那个support， v 就是 Vector 那个 v ，M就是machine， SVM 就是 port v Vector machine 支持向量机，这个支持向量机的概念听起来很数学，听起来也不是，就是很抽象，不是很好理解。
所以我们用图形化的方式来解释它，我们还是把这个问题先简单化，简单考虑。比如这个有点还有这个三角形，这些都是我们的学习样本，学习数据。然后我们也是要进行分类，我们开始找决策边界，这里叫做最大边距超平面，因为是平面化，比较简单，我们在这里找的不用是超平面，在这个二维空间里面我们只要找到线就可以，如果立体想象能力好，你可以把它想象成立体空间。
然后我们去寻找一个平面的时候，将左边和右边的图你能看到就是这条直线，这实线，左边和右边的实线都已经把这个数据即三角形和圆形的数据分开了，都已经分开，即一边都是一类的，另一边都是另一类，这个已经完成。但是我们明显的也能感觉出，像右边这种分割的方式会最好，因为右边这个它叫别策决策边界最大化。
左边那个图，虚线就是决策边界，右边是这个实线是决策边界，虚线是间隔边界。这个落在虚线上的点两边都有，就是支持向量。
支持向量级算法就是通过一种方式去找到那个合理的决策边界后，一切问题就变得简单，然后再有新的数据，我们去进行分类时，根据这个边界就能判断它是属于哪一类，这个如果维度很多，不是二维，可以想象它就是去找一个超平面，找到这个平面的一边和另一边就是不同的分类。
支持向量级的算法像是心脏病预测上面，或者是用户切电识别，就是典型应用。
2.线性可分与线性不可分
线性可分是如果样本可以直接使用一个线性函数区分，则称样本线性可分。反之如果样本不能够使用一个线性函数区分，这种就称为线性不可分。
线性函数我们看左下面这个图，比如这个数据，点和三角，圆和三角，它们是可以用一个线划分，这种就是线性可分，在二维的空间里，线性函数是一条直线，在三维的空间里面线性函数就是一个平面，以此类推。
线性不可分的这个情况如果遇到就是没有办法，比如二维空间里面没有办法用一个线性函数来把它分开，这个时候就可以通过升维的方式将低维度映射到高维度来实现线性可分。
升维把这个低维映射到高维，实现线性可分，我们看右下角的这个图，这个图看圆和三角，不管我们怎么去画直线，都不可能实现线性函数的切分，我们可以把它升为到三维的空间，看右边这个图，升维到三维的空间每个点对应的比如这个 1234 还是这四个点，升级到三维空间后，我们可以用一个新的平面，这高维度用一个新的平面来把它分开，这样就实现了线性可分，这就是线性不可分的情况怎么去处理。
换个角度就是也可以发现有这种情况，就是一个数据如果是降维，原来是线性可分的，可能就会变成线性不可分的。为了支持解决支持向量级的线性不可分，我们会引入核函数的概念。
3. 核函数概念雨常用核函数介绍
当数据在原始维度上线性不可分时，这个时候需要进行升维，使得低维的非线性数据变为高维线性可分的数据，核函数可以方便的实现维度的转换。
常见的核函数有四种，一种是线性核函数、径向基核函数、多项式核函数和 sigmode 核函数。我们首先线性核函数，这种主要用于线性可分的情况。
我们可以看到特征空间到收入空间的维度是一样，所以它参数少，速度快。对于线性可分数据分类的效果非常理想。因此我们通常会首先尝试用线性函数来做分类，看看效果如何，如果不行，再更换的其他。
径向基和函数，又叫做高斯径向基核函数，这是一种局部性非常强的函数，局部性非常强，这种可以把一个样本映射到更高位的空间。
核函数是应用最广的一个，无论是大样本还是小样本都有比较好的性能，而且它相对于多项式核函数参数要更少，所以大多数情况下在不知道用什么核函数的时候，优先会使用高斯径向基核函数。
第三种是多项式核函数，可以实现将低维的输入空间映射到高维的特征空间，但是多项式核函数的参数比较多，当多项式的接触比较高的时候，核矩阵的元素会趋于无穷大或者是无穷小，这时候计算复杂度会扩大到无法计算。
最后一种叫 sigmoid 核函数支持向量机实现的是一种多层神经网络，把这个支持向量机当成是多层神经网络就可以。
综上所述，我们在选用核函数的时候，如果对我们的数据有一定的先验知识，就利用先验来选择符合数据分布的和函数，如果不知道，通常使用交叉验证的方式来试用不同的核函数，而误差最小的就是效果最好的核函数。或者也可以将多个核函数结合起来形成混合函数。
六、决策树算法介绍与应用
决策树算法是分类算法里面非常经典的算法，很多教材里面都是把决策树算法放在分类算法里第一个算法，我们这一节主要了解决策树的定义，掌握决策树的类别，熟悉决策树的结构。
1.决策树算法介绍
我们先来学习决策树的定义：决策树是一种叫以树结构形式来表达的预测分析模型，也就是它是一个预测分析模型，怎么表达就是树的形式来表达的，树的结构形式来表达的，所以它的英文名叫 decision tree。 decision tree 就是用来做决策的树，它是一种有监督学习的算法。
决策树主要有两种，一种是叫分类树，一种是回归树。
决策树因为它是树，如果是学过数据结构的应该会比较了解，它是由根节点、内部节点、叶子节点组成。一般一棵决策树它包含一个根节点，若干个内部节点和若干个叶子节点，分支就是用来连接各个节点，决策树是一个树形的结构。
应用场景非常的广泛，比如在银行贷款，预测银行的能不能去放贷，这个判定的数据是有监督的数据，通过银行的数据生成一个决策树，用这个树可以根据用户的这个一些条件，一些数据来判断能不能这个发放贷款。还有比如动物识别，这也是分类的一种情况，知道这个动物是属于哪一个类别，根据某些条件来进行判定。
2.决策树结构
决策树是由节点和分支构成的，我们看右边，右边这是一个决策树，即使你没有学过决策树，看到这个树状的这个结构，就知道它什么意思。输入密码，这个是根节点，然后判断密码的长度，如果是大于20，判断有没有符号，无符号，这个是内部节点。
如果是密码里面有符号，它就是强，就是密码的强度是强，如果没有符号就是中，从这边分值密码长度下面判断，如果密码长度是小于20，判断有无大小写，有是强，密码强度为强，没有是弱。这样一个树状的结构，这里已经能看得出是根节点，有内部节点，有叶子节点。我们可以看到在根节点主要是一些判断的属性，在叶子节点是这个决策进行判断时的值，决策树的模型，得到的模型就是这样的结构，非常的好理解。
决策树跟树形结构跟二叉树非常的像，但是它还可以是二叉树，也可以是多叉树，这种判断在运算中的速度也可以非常的快，但关键的问题是我们怎么样得到决策树，决策树是在机器学习，从数据里面学习得来的，得到这个数之后，我们可以用这个数直接去做预测，做判断，然后可以把这个数存储起来，然后可以再利用。
对于决策树算法，最难的地方是怎样生成从数据里面生成这个决策树，然后这个判断这个决策树的它的效果到底是怎么样，这个模型的质量怎么样，下面我们一起来学习决策树是怎么生成的。
3.决策树建构步骤
决策树的构造通常有三个步骤：
第一是特征选择，然后是决策树的生成，然后是决策树的剪枝。简单就是特征选择就是判断生成树的时候应该是怎样去选取当前的特征作为树的节点。
第二是决策树的生成的算法，生成算法有主要有三种，生成算法的时候要对这个数进行剪枝，避免过拟合。这个剪枝又有预剪枝和后剪枝两种策略。我们首先看特征选择，这里我们先要了解一些信息论的基本的概念。
信息熵是在信息的基础上将有可能产生的信息定义为一个随机变量，这个变量的期望就是信息熵，
信息增益就是用整体的信息熵减掉某一部分特征分裂后的条件熵，如果这个与结果越大，说明这个特征越能消除不确定性。最极端的情况，按照这个特征分裂后的信息增益和信息熵一样，这个特征就可以获得唯一的结果，这个是信息增益的概念。如果只是看信息增益去分类的特别多的这个特征，它的信息增益就会非常大，这时为了平衡，在这个信息增益的基础上，增加这个特征包含的类别的惩罚项，这个放在一起就变成信息增益率。
从信息到信息上到信息增益，增益率主要是我们进行特征选取时，一个原则就是选哪一个特征，对于这个消除不确定性是最大最有效的，就选哪一个特征。
基尼系数也是一种衡量不确定性的信息不确定性的一种方法，它跟信息熵计算出来的结果差距比较小，基本上可以忽略。但是基尼系数计算的要快很多，因为它的计算方式里面没有用到对数。这个和信息熵相同，当类别的概率趋于平均的时候，基尼系数就越大。
信息增益率和基尼系数它都给我们去做特征选择提供了很好的工具。这个决策树生成时主要有这三种算法， ID3，C4. 5 和 CART算法。 ID3 算法在选取特征的时候，主要看这个特征的信息增益是怎么样。 C 4.5决策数，它主要用信息增益率来划分样本。 CART算法，其实它出现的会更早。 CART 这个词其实是分类回归树的英文的缩写，它是采用二元切分的方，如果数据切分，特征值等于切分要求，那么进入左指数，否则进入右指数。数也比较有特点，它既可以处理分类的问题，也可以处理回归的问题。它的分类用基尼系数，基尼系数帮助它去选取最优的特征点和分裂点。它的回归问题采用平方误差总值来选择最优特征分裂点。
这里要注意 ID3 和 C4. 5 都是多叉数，但是 CART是 2 叉数，总的看，在样本量比较小时，建议用 C4. 5，样本量比较大时，简易用 CART算法。在决策树生成的过程中，很可能出现这个决策树会变得非常的复杂，特别是在这个属性非常多，属性特征值也非常多的时候，如果这个决策树非常的复杂，树看起来非常的茂盛，它可能会带来过拟合的情况。
第三是决策树剪枝主要是两种策略，一个是预剪枝，一个是后剪枝。简单就是预剪枝就是在构造过决策树的过程中，边构造就边剪枝，后剪枝就是构造完之后再一起来剪枝。
这就是整个决策树的构建步骤。先进行特征的选择，确定用什么样的特征选择的方式，然后选定用什么样的数的生成的算法。生成的过程中或者是生成后要对树进行剪枝，做完这些后，决策树就构建成功。
