每周学点大数据 | No.10何谓大数据算法

No.10期

何谓大数据算法

Mr. 王:下面我们就来谈谈大数据算法与一般算法的区别和联系。

小可:好。

Mr. 王:前面我们讲了如何评价一个算法,在相对比较小的数据规模下,我们往往可以接受多项式时间算法。但是当数据量很大时,很多小数据量上我们能够在可以接受的时间内解决问题的方法,也都变得不再可以接受。虽然有些算法是多项式算法,但是它的高阶项指数却是非常大的,导致当数据规模大起来时,它的增长速度会变得非常快。对于较大的数据量,资源约束和时间约束都变得相对很苛刻,我们要对可以接受的时间界限进行重新思考。

小可:那在大数据上比较好的算法是什么样的呢?

Mr. 王:大数据算法是在给定的资源约束下,以大数据为输入,在给定的时间约束内可以生成满足给定约束结果的算法。

对于大数据而言,访问全部数据是很费时的,所以大数据算法有时需要采取读取部分数据的办法,也就是设计时间亚线性算法。而且数据往往在内存中也存不下,数据要存储在磁盘上,所以要考虑设计外存算法;或者是采取读取部分数据的办法,设计空间亚线性算法。

小可:亚线性算法有一种抽样的感觉,不访问全部数据,而是尝试选择部分数据来代表全部数据。

Mr. 王:没错。如果单台计算机不能保存所有的数据,或者一台计算机的计算资源不足以在给定的时间内解决问题,则还要引入多台计算机进行并行处理,让它们的CPU、内存、磁盘都参与到问题的解决之中,这时候还要设计并行算法。甚至当计算机的能力不足以对某些问题进行处理,或者对某些问题的处理不够好,而这些问题的某一部分恰好是人类非常擅长做的工作时,还可以引入人工参与到问题的解决之中。

小可:引入人工来帮忙,这倒真是神奇啊!我还以为计算机算法都是一定要计算机来执行的呢,大数据算法还可以不是完全由计算机执行的啊?

Mr. 王:嗯,不仅如此,大数据算法还可以不是内存算法,很多时候需要磁盘参与到海量数据的存储之中;可以不是精确算法,很多时候得出精确解的代价过大,大数据算法就以得出一个足够让我们满意的近似解来谋求更高的计算效率;可以不是串行算法,在很多常见的大数据问题求解中,引入多台计算机参与到其中,发挥它们的各种计算资源的使用以提升问题的解决速度;甚至可以不是仅仅由计算机来执行的算法,在某些特定的情况下,有很多问题由人工来解决会比由机器来解决更容易、更准确或者更高效一些。从这些方面来看,大数据算法的设计和分析与传统的经典算法有着很大的区别。

另外,在大数据算法中常用的算法设计技术有:精确算法设计方法、并行算法、近似算法、随机算法、在线算法/ 数据流算法、外存算法、面向新型体系结构的算法、现代优化算法等。在大数据算法设计之后,与经典算法一样,依然要对算法进行分析。但在分析大数据算法时,我们需要研究的也不仅仅限于时间、空间复杂度的分析和优化。对于一些不能得出精确解的算法,还要对结果质量进行分析,看看在我们可以接受的时间范围内得出的近似结论是不是足够达到要求;对于要借助磁盘存储的算法,还要考虑磁盘的IO 复杂性。有时候大数据算法会运行在比如无线传感器节点这样的对电池电力有较强限制的终端上,我们还要分析算法运行消耗的能量是不是很大,这时还要进行能量复杂度分析;如果我们使用的是一个分布式系统,整个系统架构在网络上,要依靠各个节点的频繁通信来实现,那么还要考虑系统的通信复杂度。这些特点也使得大数据算法的分析变得相对复杂一些。

这些概念现在听起来也是一头雾水吧?

小可:嗯,的确。

Mr. 王:在以后的课程中,我会把大数据算法所涉及的内容讲解给你。以后我会给你讲讲大数据算法中的亚线性算法、外存算法、并行算法、众包算法,这些都是大数据算法中的核心算法。时间不早了,我们先下课吧。

小可:那太好了。那就明天再见了,老师。

内容来源:灯塔大数据

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2016-10-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏织云平台团队的专栏

腾讯百万指标的无阈值检测算法即将开源

别焦虑,为了让广大运维同仁能够尽快步入 AIOps 的技术殿堂,降低实施 AIOps 的技术门槛,腾讯织云团队即将开源运维学件!( ps: 学件由南京大学周志华...

5882
来自专栏机器之心

前沿 | BAIR提出人机合作新范式:教你如何高效安全地在月球着陆

选自BAIR 作者:Siddharth Reddy 机器之心编译 参与:Pedro、刘晓坤 人机合作可以提高很多现实高危任务的成功率和安全性,特别是对于视野受限...

2716
来自专栏AI科技评论

学界丨从一个失败的强化学习训练说起:OpenAI 探讨应该如何设计奖励函数?

AI科技评论按:在当下,强化学习算法以一种惊奇、不可思议的方式进入到了我们的视野中。AI 科技评论此前也做过不少相关的覆盖和报道,而在 OpenAI 的这篇文章...

29811
来自专栏申龙斌的程序人生

读书:学得少,考得好

《Learn More Study Less》这本书最早在网上直译为《学得少却考得好》,后来机械工业出版社翻译为《如何高效学习》。这本书我是2013年从褪墨网站...

37313
来自专栏大数据挖掘DT机器学习

当推荐算法开源包多如牛毛,为什么我们还要专门的推荐算法工程师

作为一个推荐系统业余爱好者,在机器学习领域的鄙视链中,我感觉一直地位不高,时常被搞NLP CV语音等高科技技术的朋友鄙视。 最近甚至被人问,推荐算法开源包多如牛...

4059
来自专栏新智元

DeepMind 新算法NEC:让 AI 在学习速度上超越人类

【新智元导读】 DeepMind 研究团队的新论文Neural Episodic Control提出了一种称为NEC的新算法,使得“更广泛环境下的学习速度大幅度...

3375
来自专栏AI科技评论

【深度】机器学习如何帮助Youtube 实现高效转码?

GAIR 今年夏天,雷锋网将在深圳举办一场盛况空前的“全球人工智能与机器人创新大会”(简称GAIR)。大会现场,雷锋网将发布“人工智能&机器人Top25创新企...

3955
来自专栏ATYUN订阅号

OpenAI发布8个模拟机器人环境以及一种HER实现,以训练实体机器人模型

OpenAI:我们将发布8个模拟的机器人环境,以及一种叫做“事后经验回顾”(Hindsight Experience Replay,简称HER)的一种Basel...

45212
来自专栏新智元

Jeff Dean、李飞飞等发起SysML大会,Jeff Dean主题演讲:系统与机器学习融合(45PPT)

新智元报道 来源:SysML 2018 编辑:闻菲、艾霄葆、常佩琦、刘小芹 【新智元导读】Jeff Dean、Michael I.Jordan、李飞飞、...

4288
来自专栏AI科技评论

利用好奇心做稀疏反馈任务的学习

AI 科技评论按:近期,Unity 发布了版本 0.4 的机器学习智能体工具包(ML-Agent toolkit v0.4),其中最为突出的新功能是通过额外的基...

952

扫码关注云+社区

领取腾讯云代金券