第1卷第6期 VoL 1 No 6 012年11月 网络新媒体技术 Nov.2012 面向大数据的海云数据系统关键技术研究 黄哲学曹付元李俊杰陈小军 (中国科学院深圳先进技术研究院深圳518055深圳市高性能数据挖掘重点实验室深圳518055) 摘要:由于数据产生成本的急速下降,人类社会产生的数据不仅以指数级别增长,而且数据的结构变得日趋复杂,使得传统的 数据分析技术遇到了极大的挑战。如何对大量复杂数据进行分析和挖掘,从中提取有价值的知识用于决策,已经成为产业界 和学术界的广泛关注问题,在一些国家已己上升到国家战略层面。本文介绍了大数据的基本概念、特征和面临的科学问题,总 结了中国科学院战略性先导科技专项“面向感知中国的新一代信息技术研究”中“海云数据系统关键技术研究与系统研制”课 题的一些先期成果,为开发大数据管理、分析和挖掘系统提供一些参考依据。 关键词:大数据系统,大数据分析,数据挖掘,可视分析 Developing Sea Cloud Data System Key Technologies for Large Data Analysis and mining HUANG Zhexue, CAO Fuyuan, LI Junjie, CHEN Xiaojun (Shenzhen Institutes of Advanced Technology, CAS, Shenzhen,518055,China Shenzhen Key Laboratory of High Performance Data Mining, Shenzhen, 518055, China) Abstract: As the cost of data generation is going down, the data generated in the society potentially. Furthermore, the complexity of the data structure is increasing as well. This phenomenon presents an extremely big challenge to the traditional data anal ysis techniques. How to analyze and mine big data and extract valuable knowledge for decision making has become a popular big con cern in academics and industry. Some countries have raised this issue to the national strategic level. In this paper, we some basic concepts about big data, its characteristics and scientifie research problems. We then summarize some initial project of"research and development of key technologies for sea and cloud data systems" in the program of"sensing China oriented next generation information technologies" being carried out in Chinese Academy of Sciences. We propose further innovations on the re- lated technologies to spearhead the research on big data management, analysis and mining in the near future. Keywords: Big data system, big data analysis, data mining, visual analytics 引言 随着物联网、移动互联网和云计算技术及应用的蓬勃发展,人类产生的数据量不仅以指数级增长,而且数 据的结构变得日趋复杂,超越了传统数据库的管理能力。大数据问题( Big data problen)近两年成为信息技术 学术界和产业界热论的焦点。普遍舆论认为,大数据问题已经成为信息科学技术领域的重要前沿课题之 本文于2012-09-17收到 *中国科学院战略性先导科技专项“面向感知中国的新一代信息技术研究”(XDA06000000课题“海云数据系统关键技术研究与系统研制” o1994-2013CHinaAcademicJournalElectronicpUblishingHouse.Allrightsreservedhttp://www.cnki.net
第 1 卷第 6 期 2012 年 11 月 网 络 新 媒 体 技 术 Vol. 1 No. 6 Nov. 2012 面向大数据的海云数据系统关键技术研究* 黄哲学 曹付元 李俊杰 陈小军 ( 中国科学院深圳先进技术研究院 深圳 518055 深圳市高性能数据挖掘重点实验室 深圳 518055) 摘要: 由于数据产生成本的急速下降，人类社会产生的数据不仅以指数级别增长，而且数据的结构变得日趋复杂，使得传统的 数据分析技术遇到了极大的挑战。如何对大量复杂数据进行分析和挖掘，从中提取有价值的知识用于决策，已经成为产业界 和学术界的广泛关注问题，在一些国家已上升到国家战略层面。本文介绍了大数据的基本概念、特征和面临的科学问题，总 结了中国科学院战略性先导科技专项“面向感知中国的新一代信息技术研究”中“海云数据系统关键技术研究与系统研制”课 题的一些先期成果，为开发大数据管理、分析和挖掘系统提供一些参考依据。 关键词: 大数据系统，大数据分析，数据挖掘，可视分析 Developing Sea Cloud Data System Key Technologies for Large Data Analysis and Mining HUANG Zhexue，CAO Fuyuan，LI Junjie，CHEN Xiaojun ( Shenzhen Institutes of Advanced Technology，CAS，Shenzhen，518055，China， Shenzhen Key Laboratory of High Performance Data Mining，Shenzhen，518055，China) Abstract: As the cost of data generation is going down，the data generated in the society increases exponentially. Furthermore，the complexity of the data structure is increasing as well. This phenomenon presents an extremely big challenge to the traditional data analysis techniques. How to analyze and mine big data and extract valuable knowledge for decision making has become a popular big concern in academics and industry. Some countries have raised this issue to the national strategic level. In this paper，we first introduce some basic concepts about big data，its characteristics and scientific research problems. We then summarize some initial results of the project of“research and development of key technologies for sea and cloud data systems”in the program of“sensing China oriented next generation information technologies”being carried out in Chinese Academy of Sciences. We propose further innovations on the related technologies to spearhead the research on big data management，analysis and mining in the near future. Keywords: Big data system，big data analysis，data mining，visual analytics 1 引言 随着物联网、移动互联网和云计算技术及应用的蓬勃发展，人类产生的数据量不仅以指数级增长，而且数 据的结构变得日趋复杂，超越了传统数据库的管理能力。大数据问题( Big Data Problem) 近两年成为信息技术 学术界和产业界热论的焦点。普遍舆论认为，大数据问题已经成为信息科学技术领域的重要前沿课题之一。 本文于 2012 － 09 － 17 收到。 * 中国科学院战略性先导科技专项“面向感知中国的新一代信息技术研究”( XDA06000000) 课题“海云数据系统关键技术研究与系统研制” ( XDA06010500) 资助
6期 黄哲学等:面向大数据的海云数据系统关键技术研究 21 011年5月,EMC公司在美国拉斯维加斯举办了第11届 EMC World年度大会,设定的主题为“云计算 相遇大数据”,大会正式提出了“大数据”( Big data)概念。随后,IBM和麦肯锡等众多国外机构发布了“大数 据”相关研究报告,阐述了大数据的特征,给社会经济发展带来的机遇和对当前信息技术的挑战。可以预 测,大数据将成为继云计算和物联网之后,信息技术产业又一次颠覆性的技术变革 在学术界,国际顶级期刊cae》和 <Sciences》近期针对大数据分别出版了专刊 Big data》的和el ing with data》向,从互联网技术、互联网经济学、超级计算、环境科学、生物医药等多个方面讨论了大数据处 理面临的各种问题。2012年8月12~16日在北京举办的第18届知识发现与数据挖掘(KDD)国际会议,大 数据成为重要议题,其暑期培训班( KDD Summer School on Mining the Big Data)和专家论坛( Panel discus- sion)都是集中讨论大数据问题。2011年11月26日,中国软件开发联盟(CSDN)在北京成功举办了中国大 数据技术大会。为推动大数据这个交叉学科的发展,中国计算机学会(CCF)成立了大数据专家委员会(CCF Big data task force,简称 CCF TFBD)。 大数据的机遇与挑战已经从商业领域上升到国家战略层面。2012年3月29日,美国政府发布了“大数 据研究和发展倡议”。随后,美国国家科学基金委员会(NSF)、美国国家卫生研究院(NIH)、美国能源部 (DOE)、美国国防部(DOD)、美国国防部高级研究计划局( DARPA)、美国地质勘探局(USGS)六个部门联合 推出了大数据计划,旨在提升从大量复杂数据中获取知识和洞见的能力。 为探讨中国大数据的发展战略,由中国科学院计算技术研究所牵头,2012年5月22~24日在北京成功 举办了以“网络数据科学与工程 门新兴的交叉学科?”为主题的第424次香山科学会议,与会国内外知 名专家学者为中国大数据发展战略建言献计。2012年8月14~15日,中国科学院启动了“面向感知中国的 新一代信息技术研究”战略性先导科技专项,任务之一是研制用于大数据采集、存储、处理、分析和挖掘的未 来数据系统 信息时代万物数化,大数据的重要性已成行业共识,针对大数据技术和应用的创新,其发展趋势不可阻 挡。如何对大数据进行充分和有效的分析和挖掘,使之转换为有价值的信息和知识,用于解决各种各样的 科学和应用问题,成为大数据时代信息技术发展的重大挑战,同时也是信息技术创新的新的制高点。 本文首先对大数据的概念、特征及其价值作简要概述,然后阐述大数据分析与挖掘的三个科学问题,最 后介绍中国科学院“面向感知中国的新一代信息技术研究”战略性先导科技专项“海云数据系统关键技术研 究与系统研制”课题的一些前期研究成果。 2大数据 2.1什么是大数据? 对于什么样的数据是大数据目前还没有明确的定义,对数据的使用者来讲,如果数据集超出了使用者 所拥有的信息处理和分析的能力,就给使用者带来了大数据问题。 根据麦肯锡预计,至200年,美国超过1000雇员的公司,平均每个公司存有200TB的数据,很多行业 的公司,如银行、电讯、互联网、政府部门等,平均存储的数据超过1个PB。尽管大量的数据存储在各大公司 和政府机构的数据中心,但数据的价值都没有充分发挥出来。缺少有效的数据整合和数据分析与挖掘技术 及方法是其主要的技术障碍,更深层次的原因是对数据潜在价值的认识不足和缺少可以挖掘出数据价值的 技术手段及人才 2.2大数据特征 在2011年10月美国拉斯维加斯举办的IOD2011大会上,BM给出了大数据的“3V”特征,即多样性 ( variety))、体量( volume)、速度( velocity)。多样性是指数据来自多种数据源,并且数据类型包含结构化和非 结构化数据。体量是指整合在一起供分析与挖掘的数据量非常庞大的。速度则是指数据生成和处理的速 度必须很快,也包含数据内容的变化也快。 大数据的这些特征对现有的数据分析与挖掘方法、技术、算法和软件带来新的挑战,使基于传统服务器 进行数据挖掘的方式产生极大的瓶颈。用户为提高大数据分析与挖掘的能力,必须提高服务器的性能,包 o1994-2013CHinaAcademicJournalElectronicpUblishingHouse.Allrightsreservedhttp://www.cnki.net
6 期 黄哲学 等: 面向大数据的海云数据系统关键技术研究 2011 年 5 月，EMC 公司在美国拉斯维加斯举办了第 11 届 EMC World 年度大会，设定的主题为“云计算 相遇大数据”，大会正式提出了“大数据”( Big Data) 概念。随后，IBM 和麦肯锡等众多国外机构发布了“大数 据”相关研究报告，阐述了大数据的特征，给社会经济发展带来的机遇和对当前信息技术的挑战。可以预 测，大数据将成为继云计算和物联网之后，信息技术产业又一次颠覆性的技术变革。 在学术界，国际顶级期刊《Nature》和《Sciences》近期针对大数据分别出版了专刊《Big Data》［3］和《Dealing with Data》［4］，从互联网技术、互联网经济学、超级计算、环境科学、生物医药等多个方面讨论了大数据处 理面临的各种问题。2012 年 8 月 12 ～ 16 日在北京举办的第 18 届知识发现与数据挖掘( KDD) 国际会议，大 数据成为重要议题，其暑期培训班( KDD Summer School on Mining the Big Data) 和专家论坛( Panel Discussion) 都是集中讨论大数据问题。2011 年 11 月 26 日，中国软件开发联盟( CSDN) 在北京成功举办了中国大 数据技术大会。为推动大数据这个交叉学科的发展，中国计算机学会( CCF) 成立了大数据专家委员会( CCF Big Data Task Force，简称 CCF TFBD) 。 大数据的机遇与挑战已经从商业领域上升到国家战略层面。2012 年 3 月 29 日，美国政府发布了“大数 据研究和发展倡议”。随后，美国国家科学基金委员会( NSF) 、美国国家卫生研究院( NIH) 、美国能源部 ( DOE) 、美国国防部( DOD) 、美国国防部高级研究计划局( DARPA) 、美国地质勘探局( USGS) 六个部门联合 推出了大数据计划，旨在提升从大量复杂数据中获取知识和洞见的能力。 为探讨中国大数据的发展战略，由中国科学院计算技术研究所牵头，2012 年 5 月 22 ～ 24 日在北京成功 举办了以“网络数据科学与工程 ─ 一门新兴的交叉学科?”为主题的第 424 次香山科学会议，与会国内外知 名专家学者为中国大数据发展战略建言献计。2012 年 8 月 14 ～ 15 日，中国科学院启动了“面向感知中国的 新一代信息技术研究”战略性先导科技专项，任务之一是研制用于大数据采集、存储、处理、分析和挖掘的未 来数据系统。 信息时代万物数化，大数据的重要性已成行业共识，针对大数据技术和应用的创新，其发展趋势不可阻 挡。如何对大数据进行充分和有效的分析和挖掘，使之转换为有价值的信息和知识，用于解决各种各样的 科学和应用问题，成为大数据时代信息技术发展的重大挑战，同时也是信息技术创新的新的制高点。 本文首先对大数据的概念、特征及其价值作简要概述，然后阐述大数据分析与挖掘的三个科学问题，最 后介绍中国科学院“面向感知中国的新一代信息技术研究”战略性先导科技专项“海云数据系统关键技术研 究与系统研制”课题的一些前期研究成果。 2 大数据 2. 1 什么是大数据? 对于什么样的数据是大数据目前还没有明确的定义，对数据的使用者来讲，如果数据集超出了使用者 所拥有的信息处理和分析的能力，就给使用者带来了大数据问题。 根据麦肯锡预计［5］，至2009 年，美国超过1000 雇员的公司，平均每个公司存有200TB 的数据，很多行业 的公司，如银行、电讯、互联网、政府部门等，平均存储的数据超过 1 个 PB。尽管大量的数据存储在各大公司 和政府机构的数据中心，但数据的价值都没有充分发挥出来。缺少有效的数据整合和数据分析与挖掘技术 及方法是其主要的技术障碍，更深层次的原因是对数据潜在价值的认识不足和缺少可以挖掘出数据价值的 技术手段及人才。 2. 2 大数据特征 在 2011 年 10 月美国拉斯维加斯举办的 IOD2011 大会上，IBM 给出了大数据的“3V”特征［6］，即多样性 ( variety) 、体量( volume) 、速度( velocity) 。多样性是指数据来自多种数据源，并且数据类型包含结构化和非 结构化数据。体量是指整合在一起供分析与挖掘的数据量非常庞大的。速度则是指数据生成和处理的速 度必须很快，也包含数据内容的变化也快。 大数据的这些特征对现有的数据分析与挖掘方法、技术、算法和软件带来新的挑战，使基于传统服务器 进行数据挖掘的方式产生极大的瓶颈。用户为提高大数据分析与挖掘的能力，必须提高服务器的性能，包 21
网络新媒体技术 2012年 括存储、内存和CPU,造成机器成本和能耗不断提高。当前大部分数据分析与挖掘软件不具备TB级以上大 数据的复杂分析和建模能力。 随着对大数据价值认识的深入,大数据的典型特征又加入的一个价值( Value)维度,用以描述大数据的 价值。在现实应用中,数据量大的数据并不一定有很大的价值。例如,很多数据在没有有效整合之前,重要 的分析与挖掘无法开展,因此不具有很大的应用价值,而数据整合本身就是大数据的一大挑战。不能及时 有效处理分析的数据也没有很大的应用价值,如大量的视频数据,目前还没有有效分析和挖掘大量视频数 据的技术,很多应用还要靠人来监控 2.3大数据的价值 大量数据的生成和累积是信息化的必然结果。现代企业在采购、仓储、运输、产品设计、生产、销售和客 户服务等诸多环节都采集并积累了大量的供应商、服务提供商和客户的交易数据,生产和经营数据,产品研 发数据,财务及人力资源管理数据等,因此可以说现代企业是运营在数据之上,诸多生产和经营的决策问题 必须通过数据分析才能解决 麦肯锡的研究表明,随着消费者、企业和各经济部门充分发挥大数据的潜力,由大数据驱动的创新、生 产力提高、经济增长、以及新的竞争模式和价值取向变革的巨大浪潮将达到巅峰。与过去不同的是,随着 系列新技术趋势发展的加速和凝聚,大数据所带来的变化规模和范围已经达到新的拐点,将会迅速膨胀 比如,有效利用大数据可以提高健康护理的质量和效率,潜在为美国每年创造3千亿美元的价值,其中三分 之二是来自于降低健康护理的成本,相当于每年减少全国健康护理花费的8%。零售业充分利用大数据可 以提高运营效益60%。在欧洲发达国家,充分利用大数据提高政府管理效率,每年可以减少政府运营费用1 千亿欧元。相信未来大数据的产业规模将会至少以万亿美元来进行衡量,大数据将会给信息技术领域带来 个新的增长点。 大数据带来的潜在经济价值和社会价值巨大,但这些价值必须通过数据的有效整合、分析和挖掘才能 释放出来。数据的整合是建立数据仓库的必要工作,对于结构化数据的整合有很多解决方案和软件工具 目前的挑战是非结构化数据的融合和整合,如:文本数据、图像数据、信号数据、音频数据、视频数据等,由于 这方面的技术挑战较多,本文不作详细论述。下节针对大数据分析的科学问题和方法问题作一简要介绍。 3大数据分析的科学问题 f1 f2 f3 f4 f5 Thousands of features 数据分析与挖掘的数据基本表达形 1XYZX37 A N 2C V 54 C Y 式是对象一属性矩阵或表格,如图1所 示。其中每一行表达一个对象,如一个 客户。每一列表达对象的一个属性,如 Z C E09 客户的年龄或性别。整个属性的集合确 n-4xVsx口8……1Y 定了对象表达的维度,而行数代表对象 n-3XC口X口 C N 样本的个数。大多数数据分析和挖掘算 n-2DV Y68 法以对象一属性矩阵为输入数据格式, n-1X S VY 57 nZ S V X 0 对这些算法来讲,大数据的挑战具体体 现在对象一属性矩阵的属性数量和对象 Millions of bjects/ 数量都很大,使得这些算法难以处理或 records 得到的结果不满足应用要求。 图1对象一属性矩阵,口表示缺省值 1超高维问题 大数据带来的变化之一是对象的属 性越来越多,虽然表达对象的信息越来越丰富,但成千上万的属性也造成巨大的维度灾难( curse of dimer signality)。 与此同时,这种超高维数据也带来其他一些问题,如:复杂数据类型问题,噪声和缺省值问题,分布不平 o1994-2013CHinaAcademicJournalElectronicpUblishingHouse.Allrightsreservedhttp://www.cnki.net
网 络 新 媒 体 技 术 2012 年 括存储、内存和 CPU，造成机器成本和能耗不断提高。当前大部分数据分析与挖掘软件不具备 TB 级以上大 数据的复杂分析和建模能力。 随着对大数据价值认识的深入，大数据的典型特征又加入的一个价值( Value) 维度，用以描述大数据的 价值。在现实应用中，数据量大的数据并不一定有很大的价值。例如，很多数据在没有有效整合之前，重要 的分析与挖掘无法开展，因此不具有很大的应用价值，而数据整合本身就是大数据的一大挑战。不能及时 有效处理分析的数据也没有很大的应用价值，如大量的视频数据，目前还没有有效分析和挖掘大量视频数 据的技术，很多应用还要靠人来监控。 2. 3 大数据的价值 大量数据的生成和累积是信息化的必然结果。现代企业在采购、仓储、运输、产品设计、生产、销售和客 户服务等诸多环节都采集并积累了大量的供应商、服务提供商和客户的交易数据，生产和经营数据，产品研 发数据，财务及人力资源管理数据等，因此可以说现代企业是运营在数据之上，诸多生产和经营的决策问题 必须通过数据分析才能解决。 麦肯锡的研究表明，随着消费者、企业和各经济部门充分发挥大数据的潜力，由大数据驱动的创新、生 产力提高、经济增长、以及新的竞争模式和价值取向变革的巨大浪潮将达到巅峰。与过去不同的是，随着一 系列新技术趋势发展的加速和凝聚，大数据所带来的变化规模和范围已经达到新的拐点，将会迅速膨胀。 比如，有效利用大数据可以提高健康护理的质量和效率，潜在为美国每年创造 3 千亿美元的价值，其中三分 之二是来自于降低健康护理的成本，相当于每年减少全国健康护理花费的 8% 。零售业充分利用大数据可 以提高运营效益 60% 。在欧洲发达国家，充分利用大数据提高政府管理效率，每年可以减少政府运营费用 1 千亿欧元。相信未来大数据的产业规模将会至少以万亿美元来进行衡量，大数据将会给信息技术领域带来 一个新的增长点。 大数据带来的潜在经济价值和社会价值巨大，但这些价值必须通过数据的有效整合、分析和挖掘才能 释放出来。数据的整合是建立数据仓库的必要工作，对于结构化数据的整合有很多解决方案和软件工具。 目前的挑战是非结构化数据的融合和整合，如: 文本数据、图像数据、信号数据、音频数据、视频数据等，由于 这方面的技术挑战较多，本文不作详细论述。下节针对大数据分析的科学问题和方法问题作一简要介绍。 图 1 对象 － 属性矩阵，□表示缺省值 3 大数据分析的科学问题 数据分析与挖掘的数据基本表达形 式是对象—属性矩阵或表格，如图 1 所 示。其中每一行表达一个对象，如一个 客户。每一列表达对象的一个属性，如 客户的年龄或性别。整个属性的集合确 定了对象表达的维度，而行数代表对象 样本的个数。大多数数据分析和挖掘算 法以对象—属性矩阵为输入数据格式， 对这些算法来讲，大数据的挑战具体体 现在对象—属性矩阵的属性数量和对象 数量都很大，使得这些算法难以处理或 得到的结果不满足应用要求。 3. 1 超高维问题 大数据带来的变化之一是对象的属 性越来越多，虽然表达对象的信息越来越丰富，但成千上万的属性也造成巨大的维度灾难( curse of dimensionality) 。 与此同时，这种超高维数据也带来其他一些问题，如: 复杂数据类型问题，噪声和缺省值问题，分布不平 22
6期 黄哲学等:面向大数据的海云数据系统关键技术研究 23 衡问题,属性相关问题等。这些问题虽然在一般性数据分析中普遍存在,但超高维数据使得这些问题更难 处理。网络社会化文本数据,如微博数据,就属于这类大数据,表达微博内容的关键词属性可以有几万个, 而处理的微博数量也是百万或千万级。 超高维数据不适合用传统的全空间方法来分析,因为超高维数据带有很大的稀疏性,对象簇和类别的表达 体现在部分属性子集,较有效的分析方法是采用子空间方法。同时,由于数据的复杂性,单一的数据挖掘模型, 如决策树模型,难以满足应用的精度要求,必须采用多个模型的集成学习方法建立聚类或分类的集成模型,通 过多个单一模型的综合结果做出最后的决策。目前子空间方法和集成学习方法在国内外已经有大量研究8 3.2数据量问题 大数据分析的另一科学问题是当图1的对象一属性矩阵的行数超过千万或亿的数量级后,其整个矩阵 的数据量将达到上百个GB至TB级,这样大的输入数据远远超出大多数服务器的内存,更不用说在单一服 务器上用复杂的迭代或递归数据挖掘算法进行建模和挖掘。因此,现有的数据挖掘软件和大多数传统的分 类和聚类等算法无法处理这个规模的数据。 解决TB级规模输入数据建模问题的一个可行方法是将对象一属性矩阵切分成大量的子矩阵,然后将 子矩阵文件分布到多个服务器节点上。同时对薮据挖掘算法作并行分布式改造,使每次迭代运算分两步进 行,第一步是在每个计算节点上对子矩阵进行运算,取得子矩阵的局部结果;第二步是将所有子矩阵的局部 结果集中运算,计算出整个对象一属性矩阵的全局结果,然后进入下一次迭代直到得出最后模型。 Hadoop 平台上的Map- reduce计算模型通常用来实现上述分布式算法。 对复杂的数据挖掘算法进行分布式改造需要解决一个算法上的数学问题,即证明这种分解计算再综合 的两步式方法得出的结果要同直接对整个矩阵一步运算的结果等价。如果采用近似计算方法,需要证明两 步式方法得出结果的偏差在可控范围内。在 Hadoop上实现分布式数据挖掘算法的一个技术问题是Map reduce计算模型本身的局限性。Map- reduce最初是为词频统计设计的,适合数据一次性处理,而多数数据 挖掘算法具有迭代、递归、层次等特性,用Map- reduce实现分布式算法经常产生很多额外开销,极大影响运 算效率。因此,设计适合大数据分析与挖掘分布式算法的新型计算模型也是一个重要的科学问题。 当前,许多常用的机器学习和数据挖掘算法都有了Map- reduce分布式版本,最流行的是 Apache的 Mahout开源系统呵,但其算法的执行效率还远远达不到TB级大数据的水平0。 3.3大数据分析方法 大薮据分析与挖掘的另一科学问题是分析方法和分析手段落后。当前普遍采用的数据挖掘建模方法 是样本->建模->测试三步骤方法,建模的过程由算法自动完成,模型建好后,用户对模型进行测试,结 果不满意,改变训练数据和算法参数,由算法自动产生新的模型。这种方法不适用于大数据分析,因为数据 大,算法建模的时间较长,多次重复建模步骤使计算成本和能耗加大。因此,必须硏究新的大数据分析方法。 提高大数据分析与挖掘的效率和效果的方法之一是改变建模的全自动过程,实现大数据建模人机交 互,让专业分析人员的领域知识融入到建模过程中,通过人机交互获得优化模型。实现大数据建模过程人 机交互需要解决两大关键技术’,交互式数据挖掘算法和数据及模型可视化。交互式算法在建模过程中生成 大量中间结果,用可视化技术展现给分析人员,分析人员可以通过观察分析建模的阶段性结果,调整算法参 数或输入数据,指引交互式算法向优化模型的方向计算 大数据可视分析已经成为图形学和可视化领域的研究热点,目前大规模超高维数据可视化方法和技术 还不多,数据挖掘模型和知识可视化研究也在起始阶段,可用的成果很少。 4海云数据系统 海云数据系统是中国科学院“面向感知中国的新一代信息技术”战略性先导科技专项“海云数据系统关 键技术研究与系统研制”课题硏究的重要内容。其目标是研制面向海量数据存储与挖掘的互联网服务平 台,为“海云创新实验环境”用户提供大规模数据存储、处理、挖掘与可视化分析服务,创新数据挖掘互联网 服务模式。 o1994-2013CHinaAcademicJournalElectronicpUblishingHouse.Allrightsreservedhttp://www.cnki.net
6 期 黄哲学 等: 面向大数据的海云数据系统关键技术研究 衡问题，属性相关问题等。这些问题虽然在一般性数据分析中普遍存在，但超高维数据使得这些问题更难 处理。网络社会化文本数据，如微博数据，就属于这类大数据，表达微博内容的关键词属性可以有几万个， 而处理的微博数量也是百万或千万级。 超高维数据不适合用传统的全空间方法来分析，因为超高维数据带有很大的稀疏性，对象簇和类别的表达 体现在部分属性子集，较有效的分析方法是采用子空间方法。同时，由于数据的复杂性，单一的数据挖掘模型， 如决策树模型，难以满足应用的精度要求，必须采用多个模型的集成学习方法建立聚类或分类的集成模型，通 过多个单一模型的综合结果做出最后的决策。目前子空间方法和集成学习方法在国内外已经有大量研究［7，8］。 3. 2 数据量问题 大数据分析的另一科学问题是当图 1 的对象—属性矩阵的行数超过千万或亿的数量级后，其整个矩阵 的数据量将达到上百个 GB 至 TB 级，这样大的输入数据远远超出大多数服务器的内存，更不用说在单一服 务器上用复杂的迭代或递归数据挖掘算法进行建模和挖掘。因此，现有的数据挖掘软件和大多数传统的分 类和聚类等算法无法处理这个规模的数据。 解决 TB 级规模输入数据建模问题的一个可行方法是将对象—属性矩阵切分成大量的子矩阵，然后将 子矩阵文件分布到多个服务器节点上。同时对数据挖掘算法作并行分布式改造，使每次迭代运算分两步进 行，第一步是在每个计算节点上对子矩阵进行运算，取得子矩阵的局部结果; 第二步是将所有子矩阵的局部 结果集中运算，计算出整个对象—属性矩阵的全局结果，然后进入下一次迭代直到得出最后模型。Hadoop 平台上的 Map － reduce 计算模型通常用来实现上述分布式算法。 对复杂的数据挖掘算法进行分布式改造需要解决一个算法上的数学问题，即证明这种分解计算再综合 的两步式方法得出的结果要同直接对整个矩阵一步运算的结果等价。如果采用近似计算方法，需要证明两 步式方法得出结果的偏差在可控范围内。在 Hadoop 上实现分布式数据挖掘算法的一个技术问题是 Map － reduce 计算模型本身的局限性。Map － reduce 最初是为词频统计设计的，适合数据一次性处理，而多数数据 挖掘算法具有迭代、递归、层次等特性，用 Map － reduce 实现分布式算法经常产生很多额外开销，极大影响运 算效率。因此，设计适合大数据分析与挖掘分布式算法的新型计算模型也是一个重要的科学问题。 当前，许多常用的机器学习和数据挖掘算法都有了 Map － reduce 分布式版本，最流行的是 Apache 的 Mahout 开源系统［9］，但其算法的执行效率还远远达不到 TB 级大数据的水平［10，11］。 3. 3 大数据分析方法 大数据分析与挖掘的另一科学问题是分析方法和分析手段落后。当前普遍采用的数据挖掘建模方法 是样本– ＞ 建模– ＞ 测试三步骤方法，建模的过程由算法自动完成，模型建好后，用户对模型进行测试，结 果不满意，改变训练数据和算法参数，由算法自动产生新的模型。这种方法不适用于大数据分析，因为数据 大，算法建模的时间较长，多次重复建模步骤使计算成本和能耗加大。因此，必须研究新的大数据分析方法。 提高大数据分析与挖掘的效率和效果的方法之一是改变建模的全自动过程，实现大数据建模人机交 互，让专业分析人员的领域知识融入到建模过程中，通过人机交互获得优化模型。实现大数据建模过程人 机交互需要解决两大关键技术，交互式数据挖掘算法和数据及模型可视化。交互式算法在建模过程中生成 大量中间结果，用可视化技术展现给分析人员，分析人员可以通过观察分析建模的阶段性结果，调整算法参 数或输入数据，指引交互式算法向优化模型的方向计算。 大数据可视分析已经成为图形学和可视化领域的研究热点，目前大规模超高维数据可视化方法和技术 还不多，数据挖掘模型和知识可视化研究也在起始阶段，可用的成果很少。 4 海云数据系统 海云数据系统是中国科学院“面向感知中国的新一代信息技术”战略性先导科技专项“海云数据系统关 键技术研究与系统研制”课题研究的重要内容。其目标是研制面向海量数据存储与挖掘的互联网服务平 台，为“海云创新实验环境”用户提供大规模数据存储、处理、挖掘与可视化分析服务，创新数据挖掘互联网 服务模式。 23
网络新媒体技术 2012年 4.1系统架构 海云数据系统的设计理念是以 统至 分布式运算平百 区域性智能数据中心和高速互联网 为基础设施,以互联网服务体系为 架构,以大规模海量数据存储、处 专业用户 路由防火墙 理、挖掘和可视化分析等关键技术 为支撑,通过多样化智能终端及互 联网为用户提供数据存储、管理及 运算集群 分析服务。 了“面 海云数据系统的拓扑架构如图 平台服务器 所示。区域智能数据中心提供基 于云计算的大规模数据存储及数据 挖掘平台,通过平台服务器对外接 口提供数据存储、分析与挖掘服务。 用户使用Web浏览器或智能终端移动设备 区域智能数据中心 数据存储集群 应用程序提出数据存储和分析的服 务请求,经Web服务器通过互联网 图2海云数据系统拓扑示意图 将服务请求发送给数据中心平台服务器,平台服务器对服务请求进行解析,发送给工作流引擎调度执行,执 行结果通过互联网发送给用户终端。 4.2关键技术 为支持海云数据系统的研制,课题组己经搭建了由110台高性能服务器组成,具有500TB存储能力和 840CPU核运算能力的云存储系统和云计算平台。海云数据系统的研制主 要包括下面6个关键技术 (1)云存储系统。为海云数据系统的大数据分析提供海量数据存储与管理服务; (2)云计算平台。为大规模海量数据处理、挖掘与分析提供高性能计算服务 (3)海量数据挖掘算法库。为海量复杂数据处理、挖掘与分析提供髙可扩展算法 (4)可视化交互分析引擎。启发式、人机交互、可视化数据挖掘新技术,提供海量数据挖掘高度人机交互功能 (5)工作流引擎。为用户创建海量数据处理、分析流程提供图形化流程设计工具,自动执行用户创建的 数据处理分析流程,提供资源调度及优化服务 (6) Open APl。提供数据挖掘平台与第三方应用系统的扩展接口 4.3算法创新 分类与聚类是数据分析与挖掘的两大主要任务,大数据的超高维问题对现有的分类和聚类技术造成很 大的挑战,很多经典算法,如决策树、k- means等,已经不能满足应用需求。针对超高维数据的分类和聚类 问题,课题组对著名的随机森林分类算法和属性加权的k- means子空间聚类算法作了改进,取得了很好的 效果,新算法对超高维数据的分类和聚类精度有了显著提高。 4.4可扩展分类算法 针对大数据建立分类模型的挑战,课题组采用Map- reduce编程模型对随机森林算法作了分布式改进, 建立随机森林模型的核心是生成大量决策树模型,经典的决策树建模方法采用深度优先的递归式算法,如 图3所示。但是,Map- reduce编程模型并不支持递归机制,决策树递归算法只能在Map内部操作实现,致 使运行Map的单个节点内存消耗随着决策树深度不断递增而增加,内存溢出风险高,不适合大数据。目前 流行的基于Map- reduce的开源项目 Mahout采用这种方式实现随机森林算法。针对这一问题,课题组采用 了广度优先的建树机制,如图4所示。这种方法的优点是构建的决策树在节点分裂后,生成更多的并行 的子任务,实现高效的并行,避免了内存过快消耗,具体执行流程见图5 o1994-2013CHinaAcademicJournalElectronicpUblishingHouse.Allrightsreservedhttp://www.cnki.net
网 络 新 媒 体 技 术 2012 年 4. 1 系统架构 图 2 海云数据系统拓扑示意图 海云数据系统的设计理念是以 区域性智能数据中心和高速互联网 为基础设施，以互联网服务体系为 架构，以大规模海量数据存 储、处 理、挖掘和可视化分析等关键技术 为支撑，通过多样化智能终端及互 联网为用户提供数据存储、管理及 分析服务。 海云数据系统的拓扑架构如图 2 所示。区域智能数据中心提供基 于云计算的大规模数据存储及数据 挖掘平台，通过平台服务器对外接 口提供数据存储、分析与挖掘服务。 用户使用 Web 浏览器或智能终端 应用程序提出数据存储和分析的服 务请求，经 Web 服务器通过互联网 将服务请求发送给数据中心平台服务器，平台服务器对服务请求进行解析，发送给工作流引擎调度执行，执 行结果通过互联网发送给用户终端。 4. 2 关键技术 为支持海云数据系统的研制，课题组已经搭建了由 110 台高性能服务器组成，具有 500TB 存储能力和 840CPU 核运算能力的云存储系统和云计算平台。海云数据系统的研制主 要包括下面 6 个关键技术: ( 1) 云存储系统。为海云数据系统的大数据分析提供海量数据存储与管理服务; ( 2) 云计算平台。为大规模海量数据处理、挖掘与分析提供高性能计算服务; ( 3) 海量数据挖掘算法库。为海量复杂数据处理、挖掘与分析提供高可扩展算法; ( 4) 可视化交互分析引擎。启发式、人机交互、可视化数据挖掘新技术，提供海量数据挖掘高度人机交互功能; ( 5) 工作流引擎。为用户创建海量数据处理、分析流程提供图形化流程设计工具，自动执行用户创建的 数据处理分析流程，提供资源调度及优化服务; ( 6) Open API。提供数据挖掘平台与第三方应用系统的扩展接口。 4. 3 算法创新 分类与聚类是数据分析与挖掘的两大主要任务，大数据的超高维问题对现有的分类和聚类技术造成很 大的挑战，很多经典算法，如决策树、k － means 等，已经不能满足应用需求。针对超高维数据的分类和聚类 问题，课题组对著名的随机森林分类算法和属性加权的 k － means 子空间聚类算法作了改进，取得了很好的 效果，新算法对超高维数据的分类和聚类精度有了显著提高。 4. 4 可扩展分类算法 针对大数据建立分类模型的挑战，课题组采用 Map － reduce 编程模型对随机森林算法作了分布式改进。 建立随机森林模型的核心是生成大量决策树模型，经典的决策树建模方法采用深度优先的递归式算法，如 图 3 所示。但是，Map － reduce 编程模型并不支持递归机制，决策树递归算法只能在 Map 内部操作实现，致 使运行 Map 的单个节点内存消耗随着决策树深度不断递增而增加，内存溢出风险高，不适合大数据。目前 流行的基于 Map － reduce 的开源项目 Mahout 采用这种方式实现随机森林算法。针对这一问题，课题组采用 了广度优先的建树机制［16］，如图 4 所示。这种方法的优点是构建的决策树在节点分裂后，生成更多的并行 的子任务，实现高效的并行，避免了内存过快消耗，具体执行流程见图 5。 24
6期 黄哲学等:面向大数据的海云数据系统关键技术研究 采用广度优先决策树生成方法实现的分布式随机森林算法,课题组在30台服务器的云平台上实现了 100分钟内对100个属性、1000万个纪录的输入矩阵,规模达到110GB的数据建立随机森林模型的能力。 Nodel Leafl Leaf)(Leaf 2 Leaf2 Leaf2 Leaf3 图3深度优先构建随机森林决策树 图4广度优先构建随机森林决策树 O00000Q0 Time 图5随机森林的层次构造流程 4.5交互式可视化 为探索交互式可视化数据挖掘新方法,课题组针 对随机森林建模设计开发了随机森林交互视可视化分 析平台。给定一个输入训练数据和一组随机森林算法 参数该平台启动随机在林法生成最初随机森林模, 型,然后计算树与树之间的相互关系,确定树的空间坐 标并用模拟树的形式在三维空间展示,如图6所示 随机森林模型精度和每棵树的精度在右边的窗口 用数字展示。用户可以根据每棵树的精度,用鼠标选 择其中任何一棵树,并将选择的树在新的窗口显示,如 6随机森林交互式可视化分析平 图7所示。在所选择的树中,顶部端点的球表示决策树叶结点对象的数量,对象越多,球越大。球的颜色表 示叶结点的主要类别,深蓝色表示NO类,浅蓝色表示YES类。根据决策树的特点,用户可以通过鼠标对树 进行如下操作:剪切树叶,使叶结点归并到更低的节点,相当于树剪枝操作;如果树的精度很低,用户可以将 树砍掉,重新启动决策树算法,用不同的输入参数生成新的树,并更新随机森林模型,重新计算树与树的关 系,产生新的随机森林可视化模型;用户也可以将树砍掉,重新生成训练数据,调用决策树算法生成新的决 策树。通过对决策树的交互操作,用户可以逐渐逼近最优的随机森林模型,充分利用交互式可视化的分析 功能,提高大数据挖掘的建模效率。 5结束语 大数据已经成为行业共识,大数据中的潜在价值已经引起了产业界和学术界的高度关注,并将对国家 o1994-2013CHinaAcademicJournalElectronicpUblishingHouse.Allrightsreservedhttp://www.cnki.net
6 期 黄哲学 等: 面向大数据的海云数据系统关键技术研究 采用广度优先决策树生成方法实现的分布式随机森林算法，课题组在 30 台服务器的云平台上实现了 100 分钟内对 100 个属性、1000 万个纪录的输入矩阵，规模达到 110 GB 的数据建立随机森林模型的能力。 图 3 深度优先构建随机森林决策树 图 4 广度优先构建随机森林决策树 图 5 随机森林的层次构造流程 图 6 随机森林交互式可视化分析平台 4. 5 交互式可视化 为探索交互式可视化数据挖掘新方法，课题组针 对随机森林建模设计开发了随机森林交互视可视化分 析平台。给定一个输入训练数据和一组随机森林算法 参数，该平台启动随机森林算法生成最初随机森林模 型，然后计算树与树之间的相互关系，确定树的空间坐 标并用模拟树的形式在三维空间展示，如图 6 所示。 随机森林模型精度和每棵树的精度在右边的窗口 用数字展示。用户可以根据每棵树的精度，用鼠标选 择其中任何一棵树，并将选择的树在新的窗口显示，如 图 7 所示。在所选择的树中，顶部端点的球表示决策树叶结点对象的数量，对象越多，球越大。球的颜色表 示叶结点的主要类别，深蓝色表示 NO 类，浅蓝色表示 YES 类。根据决策树的特点，用户可以通过鼠标对树 进行如下操作: 剪切树叶，使叶结点归并到更低的节点，相当于树剪枝操作; 如果树的精度很低，用户可以将 树砍掉，重新启动决策树算法，用不同的输入参数生成新的树，并更新随机森林模型，重新计算树与树的关 系，产生新的随机森林可视化模型; 用户也可以将树砍掉，重新生成训练数据，调用决策树算法生成新的决 策树。通过对决策树的交互操作，用户可以逐渐逼近最优的随机森林模型，充分利用交互式可视化的分析 功能，提高大数据挖掘的建模效率。 5 结束语 大数据已经成为行业共识，大数据中的潜在价值已经引起了产业界和学术界的高度关注，并将对国家 25
网络新媒体技术 2012年 的发展战略产生深远的影响。本文介绍了大数据的一些基本概念、特征和面 YES 临的科学问题,总结了中国科学院战略性先导科技专项课题“海云数据系统 关键技术研究与系统研制”的一些前期工作,对未来的研究方向进行了展望。 YES 参考文献 u] Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. The Google file system [C]//Pro- ceedings of the 19th ACM Symposium on Operating Systems Principles, ACM, Bolton Landing, NY, 2003, 20-43 2] Jeffrey Dean, Sanjay Ghemawat. MapReduce: simplified data processing on large clusters C]//OSDI04: Sixth Symposium on Operating System Design and Implementation,San Francisco, CA, 2004, 137-150 3] Clifford Lynch. Big data: How do your data grow? D]. Nature, 2008, 455(7209): 28-29 4]http://www.sciencemag,org/site/special/data/ 5] James Manyika, Michael Chui, Brad Brown, etc. Big data: The next frontier for innova- ion,competition, and productivity. 2011 6]http://www-01.ibmcom/software/data/bigdata/. J Joshua Zhexue Huang, Michael K. Ng, Hongqiang Rong, etc. Automated variable weigh- ting in k- means type clustering D. IEEE Transactions on pattern analysis and machine图7随机森林模型可视化 Intelligence,2005,27(5):657-668 8] Liping Jing, Michael K. Ng, Joshua Zhexue Huang. An entropy weighting k-means algorithm for subspace clustering of high dimensional sparse data []. IEEE Transactions Knowledge and Data Engineering, 2007, 19(8):1026-1041 9]http://lucene.apacheorg/mahout/ o]王珊,王会举,覃雄派,周烜.架构大数据:挑战、现状与展望.计算机学报,2011,34(10):1741-1752 ]覃雄派,王会举,杜小勇,王珊.大数据分析- RDBMS与 MapReduce的竞争与共生D].软件学报,2012,23(1):32 [2 Leo Breiman. Random forests [). Machine learning, 2001, 45(1): 5-32 03] Baoxun Xu, Joshua Zhexue Huang, Graham Willams, etc. Classifying very high-dimensional data with random forests built from small subspaces [], International Journal of Data Warehouse and Mining, 2012,8(2): 45-62 [14] Xiaojun Chen, Xiaofei Xu, Yunming Ye, etc. TW-k-means: automated two-level variable weighting clustering algorithm for multi-viewdataD].ieeetrAnsactionsonKnowledgeandDataEngineering,http://doi.ieeecomputersociety.org/10.1109 TKDE2011.262 [5] Xiaojun Chen, Yunming Ye, Xiaofei Xu etc. A feature group weighting method for subspace clustering of high-dimensional data D]. Pattern Recognition, 2012, 45(1):434-446 16] Bingguo Li, Xiaojun Chen, Mark Junjie Li, etc. Scalable random forests for massive data [C. PAKDD,2012. 作者简介 黄晢学,男,博土,中科院深圳先进技术硏究院研究员,主要从事数据挖掘与机器学习方面的硏究 曹付元,男,博士,中科院深圳先进技术研究院博士后,主要从事数据挖掘与机器学习方面的研究。 李俊杰,男,博土,中科院深圳先进技术硏究院助理硏究员,主要从事数据挖掘与机器学习方面的硏究。 陈小军,男,博土,中科院深圳先进技术研究院助理研究员,主要从事数据挖掘与机器学习方面的硏究 o1994-2013CHinaAcademicJournalElectronicpUblishingHouse.Allrightsreservedhttp://www.cnki.net
网 络 新 媒 体 技 术 2012 年 图 7 随机森林模型可视化 的发展战略产生深远的影响。本文介绍了大数据的一些基本概念、特征和面 临的科学问题，总结了中国科学院战略性先导科技专项课题“海云数据系统 关键技术研究与系统研制”的一些前期工作，对未来的研究方向进行了展望。 参 考 文 献 ［1］Sanjay Ghemawat，Howard Gobioff，Shun － Tak Leung. The Google file system［C］/ /Proceedings of the 19th ACM Symposium on Operating Systems Principles，ACM，Bolton Landing，NY，2003，20 － 43 ［2］Jeffrey Dean，Sanjay Ghemawat. MapReduce: simplified data processing on large clusters ［C］/ /OSDI＇04: Sixth Symposium on Operating System Design and Implementation，San Francisco，CA，2004，137 － 150 ［3］Clifford Lynch. Big data: How do your data grow? ［J］. Nature，2008，455( 7209) : 28 －29 ［4］http: / /www. sciencemag. org /site /special /data /. ［5］James Manyika，Michael Chui，Brad Brown，etc. Big data: The next frontier for innovation，competition，and productivity. 2011. ［6］http: / /www － 01. ibm. com/software /data /bigdata /. ［7］Joshua Zhexue Huang，Michael K. Ng，Hongqiang Rong，etc. Automated variable weighting in k － means type clustering［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27( 5) : 657 － 668 ［8］Liping Jing，Michael K. Ng，Joshua Zhexue Huang. An entropy weighting k － means algorithm for subspace clustering of high － dimensional sparse data［J］. IEEE Transactions Knowledge and Data Engineering，2007，19( 8) : 1026 － 1041 ［9］http: / /lucene. apache. org /mahout /. ［10］王珊，王会举，覃雄派，周烜 . 架构大数据: 挑战、现状与展望［J］. 计算机学报，2011，34( 10) : 1741 － 1752 ［11］覃雄派，王会举，杜小勇，王珊 . 大数据分析 － RDBMS 与 MapReduce 的竞争与共生［J］. 软件学报，2012，23( 1) : 32 － 45 ［12］Leo Breiman. Random forests［J］. Machine learning，2001，45( 1) : 5 – 32 ［13］Baoxun Xu，Joshua Zhexue Huang，Graham Willams，etc. Classifying very high － dimensional data with random forests built from small subspaces［J］，International Journal of Data Warehouse and Mining，2012，8( 2) : 45 － 62 ［14］Xiaojun Chen，Xiaofei Xu，Yunming Ye，etc. TW － k － means: automated two － level variable weighting clustering algorithm for multi － view data［J］. IEEE Transactions on Knowledge and Data Engineering，http: / /doi. ieeecomputersociety. org /10. 1109 / TKDE. 2011. 262 ［15］Xiaojun Chen，Yunming Ye，Xiaofei Xu etc. A feature group weighting method for subspace clustering of high － dimensional data ［J］. Pattern Recognition，2012，45( 1) : 434 － 446 ［16］Bingguo Li，Xiaojun Chen，Mark Junjie Li，etc. Scalable random forests for massive data［C］. PAKDD，2012. 作者简介 黄哲学，男，博士，中科院深圳先进技术研究院研究员，主要从事数据挖掘与机器学习方面的研究。 曹付元，男，博士，中科院深圳先进技术研究院博士后，主要从事数据挖掘与机器学习方面的研究。 李俊杰，男，博士，中科院深圳先进技术研究院助理研究员，主要从事数据挖掘与机器学习方面的研究。 陈小军，男，博士，中科院深圳先进技术研究院助理研究员，主要从事数据挖掘与机器学习方面的研究。 26
