马上注册，结交更多数据大咖，获取更多知识干货，轻松玩转大数据
您需要 登录 才可以下载或查看，没有帐号？立即注册
x
科学家找到对付数据洪流的最佳算法 原文: Best-Ever Algorithm Found for HugeStreams of Data 来自：品觉微信公众号
来源: https://www.quantamagazine.org/best-ever-algorithm-found-for-huge-streams-of-data-20171024/ 原文翻译：
要对数据洪流展开高效分析，科学家先得把它们拆分成涓涓溪流。 如果你迎面受到消防水龙带的冲击，就很难测量它的水量。从某种意义上讲，流数据分析的难点就在这里，这股洪流接连不断，一刻也不停歇。监测Twitter上源源不断的推文时，你也许想按下暂停键，以便找出当前的热门趋势。但这不可行，你得想个办法，在主题标签不断涌现的同时，计算出最新流行趋势。 执行此类动态计算的程序被称为流算法。在大量数据的持续冲击之下，它们试图将精髓记录下来，同时有策略地遗忘其余。30多年来，计算机科学家不断改进着流算法。直至去年秋天，一研究团队终于开发出一种堪称完美的算法。 从各个维度看，“这个新算法的表现都是最优秀的，”研究参与者、哈佛大学计算机科学家杰拉尼·尼尔森（Jelani Nelson）说。同时参与研究的还有丹麦奥胡斯大学的卡斯珀·格林拉森（Kasper Green Larsen）、美国东北大学的阮辉（HuyNguyen；音），以及哥本哈根大学的米尔·索普（Mikkel Thorup）。 这个最佳流算法的原理是：只把处理对象中该记的记录下来，以能判断出现频现项目为限。它告诉我们，在流数据分析中，那些看似不可避免的妥协其实并非必要。另外，它也为我们进入“战略性遗忘”时代指明了道路。 发现趋势 : 只要你监测的是一个持续更新的数据库，流算法就有用武之地。可以是AT&T追踪数据包，也可以是谷歌追踪永无止境的搜索词条流——在这些情况下，如果不用重新检查甚至记住每一个数据就能实时解答问题，这样的方法非常有用，甚至是必不可少的。 举个简单的例子：试想你有一个持续的数字流，你想知道每时每刻的所有数字之和。很明显：你不必记住每一个出现过的数字，只要记住一个数字就行：不断更新的总和。 但是，如果你想从数据中提取更为复杂的信息，难度就会增加。比如，你想知道的不是总和，而是哪个数字出现频率最高。这种情况下，有没有一种简便的途径，使你随时掌握答案？这就没那么显而易见了。 这个难题被称为“频现项目”或“重量级项目”难题。针对该难题的第一个算法出现于80年代，由康奈尔大学的贾戴维·格里斯（David Gries）和德州大学奥斯汀分校的雅德维·米斯雷拉（Jayadev Misra）开发。他们的程序适用于多种情境，但无法应对所谓的“变化检测”。它能找出最常搜索词条，但无法辨别当前流行趋势。就好比谷歌可以找到“Wikipedia”是有史以来搜索次数最多的词条，但无法判断出厄玛飓风发生时的热门搜索词条。 “这是一个编码问题——将信息编码成简练的摘要，之后再将信息提取出来，找回你最初编入的内容，”华威大学计算机科学家格雷厄姆·科莫德（Graham Cormode）说。
后来的30年中，科莫德等计算机科学家改进了格里斯和米斯拉的算法。在那些新算法中，有的能检测流行词条等，还有的能找出定义更为精细的“频现”项目。这些算法都有所取舍，比如牺牲速度，以求准确，或是牺牲内存以求可靠性。 其中大多数都离不开索引。比如，你想找出搜索频率最高的词条。办法之一就是给英语中每一个单词指定一个数字，继而给这个数字匹配另一个数字，记录该单词被搜索的次数。打个比方，“aardvark”一词被指定的索引数字是17，它在数据库中显示为（17，9），意为第17号单词被搜索过9次。这样一来，你随时都能调取出现频率最高的单词，因为你知道每个单词被搜索过多少次。 但这样做也有一个缺陷——英语中有几十万个单词，算法每次把它们过一遍，都要耗费大量时间。 但是，假如字典中只有100个单词呢？这样的话，“将所有单词过一遍就不需要那么长时间了，”尼尔森说。 可惜，字典中的单词数是不可更改的事实。但新算法的开发者们发现，我们可以将大字典拆成小字典，再将其巧妙地拼接回去。 小数据 举个例子，你正在检测一个数字流，其中的数字从0-50,000,000不等（类似于通过IP地址记录互联网用户的任务）。你当然能使用一个50,000,000词条组成的索引，但这样很不好办。更好的办法是将八位数拆分成四个两位数。 就以数字12,345,678为例。想要节省内存，一种存储方法就是把它拆分成四个两位数字块：12，34，56，78。然后分配给负责计算项目频率的次级算法：12分配给算法副本一，34分配给副本二，56分配给副本三，78分配给副本四。 每个次级算法都维护着一个索引，用于处理分配到的数字，但由于其处理对象最大不过两位数，因此，每个索引的区间只为0到99。 分拆有一个重要功能：若某个大数（如12,345,678）在整个数据流中反复出现，那么，它的各个两位数字块也会反复出现。你要求次级算法找出各自的频现字块，于是，副本一返回结果为12，副本二返回结果34，以此类推。只要在四个简短得多的列表中寻找频率最高的数字，你就能找到巨型列表中频率最高的数字。
“本来，你得耗费5000万个单位的时间，把整个宇宙都过一遍；现在，你只需要四个算法，并使用100个单位的时间，”尼尔森说。 这种化整为零的策略有个主要问题：虽然将大数拆分出小数很容易，但反过来就难了——你很难把小数寻回，丝毫不差地组合成原先的大数。 继续刚才的例子，在你的数字流中，一个两位数字块频繁出现，比如12,345,678和12,999,999，两者都以12开头。算法将两个大数分别拆分成四个小数，再将小数分配给次级算法。之后，你问次级算法：“在你看到的数字中，哪个数字出现频率最高？”算法副本一就会回答：“数字12出现最多。”算法在判断出现频率最高的八位数时，无法判定这些12是隶属于同一个八位数，还是来自两个不同的八位数。 “确定哪个字块该跟哪个字块串联起来，这是一大难点，”尼尔森说。 为解决这一困境，算法作者们给每个字块添上小标签，标签本身不占什么内存，但有了它们，算法就能将字块组回最初的大数。 举个例子，先将12,345,678拆分成两位数字块。但先不要分配给次级算法，先给它们添加一对唯一识别号，用于之后的重新组合。一个标签为字块本身的名称，另一个标签将其链接到另一个字块。于是，12,345,678就成了： 在上例中，字块12的名称为“0”，被链接到名称为“1”的字块。字块34名称为“1”，被连接到名称为“2”的字块。以此类推。 次级算法在返回频率最高的两位数字块之后，12就开始寻找标记为“1”的字块，结果找了了34，34寻找标记为“2”的字块，结果找到了56，56寻找标记为“3”的字块，结果找到了78。 这些两位数字块就相当于一根链条中的不同环节，将它们链接起来的是这些附带的数字标签。 常言道，链条的强度取决于最弱的一环。而这些链条的断裂几乎不可避免。 搭字块 没有什么算法是每次运行都滴水不漏的——哪怕是最好的算法，偶尔也有掉链子的时候。比如说，第二个两位数字块被指定了一个错误的标签，结果，它在寻找后续字块时，就找不到56。而只要其中一环断裂，整场努力就作废了。 哥本哈根大学计算机科学家米尔·索普参与开发了一种不易出错的数据存取方式。 为避免这种情况，研究人员们用到了“扩展图”。在扩展图中，每个两位数字块为一个点。点与点之间通过线段相连（见上图所示流程），构成一个集群。扩展图的重要功能在于，每个点（两位数字块）都与多个点相连，不仅仅是与邻接的点相链。比如12,345,678，12在与34相连的同时，也与56相连，这样一来，即便12和34之间的链接断裂，你依然知道，12与56从属于同一个数字。 扩展图并非天衣无缝。本应存在的链接会缺失，不应链接的字块也会被链到一块。为抵消这一倾向，研究人员开发了算法中的最后一步：一种致力于“集群保有”的次级算法，可以检验扩展图，在某些链接缺失，或者存在错误链接的情况下，它能准确确定哪些点属于同一个集群、哪些不属于一个集群。 “这确保了最初集群能被恢复出来，”索普说。 虽然Twitter不至于明天就用上扩展图，但其背后的基本思路适用于范围很广的计算机科学问题，而不仅限于推文趋势的计算。该算法还证明，在解决频现项目问题时，妥协并不是必须的。先前的算法总是有所取舍——要么虽然准确但耗内存，要么速度快但计算不了当前热门趋势。而这一最新成果显示，有了最合适的编码方式，你可以做到十全十美：既可以将频现项目存储起来，也能在需要时调用。
车品觉简介
畅销书《决战大数据》作者 红杉资本中国基金专家合伙人 国信优易数据研究院院长 滨海泰达物流(HK：08348)非執行董事
香港特区创新科技及再工业化委员会委员
贵阳市大数据委顧问 上海市司法局大数据实验室专家 CCF大数据委副主任 乌镇智厍理事
浙江大学管理学院兼职教授 清华大学（大数据项目）教育指导委员 Advisory Committee of Big Data institute - HKUST
全国信标委大数据标准工作组副组长(2015-2017) 原阿里巴巴集团副总裁 原阿里健康（HK：00241）独立董事 原阿里数据委员会会长
2014年领导阿里数据团队获得Top CIO评选为中国最佳信息化团队 2017年被国家信息中心选为中国十大最具影响力大数据企业家
拥有十几年丰富的数据实战经验，并在实践中形成了独特的数据化思考及管理方式，对大数据未来趋势有独到见解；亲自领导阿里数据团队在大数据实践领域取得了一系列重要成果，包括为阿里建立集团各事业群的业务及决策分析框架，开发智能化的数据产品，成立了驱动集团数据化的运营团队，成功发起了公共与专有数据资产管理体系，还发布了数据安全规范等。
| 
/1 
发表于 2017-11-8 11:17:36
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
转播
分享
淘帖
赞
踩
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜