《数据挖掘应》PPT课件

第 12讲 数 据 挖 掘 应 用Chapter 12 Applications of Data Mining徐 从 富 (Congfu Xu), PhD, Asso. Professor 浙 江 大 学 人 工 智 能 研 究 所2005年 5月 17日 第 一 稿2006年 10月 30日 第 二 次 修 改浙 江 大 学 研 究 生 人 工 智 能 引 论 课 件 目 录一 关 联 规 则 挖 掘二 聚 类 分 析三 分 类 与 预 测四 Web挖 掘五 流 数 据 挖 掘六 隐 私 保 护 数 据 挖 掘 一 关 联 规 则 挖 掘1. 关 联 规 则 挖 掘 简 介2. 关 联 规 则 基 本 模 型3. 关 联 规 则 价 值 衡 量 与 发 展 1. 关 联 规 则 简 介n 关 联 规 则 反 映 一 个 事 物 与 其 他 事 物 之 间 的 相 互 依存 性 和 关 联 性 。 如 果 两 个 或 者 多 个 事 物 之 间 存 在一 定 的 关 联 关 系 ， 那 么 ， 其 中 一 个 事 物 就 能 够 通过 其 他 事 物 预 测 到 。 n 典 型 的 关 联 规 则 发 现 问 题 是 对 超 市 中 的 货 篮 数 据（ Market Basket） 进 行 分 析 。 通 过 发 现 顾 客 放 入货 篮 中 的 不 同 商 品 之 间 的 关 系 来 分 析 顾 客 的 购 买习 惯 。 什 么 是 关 联 规 则 挖 掘n 关 联 规 则 挖 掘 首 先 被 Agrawal, Imielinski and Swami在 1993年 的 SIGMOD会 议 上 提 出 在 事 务 、 关 系 数 据 库 中 的 项 集 和 对 象 中 发 现 频 繁 模 式 、 关 联 规 则 、 相 关 性 或 者 因果 结 构 频 繁 模 式 : 数 据 库 中 频 繁 出 现 的 项 集 n 目 的 : 发 现 数 据 中 的 规 律 超 市 数 据 中 的 什 么 产 品 会 一 起 购 买 ？ 啤 酒 和 尿 布 在 买 了 一 台 PC之 后 下 一 步 会 购 买 ? 哪 种 DNA对 这 种 药 物 敏 感 ? 我 们 如 何 自 动 对 Web文 档 进 行 分 类 ? 频 繁 模 式 挖 掘 的 重 要 性n 许 多 重 要 数 据 挖 掘 任 务 的 基 础关 联 、 相 关 性 、 因 果 性序 列 模 式 、 空 间 模 式 、 时 间 模 式 、 多 维关 联 分 类 、 聚 类 分 析n 更 加 广 泛 的 用 处购 物 篮 分 析 、 交 叉 销 售 、 直 销点 击 流 分 析 、 DNA序 列 分 析 等 等 2. 关 联 规 则 基 本 模 型 关 联 规 则 基 本 模 型 Apriori算 法 关 联 规 则 基 本 模 型 n IBM公 司 Almaden研 究 中 心 的 R.Agrawal首 先提 出 关 联 规 则 模 型 ， 并 给 出 求 解 算 法 AIS。随 后 又 出 现 了 SETM和 Apriori等 算 法 。 其 中 ，Apriori是 关 联 规 则 模 型 中 的 经 典 算 法 。 给 定 一 组 事 务产 生 所 有 的 关 联 规 则满 足 最 小 支 持 度 和 最 小 可 信 度 关 联 规 则 基 本 模 型 （ 续 ）n 设 I=i1, i2, im为 所 有 项 目 的 集 合 ， D为 事 务 数据 库 ， 事 务 T是 一 个 项 目 子 集 （ TI） 。 每 一 个 事务 具 有 唯 一 的 事 务 标 识 TID。 设 A是 一 个 由 项 目 构成 的 集 合 ， 称 为 项 集 。 事 务 T包 含 项 集 A， 当 且 仅当 AT。 如 果 项 集 A中 包 含 k个 项 目 ， 则 称 其 为 k项集 。 项 集 A在 事 务 数 据 库 D中 出 现 的 次 数 占 D中 总事 务 的 百 分 比 叫 做 项 集 的 支 持 度 。 如 果 项 集 的 支持 度 超 过 用 户 给 定 的 最 小 支 持 度 阈 值 ， 就 称 该 项集 是 频 繁 项 集 （ 或 大 项 集 ） 。 关 联 规 则 基 本 模 型 （ 续 ）n 关 联 规 则 是 形 如 XY的 逻 辑 蕴 含 式 ， 其 中 XI，YI， 且 XY=。 如 果 事 务 数 据 库 D中 有 s%的 事务 包 含 XY， 则 称 关 联 规 则 XY的 支 持 度 为 s%，实 际 上 ， 支 持 度 是 一 个 概 率 值 。 若 项 集 X的 支 持 度记 为 support (X)， 规 则 的 信 任 度 为 support (XY)support (X)。 这 是 一 个 条 件 概 率 P (Y | X)。 也 就 是 ： support (XY)=P (X Y) confidence (XY)=P (Y | X) 规 则 度 量 ： 支 持 度 与 可 信 度n 查 找 所 有 的 规 则 X n (2) for(k=2;Lk-1;k+) do begin n (3) Ck=apriori_gen(Lk-1); /新 的 潜 在 频 繁 项 集 n (4) for all transactions tD do begin n (5) Ct=subset(Ck,t); /t中 包 含 的 潜 在 频 繁 项 集 n (6) for all candidates cCt do n (7) c.count+; n (8) end; n (9) Lk=cCk|c.countminsup n (10) end; n (11) Answer= k kL 实 例Database TDB 1st scanC1 L1L2 C2 C22nd scanC 3 L33rd scan Tid Items10 A, C, D20 B, C, E30 A, B, C, E40 B, E Itemset supA 2B 3C 3D 1E 3 Itemset supA 2B 3C 3E 3ItemsetA, BA, CA, EB, CB, EC, EItemset supA, B 1A, C 2A, E 1B, C 2B, E 3C, E 2Itemset supA, C 2B, C 2B, E 3C, E 2Itemset B, C, E Itemset supB, C, E 2 Visualization of Association Rules: Pane Graph Visualization of Association Rules: Rule Graph 提 高 Apriori算 法 的 方 法n Hash-based itemset counting（ 散 列 项 集 计 数 ）n Transaction reduction（ 事 务 压 缩 ）n Partitioning（ 划 分 ）n Sampling（ 采 样 ） 关 联 规 则 挖 掘 算 法n Agrawal等 人 提 出 的 AIS， Apriori和 AprioriTidn Cumulate和 Stratify， Houstsma等 人 提 出 的 SETMn Park等 人 提 出 的 DHPn Savasere等 人 的 PARTITIONn Han等 人 提 出 的 不 生 成 候 选 集 直 接 生 成 频 繁 模 式FPGrowthn 其 中 最 有 效 和 有 影 响 的 算 法 为 Apriori， DHP和PARTITION， FPGrowth。 n 用 Frequent-Pattern tree (FP-tree) 结 构 压 缩数 据 库 , 高 度 浓 缩 ， 同 时 对 频 繁 集 的 挖 掘 又 完 备 的避 免 代 价 较 高 的 数 据 库 扫 描n 开 发 一 种 高 效 的 基 于 FP-tree的 频 繁 集 挖 掘算 法采 用 分 而 治 之 的 方 法 学 ： 分 解 数 据 挖 掘 任 务 为小 任 务避 免 生 成 关 联 规 则 : 只 使 用 部 分 数 据 库 !挖 掘 频 繁 集 不 用 生 成 候 选 集 f:4 c:1b:1p:1b:1c:3a:3b:1m:2p:2 m:1头 表Item frequency head f 4c 4a 3b 3m 3p 3 最 小 支 持 度 = 0.5TID Items bought (ordered) frequent items100 f, a, c, d, g, i, m, p f, c, a, m, p200 a, b, c, f, l, m, o f, c, a, b, m300 b, f, h, j, o f, b400 b, c, k, s, p c, b, p500 a, f, c, e, l, p, m, n f, c, a, m, p步 骤 :1. 扫 描 数 据 库 一 次 ， 得 到 频 繁1-项 集2. 把 项 按 支 持 度 递 减 排 序3. 再 一 次 扫 描 数 据 库 ， 建 立 FP-tree用 交 易 数 据 库 建 立 FP-tree n 完 备 : 不 会 打 破 交 易 中 的 任 何 模 式包 含 了 频 繁 模 式 挖 掘 所 需 的 全 部 信 息n 紧 密去 除 不 相 关 信 息 不 包 含 非 频 繁 项支 持 度 降 序 排 列 : 支 持 度 高 的 项 在 FP-tree中 共 享的 机 会 也 高决 不 会 比 原 数 据 库 大 （ 如 果 不 计 算 树 节 点 的 额 外开 销 )例 子 : 对 于 Connect-4 数 据 库 ,压 缩 率 超 过 100FP-tree 结 构 的 好 处 n 基 本 思 想 (分 而 治 之 )用 FP-tree地 归 增 长 频 繁 集n 方 法 对 每 个 项 ， 生 成 它 的 条 件 模 式 库 , 然 后 是 它 的 条 件 FP-tree对 每 个 新 生 成 的 条 件 FP-tree， 重 复 这 个 步 骤直 到 结 果 FP-tree为 空 , 或 只 含 维 一 的 一 个 路 径 (此 路 径 的 每 个 子 路 径 对 应 的 项 集 都 是 频 繁 集 )用 FP-tree挖 掘 频 繁 集 1) 为 FP-tree中 的 每 个 节 点 生 成 条 件 模 式 库2) 用 条 件 模 式 库 构 造 对 应 的 条 件 FP-tree3) 递 归 构 造 条 件 FP-trees 同 时 增 长 其 包 含的 频 繁 集 如 果 条 件 FP-tree只 包 含 一 个 路 径 ， 则 直 接 生成 所 包 含 的 频 繁 集 。挖 掘 FP-tree的 主 要 步 骤 n 从 FP-tree的 头 表 开 始n 按 照 每 个 频 繁 项 的 连 接 遍 历 FP-treen 列 出 能 够 到 达 此 项 的 所 有 前 缀 路 径 ， 得 到 条 件模 式 库 条 件 模 式 库item cond. pattern basec f:3a fc:3b fca:1, f:1, c:1m fca:2, fcab:1p fcam:2, cb:1f:4 c:1b:1p:1b:1c:3a:3b:1m:2 p:2 m:1头 表Item frequency head f 4c 4a 3b 3m 3p 3 步 骤 1: 从 FP-tree 到 条 件 模 式 库 n 节 点 裢 接任 何 包 含 ai, 的 可 能 频 繁 集 ， 都 可 以 从 FP-tree头表 中 的 ai沿 着 ai 的 节 点 链 接 得 到n 前 缀 路 径要 计 算 路 径 P 中 包 含 节 点 ai 的 频 繁 集 ， 只 要 考察 到 达 ai 的 路 径 前 缀 即 可 ， 且 其 支 持 度 等 于 节点 ai 的 支 持 度FP-tree支 持 条 件 模 式 库 构 造 的 属 性 n 对 每 个 模 式 库计 算 库 中 每 个 项 的 支 持 度用 模 式 库 中 的 频 繁 项 建 立 FP-treem-条 件 模 式 库 :fca:2, fcab:1f:3c:3a:3 m-conditional FP-treeAll frequent patterns concerning mm, fm, cm, am, fcm, fam, cam, fcam f:4 c:1b:1p:1b:1c:3a:3b:1m:2p:2 m:1头 表Item frequency head f 4c 4a 3b 3m 3p 3 步 骤 2: 建 立 条 件 FP-tree EmptyEmptyf (f:3)|c(f:3)c (f:3, c:3)|a(fc:3)a Empty(fca:1), (f:1), (c:1)b (f:3, c:3, a:3)|m(fca:2), (fcab:1)m (c:3)|p(fcam:2), (cb:1)p 条 件 FP-tree条 件 模 式 库项通 过 建 立 条 件 模 式 库 得 到 频 繁 集 f:3c:3a:3m-条 件 FP-tree “am”的 条 件 模 式 库 : (fc:3) f:3c:3am-条 件 FP-tree“cm”的 条 件 模 式 : (f:3) f:3cm-条 件 FP-tree“cam”条 件 模 式 库 : (f:3) f:3 cam-条 件 FP-tree 第 3步 : 递 归 挖 掘 条 件 FP-tree 3. 关 联 规 则 价 值 衡 量 与 发 展 关 联 规 则 价 值 衡 量 关 联 规 则 最 新 进 展 规 则 价 值 衡 量 n 对 关 联 规 则 的 评 价 与 价 值 衡 量 涉 及 两 个 层面 ：系 统 客 观 的 层 面用 户 主 观 的 层 面 系 统 客 观 层 面 n 使 用 “ 支 持 度 和 信 任 度 ” 框 架 可 能 会 产 生一 些 不 正 确 的 规 则 。 只 凭 支 持 度 和 信 任 度阈 值 未 必 总 能 找 出 符 合 实 际 的 规 则 。 用 户 主 观 层 面 n 只 有 用 户 才 能 决 定 规 则 的 有 效 性 、 可 行 性 。 所 以 ，应 该 将 用 户 的 需 求 和 系 统 更 加 紧 密 地 结 合 起 来 。 n 可 以 采 用 基 于 约 束 （ Consraint-based） 的 数 据 挖掘 方 法 。 具 体 约 束 的 内 容 有 ： 数 据 约 束 、 限 定 数据 挖 掘 的 维 和 层 次 、 规 则 约 束 。n 如 果 把 某 些 约 束 条 件 与 算 法 紧 密 结 合 ， 既 能 提 高数 据 挖 掘 效 率 ， 又 能 明 确 数 据 挖 掘 的 目 标 。 关 联 规 则 新 进 展 n 在 基 于 一 维 布 尔 型 关 联 规 则 的 算 法 研 究 中 先 后 出现 了 AIS、 SETM等 数 据 挖 掘 算 法 。 n R.Agrawal等 人 提 出 的 Apriori 是 经 典 算 法 。 随 后 的关 联 规 则 发 现 算 法 大 多 数 建 立 在 Apriori算 法 基 础上 ， 或 进 行 改 造 ， 或 衍 生 变 种 。 比 如 AprioriTid和AprioriHybrid算 法 。 n Lin等 人 提 出 解 决 规 则 挖 掘 算 法 中 的 数 据 倾 斜 问 题 ，从 而 使 算 法 具 有 较 好 的 均 衡 性 。 Park等 人 提 出 把哈 希 表 结 构 用 于 关 联 规 则 挖 掘 。 关 联 规 则 新 进 展 （ 续 ）n 数 据 挖 掘 工 作 是 在 海 量 数 据 库 上 进 行 的 ， 数 据 库 的规 模 对 规 则 的 挖 掘 时 间 有 很 大 影 响 。n Agrawal首 先 提 出 事 务 缩 减 技 术 ， Han和 Park等 人 也分 别 在 减 小 数 据 规 模 上 做 了 一 些 工 作 。 n 抽 样 的 方 法 是 由 Toivonen提 出 的 。 n Brin等 人 采 用 动 态 项 集 计 数 方 法 求 解 频 繁 项 集 。 n Aggarwal提 出 用 图 论 和 格 的 理 论 求 解 频 繁 项 集 的 方法 。 Prutax算 法 就 是 用 格 遍 历 的 办 法 求 解 频 繁 项 集 。 关 联 规 则 新 进 展 （ 续 ）n 关 联 规 则 模 型 有 很 多 扩 展 ， 如 顺 序 模 型 挖 掘 ， 在 顺序 时 间 段 上 进 行 挖 掘 等 。n 还 有 挖 掘 空 间 关 联 规 则 ， 挖 掘 周 期 性 关 联 规 则 ， 挖掘 负 关 联 规 则 ， 挖 掘 交 易 内 部 关 联 规 则 等 。 n Guralnik提 出 顺 序 时 间 段 问 题 的 形 式 描 述 语 言 ， 以便 描 述 用 户 感 兴 趣 的 时 间 段 ， 并 且 构 建 了 有 效 的 数据 结 构 SP树 （ 顺 序 模 式 树 ） 和 自 底 向 上 的 数 据 挖 掘算 法 。 n 最 大 模 式 挖 掘 是 Bayardo等 人 提 出 来 的 。 关 联 规 则 新 进 展 （ 续 ）n 随 后 人 们 开 始 探 讨 频 率 接 近 项 集 。 Pei给 出 了 一 种 有效 的 数 据 挖 掘 算 法 。 n B.zden等 人 的 周 期 性 关 联 规 则 是 针 对 具 有 时 间 属性 的 事 务 数 据 库 ， 发 现 在 规 律 性 的 时 间 间 隔 中 满 足最 小 支 持 度 和 信 任 度 的 规 则 。 n 贝 尔 实 验 室 的 S.Ramaswamy等 人 进 一 步 发 展 了 周 期性 关 联 规 则 ， 提 出 挖 掘 符 合 日 历 的 关 联 规 则（ Calendric Association Rules） 算 法 ， 用 以 进 行 市 场货 篮 分 析 。 n Fang等 人 给 出 冰 山 查 询 数 据 挖 掘 算 法 。 关 联 规 则 新 进 展 （ 续 ）n T.Hannu等 人 把 负 边 界 引 入 规 则 发 现 算 法 中 ， 每 次 挖掘 不 仅 保 存 频 繁 项 集 ， 而 且 同 时 保 存 负 边 界 ， 达 到下 次 挖 掘 时 减 少 扫 描 次 数 的 目 的 。 n Srikant等 人 通 过 研 究 关 联 规 则 的 上 下 文 ， 提 出 规 则兴 趣 度 尺 度 用 以 剔 除 冗 余 规 则 。 n Zakia还 用 项 集 聚 类 技 术 求 解 最 大 的 近 似 潜 在 频 繁 项集 ， 然 后 用 格 迁 移 思 想 生 成 每 个 聚 类 中 的 频 繁 项 集 。 n CAR， 也 叫 分 类 关 联 规 则 ， 是 Lin等 人 提 出 的 一 种 新的 分 类 方 法 ， 是 分 类 技 术 与 关 联 规 则 思 想 相 结 合 的产 物 ， 并 给 出 解 决 方 案 和 算 法 。 关 联 规 则 新 进 展 （ 续 ）n Cheung等 人 提 出 关 联 规 则 的 增 量 算 法 。n Thomas等 人 把 负 边 界 的 概 念 引 入 其 中 ， 进 一步 发 展 了 增 量 算 法 。 如 ， 基 于 Apriori框 架 的并 行 和 分 布 式 数 据 挖 掘 算 法 。n Oates等 人 将 MSDD算 法 改 造 为 分 布 式 算 法 。还 有 其 他 的 并 行 算 法 ， 如 利 用 垂 直 数 据 库 探求 项 集 聚 类 等 。 二 聚 类 分 析I. 聚 类 分 析 简 介II. 聚 类 分 析 中 的 数 据 类 型III. 划 分 方 法IV. 层 次 方 法 I. 聚 类 （ Clustering） 分 析 简 介n 聚 类 （ Clustering） 是 对 物 理 的 或 抽 象 的 对象 集 合 分 组 的 过 程 。 n 聚 类 生 成 的 组 称 为 簇 （ Cluster） ， 簇 是 数 据对 象 的 集 合 。 簇 内 部 的 任 意 两 个 对 象 之 间具 有 较 高 的 相 似 度 ， 而 属 于 不 同 簇 的 两 个对 象 间 具 有 较 高 的 相 异 度 。 相 异 度 可 以 根据 描 述 对 象 的 属 性 值 计 算 ， 对 象 间 的 距 离是 最 常 采 用 的 度 量 指 标 。 聚 类 分 析 简 介 （ 续 ） n 聚 类 分 析 是 数 据 分 析 中 的 一 种 重 要 技 术 ，它 的 应 用 极 为 广 泛 。 许 多 领 域 中 都 会 涉 及聚 类 分 析 方 法 的 应 用 与 研 究 工 作 ， 如 数 据挖 掘 、 统 计 学 、 机 器 学 习 、 模 式 识 别 、 生物 学 、 空 间 数 据 库 技 术 、 电 子 商 务 等 。 聚 类 分 析 简 介 （ 续 ）n 从 统 计 学 的 观 点 看 ， 聚 类 分 析 是 通 过 数 据建 模 简 化 数 据 的 一 种 方 法 。 传 统 的 统 计 聚类 分 析 方 法 包 括 系 统 聚 类 法 、 分 解 法 、 加入 法 、 动 态 聚 类 法 、 有 序 样 品 聚 类 、 有 重叠 聚 类 和 模 糊 聚 类 等 。 采 用 k-均 值 、 k-中 心点 等 算 法 的 聚 类 分 析 工 具 已 被 加 入 到 许 多著 名 的 统 计 分 析 软 件 包 中 ， 如 SPSS、 SAS等 。 聚 类 分 析 简 介 （ 续 ）n 从 机 器 学 习 的 角 度 讲 ， 簇 相 当 于 隐 藏 模 式 。聚 类 是 搜 索 簇 的 无 监 督 学 习 过 程 。 与 分 类不 同 ， 无 监 督 学 习 不 依 赖 预 先 定 义 的 类 或带 类 标 记 的 训 练 实 例 ， 需 要 由 聚 类 学 习 算法 自 动 确 定 标 记 ， 而 分 类 学 习 的 实 例 或 数据 对 象 有 类 别 标 记 。 聚 类 是 观 察 式 学 习 ，而 不 是 示 例 式 的 学 习 。 聚 类 分 析 简 介 （ 续 ） n 从 实 际 应 用 的 角 度 看 ， 聚 类 分 析 是 数 据 挖 掘 的 主要 任 务 之 一 。n 就 数 据 挖 掘 功 能 而 言 ， 聚 类 能 够 作 为 一 个 独 立 的工 具 获 得 数 据 的 分 布 状 况 ， 观 察 每 一 簇 数 据 的 特征 ， 集 中 对 特 定 的 聚 簇 集 合 作 进 一 步 地 分 析 。n 聚 类 分 析 还 可 以 作 为 其 他 数 据 挖 掘 任 务 （ 如 分 类 、关 联 规 则 ） 的 预 处 理 步 骤 。 n 数 据 挖 掘 领 域 主 要 研 究 面 向 大 型 数 据 库 、 数 据 仓库 的 高 效 实 用 的 聚 类 分 析 算 法 。 聚 类 的 常 规 应 用 n 模 式 识 别n 空 间 数 据 分 析 在 GIS中 ， 通 过 聚 类 发 现 特 征 空 间 来 建 立 主 题 索引 ；在 空 间 数 据 挖 掘 中 ， 检 测 并 解 释 空 间 中 的 簇 ；n 图 象 处 理n 经 济 学 (尤 其 是 市 场 研 究 方 面 )n WWW文 档 分 类 分 析 WEB日 志 数 据 来 发 现 相 似 的 访 问 模 式 应 用 聚 类 分 析 的 例 子n 市 场 销 售 : 帮 助 市 场 人 员 发 现 客 户 中 的 不 同 群 体 ，然 后 用 这 些 知 识 来 开 展 一 个 目 标 明 确 的 市 场 计 划 ；n 土 地 使 用 : 在 一 个 陆 地 观 察 数 据 库 中 标 识 那 些 土 地使 用 相 似 的 地 区 ；n 保 险 : 对 购 买 了 汽 车 保 险 的 客 户 ， 标 识 那 些 有 较 高平 均 赔 偿 成 本 的 客 户 ；n 城 市 规 划 : 根 据 类 型 、 价 格 、 地 理 位 置 等 来 划 分 不同 类 型 的 住 宅 ； n 地 震 研 究 : 根 据 地 质 断 层 的 特 点 把 已 观 察 到 的 地 震中 心 分 成 不 同 的 类 ； 什 么 是 一 个 好 的 聚 类 方 法 ?n 一 个 好 的 聚 类 方 法 要 能 产 生 高 质 量 的 聚 类 结 果 簇 ， 这 些 簇 要 具 备 以 下 两 个 特 点 ：高 的 簇 内 相 似 性低 的 簇 间 相 似 性 n 聚 类 结 果 的 好 坏 取 决 于 该 聚 类 方 法 采 用 的 相 似 性评 估 方 法 以 及 该 方 法 的 具 体 实 现 ；n 聚 类 方 法 的 好 坏 还 取 决 与 该 方 法 是 能 发 现 某 些 还是 所 有 的 隐 含 模 式 ； II. 聚 类 分 析 中 的 数 据 类 型n 聚 类 分 析 主 要 针 对 的 数 据 类 型 包 括 区 间 标度 变 量 、 二 元 变 量 、 标 称 变 量 、 序 数 型 变量 ， 以 及 由 这 些 变 量 类 型 构 成 的 复 合 类 型 。 n 一 些 基 于 内 存 的 聚 类 算 法 通 常 采 用 数 据 矩阵 和 相 异 度 矩 阵 两 种 典 型 的 数 据 结 构 。 数 据 矩 阵 （ Data Matrix） n 设 有 n个 对 象 ， 可 用 p个 变 量 （ 属 性 ） 描 述 每 个 对象 ， 则 np矩 阵 称 为 数 据 矩 阵 。 数 据 矩 阵 是 对 象 -变 量 结 构 的 数 据表 达 方 式 。 npnn ppxxx xxx xxx 21 22221 11211 相 异 度 矩 阵 （ Dissimilarity Matrix） n 按 n个 对 象 两 两 间 的 相 异 度 构 建 n阶 矩 阵 （ 因 为 相 异 度 矩 阵是 对 称 的 ， 只 需 写 出 上 三 角 或 下 三 角 即 可 ） ： n 其 中 d (i, j)表 示 对 象 i与 j的 相 异 度 ， 它 是 一 个 非 负 的 数 值 。当 对 象 i和 j越 相 似 或 “ 接 近 ” 时 ， d (i, j)值 越 接 近 0； 而 对 象i和 j越 不 相 同 或 相 距 “ 越 远 ” 时 ， d (i, j)值 越 大 。 显 然 ， d (i, j)=d (j, i)， d (i, i)=0。 相 异 度 矩 阵 是 对 象 -对 象 结 构 的 一 种 数据 表 达 方 式 。 0 )2 ,( )1 ,( 0 )2 ,3( )1 ,3( 0 )1 ,2( 0 ndnd ddd 评 价 聚 类 质 量n 差 异 度 /相 似 度 矩 阵 : 相 似 度 通 常 用 距 离 函 数 来 表示 ；n 有 一 个 单 独 的 质 量 评 估 函 数 来 评 判 一 个 簇 的 好 坏 ；n 对 不 同 类 型 的 变 量 ， 距 离 函 数 的 定 义 通 常 是 不 同 的 ；n 根 据 实 际 的 应 用 和 数 据 的 语 义 ， 在 计 算 距 离 的 时 候 ，不 同 的 变 量 有 不 同 的 权 值 相 联 系 ；n 很 难 定 义 “ 足 够 相 似 了 ” 或 者 “ 足 够 好 了 ” 只 能 凭 主 观 确 定 ； 聚 类 分 析 中 的 数 据 类 型n 区 间 标 度 变 量 ；n 二 元 变 量 ；n 标 称 型 ， 序 数 型 变 量 ；n 混 合 类 型 变 量 ； 对 象 间 距 离 的 计 算n 设 两 个 p维 向 量 xi = (xi1, xi2, xi p)T和 xj=(xj1, xj2, xj p)T分 别 表 示 两 个 对 象 ， 有 多 种 形 式 的 距 离 度 量可 以 采 用 。 闵 可 夫 斯 基 （ Minkowski） 距 离 ： 曼 哈 坦 （ Manhattan） 距 离 ： 欧 几 里 得 （ Euclidean） 距 离 ： 切 比 雪 夫 （ Chebyshev） 距 离 ： 马 哈 拉 诺 比 斯 （ Mahalanobis） 距 离 ： III.划 分 方 法 简 介n 对 于 一 个 给 定 的 n个 对 象 或 元 组 的 数 据 库 ， 采 用 目标 函 数 最 小 化 的 策 略 ， 通 过 迭 代 把 数 据 分 成 k个 划分 块 ， 每 个 划 分 块 为 一 个 簇 ， 这 就 是 划 分 方 法 。 n 划 分 方 法 满 足 两 个 条 件 ：（ 1） 每 个 分 组 至 少 包 含 一 个 对 象 ；（ 2） 每 个 对 象 必 属 于 且 仅 属 于 某 一 个 分 组 。 n 常 见 的 划 分 方 法 有 k-均 值 方 法 和 k-中 心 点 方 法 。 其他 方 法 大 都 是 这 两 种 方 法 的 变 形 。 k-均 值 算 法 n k-均 值 聚 类 算 法 的 核 心 思 想 是 通 过 迭 代 把 数 据 对象 划 分 到 不 同 的 簇 中 ， 以 求 目 标 函 数 最 小 化 ， 从而 使 生 成 的 簇 尽 可 能 地 紧 凑 和 独 立 。首 先 ， 随 机 选 取 k个 对 象 作 为 初 始 的 k个 簇 的 质 心 ；然 后 ， 将 其 余 对 象 根 据 其 与 各 个 簇 质 心 的 距 离 分 配 到最 近 的 簇 ； 再 求 新 形 成 的 簇 的 质 心 。这 个 迭 代 重 定 位 过 程 不 断 重 复 ， 直 到 目 标 函 数 最 小 化为 止 。 k-均 值 算 法 n 输 入 期 望 得 到 的 簇 的 数 目 k， n个 对 象 的 数 据 库 。n 输 出 使 得 平 方 误 差 准 则 函 数 最 小 化 的 k个 簇 。n 方 法 选 择 k个 对 象 作 为 初 始 的 簇 的 质 心 ； repeat 计 算 对 象 与 各 个 簇 的 质 心 的 距 离 ， 将 对 象 划 分 到 距 离其 最 近 的 簇 ； 重 新 计 算 每 个 新 簇 的 均 值 ； until簇 的 质 心 不 再 变 化 。 K-均 值 算 法 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 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 IV. 层 次 聚 类n 层 次 聚 类 按 数 据 分 层 建 立 簇 ， 形 成 一 棵 以簇 为 节 点 的 树 ， 称 为 聚 类 图 。 n 按 自 底 向 上 层 次 分 解 ， 则 称 为 凝 聚 的 层 次聚 类 。 n 按 自 顶 向 下 层 次 分 解 ， 就 称 为 分 裂 的 层 次聚 类 。 凝 聚 的 和 分 裂 的 层 次 聚 类 n 凝 聚 的 层 次 聚 类 采 用 自 底 向 上 的 策 略 ， 开始 时 把 每 个 对 象 作 为 一 个 单 独 的 簇 ， 然 后逐 次 对 各 个 簇 进 行 适 当 合 并 ， 直 到 满 足 某个 终 止 条 件 。 n 分 裂 的 层 次 聚 类 采 用 自 顶 向 下 的 策 略 ， 与凝 聚 的 层 次 聚 类 相 反 ， 开 始 时 将 所 有 对 象置 于 同 一 个 簇 中 ， 然 后 逐 次 将 簇 分 裂 为 更小 的 簇 ， 直 到 满 足 某 个 终 止 条 件 。 凝 聚 的 和 分 裂 的 层 次 聚 类 a, b, c, d, e c, d, e d, e a, b e d c b a 第 4步 第 3步 第 2步 第 1步 第 0步 凝 聚 的 （ AGENS） 第 0步 第 1步 第 2步 第 3步 第 4步 分 裂 的 （ DIANA） 层 次 聚 类 方 法 的 优 缺 点n 层 次 聚 类 方 法 的 优 点 在 于 可 以 在 不 同 粒 度 水 平 上 对 数 据 进 行探 测 ， 而 且 容 易 实 现 相 似 度 量 或 距 离 度 量 。 n 单 纯 的 层 次 聚 类 算 法 终 止 条 件 含 糊 ， 而 且 执 行 合 并 或 分 裂 簇的 操 作 后 不 可 修 正 ， 这 很 可 能 导 致 聚 类 结 果 质 量 很 低 。 由 于需 要 检 查 和 估 算 大 量 的 对 象 或 簇 才 能 决 定 簇 的 合 并 或 分 裂 ，所 以 这 种 方 法 的 可 扩 展 性 较 差 。 通 常 考 虑 把 层 次 聚 类 方 法 与其 他 方 法 （ 如 迭 代 重 定 位 方 法 ） 相 结 合 来 解 决 实 际 聚 类 问 题 。 n 层 次 聚 类 和 其 他 聚 类 方 法 的 有 效 集 成 可 以 形 成 多 阶 段 聚 类 ，能 够 改 善 聚 类 质 量 。 这 类 方 法 包 括 BIRCH、 CURE、 ROCK、Chameleon等 。 三 分 类 与 预 测1. 简 介2. 决 策 树 1. 简 介 分 类 预 测 分 类n 分 类 的 目 的 是 提 出 一 个 分 类 函 数 或 分 类 模 型 （ 即 分类 器 ） ， 通 过 分 类 器 将 数 据 对 象 映 射 到 某 一 个 给 定的 类 别 中 。 n 数 据 分 类 可 以 分 为 两 步 进 行 。第 一 步 建 立 模 型 ， 用 于 描 述 给 定 的 数 据 集 合 。 通 过 分 析由 属 性 描 述 的 数 据 集 合 来 建 立 反 映 数 据 集 合 特 性 的 模 型 。这 一 步 也 称 作 有 监 督 的 学 习 ， 导 出 模 型 是 基 于 训 练 数 据集 的 ， 训 练 数 据 集 是 已 知 类 标 记 的 数 据 对 象 。第 二 步 使 用 模 型 对 数 据 对 象 进 行 分 类 。 首 先 应 该 评 估 模型 的 分 类 准 确 度 ， 如 果 模 型 准 确 度 可 以 接 受 ， 就 可 以 用它 来 对 未 知 类 标 记 的 对 象 进 行 分 类 。 训 练 集 与 测 试 集n 训 练 集 ： 数 据 库 中 为 建 立 模 型 而 被 分 析 的数 据 元 组 形 成 训 练 集 。n 训 练 集 中 的 单 个 元 组 称 为 训 练 样 本 ,每 个 训练 样 本 有 一 个 类 别 标 记 。 一 个 具 体 样 本 的形 式 可 为 :( v1, v2, ., vn; c );其 中vi表 示 属 性 值 ,c表 示 类 别 。n 测 试 集 ： 用 于 评 估 分 类 模 型 的 准 确 率 。 分 类 的 两 个 阶 段a.模 型 训 练 阶 段 训 练 集b.使 用 模 型 分 类 阶 段评 估 准 确 率 （ 测 试 集 ）对 类 标 号 未 知 的 新数 据 分 类 分 类 模 型 的 构 造 方 法机 器 学 习 方 法 ：决 策 树 法 知 识 表 示 是 决 策 树规 则 归 纳 知 识 表 示 是 产 生 式 规 则神 经 网 络 方 法 ：BP算 法 ,模 型 表 示 是 前 向 反 馈 神 经 网 络 模 型粗 糙 集 (rough set)知 识 表 示 是 产 生 式 规 则 预 测n 预 测 的 目 的 是 从 历 史 数 据 记 录 中 自 动 推 导出 对 给 定 数 据 的 推 广 描 述 ， 从 而 能 够 对 事先 未 知 的 数 据 进 行 预 测 。n 分 类 和 回 归 是 两 类 主 要 的 预 测 问 题 。 分 类是 预 测 离 散 的 值 ， 回 归 是 预 测 连 续 值 。n 用 预 测 法 预 测 类 标 号 为 分 类n 用 预 测 法 预 测 连 续 值 为 预 测 评 估 分 类 和 预 测 方 法 的 五 条 标 准n 预 测 的 准 确 率n 计 算 速 度n 鲁 棒 性n 可 伸 缩 性n 可 解 释 性 2. 决 策 树 决 策 树 学 习 简 介 决 策 树 实 例 决 策 树 学 习 的 算 法 决 策 树 学 习 简 介n 决 策 树 （ Decision Tree） 学 习 是 以 样 本 为 基 础 的 归纳 学 习 方 法 。n 决 策 树 的 表 现 形 式 是 类 似 于 流 程 图 的 树 结 构 ， 在 决策 树 的 内 部 节 点 进 行 属 性 值 测 试 ， 并 根 据 属 性 值 判断 由 该 节 点 引 出 的 分 支 ， 在 决 策 树 的 叶 节 点 得 到 结论 。 内 部 节 点 是 属 性 或 属 性 的 集 合 ， 叶 节 点 代 表 样本 所 属 的 类 或 类 分 布 。n 经 由 训 练 样 本 集 产 生 一 棵 决 策 树 后 ， 为 了 对 未 知 样本 集 分 类 ， 需 要 在 决 策 树 上 测 试 未 知 样 本 的 属 性 值 。测 试 路 径 由 根 节 点 到 某 个 叶 节 点 ， 叶 节 点 代 表 的 类就 是 该 样 本 所 属 的 类 。 决 策 树 实 例n 关 于 PlayTennis的 决 策 树 如 图 所 示 ： High Overcast Normal Strong Weak Sunny Rain Outlook Wind Humidity No Yes Yes No Yes 决 策 树 学 习 的 算 法 n 决 策 树 学 习 的 基 本 算 法 是 贪 心 算 法 ， 采 用 自 顶 向 下的 递 归 方 式 构 造 决 策 树 。 n Hunt等 人 于 1966年 提 出 的 概 念 学 习 系 统 CLS是 最 早的 决 策 树 算 法 ， 以 后 的 许 多 决 策 树 算 法 都 是 对 CLS算 法 的 改 进 或 由 CLS衍 生 而 来 。 n Quinlan于 1979年 提 出 了 著 名 的 ID3方 法 。 以 ID3为蓝 本 的 C4.5是 一 个 能 处 理 连 续 属 性 的 算 法 。 n 其 他 决 策 树 方 法 还 有 ID3的 增 量 版 本 ID4和 ID5等 。 n 强 调 在 数 据 挖 掘 中 有 伸 缩 性 的 决 策 树 算 法 有 SLIQ、SPRINT、 RainForest算 法 等 。 四 Web 挖 掘 K nowledgeWWW 目 录I. Web 挖 掘 简 介II. Web日 志 挖 掘 I. Web Mining简 介1. 产 生 原 因2. 应 用3. 分 类4. 过 程 1. 产 生 原 因n 网 络 信 息 搜 集 的 需 求 与 收 集 结 果 低 效 性 的矛 盾 迫 切 需 要 对 网 络 资 源 的 整 序 与 检 索 。n 传 统 数 据 挖 掘 和 文 本 挖 掘 技 术 的 不 断 完 善和 应 用 。 2. 应 用n 查 询 相 关 信 息n 从 Web数 据 发 现 潜 在 的 未 知 信 息n 了 解 用 户 的 兴 趣 爱 好n 信 息 个 性 化 3. Web 挖 掘 分 类Web MiningWeb Content Mining Web Usage MiningWeb Structure Mining Web内 容 挖 掘n Web内 容 挖 掘 是 从 文 档 内 容 或 其 描 述 中 抽取 知 识 的 过 程 。n Web内 容 挖 掘 策 略直 接 挖 掘 文 档 的 内 容在 其 它 工 具 搜 索 的 基 础 上 进 行 改 进 Web内 容 挖 掘 （ 续 ）n 提 取 文 字 、 图 片 或 者 其 他 组 成 网 页 内 容 成分 的 信 息 ， 即 通 过 有 效 的 内 容 挖 掘 能 告 诉我 们 哪 些 页 面 是 德 文 或 者 法 文 的 ？ 哪 些 站点 卖 我 们 喜 欢 的 东 西 ？ 哪 些 页 面 介 绍 了 我们 感 兴 趣 的 知 识 ？ 搜 索 引 擎 、 智 能 代 理 和一 些 推 荐 引 擎 都 使 用 内 容 挖 掘 来 帮 助 客 户在 浩 瀚 的 网 络 空 间 中 寻 找 所 需 的 内 容 。 Web结 构 挖 掘n Web结 构 挖 掘 研 究 的 是 Web文 档 的 链 接 结构 ， 揭 示 蕴 含 在 这 些 文 档 结 构 中 的 有 用 模式 ， 处 理 的 数 据 是 Web结 构 数 据 。 是 从WWW的 组 织 结 构 和 链 接 关 系 中 推 导 知 识 。由 于 文 档 之 间 的 互 连 ， WWW能 够 提 供 除 文档 内 容 之 外 的 有 用 信 息 。 利 用 这 些 信 息 ，可 以 对 页 面 进 行 排 序 ， 发 现 重 要 的 页 面 。 Web结 构 挖 掘 （ 续 ）n 提 取 网 络 的 拓 扑 信 息 网 页 之 间 的 链 接信 息 ， 即 通 过 有 效 的 结 构 挖 掘 能 告 诉 我 们哪 些 页 面 被 其 他 页 面 所 链 接 ？ 哪 些 页 面 指向 了 其 他 页 面 ？ 哪 些 页 面 的 集 合 构 成 了 一个 独 立 的 整 体 ？ Web日 志 挖 掘n Web日 志 挖 掘 的 主 要 目 标 则 是 从 Web的 访问 记 录 中 （ Web服 务 器 log日 志 ） 抽 取 感 兴趣 的 模 式 。 WWW中 的 每 个 服 务 器 都 保 留 了访 问 日 志 （ Web access log） ， 记 录 了 用户 访 问 和 交 互 的 信 息 。 分 析 这 些 数 据 可 以帮 助 理 解 用 户 的 行 为 ， 从 而 改 进 站 点 的 结构 ， 或 为 用 户 提 供 个 性 化 的 服 务 。 Web日 志 挖 掘 （ 续 ）n 一 般 的 访 问 模 式 跟 踪通 过 分 析 日 志 数 据 来 了 解 用 户 的 访 问 模 式 和 倾向 ， 以 改 进 站 点 的 组 织 结 构n 个 性 化 的 使 用 记 录 跟 踪倾 向 于 分 析 单 个 用 户 的 偏 好 ， 其 目 的 是 根 据 不同 用 户 的 访 问 模 式 ， 为 每 个 用 户 提 供 定 制 的 站点 。 Web日 志 挖 掘 （ 续 ）n 提 取 关 于 客 户 如 何 运 用 浏 览 器 浏 览 和 使 用这 些 链 接 的 信 息 ， 即 通 过 有 效 的 日 志 挖 掘能 告 诉 我 们 那 些 客 户 访 问 了 哪 些 页 面 ？ 在每 一 页 上 待 了 多 长 时 间 ？ 下 一 步 单 击 了 什么 ？ 在 站 点 中 是 按 照 怎 样 的 访 问 路 线 通 向检 查 计 数 器 ， 又 是 通 过 怎 样 的 路 线 直 接 退出 的 ？ Web内 容 挖 掘 Web结 构 挖掘 Web日 志 挖掘处 理 数 据类 型 IR方 法 ： 无 结 构数 据 、 半 结 构 数据 数 据 库 方 法 ： 半结 构 化 数 据 Web结 构 数 据 用 户 访 问 Web数据主 要 数 据 自 由 化 文 本 、HTML标 记 的 超文 本 HTML标 记 的 超文 本 Web文 档 内 及 文档 间 的 超 链 Serverlog,Proxy serverlog,Client log表 示 方 法 词 集 、 段 落 、 概念 、 IR的 三 种 经典 模 型 对 象 关 系 模 型 图 关 系 表 、 图处 理 方 法 统 计 、 机 器 学 习 、 自 然 语 言 理 解 数 据 库 技 术 机 器 学 习 、 专 有算 法 统 计 、 机 器 学 习 、关 联 规 则主 要 应 用 分 类 、 聚 类 、 模式 发 现 模 式 发 现 、 数 据向 导 、 多 层 数 据库 、 站 点 创 建 与维 护 页 面 权 重分 类 聚 类模 式 发 现 Web站 点 重 建 ，商 业 决 策 4. Web挖 掘 过 程n 资 源 发 现 ： 在 线 或 离 线 检 索 Web的 过 程 ， 例 如 用爬 虫 （ crawler） 或 （ spider） 在 线 收 集 Web页 面n 信 息 选 择 与 预 处 理 ： 对 检 索 到 的 Web资 源 的 任 何变 换 都 属 于 此 过 程 。词 干 提 取高 低 频 词 的 过 滤汉 语 词 的 切 分n 综 合 过 程 ： 自 动 发 现 Web站 点 的 共 有 模 式n 分 析 过 程 ： 对 挖 掘 到 的 模 式 进 行 验 证 和 可 视 化 处理 II. Web日 志 挖 掘1. Web日 志 挖 掘 数 据 类 型2. Web日 志 挖 掘 应 用3. Web日 志 挖 掘 过 程 服 务 器 日 志 数 据 类 型n Client IP: 128.101.228.20n Authenticated User ID: - -n Time/Date: 10/Nov/1999:10:16:39 -0600n Request: GET / HTTP/1.0n Status: 200n Bytes: -n Referrer: “-”n Agent: Mozilla/4.61 en (WinNT; I) 2. Web 日 志 挖 掘 应 用n Applications电 子 商 务 中 发 现 潜 在 客 户增 强 终 端 用 户 信 息 获 取 的 质 量提 高 Web服 务 器 的 性 能合 理 放 置 广 告提 高 站 点 设 计欺 诈 和 入 侵 检 测预 测 用 户 行 为 3. Web日 志 挖 掘 过 程 Web日 志 挖 掘 过 程 预 处 理 数 据 挖 掘 模 式 分 析 数 据 预 处 理n 数 据 清 理n 用 户 对 话 识 别n 页 面 视 图 识 别n 路 径 完 整 数 据 清 理n 根 据 一 组 原 始 的 日 志 项 ， 完 成 一 系 列 基 本任 务 ， 如 归 并 日 志 、 解 析 日 志 等 。 对 于 一些 网 站 ， 需 要 过 滤 掉 图 象 文 件 ， 这 可 以 通过 检 查 文 件 后 缀 实 现 。 一 般 地 ， 我 们 需 要对 日 志 中 的 状 态 码 （ status code） 进 行 检查 。 清 理 后 的 Sample LogIP Address Time/Date Method/URI Referrer Agent202.120.224.4 15:30:01/2-Jan-01 GET Index.htm http:/ok.edu/link.htm Mozilla/4.0(IE5.0W98)20