大数据的处理和分析计算机科学导论第十讲

大 数 据 的 处 理 和 分 析计 算 机 科 学 导 论 第 十 讲计 算 机 科 学 技 术 学 院陈 意 云0551-63607043, http:/ 课 程 内 容 课 程 内 容围 绕 学 科 理 论 体 系 中 的 模 型 理 论 , 程 序 理 论 和 计 算 理 论1. 模 型 理 论 关 心 的 问 题 给 定 模 型 M， 哪 些 问 题 可 以 由 模 型 M解 决 ； 如 何比 较 模 型 的 表 达 能 力2. 程 序 理 论 关 心 的 问 题 给 定 模 型 M， 如 何 用 模 型 M解 决 问 题 包 括 程 序 设 计 范 型 、 程 序 设 计 语 言 、 程 序 设 计 、形 式 语 义 、 类 型 论 、 程 序 验 证 、 程 序 分 析 等3. 计 算 理 论 关 心 的 问 题给 定 模 型 M和 一 类 问 题 , 解 决 该 类 问 题 需 多 少 资 源 2 本 次 讲 座 与 这 些 内 容 关 系不 大 讲 座 提 纲 大 数 据 的 魅 力 数 据 挖 掘 、 大 数 据 、 大 数 据 案 例 、 大 数 据 的 特 点 大 数 据 时 代 的 思 维 变 革 样 本 和 全 体 、 精 确 性 和 混 杂 性 、 因 果 关 系 和 相 关关 系 大 数 据 的 处 理 几 种 主 要 处 理 方 式 、 MapReduce编 程 模 型 大 数 据 的 分 析 关 键 技 术 概 述 、 PageRank初 步 3 数 据 挖 掘 数 据 挖 掘 的 定 义1. 从 数 据 中 提 取 出 隐 含 的 、 过 去 未 知 的 、 有 价 值的 潜 在 信 息2. 从 大 量 数 据 或 者 数 据 库 中 提 取 有 用 信 息 的 科 学 相 关 概 念 ： 知 识 发 现1. 数 据 挖 掘 是 知 识 发 现 过 程 中 的 一 步2. 粗 略 看 ： 数 据 预 处 理 数 据 挖 掘 数 据 后 处 理预 处 理 : 将 未 加 工 输 入 数 据 转 换 为 适 合 处 理 的 形 式后 处 理 : 如 可 视 化 , 便 于 从 不 同 视 角 探 查 挖 掘 结 果大 数 据 的 魅 力 4 数 据 挖 掘 典 型 事 例 ： 购 物 篮 分 析顾 客 一 次 购 买 商 品 1 面 包 、 黄 油 、 尿 布 、 牛 奶 2 咖 啡 、 糖 、 小 甜 饼 、 鲑 鱼 3 面 包 、 黄 油 、 咖 啡 、 尿 布 、 牛 奶 、 鸡 蛋 4 面 包 、 黄 油 、 鲑 鱼 、 鸡 5 鸡 蛋 、 面 包 、 黄 油 6 鲑 鱼 、 尿 布 、 牛 奶 7 面 包 、 茶 叶 、 糖 、 鸡 蛋 8 咖 啡 、 糖 、 鸡 、 鸡 蛋 9 面 包 、 尿 布 、 牛 奶 、 盐10 茶 叶 、 鸡 蛋 、 小 甜 饼 、 尿 布 、 牛 奶大 数 据 的 魅 力 5 数 据 挖 掘 典 型 事 例 ： 购 物 篮 分 析顾 客 一 次 购 买 商 品 1 面 包 、 黄 油 、 尿 布 、 牛 奶 2 咖 啡 、 糖 、 小 甜 饼 、 鲑 鱼 3 面 包 、 黄 油 、 咖 啡 、 尿 布 、 牛 奶 、 鸡 蛋 4 面 包 、 黄 油 、 鲑 鱼 、 鸡 5 鸡 蛋 、 面 包 、 黄 油 6 鲑 鱼 、 尿 布 、 牛 奶 7 面 包 、 茶 叶 、 糖 、 鸡 蛋 8 咖 啡 、 糖 、 鸡 、 鸡 蛋 9 面 包 、 尿 布 、 牛 奶 、 盐10 茶 叶 、 鸡 蛋 、 小 甜 饼 、 尿 布 、 牛 奶经 关 联 分 析 ， 可 发 现 顾 客 经 常 同 时 购 买 的 商 品 ： 尿 布 牛 奶大 数 据 的 魅 力 6 大 数 据 大 数 据 ， 或 称 海 量 数 据 ， 指 所 涉 及 的 数 据 量 规 模巨 大 到 无 法 通 过 人 工 ， 在 合 理 时 间 内 达 到 截 取 、管 理 、 处 理 、 并 整 理 成 为 人 类 所 能 解 读 的 信 息 例 如 ： Google每 天 有 来 自 全 球 30亿 条 搜 索 指 令 每 天 都 有 成 千 上 万 的 人 通 过 Google搜 索 信 息 ，从 出 游 的 路 线 和 耗 时 、 治 疗 某 种 疾 病 的 方 法 和 某研 究 方 向 的 最 新 学 术 资 料 ， 各 式 各 样 的 搜 索 要 求都 有 这 样 的 搜 索 引 擎 无 疑 极 大 地 方 便 了 人 们 的 生 活和 工 作 大 数 据 的 魅 力 7 大 数 据 大 数 据 ， 或 称 海 量 数 据 ， 指 所 涉 及 的 数 据 量 规 模巨 大 到 无 法 通 过 人 工 ， 在 合 理 时 间 内 达 到 截 取 、管 理 、 处 理 、 并 整 理 成 为 人 类 所 能 解 读 的 信 息 这 一 系 列 搜 索 数 据 从 侧 面 显 示 出 搜 索 这 些 信 息 的人 的 本 身 情 况 ， 比 如 他 们 的 想 法 、 需 求 、 忧 虑 等非 常 有 价 值 的 信 息 如 果 这 些 搜 索 数 据 能 准 确 地 反 映 人 们 的 生 活 和 工作 状 况 ， 那 么 就 有 可 能 利 用 这 些 信 息 来 察 觉 商 业趋 势 、 避 免 疾 病 扩 散 、 打 击 犯 罪 、 测 定 实 时 交 通路 况 和 预 测 选 举 结 果 等大 数 据 的 魅 力 8 大 数 据 大 数 据 ， 或 称 海 量 数 据 ， 指 所 涉 及 的 数 据 量 规 模巨 大 到 无 法 通 过 人 工 ， 在 合 理 时 间 内 达 到 截 取 、管 理 、 处 理 、 并 整 理 成 为 人 类 所 能 解 读 的 信 息 与 小 数 据 集 的 比 较 ： 在 总 数 据 量 相 同 的 情 况 下 ， 与 个 别 分 析 独 立 的小 型 数 据 集 相 比 ， 将 各 个 小 型 数 据 集 合 并 后 进 行大 数 据 分 析 可 得 出 许 多 额 外 的 信 息 和 数 据 关 联 性 这 正 是 大 型 数 据 集 盛 行 的 原 因 数 据 挖 掘 则 是 探 讨 用 以 解 析 大 数 据 的 方 法大 数 据 的 魅 力 9 大 数 据 案 例 谷 歌 预 测 冬 季 流 感 的 传 播 2008年 11月 谷 歌 公 司 启 动 “ 谷 歌 流 感 趋 势”(Google Flu Trends, GFT) 项 目 GFT项 目 把 5000万 个 美 国 人 最 频 繁 检 索 的 词 项 与美 国 疾 病 预 防 控 制 中 心 告 知 的 2003年 2008年 季节 性 流 感 传 播 期 间 的 数 据 进 行 比 较 ， 以 确 定 相 关检 索 词 项 为 测 试 这 些 检 索 词 项 的 使 用 频 率 与 流 感 在 时 间 和空 间 上 传 播 之 间 的 联 系 ， GFT共 处 理 了 4.5亿 个 不同 的 数 学 模 型大 数 据 的 魅 力 10 大 数 据 案 例 谷 歌 预 测 冬 季 流 感 的 传 播 为 测 试 这 些 检 索 词 项 的 使 用 频 率 与 流 感 在 时 间 和空 间 上 传 播 之 间 的 联 系 ， GFT共 处 理 了 4.5亿 个 不同 的 数 学 模 型 在 把 得 出 的 预 测 与 2007年 和 2008年 疾 病 预 防 控 制中 心 记 录 的 实 际 流 感 病 例 进 行 对 比 后 ， GFT的 软件 发 现 了 45个 检 索 词 项 的 组 合 把 这 些 检 索 词 项 用 于 一 个 特 定 的 数 学 模 型 后 ， 其预 测 与 官 方 数 据 相 关 性 高 达 97%大 数 据 的 魅 力 11 大 数 据 案 例 谷 歌 预 测 冬 季 流 感 的 传 播 2009年 谷 歌 把 研 究 成 果 发 表 在 自 然 杂 志 上 ，这 篇 引 人 注 目 的 论 文 令 公 共 卫 生 官 员 和 计 算 机 科学 家 感 到 震 惊 文 章 不 仅 预 测 了 流 感 在 全 美 的 传 播 ， 而 且 具 体 到特 定 的 地 区 和 州 并 且 预 测 非 常 及 时 ， 不 像 疾 病 预 防 控 制 中 心 的 信息 会 有 一 两 周 的 延 迟 （ 因 为 人 们 从 患 病 到 求 医 会滞 后 ， 信 息 从 医 院 传 到 疾 控 中 心 也 需 要 时 间 ， 疾控 中 心 每 周 只 进 行 一 次 数 据 汇 总 ） 信 息 滞 后 两 周 对 一 种 飞 速 传 播 的 疾 病 是 致 命 的大 数 据 的 魅 力 12 大 数 据 案 例 谷 歌 预 测 冬 季 流 感 的 传 播 在 论 文 发 表 后 的 几 周 内 ， 出 现 了 一 种 称 为 甲 型H1N1的 新 流 感 病 毒 ， 它 在 短 短 几 周 内 迅 速 传 播 开来 ， 全 球 的 公 共 卫 生 机 构 都 担 心 一 场 致 命 的 流 行病 即 将 来 袭 这 时 ， 与 习 惯 性 滞 后 的 官 方 数 据 相 比 ， 谷 歌 的 预测 是 一 个 更 有 效 、 更 及 时 的 指 示 标 ， 公 共 卫 生 机构 的 官 员 因 此 获 得 了 非 常 有 价 值 的 数 据 信 息 谷 歌 的 方 法 不 需 要 分 发 口 腔 试 纸 和 联 系 医 生 ， 因为 它 是 建 立 在 大 数 据 的 基 础 之 上大 数 据 的 魅 力 13 大 数 据 的 魅 力 大 数 据 案 例 谷 歌 预 测 冬 季 流 感 的 传 播 这 是 当 今 社 会 所 独 有 的 一 种 新 型 能 力 ： 以 一 种 前所 未 有 的 方 式 ， 通 过 对 海 量 数 据 的 分 析 ， 获 得 巨大 价 值 的 产 品 和 服 务 ， 或 深 刻 的 洞 见 大 数 据 不 仅 会 变 革 公 共 卫 生 ， 也 会 变 革 商 业 、 变革 思 维 ， 改 变 政 府 与 民 众 关 系 的 方 法 ， ， 开 启重 大 的 时 代 转 型 14 大 数 据 的 魅 力 大 数 据 案 例 谷 歌 预 测 冬 季 流 感 的 传 播 2013年 2月 ， GFT再 次 上 头 条 ， 不 是 因 为 什 么 新 的成 就 ， 而 是 因 2013年 1月 ， 美 国 流 感 发 生 率 达 到 峰值 ， GFT事 先 的 估 计 比 实 际 数 据 高 两 倍 造 成 这 种 结 果 的 原 因 ： 大 数 据 傲 慢 （ Big Data Hubris） ： 认 为 自 己 拥有 的 数 据 是 总 体 ， 可 以 完 全 取 代 科 学 抽 样 基 础 上形 成 的 传 统 小 数 据 ， 而 非 作 为 后 者 的 补 充 还 有 搜 索 算 法 变 化 等 原 因 大 数 据 运 用 的 典 范 GFT的 失 败 并 不 能 够 抹 灭 大 数据 本 身 的 价 值 15 大 数 据 的 魅 力 大 数 据 的 特 点 体 量 巨 大 (Volume) 数 据 集 合 的 规 模 不 断 扩 大 ， 已 从 GB(1024MB)到 TB(1024GB)再 到 PB级 ， 甚 至 已 经 开 始 以 EB和ZB来 计 数 至 今 ， 人 类 生 产 的 所 有 印 刷 材 料 的 数 据 量 是200PB 未 来 10年 ， 全 球 大 数 据 将 增 加 50倍 ， 管 理 数 据仓 库 的 服 务 器 的 数 量 将 增 加 10倍 16 大 数 据 的 魅 力 大 数 据 的 特 点 种 类 繁 多 (Variety) 数 据 种 类 繁 多 ， 并 且 被 分 为 结 构 化 、 半 结 构 化和 非 结 构 化 的 数 据 半 结 构 化 和 非 结 构 化 的 数 据 ， 包 括 网 络 日 志 、传 感 器 数 据 、 音 频 、 视 频 、 图 片 、 地 理 位 置 信 息等 ， 占 有 量 越 来 越 大 ， 已 远 远 超 过 结 构 化 数 据 17 大 数 据 的 魅 力 大 数 据 的 特 点 价 值 密 度 低 (Value) 数 据 总 体 的 价 值 巨 大 ， 但 价 值 密 度 很 低 以 视 频 为 例 ， 在 长 达 数 小 时 连 续 不 断 的 视 频 监控 中 ， 有 用 数 据 可 能 仅 一 二 秒 另 一 极 端 是 各 个 数 据 都 有 贡 献 ， 但 单 个 数 据 价值 很 低 18 大 数 据 的 魅 力 大 数 据 的 特 点 速 度 快 (Velocity) 数 据 往 往 以 数 据 流 的 形 式 动 态 快 速 地 产 生 ， 具有 很 强 的 时 效 性 用 户 只 有 把 握 好 对 数 据 流 的 掌 控 才 能 有 效 利 用这 些 数 据 例 如 ， 一 天 之 内 需 要 审 查 500万 起 潜 在 的 贸 易 欺诈 案 件 ； 需 要 分 析 5亿 条 日 实 时 呼 叫 的 详 细 记 录 ，以 预 测 客 户 的 流 失 率 19 大 数 据 时 代 的 思 维 变 革数 据 采 集 和 数 据 处 理 技 术 已 经 发 生 了 翻 天覆 地 的 变 化 ， 人 们 的 思 维 和 方 法 要 跟 得 上 这个 变 化大 数 据 时 代 的 精 髓 在 于 人 们 分 析 信 息 时 的三 个 转 变 ， 这 些 转 变 将 改 变 人 们 决 策 的 制 定和 对 表 象 的 理 解 20 大 数 据 时 代 的 思 维 变 革 变 革 一 更 多 : 不 是 随 机 样 本 , 而 是 全 体 数 据1. 随 机 抽 样 ： 用 最 少 的 数 据 获 得 最 多 的 信 息 过 去 由 于 获 取 和 分 析 全 体 数 据 的 困 难 ， 抽 样 调 查是 一 种 常 用 统 计 分 析 方 法 。 它 根 据 随 机 原 则 从 总体 中 抽 取 部 分 实 际 数 据 进 行 调 查 ， 并 运 用 概 率 估计 方 法 ， 根 据 样 本 数 据 推 算 总 体 相 应 的 数 量 指 标 抽 样 分 析 的 精 确 性 随 抽 样 随 机 性 的 增 加 而 提 高 ，与 样 本 数 量 的 增 加 关 系 不 大 。 抽 样 随 机 性 高 时 ，分 析 的 精 度 能 达 到 把 全 体 作 为 样 本 调 查 时 的 97% 样 本 选 择 的 随 机 性 比 样 本 数 量 更 重 要 21 大 数 据 时 代 的 思 维 变 革 变 革 一 更 多 : 不 是 随 机 样 本 , 而 是 全 体 数 据1. 随 机 抽 样 ： 用 最 少 的 数 据 获 得 最 多 的 信 息 抽 样 分 析 的 成 功 依 赖 于 抽 样 的 随 机 性 ， 但 实 现 抽样 的 随 机 性 非 常 困 难 当 想 了 解 更 深 层 次 的 细 分 领 域 的 情 况 时 ， 随 机 抽样 方 法 不 一 定 有 效 ， 即 在 宏 观 领 域 起 作 用 的 方 法在 微 观 领 域 可 能 失 去 了 作 用 随 机 抽 样 需 要 严 密 的 安 排 和 执 行 ， 人 们 只 能 从 抽样 数 据 中 得 出 事 先 设 计 好 的 问 题 的 结 果 22 大 数 据 时 代 的 思 维 变 革 变 革 一 更 多 : 不 是 随 机 样 本 , 而 是 全 体 数 据2. 全 体 数 据 ： 用 全 体 数 据 可 对 数 据 进 行 深 度 探 讨 流 感 趋 势 预 测 分 析 了 整 个 美 国 几 十 亿 条 互 联 网 检索 记 录 ， 使 得 它 能 提 高 微 观 层 面 分 析 的 准 确 性 ，甚 至 能 够 推 测 某 个 特 定 城 市 的 流 感 状 况 信 用 卡 诈 骗 需 通 过 观 察 异 常 情 况 来 识 别 ， 这 只 有在 掌 握 所 有 的 数 据 时 才 能 做 到 社 会 科 学 是 被 “ 样 本 =全 体 ”撼 动 得 最 厉 害 的 一 门学 科 。 这 门 学 科 过 去 非 常 依 赖 于 样 本 分 析 、 研 究和 调 查 问 卷 。 当 记 录 下 人 们 的 平 常 状 态 ， 就 不 用担 心 在 做 研 究 和 调 查 问 卷 时 存 在 的 偏 见 了 23 大 数 据 时 代 的 思 维 变 革 变 革 二 更 杂 ： 不 是 精 确 性 ， 而 是 混 杂 性 对 小 数 据 而 言 ， 最 基 本 和 最 重 要 的 要 求 就 是 减 少错 误 ， 保 证 质 量 。 因 为 收 集 的 数 据 较 少 ， 应 确 保每 个 数 据 尽 量 精 确 ， 以 保 证 分 析 结 果 的 准 确 性 允 许 不 精 确 数 据 是 大 数 据 的 一 个 亮 点 , 而 非 缺 点 。因 为 放 松 了 容 错 的 标 准 ， 就 可 以 掌 握 更 多 数 据 ；而 掌 握 大 量 新 型 数 据 时 ， 精 确 性 就 不 那 么 重 要 了 例 如 ， 与 服 务 器 处 理 投 诉 时 的 数 据 进 行 比 较 ， 用语 音 识 别 系 统 识 别 呼 叫 中 心 接 到 的 投 诉 会 产 生 不太 准 确 的 结 果 , 但 它 有 助 于 把 握 事 情 的 大 致 情 况 不 精 确 的 大 量 新 型 数 据 能 帮 助 掌 握 事 情 发 展 趋 势 24 大 数 据 时 代 的 思 维 变 革 变 革 二 更 杂 ： 不 是 精 确 性 ， 而 是 混 杂 性 执 迷 于 精 确 性 是 信 息 缺 乏 时 代 的 产 物 ， 大 数 据 时代 要 求 重 新 审 视 精 确 性 的 优 劣 ， 如 果 将 传 统 的 思维 模 式 运 用 于 数 字 化 、 网 络 化 的 21世 纪 ， 就 会 错过 重 要 信 息 ， 失 去 做 更 多 事 情 ， 创 造 出 更 好 结 果的 机 会 另 一 方 面 ， 需 要 与 数 据 增 加 引 起 的 各 种 混 乱 （ 数据 格 式 不 一 致 ， 数 据 错 误 率 增 加 等 ） 做 斗 争 。 错误 并 不 是 大 数 据 的 固 有 特 性 ， 但 可 能 是 长 期 存 在并 需 要 去 处 理 的 现 实 问 题 25 大 数 据 时 代 的 思 维 变 革 变 革 三 更 好 : 不 是 因 果 关 系 , 而 是 相 关 关 系1. 因 果 关 系 与 相 关 关 系 因 果 关 系 是 指 一 个 事 件 是 另 一 个 事 件 的 结 果 相 关 关 系 是 指 两 个 事 件 的 发 生 存 在 某 个 规 律 与 通 过 逻 辑 推 理 研 究 因 果 关 系 不 同 ， 大 数 据 研 究通 过 对 巨 量 数 据 做 统 计 性 的 搜 索 、 比 较 、 聚 类 、分 析 和 归 纳 ， 寻 找 事 件 （ 或 数 据 ） 之 间 的 相 关 性 一 般 来 说 ， 统 计 学 无 法 检 验 逻 辑 上 的 因 果 关 系 也 许 正 因 为 统 计 方 法 不 致 力 于 寻 找 真 正 的 原 因 , 才促 进 数 据 挖 掘 和 大 数 据 技 术 在 商 业 领 域 广 泛 应 用 26 大 数 据 时 代 的 思 维 变 革 变 革 三 更 好 : 不 是 因 果 关 系 , 而 是 相 关 关 系2. 相 关 关 系 帮 助 捕 捉 现 在 和 预 测 未 来 如 果 A和 B经 常 一 起 发 生 ， 则 只 需 注 意 到 B发 生 了 , 就 可 以 预 测 A也 发 生 了 故 障 经 常 是 慢 慢 出 现 的 ， 通 过 收 集 所 有 数 据 ， 可预 先 捕 捉 到 事 物 要 出 故 障 的 信 号 。 如 把 发 动 机 的嗡 嗡 声 、 引 擎 过 热 等 异 常 情 况 与 正 常 情 况 对 比 ，就 能 知 道 什 么 地 方 将 出 毛 病 ， 及 时 更 换 或 修 复 过 去 需 先 有 想 法 ， 然 后 收 集 数 据 来 测 试 想 法 的 可行 性 ， 现 在 可 以 对 大 数 据 进 行 相 关 关 系 分 析 知 道机 票 是 否 会 飞 涨 、 哪 些 词 项 最 能 显 示 流 感 的 传 播 27 大 数 据 时 代 的 思 维 变 革 变 革 三 更 好 : 不 是 因 果 关 系 , 而 是 相 关 关 系3. 大 数 据 改 变 人 类 探 索 世 界 的 方 法 越 来 越 多 的 事 物 不 断 地 数 据 化 ， 将 拓 展 人 类 的 视野 ， 使 得 人 们 可 从 大 量 的 数 据 中 ， 发 现 隐 藏 在 其中 的 自 然 规 律 、 社 会 规 律 和 经 济 规 律 当 网 页 变 成 数 据 ， 谷 歌 具 备 了 令 人 大 跌 眼 球 的 全文 搜 索 能 力 ， 在 几 个 毫 秒 之 内 ， 就 能 让 人 们 检 索世 界 上 几 乎 所 有 的 网 页 当 方 位 变 成 数 据 ， 每 个 人 都 能 借 助 GPS 快 速 到 达目 的 地 28 大 数 据 时 代 的 思 维 变 革 变 革 三 更 好 : 不 是 因 果 关 系 , 而 是 相 关 关 系3. 大 数 据 改 变 人 类 探 索 世 界 的 方 法 当 情 绪 变 成 数 据 ， 人 们 甚 至 根 据 大 家 快 乐 与 否 判断 股 市 的 涨 跌 上 述 这 些 不 同 的 数 据 可 归 结 为 几 类 相 似 的 数 学 模型 ， 从 而 使 得 “ 数 据 科 学 ” （ 应 用 数 据 学 习 知 识的 学 科 ） 成 为 一 门 具 备 普 遍 适 用 的 学 科 生 物 信 息 学 、 计 算 社 会 学 、 天 体 信 息 学 、 电 子 工程 、 金 融 学 、 经 济 学 等 学 科 ， 都 依 赖 数 据 科 学 的发 展 29 大 数 据 的 处 理 大 数 据 处 理 的 几 种 主 要 方 式 海 量 数 据 的 处 理 对 于 当 前 的 技 术 来 说 是 一 种 极 大的 挑 战 ， 目 前 大 数 据 的 主 要 处 理 形 式 如 下 ： 静 态 数 据 的 批 量 处 理 数 据 体 量 巨 大 、 精 度 高 、 价 值 密 度 低 利 用 批 量 数 据 ， 挖 掘 合 适 的 模 式 (数 据 的 结 构 、属 性 、 联 系 和 约 束 的 描 述 )、 得 出 具 体 的 含 义 、 制定 明 智 的 决 策 、 做 出 有 效 的 应 对 措 施 、 实 现 业 务目 标 用 于 社 交 网 络 、 电 子 商 务 、 搜 索 引 擎 等 30 大 数 据 的 处 理 大 数 据 处 理 的 几 种 主 要 方 式 海 量 数 据 的 处 理 对 于 当 前 的 技 术 来 说 是 一 种 极 大的 挑 战 ， 目 前 大 数 据 的 主 要 处 理 形 式 如 下 ： 在 线 数 据 的 实 时 流 式 处 理 日 志 数 据 、 传 感 器 数 据 、 Web数 据 等 数 据 连 续 不 断 、 来 源 众 多 、 格 式 复 杂 、 物 理 顺序 不 一 、 价 值 密 度 低 流 式 挖 掘 、 实 时 分 析 、 应 用 于 智 能 交 通 、 环 境 监 控 、 灾 难 预 警 、金 融 银 行 等 还 有 在 线 数 据 的 交 互 处 理 、 图 数 据 处 理 31 大 数 据 的 处 理 MapReduce编 程 模 型 是 批 量 数 据 处 理 的 一 种 常 用 编 程 模 型 ， 源 于 函 数式 编 程 语 言 的 两 个 高 阶 函 数 ： map和 reduce map(f1, x1, , xn) = f1(x1), , f1(xn) f1作 用 于 n个 变 元 的 计 算 可 以 并 行 reduce(f2, y1, , yn) = f2( f2(f2(y1, y2), y3), , yn) 若 二 元 函 数 f2是 有 交 换 律 和 结 合 率 的 运 算 ， 则 f2作用 于 n个 变 元 的 计 算 也 可 以 适 当 并 行 两 者 的 复 合 ： reduce(f 2, map(f1, x1, , xn) MapReduce源 于 此 ， 但 更 加 一 般 32 MapReduce编 程 模 型 MapReduce是 一 种 比 较 专 用 的 并 行 编 程 模 型 ， 面向 大 数 据 集 上 的 可 并 行 化 的 问 题 Map完 成 过 滤 或 分 类 ， 例 如 ， 它 把 数 据 集 中 所 有的 人 按 姓 氏 分 成 若 干 队 列 ， 每 个 姓 氏 一 个 队 列 ； Reduce完 成 概 括 总 结 操 作 ， 例 如 ， 计 算 各 姓 氏 队列 中 的 人 数 ， 产 生 按 姓 氏 的 人 口 比 例 MapReduce可 以 在 并 行 计 算 机 、 计 算 机 集 群 和 计算 机 网 格 上 实 现大 数 据 的 处 理 33 MapReduce编 程 模 型 计 算 过 程 如 图 所 示 程 序 员 只 需 编写 Map和 Reduce函 数1. Map任 务 执 行 Map函 数 的多 个 任 务 并 行 执 行 每 个 Map任 务 把 文件 块 转 换 成 “ 键 -值 ”(key-value)对 序 列大 数 据 的 处 理Map任 务 Reduce任 务按 键 分 组 输出文件输 入文 件 块 键 -值 对 (k, v) 键 及 所 有 值(k, v, w, ) 34 MapReduce编 程 模 型2. 按 键 组 合 其 处 理 方 式 与两 个 函 数 无 关 把 “ 键 -值 ” 对 序列 组 成 “ 键 -值 表 ” 对序 列 把 各 “ 键 -值 表 ” 对分 发 给 Reduce任 务 按 键 组 合 由 主 控程 序 完 成 大 数 据 的 处 理Map任 务 Reduce任 务按 键 分 组 输出文件输 入文 件 块 键 -值 对 (k, v) 键 及 所 有 值(k, v, w, ) 35 MapReduce编 程 模 型3. Reduce任 务 执 行 Reduce函数 的 多 个 任 务 并行 执 行 每 个 Reduce任 务把 “ 键 -值 表 ” 对 中的 值 以 某 种 方 式 组合 ， 转 换 成 “ 键 -值 ”对 输 出 大 数 据 的 处 理Map任 务 Reduce任 务按 键 分 组 输出文件输 入文 件 块 键 -值 对 (k, v) 键 及 所 有 值(k, v, w, ) 36 当 矩 阵 很 大 时 ， 可 用 MapReduce实 现 矩 阵 运 算 。 对 于 分 块 乘 ：1. Map任 务 计 算 两 块 的 乘 ， 用 结果 在 Z中 的 位 置 作 为 键2. Reduce任 务 按 键 值 来 分 别 累 加Map任 务 的 结 果b n 大 数 据 的 处 理X: Y:Z: 37 当 矩 阵 很 大 时 ， 可 用 MapReduce实 现 矩 阵 运 算 。 对 于 分 块 乘 ：1. Map任 务 计 算 两 块 的 乘 ， 用 结果 在 Z中 的 位 置 作 为 键2. Reduce任 务 按 键 值 来 分 别 累 加Map任 务 的 结 果b n 大 数 据 的 处 理X: Y:Z: 38 b n 大 数 据 的 处 理X: Y:Z: 当 矩 阵 很 大 时 ， 可 用 MapReduce实 现 矩 阵 运 算 。 对 于 分 块 乘 ：1. Map任 务 计 算 两 块 的 乘 ， 用 结果 在 Z中 的 位 置 作 为 键2. Reduce任 务 按 键 值 来 分 别 累 加Map任 务 的 结 果 39 b n 大 数 据 的 处 理X: Y:Z: 当 矩 阵 很 大 时 ， 可 用 MapReduce实 现 矩 阵 运 算 。 对 于 分 块 乘 ：1. Map任 务 计 算 两 块 的 乘 ， 用 结果 在 Z中 的 位 置 作 为 键2. Reduce任 务 按 键 值 来 分 别 累 加Map任 务 的 结 果 40 当 矩 阵 很 大 时 ， 可 用 MapReduce实 现 矩 阵 运 算 。 对 于 分 块 乘 ：1. Map任 务 计 算 两 块 的 乘 ， 用 结果 在 Z中 的 位 置 作 为 键2. Reduce任 务 按 键 值 来 分 别 累 加Map任 务 的 结 果b n 大 数 据 的 处 理X: Y:Z: 41 b n 大 数 据 的 处 理X: Y:Z: 当 矩 阵 很 大 时 ， 可 用 MapReduce实 现 矩 阵 运 算 。 对 于 分 块 乘 ：1. Map任 务 计 算 两 块 的 乘 ， 用 结果 在 Z中 的 位 置 作 为 键2. Reduce任 务 按 键 值 来 分 别 累 加Map任 务 的 结 果 42 b n 大 数 据 的 处 理X: Y:Z: 当 矩 阵 很 大 时 ， 可 用 MapReduce实 现 矩 阵 运 算 。 对 于 分 块 乘 ：1. Map任 务 计 算 两 块 的 乘 ， 用 结果 在 Z中 的 位 置 作 为 键2. Reduce任 务 按 键 值 来 分 别 累 加Map任 务 的 结 果 43 大 数 据 分 析 的 关 键 技 术要 挖 掘 大 数 据 的 大 价 值 ， 必 须 对 大 数 据 进 行 内 容上 的 分 析 与 计 算深 度 学 习 和 知 识 计 算 是 大 数 据 分 析 的 基 础 深 度 学 习 大 数 据 的 出 现 提 供 了 使 用 复 杂 （ 而 不 是 简 单 或浅 层 ） 的 模 型 来 有 效 地 表 征 和 解 释 数 据 的 机 会 深 度 学 习 就 是 利 用 层 次 化 的 架 构 学 习 出 对 象 在不 同 层 次 上 的 表 达 （ 例 :降 低 语 音 识 别 错 误 率 ） 近 几 年 ， 深 度 学 习 在 语 音 、 图 像 和 自 然 语 言 理解 等 应 用 领 域 取 得 重 大 进 展大 数 据 的 分 析 44 大 数 据 分 析 的 关 键 技 术要 挖 掘 大 数 据 的 大 价 值 ， 必 须 对 大 数 据 进 行 内 容上 的 分 析 与 计 算深 度 学 习 和 知 识 计 算 是 大 数 据 分 析 的 基 础 知 识 计 算 要 对 大 数 据 进 行 高 端 分 析 ， 就 需 要 从 大 数 据 中抽 取 出 有 价 值 的 知 识 并 将 其 构 建 成 可 支 持 查 询 、 分 析 和 计 算 的 知 识库 涉 及 知 识 库 的 构 建 、 多 源 知 识 的 融 合 和 知 识 库的 更 新 、 知 识 的 复 用大 数 据 的 分 析 45 大 数 据 的 分 析 大 数 据 分 析 的 关 键 技 术要 挖 掘 大 数 据 的 大 价 值 ， 必 须 对 大 数 据 进 行 内 容上 的 分 析 与 计 算 社 会 计 算 是 现 代 计 算 技 术 与 社 会 科 学 之 间 的 交 叉 学 科 它 是 指 面 向 社 会 活 动 、 社 会 过 程 、 社 会 结 构 、社 会 组 织 和 社 会 功 能 的 计 算 理 论 和 方 法 在 线 社 会 计 算 包 括 在 线 社 会 网 络 的 结 构 分 析 、信 息 传 播 模 型 以 及 信 息 内 容 的 分 析 、 建 模 与 挖 掘等 46 大 数 据 的 分 析 大 数 据 分 析 的 关 键 技 术要 挖 掘 大 数 据 的 大 价 值 ， 必 须 对 大 数 据 进 行 内 容上 的 分 析 与 计 算 可 视 化 可 视 化 不 仅 可 对 数 据 分 析 的 结 果 进 行 更 有 效 的展 示 ， 而 且 在 大 数 据 的 分 析 过 程 中 发 挥 重 要 作 用 不 同 于 传 统 的 信 息 可 视 化 ， 大 数 据 可 视 化 的 最大 挑 战 源 自 其 数 据 规 模 如 何 提 出 新 的 可 视 化 方 法 ， 它 能 够 帮 助 人 们 分析 大 规 模 、 高 维 度 、 多 来 源 、 动 态 演 化 的 信 息 ，并 辅 助 作 出 实 时 的 决 策 47 大 数 据 的 分 析 PageRank初 步 PageRank（ 网 页 排 名 ） 通 过 对 网 络 浩 瀚 的 超 链 接关 系 的 分 析 来 确 定 一 个 页 面 的 等 级 Google把 从 A页 面 到 B页 面 的 链 接 解 释 为 A页 面 给B页 面 投 票 ， B页 面 从 A页 面 的 投 票 能 得 多 少 分 还与 A页 面 的 等 级 有 关 一 个 页 面 的 PageRank， 由 所 有 给 它 投 票 的 页 面 的数 量 和 重 要 性 ， 经 过 迭 代 计 算 得 到 这 项 技 术 使 得 Google成 为 第 一 个 能 够 战 胜 作 弊 者的 搜 索 引 擎 。 当 然 ， 与 作 弊 者 之 间 的 斗 争 永 远 不会 停 止 48 大 数 据 的 分 析 PageRank初 步1. 早 期 搜 索 引 擎 与 词 项 作 弊 搜 索 引 擎 ： 词 项 出 现 在 网 页 头 部 比 在 普 通 正 文 的得 分 高 、 词 项 在 网 页 中 出 现 的 次 数 越 多 得 分 越 高 作 弊 者 ： 在 自 己 的 网 页 上 增 加 热 门 词 项 , 如 movie, 并 重 复 很 多 次 ， 以 提 高 与 movie的 相 关 性 。 词 项movie在 该 网 页 上 的 颜 色 与 背 景 色 一 样 ， 以 掩 盖 作弊 者 的 不 道 德 行 为 49 大 数 据 的 分 析 PageRank初 步2. Google的 对 策 使 用 PageRank技 术 来 模 拟 Web漫 游 者 的 行 为 ： 他们 从 随 机 页 面 出 发 ， 每 次 从 当 前 网 页 随 机 地 选 择出 链 前 行 ， 该 过 程 可 以 迭 代 多 次 。 最 终 ， 较 多 漫游 者 访 问 的 网 页 则 重 要 性 较 高 。 在 决 定 查 询 应 答顺 序 时 ， Google把 重 要 页 面 放 在 前 面 在 判 断 网 页 内 容 时 , 不 仅 考 虑 网 页 上 出 现 的 词 项 ，还 考 虑 有 链 接 指 向 该 网 页 的 网 页 中 所 使 用 的 词 项 50 大 数 据 的 分 析 PageRank初 步3. 最 简 单 的 PageRank举 例 PageRank： 网 页 集 实 数 ， 值 越 大 则 网 页 越 重 要 定 义 网 页 的 Web迁 移 矩 阵 M来 描 述 随 机 漫 游 者 的下 一 步 访 问 行 为例 ： 从 A出 发 ， 以 1/3的 概 率访 问 B、 C和D， 访 问 A的概 率 为 0 0 1/2 1 01/3 0 0 1/21/3 0 0 1/21/3 1/2 0 0A B C DM = A BC D 51 大 数 据 的 分 析 PageRank初 步3. 最 简 单 的 PageRank举 例 随 机 漫 游 者 位 置 的 概 率 分 布 可 通 过 一 个 n维 向 量 v来 描 述 ， 每 个 分 量 表 示 处 于 相 应 网 页 的 概 率例 (续 )： 假 定 处 于 各 网 页 的 初 始 概 率 相 等 Mkv是 随 机 漫 游 者 k步 后 的 概 率 分布 向 量 A BC D 0 1/2 1 01/3 0 0 1/21/3 0 0 1/21/3 1/2 0 0A B C DM = 1/41/41/41/4v 52 大 数 据 的 分 析 PageRank初 步3. 最 简 单 的 PageRank举 例 在 Web网 页 链 接 图 满 足 一 定 的 条 件 下 ， 概 率 分 布向 量 将 逼 近 一 个 极 限 分 布 ， 它 满 足 v = Mv 并 且 ， 若 分 布 向 量 各 分 量 之 和 为 1时 ， 方 程 v = Mv有 唯 一 解 在 常 规 情 况 下 ， 可 用 高 斯 消 去 法 解 方 程 v = Mv 在 实 际 情 况 下 ， 图 由 几 百 亿 甚 至 几 千 亿 个 节 点 组成 ， 高 斯 消 去 法 不 可 行 ， 原 因 在 于 其 时 间 复 杂 度是 方 程 个 数 的 三 次 方 若 迭 代 求 解 ， 每 轮 迭 代 的 时 间 复 杂 度 是 平 方 级 53 大 数 据 的 分 析 PageRank初 步3. 最 简 单 的 PageRank举 例 例 (续 )： 对 矩 阵 M进 行迭 代 计 算 ： 相 当 把 求 解方 程 v = Mv转 化 为 找 函 数v.Mv最 小 不 动 点 的 迭 代 过 程 A BC D9/245/245/245/24Mv 15/4811/4811/4811/48M2v 11/327/327/327/32M3v 3/92/92/92/9极 限 0 1/2 1 01/3 0 0 1/21/3 0 0 1/21/3 1/2 0 0A B C DM = 1/41/41/41/4v 54 大 数 据 的 分 析 PageRank初 步3. 最 简 单 的 PageRank举 例 需 要 基 于 MapReduce进行 PageRank的 迭 代 计 算 A BC D 3/92/92/92/99/245/245/245/24 15/4811/4811/4811/48 11/327/327/327/32 Mv M2v M3v 极 限 0 1/2 1 01/3 0 0 1/21/3 0 0 1/21/3 1/2 0 0A B C DM = 1/41/41/41/4v 55 小 结 本 讲 座 小 结 概 要 介 绍 了 大 数 据 的 基 本 概 念 和 特 点 、 大 数 据 时代 的 思 维 变 革 ， 大 数 据 的 处 理 和 分 析 技 术 面 临 的 挑 战 数 据 复 杂 ： 数 据 的 种 类 复 杂 、 结 构 复 杂 和 模 式 复杂 ， 使 得 数 据 感 知 、 表 达 、 理 解 和 计 算 都 面 临 挑 战 计 算 复 杂 ： 数 据 多 源 异 构 、 规 模 巨 大 、 快 速 多 变 , 使 传 统 的 机 器 学 习 、 信 息 检 索 和 数 据 挖 掘 都 显 不 足 系 统 复 杂 ： 对 处 理 系 统 的 系 统 架 构 、 计 算 框 架 、处 理 方 法 、 运 行 效 率 和 单 位 能 耗 等 都 有 挑 战 56 小 结 参 考 文 献 维 克 托 尔 耶 舍 恩 伯 格 等 ， 大 数 据 时 代 ： 生 活 、工 作 与 思 维 的 大 变 革 ， 浙 江 人 民 出 版 社 ， 2012 Anand Rajaraman等 , 大 数 据 ： 互 联 网 大 规 模 数 据挖 掘 与 分 布 式 处 理 ， 人 民 邮 电 出 版 社 ， 2012 程 学 旗 等 ， 大 数 据 系 统 和 分 析 技 术 综 述 ， 软 件 学报 ， 25(9):1889-1908, 2014 相 关 课 程 机 器 学 习 与 知 识 发 现 （ 研 ） 、 机 器 学 习 与 数 据 挖掘 前 沿 （ 研 ） 57