python中算法实现

在之前的文章中有介绍过感知器，自适应线性神经网络(Adaptive Linear Neuron,Adaline)是在Frank Rosenblatt提取感知器算法之后的几年，Bernard Widrow和Tedd Hoff提出的Adaline算法，它是对感知器算法的改进。它的核心思想是通过对代价函数做最小优化，这也是机器学习算法的核心思想，以及之后的逻辑斯蒂回归、支持向量机等都采用了这种思想。Adeline算法更新权重的规则是通过一个联系的线性激励函数来完成的，而之前的感知器算法是通过单位阶跃函数（在0处不连续），这是两种算法最主要的区别。线性激励函数在更新权重的同时，我们使用量化器对类标进行预测，这里所使用的量化器其实也是一个单位阶跃函数，量化器的使用是在训练好模型之后，通过量化器来预测类标。

自适应线性神经元

一、代价函数

代价函数就是指在机器学习的监督算法中，在学习阶段我们需要定义一个目标函数，而这个目标函数通常是需要我们做最小优化处理的代价函数。在Adeline算法中，所使用的代价函数是模型的预测值与实际值之间的误差平方和，公式如下，系数为1/2的目的是为了方便与求导之后的2相乘抵消，方便计算。

代价函数

连续激励函数相对于单位阶跃函数的优点：

1、代价函数可导

2、代价函数是一个凸函数，可以通过梯度下降算法求权重，而且能保证模型对样本进行分类时代价函数最小

通过下面的图来了解梯度下降的过程：

梯度下降

可以将梯度下降的过程理解成一个下山的过程，想象一下你站在山顶，为了能保证以最快的速度下上，你会寻找一个梯度最大的方向迈出一步。想象一下，当长度一样的时候，坡度越陡（梯度越大）的时候，是不是垂直方向的长度是最大的，y = x sinα，当阿尔法为90度的时候，y最大。下上的步长就由学习速率和梯度的斜率决定。

为什么是梯度的反方向而不是梯度方向？

因为梯度的反方向是函数值下降最快的方向，而梯度方向是函数值增长最快的方向，这里推荐一篇知乎专栏博客的解释https://zhuanlan.zhihu/p/24913912，为了便于大家理解，通过上面的梯度下降图简单介绍一下，对于只有一个自变量的情况下，函数的斜率就是导数，而有两个及以上的自变量的时候被称为偏导。当只有一个自变量的时候，梯度其实也就是导数。可以看到初始的ω值是大于全局最小值所对应的ω，如果想要让初始的ω向全局最小值所对应的ω靠近，那么我们就需要增加初始的ω的值，而在初始ω所对应的梯度（导数）是小于0的，为了事ω的值增加，所以应该是梯度的反方向，当初始值在全局最小值的右边的时候也是这样的。

下面推导一下代价函数对于某一个权重的偏导数

仔细一看，最后推导出来的公式貌似和之前的感知器的好像是一样的，其实不一样，感知器的激活函数是阶跃函数，而自适应线性神经元的激活函数是线性的（f(x)=x）。而且在训练模型的时候，自适应线性神经元的权重更新是基于训练集中的所有样本完成的，而感知器是每次一个样本进行权重更新，所以这种更新权重的方法被称之为批量梯度下降算法。

二、python实现自适应神经线性单元

1、初始化自适应线性神经元

2、通过权重和输入来计算输出

3、定义线性激活函数f(x)=x

4、根据输入和权重预测输出类标

5、通过输入和输出数据训练模型获取权重

（1）不使用eval()等系统自带的计算方法

（2）实现四则混合运算、括号优先级解析

思路：

1、字符串预处理，将所有空格去除

2、判断是否存在括号运算，若存在进行第3步，若不存在则直接进入第4步

3、利用正则表达式获取最底层括号内的四则运算表达式

4、将四则运算表达式进行预处理：表达式开头有负数时，在表达式前加上一个0

5、利用re.split()、re.findall()方法，通过加减符号，对四则运算进行拆分为乘除运算式和数字，并保留对应的位置下标。

6、利用re.split()、re.findall()方法，通过乘除符号，将乘除式拆分为乘除符号与数字，然后进行计算，并返回数值。

7、通过re.split()、re.findall()保留的下标位置，将表达式还原。

8、完成所有乘除运算之后，返回进行加减运算。

9、完成加减运算后，返回表达式进行替代。

10、通过递归函数，完成所有括号运算后。最后再完成一次四则运算即可完成所有运算。

注：在过程中，负数的处理存在三个要点：当负数出现在表达式开头、负数前面存在减法、乘除式中存在负数且不在表达式开头。

（1）当负数出现在表达式开头：在前面加上一个0

（2）负数前面存在减法：每次完成一次运算后需要进行一次符号检查替换

（3）乘除式中存在负数且不在表达式开头：将负号移到表达式最开头

更多腾讯海量技术文章，请关注云+社区：https://cloud.tencent/developer

k近邻法（或简称为kNN）是一种易于理解和实现的算法，也是一种功能强大的工具。

在本教程中，您将学会使用Python（2.7）从零开始实现k近邻（k-Nearest Neighbors）算法。并将这一算法使用在具体的分类问题上，并对鸢尾花分类问题进行论证。

如果你是一名Python程序员，或是一个能够快速学会python的程序员，本教程适合你，当然你还要对如何从头开始实现k近邻算法算法感兴趣。

k-Nearest Neighbors算法 （图片来自维基百科，保留所有权利）

什么是k近邻算法

kNN的模型是整个训练数据集。当一个不可见的数据实例需要预测时，kNN算法将通过训练数据集搜索k个最相似的实例，并汇总最相似实例的预测属性，将其作为不可见数据实例的预测返回。

相似性的度量取决于数据的类型。对于实值数据，可以使用欧氏距离。其他类型的数据，如分类或二进制数据，可以使用汉明距离。

在回归问题的情况下，可以返回预测属性的平均值。在分类的情况下，会返回最可能的类别。

k近邻算法如何工作

kNN算法属于基于数据实例的竞争学习和即时学习算法。

基于实例的算法是那些使用数据实例（或单条数据）对问题进行建模以便做出预测性决策的算法。kNN算法是基于实例的算法的一种极端形式，因为所有的训练观察值都保留为模型的一部分。

这是一种竞争学习算法，因为它在内部使用模型元素（数据实例）之间的竞争来作出预测性决策。数据实例之间的客观相似性度量使得每个数据实例与“胜利”竞争或者与给定的不可见数据实例最相似并对预测进行贡献。

即时学习指的是这个算法直到需要预测的时候才建立一个模型。这是“懒惰”，因为它只在最后一秒工作。这样做的好处是只包括与不可见的待预测数据相关的数据，称为本地化模型。缺点是在较大的训练数据集上重复相同或类似的搜索可能使计算量难以承受。

最后，kNN是强大的，因为它不会假设任何关于数据的内容，除了可以在任何两个实例之间一致地计算距离度量。因此，它被称为非参数或非线性的，因为它不具有函数形式。

使用测量数据分类鸢尾花

我们将在本教程中使用鸢尾花分类问题作为测试。

问题是由三种不同种类的鸢尾花的150个观察结果组成。给定的花有4种测量值：萼片长度，萼片宽度，花瓣长度和花瓣宽度，全部以厘米为单位。预测属性是种类，看看数据实例属于setosa，versicolor或者virginica三种花的哪一种。

这是一个标准的数据集，其中的物种数据已知所有情况。因此，我们可以将数据分成训练和测试数据集，并使用预测结果来对我们的算法实现进行评估。正确的对这个问题的分类准确度要求在90％以，通常是96％或更好。

您可以从iris.data（https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data）免费下载数据集，也可参阅资源部分了解更多详情。

如何在Python中实现k近邻算法

本教程分为以下几个步骤：

数据处理：从CSV文件导入数据集并分割成测试/训练数据集。

相似度：计算两个数据实例之间的距离。

近邻：找到k个最相似的数据实例。

响应：从一组数据实例生成响应。

准确性：总结预测的准确性。

集成：把算法各部分集成在一起。

1.处理数据

我们需要做的第一件事是加载我们的数据文件。数据为CSV格式，没有标题行或任何引号。我们可以使用open函数打开文件，并使用csv库中的reader函数逐行读取数据。

接下来，我们需要将数据拆分成可被kNN用于预测的训练数据集，以及可用于评估模型准确性的测试数据集。

我们首先需要将作为字符串类型加载的花朵测量值转换为我们可以使用的数字类型。接下来，我们需要将数据集随机分成训练和测试数据集。训练/测试的比例为67/33，是使用的标准比率。

综合起来，我们可以定义一个名为loadDataset的函数，它使用提供的文件名加载一个CSV文件，并使用提供的分割比例随机地将其分割为火车和测试数据集。

将鸢尾花数据集CSV文件下载到本地目录。我们可以用我们的该数据集来测试这个函数，如下所示：

2.相似性

为了做出预测，我们需要计算任意两个给定数据实例之间的相似度。这是必要的，以便我们可以在训练数据集中为测试数据集的给定成员定位k个最相似的数据实例，从而进行预测。

考虑到花朵的四种测量属性都是数字类型的，并且具有相同的单位，我们可以直接使用欧几里得距离度量。这被定义为两个数字数组之间的平方差的总和的平方根（再读几次，真正理解它）。

此外，我们要控制哪些字段包含在距离计算中。具体来说，我们只想包含前4个属性。一种方法是将欧氏距离限制在一个固定的长度，忽略超出的内容。

把所有这些放在一起，我们可以定义euclideanDistance函数如下：

我们可以用一些示例数据来测试这个函数，如下所示：

3.近邻

现在我们有了一个相似性度量，我们可以用它为一个给定的不可见的实例收集k个最相似的实例。

这是计算所有实例的距离和选择具有最小距离值的子集的直接过程。

下面是getNeighbors函数，该函数从给定测试实例的训练集中返回k个最相似的邻居（使用已定义的euclideanDistance函数）

我们可以测试这个函数，如下：

4.响应

一旦找到测试实例最相似的邻居，下一个任务是根据这些邻居设计一个预测的响应。

我们可以通过允许每个邻居为他们的类属性进行投票来做到这一点，并以多数票作为预测。

以下提供了获得多个邻居的多数投票答复的功能。它假定所分种类是每个邻居的最后一个属性。

我们可以用一些测试邻居来测试这个函数，如下所示：

这种方法在特定的情况下返回一个响应，但是您可以以特定方式处理这些情况，例如不返回响应或选择无偏差的随机响应。

5.准确性

我们已经实现了全部的kNN算法。剩下的一个重要问题是如何评估预测的准确性。

评估模型准确性的简单方法是计算所有预测中所有正确预测的比例，称为分类准确率。

下面是getAccuracy函数，将总体正确预测相加，并以正确分类的百分比形式返回准确性：

我们可以用一个测试数据集和预测来测试这个函数，如下所示：

6.集成

我们现在拥有算法的所有元素，我们可以将它们与主函数结合在一起。

下面是在Python中从头开始实现kNN算法的完整示例。

运行该示例，您将看到每个预测的结果与测试集中的实际类别值相比较。在运行结束时，您将看到模型的准确性。在这种情况下，略高于98％。

一些扩展问题

本节为您提供继续扩展的一些思路，您可以使用您在本教程中实现的Python代码进行尝试。

回归：可以使实现适应回归问题（预测实值属性）。总结最接近的实例可能涉及到预测属性的平均值或中值。

规范化：当度量单位在属性之间不同时，某种属性可能在对距离度量的贡献中占主导地位。对于这些类型的问题，在计算相似性之前，您需要将所有数据属性重新缩放到0-1范围内（称为归一化）。更新模型以支持数据规范化。

可选的距离度量：有很多距离度量可用，你甚至可以开发自己的域特定的距离度量，如果你喜欢。实施一个可选的距离测量，如曼哈顿距离或矢量点乘。

关于这个算法还有更多的扩展，也许你会想要探索一下。另外两个思路包括支持与预测的k个最相似实例的距离加权和用于搜索相似实例的更高级的基于数据树的结构。

了解更多

本节将提供一些资源，您可以使用这些资源来了解有关k邻近算法的更多信息，从算法的工作原理和工作原理以及在代码中实现它们的实际问题两方面进行了解。

问题

维基百科上的鸢尾花数据集（http://en.wikipedia.org/wiki/Iris_flower_data_set）

UCI机器学习知识库Iris数据集（https://archive.ics.uci.edu/ml/datasets/Iris）

代码

本节链接到流行的机器学习库中kNN的开源实现。如果您正在考虑实施您自己的操作使用方法，请查看这些内容。

在scikit-learn中实现kNN（https://github/scikit-learn/scikit-learn/tree/master/sklearn/neighbors）

在Weka中实施kNN（非官方）

（https://github/baron/weka/blob/master/weka/src/main/java/weka/classifiers/lazy/IBk.java）

书

你可能有一本或多本关于应用机器学习的书籍。本部分重点介绍机器学习常用的应用书中关于k近邻法的章节。

Applied Predictive Modeling, pages 159 and 350.

Data Mining: Practical Machine Learning Tools and Techniques, Third Edition (The Morgan Kaufmann Series in Data Management Systems), pages 76, 128 and 235.

Machine Learning for Hackers, Chapter 10.

Machine Learning in Action, Chapter 2.

Programming Collective Intelligence: Building Smart Web 2.0 Applications, Chapters 2 and 8 and page 293.

教程摘要

在本教程中，您了解了k-Nearest Neighbor算法，它是如何工作的以及可用于思考算法并将其与其他算法关联的一些比喻。建议您从头开始在Python中实现kNN算法，这样您就可以了解每一行代码，并且可以调整算法实现并探索扩展以满足自己的项目需求。

以下是本教程的5个关键知识：

k-最近邻：一个简单的算法来理解和实现，以及一个强大的非参数方法。

基于实例的方法：使用数据实例（观察）对问题进行建模。

竞争学习：学习和预测决策是通过模型元素之间的内部竞争来实现的。

即时学习：一个模型直到需要时才被构建出来，以便进行预测。

相似度量：计算数据实例之间的目标距离度量是该算法的一个关键特征。

最后，回顾一下，你使用这个教程实现了kNN吗？你怎么实现的的？你学会了什么？

翻译人：hzr，该成员来自云+社区翻译社

原文链接：https://machinelearningmastery/tutorial-to-implement-k-nearest-neighbors-in-python-from-scratch/

原文作者：Jason Brownlee

选自Machine Learning Mastery作者：Jason Brownlee机器之心编译参与：沈泽江、吴攀

决策树算法是一个强大的预测方法，它非常流行。因为它们的模型能够让新手轻而易举地理解得和专家一样好，所以它们比较流行。同时，最终生成的决策树能够解释做出特定预测的确切原因，这使它们在实际运用中倍受亲睐。

同时，决策树算法也为更高级的集成模型（如 bagging、随机森林及 gradient boosting）提供了基础。

在这篇教程中，你将会从零开始，学习如何用 Python 实现《Classification And Regression Tree algorithm》中所说的内容。

在学完该教程之后，你将会知道：

如何计算并评价数据集中地候选分割点（Candidate Split Point）如何在决策树结构中排分配这些分割点如何在实际问题中应用这些分类和回归算法

一、概要

本节简要介绍了关于分类及回归树（Classification and Regression Trees）算法的一些内容，并给出了将在本教程中使用的钞票数据集（Banknote Dataset）。

1.1 分类及回归树

分类及回归树（CART）是由 Leo Breiman 提出的一个术语，用来描述一种能被用于分类或者回归预测模型问题的回归树算法。

我们将在本教程中主要讨论 CART 在分类问题上的应用。

二叉树（Binary Tree）是 CART 模型的代表之一。这里所说的二叉树，与数据结构和算法里面所说的二叉树别无二致，没有什么特别之处（每个节点可以有 0、1 或 2 个子节点）。

每个节点代表在节点处有一个输入变量被传入，并根据某些变量被分类（我们假定该变量是数值型的）。树的叶节点（又叫做终端节点，Terminal Node）由输出变量构成，它被用于进行预测。

在树被创建完成之后，每个新的数据样本都将按照每个节点的分割条件，沿着该树从顶部往下，直到输出一个最终决策。

创建一个二元分类树实际上是一个分割输入空间的过程。递归二元分类（Recursive Binary Splitting）是一个被用于分割空间的贪心算法。这实际上是一个数值过程：当一系列的输入值被排列好后，它将尝试一系列的分割点，测试它们分类完后成本函数（Cost Function）的值。

有最优成本函数（通常是最小的成本函数，因为我们往往希望该值最小）的分割点将会被选择。根据贪心法（greedy approach）原则，所有的输入变量和所有可能的分割点都将被测试，并会基于它们成本函数的表现被评估。（译者注：下面简述对回归问题和分类问题常用的成本函数。）

回归问题：对落在分割点确定区域内所有的样本取误差平方和（Sum Squared Error）。分类问题：一般采用基尼成本函数（Gini Cost Function），它能够表明被分割之后每个节点的纯净度（Node Purity）如何。其中，节点纯净度是一种表明每个节点分类后训练数据混杂程度的指标。

分割将一直进行，直到每个节点（分类后）都只含有最小数量的训练样本或者树的深度达到了最大值。

1.2 Banknote 数据集

Banknote 数据集，需要我们根据对纸币照片某些性质的分析，来预测该钞票的真伪。

该数据集中含有 1372 个样本，每个样本由 5 个数值型变量构成。这是一个二元分类问题。如下列举 5 个变量的含义及数据性质：

1. 图像经小波变换后的方差（Variance）（连续值）

2. 图像经小波变换后的偏度（Skewness）（连续值）

3. 图像经小波变换后的峰度（Kurtosis）（连续值）

4. 图像的熵（Entropy）（连续值）

5. 钞票所属类别（整数，离散值）

如下是数据集前五行数据的样本。

3.6216,8.6661,-2.8073,-0.44699,0

4.5459,8.1674,-2.4586,-1.4621,0

3.866,-2.6383,1.9242,0.10645,0

3.4566,9.5228,-4.0112,-3.5944,0

0.32924,-4.4552,4.5718,-0.9888,0

4.3684,9.6718,-3.9606,-3.1625,0

使用零规则算法（Zero Rule Algorithm）来预测最常出现类别的情况（译者注：也就是找到最常出现的一类样本，然后预测所有的样本都是这个类别），对该问的基准准确大概是 50%。

你可以在这里下载并了解更多关于这个数据集的内容：UCI Machine Learning Repository。

请下载该数据集，放到你当前的工作目录，并重命名该文件为 data_banknote_authentication.csv。

二、教程

本教程分为五大部分：

1. 对基尼系数（Gini Index）的介绍

2.（如何）创建分割点

3.（如何）生成树模型

4.（如何）利用模型进行预测

5. 对钞票数据集的案例研究

这些步骤能帮你打好基础，让你能够从零实现 CART 算法，并能将它应用到你子集的预测模型问题中。

2.1 基尼系数

基尼系数是一种评估数据集分割点优劣的成本函数。

数据集的分割点是关于输入中某个属性的分割。对数据集中某个样本而言，分割点会根据某阈值对该样本对应属性的值进行分类。他能根据训练集中出现的模式将数据分为两类。

基尼系数通过计算分割点创建的两个类别中数据类别的混杂程度，来表现分割点的好坏。一个完美的分割点对应的基尼系数为 0（译者注：即在一类中不会出现另一类的数据，每个类都是「纯」的），而最差的分割点的基尼系数则为 1.0（对于二分问题，每一类中出现另一类数据的比例都为 50%，也就是数据完全没能被根据类别不同区分开）。

下面我们通过一个具体的例子来说明如何计算基尼系数。

我们有两组数据，每组有两行。第一组数据中所有行都属于类别 0（Class 0），第二组数据中所有的行都属于类别 1（Class 1）。这是一个完美的分割点。

首先我们要按照下式计算每组数据中各类别数据的比例：

proportion = count(class_value) / count(rows)

那么，对本例而言，相应的比例为：

group_1_class_0 = 2 / 2 = 1group_1_class_1 = 0 / 2 = 0group_2_class_0 = 0 / 2 = 0group_2_class_1 = 2 / 2 = 1

基尼系数按照如下公式计算：

gini_index = sum(proportion * (1.0 - proportion))

将本例中所有组、所有类数据的比例带入到上述公式：

gini_index = (group_1_class_0 * (1.0 - group_1_class_0)) +(group_1_class_1 * (1.0 - group_1_class_1)) +(group_2_class_0 * (1.0 - group_2_class_0)) +(group_2_class_1 * (1.0 - group_2_class_1))

化简，得：

gini_index = 0 + 0 + 0 + 0 = 0

如下是一个叫做 gini_index() 的函数，它能够计算给定数据的基尼系数（组、类别都以列表（list）的形式给出）。其中有些算法鲁棒性检测，能够避免对空组除以 0 的情况。

# Calculate the Gini index for a split datasetdef gini_index(groups, class_values):gini = 0.0for class_value in class_values:for group in groups:size = len(group)if size == 0:continueproportion = [row[-1] for row in group].count(class_value) / float(size)gini += (proportion * (1.0 - proportion))return gini

我们可以根据上例来测试该函数的运行情况，也可以测试最差分割点的情况。完整的代码如下：

# Calculate the Gini index for a split datasetdef gini_index(groups, class_values):gini = 0.0for class_value in class_values:for group in groups:size = len(group)if size == 0:continueproportion = [row[-1] for row in group].count(class_value) / float(size)gini += (proportion * (1.0 - proportion))return gini# test Gini valuesprint(gini_index([[[1, 1], [1, 0]], [[1, 1], [1, 0]]], [0, 1]))print(gini_index([[[1, 0], [1, 0]], [[1, 1], [1, 1]]], [0, 1]))

运行该代码，将会打印两个基尼系数，其中第一个对应的是最差的情况为 1.0，第二个对应的是最好的情况为 0.0。

1.00.0

2.2 创建分割点

一个分割点由数据集中的一个属性和一个阈值构成。

我们可以将其总结为对给定的属性确定一个分割数据的阈值。这是一种行之有效的分类数据的方法。

创建分割点包括三个步骤，其中第一步已在计算基尼系数的部分讨论过。余下两部分分别为：

1. 分割数据集。

2. 评价所有（可行的）分割点。

我们具体看一下每个步骤。

2.2.1 分割数据集

分割数据集意味着我们给定数据集某属性（或其位于属性列表中的下表）及相应阈值的情况下，将数据集分为两个部分。

一旦数据被分为两部分，我们就可以使用基尼系数来评估该分割的成本函数。

分割数据集需要对每行数据进行迭代，根据每个数据点相应属性的值与阈值的大小情况将该数据点放到相应的部分（对应树结构中的左叉与右叉）。

如下是一个名为 test_split() 的函数，它能实现上述功能：

# Split a dataset based on an attribute and an attribute valuedef test_split(index, value, dataset):left, right = list(), list()for row in dataset:if row[index] < value:left.append(row)else:right.append(row)return left, right

代码还是很简单的。

注意，在代码中，属性值大于或等于阈值的数据点被分类到了右组中。

2.2.2 评价所有分割点

在基尼函数 gini_index() 和分类函数 test_split() 的帮助下，我们可以开始进行评估分割点的流程。

对给定的数据集，对每一个属性，我们都要检查所有的可能的阈值使之作为候选分割点。然后，我们将根据这些分割点的成本（cost）对其进行评估，最终挑选出最优的分割点。

当最优分割点被找到之后，我们就能用它作为我们决策树中的一个节点。

而这也就是所谓的穷举型贪心算法。

在该例中，我们将使用一个词典来代表决策树中的一个节点，它能够按照变量名储存数据。当选择了最优分割点并使用它作为树的新节点时，我们存下对应属性的下标、对应分割值及根据分割值分割后的两部分数据。

分割后地每一组数据都是一个更小规模地数据集（可以继续进行分割操作），它实际上就是原始数据集中地数据按照分割点被分到了左叉或右叉的数据集。你可以想象我们可以进一步将每一组数据再分割，不断循环直到建构出整个决策树。

如下是一个名为 get_split() 的函数，它能实现上述的步骤。你会发现，它遍历了每一个属性（除了类别值）以及属性对应的每一个值，在每次迭代中它都会分割数据并评估该分割点。

当所有的检查完成后，最优的分割点将被记录并返回。

# Select the best split point for a datasetdef get_split(dataset):class_values = list(set(row[-1] for row in dataset))b_index, b_value, b_score, b_groups = 999, 999, 999, Nonefor index in range(len(dataset[0])-1):for row in dataset:groups = test_split(index, row[index], dataset)gini = gini_index(groups, class_values)if gini < b_score:b_index, b_value, b_score, b_groups = index, row[index], gini, groupsreturn {'index':b_index, 'value':b_value, 'groups':b_groups}

我们能在一个小型合成的数据集上来测试这个函数以及整个数据集分割的过程。

X1 X2 Y2.771244718 1.784783929 01.728571309 1.169761413 03.678319846 2.81281357 03.961043357 2.61995032 02.999208922 2.209014212 07.497545867 3.162953546 19.00220326 3.339047188 17.444542326 0.476683375 110.12493903 3.234550982 16.642287351 3.319983761 1

同时，我们可以使用不同颜色标记不同的类，将该数据集绘制出来。由图可知，我们可以从 X1 轴（即图中的 X 轴）上挑出一个值来分割该数据集。

范例所有的代码整合如下：

# Split a dataset based on an attribute and an attribute valuedef test_split(index, value, dataset):left, right = list(), list()for row in dataset:if row[index] < value:left.append(row)else:right.append(row)return left, right# Calculate the Gini index for a split datasetdef gini_index(groups, class_values):gini = 0.0for class_value in class_values:for group in groups:size = len(group)if size == 0:continueproportion = [row[-1] for row in group].count(class_value) / float(size)gini += (proportion * (1.0 - proportion))return gini# Select the best split point for a datasetdef get_split(dataset):class_values = list(set(row[-1] for row in dataset))b_index, b_value, b_score, b_groups = 999, 999, 999, Nonefor index in range(len(dataset[0])-1):for row in dataset:groups = test_split(index, row[index], dataset)gini = gini_index(groups, class_values)print('X%d < %.3f Gini=%.3f' % ((index+1), row[index], gini))if gini < b_score:b_index, b_value, b_score, b_groups = index, row[index], gini, groupsreturn {'index':b_index, 'value':b_value, 'groups':b_groups}dataset = [[2.771244718,1.784783929,0],[1.728571309,1.169761413,0],[3.678319846,2.81281357,0],[3.961043357,2.61995032,0],[2.999208922,2.209014212,0],[7.497545867,3.162953546,1],[9.00220326,3.339047188,1],[7.444542326,0.476683375,1],[10.12493903,3.234550982,1],[6.642287351,3.319983761,1]]split = get_split(dataset)print('Split: [X%d < %.3f]' % ((split['index']+1), split['value']))

优化后的 get_split() 函数能够输出每个分割点及其对应的基尼系数。

运行如上的代码后，它将 print 所有的基尼系数及其选中的最优分割点。在此范例中，它选中了 X1<6.642 作为最终完美分割点（它对应的基尼系数为 0）。

X1< 2.771 Gini=0.494X1 < 1.729 Gini=0.500X1 < 3.678 Gini=0.408X1 < 3.961 Gini=0.278X1 < 2.999 Gini=0.469X1 < 7.498 Gini=0.408X1 < 9.002 Gini=0.469X1 < 7.445 Gini=0.278X1 < 10.125 Gini=0.494X1 < 6.642 Gini=0.000X2 < 1.785 Gini=1.000X2 < 1.170 Gini=0.494X2 < 2.813 Gini=0.640X2 < 2.620 Gini=0.819X2 < 2.209 Gini=0.934X2 < 3.163 Gini=0.278X2 < 3.339 Gini=0.494X2 < 0.477 Gini=0.500X2 < 3.235 Gini=0.408X2 < 3.320 Gini=0.469Split: [X1 < 6.642]

既然我们现在已经能够找出数据集中最优的分割点，那我们现在就来看看我们能如何应用它来建立一个决策树。

2.3 生成树模型

创建树的根节点（root node）是比较方便的，可以调用 get_split() 函数并传入整个数据集即可达到此目的。但向树中增加更多的节点�...

感知器算法是最简单的人工神经网络形式之一。感知器是一个单神经元的模型，可以用于两个类别的分类问题，也能为以后开发更大的神经网络奠定基础。在本教程中，你将了解到如何利用 Python 从头开始实现感知器算法。

在完成本教程后，你将学会：

如何训练感知器的网络权重

如何利用感知器做出预测

如何对于现实世界的分类问题实现感知器算法

让我们开始吧。

概述

本节简要介绍了感知器算法和 Sonar 数据集，我们将会在后面应用。

感知器算法

感知器的灵感来自于被称为神经元的单个神经细胞的信息处理过程。

神经元通过其树突接受输入信号，并将电信号向下传递到细胞体内。

通过类似的方式，感知器从训练数据的样本中接受输入信号，训练数据被加权并在称为激活（activation）的线性方程中进行组合。

然后，使用诸如阶跃传递函数（step transfer function）的传递函数将激活变换为输出值或预测。

以这种方式，感知器是用于具有两个类（0 和 1）的问题的分类算法，其中可以使用线性方程来分离这两个类。

它与以类似方式进行预测的线性回归和 logistic 回归密切相关（例如输入的加权和）。

感知器算法的权重必须使用随机梯度下降算法从训练数据中估计。

随机梯度下降

梯度下降是通过跟随成本函数（cost function）的梯度来最小化函数的过程。

这涉及了解成本的形式以及导数，使得从给定的点你可以知道梯度并且可以在该方向上移动，比如下坡到最小值。

在机器学习中，我们可以使用一种技术来评估和更新称为随机梯度下降的每次迭代的权重，以最小化我们的训练数据模型的误差。

这种优化算法的工作方式是每次向模型显示每个训练实例。模型对训练实例进行预测，计算误差并更新模型以便减少下一预测的误差。

该过程可以用于在模型中找到能使训练数据上模型误差最小的权重集合。

对于感知器算法，每次迭代，权重（w）使用以下等式更新：

其中w是正在被优化的权重，learning_rate是必须配置的学习速率（例如 0.01），（expected - predicted）是在归因于权重的训练数据上的模型的预测误差，x是输入值。

Sonar 数据集

我们将在本教程中使用的数据集是 Sonar 数据集。

这是一个描述了声呐啾啾叫声并返回不同服务的试探的数据集。60 个输入变量是在不同角度的返回强度。这是一个二元分类问题，需要一个模型来区分金属圆柱体和岩石。

它是一个很好理解的数据集。所有的变量是连续的，通常在 0 到 1 的范围内。因此，我们不必对输入数据进行归一化，这通常是使用感知器算法的一个好地方。输出变量是字符串「M」（表示矿 mine）和「R」（表示岩石 rock），我们需要将其转换为整数 1 和 0。

通过在数据集（M 或 Mines）中预测具有最多观测值的类，零规则算法（Zero Rule Algorithm）可以实现 53％的精度。

你可以在 UCI Machine Learning repository：

https://archive.ics.uci.edu/ml/datasets/Connectionist+Bench+(Sonar,+Mines+vs.+Rocks)）中了解有关此数据集的更多信息。你也可以免费下载数据集，并将其放在工作目录中，文件名为 sonar.all-data.csv。

教程

这个教程分为三个部分：

1.作出预测

2.训练网络权重

3.将 Sonar 数据集建模

这些步骤将带给你实现和应用感知器算法到你自己的分类预测建模问题的基础。

1. 作预测

第一步是开发一个可以进行预测的函数。

这将会需要在随机梯度下降中的候选权重值的评估以及在模型被最终确定之后，我们希望开始对测试数据或新数据进行预测。

下面是一个名为 predict() 的函数，用于预测给定一组权重的行的输出值。

第一个权重始终是偏差，因为它是独立的，不负责特定的输入值。

我们可以设计一个小数据集来测试我们的预测函数。

我们也可以使用之前准备好的权重来为这个数据集做预测。

将所有这些集中起来，我们就可以测试我们的 predict() 函数了，如下：

该函数有两个输入值 X1、X2 和三个权重参数 bias、w1 及 w2。该问题的激活函数有如下的形式：

或者，我们能够手动地选择权重值：

运行这个函数，我们将会得到与期望输出值 (**y**) 相符合的预测值。

现在，我们已经准备好使用随机梯度下降法（SGD）来最优化我们的权重值。

2. 训练神经权重

我们可以使用 SGD，来估计出对于训练集的权重值。

SGD 有两个参数：

学习率（Learning Rate）：用来限制每次更新中权重项修正值的大小。

迭代次数（Epochs）：在训练集上训练同时更新权重项的次数。

这两个参数，和训练集一起，都将会是预测函数的输入参数。

在这个函数中，我们需要运行三个循环：

1. 对于每次迭代进行循环；

2. 对于一次迭代中，训练集的每一行进行循环；

3. 对于每一行中，每一个值进行循环。

如你所见，我们在每一次迭代中，对训练集每一行中每一个权值都进行更新。

我们基于现有情况模型预测的「误差」，来对权重值进行更新。误差，是由候选权值计算出来的预测值与（数据集中的）期望值的差。

对每一个输入属性，都有一个权重值，并且这些权_重值都连续更新_。如：

偏差项以一种相似的方式更新，不过因为它本身就不与特定的输入值有关，因而在式子中没有输入值的项。

现在，我们把所有的内容组合到一起。如下所示，在 train_weights() 函数中，它使用 SGD 方法，计算对于给定训练集的权重值。

如你所见，我们也在每次迭代中，记录下了平方误差之和（这始终是一个正值）。因而我们能在外循环的每次迭代中，print 一些有用的信息。

我们也可以在我们上面创建的小规模数据集上，对该函数进行测试。

我们将使用 0.1 的学习率和 5 次迭代，也就是把参数在训练集上更新五次，来训练这个模型。

运行这个案例，它将会在每一次迭代结束后，显示出该次迭代后的平方误差和，并在完成所有迭代后，显示最后的权重集。

你可以看到，这个算法很快学会了「解决」这个问题。

现在我们来试试看，如何在一个实际的数据集上应用这个算法。

3. 对声纳数据集进行建模

在这一节中，我们将使用 SGD 方法，对一个声纳数据集，训练一个感知器模型。

在该例子中，我们假定，在当前的工作目录下，有一名为sonar.all-data.csv 的文件，存储着该数据集。

首先该数据集被载入。数据集中字符串格式的数据被转换为数值型，同时输出值从字符串被转换了 0 或 1 的两个整数值。

通过 load_csv(), str_column_to_float()及str_column_to_int() 三个函数，我们实现了对数据集的读取及预处理。

我们使用「k 倍交叉验证法」（k-fold cross validation）来对学习后的模型在未知数据集上的表现进行评估。也就是说，我们需要建立 k 个模型并估计各模型的平均误差。分类准确性将被用于模型的评估工作中。这些工作在 cross_validation_split(), accuracy_metric() 及 evaluate_algorithm() 函数中被完成。

我们将会使用上面设置的 predict() 和 train_weights()函数来训练该模型。同时，我们将会用一个新函数perceptron() 来将它们组合在一起。如下是完整的例子。

在交叉验证中，我们取 k 为 3——也就是对每一块数据，都有 208/3 约 70 个记录，会在每次迭代中被用于计算。我们取 0.1 的学习率及 500 的训练迭代次数，来训练模型。

你可以尝试你自己的参数，并且看看你的结果能否战胜我的分数。运行这个例子，将会显示对 3 倍交叉验证中每一块的分数，以及平均的分类正确率。

我们可以看到，这个正确率约为 73%，高于由仅考虑主要类的零规则算法（Zero Rule Algorithm）得到的 50% 的正确率基准值。

拓展

这一节列举了关于该入门指导的拓展内容，你可以考虑深入探究其中的一些内容。

调试样例参数。尝试着去调整包括学习率、迭代次数乃至于数据预处理的方法，以使模型在该数据集上，得到更高的分数。

批量化进行随机梯度下降。修改随机梯度下降的算法，使得我们能记录下每一次迭代的更新值，并且在迭代结束的时候再基于记录的更新值来更新权重值。

额外的分类问题。将文中提到的技巧，应用于 UCI 机器学习数据集中其他数据。

回顾

在该教程中，你学习了如何从零开始，用 Python 实现，基于随机梯度下降的感知器算法。

你学会了：

如何对一个二元分类问题进行预测。

如何使用随机梯度下降，对一系列的权重值进行最优化。

如何将这个技巧，应用到一个实际的分类预测模型。

关注小编 私信 python资料 获取学习资料

一、SMO算法

序列最小化优化算法（Sequential minimal optimization,SMO）是一种用于解决支持向量机训练过程中所产生优化问题的算法。SMO由微软研究院的约翰·普莱特在1998发明，用于训练SVM。在SMO之前，SVM的训练必须使用复杂的方法，并需要昂贵的第三方二次规划工具。SMO算法将大优化问题分解为了多个小优化问题来求解的，这些小优化问题通常比较容易求解，并且对它们进行顺序求解的结果与将它们作为整体求解的结果是完全一致的。在结果完全相同的同时，SMO算法的求解时间要短很多。

SMO算法的目标是求解参数α和b，然后通过参数α来求解权重ω，从而获取到分割超平面的方程。

SMO算法的工作原理：每次循环中选择两个α进行优化处理。一旦找到一对合适的α，就增大其中一个α减少另一个α来保证，约束条件的成立。“合适”需要满足两个条件，第一个条件就是这两个α必须要在间隔边界之外，第二个条件是指两个α还没有进行过区间化处理或者不在边界上。

二、SMO算法的参数更新过程

在上一篇文章的最后，我们给出了这个公式。我们假设更新的参数是α1和α2，其它的α保持不变，根据约束条件我们可以获得几个下面的等式

所以我们将ω转换成为α1和α2的函数

根据约束条件可得

将α1代入到上式，可得

根据分割超平面的方程和已知参数条件，可得v1-v2

截距参数b的更新过程

三、实现一个简版的SMO算法

下面，我们使用python来实现一个简版的SMO算法。

1.《机器学习实战》

2.《机器学习》

3.https://zhuanlan.zhihu/p/29212107

有那么一种Python人工智能算法可以良好的控制你传输的数据，避免网络堵塞，合理的分配你的流量大小以及速度。他可以控制数据发送到互联网上的数目，可以发送突发数据的。是不是很神奇，然而你知道它是什么算法？可以先透漏给你们哟，这个神器的Python人工智能算法只需15行代码！

代码：

import timeclass TokenBucket(object):# rate是令牌发放速度，capacity是桶的大小def __init__(self, rate, capacity):self._rate = rateself._capacity = capacityself._current_amount = 0self._last_consume_time = int(time.time()) # token_amount是发送数据需要的令牌数def consume(self, token_amount):increment = (int(time.time()) - self._last_consume_time) * self._rate # 计算从上次发送到这次发送，新发放的令牌数量self._current_amount = min(increment + self._current_amount, self._capacity) # 令牌数量不能超过桶的容量if token_amount > self._current_amount: # 如果没有足够的令牌，则不能发送数据return Falseself._last_consume_time = int(time.time())self._current_amount -= token_amount return True

本文是一些机器人算法（特别是自动导航算法）的Python代码合集。

其主要特点有以下三点：选择了在实践中广泛应用的算法；依赖最少；容易阅读，容易理解每个算法的基本思想。希望阅读本文后能对你有所帮助。

前排友情提示，文章较长，建议收藏后再看。

目录

环境需求怎样使用本地化扩展卡尔曼滤波本地化无损卡尔曼滤波本地化粒子滤波本地化直方图滤波本地化映射高斯网格映射光线投射网格映射k均值物体聚类圆形拟合物体形状识别SLAM迭代最近点匹配EKF SLAMFastSLAM 1.0FastSLAM 2.0基于图的SLAM路径规划动态窗口方式基于网格的搜索迪杰斯特拉算法A*算法势场算法模型预测路径生成路径优化示例查找表生成示例状态晶格规划均匀极性采样（Uniform polar sampling）偏差极性采样（Biased polar sampling）路线采样（Lane sampling）随机路径图（PRM）规划Voronoi路径图规划快速搜索随机树（RRT）基本RRTRRT*基于Dubins路径的RRT基于Dubins路径的RRT*基于reeds-shepp路径的RRT*Informed RRT*批量Informed RRT*三次样条规划B样条规划贝济埃路径规划五次多项式规划Dubins路径规划Reeds Shepp路径规划基于LQR的路径规划Frenet Frame中的最优路径路径跟踪纯追迹跟踪史坦利控制后轮反馈控制线性二次regulator（LQR）转向控制线性二次regulator（LQR）转向和速度控制项目支持

环境需求

Python 3.6.xnumpyscipymatplotlibpandascvxpy 0.4.x

怎样使用

安装必要的库；克隆本代码仓库；执行每个目录下的python脚本；如果你喜欢，则收藏本代码库：）

本地化

扩展卡尔曼滤波本地化

该算法利用扩展卡尔曼滤波器（Extended Kalman Filter, EKF）实现传感器混合本地化。

蓝线为真实路径，黑线为导航推测路径（dead reckoning trajectory），绿点为位置观测（如GPS），红线为EKF估算的路径。

红色椭圆为EKF估算的协方差。

相关阅读：概率机器人学http://probabilistic-robotics.org/

无损卡尔曼滤波本地化

该算法利用无损卡尔曼滤波器（Unscented Kalman Filter, UKF）实现传感器混合本地化。

线和点的含义与EKF模拟的例子相同。

相关阅读：利用无差别训练过的无损卡尔曼滤波进行机器人移动本地化https://researchgate/publication/267963417_Discriminatively_Trained_Unscented_Kalman_Filter_for_Mobile_Robot_Localization

粒子滤波本地化

该算法利用粒子滤波器（Particle Filter, PF）实现传感器混合本地化。

蓝线为真实路径，黑线为导航推测路径（dead reckoning trajectory），绿点为位置观测（如GPS），红线为PF估算的路径。

该算法假设机器人能够测量与地标（RFID）之间的距离。

PF本地化会用到该测量结果。

相关阅读：概率机器人学http://probabilistic-robotics.org/

直方图滤波本地化

该算法是利用直方图滤波器（Histogram filter）实现二维本地化的例子。

红十字是实际位置，黑点是RFID的位置。

蓝色格子是直方图滤波器的概率位置。

在该模拟中，x，y是未知数，yaw已知。

滤波器整合了速度输入和从RFID获得距离观测数据进行本地化。

不需要初始位置。

相关阅读：概率机器人学http://probabilistic-robotics.org/

映射

高斯网格映射

本算法是二维高斯网格映射（Gaussian grid mapping）的例子。

光线投射网格映射

本算法是二维光线投射网格映射（Ray casting grid map）的例子。

k均值物体聚类

本算法是使用k均值算法进行二维物体聚类的例子。

圆形拟合物体形状识别

本算法是使用圆形拟合进行物体形状识别的例子。

蓝圈是实际的物体形状。

红叉是通过距离传感器观测到的点。

红圈是使用圆形拟合估计的物体形状。

SLAM

同时本地化和映射（Simultaneous Localization and Mapping，SLAM）的例子。

迭代最近点匹配

本算法是使用单值解构进行二维迭代最近点（Iterative Closest Point，ICP）匹配的例子。

它能计算从一些点到另一些点的旋转矩阵和平移矩阵。

相关阅读：机器人运动介绍：迭代最近点算法https://cs.gmu.edu/~kosecka/cs685/cs685-icp.pdf

EKF SLAM

这是基于扩展卡尔曼滤波的SLAM示例。

蓝线是真实路径，黑线是导航推测路径，红线是EKF SLAM估计的路径。

绿叉是估计的地标。

相关阅读：概率机器人学http://probabilistic-robotics.org/

FastSLAM 1.0

这是用FastSLAM 1.0进行基于特征的SLAM的示例。

蓝线是实际路径，黑线是导航推测，红线是FastSLAM的推测路径。

红点是FastSLAM中的粒子。

黑点是地标，蓝叉是FastLSAM估算的地标位置。

相关阅读：概率机器人学http://probabilistic-robotics.org/

FastSLAM 2.0

这是用FastSLAM 2.0进行基于特征的SLAM的示例。

动画的含义与FastSLAM 1.0的情况相同。

相关阅读：概率机器人学http://probabilistic-robotics.org/Tim Bailey的SLAM模拟http://www-personal.acfr.usyd.edu.au/tbailey/software/slam_simulations.htm

基于图的SLAM

这是基于图的SLAM的示例。

蓝线是实际路径。

黑线是导航推测路径。

红线是基于图的SLAM估算的路径。

黑星是地标，用于生成图的边。

相关阅读：基于图的SLAM入门http://www2.informatik.uni-freiburg.de/~stachnis/pdf/grisetti10titsmag.pdf

路径规划

动态窗口方式

这是使用动态窗口方式（Dynamic Window Approach）进行二维导航的示例代码。

相关阅读：用动态窗口方式避免碰撞https://ri.cmu.edu/pub_files/pub1/fox_dieter_1997_1/fox_dieter_1997_1.pdf

基于网格的搜索

迪杰斯特拉算法

这是利用迪杰斯特拉（Dijkstra）算法实现的基于二维网格的最短路径规划。

动画中青色点为搜索过的节点。

A*算法

下面是使用A星算法进行基于二维网格的最短路径规划。

动画中青色点为搜索过的节点。

启发算法为二维欧几里得距离。

势场算法

下面是使用势场算法进行基于二维网格的路径规划。

动画中蓝色的热区图显示了每个格子的势能。

相关阅读：机器人运动规划：势能函数https://cs.cmu.edu/~motionplanning/lecture/Chap4-Potential-Field_howie.pdf

模型预测路径生成

下面是模型预测路径生成的路径优化示例。

算法用于状态晶格规划（state lattice planning）。

路径优化示例

查找表生成示例

相关阅读：用于带轮子的机器人的最优不平整地形路径生成http://journals.sagepub/doi/pdf/10.1177/0278364906075328

状态晶格规划

这个脚本使用了状态晶格规划（state lattice planning）实现路径规划。

这段代码通过模型预测路径生成来解决边界问题。

相关阅读：用于带轮子的机器人的最优不平整地形路径生成http://journals.sagepub/doi/pdf/10.1177/0278364906075328用于复杂环境下的高性能运动机器人导航的可行运动的状态空间采样http://frc.ri.cmu.edu/~alonzo/pubs/papers/JFR_08_SS_Sampling.pdf

均匀极性采样（Uniform polar sampling）

偏差极性采样（Biased polar sampling）

路线采样（Lane sampling）

随机路径图（PRM）规划

这个随机路径图（Probabilistic Road-Map，PRM）规划算法在图搜索上采用了迪杰斯特拉方法。

动画中的蓝点为采样点。

青色叉为迪杰斯特拉方法搜索过的点。

红线为PRM的最终路径。

相关阅读：随机路径图https://en.wikipedia.org/wiki/Probabilistic_roadmap

Voronoi路径图规划

这个Voronoi路径图（Probabilistic Road-Map，PRM）规划算法在图搜索上采用了迪杰斯特拉方法。

动画中的蓝点为Voronoi点。

青色叉为迪杰斯特拉方法搜索过的点。

红线为Voronoi路径图的最终路径。

相关阅读：机器人运动规划https://cs.cmu.edu/~motionplanning/lecture/Chap5-RoadMap-Methods_howie.pdf

快速搜索随机树（RRT）

基本RRT

这是个使用快速搜索随机树（Rapidly-Exploring Random Trees，RRT）的简单路径规划代码。

黑色圆为障碍物，绿线为搜索树，红叉为开始位置和目标位置。

RRT*

这是使用RRT*的路径规划代码。

黑色圆为障碍物，绿线为搜索树，红叉为开始位置和目标位置。

相关阅读：最优运动规划的基于增量采样的算法https://arxiv.org/abs/1005.0416最优运动规划的基于采样的算法http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.5503&rep=rep1&type=pdf

基于Dubins路径的RRT

为汽车形机器人提供的使用RRT和dubins路径规划的路径规划算法。

基于Dubins路径的RRT*

为汽车形机器人提供的使用RRT*和dubins路径规划的路径规划算法。

基于reeds-shepp路径的RRT*

为汽车形机器人提供的使用RRT*和reeds shepp路径规划的路径规划算法。

Informed RRT*

这是使用Informed RRT*的路径规划代码。

青色椭圆为Informed RRT*的启发采样域。

相关阅读：Informed RRT*：通过对可接受的椭球启发的直接采样实现最优的基于采样的路径规划https://arxiv.org/pdf/1404.2334.pdf

批量Informed RRT*

这是使用批量Informed RRT*的路径规划代码。

相关阅读：批量Informed树（BIT*）：通过对隐含随机几何图形进行启发式搜索实现基于采样的最优规划https://arxiv.org/abs/1405.5848

闭合回路RRT*

使用闭合回路RRT*（Closed loop RRT*）实现的基于车辆模型的路径规划。

这段代码里，转向控制用的是纯追迹算法（pure-pursuit algorithm）。

速度控制采用了PID。

相关阅读：使用闭合回路预测在复杂环境内实现运动规划http://acl.mit.edu/papers/KuwataGNC08.pdf）应用于自动城市驾驶的实时运动规划http://acl.mit.edu/papers/KuwataTCST09.pdf[1601.06326]采用闭合回路预测实现最优运动规划的基于采样的算法https://arxiv.org/abs/1601.06326

LQR-RRT*

这是个使用LQR-RRT*的路径规划模拟。

LQR局部规划采用了双重积分运动模型。

相关阅读：LQR-RRT*：使用自动推导扩展启发实现最优基于采样的运动规划http://lis.csail.mit.edu/pubs/perez-icra12.pdfMahanFathi/LQR-RRTstar：LQR-RRT*方法用于单摆相位中的随机运动规划https://github/MahanFathi/LQR-RRTstar

三次样条规划

这是段三次路径规划的示例代码。

这段代码根据x-y的路点，利用三次样条生成一段曲率连续的路径。

每个点的指向角度也可以用解析的方式计算。

B样条规划

这是段使用B样条曲线进行规划的例子。

输入路点，它会利用B样条生成光滑的路径。

第一个和最后一个路点位于最后的路径上。

相关阅读：B样条https://en.wikipedia.org/wiki/B-spline

Eta^3样条路径规划

这是使用Eta ^ 3样条曲线的路径规划。

相关阅读：\eta^3-Splines for the Smooth Path Generation of Wheeled Mobile Robotshttps://ieeexplore.ieee.org/document/4339545/

贝济埃路径规划

贝济埃路径规划的示例代码。

根据四个控制点生成贝济埃路径。

改变起点和终点的偏移距离，可以生成不同的贝济埃路径：

相关阅读：根据贝济埃曲线为自动驾驶汽车生成曲率连续的路径http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.294.6438&rep=rep1&type=pdf

五次多项式规划

利用五次多项式进行路径规划。

它能根据五次多项式计算二维路径、速度和加速度。

相关阅读：用于Agv In定位的局部路径规划和运动控制http://ieeexplore.ieee.org/document/637936/

Dubins路径规划

Dubins路径规划的示例代码。

相关阅读：Dubins路径https://en.wikipedia.org/wiki/Dubins_path

Reeds Shepp路径规划

Reeds Shepp路径规划的示例代码。

相关阅读：15.3.2 Reeds-Shepp曲线http://planning.cs.uiuc.edu/node822.html用于能前进和后退的汽车的最优路径https://pdfs.semanticscholar.org/932e/c495b1d0018fd59dee12a0bf74434fac7af4.pdfghliu/pyReedsShepp：实现Reeds Shepp曲线https://github/ghliu/pyReedsShepp

基于LQR的路径规划

为双重积分模型使用基于LQR的路径规划的示例代码。

Frenet Frame中的最优路径

这段代码在Frenet Frame中生成最优路径。

青色线为目标路径，黑色叉为障碍物。

红色线为预测的路径。

相关阅读：Frenet Frame中的动态接到场景中的最优路径生成https://researchgate/profile/Moritz_Werling/publication/224156269_Optimal_Trajectory_Generation_for_Dynamic_Street_Scenarios_in_a_Frenet_Frame/links/54f749df0cf210398e9277af.pdfFrenet Frame中的动态接到场景中的最优路径生成https://youtube/watch?v=Cj6tAQe7UCY

路径跟踪

姿势控制跟踪

这是姿势控制跟踪的模拟。

相关阅读：Robotics, Vision and Control - Fundamental Algorithms In MATLAB Second, Completely Revised, Extended And Updated Edition | Peter Corke | Springerhttps://springer/us/book/9783319544120

纯追迹跟踪

使用纯追迹（pure pursuit）转向控制和PID速度控制的路径跟踪模拟。

红线为目标路线，绿叉为纯追迹控制的目标点，蓝线为跟踪路线。

相关阅读：城市中的自动驾驶汽车的运动规划和控制技术的调查https://arxiv.org/abs/1604.07446

史坦利控制

使用史坦利（Stanley）转向控制和PID速度控制的路径跟踪模拟。

相关阅读：史坦利：赢得DARPA大奖赛的机器人http://robots.stanford.edu/papers/thrun.stanley05.pdf用于自动驾驶机动车路径跟踪的自动转向方法https://ri.cmu.edu/pub_files/2009/2/Automatic_Steering_Methods_for_Autonomous_Automobile_Path_Tracking.pdf

后轮反馈控制

利用后轮反...

python中有现成的文本相似度算法levenstein距离（编辑距离）的算法包：python- Levenshtein，可以直接使用：

python-Levenshtein算法库

distance函数计算编辑距离，规则是：添加、删除和替换一个字符距离都+1；

ratio函数计算Levenstein比，其中替换一个字符距离变为2。这个也是我们需要实现的。

但是因为一些原因，有个外部程序调用第三方python包有点问题，所以需要用python写一个简单的Levenstein距离实现算法。本着拿来主义在网上找了找，好多程序执行有问题，所以自己重写了一下：

简洁版Levenshtein.ratio算法

根据百度百科“编辑距离”了解一下具体算法（不要嘲笑），维基百科“Levenshtein distance”也一样：

假设比较“coffee”和‘cafe’的相似度：

① 初始化一个5*7矩阵：

图片来自百度百科

② 除了第一行和第一列，分别计算剩下的值，例如Dij取3个值得最小值：正上方的值distance_matrix(i-1)j+1，左方相邻值distance_matrixi(j-1)+1，四方格对角值distance_matrix (i-1)(j-1)+2（如果是只计算编辑距离的话，这里是+1，因为我们需要Levenshtein比，所以这里是+2）；

③ 最终结果为矩阵右下角的值，结果为4。也就是cafe中a替换为o，插入f和e，变为coffee；Levenshtein比为4/（4+6）=0.6。

本算法对于字符串相似度比较比较适合，而对于文章的相似度比较则较多使用向量空间模型VSM，例如TD-IDF算法。先进行分词再通过词频向量，利用向量余弦值计算相似度。