1999年5月31日
田 金 兰--李 奔 一 分 类 器 的 基 本 概 念 ----分 类 是 数 据 挖 掘 的 一 种 非 常 重 要 的 方 法。 分 类 的 概 念 是 在 已 有 数 据 的 基 础 上 学 会 一 个 分 类 函 数 或 构 造 出 一 个 分 类 模 型（ 即 我 们 通 常 所 说 的 分 类 器(Classifier)）。 该 函 数 或 模 型 能 够 把 数 据 库 中 的 数 据 纪 录 映 射 到 给 定 类 别 中 的 某 一 个， 从 而 可 以 应 用 于 数 据 预 测。 要 构 造 分 类 器， 需 要 有 一 个 训 练 样 本 数 据 集 作 为 输 入。 训 练 集(Training set) 由 一 组 数 据 库 纪 录 或 元 组 构 成， 每 个 纪 录 是 一 个 由 有 关 字 段 值 组 成 的 特 征 向 量， 我 们 把 这 些 字 段 称 做 属 性(Attribute)， 把 用 于 分 类 的 属 性 叫 做 标 签(Label)， 标 签 属 性 也 就 是 训 练 集 的 类 别 标 记。 一 个 具 体 的 样 本 的 形 式 可 以 表 示 为(v1, v2...... vn; c), 其 中vi 表 示 字 段 值，c 表 示 类 别。
----训 练 集 是 构 造 分 类 器 的 基 础。 训 练 集 是 包 含 一 些 属 性 的 一 个 数 据 库 表 格， 其 中 的 一 个 属 性 被 制 定 为 分 类 标 签。 标 签 属 性 的 类 型 必 须 是 离 散 的， 且 标 签 属 性 的 可 能 值 的 数 目 越 少 越 好（ 最 好 是 两 或 三 个 值）。 标 签 值 的 数 目 越 少， 构 造 出 来 的 分 类 器 的 错 误 率 越 低。
----从 训 练 集 中 自 动 地 构 造 出 分 类 器 的 算 法 叫 做 生 成 器(Inducer)。 在 生 成 分 类 器 后， 可 以 利 用 它 来 对 数 据 集 中 不 包 含 标 签 属 性 的 记 录 进 行 分 类， 标 签 属 性 的 值 也 可 以 用 分 类 器 来 预 测。 二 几 种 基 本 的 分 类 器 ----1. 决 策 树 分 类 器
----提 供 一 个 属 性 集 合， 决 策 树 通 过 在 属 性 集 的 基 础 上 作 出 一 系 列 的 决 策， 将 数 据 分 类。 这 个 过 程 类 似 于 通 过 一 个 植 物 的 特 征 来 辨 认 植 物。 可 以 应 用 这 样 的 分 类 器 来 判 定 某 人 的 信 用 程 度， 比 如， 一 个 决 策 树 可 能 会 断 定“ 一 个 有 家、 拥 有 一 辆 价 值 在1.5 万 到2.3 万 美 元 之 间 的 轿 车、 有 两 个 孩 子 的 人” 拥 有 良 好 的 信 用。 决 策 树 生 成 器 从 一 个“ 训 练 集” 中 生 成 决 策 树。 SGI 公 司 的 数 据 挖 掘 工 具MineSet 所 提 供 的 可 视 化 工 具 使 用 树 图 来 显 示 决 策 树 分 类 器 的 结 构， 在 图 中， 每 一 个 决 策 用 树 的 一 个 节 点 来 表 示。 图 形 化 的 表 示 方 法 可 以 帮 助 用 户 理 解 分 类 算 法， 提 供 对 数 据 的 有 价 值 的 观 察 视 角。 生 成 的 分 类 器 可 用 于 对 数 据 的 分 类。
----2. 选 择 树 分 类 器
----选 择 树 分 类 器 使 用 与 决 策 树 分 类 器 相 似 的 技 术 对 数 据 进 行 分 类。 与 决 策 树 不 同 的 是， 选 择 树 中 包 含 特 殊 的 选 择 节 点， 选 择 节 点 有 多 个 分 支。 比 如， 在 一 棵 用 于 区 分 汽 车 产 地 的 选 择 树 中 的 一 个 选 择 节 点 可 以 选 择 马 力、 汽 缸 数 目 或 汽 车 重 量 等 作 为 信 息 属 性。 在 决 策 树 中， 一 个 节 点 一 次 最 多 可 以 选 取 一 个 属 性 作 为 考 虑 对 象。 在 选 择 树 中 进 行 分 类 时， 可 以 综 合 考 虑 多 种 情 况。 选 择 树 通 常 比 决 策 树 更 准 确， 但 是 也 大 得 多。
----选 择 树 生 成 器 使 用 与 决 策 树 生 成 器 生 成 决 策 树 同 样 的 算 法 从 训 练 集 中 生 成 选 择 树。MineSet 的 可 视 化 工 具 使 用 选 择 树 图 来 显 示 选 择 树。 树 图 可 以 帮 助 用 户 理 解 分 类 器， 发 现 哪 个 属 性 在 决 定 标 签 属 性 值 时 更 重 要。 同 样 可 以 用 于 对 数 据 进 行 分 类。
----3. 证 据 分 类 器
----证 据 分 类 器 通 过 检 查 在 给 定 一 个 属 性 的 基 础 上 某 个 特 定 的 结 果 发 生 的 可 能 性 来 对 数 据 进 行 分 类。 比 如， 它 可 能 作 出 判 断， 一 个 拥 有 一 辆 价 值 在1.5 万 到2.3 万 美 元 之 间 的 轿 车 的 人 有70 ％ 的 可 能 是 信 用 良 好 的， 而 有30 ％ 的 可 能 是 信 用 很 差。 分 类 器 在 一 个 简 单 的 概 率 模 型 的 基 础 上， 使 用 最 大 的 概 率 值 来 对 数 据 进 行 分 类 预 测。
----与 决 策 树 分 类 器 类 似， 生 成 器 从 训 练 集 中 生 成 证 据 分 类 器。MineSet 的 可 视 化 工 具 使 用 证 据 图 来 显 示 分 类 器， 证 据 图 由 一 系 列 描 述 不 同 的 概 率 值 的 饼 图 组 成。 证 据 图 可 以 帮 助 用 户 理 解 分 类 算 法， 提 供 对 数 据 的 深 入 洞 察， 帮 助 用 户 回 答 像“ 如 果... 怎 么 样" 一 类 的 问 题。 同 样 可 以 用 于 对 数 据 进 行 分 类。 三 分 类 器 的 准 确 度 评 估 方 法 ----1. 影 响 一 个 分 类 器 错 误 率 的 因 素
----2. 评 估 方 法
----有 两 种 方 法 可 以 用 于 对 分 类 器 的 错 误 率 进 行 评 估， 它 们 都 假 定 待 预 测 记 录 和 训 练 集 取 自 同 样 的 样 本 分 布。
----(1) 保 留 方 法(Holdout)： 记 录 集 中 的 一 部 分 （ 通 常 是2/3） 作 为 训 练 集， 保 留 剩 余 的 部 分 用 作 测 试 集。 生 成 器 使 用2/3 的 数 据 来 构 造 分 类 器， 然 后 使 用 这 个 分 类 器 来 对 测 试 集 进 行 分 类， 得 出 的 错 误 率 就 是 评 估 错 误 率。
----虽 然 这 种 方 法 速 度 快， 但 由 于 仅 使 用2/3 的 数 据 来 构 造 分 类 器， 因 此 它 没 有 充 分 利 用 所 有 的 数 据 来 进 行 学 习。 如 果 使 用 所 有 的 数 据， 那 么 可 能 构 造 出 更 精 确 的 分 类 器。
----(2) 交 叉 纠 错 方 法(Cross ?validation)： 数 据 集 被 分 成k 个 没 有 交 叉 数 据 的 子 集， 所 有 子 集 的 大 小 大 致 相 同。 生 成 器 训 练 和 测 试 共k 次； 每 一 次， 生 成 器 使 用 去 除 一 个 子 集 的 剩 余 数 据 作 为 训 练 集， 然 后 在 被 去 除 的 子 集 上 进 行 测 试。 把 所 有 得 到 的 错 误 率 的 平 均 值 作 为 评 估 错 误 率。
----交 叉 纠 错 法 可 以 被 重 复 多 次(t)， 对 于 一 个t 次k 分 的 交 叉 纠 错 法，k ＊t 个 分 类 器 被 构 造 并 被 评 估， 这 意 味 着 交 叉 纠 错 法 的 时 间 是 分 类 器 构 造 时 间 的k ＊t 倍。 增 加 重 复 的 次 数 意 味 着 运 行 时 间 的 增 长 和 错 误 率 评 估 的 改 善。 我 们 可 以 对 k 的 值 进 行 调 整， 将 它 减 少 到3 或5， 这 样 可 以 缩 短 运 行 时 间。 然 而， 减 小 训 练 集 有 可 能 使 评 估 产 生 更 大 的 偏 差。
----通 常Holdout 评 估 方 法 被 用 在 最 初 试 验 性 的 场 合， 或 者 多 于5000 条 记 录 的 数 据 集； 交 叉 纠 错 法 被 用 于 建 立 最 终 的 分 类 器， 或 者 很 小 的 数 据 集。 四 MineSet 中 的 分 类 器 ----1. 决 策 树 分 类 器
----决 策 树 分 类 器 把 数 据 表 中 的 每 条 记 录 归 入 一 类， 用 于 分 类 的 结 构 是 一 棵 决 策 树。 对 于MineSet 工 具 来 说， 生 成 决 策 树 分 类 器 需 要 使 用 的 训 练 集 是 一 个ASCII 码 或 二 进 制 的 文 件， 或 者Oracle、Informix、Sybase 数 据 库 中 的 一 张 表。 要 使 用 分 类 器， 就 必 须 提 供 一 组 记 录， 这 些 记 录 具 有 被 分 类 器 使 用 的 那 些 属 性， 而 不 必 提 供 分 类 属 性。
----下 面 我 们 以 一 个 汽 车 数 据 集 为 例 来 说 明 如 何 产 生 决 策 树 分 类 器， 以 及 决 策 树 分 类 器 可 视 化 树 图 的 含 义。 汽 车 数 据 集 结 构 如 表 所 示。
----汽 车 数 据 集 包 括70 年 代 到80 年 代 早 期 不 同 模 式 的 汽 车 的 详 细 信 息。 我 们 挑 选 出Weight、Acceleration 和Mpg 等 字 段 作 为 属 性 字 段， 将 产 地 标 为 标 签 字 段。 在 得 到 这 样 一 个 数 据 集 以 后， 你 可 能 想 知 道 不 同 产 地 的 汽 车 的 特 征 是 什 么。 然 后 如 果 再 提 供 给 你 新 的 汽 车 数 据， 那 么 你 可 以 尝 试 根 据 它 的 特 征 判 断 出 其 产 地。
----在MineSet 工 具 中 我 们 可 以 构 造 一 棵 决 策 树 来 完 成 上 面 的 工 作。
----打 开 数 据 集 以 后，MineSet 自 动 将 唯 一 的 离 散 属 性Origin 属 性 作 为 标 签 属 性。 所 谓 离 散 属 性 是 指 具 有 有 限 数 目 值 的 属 性。 应 当 选 择 具 有 比 较 少 值 的 属 性 作 为 标 签 属 性， 两 个 或 者 三 个。 如 果 数 据 集 中 没 有 离 散 属 性， 则 必 须 使 用 工 具 管 理 器 中 的 数 据 转 换 功 能 来 生 成 离 散 属 性。
----在MineSet 工 具 箱 中 选 择 决 策 树 生 成 器， 选 取Classifrie ＆ Error 模 式， 并 且 对 决 策 树 生 成 器 的 一 些 选 项 进 行 配 置 后， 就 可 以 产 生 决 策 树 分 类 器。MineSet 的 可 视 化 工 具 将 自 动 显 示 生 成 的 决 策 树， 如 图1 所 示。
----决 策 树 由 连 线 连 接 的 节 点 组 成。 存 在 两 种 类 型 的 节 点： 决 策 节 点 和 叶 子 节 点。 决 策 节 点 指 定 在 该 节 点 被 检 验 的 属 性 的 属 性 值（ 或 范 围） 在 线 条 上 被 显 示 出 来， 每 一 种 可 能 的 值 和 一 条 线 一 一 对 应。 叶 子 节 点 指 定 一 个 类 别。
----每 个 节 点 上 的 垂 直 条 显 示 类 在 该 节 点 上 的 分 布。 每 个 节 点 的 基 石 具 有 自 己 的 高 度 和 颜 色。 高 度 对 应 到 达 这 个 节 点 的 训 练 集 的 权 重。 权 重 越 高， 在 每 个 节 点 上 的 类 分 布 就 越 可 靠。 基 石 上 的 颜 色 指 示 其 子 树 的 错 误 率 评 估， 红 色 代 表 高 错 误 率， 黄 色 表 示 中 等， 绿 色 表 示 低 错 误 率。 如 果 没 有 测 试 集 到 达 该 节 点， 则 用 黑 色 来 表 示， 这 样 就 没 有 错 误 率 评 估。
----指 向 一 个 节 点， 屏 幕 上 将 显 示 下 列 信 息：
----每 条 线 条 标 出 节 点 属 性 被 测 试 的 值（ 或 值 的 范 围）。
----从 图1 中 的 决 策 树 我 们 可 以 看 出，Cubic Inches 可 以 作 为 辨 别 美 国 产 汽 车 的 一 个 很 好 的 特 征。 大 引 擎（>169.5 Cubic inches） 的 汽 车 都 产 自 美 国， 而 小 引 擎 的 则 产 自 各 地。 根 节 点（ 它 表 示 整 个 训 练 集） 拥 有 更 多 的 美 国 产 汽 车（62.5 ％）， 而 在 以Cubic inches 为 基 准 作 一 次 划 分 后， 对 于 小 引 擎 的 汽 车 则 较 难 预 测 出 它 们 的 产 地， 根 节 点 的 纯 度 为16.2， 表 明 一 个 类（ 这 儿 是 美 国 产） 占 主 要 地 位。 右 节 点（Cubic inches >169.5） 的 纯 度 为96.81， 表 明 我 们 找 出 了 一 个 纯 度 很 高 的 子 分 布（ 几 乎 所 有 的 大 引 擎 汽 车 都 产 自 美 国）。 事 实 上， 右 节 点 的 错 误 率 估 计 为0 ％， 显 示 为 绿 色 基 石； 而 左 节 点 的 纯 度 为0.23， 错 误 率 也 要 高 得 多， 为31.25 ％， 基 石 为 橙 色。 小 引 擎 汽 车 的 分 类 比 原 始 数 据 集 要 困 难 得 多， 几 乎 每 一 类 的 数 量 都 是 一 样 的。
----2. 选 择 树 分 类 器
----选 择 树 分 类 器 将 每 条 记 录 都 归 入 一 个 类 中。 归 类 的 基 本 结 构 为 决 策 树。
----同 样 以 汽 车 数 据 集 为 例。 为 生 成 选 择 树， 我 们 在MineSet 中 打 开 汽 车 数 据 集， 选 择 选 择 树 生 成 器 和Classifier ＆ Error 模 式， 并 对 生 成 器 的 一 些 选 项 进 行 设 置， 以 微 调 选 择 树 生 成 算 法。 确 认 后 即 可 生 成 选 择 树 生 成 器，MineSet 将 自 动 启 动 可 视 化 工 具 显 示 选 择 树 图, 如 图2 所 示。
----选 择 树 通 过 选 择 节 点（Option Nodes） 对 通 常 的 决 策 树 进 行 扩 展。 选 择 节 点 显 示 了 在 树 中 的 一 个 决 策 节 点 能 作 出 的 几 种 选 择。 例 如， 在 图2 中， 根 节 点 是 一 个 具 有5 种 选 择 的 选 择 节 点： 引 擎 尺 寸、 汽 缸、 重 量、 每 加 仑 公 里 数、 产 地。
----选 择 节 点 提 供 两 个 功 能：
----(1) 通 过 显 示 可 以 作 出 的 几 种 选 择， 加 强 了 影 响 分 类 标 签 的 因 素 的 可 理 解 性。 不 同 于 决 策 树 的 一 个 节 点 一 个 属 性， 选 择 节 点 给 出 多 个 选 择。 在 选 择 树 上 浏 览 时， 可 以 选 择： 易 于 理 解 的 选 项； 根 据 以 前 的 经 验， 认 为 更 适 合 的 预 测 选 项； 基 于 错 误 率 估 计 的 选 项。
----在 图2 中， 可 以 因 为Cylinder 值 较 少 而 选 用 它， 或 由 于Weightlbs 估 计 错 误 率 低 而 选 用 它。 注 意 错 误 估 计 只 是 估 计， 一 般 而 言， 选 项 间 的 错 误 率 低 于 两 倍 方 差， 则 可 以 认 为 二 者 无 差 别。
----(2） 对 各 选 项 的 统 筹 估 计 可 以 减 少 误 差。 每 个 选 项 可 以 被 看 成 是 一 个“ 专 家” 提 出 的 建 议 方 向。 选 择 节 点 综 合 考 虑 了 多 个“ 专 家” 的 意 见 而 生 成 了 低 错 误 率 的 分 类 器。
----如 图2 所 示， 根 节 点 错 误 率 为0.76 ％， 比 各 个 子 节 点 都 低。 请 注 意， 该 训 练 集 不 一 定 包 含 所 有Brand 信 息（ 会 缺 一 些）， 对 所 缺 少 的， 选 择 树 猜 测 为 占 多 数 的 类（ 美 国 产）， 因 而 带 来 了 错 误。 而 考 虑 了 其 他 选 项 时， 错 误 率 被 平 均， 从 而 减 少 了 错 误。
----选 择 树 有 两 个 缺 点： 构 造 选 择 树 的 耗 时 是 决 策 树 的10 ～15 倍， 而 且 树 可 视 化 文 件 复 杂 度 高10 ～15 倍。 但 是 选 择 树 生 成 器 能 增 强 可 理 解 性， 降 低 错 误 率， 因 而 抵 消 了 上 述 缺 点。
----3 ． 生 成 器 运 行 模 式
----在MineSet 中 运 行 一 个 生 成 器 有 以 下 四 种 模 式：
