《数据挖掘》课程PPT-聚类分析

《《数据挖掘》课程PPT-聚类分析》由会员分享，可在线阅读，更多相关《《数据挖掘》课程PPT-聚类分析（38页珍藏版）》请在装配图网上搜索。

1、聚 类 分 析 什 么 是 聚 类 分 析 ？n 聚 类 （ 簇 ） ： 数 据 对 象 的 集 合q 在 同 一 个 聚 类 （ 簇 ） 中 的 对 象 彼 此 相 似q 不 同 簇 中 的 对 象 则 相 异n 聚 类 分 析q 将 物 理 或 抽 象 对 象 的 集 合 分 组 成 为 由 类 似 的 对 象 组 成 的 多 个类 的 过 程n 聚 类 是 一 种 无 指 导 的 学 习 ： 没 有 预 定 义 的 类 编 号 n 聚 类 分 析 的 数 据 挖 掘 功 能q 作 为 一 个 独 立 的 工 具 来 获 得 数 据 分 布 的 情 况q 作 为 其 他 算 法 （ 如 ：

2、 特 征 和 分 类 ） 的 预 处 理 步 骤 聚 类 分 析 的 典 型 应 用n 模 式 识 别n 空 间 数 据 分 析q 在 GIS系 统 中 ， 对 相 似 区 域 进 行 聚 类 ， 产 生 主 题 地 图q 检 测 空 间 聚 类 ， 并 给 出 它 们 在 空 间 数 据 挖 掘 中 的 解 释q 图 像 处 理n 商 务 应 用 中 ， 帮 市 场 分 析 人 员 发 现 不 同 的 顾 客 群n 万 维 网 q 对 WEB上 的 文 档 进 行 分 类q 对 WEB日 志 的 数 据 进 行 聚 类 ， 以 发 现 相 同 的 用 户 访 问 模 式 什 么 是 好 的

3、聚 类 分 析 ？n 一 个 好 的 聚 类 分 析 方 法 会 产 生 高 质 量 的 聚 类q 高 类 内 相 似 度q 低 类 间 相 似 度n 作 为 统 计 学 的 一 个 分 支 ， 聚 类 分 析 的 研 究 主 要是 基 于 距 离 的 聚 类 ； 一 个 高 质 量 的 聚 类 分 析 结果 ， 将 取 决 于 所 使 用 的 聚 类 方 法 q 聚 类 方 法 的 所 使 用 的 相 似 性 度 量 和 方 法 的 实 施q 方 法 发 现 隐 藏 模 式 的 能 力 数 据 挖 掘 对 聚 类 分 析 的 要 求 (1)n 可 扩 展 性 (Scalability)q 大

4、 多 数 来 自 于 机 器 学 习 和 统 计 学 领 域 的 聚 类 算 法 在 处 理 数 百条 数 据 时 能 表 现 出 高 效 率n 处 理 不 同 数 据 类 型 的 能 力q 数 字 型 ； 二 元 类 型 ， 分 类 型 /标 称 型 ， 序 数 型 ,比 例 标 度 型 等等n 发 现 任 意 形 状 的 能 力 q 基 于 距 离 的 聚 类 算 法 往 往 发 现 的 是 球 形 的 聚 类 ， 其 实 现 实 的聚 类 是 任 意 形 状 的n 用 于 决 定 输 入 参 数 的 领 域 知 识 最 小 化q 对 于 高 维 数 据 ， 参 数 很 难 决 定 ， 聚

5、 类 的 质 量 也 很 难 控 制n 处 理 噪 声 数 据 的 能 力q 对 空 缺 值 、 离 群 点 、 数 据 噪 声 不 敏 感 数 据 挖 掘 对 聚 类 分 析 的 要 求 (2)n 对 于 输 入 数 据 的 顺 序 不 敏 感q 同 一 个 数 据 集 合 ， 以 不 同 的 次 序 提 交 给 同 一 个 算 法 ，应 该 产 生 相 似 的 结 果n 高 维 性q 高 维 的 数 据 往 往 比 较 稀 松 ， 而 且 高 度 倾 斜n 基 于 约 束 的 聚 类 q 找 到 既 满 足 约 束 条 件 ， 又 具 有 良 好 聚 类 特 性 的 数 据分 组n 可 解

6、 释 性 和 可 用 性q 聚 类 要 和 特 定 的 语 义 解 释 和 应 用 相 联 系 聚 类 分 析 中 的 数 据 类 型n 许 多 基 于 内 存 的 聚 类算 法 采 用 以 下 两 种 数据 结 构q 数 据 矩 阵 ： 用 p个 变 量来 表 示 n个 对 象n 也 叫 二 模 矩 阵 ， 行 与 列代 表 不 同 实 体 q 相 异 度 矩 阵 ： 存 储 n个对 象 两 两 之 间 的 临 近 度n 也 叫 单 模 矩 阵 ， 行 和 列代 表 相 同 的 实 体 npx.nfx.n1x . ipx.ifx.i1x . 1px.1fx.11x 0.)2,()1,( :

7、)2,3() .ndnd 0dd(3,1 0d(2,1)0 相 异 度 计 算n 许 多 聚 类 算 法 都 是 以 相 异 度 矩 阵 为 基 础 ， 如 果数 据 是 用 数 据 矩 阵 形 式 表 示 ， 则 往 往 要 将 其 先转 化 为 相 异 度 矩 阵 。n 相 异 度 d(i,j)的 具 体 计 算 会 因 所 使 用 的 数 据 类 型不 同 而 不 同 ， 常 用 的 数 据 类 型 包 括 ： q 区 间 标 度 变 量q 二 元 变 量q 标 称 型 、 序 数 型 和 比 例 标 度 型 变 量q 混 合 类 型 的 变 量 区 间 标 度 变 量n 区 间 标 度

8、 度 量 是 一 个 粗 略 线 性 标 度 的 连 续 度 量 ， 比 如 重 量 、 高 度等n 选 用 的 度 量 单 位 将 直 接 影 响 聚 类 分 析 的 结 果 ， 因 此 需 要 实 现 度 量值 的 标 准 化 ， 将 原 来 的 值 转 化 为 无 单 位 的 值 ， 给 定 一 个 变 量 f的 度量 值 ， 可 使 用 以 下 方 法 进 行 标 准 化 ：q 计 算 平 均 的 绝 对 偏 差 q 其 中q 计 算 标 准 化 的 度 量 值 (z-score)q 使 用 平 均 的 绝 对 偏 差 往 往 比 使 用 标 准 差 更 具 有 健 壮 性.).211

9、 nffff xx(xn m |)|.|(|1 21 fnffffff mxmxmxns f fifif s mx z 对 象 间 的 相 似 度 和 相 异 度 (1)n 对 象 间 的 相 似 度 和 相 异度 是 基 于 两 个 对 象 间 的距 离 来 计 算 的q Euclidean距 离 n i=(xi1,xi2,xip)和j=(xj1,xj2,xjp)是 两 个 p维数 据 对 象q Manhattan距 离 )|.|(|),( 2222211 pp jxixjxixjxixjid |.|),( 2211 pp jxixjxixjxixjid 对 象 间 的 相 似 度 和 相

10、异 度 (2)q Manhattan距 离 和 Euclidean距 离 的 性 质n d(i,j) 0n d(i,i) = 0n d(i,j) = d(j,i)n d(i,j) d(i,k) + d(k,j) q Minkowski距 离n 上 式 中 ， q为 正 整 数 ， 如 果 q=1则 表 示 Manhattan距 离 ， 如 果q=2则 表 示 Euclidean距 离q qppqq jxixjxixjxixjid )|.|(|),( 2211 二 元 变 量 (1)n 一 个 二 元 变 量 只 有 两 种 状 态 ： 0或 1；q e.g. smoker来 表 示 是 否 吸

11、 烟n 一 个 对 象 可 以 包 含 多 个 二 元 变 量 。n 二 元 变 量 的 可 能 性 表 ：q 如 何 计 算 两 个 二 元 变 量 之 间 的 相 似 度 ？pdbcasum dcdc baba sum 01 01O bject i O bject j 二 元 变 量 (2)n 对 称 的 VS. 不 对 称 的 二 元 变 量q 对 称 的 二 元 变 量 指 变 量 的 两 个 状 态 具 有 同 等 价 值 ， 相 同 权 重 ；e.g. 性 别q 基 于 对 称 的 二 元 变 量 的 相 似 度 称 为 恒 定 的 相 似 度 ， 可 以 使 用简 单 匹 配 系

12、 数 评 估 它 们 的 相 异 度 ： q 不 对 称 的 二 元 变 量 中 ， 变 量 的 两 个 状 态 的 重 要 性 是 不 同 的 ；e.g. HIV阳 性 VS HIV阴 性q 基 于 不 对 称 的 二 元 变 量 的 相 似 度 称 为 非 恒 定 的 相 似 度 ， 可 以使 用 Jaccard系 数 评 估 它 们 的 相 异 度 dcba cb jid ),( cba cb jid ),( 二 元 变 量 的 相 异 度 示 例Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4Jack M Y N P N N NMa

13、ry F Y N P N P N Jim M Y P N N N NP228 例 8.1 二 元 变 量 之 间 的 相 异 度 （ 病 人 记 录 表 ）Name是 对 象 标 识gender是 对 称 的 二 元 变 量其 余 属 性 都 是 非 对 称 的 二 元 变 量如 过 Y和 P（ positive阳 性 ） 为 1， N为 0， 则 ：75.0211 21),( 67.0111 11),( 33.0102 10),( maryjimd jimjackd maryjackd 标 称 变 量n 标 称 变 量 是 二 元 变 量 的 推 广 ， 它 可 以 具 有 多 于 两 个

14、的 状 态 值 。比 如 ： 红 、 绿 、 蓝 、 黄 。 对 于 标 称 型 变 量 ， 值 之 间 的 排 列 顺 序是 不 重 要 的 。n 计 算 标 称 变 量 所 描 述 的 对 象 （ 一 个 对 象 可 以 包 含 多 个 标 称 变 量 ）i和 j之 间 的 相 异 度 q 方 法 一 ： 简 单 匹 配 方 法n m: 匹 配 的 数 目 ， 即 对 象 i和 j取 值 相 同 的 变 量 的 数 目 (也 可 加 上 权 重 )q 方 法 二 ： 对 M个 标 称 状 态 中 的 每 个 状 态 创 建 一 个 新 的 二 元 变 量 ， 并用 非 对 称 的 二 元

15、变 量 来 编 码 标 称 变 量pmpjid ),(红 绿 蓝 黄 取 值0 1 0 0 绿0 0 1 0 蓝。 。 。 。 。 。 序 数 型 变 量n 一 个 序 数 型 变 量 可 以 是 离 散 的 或 者 是 连 续 的n 序 数 型 变 量 的 值 之 间 是 有 顺 序 关 系 的 ， 比 如 ： 讲师 、 副 教 授 、 正 教 授 。n 假 设 f是 描 述 n个 对 象 的 一 组 序 数 型 变 量 之 一 ， f的 相 异 度 计 算 如 下 ： q 1. 设 第 i个 对 象 的 f值 为 xif， 则 用 它 在 值 中 的 序 rif代替q 2. 将 每 个 变

16、 量 的 值 域 映 射 到 0,1的 空 间q 3. 采 用 区 间 标 度 变 量 的 相 异 度 计 算 方 法 计 算 f的 相异 度 11 fifif Mrz ,.,1 fif Mr 比 例 标 度 变 量n 一 个 比 例 标 度 型 变 量 xif是 在 非 线 性 的 标 度 中 所 取 的 正的 度 量 值 ， 例 如 指 数 标 度 ， 近 似 的 遵 循 以 下 公 式 ：AeBt or Ae-Bt n 计 算 比 例 标 度 型 变 量 描 述 的 对 象 之 间 的 相 异 度q 采 用 与 区 间 标 度 变 量 同 样 的 方 法 标 度 可 能 被 扭 曲 ，

17、效 果往 往 不 好 q 对 比 例 标 度 型 变 量 进 行 对 数 变 化 之 后 进 行 与 区 间 标 度 变 量 的相 似 处 理 yif = log(xif)q 将 xif看 作 连 续 的 序 数 型 数 据 ， 将 其 秩 作 为 区 间 标 度 的 值 来 对待 混 合 类 型 的 变 量n 在 真 实 的 数 据 库 中 ， 数 据 对 象 不 是 被 一 种 类 型 的 度 量所 描 述 ， 而 是 被 多 种 类 型 （ 即 混 合 类 型 ） 的 度 量 所 描述 ， 包 括 ：q 区 间 标 度 度 量 、 对 称 二 元 变 量 ， 不 对 称 二 元 变 量

18、， 标 称 变 量 ，序 数 型 变 量 合 比 例 标 度 变 量n 计 算 混 合 型 变 量 描 述 的 对 象 之 间 的 相 异 度 q 将 变 量 按 类 型 分 组 ， 对 每 种 类 型 的 变 量 进 行 单 独 的 聚 类 分 析n 在 每 种 聚 类 分 析 导 出 相 似 结 果 的 情 况 下 可 行q 所 有 变 量 一 起 处 理 ， 进 行 一 次 聚 类 分 析 ， 可 以 将 不 同 类 型 的变 量 组 合 在 单 个 相 异 度 矩 阵 中 ， 把 所 有 有 意 义 的 变 量 转 换 到共 同 的 值 域 区 间 0,1之 内 主 要 的 聚 类 方

19、 法n 聚 类 分 析 算 法 种 类 繁 多 ， 具 体 的 算 法 选 择 取 决 于 数 据类 型 ， 聚 类 的 应 用 和 目 的 ， 常 用 的 聚 类 算 法 包 括 ：q 划 分 方 法q 层 次 的 方 法q 基 于 密 度 的 方 法 q 基 于 网 格 的 方 法q 基 于 模 型 的 方 法n 实 际 应 用 中 的 聚 类 算 法 ， 往 往 是 上 述 聚 类 方 法 中 多 种方 法 的 整 合 划 分 方 法n 给 定 一 个 n个 对 象 或 元 组 的 数 据 库 ， 一 个 划 分 方 法 构建 数 据 的 k个 划 分 ， 每 个 划 分 表 示 一 个

20、 簇 ， 并 且 k=n。q 每 个 组 至 少 包 含 一 个 对 象q 每 个 对 象 属 于 且 仅 属 于 一 个 组n 划 分 准 则 ： 同 一 个 聚 类 中 的 对 象 尽 可 能 的 接 近 或 相 关 ，不 同 聚 类 中 的 对 象 尽 可 能 的 原 理 或 不 同n 簇 的 表 示 q k-平 均 算 法n 由 簇 的 平 均 值 来 代 表 整 个 簇q k中 心 点 算 法n 由 处 于 簇 的 中 心 区 域 的 某 个 值 代 表 整 个 簇 层 次 的 方 法n 对 给 定 数 据 对 象 集 合 进 行 层 次 分 解q 自 底 向 上 方 法 （ 凝 聚

21、 ） ： 开 始 将 每 个 对 象 作 为 单 独的 一 个 组 ， 然 后 相 继 的 合 并 相 近 的 对 象 或 组 ， 直 到所 有 的 组 合 并 为 一 个 ， 或 者 达 到 一 个 终 止 条 件 。q 自 顶 向 下 方 法 （ 分 裂 ） ： 开 始 将 所 有 的 对 象 置 于 一个 簇 中 ， 在 迭 代 的 每 一 步 ， 一 个 簇 被 分 裂 为 多 个 更小 的 簇 ， 直 到 最 终 每 个 对 象 在 一 个 单 独 的 簇 中 ， 或达 到 一 个 终 止 条 件 q 缺 点 ： 合 并 或 分 裂 的 步 骤 不 能 被 撤 销 基 于 密 度 的

22、 方 法n 基 于 距 离 的 聚 类 方 法 的 缺 点 ： 只 能 发 现 球 状 的簇 ， 难 以 发 现 任 意 形 状 的 簇 。n 基 于 密 度 的 据 类 ： 只 要 临 近 区 域 的 密 度 （ 对 象或 数 据 点 的 数 目 ） 超 过 某 个 临 界 值 ， 就 继 续 聚类 。 q 优 点 ： 可 以 过 滤 掉 “ 噪 声 ” 和 “ 离 群 点 ” ， 发 现 任意 形 状 的 簇 。 基 于 网 格 的 方 法n 把 对 象 空 间 量 化 为 有 限 数 目 的 单 元 ， 形 成 一 个网 格 结 构 。 所 有 的 聚 类 都 在 这 个 网 格 结 构

23、 上 进行 。q 优 点 ： 处 理 数 度 快 （ 因 为 处 理 时 间 独 立 于 数 据 对 象数 目 ， 只 与 量 化 空 间 中 每 一 维 的 单 元 数 目 有 关 ） 基 于 模 型 的 方 法n 为 每 个 簇 假 定 一 个 模 型 ， 寻 找 数 据 对 给 定 模 型的 最 佳 拟 合 。q 一 个 基 于 模 型 的 算 法 可 能 通 过 构 建 反 映 数 据 点 空 间分 布 的 密 度 函 数 来 定 位 聚 类q 这 种 方 法 同 时 也 用 于 自 动 的 决 定 数 据 集 中 聚 类 的 数目 n 通 过 统 计 学 的 方 法 ， 考 虑 噪

24、声 和 离 群 点 ， 从 而 产 生 健 壮 的聚 类 方 法 划 分 的 方 法n 给 定 n个 对 象 的 数 据 集 ， 以 及 要 生 成 的 簇 的 数目 k， 划 分 算 法 将 对 象 组 织 为 k个 划 分 （ k n）每 个 划 分 代 表 一 个 簇q 通 常 通 过 计 算 对 象 间 距 离 进 行 划 分n 典 型 的 划 分 方 法 q k均 值q k中 心 点q 以 上 两 种 方 法 的 变 种 基 于 质 心 的 技 术 ： k均 值 方 法n 簇 的 相 似 度 是 关 于 簇 中 对 象 的 均 值 度 量 ， 可 以 看作 簇 的 质 心 （ cen

25、troid）n k均 值 算 法 流 程1. 随 机 选 择 k个 对 象 ， 每 个 对 象 代 表 一 个 簇 的 初 始 均 值 或中 心2. 对 剩 余 的 每 个 对 象 ， 根 据 它 与 簇 均 值 的 距 离 ， 将 他 指派 到 最 相 似 的 簇 3. 计 算 每 个 簇 的 新 均 值4. 回 到 步 骤 2， 循 环 ， 直 到 准 则 函 数 收 敛n 常 用 准 则 函 数 ： 平 方 误 差 准 则21 iCpki mpE i (p是 空 间 中 的 点 ， mi是 簇 Ci的 均 值 ) k均 值 方 法 -示 例 0 1 2 3 4 5 6 7 8 9 10

26、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 10 012345678 910 0 1 2 3 4 5 6 7 8 9 10K=2随机选 择 2个 对象，作为簇的中心将每个对象指派到最相似的簇更 新 每个 簇 的均 值更 新 每个 簇 的均 值重新分派重新分派 k均 值 算 法 的 评 论n 可 扩 展 性 较 好 ， 算 法 复 杂 度 为 O(nkt)， 其 中 n为 对 象 总 数 ， k是 簇 的 个 数 ， t是 迭 代 次

27、 数 。n 经 常 终 止 于 局 部 最 优 解n 缺 点q 只 有 当 簇 均 值 有 定 义 的 情 况 下 ， k均 值 方 法 才 能 使用 。 （ 某 些 分 类 属 性 的 均 值 可 能 没 有 定 义 ） q 用 户 必 须 首 先 给 定 簇 数 目q 不 适 合 发 现 非 凸 形 状 的 簇 ， 或 者 大 小 差 别 很 大 的 簇q 对 噪 声 和 离 群 点 数 据 敏 感 k均 值 方 法 的 变 种n k均 值 方 法 有 些 变 种 ， 他 们 的 区 别 在 于q 不 同 的 初 始 k个 均 值 的 选 择q 不 同 的 相 异 度 计 算q 不 同 的

28、 计 算 簇 均 值 的 策 略n 聚 类 分 类 数 据 的 方 法 ： k众 数 （ mode） 方 法q 用 众 数 来 替 代 簇 的 均 值 q 采 用 新 的 相 异 性 度 量 处 理 分 类 对 象q 采 用 基 于 频 率 的 方 法 更 新 簇 的 众 数q 可 以 集 成 k均 值 和 k众 数 方 法 ， 对 具 有 数 值 和 分 类 值的 数 据 进 行 聚 类 基 于 代 表 对 象 的 技 术 ： k中 心 点 方 法n k均 值 方 法 对 于 离 群 点 敏 感q 一 个 具 有 很 大 极 端 值 的 对 象 可 能 显 著 的 扭 曲 数 据 的 分 布

29、q 平 方 误 差 函 数 将 进 一 步 严 重 恶 化 这 种 影 响n k中 心 点 方 法 ： 采 用 簇 的 中 心 点 ， 即 最 靠 近 中 心 的对 象 来 代 表 簇 q 降 低 算 法 对 离 群 点 的 敏 感 度 0123456789 10 0 1 2 3 4 5 6 7 8 9 10 012345678 910 0 1 2 3 4 5 6 7 8 9 10 k中 心 点 方 法 步 骤n k中 心 点 方 法 仍 然 基 于 最 小 化 所 有 对 象 与 其 对 应 的参 照 点 之 间 的 相 异 度 之 和 原 则 ， 使 用 的 是 绝 对 误差 标 准(p是

30、 空 间 中 的 点 ， 代 表 簇 Cj中 一 个 给 定 对 象 ； oj是 簇 Cj中 的 代 表 对 象 )n 通 常 该 算 法 重 复 迭 代 ， 直 到 每 个 代 表 对 象 都 成 为它 的 簇 的 实 际 中 心 点 q 首 先 随 意 选 择 初 始 代 表 对 象q 只 要 能 够 提 高 结 果 聚 类 质 量 ， 迭 代 过 程 就 使 用 非 代 表 对象 替 换 代 表 对 象n 聚 类 结 果 的 质 量 用 代 价 函 数 评 估 ， 该 函 数 度 量 对 象 与 其 簇 的 代表 对 象 之 间 的 平 均 差 异 度 jCpkj opE j 1 k中

31、心 点 方 法 -代 表 对 象 替 换 (1)+Oi +Ojp +Orandom1. 重 新 分 配 给 O i +Oi +Ojp +Orandom2. 重 新 分 配 给 Orandom+Oi +Ojp +Orandom3. 不 发 生 变 化 +Oi +Ojp +Orandom4. 重 新 分 配 给 Orandomn 为 了 确 定 非 代 表对 象 Orandom是 否能 够 替 代 当 前 代表 对 象 Oj， 对 于每 一 个 非 代 表 对象 p， 考 虑 四 种 情况 k中 心 点 方 法 -代 表 对 象 替 换 (2)n 重 新 分 配 将 对 代 价 函 数 产 生 影

32、 响 ， 如 果 当 前 的代 表 对 象 被 非 代 表 对 象 所 取 代 ， 代 价 函 数 就 是计 算 绝 对 误 差 值 的 差n 变 换 的 总 代 价 是 所 有 非 代 表 对 象 所 产 生 的 代 价之 和 q 总 代 价 为 负 ， 实 际 的 绝 对 误 差 E将 减 少 ， Oj可 以 被Orandom所 取 代q 总 代 价 为 正 ， 则 本 次 迭 代 没 有 变 化 k均 值 方 法 与 k中 心 点 方 法 比 较n 当 存 在 噪 声 和 离 群 点 时 ， k中 心 点 方 法 比 k均 值方 法 更 加 鲁 棒q 中 心 点 较 少 的 受 离 群

33、点 影 响n k中 心 点 方 法 的 执 行 代 价 比 k均 值 方 法 要 高q k均 值 方 法 ： O(nkt) q k中 心 点 方 法 ： O(k(n-k)2)n n与 k较 大 时 ， k中 心 点 方 法 的 执 行 代 价 很 高n 两 种 方 法 都 要 用 户 指 定 簇 的 数 目 k 离 群 点 分 析n 什 么 是 离 群 点 ？q 一 个 数 据 集 与 其 他 数 据 有 着 显 著 区 别 的 数 据 对 象 的 集 合q 例 如 ： 运 动 员 ： Michael Jordon, 舒 马 赫 ， 布 勃 卡n 离 群 点 产 生 原 因q 度 量 或 执

34、行 错 误 （ 年 龄 ： -999）q 数 据 变 异 的 结 果n 离 群 点 挖 掘 q 给 定 一 个 n个 数 据 对 象 的 集 合 ， 以 及 预 期 的 离 群 点 数 目 k， 发 现 与 剩 余 的 数 据 有 着 显 著 差 异 的 头 k个 数 据 对 象n 应 用q 欺 诈 检 测 、 医 疗 中 的 异 常 分 析 等 基 于 统 计 的 离 群 点 检 测n 统 计 的 方 法 对 于 给 定 的 数 据 集 合 假 定 了 一 个 分 布 或 概率 模 型 （ 例 如 正 态 分 布 ）n 使 用 依 赖 于 以 下 参 数 的 不 一 致 性 检 验 （ di

35、scordancy tests）q 数 据 分 布 q 分 布 参 数 （ e.g. 均 值 或 方 差 ）q 预 期 的 离 群 点 数n 缺 点q 绝 大 多 数 检 验 是 针 对 单 个 属 性 的 ， 而 数 据 挖 掘 要 求 在 多 维 空间 中 发 现 离 群 点q 大 部 分 情 况 下 ， 数 据 分 布 可 能 是 未 知 的 基 于 距 离 的 离 群 点 检 测n 为 了 解 决 统 计 学 方 法 带 来 的 一 些 限 制 ， 引 入 了基 于 距 离 的 离 群 点 检 测q 在 不 知 道 数 据 分 布 的 情 况 下 对 数 据 进 行 多 维 分 析n

36、基 于 距 离 的 离 群 点 ： 即 DB(p,d)， 如 果 数 据 集合 S中 的 对 象 至 少 有 p部 分 与 对 象 o的 距 离 大 于d， 则 对 象 o就 是 DB(p,d)。n 挖 掘 基 于 距 离 的 离 群 点 的 高 效 算 法 ： q 基 于 索 引 的 算 法q 嵌 套 循 环 算 法q 基 于 单 元 的 算 法 基 于 偏 离 的 离 群 点 检 测n 通 过 检 查 一 组 对 象 的 主 要 特 征 来 确 立 离 群 点n 跟 主 要 特 征 的 描 述 相 “ 偏 离 ” 的 对 象 被 认 为 是离 群 点n 两 种 基 于 偏 离 的 离 群 点 探 测 技 术q 序 列 异 常 技 术 n 模 仿 人 类 从 一 系 列 推 测 类 似 的 对 象 中 识 别 异 常 对 象 的 方 式q OLAP数 据 立 方 体 技 术n 在 大 规 模 的 多 维 数 据 中 采 用 数 据 立 方 体 来 确 定 异 常 区 域 。如 果 一 个 立 方 体 的 单 元 值 显 著 的 不 同 于 根 据 统 计 模 型 得 到的 期 望 值 ， 则 改 单 元 值 被 认 为 是 一 个 异 常 ， 并 用 可 视 化 技术 表 示 。