Vol.26 No.5 张德政等：基于支持向量机挖据不一致事例隐含的异常信息 ·565. 定义的一族等价关系， 则间隔为2wl,因此使间隔最大等价于使w最 1.2不一致信息表 小，面对训练样本集(xy),i=1,2,…,n,x∈R,yE 一般在决策表中可能存在以下三种不一致 {1,-1,分类线应满足 信息： y(wx+b)-1≥0. (1)决策表中包含冲突（矛盾）样本，即两个样 满足上述条件的分类线为最优分类线.经过一系 本的条件属性取值完全相同，而决策（分类）属性 列优化方法推导后，上述求最优分类面的问题转 的取值不同.这种不一致的产生，主要有三种可 化为下列问题： 能性：(a)条件属性不充分.根据所采用的条件属 ya=0,a=0,i=1,2,,n. 性不能对样本进行正确分类，必须增加额外的条 对a,求解下列函数的最大值： 件属性才能够正确区分样本.()样本属性值的测 量和记录有误差或错误.（©）在产生决策表的预处 ayx:) 理过程中产生了冲突，如在离散化过程中，可能 这是一个在不等式约束下的二次函数寻优问题， 把本来可以区分的样本变得不可区分. 存在惟一解，可以证明，以上优化问题的解中将 (2)决策表中无冲突情况，在决策表化简过程 只有一部分（通常是很少部分）的a不为零，非0 中产生的不一致.对于本身一致或不一致的决策 的a所对应的样本仅由最靠近超平面的样本组 表，有的化简算法将导致一些新的不一致性信 成，这些样本完全确定了超平面，因此称为支持 息，比如Skowron的缺省规则获取方法. 向量.解上述问题后得到的最优分类函数是： (3)决策表只包含了所有可能样本（或者样本 f)=sgn(（ox+b)=sg(②ayc:xHb). 全集.问题空间)中的一部分，没有包括所有可能 这就是支持向量机.从支持向量机算法不难得 出现的样本情况，即待识样本和决策表中的样本 出：判别函数x)由支持向量惟一决定且支持向 有冲突， 量是训练集中的基本元素，它们离决策边界最 第三种不一致是在规则知识的获取过程中 近，若任何非支持向量被移去，重复训练，分离超 所不能预料的，在发现不一致情况之前，不能肯 平面不会改变，而移去一个支持向量，则决策平 定系统是否包含不一致性.而前两种不一致情况 面往往改变，即支持向量是两类边界上的点，通 是从待处理的决策表中就可以直接发现的， 过求支特向量可求出两类数据集中边界上的点， 2支持向量机与支持向量 支持向量机(Support Vector Machine,SVM)方 法是从线性可分情况下的最优分类面提出的.所 H 谓最优分类面，就是这样的分类超平面，它不但 H 能够将所有训练样本正确分类，而且使训练样本 ● 中离分类面最近的点到分类面的距离（定义为间 隔)最大，通过使间隔最大化来控制分类器的复 图1支持向量机线性最优分类线 Fig.1 Optimum classifying line of SVM 杂度，进而实现较好的推广能力.在线性不可分 的情况下，有广义最优分类面问题，即在追求最 3不一致事例所隐含的信息挖掘 大化分类间隔的同时最小化错分样本的数目， 如图1所示，在二维情况下，实心点和空心点 31不一致事例的类型 分别代表两类，H为两类的分类线，H,H分别为 对于信息表中的数据，如果采用不产生不一 过各类样本中离分类线最近且平行于分类线的 致事例的离散化方法，那么就排除了离散化造成 直线，它们之间的距离叫做间隔(margin),记为b. 不一致事例的原因. 最优分类线就是要求分类线不但能将两类正确 这样，除了个别数量很少的不一致事例是由 分开，而且要使两类的间隔最大.可以证明，如果 于各种错误（如记录错误）造成以外，一定数量 分类线为 (多次重复出现)的不一致事例出现的原因就剩 xw+b)-1=0, 下两种：一种是不一致事例在两类的边界上，如一 一 张德 政 等 基 于 支持 向量 机 挖 掘 不 一 致 事例 隐含的异 常信 息 定 义 的一 族 等 价 关 系 不 一致 信 息 表 一 般 在 决 策 表 中可 能 存 在 以下 三 种 不 一 致 信 息 决策 表 中包 含 冲 突 矛盾 样 本 ， 即两个样 本 的条件 属 性 取 值 完全 相 同 ， 而 决策 分类 属 性 的取 值 不 同 这 种 不 一 致 的产 生 ， 主 要 有三 种 可 能性 条 件 属 性 不 充分 根 据 所 采 用 的条件 属 性 不 能对 样 本进 行 正 确 分 类 ， 必 须 增 加 额 外 的条 件 属 性才 能够 正确 区 分样 本 伪 样 本 属 性值 的测 量 和 记 录 有误 差 或 错 误 在 产 生 决策 表 的预 处 理 过程 中产 生 了冲 突 如 在 离 散化 过 程 中 ， 可 能 把 本来 可 以区 分 的样本 变 得 不 可 区 分 决策 表 中无 冲突情 况 ， 在 决策表 化 简过程 中产 生 的不 一 致 对 于本 身一致 或 不 一致 的决策 表 ， 有 的化 简 算 法 将 导 致 一 些 新 的 不 一 致 性 信 息 ， 比 如 的缺 省规 则 获取 方 法 决策 表 只 包 含 了所 有 可 能样 本 或 者 样 本 全 集 问题 空 间 中 的一 部 分 ， 没 有 包 括 所 有 可 能 出现 的样 本 情 况 ， 即待 识样 本和 决策 表 中 的样 本 有 冲 突 第 三 种 不 一 致 是 在 规 则 知 识 的 获 取 过 程 中 所 不 能预 料 的 ， 在 发 现 不 一 致 情 况 之 前 ， 不 能 肯 定系 统 是 否 包 含 不 一 致 性 而 前 两 种 不 一 致 情况 是 从 待处 理 的决策 表 中就 可 以直 接 发现 的 则 间 隔 为 】 ， 因此 使 间 隔最 大 等 价 于 使 最 小 ， 面 对 训 练 样 本 集 ， ，川 ， ， ， … ，。 ， 任 气 任 ， 一 ， 分 类 线 应 满 足 笋 · 一 之 满 足 上 述 条件 的分类 线 为最 优 分类 线 经 过 一 系 列 优化 方 法 推 导 后 ， 上述 求 最优 分类 面 的 问题 转 化 为 下 列 问题 艺夕召， ， ‘ ， ， ， … ， 对 ‘求 解 下 列 函 数 的最 大值 卜 久一 操乃 、 ， · ， 这 是 一 个 在 不 等 式 约束 下 的二 次 函数 寻优 问题 ， 存 在 惟 一 解 可 以证 明 ， 以上 优 化 问题 的解 中将 只 有 一 部 分 通 常 是 很 少 部 分 的 氏 不 为零 ， 非 的 ‘ 所 对 应 的样 本 仅 由最 靠 近 超 平 面 的样 本 组 成 ， 这 些 样 本 完 全 确 定 了超 平 面 ， 因此 称 为支 持 向量 解 上 述 问题 后 得 到 的最 优 分类 函 数 是 。 · 艺 ‘必 ‘ · 这 就 是 支 持 向量 机 从 支 持 向量 机 算 法 不 难 得 出 判 别 函数刀大 由支 持 向量惟 一 决 定 且 支 持 向 量 是 训 练 集 中 的基 本 元 素 ， 它 们 离 决 策 边 界 最 近 ， 若 任 何 非支 持 向量 被移 去 ， 重 复训练 ， 分离超 平 面 不会 改 变 ， 而 移 去 一 个 支 持 向量 ， 则 决策 平 面 往 往 改变 ， 即支 持 向量 是 两类 边 界 上 的 点 通 过 求支 持 向量 可求 出两类 数 据 集 中边 界上 的点 支持 向量 机 与支 持 向量 ‘ 支 持 向量 机 ， 方 法 是 从 线 性 可分 情 况 下 的最优 分类面 提 出的 所 谓 最 优 分 类 面 ， 就 是 这 样 的分 类 超 平 面 ， 它 不但 能够 将所 有 训 练样 本 正确 分类 ， 而 且 使 训练 样 本 中离分类 面 最 近 的 点 到 分 类 面 的距 离 定义 为 间 隔 最 大 通 过 使 间 隔最 大 化 来 控 制 分 类 器 的复 杂度 ， 进 而 实现 较 好 的推 广 能力 在 线 性 不 可 分 的情 况 下 ， 有 广 义 最优 分 类 面 问题 ， 即在 追 求 最 大 化 分 类 间 隔 的 同 时最 小 化 错 分 样 本 的数 目 如 图 所 示 ， 在 二 维情况 下 ， 实心 点和 空心 点 分 别代 表 两 类 ， 为 两 类 的分 类 线 ，私 ， 从 分 别 为 过 各 类 样 本 中离 分 类 线 最 近 且 平 行 于 分 类 线 的 直 线 ， 它 们 之 间 的距 离 叫做 间 隔 ， 记 为 最 优 分 类 线 就 是 要 求 分 类 线 不 但 能 将 两 类 正 确 分 开 ， 而 且 要 使两类 的间 隔最 大 可 以证 明 ， 如 果 分类 线 为 少 · 一 ， 图 支持 向量 机 线 性最 优 分 类线 · 介 五度 不 一 致 事 例 所 隐 含 的信 息 挖 掘 不 一 致 事 例 的 类型 对 于信 息表 中 的数 据 ， 如 果 采用 不产 生 不 一 致 事例 的离 散化 方 法 ， 那 么 就 排 除 了离散化 造 成 不 一 致 事 例 的原 因 这 样 ， 除 了个 别 数 量 很 少 的不 一 致 事 例 是 由 于 各 种 错 误 如 记 录 错 误 造 成 以外 ， 一 定 数量 多 次 重 复 出现 的不 一 致 事例 出现 的原 因就 剩 下 两 种 一 种 是 不 一 致 事例 在 两类 的边 界上 ， 如