ARTS-for-week5

每周完成一个ARTS：

每周至少做一个 leetcode 的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的技术文章。（也就是 Algorithm、Review、Tip、Share 简称ARTS）

Algorithm

LeetCode 2. Add Two Numbers链接难度：[Medium]

【题意】

You are given twonon-emptylinked lists representing two non-negative integers. The digits are stored inreverse orderand each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

【思路】

算法很简单，链表的数据类型也不难。就是建立一个新链表，然后一步一步把输入的两个链表从头往后扫描计算，每碰到两个数相加，添加一个新节点到新链表后面，注意就是要处理下进位问题。还有就是最高位的进位问题要最后特殊处理一下。

【参考代码】

Review

A Tour of The Top 10 Algorithms for Machine Learning Newbies

In machine learning

新手必学的机器学习常用十大算法

机器学习算法可以通俗的描述为学习一个目标函数(F)，能将一系列输入变量(X)最佳映射到输出变量(Y)使得Y = F(X)。

这是一个通用的学习任务，更进一步说，我们希望在未来(Y)中给出新的输入变量(X)示例。我们不知道函数(F)的外观或形式。如果我们这样做，我们将直接使用它，而不需要使用机器学习算法从数据中学习它。

最常见的机器学习类型是学习映射Y = F(X)。来预测新X的Y

这种被称为预测建模或预测分析，我们的目标是使最准确的预测成为可能。

对于渴望了解机器学习基础的机器学习新手，以下将介绍常见的数据科学家使用的十大机器学习算法。

（PS：以下介绍的机器学习算法都是属于有监督学习的机器学习算法。）

1 — Linear Regression（线性回归）

线性回归可能是统计学和机器学习中最知名且易于理解的算法之一。 预测建模主要关注最小化模型的误差或使可能性最准确的预测，但代价是可解释性。 我们将从许多不同的领域借用，重用和窃取算法，包括统计数据并将其用于这些目的。 线性回归的表示是通过查找称为系数（B）的输入变量的特定权重来描述最符合输入变量（x）和输出变量（y）之间关系的线的等式。

例如：y = B0 + B1 * x

我们将在给定输入x的情况下预测y，并且线性回归学习算法的目标是找到系数B0和B1的值。

可以使用不同的技术从数据中学习线性回归模型，例如用于普通最小二乘的线性代数解和梯度下降优化。

线性回归已经存在了200多年，并且已经被广泛研究。 使用此技术时，一些好的经验法则是删除非常相似（相关）的变量，并尽可能消除数据中的噪声。 这是一种快速而简单的技术和良好的第一种算法。

2 — Logistic Regression（逻辑回归）

逻辑回归是从统计领域的机器学习中借用的另一种技术。 它是二进制分类问题的首选方法（两个类值的问题）。 逻辑回归就像线性回归一样，目标是找到加权每个输入变量的系数的值。 与线性回归不同，使用称为逻辑函数的非线性函数来转换输出的预测。 逻辑函数看起来像一个大 S 并将任何值转换为 0 到 1 的范围。这很有用，因为我们可以将一个规则应用于逻辑函数的输出以将值捕捉到 0 和 1（例如 IF 小于0.5然后 输出1）并预测一个类值。

由于学习模型的方式，逻辑回归所做的预测也可以用作属于 0 级或 1 级的给定数据实例的概率。这对于需要给出更多基本原理的问题非常有用。 一个预测。

与线性回归一样，当您删除与输出变量无关的属性以及彼此非常相似（相关）的属性时，逻辑回归确实更有效。 这是学习二元分类问题并快速有效的快速模型。

3 — Linear Discriminant Analysis（线性判别分析）

Logistic 回归是一种传统上仅限于两类分类问题的分类算法。 如果有两个以上的类，那么线性判别分析算法是首选的线性分类技术。 LDA的代表非常简单。 它包含数据的统计属性，为每个类计算。 对于单个输入变量，这包括：每个类的平均值。 在所有类别中计算的方差。

通过计算每个类的判别值并对具有最大值的类进行预测来进行预测。 该技术假设数据具有高斯分布（钟形曲线），因此最好事先从数据中删除异常值。 它是分类预测建模问题的一种简单而强大的方法。

4 — Classification and Regression Trees（分类和回归树==决策树）

决策树是预测建模机器学习的一种重要算法。

决策树模型的表示是二叉树。 这是来自算法和数据结构的二叉树，没什么太花哨的。 每个节点代表一个输入变量（x）和该变量上的分裂点（假设变量是数字）。

树的叶节点包含用于进行预测的输出变量（y）。通过遍历树的分裂直到到达叶节点并在该叶节点处输出类值来进行预测。

决策树学习速度快，预测速度非常快。它们通常对于广泛的问题也是准确的，并且不需要对数据进行任何特殊准备。

5 — Naive Bayes（朴素贝叶斯）

朴素贝叶斯之所以朴素，因为它假设每个输入变量是独立的。 这是一个强有力的假设，对于实际数据是不现实的，然而，该技术对于大范围的复杂问题非常有效。

6 — K-Nearest Neighbors（K-近邻）

KNN算法非常简单且非常有效。 KNN的模型表示是整个训练数据集。

通过搜索K个最相似的实例（邻居）的整个训练集并总结那些K个实例的输出变量，对新数据点进行预测。 对于回归问题，这可能是平均输出变量，对于分类问题，这可能是模式（或最常见）类值。

诀窍在于如何确定数据实例之间的相似性。 如果属性都具有相同的比例（例如以英寸为单位），则最简单的技术是使用欧几里德距离，那么可以根据每个输入变量之间的差异直接计算该数字。

KNN可能需要大量内存或空间来存储所有数据，但只在需要预测时才进行计算（或学习），及时。 还可以随着时间的推移更新和策划您的训练实例，以保持预测准确。

距离或接近度的概念可以在非常高的维度（许多输入变量）中分解，这会对算法在问题上的性能产生负面影响。 这被称为维度的诅咒。 建议仅使用与预测输出变量最相关的输入变量。

7 — Learning Vector Quantization（学习矢量量化）

K-Nearest Neighbors 的缺点是你需要整个训练数据集。 学习矢量量化算法（或简称 LVQ）是一种人工神经网络算法，允许指定选择的训练实例数量，并准确了解这些实例应该是什么样子。

LVQ 的表示是 codebook vectors 向量的集合。 这些是在开始时随机选择的，并且适于在学习算法的多次迭代中最佳地总结训练数据集。 在学习之后，可以使用 codebook vectors 向量来进行与 K-Nearest Neighbors 类似的预测。 通过计算每个 codebook vectors 矢量和新数据实例之间的距离来找到最相似的邻居（最佳匹配码本矢量）。 然后返回最佳匹配单元的类值或（回归情况下的实际值）作为预测。 如果将数据重新缩放至相同范围（例如0到1之间），则可获得最佳结果。

如果发现 KNN 在的数据集上提供了良好的结果，则可以请尝试使用LVQ来降低存储整个训练数据集的内存要求。

8 — Support Vector Machines（支持向量机）

支持向量机可能是最流行和最受关注的机器学习算法之一。

超平面指的是分割输入变量空间的直线。 在 SVM 中，选择超平面以最好地将输入变量空间中的点与它们的类（0级或1级）分开。在二维中，我们可以将其视为一条线，并假设我们的所有输入点都可以 被这条线完全分开。 SVM 学习算法找到导致超平面最好地分离类的系数。

超平面和最近数据点之间的距离称为边距。 可以分离两个类的最佳或最佳超平面是具有最大边距的线。 只有这些点与定义超平面和分类器的构造有关。 这些点称为支持向量。 它们支持或定义超平面。 实际上，优化算法用于找到使裕度最大化的系数的值。

SVM 可能是最强大的开箱即用分类器之一，值得在数据集上使用。

9 — Bagging and Random Forest（随机森林）

随机森林是最流行和最强大的机器学习算法之一。 它是一种称为 Bootstrap Aggregation 或bagging 的集成机器学习算法。

引导程序是用于从数据样本估计数量的强大统计方法。 比如一个意思。 您可以获取大量数据样本，计算平均值，然后平均所有平均值，以便更好地估计真实平均值。

在 bagging 中，使用相同的方法，但是用于估计整个统计模型，最常见的是决策树。 获取训练数据的多个样本，然后为每个数据样本构建模型。 当您需要对新数据进行预测时，每个模型都会进行预测，并对预测进行平均以更好地估计真实输出值。

随机森林是对这种方法的一种调整，其中创建决策树，使得不是选择最佳分裂点，而是通过引入随机性来进行次优分割。

因此，为每个数据样本创建的模型与其他情况相比更加不同，但仍然以其独特和不同的方式准确。 结合他们的预测可以更好地估计真实的基础产值。

如果使用具有高方差的算法（如决策树）获得良好的结果，通常可以通过 bagging 算法获得更好的结果。

10 — Boosting and AdaBoost（集成学习）

Boosting 是一种集合技术，试图从许多弱分类器中创建一个强分类器。这是通过从训练数据构建模型，然后创建第二个模型来尝试从第一个模型中纠正错误来完成的。添加模型直到完美预测训练集或添加最大数量的模型。

AdaBoost 是第一个为二进制分类开发的真正成功的增强算法。这是理解助力的最佳起点。现代助推方法建立在 AdaBoost 上，最着名的是随机梯度增强机。

AdaBoost 用于短决策树。在创建第一个树之后，每个训练实例上的树的性能用于加权创建的下一个树应该关注每个训练实例的注意力。难以预测的训练数据被赋予更多权重，而易于预测的实例被赋予更少的权重。模型是一个接一个地顺序创建的，每个模型更新训练实例上的权重，这些权重影响序列中下一个树所执行的学习。构建完所有树之后，将对新数据进行预测，并根据训练数据的准确性对每棵树的性能进行加权。 因为通过算法如此关注纠正错误，所以必须删除带有异常值的干净数据。

Tip

一条 SQL 查询语句到底是如何执行的？

MySQL 数据库相信大家都不陌生，开发技术人员几乎每天都要和它打交道，但是当我们在命令终端或数据库可视化软件输入 这样一条最常见的 SQL 语句

时，你是否问过自己，这条 SQL 查询语句到底是如何执行的？它内部的逻辑，处理流程到底是怎样的？

我们来看下面这张图：

MySQL 的逻辑架构图

大体来说, MySQL 可以分为 Server 层和存储引|擎层两部分。

Server 层包括连接器、查询缓存、分析器、优化器、执行器等,涵盖 MySQL 的大多数核心服务功能,以及所有的内置函数(如日期、时间、数学和加密函数等) ,所有跨存储引擎的功能都在这一层实现，比如存储过程、触发器、视图等。

而存储引|擎层负责数据的存储和提取。其架构模式是插件式的,支持 InnoDB、MyISAM、Memory 等多个存储引擎。现在最常用的存储引擎是 InnoDB ,它从 MySQL 5.5.5版本开始成为了默认存储引擎。

也就是说

你执行 create table 建表的时候,如果不指定引擎类型,默认使用的就是 InnoDB。不过,你也可以通过指定存储弓擎的类型来选择别的引擎,比如在 create table 语句中使用来指定使用内存引擎创建表。不同存储引擎的表数据存取方式不同,支持的功能也不同。

从图中不难看出,不同的存储引擎共用一个 Server 层,也就是从连接器到执行器的部分。

Share

QR 二维码是怎么生成的？

本文通过一个实例，一步步演示二维码的生成算法。