Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

基于Spark的医疗和金融大数据

No description
by

Chunnan Yao

on 24 June 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of 基于Spark的医疗和金融大数据

数据预处理和统计分析
背景和意义
伪数据下的性能分析及方案选择
大规模谱聚类算法
基于Spark的医疗和金融大数据
算法工具包的开发

大数据是跨学科的分析工具,能够挖掘数据潜在价值
大规模数据预处理、统计分析和谱聚类算法在医疗和金融领域有较广泛应用
实现并调优开源社区未开发的并行算法,为开源软件做贡献
结论
+
分布式文件系统
定义:文件系统管理的物理存储资源不一定直接连接在本地节点上,而是通过计算机网络与节点相连。

解决的问题:为存储海量数据降低成本。

本设计采用:Hadoop Distributed File System
(HDFS)
大规模数据预处理
缺失数据的填补
数值型数据(平均值、最小值、中位数、最大值、按正态分布的随机值)
标称型数据(按出现概率随机填补)
基于算法要求的数据格式化
数值型数据的定标
标称型数据向项目数据的转换
Aggregate函数:
子函数1:指定单机归约
子函数2:指定多机归约
数据类型转换:
大规模统计分析算法
系 统 架 构
双样本卡方检验
双样本费谢尔精确度检验
双样本柯尔莫诺夫-斯米尔诺夫检验
威尔科克森符号秩检验
单向方差分析
分布式环境中的两两计算
RDD逐特征选取法
优:利用Spark的Sort算子,不需对全体数据做转置
劣:并行度低
广播分区法
优:增加并行度
劣:网络和CPU负载高
转置分块笛卡尔积法
-------------对三种方法的实验
优:增加并行度,不需要额外特殊变量
劣:内存和CPU负载高
谱聚类介绍
一般来说,计算出数据点两两邻接关系矩阵后,通过求特征向量将其降维,最后对降维数据做普通聚类(如K-Means)的方法叫做谱聚类方法
优点:
更充分利用数据间信息
不会陷入局部最优解
已被广泛应用于信息提取、图像处理中
大规模谱聚类实现方法
--------三种尝试
基于K近邻稀疏化算法
基于奈斯特龙优化
基于局部敏感哈希算法
基于LSH的大规模谱聚类算法的实现
稀疏化邻接关系矩阵,提高效率
以近似计算规避邻接关系矩阵的计算
利用哈希函数对数据作多次哈希操作产生哈希签名,以此进行并行的预聚类
姚春楠 信息工程
MapReduce
Apache Spark
并行计算引擎
并行计算引擎
定义:一种以映射(Map)和归约(Reduce)为基本操作的并行程序设计框架。
逻辑范式: 给定的问题尽量分解成相互独立的子问题,以便多台计算机在尽量小的网络通信负担下同时求解它们,最终将各个子问题的结果汇总得到原问题的解
解决的问题:对开发人员隐藏并行编程复杂的底层细节
最流行的开源MapReduce实现是Hadoop。
定义:
基于内存的并行计算引擎
解决的问题:
沿用MapReduce的逻辑范式,但将大部分计算放在内存中进而大大提高计算速度。
提出的概念:
弹性分布式数据集(Resilient Distributed Datasets)。
目标:
结合了速度、易于使用的编程模型和统一设计,让用户能够将交互式查询、流式分析、机器学习和图形计算合并到单一系统里面
目前的发展阶段:
2014年Apache开源社区最活跃的项目之一,全球上百家企业在生产环境中使用、贡献代码。
本设计的工作
为Spark的机器学习模块添加三个新功能(数据预处理,统计分析算法,谱聚类算法),确保它们在分布式环境中的高效实现,并在顶层搭建可视化模块。
对数据点进行预聚类(分桶),指定哈希签名规则:
随机投影算法:
Spark实现的算法流程:
(1) 通过若干次映射和归约过程参照上式的方法选出哈希过程需要使用的超平面和比较阈值,将它们输入LSH 模型。

(2) 广播LSH 模型,使得每个Worker 都能够独立进行哈希过程。通过一次映射,计算出全数据集的哈希签名,并把这些哈希签名本地化(collect)。

(3) 本地扫描全数据哈希签名,按照h汉明码比较规则为每条签名打上分桶标记。

(4) 通过一次join 操作为原数据中每条记录打上分桶标记。

(5) 通过一次groupByKey 的洗牌(shuffle)动作将同一个桶中的数据聚集到同一台Worker 中。

(6) 集群同时并行扫描桶中的数据,计算相似度矩阵(稀疏矩阵)S。后计算拉普拉斯矩阵并调用Spark MLlib中的SVD函数进行特征值分解

(7) 对分解结果归一化后进行K-Means聚类
本设计中算法性能验证的一般步骤:
测试环境:
集群计算机数量:7
CPU型号:lntel Xeon CPU E5-2660 2.20GHZ
单台机器CPU核数:32
单台worker内存:160G
单台硬盘空间:262G
并行批量统计测试方案的选择
500kx1k数据量:广播分区法6957s,转置分块笛卡尔积法:3219s
结论:选择转置分块笛卡尔积法作为KS Test/Wilcoxon Test的并行执行方法。
谱聚类算法KNN图计算方案的选择
基于奈斯特龙优化的实现在大数据上仍不稳定,故不进行性能分析。
比较PSC(基于K近邻)和DASC(基于LSH):
伪数据生成方法:
(1)统计分析算法:按不同分布产生的特征列。
(2)谱聚类算法:数据点各自散落在指定的随机中心点附近
(1)运行单机典型小数据检查算法正确性。
(2)分布式集群大规模数据实测。按不同数据量、不同节点数进行分别测试比较
32kx64数据量: PSC139s,DASC54s,且根据WSSE值,DASC聚类效果更好。

结论:选择LSH作为谱聚类KNN邻接矩阵计算的方法。
算法实现性能综合分析
可视化接口
需求分析:原始的Spark将结果打印或以文件形式输出,操作复杂,结果不直观,妨碍跨领域科学家的分析工作。
本设计的解决方案:选用Apache Zeppelin作为用户接口和数据可视化模块, 部署到集群中后,可以从任何终端的浏览器中与Spark集群进行交互。用例说明:
本课题主要完成了以下内容:
1. 部署Spark系统,学习Scala语言,阅读Spark MLlib主要源代码。

2. 运用对Spark架构和相应算法的理解以及对Scala语言的掌握在实际集群中完成大规模并行算法的编写、调试和部署工作,并进行合理的可视化呈现。
本课题的难点和特色:
1. 在资源有限的环境中进行分布式编程,需要大量动手实验和性能调优(GC,分区数,cache,shuffle量,底层工具调度)。

2. 分别用三种方法实现两两特征对统计分析和谱聚类算法,并通过实验比较证实在Spark上最高效的方案。
3. 数据、算法、可视化三个大数据工具的关键组件结合,为大数据应用提供了一套系统的方案。
DASC谱聚类算法比[1]在Hadoop上的实现性能提高42倍!
[1] Hefeeda M, Gao F, Abd-Almageed W. Distributed approximate spectral clustering for large-scale datasets[C]//Proceedings of the 21st international symposium on High-Performance Parallel and Distributed Computing. ACM, 2012: 223-234.
https://github.com/milesyao
Full transcript