机器学习与数据挖掘

《机器学习与数据挖掘》由会员分享，可在线阅读，更多相关《机器学习与数据挖掘（57页珍藏版）》请在装配图网上搜索。

1、机器学习与数据挖掘基础 1.1 机 器 学 习 的 概 念 心 理 学 中 对 学 习 的 解 释 是 ： 学 习 是 指 （ 人 或 动 物 ） 依 靠 经验 的 获 得 而 使 行 为 持 久 变 化 的 过 程 。 Simon认 为 ： 如 果 一 个 系 统 能 够 通 过 执 行 某 种 过 程 而 改 进它 的 性 能 ， 这 就 是 学 习 。 Minsky认 为 ： 学 习 是 在 人 们 头 脑 中 （ 心 理 内 部 ） 进 行 有 用的 变 化 。 Tom M. Mitchell在 机 器 学 习 一 书 中 对 学 习 的 定 义 是 ：对 于 某 类 任 务 T和 性

2、 能 度 P， 如 果 一 个 计 算 机 程 序 在 T上 以 P衡 量 的 性 能 随 着 经 验 E而 自 我 完 善 ， 那 么 ， 我 们 称 这 个 计算 机 程 序 从 经 验 E中 学 习 。 当 前 关 于 机 器 学 习 的 许 多 文 献 中 也 大 都 认 为 ： 学 习 是 系 统积 累 经 验 以 改 善 其 自 身 性 能 的 过 程 。1 机 器 学 习 概 述 总 之 ： 学 习 与 经 验 有 关 ； 学 习 可 以 改 善 系 统 性 能 ； 学 习 是 一 个 有 反 馈 的 信 息 处 理 与 控 制 过 程 。 因为 经 验 是 在 系 统 与 环

3、境 的 交 互 过 程 中 产 生 的 ， 而经 验 中 应 该 包 含 系 统 输 入 、 响 应 和 效 果 等 信 息 。因 此 经 验 的 积 累 、 性 能 的 完 善 正 是 通 过 重 复 这 一过 程 而 实 现 的 。 1.2 机器学习系统的基本模型 模 型 中 包 含 学 习 系 统 的 四 个 基 本 组 成 环 节 。 环 境 和 知 识 库 是 以 某 种 知 识 表 示 形 式 表 达 的 信 息 的 集 合 ，分 别 代 表 外 界 信 息 来 源 和 系 统 具 有 的 知 识 。 学 习 环 节 和 执 行 环 节 代 表 两 个 过 程 。 学 习 环 节

4、处 理 环 境 提供 的 信 息 ， 以 便 改 善 知 识 库 中 的 显 式 知 识 。 执 行 环 节 利 用知 识 库 中 的 知 识 来 完 成 某 种 任 务 ， 并 把 执 行 中 获 得 的 信 息回 送 给 学 习 环 节 。 1.2 机器学习系统的基本模型 环 境 可 以 是 系 统 的 工 作 对 象 ， 也 可 以 包 括 工 作 对象 和 外 界 条 件 。 例 如 在 医 疗 系 统 中 ， 环 境 就 是 病人 当 前 的 症 状 、 检 验 的 数 据 和 病 历 。 在 模 式 识 别中 ， 环 境 就 是 待 识 别 的 图 形 或 景 物 。 学 习 环

5、节 通 过 获 得 外 部 信 息 ， 并 将 这 些 信 息 与 执行 环 节 所 反 馈 回 的 信 息 进 行 比 较 。 一 般 情 况 下 环境 提 供 的 信 息 水 平 与 执 行 环 节 所 需 的 信 息 水 平 之间 往 往 有 差 距 ， 经 分 析 、 综 合 、 类 比 、 归 纳 等 思维 过 程 ， 学 习 环 节 就 要 从 这 些 差 距 中 获 取 相 关 对象 的 知 识 ， 并 将 这 些 知 识 存 入 知 识 库 中 。1.2 机器学习系统的基本模型 知 识 库 用 于 存 放 由 学 习 环 节 所 学 到 的 知 识 。 影 响 学 习 系 统

6、设 计 的 第 二 个 因 素 是 知 识 库 的 形 式和 内 容 。 知 识 库 的 形 式 就 是 知 识 表 示 的 形 式 （ 一阶 谓 词 逻 辑 、 产 生 式 规 则 、 框 架 、 语 义 网 络 、 类和 对 象 、 模 糊 集 合 、 贝 叶 斯 网 络 、 脚 本 、 过 程等 ） 。 选 择 知 识 表 示 方 法 要 考 虑 下 列 准 则 ： 可 表达 性 、 推 理 难 度 、 可 修 改 性 和 可 扩 充 性 。1.2 机器学习系统的基本模型 执 行 环 节 是 整 个 机 器 学 习 系 统 的 核 心 。 执行 环 节 用 于 处 理 系 统 面 临 的

7、 现 实 问 题 ， 即应 用 知 识 库 中 所 学 到 的 知 识 求 解 问 题 ， 并对 执 行 的 效 果 进 行 评 价 ， 将 评 价 的 结 果 反馈 回 学 习 环 节 ， 以 便 系 统 进 一 步 的 学 习 。1.2 机器学习系统的基本模型 1. 基 于 学 习 策 略 的 分 类机 械 学 习传 授 学 习类 比 学 习归 纳 学 习基 于 解 释 的 学 习1.3 机 器 学 习 的 分 类 机械学习 机 械 学 习 (Rote Learning)又 叫 做 记 忆 学 习 ， 或 死记 硬 背 学 习 。 机 械 学 习 就 是 记 忆 ， 把 新 知 识 储 存

8、 起 来 ， 需 要 时对 储 存 的 知 识 进 行 检 索 ， 而 不 再 需 要 计 算 和 推 理 。 机 械 学 习 模 式 ： 设 系 统 的 输 入 模 式 为 (X1， X2， ， Xn)， 对 应 的 输 出模 式 为 (Y1， Y2 ， Ym)。 把 每 次 的 输 入 输 出 数 据 存储 起 来 ， 形 成 输 入 输 出 模 式 集 合 (X1， X2， ， Xn)，(Y1， Y2， ， Ym)， 使 用 时 根 据 给 定 的 输 入 数 据 ，直 接 查 找 、 检 索 输 出 。 传 授 式 学 习 传 授 学 习 (Learning by Being Told

9、或Learning by Instruction)又 称 为 指 点 学习 。 这 时 ， 环 境 提 供 的 信 息 较 抽 象 ， 水 平 较 高 ，学 习 环 节 把 这 些 信 息 变 换 成 执 行 环 节 使 用的 较 低 水 平 的 信 息 。 传 授 式 学 习 McCarthy 1958年 计 划 建 立 一 个 接 收 建 议 的系 统 ， 系 统 可 以 接 受 专 家 的 建 议 并 用 于 规划 某 一 领 域 的 行 动 。 20世 纪 70年 代 后 期 ，开 始 研 究 接 收 专 家 建 议 ， 改 进 专 家 系 统 的工 作 。 1980-1981年 Ha

10、yes Roth提 出 自 动 接 收 建 议过 程 。 传 授 式 学 习 1.要 求 请 求 专 家 提 出 建 议 。 有 时 对 专 家 的 要 求 是 简 单 的 ， 即请 专 家 提 供 一 般 的 建 议 。 有 时 ， 对 专 家 的 要 求 是 复 杂的 ， 即 请 专 家 识 别 知 识 库 的 欠 缺 ， 并 提 出 修 改 方 法 。有 些 系 统 是 被 动 的 ， 它 消 极 等 待 专 家 提 出 建 议 。 有 些系 统 是 主 动 的 ， 它 把 专 家 注 意 力 引 向 特 定 的 问 题 。 2.解 释 这 是 把 专 家 建 议 转 成 内 部 表 示

11、 ， 是 知 识 表 示 问 题 。 内部 表 示 应 包 含 建 议 的 全 部 信 息 。 如 果 用 自 然 语 言 提 出建 议 ， 解 释 过 程 应 包 括 自 然 语 言 理 解 。 传 授 式 学 习 3. 实 用 化这 是 传 授 学 习 的 信 息 变 换 过 程 ， 它 把 抽 象 的 建议 转 成 具 体 的 知 识 。 实 用 化 过 程 类 似 于 自 动 程序 设 计 。 前 者 由 建 议 得 到 实 用 的 规 则 ， 后 者 由程 序 说 明 得 到 程 序 。 二 者 也 存 在 差 别 。 后 者 要求 得 到 完 全 正 确 的 程 序 ， 强 调 程

12、 序 的 正 确 性 。前 者 往 往 使 用 弱 方 法 ， 不 保 证 完 全 正 确 。 实 用化 过 程 有 时 作 试 探 性 的 假 设 和 近 似 ， 只 能 要 求其 合 理 性 。 得 到 的 假 设 还 要 经 过 检 验 和 修 改 。 传 授 式 学 习 4. 归 并将 新 知 识 加 入 知 识 库 。 学 习 系 统 往 往 是 非 单 调系 统 ， 新 知 识 加 入 知 识 库 时 ， 需 要 检 查 并 保 证知 识 的 相 容 性 。 5. 评 价实 用 化 过 程 得 到 的 新 知 识 往 往 只 是 假 设 ， 要 经过 验 证 和 修 改 ， 即 需

13、 要 进 行 评 价 。 如 果 评 价 中发 现 了 问 题 ， 就 需 要 进 行 间 题 分 析 和 知 识 库 修改 。 实 用 化 是 整 个 学 习 过 程 的 核 心 。 类 比 学 习 类 比 学 习 (Learning by Analogy)是 获 取 新 概 念 或 新 技 巧的 方 法 ， 它 把 类 似 这 些 新 概 念 或 新 技 巧 的 已 知 知 识 转 换 为适 于 新 情 况 的 形 式 。 类 比 学 习 的 第 一 步 是 从 记 忆 中 找 到 类 似 的 概 念 或 技 巧 ， 第二 步 是 把 它 们 转 换 为 新 形 式 以 便 用 于 新 情

14、 况 。 例 如 人 类 的 一 种 学 习 方 式 是 先 由 老 师 教 学 生 解 例 题 (先 例 )，再 给 学 生 留 习 题 。 学 生 寻 找 在 例 题 和 习 题 间 的 对 应 关 系 ，利 用 解 决 例 题 的 知 识 去 解 决 习 题 中 的 问 题 。 学 生 经 过 一 般化 归 纳 推 出 原 理 ， 以 便 以 后 使 用 。 这 种 类 比 学 习 方 式 是 人类 常 用 的 。 归 纳 学 习 归 纳 学 习 的 定 义 （ 1） 归 纳 （ induction） 是 人 类 拓 展 认 识 能 力 的 重 要方 法 ， 是 一 种 从 个 别 到

15、一 般 的 ， 从 部 分 到 整 体 的 推 理行 为 。 （ 2） 归 纳 推 理 是 应 用 归 纳 方 法 ， 从 足 够 多 的 具 体 事 例中 归 纳 出 一 般 性 知 识 ， 提 取 事 物 的 一 般 规 律 ； 它 是 一种 从 个 别 到 一 般 的 推 理 。 （ 3） 归 纳 学 习 （ induction learning） 是 应 用 归 纳 推理 进 行 学 习 的 一 种 方 法 。 根 据 归 纳 学 习 有 无 教 师 指 导 ，可 把 它 分 为 示 例 学 习 和 观 察 与 发 现 学 习 。 前 者 属 于 有导 师 学 习 ， 后 者 属 于

16、无 导 师 学 习 。 归 纳 学 习 示 例 学 习 示 例 学 习 (Learning From Examples)， 也 叫 做 实 例 学习 ， 从 例 子 中 学 习 。 实 例 学 习 是 典 型 的 归 纳 学 习 ， 是目 前 较 成 熟 的 学 习 方 法 之 一 。 实 例 学 习 能 从 环 境 获 取 一 些 关 于 某 个 概 念 的 实 例 ， 实例 由 老 师 准 备 好 ， 并 根 据 需 要 划 分 为 正 例 和 反 例 ， 学习 系 统 根 据 这 些 实 例 进 行 归 纳 推 理 ， 得 出 关 于 这 个 概念 的 一 般 性 规 则 (知 识 )。

17、 提 供 给 系 统 的 实 例 通 常 是 非 常 具 体 的 、 低 级 的 信 息 ，系 统 经 过 学 习 环 节 归 纳 出 概 括 的 、 高 水 平 的 信 息 ， 即规 则 (知 识 )， 并 能 使 用 学 到 的 知 识 指 导 以 后 的 执 行 行为 。 归 纳 学 习 示 例 学 习 例 如 ， 如 果 我 们 用 一 批 动 物 作 为 实 例 ， 并 且 告 诉 学 习系 统 哪 一 个 动 物 是 “ 马 ” ， 哪 一 个 动 物 不 是 ， 当 实 例足 够 多 时 ， 学 习 系 统 就 能 一 般 出 关 于 “ 马 ” 的 概 念 模型 ， 使 自 己

18、 能 识 别 马 ， 并 且 能 把 马 与 其 它 动 物 区 别 开来 ， 这 一 学 习 过 程 就 是 实 例 学 习 。 Simon和 Lea 1974年 提 出 实 例 学 习 的 两 空 间 模 型 ： 例 子空 间 和 规 则 空 间 归 纳 学 习 观 察 与 发 现 学 习观 察 发 现 学 习 又 称 为 描 述 性 概 括 ， 其 目 标 是 确定 一 个 定 律 或 理 论 的 一 般 性 描 述 ， 刻 画 观 察 集 ，指 定 某 类 对 象 的 性 质 。 观 察 发 现 学 习 可 分 为 观察 学 习 与 机 器 发 现 两 种 。 前 者 用 于 对 事

19、例 进 行聚 类 ， 形 成 概 念 描 述 ； 后 者 用 于 发 现 规 律 ， 产生 定 律 或 规 则 。 归 纳 学 习 观 察 与 发 现 学 习概 念 聚 类概 念 聚 类 就 是 一 种 观 察 学 习 ； 人 类 观 察 周 围 的 事 物 ，对 比 各 种 物 体 的 特 性 ， 把 它 们 划 分 成 动 物 、 植 物 和非 生 物 ， 并 给 出 每 一 类 的 定 义 。 这 种 把 观 察 的 事 物划 分 成 几 类 并 建 立 相 应 概 念 的 过 程 就 是 概 念 聚 类 。发 现 学 习发 现 学 习 是 由 系 统 的 初 始 知 识 和 观 察 的

20、 数 据 学 习 数学 、 物 理 和 化 学 等 方 面 的 概 念 和 规 律 。 它 也 使 用 归纳 推 理 ， 但 是 在 学 习 过 程 中 除 了 初 始 知 识 外 施 教 者不 进 行 指 导 ， 所 以 它 也 是 无 导 师 的 归 纳 学 习 。 基于解释的学习 基 于 解 释 学 习 (ExplanationBased Learning)： 通 过 运 用 相 关 的 领 域 知 识 及 一个 训 练 实 例 ， 对 某 个 目 标 概 念 进 行 学 习 ，最 终 得 到 这 个 目 标 概 念 的 一 般 描 述 (形 式 化表 示 的 一 般 知 识 )。 基于

21、解释的学习 提 出 基 于 解 释 学 习 的 动 因 ： (1)人 们 经 常 能 从 观 察 或 执 行 的 单 个 实 例 中 得 到 一 个 一般 性 的 概 念 或 规 则 (2)归 纳 学 习 是 人 类 常 用 的 学 习 方 法 ， 但 由 于 归 纳 方 法在 学 习 中 ， 靠 领 域 知 识 来 帮 助 分 析 、 判 断 实 例 的 的 属性 ， 仅 仅 通 过 实 例 间 的 比 较 来 提 取 共 性 ， 这 是 无 法 保证 推 理 的 正 确 性 的 原 因 之 一 。 而 基 于 解 释 学 习 在 学 习过 程 中 运 用 领 域 知 识 对 实 例 进 行

22、 分 析 、 解 释 从 而避 免 类 似 问 题 的 发 生 。 (3)由 于 基 于 解 释 学 习 只 需 要 一 两 个 实 例 ， 有 望 提 高 学习 的 效 率 。 2. 基 于 学 习 方 式 的 分 类（ 1） 有 导 师 学 习 （ 监 督 学 习 ） ： 输 入 数 据 中 有 导 师信 号 ， 以 概 率 函 数 、 代 数 函 数 或 人 工 神 经 网 络 为基 函 数 模 型 ， 采 用 迭 代 计 算 方 法 ， 学 习 结 果 为 函数 。（ 2） 无 导 师 学 习 （ 非 监 督 学 习 ） ： 输 入 数 据 中 无 导师 信 号 ， 采 用 聚 类 方

23、 法 ， 学 习 结 果 为 类 别 。 典 型的 无 导 师 学 习 有 发 现 学 习 、 聚 类 、 竞 争 学 习 等 。（ 3） 强 化 学 习 （ 增 强 学 习 ） ： 以 环 境 反 馈 （ 奖 /惩信 号 ） 作 为 输 入 ， 以 统 计 和 动 态 规 划 技 术 为 指 导的 一 种 学 习 方 法 。 3. 基 于 数 据 形 式 的 分 类（ 1） 结 构 化 学 习 ： 以 结 构 化 数 据 为 输 入 ， 以 数 值 计算 或 符 号 推 演 为 方 法 。 典 型 的 结 构 化 学 习 有 神 经网 络 学 习 、 统 计 学 习 、 决 策 树 学 习

24、、 规 则 学 习 。（ 2） 非 结 构 化 学 习 ： 以 非 结 构 化 数 据 为 输 入 ， 典 型的 非 结 构 化 学 习 有 类 比 学 习 、 案 例 学 习 、 解 释 学习 、 文 本 挖 掘 、 图 像 挖 掘 、 Web挖 掘 等 。 4. 基 于 学 习 目 标 的 分 类 （ 1） 概 念 学 习 ： 即 学 习 的 目 标 和 结 果 为 概 念 ， 或 者 说 是 为 了获 得 概 念 的 一 种 学 习 。 典 型 的 概 念 学 习 有 示 例 学 习 。 （ 2） 规 则 学 习 ： 即 学 习 的 目 标 和 结 果 为 规 则 ， 或 者 说 是 为

25、 了获 得 规 则 的 一 种 学 习 。 典 型 的 规 则 学 习 有 决 策 树 学 习 。 （ 3） 函 数 学 习 ： 即 学 习 的 目 标 和 结 果 为 规 则 ， 或 者 说 是 为 了获 得 函 数 的 一 种 学 习 。 典 型 的 函 数 学 习 有 神 经 网 络 学 习 。 （ 4） 类 别 学 习 ： 即 学 习 的 目 标 和 结 果 为 对 象 类 ， 或 者 说 是 为了 获 得 类 别 的 一 种 学 习 。 典 型 的 类 别 学 习 有 聚 类 分 析 。 （ 5） 贝 叶 斯 网 络 学 习 ： 即 学 习 的 目 标 和 结 果 是 贝 叶 斯 网

26、 络 ，或 者 说 是 为 了 获 得 贝 叶 斯 网 络 的 一 种 学 习 。 其 又 可 分 为 结 构 学习 和 参 数 学 习 。 2 知识发现与数据挖掘 数 据 挖 掘 （ Data Mining） 从 大 量 的 、 不 完 全 的 、有 噪 声 的 、 模 糊 的 、 随 机 的 实 际 应 用 数 据 中 ， 提取 隐 含 在 其 中 的 、 人 们 事 先 不 知 道 的 、 但 又 是 潜在 有 用 的 信 息 和 知 识 的 过 程 。 与 之 相 似 的 概 念 称为 知 识 发 现 。 知 识 发 现 （ Knowledge Discovery in Databas

27、es）是 用 数 据 库 管 理 系 统 来 存 储 数 据 ， 用 机 器 学 习 的方 法 来 分 析 数 据 ， 挖 掘 大 量 数 据 背 后 隐 藏 的 知 识 ，称 为 数 据 库 中 的 知 识 发 现 。 。 Data Mining: A KDD Process Data miningcore of knowledge discovery process（ 数 据 挖 掘 知 识 挖 掘 的 核 心 ）Data Cleaning数 据 清 洗 Data Integration（ 数 据 集 成 ）Databases（ 数 据 库 ）Data Warehouse数 据 仓 库 T

28、ask-relevant Data任 务 相 关 数 据Selection选 择 Data Mining数 据 挖 掘 Pattern Evaluation模 式 评 估 Steps of a KDD Process 了 解 应 用 领 域 创 建 目 标 数 据 集 :选 择 数 据 数 据 清 理 和 预 处 理 :(这 个 可 能 要 占 全 过 程 60%的 工 作 量 ) 数 据 缩 减 和 变 换 选 择 数 据 挖 掘 的 功 能 选 择 挖 掘 算 法 数 据 挖 掘 :寻 找 感 兴 趣 的 模 式 模 式 评 估 和 知 识 表 示 运 用 发 现 的 知 识 数据挖掘功能

29、数 据 挖 掘 任 务 有 两 类 ： 第 一 类 是 描 述 性 挖 掘 任 务 ： 刻 划 数 据 库 中数 据 的 一 般 特 性 ； 第 二 类 是 预 测 性 挖 掘 任 务 ： 在 当 前 数 据 上进 行 推 断 ， 以 进 行 预 测 。 概念 / 类描述：特征化和区分 概 念 / 类 描 述 (class / concept description)：用 汇 总 的 、 简 洁 的 、 精 确 的 方 式 描 述 每 个类 和 概 念 。数 据 特 征 化 (data characterization) ： 是 目 标 类 数据 的 一 般 特 征 或 特 性 的 汇 总 。

30、 其 中 数 据 特 征 的输 出 形 式 有 ： 饼 图 、 条 图 、 曲 线 、 多 维 数 据 立方 体 、 多 维 表 等 。数 据 区 分 (Data discrimination) ： 是 将 目 标 类 对象 的 一 般 特 性 与 一 个 或 多 个 对 比 类 对 象 的 一 般特 性 比 较 。 关联分析（ 1） 定 义 ： 关 联 分 析 (association analysis)： 发 现关 联 规 则 ， 这 些 规 则 展 示 “ 属 性 值 ” 频 繁 地 在 给定 数 据 集 中 一 起 出 现 的 条 件 。（ 2） 实 例 age(x, “20.29”)

31、 income(X, “20K.29K”) buys(X, “CD_player”) support = 2%, confidence = 60%Diaper Beer 0.5%, 75% 分类和预测（ 1） 定 义分 类 (classification)： 通 过 构 造 模 型 (或 函数 )用 来 描 述 和 区 别 类 或 概 念 ， 用 来 预 测 类 型标 志 未 知 的 对 象 类 。（ 2） 分 类 模 型 的 导 出 方 式分 类 规 则 （ IF-THEN） 、 决 策 树 、 数 学 公 式 、神 经 网 络 等 。 聚类分析（ 1） 定 义聚 类 (clustering

32、)： 将 类 似 的 数 据 归 类 到 一起 ， 形 成 一 个 新 的 类 别 进 行 分 析 。（ 2） 聚 类 或 分 组 的 原 则“ 最 大 化 类 内 的 相 似 性 、 最 小 化 类 间 的 相 似 性 ”对 象 的 簇 （ 聚 类 ） 的 形 成 办 法 为 ： 使 得 在 一 个簇 中 的 对 象 具 有 很 高 的 相 似 性 ， 而 与 其 它 簇 中的 对 象 很 不 相 似 。 所 形 成 的 每 个 簇 可 以 看 作 一个 对 象 类 ， 由 它 可 以 导 出 规 则 。 May 24, 2021 Data Mining: Concepts and Tech

33、niques 35 分类一个两步的过程 Step 1: 建 立 描 述 预 先 定 义 的 数 据 类 或 概 念 集 的分 类 器 假 设 每 一 元 组 /样 本 属 于 一 个 预 定 的 类 ,由 一 个 类 标 号 属 性 的 属 性确 定 用 来 建 立 模 型 的 元 组 集 被 称 为 训 练 样 本 集 模 型 可 用 分 类 规 则 ,决 策 树 或 数 学 公 式 表 示 Step 2:模 型 的 使 用 : 为 了 分 类 将 来 或 未 知 的 对象 评 估 模 型 的 准 确 性 对 于 每 个 测 试 样 本 ,将 已 知 的 的 类 标 号 和 该 样 本 的

34、模 型 分 类 结果 进 行 比 较 准 确 率 是 正 确 被 模 型 分 类 的 测 试 样 本 的 百 分 比 测 试 集 独 立 于 样 本 集 ,否 则 会 出 现 过 分 适 合 的 现 象 May 24, 2021 Data Mining: Concepts and Techniques 36 分类过程(1):建立模型训练数据 NAME RANK YEARS TENUREDMike Assistant Prof 3 no Mary Assistant Prof 7 yesBill Professor 2 yes Jim Associate Prof 7 yesDave Assis

35、tant Prof 6 no Anne Associate Prof 3 no 分类算法IF rank = professorOR years 6THEN tenured = yes 分类规则(模型) May 24, 2021 Data Mining: Concepts and Techniques 37 分类过程(2):使用模型进行分类分类规则训练数据 NAME RANK YEARS TENUREDTom Assistant Prof 2 no Merlisa Associate Prof 7 noGeorge Professor 5 yes Joseph Assistant Prof 7

36、yes 新数据(Jeff, Professor, 4)Tenured? 用决策树归纳分类 决 策 树 一 个 类 似 于 流 程 图 的 数 结 构 内 部 节 点 表 示 一 个 属 性 上 的 测 试 每 个 分 支 代 表 一 个 测 试 的 输 出 叶 结 点 代 表 类 或 类 分 布 决 策 树 的 生 成 包 括 两 个 过 程 树 的 建 构 首 先 所 有 的 训 练 样 本 都 在 根 结 点 基 于 所 选 的 属 性 循 环 的 划 分 样 本 树 剪 枝 识 别 和 删 除 哪 些 反 应 映 噪 声 或 孤 立 点 的 分 支 决 策 树 的 使 用 :为 一 个

37、未 知 的 样 本 分 类 在 决 策 树 上 测 试 样 本 的 属 性 值May 24, 2021 Data Mining: Concepts and Techniques 38 May 24, 2021 Data Mining: Concepts and Techniques 39 训练数据集 age income student credit_rating buys_computer =30 high no fair no 40 medium no fair yes 40 low yes fair yes 40 low yes excellent no 3140 low yes exc

38、ellent yes =30 medium no fair no 40 medium yes fair yes 40 medium no excellent no This follows an example of Quinlans ID3 (Playing Tennis) May 24, 2021 Data Mining: Concepts and Techniques 40 概念“buys_computer”的决策树的输出age?overcaststudent? credit rating?40no yes yesyes31.40 no fairexcellentyesno May 24

39、, 2021 Data Mining: Concepts and Techniques 41 决策树归纳的算法 基 本 算 法 以 自 顶 向 下 递 归 的 各 个 击 破 方 式 构 造 决 策 树 首 先 ,所 有 的 训 练 样 本 都 在 根 结 点 所 有 属 性 都 是 分 类 的 (如 果 值 是 连 续 的 ,它 们 应 预 先 被 离散 化 ) 基 于 所 选 属 性 递 归 的 划 分 样 本 在 启 发 式 或 统 计 度 量 的 基 础 上 选 择 测 试 属 性 (例 如 ,信 息增 益 ) 停 止 划 分 的 条 件 给 定 节 点 的 所 有 样 本 属 于 同

40、 一 个 类 没 有 剩 余 属 性 可 以 用 来 进 一 步 划 分 样 本 -使 用 多 数 表 决来 分 类 叶 节 点 没 有 剩 余 的 样 本 属性选择度量 信 息 增 益 (ID3/C4.5) 所 有 的 属 性 值 被 假 定 为 分 类 的 修 正 后 可 以 用 在 连 续 值 属 性 上 Giniindex (IBM IntelligentMiner) 所 有 的 属 性 被 假 定 为 连 续 值 假 定 对 每 个 属 性 存 在 一 些 可 能 的 分 裂 (split)值 需 要 一 些 其 他 的 工 具 ,像 聚 类 ,来 得 到 可 能 的 分 裂 值 修

41、 正 后 可 以 用 在 分 类 属 性 上 May 24, 2021 Data Mining: Concepts and Techniques 43 信息增益(ID3/C4.5)n 选 择 具 有 高 信 息 增 益 的 属 性n 假 定 有 两 个 类 ,P和 Nn 假 定 样 本 集 S包 含 类 P的 p个 元 素 和 类 N的 n个 元 素n 如 果 S中 任 意 的 例 子 属 于 P或 N， 则 需 要 决 定 的 信 息 数 量被 定 义 为 决策树归纳的信息增益 假 设 用 属 性 A将 集 合 S被 划 分 为 V个 子 集 S1, S2, , Sv 如 果 Si包 含 P

42、中 的 pi个 样 本 和 N中 的 ni个 样 本 , 则 熵 , 或 所 有 用 来 分 类 所 有 子 树 Si中 对 象 的期 望 信 息 由 以 下 式 给 出 ： 由 A上 分 支 将 获 得 编 码 信 息 May 24, 2021 Data Mining: Concepts and Techniques 45 Attribute Selection: Information Gaing类 P: buys_computer = “yes”g类 N: buys_computer = “no” means “age =30” has 5 out of 14 samples, with

43、 2 yeses and 3 nos. HenceSimilarly, 694.0)2,3(145 )0,4(144)3,2(145)( I IIageE 048.0)_( 151.0)( 029.0)( ratingcreditGain studentGain incomeGain 246.0)(),()( ageEnpIageGain age income student credit_rating buys_computer=30 high no fair no 40 medium no fair yes40 low yes fair yes 40 low yes excellent n

44、o3140 low yes excellent yes =30 medium no fair no40 medium yes fair yes40 medium no excellent no )3,2(145 I940.0)145(log145)149(log149)5,9(),( 22 InpI May 24, 2021 Data Mining: Concepts and Techniques 46 贝叶斯定理: Basics 设 X 是 数 据 样 本 (“证 据 ” ): 类 标 号 未 知 令 H 为 X属 于 类 C的 某 种 假 设 分 类 就 是 确 定 P(H|X)给 定 “

45、 证 据 ” 或 观 察 数 据 元 组 X，假 设 H成 立 的 概 率 P(H) (先 验 概 率 ), the initial probability E.g., X will buy computer, regardless of age, income, P(X): X的 先 验 概 率 P(X|H) (后 验 概 率 ), 假 设 H成 立 的 条 件 下 ， 观 察 数 据 样 本 X后验 概 率 E.g., Given that X will buy computer, the prob. that X is 31.40, medium income May 24, 2021

46、Data Mining: Concepts and Techniques 47 贝叶斯定理 Given training data X, posteriori probability of a hypothesis H, P(H|X), follows the Bayes theorem 如 果 概 率 P(Ci|X) 是 K类 的 所 有 P(Ck|X)中 最 高 的 ， 则 可 预测 X 属 于 Ci )( )()|()|( XXX P HPHPHP May 24, 2021 Data Mining: Concepts and Techniques 48 朴素贝叶斯分类 设 D是 训 练

47、元 组 和 相 关 联 的 类 标 号 的 集 合 。 每 个 元 组 用 一个 n维 属 性 向 量 X = (x1, x2, , xn)表 示 假 定 有 m个 类 C1, C2, , Cm. 分 类 法 将 预 测 X属 于 具 有 最 高 后 验 概 率 （ 条 件 X下 ） 的 类 , i.e., 最 大 化 P(Ci|X) 根 据 贝 叶 斯 定 理 由 于 P(X) 对 于 所 有 类 为 常 数 , 只 需 要 最 大 即 可 )( )()|()|( XXX P iCPiCPiCP )()|()|( iCPiCPiCP XX May 24, 2021 Data Mining:

48、Concepts and Techniques 49 朴素贝叶斯分类 朴 素 假 定 : 假 定 属 性 值 有 条 件 地 相 互 独 立 (i.e., 属 性间 不 存 在 依 赖 关 系 ): 这 大 大 减 少 了 计 算 开 销 ， 如 果 Ak 是 分 类 属 性 , 则 P(xk|Ci) 是 D中 属 性 Ak的 值 为 xk 的 Ci类 的 元 组 除 以 D中 Ci类 的 元 组 数|Ci, D| )|(.)|()|(1 )|()|( 21 CixPCixPCixPnk CixPCiP nk X May 24, 2021 Data Mining: Concepts and T

49、echniques 50 朴素贝叶斯分类: 训练集Class:C1:buys_computer = yesC2:buys_computer = noData sample X = (age =30,Income = medium,Student = yesCredit_rating = Fair) May 24, 2021 Data Mining: Concepts and Techniques 51 Nave Bayesian Classifier: An Example P(Ci): P(buys_computer = “yes”) = 9/14 = 0.643 P(buys_comput

50、er = “no”) = 5/14= 0.357 Compute P(X|Ci) for each class P(age = “=30” | buys_computer = “yes”) = 2/9 = 0.222 P(age = “= 30” | buys_computer = “no”) = 3/5 = 0.6 P(income = “medium” | buys_computer = “yes”) = 4/9 = 0.444 P(income = “medium” | buys_computer = “no”) = 2/5 = 0.4 P(student = “yes” | buys_

51、computer = “yes) = 6/9 = 0.667 P(student = “yes” | buys_computer = “no”) = 1/5 = 0.2 P(credit_rating = “fair” | buys_computer = “yes”) = 6/9 = 0.667 P(credit_rating = “fair” | buys_computer = “no”) = 2/5 = 0.4 X = (age = 30 , income = medium, student = yes, credit_rating = fair) P(X|Ci) : P(X|buys_c

52、omputer = “yes”) = 0.222 x 0.444 x 0.667 x 0.667 = 0.044 P(X|buys_computer = “no”) = 0.6 x 0.4 x 0.2 x 0.4 = 0.019P(X|Ci)*P(Ci) : P(X|buys_computer = “yes”) * P(buys_computer = “yes”) = 0.028 P(X|buys_computer = “no”) * P(buys_computer = “no”) = 0.007Therefore, X belongs to class (“buys_computer = y

53、es”) May 24, 2021 Data Mining: Concepts and Techniques 52 什么是聚类分析? 聚 类 （ 簇 ） ： 数 据 对 象 的 集 合 在 同 一 个 聚 类 （ 簇 ） 中 的 对 象 彼 此 相 似 不 同 簇 中 的 对 象 则 相 异 聚 类 分 析 将 物 理 或 抽 象 对 象 的 集 合 分 组 成 为 由 类 似 的 对 象 组 成 的多 个 类 的 过 程 聚 类 是 一 种 无 指 导 的 学 习 ： 没 有 预 定 义 的 类 编 号 聚 类 分 析 的 数 据 挖 掘 功 能 作 为 一 个 独 立 的 工 具 来 获

54、得 数 据 分 布 的 情 况 作 为 其 他 算 法 （ 如 ： 特 征 和 分 类 ） 的 预 处 理 步 骤 May 24, 2021 Data Mining: Concepts and Techniques 53 主要聚类方法 (I) 划 分 算 法 （ Partitioning approach ） 构 造 各 种 各 样 的 划 分 ,并 用 一 些 标 准 来 评 估 它 们 Typical methods: k-means, k-medoids, CLARANS 层 次 算 法 （ Hierarchical approach ） : 使 用 一 些 策 略 来 进 行 数 据

55、(或 对 象 )集 的 层 次 分 解 Typical methods: Diana, Agnes, BIRCH, ROCK, CAMELEON 基 于 密 度 的 方 法 （ Density-based approach） 基 于 连 续 和 密 度 函 数 Typical methods: DBSACN, OPTICS, DenClue May 24, 2021 Data Mining: Concepts and Techniques 54 主要聚类方法(II) 基 于 网 格 的 方 法 （ Grid-based approach ） : 基 于 多 层 粒 度 结 构 Typical

56、methods: STING, WaveCluster, CLIQUE 基 于 模 型 的 方 法 （ Model-based ） : 为 每 个 聚 类 假 设 一 个 模 型 ,寻 找 数 据 对 给 定 模 型 的 最 佳 拟 合 Typical methods: EM, SOM, COBWEB 基 于 频 繁 模 式 的 方 法 （ Frequent pattern-based ） : Based on the analysis of frequent patterns Typical methods: pCluster 用 户 指 导 或 基 于 约 束 的 方 法 （ User-g

57、uided or constraint-based ） : 结 合 用 户 指 定 和 面 向 应 用 的 约 束 进 行 聚 类 的 方 法 Typical methods: COD (obstacles), constrained clustering May 24, 2021 Data Mining: Concepts and Techniques 55 划分算法:基本概念 划 分 方 法 :把 具 有 n个 对 象 的 数 据 库 D构 造 成 具 有 k个簇 的 集 合 的 划 分 给 定 k， 找 出 有 k个 簇 的 一 个 划 分 使 得 所 选 择 的 划 分准 则 最 优

58、全 局 最 优 : 穷 举 所 有 可 能 的 划 分 启 发 式 方 法 : k-平 均 算 法 和 k-中 心 点 算 法k-平 均 算 法 （ k-means ） (MacQueen67): 每 个 簇 用 簇 的 中心 表 示 k-中 心 点 算 法 （ k-medoids） 或 围 绕 中 心 点 的 划 分 PAM (Partition around medoids) (Kaufman & Rousseeuw87): 每一 个 簇 用 接 近 聚 类 中 心 的 一 个 对 象 表 示 May 24, 2021 Data Mining: Concepts and Technique

59、s 56 K-平均聚类算法 给 定 k, k-平 均 算 法 由 以 下 四 步 来 完 成 :把 对 象 划 分 为 k个 非 空 的 子 集随 机 的 选 择 一 些 种 子 点 作 为 目 前 划 分 的 簇的 质 心 。 质 心 是 簇 的 中 心 （ 平 均 点 ）把 每 一 个 对 象 赋 给 最 近 的 种 子 点重 复 第 二 步 ， 直 到 没 有 新 的 分 配 May 24, 2021 Data Mining: Concepts and Techniques 57 K-平 均 聚类方 法 Example 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5

60、 6 7 8 9 10 0 123456789 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 012345678 910 0 1 2 3 4 5 6 7 8 9 10K=2Arbitrarily choose K object as initial cluster center Assign each objects to most similar center Update the cluster meansUpdate the cluster means reassignreassign