大数据的挑战性问题及关键技术65

大数据的挑战性问题及关键技术何清中国科学院计算技术研究所2014/5/26中国科学院计算技术研究所1大数据挑战性问题大数据挖掘算法大数据挖掘云服务平台Web大数据挖掘平台典型案例展望内容提要Outlines2014/5/26中国科学院计算技术研究所2何谓大数据维基百科:大数据BigData是指大小超出了常用的软件工具在运行时间内可以承受的收集，管理和处理数据能力的数据集大数据是目前存储模式与能力、计算模式与能力不能满足存储与处理现有数据集规模产生的相对概念何清——中国科学院计算技术研究所32014/5/26大数据悖论1条数据=小数据2条数据=小数据3条数据=小数据………n条数据=小数据n+1条数据=小数据有限条数据是小数据真值为1真值为(1−E)真值为(1−E)2………真值为(1−E)𝑛−1真值为(1−E)𝑛真值随条数增加趋于0数学上看大数据在数学上来看，计算机中存在不断变大的数据集，不存在绝对的大数据计算机中的所有数据集都是有限集合计算机中不存在无限集合计算机中的大数据集不具有无限可分割性没有比一个比特更小的数据单元计算机中的所有数据表达都有精度的限制这种限制导致了算法精度的受限计算机无法对无理数进行运算得到精确结果2014/5/26何清——中国科学院计算技术研究所5大数据的特征稠密与稀疏共存：局部稠密与全局稀疏冗余与缺失并在：大量冗余与局部缺失显式与隐式均有：大量显式与丰富隐式静态与动态忽现：动态演进与静态关联多元与异质共处：多元多变与异质异性量大与可用矛盾：量大低值与可用稀少何清——中国科学院计算技术研究所62014/5/26目前大数据的外延大数据规模大小是一个不断演化的指标当前任务处理的单一的数据集从数十TB到十几PB级的数据规模TB«PB«EB«ZB处理大数据的可等待的合理时间依赖任务的目标地震数据预测要求在几分钟内才有效气象数据应该在小时级别失联飞机数据处理要在7天之内数据挖掘一般要求在12小时内何清——中国科学院计算技术研究所72014/5/26大数据带来的数学问题大数据采样如何把大数据变小如何找到与算法相适应的极小样本集采样对算法误差的影响大数据如何表示表示决定存储表示影响算法效率大数据不一致问题导致算法失效和无解如何消解不一致大数据中的超高维问题超高维导致数据稀疏算法复杂度增加大数据中的不确定维问题多维度数据并存按任务定维难大数据中的不适定性问题高维导致问题的解太多难以抉择2014/5/26何清——中国科学院计算技术研究所8大数据对科学规范的挑战大数据带来了新的科研范式大数据如何应用于开放的研究如何重现大数据研究结果大数据研究结果可信吗大数据带来的社会问题谁有权收集大数据谁有权拥有大数据大数据生产如何规划大数据污染如何控制大数据销毁如何抉择大数据如何传给后代何清——中国科学院计算技术研究所102014/5/26大数据带来的技术挑战描述与存储的挑战高效查询——大海捞针分析与理解的挑战理解大数据——盲人摸象挖掘与预测的挑战增加样本容易，降低算法复杂度难并非所有的算法具有高度的并行性并行不能降低算法复杂度大数据管理的挑战可扩展的数据管理弹性有效地利用现有资源减少管理操作的成本对于大型应用程序的数据管理支持大单租户系统大型多租户数据库大量的应用程序每个程序占用很小的数据空间支持更新密集型工作负载支持大型多用户系统大数据管理的挑战传递的格式和速度、规模和复杂性需要管理内存DBMS分析已成为数据仓库的主要驱动应用,外部和内部分别使用MapReduce和DBMS按需整合来自多个源信息的逻辑数据仓库代替单一的数据仓库模式大数据挖掘挑战面临挑战1.大数据集的挑战I.缺少大数据复杂度冗余度的度量方法II.缺少确保近似算法精度分析方法III.缺少根据分布知识对大数据进行抽样的方法2.数据复杂性的挑战I.超高维、稀疏、多模态3.数据动态增长的挑战1.研究分布式并行计算环境下的大数据大数据分析的基本策略I.与数据分布相联系的分治策略II.与算法机理相结合的并行策略2.研究复杂度降精度可控的新的大数据分析算法I.大数据分类、聚类、关联分析、异常发现等3.大数据大数据分析平台研发研究内容大数据挑战性问题大数据挖掘算法大数据挖掘云服务平台Web大数据挖掘平台典型案例展望内容提要Outlines2014/5/26中国科学院计算技术研究所15大数据挖掘需要什么样的算法能反映大数据分布的抽样方法解剖麻雀基于大数据分布的算法庖丁解牛追求高效并行的数据挖掘的算法曹冲称象反映全量特征的数据挖掘的算法治大国如烹小鲜如何把大数据变小大数据重采样基于分布采样找极小样本集极小样本集与算法任务相对应极小样本集才能挖掘出全量特征极小样本集才能使用复杂精准的挖掘方法和模型数据变小——覆盖型分类算法规则覆盖样本决策树算法(QuinlanJR)AQ系列算法(MichalskiRS)空间划分覆盖样本基于球邻域的空间划分法(张铃教授、张钹院士)仿生模式识别BPR（王守觉院士)视觉分类方法VCA(徐宗本院士)分类超曲面算法HSC(何清)18空间覆盖算法－基于球邻域的空间划分投影函数19Pw分类超平面的计算样本点两两之间距离所构成的距离空间上的覆盖的计算n维训练样本(归一化)n+1维单位超半球面空间覆盖算法－仿生模式识别20折线——BP大圆——RBF椭圆——BPR空间覆盖算法－视觉分类方法VisualClassificationAlgorithm(VCA)把数据看作一幅图像，核心是基于尺度空间理论，选择合适的尺度使得同类样本区域融合在一起21基于超曲面的分类方法分类判别定理根据从样本点所引射线与封闭曲线相交点数的奇偶判别样本点在封闭曲线的内部或外部22分类超曲面算法HSC设训练样本所在空间为一封闭维方体区域将此区域按照一定细分规则划分成若干小区域，使每个小区域只包含同一类样本点，并用样本点的类别标定该区域合并相邻同类区域边界，获得若干超平面片封闭组成的分类超曲面输入新样本点，根据分类判别定理判断样本点所在的类别基于超曲面的分类方法特点通过特征区域细化直接解决非线性分类问题不需要考虑使用何种核函数，不需要升维变换通用可操作的分类超曲面构造法基于分类超曲面的方法通过区域合并计算获得分类超曲面对空间进行划分独特、简便、易行的分类判别方法基于分类超曲面的方法是基于Jordan定理的分类判断算法，使得基于非凸的超曲面的分类判别变得简便、易行24基于超曲面的分类法特点有简便的高维转化为低维数据的方法低维情况下算法复杂性低、分类效率高适合多类分类，SVM则不然与SVM适用小样本不同，HSC更适合大样本推广能力较好、准确率高适合分布复杂的样本分类对同类样本在有限连通区域连续分布的分类问题有效抗噪性占用存储和计算资源少25极小覆盖子集定义(覆盖型分类算法的极小覆盖子集)对特定的训练样本集，若其子样本集训练后得到的分类模型与与原样本集训练后得到的分类模型相同，则称子样本集是原样本集的一个覆盖在一个样本集的所有覆盖中，包含样本个数最少的覆盖称为样本集的极小覆盖子集26极小覆盖子集计算极小覆盖子集的基本步骤用一个方形区域覆盖所有样本点将该区域划分成一系列小区域(单元格)，直到每个小区域内包含的样本点都属于同一类别将落在同一小区域内的样本点中选择且仅选择一个样本构成极小覆盖子集27大数据重采样重采样遵循的原则多次重采是否意味着全采什么样的算法适合重采样后的处理哪些算法只能依赖全采重采样对算法收敛性的影响何清——中国科学院计算技术研究所282014/5/26采样受限于极小覆盖子集全样本空间必然包含极小覆盖子集任意一个数据集未必包含完整的极小覆盖子集大数据环境下，极小覆盖子集中的样本更多地包含在大数据中较多的数据可以战胜较好的算法再多的数据亦不会超过极小覆盖子集的代表性再好的提升手段亦不会超过极小覆盖子集确定的精度大数据挑战性问题大数据挖掘算法大数据挖掘云服务平台Web大数据挖掘平台典型案例展望内容提要Outlines2014/5/26中国科学院计算技术研究所30基于云计算的大数据挖掘平台——PDMinerPDMiner(1.0)于2008年开发完成Mahout(0.5)于2011年3月27日发布Mahout(0.8)于2013年7月份发布Mahout(0.9)于2014年2月份发布PDMinerVS.Mhout2014/5/26中国科学院计算技术研究所31算法类别PDMinerMahout预处理225分类1210聚类69关联挖掘31主题分析21代表性第三方评价2014/5/26中国科学院计算技术研究所32PDMiner开发完成时比Mahout项目启动早半年，比Mahout发布第一版早三年COMS大数据挖掘云服务模式2014/5/26中国科学院计算技术研究所33大数据挑战性问题大数据挖掘算法大数据挖掘云服务平台Web大数据挖掘平台典型案例展望内容提要Outlines2014/5/26中国科学院计算技术研究所34基于云计算的WEB挖掘系统数据采集Spider信息采集子系统文本预处理与建模子系统文本挖掘子系统用户接口子系统全文检索语义分析文本分类文本聚类文本关联摘要提取情感分析主题发现Internet用户云平台网页解析中文分词词频统计与建模特征提取索引建立HDFS/Hbase文本文本文本CWMS体系结构图2014/5/26中国科学院计算技术研究所35摘要算法数据源：通信厂商网页2014/5/26中国科学院计算技术研究所36基于云计算的WEB挖掘系统•基于云计算的WEB挖掘系统•功能：实现从Web数据采集、解析、建模到挖掘分析的全套流程•挖掘任务：文本分类、聚类、关联分析、语义分析、情感分析、主题发现、文档摘要以及实体词识别8大功能模块数据采集算法加速比文本主题发现算法加速比文本摘要算法加速比文本情感分析算法加速比2014/5/26中国科学院计算技术研究所37提供了完全部署在“云”上互联网文本大数据智能分析与挖掘的关键技术，支持获取大数据、处理大数据、分析大数据到结果展示的完整流程系统的数据采集子系统实现了基于Hadoop的并行网页采集工具，提供多种模式的采集方式，该项技术已经申请专利针对文本数据高维高噪声的特点，采用稀疏向量的存储模式和建模方式已于2012年底获得软件著作权2014/5/26中国科学院计算技术研究所38基于云计算的Web挖掘系统Web挖掘云服务平台——WMCS•部署在中科院计算技术研究所MLDM团队服务器，访问网址：•前台人性化的Web客户端，后台Haoop+HDFS驱动，稳定的云数据处理服务，良好的用户体验。数据管理模块数据上传、管理任务管理模块创建、管理数据挖掘任务结果展示模块返回挖掘结果给用户特征选择算法模块数据清洗、转换、加载等数据挖掘子系统聚类算法分类算法关联规则挖掘Workflow应用数据，存储在HDFS上工作流子系统后台挖掘系统前台Web部分用户管理模块安全控制机制隐私保护机制数据有效性检验Web工作流引擎包含多个job的文本挖掘任务单个文本特征提取和过滤任务2014/5/26中国科学院计算技术研究所40Web挖掘云服务平台——WMCS•文本数据获取——实现了基于Hadoop的并行网页采集工具，提供多种模式的采集方式，该项技术已经申请专利•提供从数据采集、建模到挖掘的一站式服务•提供了多种并行Web数据转换规则和并行Web数据挖掘算法服务•提供Web文档主题发现一键挖掘，集成Web网页爬取、解析、分