机器学习的十大经典算法，面试必问
来源：机器之心现在，机器学习有很多算法。如此多的算法，可能对于初学者来说，是相当不堪重负的。今天，我们将简要介绍10种最流行的机器学习算法，这样你就可以适应这个激动人心的机器学习世界了！
01线性回归
线性回归（LinearRegression）可能是最流行的机器学习算法。线性回归就是要找一条直线，并且让这条直线尽可能地拟合散点图中的数据点。它试图通过将直线方程与该数据拟合来表示自变量（x值）和数值结果（y值）。然后就可以用这条线来预测未来的值！
这种算法最常用的技术是最小二乘法（Leastofsquares）。这个方法计算出最佳拟合线，以使得与直线上每个数据点的垂直距离最小。总距离是所有数据点的垂直距离（绿线）的平方和。其思想是通过最小化这个平方误差或距离来拟合模型。
例如，简单线性回归，它有一个自变量（x轴）和一个因变量（y轴）。
02逻辑回归
逻辑回归（Logisticregression）与线性回归类似，但它是用于输出为二进制的情况（即，当结果只能有两个可能的值）。对最终输出的预测是一个非线性的S型函数，称为logisticfunction,g()。
这个逻辑函数将中间结果值映射到结果变量Y，其值范围从0到1。然后，这些值可以解释为Y出现的概率。S型逻辑函数的性质使得逻辑回归更适合用于分类任务。
逻辑回归曲线图，显示了通过考试的概率与学习时间的关系。
03决策树
决策树（DecisionTrees）可用于回归和分类任务。
在这一算法中，训练模型通过学习树表示（Treerepresentation）的决策规则来学习预测目标变量的值。树是由具有相应属性的节点组成的。
在每个节点上，我们根据可用的特征询问有关数据的问题。左右分支代表可能的答案。最终节点（即叶节点）对应于一个预测值。
每个特征的重要性是通过自顶向下方法确定的。节点越高，其属性就越重要。
决定是否在餐厅等候的决策树示例。
04朴素贝叶斯
朴素贝叶斯（NaiveBayes）是基于贝叶斯定理。它测量每个类的概率，每个类的条件概率给出x的值。这个算法用于分类问题，得到一个二进制“是/非”的结果。看看下面的方程式。
朴素贝叶斯分类器是一种流行的统计技术，可用于过滤垃圾邮件！
05支持向量机（SVM）
支持向量机（SupportVectorMachine，SVM）是一种用于分类问题的监督算法。支持向量机试图在数据点之间绘制两条线，它们之间的边距最大。为此，我们将数据项绘制为n维空间中的点，其中，n是输入特征的数量。在此基础上，支持向量机找到一个最优边界，称为超平面（Hyperplane），它通过类标签将可能的输出进行最佳分离。
超平面与最近的类点之间的距离称为边距。最优超平面具有最大的边界，可以对点进行分类，从而使最近的数据点与这两个类之间的距离最大化。
例如，H1没有将这两个类分开。但H2有，不过只有很小的边距。而H3以最大的边距将它们分开了。
06K-最近邻算法（KNN）
K-最近邻算法（K-NearestNeighbors，KNN）非常简单。KNN通过在整个训练集中搜索K个最相似的实例，即K个邻居，并为所有这些K个实例分配一个公共输出变量，来对对象进行分类。
K的选择很关键：较小的值可能会得到大量的噪声和不准确的结果，而较大的值是不可行的。它最常用于分类，但也适用于回归问题。
用于评估实例之间相似性的距离可以是欧几里得距离（Euclideandistance）、曼哈顿距离（Manhattandistance）或明氏距离（Minkowskidistance）。欧几里得距离是两点之间的普通直线距离。它实际上是点坐标之差平方和的平方根。
▲KNN分类示例
07K-均值
K-均值（K-means）是通过对数据集进行分类来聚类的。例如，这个算法可用于根据购买历史将用户分组。它在数据集中找到K个聚类。K-均值用于无监督学习，因此，我们只需使用训练数据X，以及我们想要识别的聚类数量K。
该算法根据每个数据点的特征，将每个数据点迭代地分配给K个组中的一个组。它为每个K-聚类（称为质心）选择K个点。基于相似度，将新的数据点添加到具有最近质心的聚类中。这个过程一直持续到质心停止变化为止。
08随机森林
随机森林（RandomForest）是一种非常流行的集成机器学习算法。这个算法的基本思想是，许多人的意见要比个人的意见更准确。在随机森林中，我们使用决策树集成（参见决策树）。
为了对新对象进行分类，我们从每个决策树中进行投票，并结合结果，然后根据多数投票做出最终决定。
在训练过程中，每个决策树都是基于训练集的引导样本来构建的。
在分类过程中，输入实例的决定是根据多数投票做出的。
09降维
由于我们今天能够捕获的数据量之大，机器学习问题变得更加复杂。这就意味着训练极其缓慢，而且很难找到一个好的解决方案。这一问题，通常被称为“维数灾难”（Curseofdimensionality）。
降维（Dimensionalityreduction）试图在不丢失最重要信息的情况下，通过将特定的特征组合成更高层次的特征来解决这个问题。主成分分析（PrincipalComponentAnalysis，PCA）是最流行的降维技术。
主成分分析通过将数据集压缩到低维线或超平面/子空间来降低数据集的维数。这尽可能地保留了原始数据的显著特征。
可以通过将所有数据点近似到一条直线来实现降维的示例。
10人工神经网络（ANN）
人工神经网络（ArtificialNeuralNetworks，ANN）可以处理大型复杂的机器学习任务。神经网络本质上是一组带有权值的边和节点组成的相互连接的层，称为神经元。在输入层和输出层之间，我们可以插入多个隐藏层。人工神经网络使用了两个隐藏层。除此之外，还需要处理深度学习。
人工神经网络的工作原理与大脑的结构类似。一组神经元被赋予一个随机权重，以确定神经元如何处理输入数据。通过对输入数据训练神经网络来学习输入和输出之间的关系。在训练阶段，系统可以访问正确的答案。
如果网络不能准确识别输入，系统就会调整权重。经过充分的训练后，它将始终如一地识别出正确的模式。
每个圆形节点表示一个人工神经元，箭头表示从一个人工神经元的输出到另一个人工神经元的输入的连接。
接下来是什么？现在，你已经了解了最流行的机器学习算法的基础介绍。你已经准备好学习更为复杂的概念，甚至可以通过深入的动手实践来实现它们。如果你想了解如何实现这些算法，可以参考Educative出品的GrokkingDataScience课程，该课程将这些激动人心的理论应用于清晰、真实的应用程序。
祝你学习愉快！
作者介绍：
FahimulHaq，曾在Facebook、Microsoft工作。Educative.io联合创始人。Educative旨在帮助学生使用交互式课程来学习编程知识。
原文链接：
https://towardsdatascience.com/the-top-10-ml-algorithms-for-data-science-in-5-minutes-4ffbed9c8672
NO.1
往期推荐
Historicalarticles
20个Pandas数据实战案例，干货多多
10张图带你看清俄乌冲突的始末
年轻人为什么会猝死？这篇Python数据分析报告不可错过！
厉害了，用Python绘制动态可视化图表，并保存成gif格式
分享、收藏、点赞、在看安排一下？
程序员必须要掌握的十大经典算法
算法一：快速排序算法快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn)算法更快，因为它的内部循环（innerloop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divideandconquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
算法步骤：
1从数列中挑出一个元素，称为“基准”（pivot），
2重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
算法二：堆排序算法堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的平均时间复杂度为Ο(nlogn)。
算法步骤：
创建一个堆H[0..n-1]
把堆首（最大值）和堆尾互换
3.把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4.重复步骤2，直到堆的尺寸为1
算法三：归并排序归并排序（Mergesort，中国台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（DivideandConquer）的一个非常典型的应用。
算法步骤：
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针达到序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾
算法四：二分查找算法二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn)。
算法五：BFPRT(线性查找算法)BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂度，五位算法作者做了精妙的处理。
算法步骤：
1.将n个元素每5个一组，分成n/5(上界)组。
2.取出每一组的中位数，任意排序方法，比如插入排序。
3.递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。
4.用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。
5.若i==k，返回x；若ik，在大于x的元素中递归查找第i-k小的元素。
终止条件：n=1时，返回的即是i小元素。
算法六：DFS（深度优先搜索）深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。
深度优先遍历图算法步骤：
1.访问顶点v；
2.依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
3.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
上述描述可能比较抽象，举个实例：
DFS在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。
接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。
算法七：BFS(广度优先搜索)广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。
算法步骤：
1.首先将根节点放入队列中。
2.从队列中取出第一个节点，并检验它是否为目标。
如果找到目标，则结束搜寻并回传结果。
否则将它所有尚未检验过的直接子节点加入队列中。
3.若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
4.重复步骤2。
算法八：Dijkstra算法戴克斯特拉算法（Dijkstra’salgorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
该算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。我们以E表示G中所有边的集合，而边的权重则由权重函数w:E→[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负权重（weight）。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra算法是目前已知的最快的单源最短路径算法。
算法步骤：
1.初始时令S={V0},T={其余顶点}，T中顶点对应的距离值
若存在，d(V0,Vi)为弧上的权值
若不存在，d(V0,Vi)为∞
2.从T中选取一个其距离值为最小的顶点W且不在S中，加入S
3.对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止
算法九：动态规划算法动态规划（Dynamicprogramming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
关于动态规划最经典的问题当属背包问题。
算法步骤：
1.最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2.子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
算法十：朴素贝叶斯分类算法朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况下，如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。
朴素贝叶斯分类器依靠精确的自然概率模型，在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法，换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。
新手在学习编程的时候，算法是不需要刻意学的，先把数据结构里面的基本的数据插入，删除等操作掌握熟练，复杂的算法可以在工作中继续进行修炼。
修改自：http://www.techug.com/10-algorithm-help-programmer-grow-up
几种常用的经典算法（转载）
分治算法一、基本概念
在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
二、基本思想及策略
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题，1
十大经典排序算法（动图演示）
0、算法概述0.1算法分类十种常见排序算法可以分为两大类：
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 0.2算法复杂度0.3相关概念
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
1、冒泡排序（BubbleSort）冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.1算法描述比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到排序完成。1.2动图演示
1.3代码实现functionbubbleSort(arr){varlen=arr.length;for(vari=0;i0;i--){swap(arr,0,i);len--;heapify(arr,0);}returnarr;}8、计数排序（CountingSort）计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
8.1算法描述找出待排序的数组中最大和最小的元素；统计数组中每个值为i的元素出现的次数，存入数组C的第i项；对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。8.2动图演示8.3代码实现functioncountingSort(arr,maxValue){varbucket=newArray(maxValue+1),sortedIndex=0;arrLen=arr.length,bucketLen=maxValue+1;for(vari=0;i