Spark MLlib

Spark简介

• 基于内存设计，比一般的数据分析框架有着更高的处理性能，使用Scala函数式编程语言。Spark是基于MapReduce并行算法实现的分布式计算，其结果可以保持在分布式框架的内存中，从而使得下一步的计算不再频繁地读写HDFS，是的数据分析更加快速和方便。Spark通过HDFS使用自带的和自定义的特定数据格式（RDD），Spark基本上可以按照程序设计人员的要求处理任何数据

RDD详解

• RDD：Resilient Distributed Datasets（弹性分布式数据集）

• RDD实质上是存储在不同节点计算机中的数据集

• 好处：让数据在不同的工作节点上并行存储，以便在需要数据的时候并行运算

• Resilient（弹性）：

  • 指数据的存储方式，即数据集可以使用内存，也可以使用磁盘存储
  • 具有很强的容错性。不会因为某个节点的错误而导致整个任务的失败

• 分布式数据的容错性处理

  • 检查节点
    • 对每个数据节点做个进行检测，随时查询每个节点的运行情况
    • 好处：便于操作主节点随时了解任务的真实数据运行情况
    • 坏处：节点检测的资源消耗大，一旦发现问题，将在不同节点间搬运数据，消耗时间，拉低执行效率
  • 更新记录
    • 主节点并不总是查询每个分节点的运行状态，而是将相同的数据在不同的节点（一般情况下是3个）下保存，每个工作节点按固定的周期更新在主节点中运行的记录，如果在一定时间内主节点查询到数据的更新状态超时或者有异常，则在存储相同数据的不同节点上重新启动数据计算工作。
    • 缺点：如果数据量过大，更新数据和重新启动运行任务的资源耗费也相当大

• RDD特性

  • 可以将数据存储在内存中，相对于传统MapReduce操作来说，具有更高的效率
  • 延迟计算，一个完整的RDD运行任务被分成两部分：Transformation和Action
    • Transformation用于对RDD的创建
      • 提供大量的操作方法：map、filter、groupBy、join等
      • RDD可以利用Transformation来生成新的RDD，可以在有限的内存空间中生成尽可能多的数据对象
      • 无论发生了多少次Transformation，在RDD中真正数据计算运行的操作Action都不可能真正运行
    • Action
      • 数据的执行部分：执行count、reduce、collect等方法
      • RDD中的所有操作都是使用的Lazy模式进行
      • 运行在编译的过程中不会立刻得到计算的最终结果，而是记住所有的操作步骤和方法，只有显示地遇到启动命令才进行计算
      • 好处：大部分的优化和前期工作在Transformation中已经执行完毕，当Action进行工作时，只需要利用个全部资源完成业务的核心工作

• RDD与其他分布式共享内存的区别

  • 分布式共享内存（Distributed Shared Memory，DSM）
  • 在DSM系统中，用户可以向框架内节点的任一位置进行读写操作，使得数据脱离本地单节点的束缚。
    • 缺点：在进行大规模计算时，对容错性容忍程度不够，常常因为一个节点产生错误而使得整个任务失败
  • 区别
    • RDD在框架内限制了批量读写数据的操作，有利于整体的容错性提高
    • RDD并不等待某个节点任务完成，而是使用“更新记录”的方式去主动性维护任务的运行，在某一个节点中任务失败，而只需要在存储相同数据的不同节点上重新运行即可

• RDD缺陷

  • RDD不适合做一个数据的存储和抓取框架，因为RDD主要执行在多个节点中的批量操作，即一个简单的写操作也会分成两个步骤进行，这样反而会降低运行效率

• RDD工作原理
  

  数据块存储方式
  • 每个BlockMaster管理着若干个BlockSlave
  • 每个BlockSlave管理着若干个BlockNode，当BlockSlave得到每个Node节点的地址，反向向BlockMaster注册每个Node的基本信息，形成分层管理
  • 对于某个节点中存储的数据，如果使用频率较多，BlockMaster会将其缓存在自己的内存中，这样如果以后需要调用这些数据，则可以直接从BlockMaster中读取

• RDD的相互依赖
  

  宽依赖和窄依赖
  • RDD作为一个数据集合，可以在数据集之间逐次生成，这种生成关系称为依赖关系。
  • 窄依赖：如果每个RDD的子RDD只有一个父RDD，而同时父RDD也只有一个子RDD时（原生家庭，独生子女）
    • 便于在单一节点上按次序执行任务，使任务可控
  • 宽依赖：多个RDD相互生成
    • 考虑任务的交互和容错性

• API（基本就是Scala集合中的常见函数）

  • aggregate
  • cache：将数据内容计算并保存在计算节点的内存中，针对Spark的Lazy数据处理模式（应对必须要求数据提前计算的情况）
    • foreach指定一个函数，也可以提早计算
  • cartesian：笛卡尔操作，要求数组的长度必须相同（两两组合）
  • coalesce：分片存储，将已经存储的数据重新分片后再进行存储
  • repartition
  • countByValue：计算数据集中某个数据出现的个数，并将以map的形式返回
  • countByKey：计算数组中元数据键值对key出现的个数
  • distinct：去重复
  • filter：对数据集进行过滤
  • flatMap：对RDD中的数据集进行整体操作的一个特殊方法
  • map：对RDD中的数据集中的元素逐个进行操作
  • groupBy：将传入的数据进行分组
  • keyBy：为数据集中的每个元素增加一个key，从而与原来的元素形成键值对
  • reduce：对传入的数据进行合并处理
  • sortBy：对已有的RDD重新排序，重新排序后的数据生成一个新的RDD
  • zip：合并压缩

MLlib基本概念

• 基本数据类型
  • Local vector、Labeled point、Local matrix、Distributed matrix
• Vector、Vectors
  • 创建dense数据
  • 创建sparse数据（1、大小；2、数据索引；3、数据内容）
  • 目前只支持整数和浮点型数
• 向量标签
  • LabeledPoint为向量数据添加标签（dense或者sparse数据都可以）
  • 支持直接从数据库中获取固定格式的数据集方法（loadLibSVMFile）
• 本地矩阵
  • Matrices.dense 可以更改数据形状
• 分布式矩阵
  • 行矩阵RowMatrix
  • 带有行索引的行矩阵IndexedRow、IndexedRowMatrix
  • 坐标矩阵：带有坐标的矩阵，一般用于数据比较多且数据分布较为分散的情况 MatrixEntry、CoordinateMatrix
  • 块矩阵
• 数理统计
  • colStats：以列为基础计算统计量的基本数据
    • count Max Mean normL1 normL2 numNonzeros variance
  • chiSqTest：对数据集内的数据进行皮尔逊距离计算，反映两变量间线性相关关系的统计指标，可以看作两组向量夹角的余弦，用来描述两组数据的分开程度，其与数据量大小也有关系，而斯皮尔曼相关系数更注意两组数据的拟合程度，即两组数据随数据量增加而增长曲线不变
  • corr：相关系数计算
  • 分层抽样：将总体的单位按某种特征分为若干次级总体（层），然后再从每一层内进行淡出随机抽样
  • 假设检验：卡方检验
  • 随机数

协同过滤算法

• 协同过滤
  • 基本思想：利用人的相似性进行比较
  • 一种基于群体用户或者物品的典型推荐算法
  • 两种算法
    • 通过考察具有相同爱好的用户对相同物品的评分标准进行计算
    • 考察具有相同特质的物品从而推荐给选择了某件物品的用户
  • 基于用户相似性的推荐：志趣相投
    • 缺点：容易推荐一些常用的物品
  • 基于物品的推荐：物以类聚
    • 用户购买过的商品，用户一般不会再买同类型的商品（一般是一些实用的物品）
• 相似度度量
  • 欧几里得距离：注重目标之间的差异，与目标在空间中的位置直接相关
  • 余弦相似度：不同目标在空间中的夹角，更加表现在前进趋势上的差异
• 交替最小二乘法（ALS算法）

线性回归

• 随机梯度下降
• 回归过拟合
  • 正则化：lasso回归（L1回归）、岭回归（L2回归）
• LinearRegressionWithSGD

分类

• 逻辑回归 LogisticRegressionWithSGD
• 支持向量机 SVMWithSGD
• 朴素贝叶斯 NaiveBayes

决策树与保序回归

• 决策树 DecisionTree
• 随机森林 RandomForest
• 梯度提升 GradientBoostedTrees
• 保序回归 IsotonicRegression
  • 对数据列的均值进行处理从而获得一个回归序列
  • 适合处理数据量庞大的情况

聚类

• KMeans
• 高斯混合聚类 GaussionMixture
• 快速迭代聚类 PowerIterationClustering

关联规则

• 关联规则使用支持度和置信度来说明
  • 支持度：两项同时出现的概率
  • 置信度：A出现时，B是否也会出现或者以多大概率出现
• Apriori频繁项集算法
  • 候选消除算法，消除出现次数过少的项，生成候选集，消除不满足条件的候选集，并不断循环，知道不再产生候选集的过程
  • 缺点：产生较多的小频繁项
  • 频繁项的处理需要多次扫描原样本数据集，I/O处理消耗大
• FP-growth算法
  • 根据事物数据库构建FP-Tree，然后基于FP-Tree生成频繁模式集
  • 理论上只对数据库进行两次扫描
  • FP树的算法主要由两大步骤完成：
    • 利用数据库中的已有样本数据构建FP树
    • 建立频繁项集规则

数据降维

• 奇异值分解 computeSVD方法
• 主成分分析 computePrincipalComponents方法

特征提取和转换

• TF-IDF（HashingTF IDF fit() transform()）
  • 基本思想，一篇文章的关键词应该在文章中出现频率较高，但一些常用词出现频率很高，故当一篇文章中提取的词频较多的关键词在当前文章中多次出现，而在其他文章中较少出现，那么它可能最大幅度地反映了这篇文章的“中心思想”
  • TF：词频
  • IDF：逆文档频率
  • TF-IDF=TF*IDF
• 词向量化 Word2Vec
  • MLlib采用的是skip-gram模型实现
• 基于卡方检验的特征选择

References

• 《Spark MLlib机器学习实战》