Algorithm

Algorithms20180726.jpg

计算的方法步骤——DeepCreator。

算法导论(原书第2版)

Introduction to Algorithms

目录

出版者的话
专家指导委员会
译者序
前言

第一部分 基础知识
引言
第1章 算法在计算中的作用
1.1 算法
1.2 作为一种技术的算法
第2章 算法入门
2.1 插入排序
2.2 算法分析
2.3 算法设计
2.3.1 分治法
2.3.2 分治法分析
第3章 函数的增长
3.1 渐近记号
3.2 标准记号和常用函数
第4章 传归式
4.1 代换法
4.2 递归树方法
4.3 主方法
4.4 主定理的证明
4.4.1 取正合幂时的证明
4.4.2 上取整函数和下取整函数
第5章 概率分析和随机算法
5.1 雇用问题
5.2 指示器随机变量
5.3 随机算法
5.4 概率分析和指示器随机变量的进一步使用
5.4.1 生日悖论
5.4.2 球与盒子
5.4.3 序列

讲义和视频都可以在MIT的网站上下

大家可以上MIT的OCW站看看
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm
另外还有第3版的笔记和PPT
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-006Spring-2008/CourseHome/index.htm

Ton 10 Algorithms Used by Data Scientists

在“数据为王”的今天,越来越多的人对数据科学产生了兴趣。数据科学家离不开算法的使用,那么,数据科学家最常用的算法,都是哪些呢?

  最近,著名的资料探勘信息网站KDnuggets策划了十大算法调查,这次调查对数据科学家常用的算法进行排名,并发现最“产业”和最“学术”的算法,还对这些算法在过去5年间(2011~2016)的变化,做了一番详细的介绍。

  这次调查结果,是基于844名受访者投票整理出来。

  KDnuggets总结出十大算法及其投票份额如下:


  图1:数据科学家使用的十大算法和方法。

从调查中得知,受访者平均使用8.1个算法,与2011年的一项类似调查相比大幅提高。

  与用于数据分析/数据挖掘的2011年投票算法相比,我们注意到流行的算法仍然是 回归算法、聚类算法、决策树和可视化。相对来说最大的增长是以(pct2016/pct2011-1)测定的以下算法:

  Boosting,从2011年的23.5%至2016年的32.8%,同比增长40%

  文本挖掘,从2011年的从27.7%至2016年的35.9%,同比增长30%

  可视化,从2011年的从38.3%至2016年的48.7%,同比增长27%

  时间序列分析,从2011年的从29.6%至2016年的37.0%,同比增长25%

  异常/偏差检测,从2011年的从16.4%至2016年的19.5%,同比增长19%

  集合方法,从2011年的从28.3%至2016年的33.6%,同比增长19%

  支持向量机,从2011年的从28.6%至2016年的33.6%,同比增长18%

  回归算法,从2011年的从57.9%至2016年的67.1%,同比增长16%

  在2016年最受欢迎的新算法是:

  K-近邻算法(K-nearest neighbors,KNN),46%份额

  主成分分析(Principal Commponent Analysis,PCA),43%

  随机森林算法(Random Forests,RF),38%

  最优化算法(Optimization),24%

  神经网络-深度学习(Neural networks-Deep Learning),19%

  奇异值矩阵分解(Singular Value Decomposition,SVD), 16%

  跌幅最大的算法分别为:

  关联规则(Association rules),从2011年的28.6%至2016年的15.3%,同比下降47%

  增量建模(Uplift modeling),从2011年的4.8%至2016年的3.1%,同比下降36%

  因子分析(Factor Analysis),从2011年的18.6%至2016年的14.2%,同比下降24%

  生存分析(Survival Analysis),从2011年的9.3%至2016年的7.9%,同比下降15%

  下表显示了不同算法类型的用途:监督学习、无监督学习、元分析和其他算法类型。我们排除了NA(4.5%)和其他(3%)的算法。

  表1:按行业类型的算法使用

  我们注意到,几乎所有人都在使用监督学习算法。

  政府和产业的数据科学家们比学生或学术界使用了更多的不同类型的算法,产业数据科学家更倾向使用元算法。

  接下来,我们分析深度学习的十大算法按行业类型的使用。

  表2:深度学习的十大算法按就业类型的使用

  Table 2: Top 10 Algorithms + Deep Learning usage by Employment Type

  为了使差异更为醒目,我们计算特定行业类型相关的平均算法使用量设计算法为Bias(Alg,Type)=Usage(Alg,Type)/Usage(Alg,All)-1。

  图2:按行业的算法使用偏差

  我们注意到产业界数据科学家更倾向使用回归算法、可视化、统计算法、随机森林算法和时间序列。政府/非盈利组织更倾向使用可视化、主成分分析和时间序列。学术研究人员更倾向使用主成分分析和深度学习。学生通常使用算法较少,但他们用的更多的是文本挖掘和深度学习。

  接下来,我们看看代表整体KDnuggets访客的地区参与情况。

  参与投票者的地区分布如下:

  北美,40%

  欧洲,32%

  亚洲8%

  拉美,5.0%

  非洲/中东,3.4%

  澳洲/新西兰,2.2%

  与2011年的调查一样,我们将产业/政府合并为同一个组,将学术研究人员/学生合并为第二组,并计算算法对产业/ 政府的“亲切度”:

  N(Alg,Ind_Gov) / N(Alg,Aca_Stu)
  ———————————————- - 1
  N(Ind_Gov) / N(Aca_Stu)
  
  亲切度为0的算法在产业/政府和学术研究人员/学生的使用情况相同。IG亲切度约稿表示该算法越“产业”,越低则表示越“学术”。

  其中最“产业”的算法”是:

  增量建模(Uplift modeling),2.01

  异常检测(Anomaly Detection),1.61

  生存分析(Survival Analysis),1.39

  因子分析(Factor Analysis),0.83

  时间序列(Time series/Sequences),0.69

  关联规则(Association Rules),0.5

  虽然增量建模又一次成为最“产业”的算法,但出乎意料的是它的使用率如此低:区区3.1%,在这次调查中,是使用率最低的算法。

  最“学术”的算法是:

  神经网络(Neural networks - regular),-0.35

  朴素贝叶斯(Naive Bayes),-0.35

  支持向量机(SVM),-0.24

  深度学习(Deep Learning),-0.19

  最大期望算法(EM),-0.17

  下图显示了所有算法以及它们在产业界/学术界的亲切度:

  图3:Kdnugets调查:数据科学家使用的流行算法:产业界vs学术界

  下表包含了算法的详细信息,在2016年和2011年使用它们的受访者百分比调查,变化(%2016 /%2011 - 1)和行业亲切度如上所述。

  表3:KDnuggets2016调查:数据科学家使用的算法

  下表包含各个算法的详细信息:

  N: 根据使用度排名

  Algorithm: 算法名称

  Type:类型。S - 监督,U - 无监督,M - 元,Z - 其他,

  2016 % used:2016年调查中使用该算法的受访者比例

  2011 % used:2011年调查中使用该算法的受访者比例

  %Change:变动 (%2016 / %2011 - 1)

  Industry Affinity:产业亲切度(上文已提到)

k-近邻算法

k-近邻算法

简单地说,k-近邻算法采用测量不同特征值之间的距离方法来进行分类。

优缺点

优点:精度高、对异常值不敏感、无数据输入假定
缺点:计算复杂度高、空间复杂度高
适用数据范围:数值型和标称型

工作原理

存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)的分类标签。一般说来,我们只选择样本数据集中前k个最相似的数据,这就k-近邻算法中k的出处,通常k是不大于20的整数。最后选择k个最相似数据中出现次数最多的分类(投票规则),作为新数据的分类。

一般流程

收集数据:可使用任何方法
准备数据:数据格式结构化处理
分析数据:任意选择方法
训练算法:此步骤不适用于k-近邻算法
测试算法:计算错误率
使用算法:首先输入样本数据和结构化的输出结果,然后运行k-近邻算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理

Dictionary of Algorithms and Data Structures

算法和数据结构词典

我们知道,在编程的世界里,主要就是两个事,用一定的算法去处理一定的数据。算法可以理解为业务逻辑流程,而数据自然一定是按某种结构来存放,这就是数据结构。我们知道,数据结构的修改一定会导致算法的修改,我们也知道,数据结构直接关系到了整个程序的繁简性,高效性。而算法则是关系到数据处理的时间、空间性能,以及日后的扩展和维护。这两个东西是计算机科班出生的人或是需要学习编程的人必需要注意的两件头等大事。

下面这个网站,由 Software and Systems Division, Information Technology Laboratory 创建。

http://xlinux.nist.gov/dads/

这是一个关于算法,算法技术,数据结构,系统架构等相关问题的一个词典。其中,算法包括了一些常见的算法,比如: Ackermann’s function ,一些算法问题包括了 traveling salesman(销售员出差问题) and Byzantine generals(拜占庭将军问题),还有一些关于这些问题,算法的 实现链表 以及更多的信息。而索引页包括 领域索引 和 类型索引.

参考资料

可视化的排序过程

0%