CS246: Mining Massive Data Sets

发表于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

CS246: Mining Massive Data Sets

课程教材: MMDs

前序知识: 编程语言 Python 或者 Java；数据结构和算法；概率论；线性代数；多变量积分；数据库系统

#介绍

#什么是数据挖掘

数据分析和挖掘的应用场景

  • 推荐系统
  • 网络检索
  • AlphaGo
  • 机器人控制

数据分析和挖掘的基本任务

数据分析
对数据进行 inspecting, cleaning, transforming 和 modeling，以发现有用的信息，提出建议，支持决策
数据挖掘
数据分析技术之一，更加关注于利用 modeling 和 knowledge discovery 来做预测，而不是仅仅做数据的描述

不同类型的数据

  • 高维数据
  • 图数据
  • 无限流数据
  • 多模态数据

数据挖掘与其他学科的关系

  • 与数据库: 都有大规模数据，简单查询
    • 数据库视角: 大规模数据的查询分析
  • 与机器学习: 都有小量数据，复杂模型
    • 机器学习视角: 模型推理
  • 与 AI
  • 与计算机理论: 都有随机化算法

数据挖掘的清单

  • 按照场景划分
    • 监督学习
    • 无监督学习
    • 强化学习
    • 半监督学习
    • 迁移学习
    • 结构化学习
  • 按照任务划分
    • 回归
    • 分类
    • 聚类
  • 按照方法
    • 线性模型
    • 深度学习
    • SVM
    • 决策树
    • KNN

#MapReduce & Spark

大规模计算的挑战

  • 如何分发计算

  • 如何让写分布式程序更简单

  • 机器故障: 每台机器的平均寿命是 3 年

  • 通过网络传输数据很慢

    • 近数据计算
    • Spark/Hadoop

  • 节点故障如何保证数据安全

    • 分布式存储

经典 MapReduce 模型

  • 三个阶段：Map, Shuffle, Reduce
  • 实现：原始 Google 实现，Hadoop，Spark，Flink
  • 优点：
    • 模型简单
    • 隐藏了底层细节
  • 缺点：
    • 巨大的性能折损：Map 的中间结果需要先写入磁盘，进行排序，然后再被 Reducer 读取
    • 表达力弱：很多问题不容易表示成 MapReduce 过程

MapReduce 的改进 – Data-Flow 系统

  • MapReduce 的问题在于，Map 和 Reduce 之间的数据流动是固定的，不够灵活。
  • Data-Flow 系统的改进包括
    • 允许任意数量的任务
    • 允许 Map 和 Reduce 以外的函数
    • 如果数据流是无环的，可以实现局部错误恢复

Spark 引擎

  • 表达力更强的计算系统
  • 快速数据共享
    • 中间结果可以在内存中共享
      • 需要大量内存
    • 重复计算可以缓存
  • 一般化的执行图：DAG 模型
  • 更丰富的函数库：不止 Map 和 Reduce
  • 容易编程

Spark 的关键设计

  • RDD: Resilient Distributed Dataset
    • KV 集合的分片
  • Transformations: 对 RDD 进行数据操作
    • 例如: map, filter, join, union, intersection, distinct
    • Lazy Evaluation
  • Actions: 返回结果
    • collect, count, reduce, take
  • DataFrame: 类似于 SQL 的表格
  • DataSet: 类似于 DataFrame，但是类型安全

Spark 的库

  • Spark SQL
  • Spark Streaming
  • MLlib
  • GraphX

适合于 MR 的问题

  • 统计每个 Host 下所有网页的总大小
  • 统计机器翻译：5-gram 的频率
  • 计算两个表的自然连接

不适合于 MR 的问题

  • 图
  • 相互依赖的数据
    • 机器学习
    • 很多 pair 数据的对比

MR 的开销估算

  • 通信开销
  • 已用的通信开销
  • 计算开销

#关联规则挖掘

动机：识别超市中哪些商品经常被一起购买

问题定义：

给定NN 次交易记录，每次交易记录包含若干个物品。找到频繁项集。

#应用场景

  • 搜索引擎对重复内容的网页去重
  • 新闻网站对一系列相关的新闻聚类
  • 寻找基因组中相似的序列
  • 从用户行为中找到相似的用户
  • 文本抄袭检测
  • 组合药物的相互作用

#定义

支持度SupportSupport
项集II 的支持度support(I)=包含I的交易数量Nsupport(I) = \frac{包含I的交易数量}{N}，支持度越高，说明II 共同出现得越频繁。
频繁项集（Frequent Itemset）
如果一个项集II 的支持度大于ss，则称II 是频繁的。
关联规则（Association Rules）
使用{i1,i2,...,ik}→j\{i_1, i_2, ..., i_k\} \rightarrow j 表示：如果一笔交易包含物品{i1,i2,...,ik}\{i_1, i_2, ..., i_k\}，则该交易很可能包含物品jj。
置信度ConfidenceConfidence
关联规则I={i1,...,ik}→jI=\{i_1,...,i_k\} \rightarrow j 的置信度conf(I→j)=support(I∪j)support(I)conf(I\rightarrow j) = \frac{support(I \cup j)}{support(I)}。

#Min-Hashing 算法

#动机

从大规模数据中快速找到相似的数据对。例如，从网页中找到相似的网页，从用户中找到相似的用户。严谨定义：从数据集DD 中找到所有相似的数据对xi,xj∈Dx_i, x_j \in D，并且d(xi,xj)≤sd(x_i, x_j) \leq s。

朴素方法需要计算所有数据对的相似度，复杂度为O(n2)O(n^2)，不适用于大规模数据。

#方法

  1. Shingling: 把原始文档转换成离散的集合
  2. Min-Hashing: 用小的签名表示大的集合
  3. Locality-Sensitive Hashing: 用小的签名找到相似的数据对