大数据研究的若干科学问题及初步研究结果课件

1、 大数据研究的若干科学问题 及初步研究结果 (西安交通大学)第1页，共49页。内容提要关于大数据的认识大数据分析与处理中的科学问题若干进展第2页，共49页。关于大数据的认识（数据）(文本、图像、地理数据、基因与蛋白质数据、视频、程序、有限规则集等) 数据: 信息的载体;计算机处理的基本对象。 数据的多样性和高复杂性第3页，共49页。关于大数据的认识 (什么是大数据?)大数据是指无法在容许的时间内用常规的软件工具对其内容进行抓取、管理和处理的数据集合，大数据规模的标准是持续变化的，当前泛指单一数据集的大小在十几TB和PB之间。（维基百科）ZB（1021）,EB（1018）,PB（1015）,TB

2、（1012）,GB（109）,MB（106）第4页，共49页。关于大数据的认识（主要来源）科学研究环保监视远程医疗互联网、物联网、社会网安全监控大型企业信息存储第5页，共49页。大数据：不能集中存储、难以在可接受时间内分析处理、而数据整体呈现高价值的海量复杂数据集。 体量大不能用现有的物理设备集中存储，开放，高速可扩展。复杂性高多源、异构、相关、非结构化、不一定可靠、不一致性。价值丰富个体或部分数据呈现低价值，而数据整体呈现高价值。关于大数据认识（什么是大数据？）第6页，共49页。关于大数据的认识（时代背景）被多数发达国家列为未来国家战略优先发展领域2011年，奥巴马在“美国创新战略”中发布了

3、大数据研究和发展倡议欧盟将信息技术作为欧洲2020战略的优先发展领域之一，而大数据研究为其中非常重要的一个方向法国、德国、英国、日本、韩国和俄罗斯等重要国家都将信息产业列为国家未来战略优先发展领域之一引起国际社会广泛关注麦肯锡2011年5月发布下一个前沿：创新、竞争和生产力报告，认为大数据将引发新一轮的生产力增长与创新世界经济论坛2012年发布Big Data，Big Impact报告，阐述大数据为世界带来的新机遇联合国在2012年5月公布了大数据促发展：挑战与机遇白皮书IDC 在2012年6月发布中国互联网市场洞见：互联网大数据技术创新研究报告，指出大数据将引领中国互联网行业新一轮技术浪潮第

4、7页，共49页。大数据价值：数据整体蕴含事件的相关性、发展的规律性与趋势，揭示这样的相关性、规律性与趋势为科学探索、解决广泛的社会发展与国家安全问题提供了依据与可能（特别是高的社会价值和解决社会学问题的方法论）。 科学研究高能物理天文生命科学机械设计经济与社会推动物联网、云计算产业升级大数据商业模式 (vs工业化模式)企业核心竞争力 (数据规模、 活性与解释力)影响社会文化与组织远程医疗.国家治理数据资产 (国家竞争力)数据主权 (同边、海、空防)国防安全监控网络监控.关于大数据的认识（价值与意义）第8页，共49页。大数据关注程度：30%企业已开始大数据工作，34%的企业已计划两年内开始。其中

5、50%数企业并不知道如何从数据中获取价值。 一一2013年大数据普及程度及背后的炒作（Gartner）关于大数据的认识（值得热吗？）为什么要关注呢，能做什么？ 高附加值在哪里？数据的价值得到广泛认可数据挖掘成为普世的高新技术值得热，但不可以一哄而起!第9页，共49页。物理、材料、电子等大数据研究催生大数据产业 (从数据到价值的产业链）数据获取与管理数据查存与处理数据分析与理解数据工程与应用数学与统计学大数据研究:高度的多学科综合研究大数据产业管理（产业链管理、商业模式、公共政策）计算机科学各行各业数据管理数据质量数据标准数据共享数据隐私存储查询存储模式查询算法实时处理软硬件数据挖掘数据表示数据

6、建模高效计算统计推断数据工程第10页，共49页。超高维问题重采样问题计算理论问题分布实时计算问题非结构化问题可视分析问题大数据分析与处理中的科学问题第11页，共49页。大数据高维问题：“决策要素（P）伴随大数据(n)呈现更高量级”所引起的解的不确定性与经典统计推断失效问题。 经典统计学：np; 高维问题：pn; 大数据高维问题：p=O(exp(n), n -. 解 渐近正态 大数据研究中的科学问题（超高维问题）线性模型:数据：矩阵形式：第12页，共49页。 基本科学问题 如何补足信息使问题可解?非iid 数据统计学；低维几何的高维泛化(积分几何)； 超高维数据的低维特征(多维特征提取等)；热点

7、研究：稀疏建模（压缩感知、低秩矩阵分解、基于稀疏性的特征提取、数据降维、压缩学习等）大数据研究中的科学问题（超高维问题）第13页，共49页。大数据的重采样：如何进行合适的subsampling，将大数据随机划分成若干小数据集，而根据小数据集所获得的统计推断，进行聚合处理后能反应原大数据集的规律与形态 (分布式算法)。热点问题：The Big Data Bootstrap. Kleiner et.al. 2012 ICML 大数据研究中的科学问题（重采样问题）X1X2X3Xn随机机制D1DkDm.聚合机制第14页，共49页。基本科学问题 如何重采样以反映整体数据特征? 分布式算法可行性吗? 基于

8、试验设计的重采样； 更加有效的聚合原理; Subsampling的原则（相似性，传 递性,) 大数据研究中的科学问题（重采样问题）未知总体实验设计大数据就是“总体”如何实验设计体现总体数据相似性D1D2D3传递性第15页，共49页。大数据研究中的科学问题（计算理论问题）计算理论：大数据背景下有关一个计算问题是否可解与能解的理论。传统上，一个可解性问题是指能在有限步内在图灵机上求解的问题；一个问题能解是指在可接受的存储空间与时间代价下，该问题可以求解。M.R. Garey, D.S. Johnson, Computers and Intractability: A guide to the th

9、eory of NP-completeness.经典的计算复杂性理论（可解性理论）：计算时间（时间复杂性），占用内存空间（空间复杂性）第16页，共49页。大数据研究中的科学问题（计算理论问题） 基本科学问题 大数据问题的可解性理论；时间复杂性理论（难和易如何定义？）对具体类大数据的复杂性理论: 流数据（容易=处理速度快于数据更新速度）分布式数据（容易=交互速度快于数据处理速度）D1D2D3交互数据处理第17页，共49页。分布式实时计算:是大数据处理的计算模式，它包含多处理器自主计算、相互通信，为完成统一任务而并行工作的实时计算过程。主要挑战来自数据的分布性与计算的实时性要求。大数据研究中的科学

10、问题（分布实时计算）HDFSHBaseMapReduceHadoop第18页，共49页。 基本科学问题 与分布式实时计算相适应的存储 与查询 (理论、技术)；问题的可分解性与解的可组装性?大数据环境下的机器学习与数据挖掘;众包(crowdsourcing)方法论 . 函数：新增加数据D2数据D1D1 + D2Zongben Xu et.al. Efficiency speed-up for evolutionary computation Fundamentals and Fast-Gas. AMC 2003编码大数据研究中的科学问题（分布实时计算）第19页，共49页。大数据研究中的科学问题（

11、非结构化问题）非结构化问题：不能用有限规则完全表征与刻画，并不能在可接受时间内形式化处理的大数据。主要的挑战来自数据的异构性、信息的不相容性与认知的不一致性。 (结构化大数据85%:文本、图像、时空数据、基因与蛋白质、视频）第20页，共49页。 基本科学问题 异构数据的统一表示与分析方法 (向量 矩阵 张量)非结构化数据处理的统一框架（特别是机器学习算法）； 多源异构数据的信息融合；基于认知的非结构化信息处理； 非结构化数据文本图像视频统一机器学习框架决策：大数据研究中的科学问题(非结构化问题)第21页，共49页。大数据研究中的科学问题（可视分析问题）可视分析：运用与人类视认知相一致的图形或者

12、图像方式生动展示高维数据的内在结构与规律性。提供了人机协同处理数据、人人广泛参与收集理解的平台（或许是解决大数据问题的另外一条道路）。数据空间特征提取映照关系可展示的几何空间FacebookWordleWhisper第22页，共49页。 基本科学问题 高维数据的本质特征提取；形象的结构化表征（可表达几何空间的构造）；从数据特征空间到可表达几何空间的映照设计；基于不变量（几何，代数）的高维数据展示方式；非结构化数据的隐结构识别与展示； 大数据研究中的科学问题（可视分析问题）Microsoft T-drive Yuan et al., 2010平行坐标系第23页，共49页。超高维问题：大数据聚类重

13、采样问题：分布式算法的可行性实时计算问题：网络流计算非结构化问题：基于视觉原理的数据挖掘解决科学问题的若干进展第24页，共49页。大数据聚类:对特征数p远大于样本数n的大数据进行聚类。新问题：有大量冗余特征，聚类时必须同时剔除冗余特征(识别有效特征）；特征数随样本数变化（p=p(n)）。本质上要求同时解决聚类、特征选择、不同时刻聚类相容性问题(特别是稳定聚类问题)。超高维问题：大数据聚类K均值聚类：导致：最优分类与特征的维数p变化无关对有效特征有严格的判定准则期望：第25页，共49页。超高维问题：大数据聚类K均值：模型：基本思路:重写目标函数为特征的“分离可加”形式，以此抽象新的最优划分定义，

14、使得最优划分与p无关，从而产生大数据的稳定聚类。( Chang ,Lin & Xu, Sparse K-Means via l/l0 Penalty for High-dimensional Data Clustering, 2014.) 最优划分:噪音特征:一个特征j为噪音特征如果对于任意给定的划分C都有否则为相关特征。第26页，共49页。（I） (II)理论：如果数据X由高斯混合模型产生，其中有p*个相关特征，p-p*个噪音特征，则结论：高斯混合数据具有稳定聚类；对于这样的大数据而言，其最优划分与p无关（n足够大）：Xp1Xp2Xp3XptC*1C*2C*3C*t超高维问题：大数据聚类第2

15、7页，共49页。实现算法：超高维问题：大数据聚类第28页，共49页。实验:从高斯混合分布产生60个样本，其中有50个特征为相关特征，其它为噪音特征，总特征数分别取p=200,500,1000.比较三种不同算法的特征选择结果与聚类结果如下：超高维问题：大数据聚类第29页，共49页。基于Hadoop的分布式算法:Hadoop是主流的分布式处理系统框架。Map-Reduce是基于Hadoop的一种分布式数据处理编程模式，其工作原理为“分而治之”。基于这种分而治之的策略设计的算法可统称之为分布式算法。HDFSHBaseMapReduceHadoop重采样问题：分布式回归的可行性第30页，共49页。St

16、ep 1:重采样数据使得整体数据随机均匀的分布在m台local machines上.X1X2X3Xn均匀分布D1DkDm.聚合机制Global MachineGlobal MachineLocal Machines重采样问题：分布式回归的可行性分布式回归算法：第31页，共49页。Step 2: 分布地在每台local machine运行一个回归算法（例如正则化回归算法），得到m个回归估计。X1X2X3Xn均匀分布D1DkDm.聚合机制Global MachineGlobal MachineLocal Machines重采样问题：分布式回归的可行性第32页，共49页。Step 3: 将local

17、 machine所获得的m个回归估计聚合形成一个整体估计（运用某种聚合算法，例如简单平均）。X1X2X3Xn均匀分布D1DkDm.聚合机制Global MachineGlobal MachineLocal Machines重采样问题：分布式回归的可行性第33页，共49页。 初步试验 线性回归模型：参数设置： 噪声：样本个数：100万参数空间维数：100数据总量：6G使用local machines: 试验结果重采样问题：分布式回归的可行性第34页，共49页。可行性理论:如果数据中所蕴含的回归关系f*具有一定的光滑性，LocalMachine上使用同一类核回归方法，Global Machine使

18、用简单平均聚合，则从泛化性的意义上分布式回归算法是可行的（当数据量足够大且mC0N时，分布式算法所产生的估计收敛于f*)。 (Chang & Xu, Feasibility of Distributed Regression for Big Data, 2014)重采样问题：分布式回归的可行性第35页，共49页。通信网络异常检测: 网络数据是一类典型的非结构化大数据。通过检测源节点到目的地节点连接的通信流，从而识别网络流量异常。 实时计算问题：网络流计算交通异常检测第36页，共49页。网络拓扑图稀疏异常矩阵：A低秩交通矩阵：X稀疏-低秩建模：LLA-LADM算法：序列收敛到目标函数的稳定点实时

19、计算问题：网络流计算第37页，共49页。Abilene IP网络11个城市，41个链接，121条OD通信流每5分钟记录一次网络流量动态监控网络流量的变化，实时识别流量异常Data: /observatory/achive/data-collections.html纽约与华盛顿之间的流量监控实时计算问题：网络流计算第38页，共49页。非结构化问题：基于视觉原理的数据挖掘分类 为什么我一眼就看出来了呢？ 核心思想：将数据建模问题看成是一个认知问题，然后通过模拟视觉认知原理来解决。聚类 回归 第39页，共49页。基于尺度空间的数据建模（尺度空间） 问题：如何从数学上刻画视网膜上的图像清晰程度与观察距

20、离或者晶状体曲率之间的关系？ 令 为自然界中某个物体的光强分布, 该物体在视网膜上所形成的光强分布 可以通过如下偏微分方程描述： 为尺度, 表示物体与视网膜之间的距离或者晶状体的曲率。注：该模型仅为理想视网膜模型，即假设视网膜的成像是各向同性和空间不变的。其中,线性扩散模型：第40页，共49页。基本原理： 将数据点视为单位光强的光点，将数据集视为一幅图像；通过模拟人眼的视觉原理，发展基于尺度空间的聚类原理与算法（IEEE Trans. PAMI, 2000). 数据图像:尺度空间图像:= 0.2= 1.2= 5.0数据集的多尺度演化：基于尺度空间的数据建模（聚类）第41页，共49页。什么是类：一个光斑可解释为一类。光斑是由收敛于同一极大值点的所有数据点所组成，而极大值点即为该类的类中心。光 斑类中心:梯度流:300类 (3 类 (1 类 (= 0.2 )= 1 )= 5 )基于尺度空间的数据建模（聚类）第42页，共49页。三个基本问题: 如何离散化尺度? 什么是类? 类是单调演化的吗? 步骤 1：确定一序列尺度 ，其中 。当 时, 每个数据点都是一类，而该数据点即为所在类的类中心。令 。步骤 2：在尺度 下，从前一尺度 的聚类中心点出发，找到新的聚类中心，并对