上一篇文章讲述了机器学习的基本知识点，这一篇就开启一些算法的摸索之路。既然我们是前端研发工程师，那就选择ml.js这个库进行编码。本次涉及到的算法包含：KNN、决策树、随机森林、朴素贝叶斯、支持向量机、线性回归、K-均值聚类算法，这七个算法横跨监督学习算法（分类算法、回归算法）、非监督学习算法，可以作为前端入门机器学习的必修课程，也可作为既将到来的端智能时代的必读刊物。

一、监督学习算法

1.1 分类算法

1.1.1 K-近邻分类算法（KNN）

一、定义

如果一个样本在特征空间中的k个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。（通常k是不大于20的整数）

二、优缺点

优点

简单有效
精度高
对异常值不敏感
无须训练

缺点

计算复杂度高、空间复杂度高（计算量大，内存开销大）
必须指定K值，K值选择不当则分类精度不能保证。（K值取很小，容易受到异常点的影响，容易出现过拟合；K值取很大，受到样本均衡问题）

三、计算距离

对于KNN算法，最核心的内容是计算距离，两个样本之间的距离可以通过欧氏距离计算。其计算公式为：

四、应用场景

小数据场景（几千~几万样本），可用于字符识别、文本分类、图像识别等领域

五、代码

const KNN = require('ml-knn');
// 训练集特征
const dataset = [
    [1.0, 1.1],
    [1.0, 1.0],
    [0, 0],
    [0, 0.1]
];
// 训练集目标
const labels = ['A', 'A', 'B', 'B'];
// 实例化KNN算法(进行训练)
const knn = new KNN(dataset, labels, { k: 3});
// 需要进行预测的点
const predictDataSet = [[0, 0], [3, 1]];
// 进行预测
predictLabels = knn.predict(predictDataSet);
console.log(predictLabels);// [ 'B', 'A' ]

1.1.2 决策树

一、定义

决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

二、优缺点

优点

计算复杂度不高
输出结果易于理解
对中间值的缺失不敏感
可以处理连续和种类字段
可以处理不相关特征数据

缺点

可能出现过拟合现象，需要进行剪枝操作
对于各类别样本数量不一致的数据，信息增益偏向于那些更多数值的特征

三、应用场景

常用于解决分类和回归问题，用该算法的前提条件是：

1. 具有决策者期望达到的明确目标
2. 存在决策者可以选择的两个以上的可行的备选方案
3. 存在决策者无法控制的两个以上不确定因素
4. 不同方案在不同因素下的收益或损失可以计算出来
5. 决策者可以估计不确定因素发生的概率

四、重点知识点

信息熵

信息是很抽象的概念，很难进行量化对量，为了解决对信息的量化度量问题，香农提出了“信息熵”的概念。信息熵是在信息的基础上，将有可能产生的信息定义为一个随机变量，变量的期望就是信息熵。信息熵的计算公式为（单位为比特）：

注：熵是用来度量不确定性，熵越大则其不确定性越大，反之越小 2. 信息增益

信息增益在决策树算法中是用来选择特征的指标，信息增益越大，则这个特征的选择性越好，在概率论中定义为：待分类的集合的熵和选定某个特征的条件熵之差。其计算公式为：

注：

g(D, A)表示特征A对训练数据集D的信息增益
H(D)表示集合D的信息熵
H(D|A)表示条件熵

常用算法

（1）ID3算法

ID3算法是采用信息增益作为特征选择的标准，信息增益越大，说明按此特征分类后越能消除信息的不确定性。

（2）C4.5算法

ID3算法具有两大缺点：一个是类别越多的特征计算出的信息增益越大，易导致生成的决策树广而浅；另一个是只能处理离散变量，不能处理连续变量。C4.5是在ID3的算法基础上采用信息增益率作为特征选择，通过增加类别的惩罚因子，规避了类别越多信息增益越大的问题，同时也可以对连续变量通过均值离散化的方式解决无法处理连续变量的问题。

（3）CART算法

C4.5存在不能处理回归问题的缺点，该缺点由CART解决。CART不在通过信息熵的方式选取最优划分特征，而是采用基尼系数（基尼不纯度），两者衡量信息量的作用相当，但基尼系数由于没有对数运算，可大大减少计算开销。

五、代码

const irisDataset = require('ml-dataset-iris');
const { DecisionTreeClassifier } = require('ml-cart');
// 获取训练集中的特征值
const dataSet = irisDataset.getNumbers();
// 获取训练集中的目标值，并转换为标量
const labels = irisDataset
    .getClasses()
    .map(elem => irisDataset.getDistinctClasses().indexOf(elem));
// 实例化决策树的分类器
const dTClassifier = new DecisionTreeClassifier({
    gainFunction: 'gini',
    maxDepth: 10,
    minNumSamples: 3
});
// 进行训练
dTClassifier.train(dataSet, labels);
const predictDataset = [[5.1,3.5,1.4,0.2]];
// 进行预测
const result = dTClassifier.predict(predictDataset);
// 结果转换为对应的文本形式
console.log(result.map(value => irisDataset.getDistinctClasses()[value]));

1.1.3 随机森林

一、定义

在机器学习中，随机森林是一个包含多个决策树的分类器，其输出的类别是由个别树输出的类别的众数而定（随机森林就是通过集成学习的思想将多棵树集成的一种算法，其基本单元是决策树）。

二、优缺点

优点

具有极好的准确率（由集成算法的特点引入）
抗过拟合能力：通过平均决策树，降低过拟合的风险性（由随机这个特点引入）
能够有效地运行在大数据集上，处理具有高维特征的输入样本，而且不需要降维
能够评估各个特征在分类问题上的重要性

缺点

在某些噪音较大的分类或回归问题上会过拟合
比决策树算法更复杂，计算成本更高

三、重要知识点

随机森林的每棵树的生成规则（A表示训练集总样本个数、N表示训练样本个数、M表示特征个数）

（1）对于每棵树随机有放回的从训练集中抽取N个训练样本，作为该树的训练集（2）指定一个常数m<<M，随机地从M个特征中选取m个特征子集，每次树进行分裂时，从这m个特征中选择最优的（3）每棵树都尽最大程度的生长，并且没有剪枝过程。

为什么要随机抽样训练集？

随机抽样是为了保证每棵树的训练集都不一样，若不随机抽样会导致最终训练出的分类结果完全一样。

为什么要有放回的抽样？

有放回的抽样才能保证每次抽取时的概率是一样的，达到独立同分布，可保证每一棵决策树都是相互独立的。

随机森林分类效果（错误率）相关因素？

（1）森林中任意两棵树的相关性：相关性越大，错误率越大

（2）森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低

（注：减小特征选择个数m，树的相关性和分类能力会相应降低，反之会随之增大）

四、代码

const irisDataset = require('ml-dataset-iris');
const { RandomForestClassifier } = require('ml-random-forest');
// 获取训练集中的特征值
const dataSet = irisDataset.getNumbers();
// 获取训练集中的目标值，并转换为标量
const labels = irisDataset
    .getClasses()
    .map(elem => irisDataset.getDistinctClasses().indexOf(elem));
// 实例化分类器
const rFClassifier = new RandomForestClassifier({
    seed: 3,
    maxFeatures: 0.8,
    replacement: true,
    nEstimators: 25
});
// 进行训练
rFClassifier.train(dataSet, labels);
const predictDataset = [[5.1,3.5,1.4,0.2]];
// 进行预测
const result = rFClassifier.predict(predictDataset);
// 结果转换为对应的文本形式
console.log(result.map(value => irisDataset.getDistinctClasses()[value]));

1.1.4 朴素贝叶斯

一、定义

朴素贝叶斯法（NBC）是基于贝叶斯定理与特征条件独立假设的分类方法。先通过已给定的训练集，以特征词之间独立作为前提假设，学习从输入到输出的联合概率分布，再基于学习到的模型，输入X求出使得后验概率最大的输出Y。

二、优缺点

优点

朴素贝叶斯模型发源于古典数学理论，有稳定的分类效率
对缺失数据不敏感，算法简单，常用于文本分类
分类准确度高，速度快

缺点

使用了样本独立性的假设，如果特征属性有关联性，其效果较差

三、应用场景

文本分类
文字识别
图像识别

四、重要知识点

贝叶斯公式

注：贝叶斯公式是打通P(W|C)和P(C|W)的桥梁

为什么引入拉普拉斯平滑系数

为了防止计算出的分类概率为0，所以引入拉普拉斯平滑系数，即让P（W1|C）不为0，其计算公式为：

注：其中α为指定系数，一般为1；m为训练文档中统计出的特征词个数

三种贝叶斯模型

（1）高斯分布朴素贝叶斯——用于一般分类问题

（2）多项式分布朴素贝叶斯——适用于文本数据（特征表示的是次数）

（3）伯努利分布朴素贝叶斯——适用于伯努利分布、文本数据（特征表示的是是否出现）

五、代码

const irisDataset = require('ml-dataset-iris');
const { GaussianNB } = require('ml-naivebayes');
// 获取训练集中的特征值
const dataSet = irisDataset.getNumbers();
// 获取训练集中的目标值
const labels = irisDataset
    .getClasses()
    .map(elem => irisDataset.getDistinctClasses().indexOf(elem));
//实例化分类器
const gaussianNB = new GaussianNB();
// 进行训练
gaussianNB.train(dataSet, labels);
const predictDataset = [[5.1,3.5,1.4,0.2]];
// 进行预测
const result = gaussianNB.predict(predictDataset);
// 结果转换为对应的文本形式
console.log(result.map(value => irisDataset.getDistinctClasses()[value]));

1.1.5 支持向量机

一、定义

支持向量机（SVM）是一类按监督学习方式对数据进行二元分类的广义线性分类器，其决策边界是对学习样本求解的最大边距超平面。

二、优缺点

优点

有严格的数学理论支持，可解释性强，不依靠统计方法，简化了通常的分类和回归问题。
上述支持向量决定了最终结果，对异常值不敏感，可以帮助抓住关键样本，剔除大量冗余样本
该算法简单且具有较好的“鲁棒性”
计算的复杂度取决于支持向量的数目，而不是样本空间的维数，某种意义上避免了“维数灾难”
泛化能力较强

缺点

对大规模训练样本难以实施：SVM的空间消耗主要是存储训练样本和核矩阵，由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的运算，当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。
解决多分类问题困难：经典的支持向量机算法只给出了二类分类算法，解决多分类问题需要通过多个二类支持向量机的组合来解决（一对多组合模式、一对一组合模式和SVM决策树）。
对参数和核函数选择敏感：支持向量机性能的优劣主要取决于核函数的选取。

三、应用场景

SVM在各领域的模式识别问题中有应用，包括人像识别、文本分类、手写字符识别、生物信息学等。

四、重要知识点

重要概念

（1）线性可分：在二维空间上，两类点被一条直线完全分开叫做线性可分

（2）最大间隔超平面：从二维扩展到多维空间中，将两个点集完全正确地划分开就形成一个超平面，为了使这个超平面更具鲁棒性，则会找最佳超平面（即为最大间隔超平面，该平面是以最大间隔把两类样本分开的超平面）。（两类样本分别分割在该超平面的两侧、两侧距离超平面最近的样本点到超平面的距离被最大化了）

（3）支持向量：样本中距离超平面最近的一些点叫支持向量

（4）软间隔：对于不能够完全线性可分的样本可引入软间隔，相比于硬间隔的苛刻条件，软间隔允许个别样本出现在间隔带里面。（注：硬间隔和软间隔均是在说样本的完全线性可分或者大部分样本点的线性可分）

对于线性不可分处理方式

将线性不可分样本映射到高维空间中，使样本在高维空间线性可分，此时由于维度提高会导致计算量增大，所以需要使用核函数帮助处理，引入核函数后就不需要计算高维甚至无穷维空间的内积了。

引入核函数的好处

（1）减少了计算量

（2）减少了存储数据的内存使用量

常见核函数分类

（1）线性核函数（2）多项式核函数（3）高斯核函数

五、代码

const SVM = require('libsvm-js/asm');
const svm = new SVM({
    kernel: SVM.KERNEL_TYPES.RBF,
    type: SVM.SVM_TYPES.C_SVC,
    gamma: 1,
    cost: 1
});
const dataSet = [[0, 0], [1, 1], [1, 0], [0, 1]];
const labels = [0, 0, 1, 1];
// 进行训练
svm.train(dataSet, labels);
// 进行预测
const predictedLabel = svm.pred

1.2 回归算法

1.2.1 线性回归

一、定义

线性回归是利用回归方程（函数）对一个或多个自变量（特征值）和因变量（目标值）之间关系进行建模的一种分析方式。只有一个自变量的情况称为单变量回归，大于一个自变量的情况叫做多元回归。

二、优缺点

优点

思想简单、容易实现、建模迅速，对于小数据量、简单关系情形的很有效
是需要强大的非线性模型的基础
理解容易，其结果具有很好的可解释型，有利于决策分析。
能解决回归问题

缺点

对于非线性数据或者数据特征间具有相关性多项式回归难以建模
难以很好地表达高度复杂的数据

三、应用场景

趋势线（时间序列数据的长期走势）
流行病学
金融（分析和计算投资的系统风险）
经济学（预测消费支出、固定投资支出等）

四、重要知识点

回归目的——预测数值型的目标值
回归性能评价指标——均方误差（MSE）
过拟合

（1）定义：一个建设在训练数据上能够获得比其它假设更好的拟合，但是在测试数据集上却不能很好地拟合数据，此时认为这个假设出现了过拟合现象。（模型过于复杂）

（2）原因：原始特征过多，存在一些嘈杂特征

（3）解决办法：正则化

4.欠拟合

（1）定义：一个假设在训练数据集上不能获得很好的拟合，并且在测试数据集上也不能很好地拟合数据，此时认为这个假设出现了欠拟合的现象。（模型过于简单）

（2）原因：学习到数据的特征过少

（3）解决办法：增加数据的特征数量

正则化

（1）L2正则化

L2正则化可以使得其中一些W都很小（接近于0），削弱某个特征影响。Ridge回归就是用的L2正则化。

（2）L1正则化

L1正则化可以使得其中一些W的值直接为0，删除整个特征的影响。LASSO回归用的就是L1正则化。

五、代码

const SimpleLinearRegression = require('ml-regression-simple-linear');
const x = [0.5, 1, 1.5, 2, 2.5];
const y = [0, 1, 2, 3, 4];
const regression = new SimpleLinearRegression(x, y);
const result = regression.predict(3);
console.log(result);

二、非监督学习算法

2.1 K-均值聚类算法

一、定义

K均值聚类算法是一种迭代求解的聚类分析算法，其步骤为：

随机设置K个特征空间内的点作为初始的聚类中心

对于其它每个点计算到K个中心的距离，位置的点选择最近的一个聚类中心点作为标记类别

接着重新计算出每个聚类的新中心点（平均值）

如果计算得出的新中心点与原中心点一样，则结束，否则重新进行第二步过程

二、优缺点

优点

原理简单，容易实现，算法复杂度低
可解释度较强
处理大数据集的时候，该算法可以保证较好的伸缩性
当簇近似高斯分布的时候效果很好

缺点

K值需要人为设定，不同K值得到的结果不一样
对初始的簇中心敏感，不同选取方式会得到不同结果
对异常值敏感
需样本存在均值（限定数据种类）
不适合太离散的分类、样本类别不均衡的分类、非凸形状的分类
可能收敛到局部最小值

三、代码

const kmeans = require('ml-kmeans');
// 需要进行聚类的全部数据
const data = [[1, 1, 1], [-1, -1, -1], [-1, -1, -1.5], [1, 2, 1]];
// 质心
const centers = [[1, 2, 1], [-1, -1, -1]];
const ans = kmeans(data, 2, {
    initialization: centers
});
console.log(ans);

前端也要懂机器学习（下）

一、监督学习算法

1.1 分类算法

1.1.1 K-近邻分类算法（KNN）

1.1.2 决策树

1.1.3 随机森林

1.1.4 朴素贝叶斯

1.1.5 支持向量机

1.2 回归算法

1.2.1 线性回归

二、非监督学习算法

2.1 K-均值聚类算法

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

前端也要懂机器学习（下）

一、监督学习算法

1.1 分类算法

1.1.1 K-近邻分类算法（KNN）

1.1.2 决策树

1.1.3 随机森林

1.1.4 朴素贝叶斯

1.1.5 支持向量机

1.2 回归算法

1.2.1 线性回归

二、非监督学习算法

2.1 K-均值聚类算法

热门文章

最新文章

相关课程

相关电子书

相关实验场景