D0I:10.13374/i.is8nm1001053x.2001.05.027 第26卷第5期 北京科技大学学报 VoL.26 No.5 2004年10月 Journal of University of Science and Technology Beijing 0ct.2004 基于支持向量机挖掘不一致事例 隐含的异常信息 张德政阿孜古丽冯洪海 杨炳儒 北京科技大学信息工程学院,北京100083 摘要基于支持向量机,提出一种挖掘粗集信息表中不一致事例背后隐藏某种有价值信 息的算法,即不一致是由于错误引起,还是由于误差引起,抑或是由于缺少属性引起,并提出 一些排除不一致的方案和算法。 关键词知识发现:粗糙集:支持向量机:不一致 分类号TP18 在利用粗集对信息表进行处理以挖掘规则 定的由缺少条件属性引起的不一致,也不用花力 时,经常存在着不一致事例,以往不一致推理策 量去减少误差,提高精度. 略对信息表中的不一致事例并不予以分析、处 本文通过支持向量机提出辨别不一致事例 理,或是将这些不一致事例删除,或是在保留这 是否隐含有价值信息的算法,即不一致是由于错 些不一致事例的基础上,通过其他方法挖掘带有 误引起,还是由于误差引起,拟或是由于缺少属 一定可信度的规则然而正是这些矛盾的地 性引起,并提出一些排除不一致的方案和算法. 方,会隐含着某些使人感兴趣、有价值的信息.在 为对不一致事例进行进一步处理,找寻有价值、 数据挖掘中,挖掘出的知识常常是显而易见的知 感兴趣的信息提供前提. 识,如何挖掘出决策者、研究者感兴趣的知识,是 数据挖掘、知识发现领域的重大课题.事物间的 1信息表与不一致信息表倒 矛盾和不一致蕴含着其本质上的原因.因而事物 11信息系统的表示(信息表) 间矛盾、不一致背后的原因肯定是人们感兴趣的 在粗糙集中,一个信息系统S是一个四元 知识.关注问题,关注矛盾,有利于发现非同寻 组: 常、有意义的知识. S=. 不一致信息一般由错误、误差或缺少属性引 其中,U是对象(或事例)的有限集合,即论域: 起.特别地,当样本数据处于两类边界时,样本对 A=CUD是属性的集合,C表示条件属性集,D 误差比较敏感,由于误差可能产生大量不一致样 表示决策属性集:V是属性的值域集,=UV,V。 例,或不能确定类属的样例.此时区分哪些样例 在什么条件下产生什么样的误差,就有一定意 是属性a∈A的值域:f是信息函数,f:UxA一V,即 义,因为这可指导以后取得数据时尽量避免误 fx,a)e'.,它指定U中每一对象的属性值.信息 系统可以方便地用数据表格形式来表示.在信息 差.一般地,检查误差、提高精度比增加条件属性 系统数据表中,列表示属性,行表示对象(如状 容易,因为增加条件属性可能是个比较长的过 态、过程等),并且每一行表示该对象的一一条信 程,如果不一致由误差引起,便没有必要花大量 息.因此,信息系统也称为信息表或决策表.论域 时间精力去寻找需增加的条件属性,而对那些确 中的对象根据条件属性的不同,被划分到具有不 收稿日期2003-12-26张德政男,40岁,副教授,博士 同决策属性的决策类.或者说,信息表中的一个 ★科技部推广应用项目No,EC1O0OOO)及校科研启动基金资助属性对应一个等价关系,一个信息表可以看作是
第 ‘ 卷 第 期 年 月 北 京 科 技 大 学 学 报 】 一 基于支持 向量机挖掘不一致事例 隐含的异常信息 张德 政 阿 孜 古 丽 冯 洪 海 杨 炳 儒 北 京 科技大学信息工 程 学 院 , 北 京 摘 要 基 于 支持 向量 机 , 提 出一 种挖掘粗 集信 息 表 中不 一 致事例 背 后 隐藏某种有 价值 信 息 的算法 , 即不 一 致是 由于 错 误 引起 , 还 是 由于 误 差 引起 , 抑 或 是 由于缺 少属性 引起 , 并提 出 一 些 排 除不 一 致 的方 案和 算法 关键词 知 识 发现 粗糙 集 支 持 向量 机 不 一 致 分 类号 仰 在 利 用 粗 集 对 信 息 表 进 行 处 理 以挖 掘 规 则 时 , 经 常存在着 不 一 致事例 以往 不 一致 推理 策 略对 信 息 表 中 的不 一 致 事例 并不 予 以分 析 、 处 理 , 或 是 将这 些 不 一 致 事 例 删 除 , 或 是 在 保 留这 些 不 一致 事例 的基 础 上 , 通 过其 他 方法 挖 掘 带有 一 定可 信 度 的规 则 ‘ 刀 然 而 正 是 这 些 矛盾 的地 方 , 会 隐含着 某些 使人感 兴趣 、 有 价值 的信 息 在 数据挖掘 中 , 挖掘 出的知 识 常常是 显 而 易见 的知 识 , 如何挖 掘 出决策 者 、 研 究者 感 兴趣 的知 识 , 是 数据 挖 掘 、 知 识 发 现 领 域 的重 大课题 事 物 间 的 矛盾 和 不 一致 蕴 含 着其 本质 上 的原 因 因而 事物 间矛盾 、 不 一致 背后 的原 因肯 定 是人 们 感 兴趣 的 知 识 关注 问题 , 关注 矛 盾 , 有 利 于 发现 非 同寻 常 、 有 意 义 的知 识 不 一 致 信 息 一般 由错 误 、 误 差 或 缺 少属 性 引 起 特 别地 , 当样 本数据 处 于 两类边 界 时 , 样 本对 误 差 比较 敏 感 , 由于误 差 可 能产 生 大量 不 一致样 例 , 或 不 能确 定类 属 的样 例 此 时 区 分 哪 些 样 例 在 什 么 条 件 下 产 生 什 么 样 的误 差 , 就 有 一 定 意 义 , 因 为这 可 指 导 以后 取 得 数据 时尽 量 避 免误 差 一般 地 , 检 查误 差 、 提 高精度 比增加 条件 属性 容 易 , 因 为增 加 条 件 属 性 可 能 是 个 比较 长 的过 程 , 如 果 不 一 致 由误 差 引起 , 便 没 有 必 要 花 大 量 时 间精 力去 寻 找 需增 加 的条件 属 性 而 对 那 些 确 定 的 由缺 少 条件 属性 引起 的不一 致 , 也 不用 花 力 量 去 减 少误 差 , 提 高精度 本 文 通 过 支 持 向量 机 提 出辨 别 不 一 致 事例 是否 隐含 有 价值信 息 的算法 , 即不 一 致是 由于 错 误 引起 , 还 是 由于 误 差 引起 , 拟 或 是 由于 缺 少 属 性 引起 , 并提 出一 些 排 除不 一 致 的方 案 和 算法 为对 不 一 致 事 例 进 行 进 一 步 处 理 , 找 寻 有 价 值 、 感 兴趣 的信 息提供前 提 信 息 表 与 不 一 致 信 息 表 ‘ 信 息 系统 的表 示 信 息 表 在 粗 糙 集 中 , 一 个 信 息 系 统 是 一 个 四 元 组 , , ,介 · 收稿 日期 一 一 张德 政 男 , 岁 , 副教授 , 博 士 科技部推广 应 用项 目 及 校科研启 动基 金 资助 其 中 , 是对 象 或 事例 的有 限集 合 , 即 论域 二 是 属 性 的 集 合 , 表 示 条 件 属 性 集 , 表 示 决策 属 性 集 是 属 性 的值 域 集 , 魁代 , 代 是属 性 的值域 是信 息 函 数 , 一 , 即 刀 尤, 任 , 它指 定 中每 一对 象 的属 性值 信 息 系统 可 以方 便地 用 数据 表 格 形式 来表 示 在信 息 系 统 数 据 表 中 , 列 表 示 属 性 , 行 表 示对 象 如状 态 、 过 程 等 , 并 且 每 一 行 表 示 该对 象 的一 条信 息 因此 , 信 息 系统 也称 为信 息表 或 决策表 论域 中的对 象根 据 条件 属性 的不 同 , 被划 分 到具有 不 同决 策属 性 的决策类 或 者 说 , 信 息表 中 的一 个 属 性对 应 一 个等价 关 系 , 一 个信 息表 可 以看作是 DOI :10.13374/j .issn1001-053x.2004.05.027
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, 下两种:一种是不一致事例在两类的边界上,如
一 一 张德 政 等 基 于 支持 向量 机 挖 掘 不 一 致 事例 隐含的异 常信 息 定 义 的一 族 等 价 关 系 不 一致 信 息 表 一 般 在 决 策 表 中可 能 存 在 以下 三 种 不 一 致 信 息 决策 表 中包 含 冲 突 矛盾 样 本 , 即两个样 本 的条件 属 性 取 值 完全 相 同 , 而 决策 分类 属 性 的取 值 不 同 这 种 不 一 致 的产 生 , 主 要 有三 种 可 能性 条 件 属 性 不 充分 根 据 所 采 用 的条件 属 性 不 能对 样 本进 行 正 确 分 类 , 必 须 增 加 额 外 的条 件 属 性才 能够 正确 区 分样 本 伪 样 本 属 性值 的测 量 和 记 录 有误 差 或 错 误 在 产 生 决策 表 的预 处 理 过程 中产 生 了冲 突 如 在 离 散化 过 程 中 , 可 能 把 本来 可 以区 分 的样本 变 得 不 可 区 分 决策 表 中无 冲突情 况 , 在 决策表 化 简过程 中产 生 的不 一 致 对 于本 身一致 或 不 一致 的决策 表 , 有 的化 简 算 法 将 导 致 一 些 新 的 不 一 致 性 信 息 , 比 如 的缺 省规 则 获取 方 法 决策 表 只 包 含 了所 有 可 能样 本 或 者 样 本 全 集 问题 空 间 中 的一 部 分 , 没 有 包 括 所 有 可 能 出现 的样 本 情 况 , 即待 识样 本和 决策 表 中 的样 本 有 冲 突 第 三 种 不 一 致 是 在 规 则 知 识 的 获 取 过 程 中 所 不 能预 料 的 , 在 发 现 不 一 致 情 况 之 前 , 不 能 肯 定系 统 是 否 包 含 不 一 致 性 而 前 两 种 不 一 致 情况 是 从 待处 理 的决策 表 中就 可 以直 接 发现 的 则 间 隔 为 】 , 因此 使 间 隔最 大 等 价 于 使 最 小 , 面 对 训 练 样 本 集 , ,川 , , , … ,。 , 任 气 任 , 一 , 分 类 线 应 满 足 笋 · 一 之 满 足 上 述 条件 的分类 线 为最 优 分类 线 经 过 一 系 列 优化 方 法 推 导 后 , 上述 求 最优 分类 面 的 问题 转 化 为 下 列 问题 艺夕召, , ‘ , , , … , 对 ‘求 解 下 列 函 数 的最 大值 卜 久一 操乃 、 , · , 这 是 一 个 在 不 等 式 约束 下 的二 次 函数 寻优 问题 , 存 在 惟 一 解 可 以证 明 , 以上 优 化 问题 的解 中将 只 有 一 部 分 通 常 是 很 少 部 分 的 氏 不 为零 , 非 的 ‘ 所 对 应 的样 本 仅 由最 靠 近 超 平 面 的样 本 组 成 , 这 些 样 本 完 全 确 定 了超 平 面 , 因此 称 为支 持 向量 解 上 述 问题 后 得 到 的最 优 分类 函 数 是 。 · 艺 ‘必 ‘ · 这 就 是 支 持 向量 机 从 支 持 向量 机 算 法 不 难 得 出 判 别 函数刀大 由支 持 向量惟 一 决 定 且 支 持 向 量 是 训 练 集 中 的基 本 元 素 , 它 们 离 决 策 边 界 最 近 , 若 任 何 非支 持 向量 被移 去 , 重 复训练 , 分离超 平 面 不会 改 变 , 而 移 去 一 个 支 持 向量 , 则 决策 平 面 往 往 改变 , 即支 持 向量 是 两类 边 界 上 的 点 通 过 求支 持 向量 可求 出两类 数 据 集 中边 界上 的点 支持 向量 机 与支 持 向量 ‘ 支 持 向量 机 , 方 法 是 从 线 性 可分 情 况 下 的最优 分类面 提 出的 所 谓 最 优 分 类 面 , 就 是 这 样 的分 类 超 平 面 , 它 不但 能够 将所 有 训 练样 本 正确 分类 , 而 且 使 训练 样 本 中离分类 面 最 近 的 点 到 分 类 面 的距 离 定义 为 间 隔 最 大 通 过 使 间 隔最 大 化 来 控 制 分 类 器 的复 杂度 , 进 而 实现 较 好 的推 广 能力 在 线 性 不 可 分 的情 况 下 , 有 广 义 最优 分 类 面 问题 , 即在 追 求 最 大 化 分 类 间 隔 的 同 时最 小 化 错 分 样 本 的数 目 如 图 所 示 , 在 二 维情况 下 , 实心 点和 空心 点 分 别代 表 两 类 , 为 两 类 的分 类 线 ,私 , 从 分 别 为 过 各 类 样 本 中离 分 类 线 最 近 且 平 行 于 分 类 线 的 直 线 , 它 们 之 间 的距 离 叫做 间 隔 , 记 为 最 优 分 类 线 就 是 要 求 分 类 线 不 但 能 将 两 类 正 确 分 开 , 而 且 要 使两类 的间 隔最 大 可 以证 明 , 如 果 分类 线 为 少 · 一 , 图 支持 向量 机 线 性最 优 分 类线 · 介 五度 不 一 致 事 例 所 隐 含 的信 息 挖 掘 不 一 致 事 例 的 类型 对 于信 息表 中 的数 据 , 如 果 采用 不产 生 不 一 致 事例 的离 散化 方 法 , 那 么 就 排 除 了离散化 造 成 不 一 致 事 例 的原 因 这 样 , 除 了个 别 数 量 很 少 的不 一 致 事 例 是 由 于 各 种 错 误 如 记 录 错 误 造 成 以外 , 一 定 数量 多 次 重 复 出现 的不 一 致 事例 出现 的原 因就 剩 下 两 种 一 种 是 不 一 致 事例 在 两类 的边 界上 , 如
·566· 北京科技大学学报 2004年第5期 图2中的A:和B,由于人们认识上的差距,即模糊 通过增加新的条件属性,使得不相容的决策 化概念上的错误,以及观察、测量上的误差,使得 问题变得相容、一致,使获得数据中隐含的新的 这些不一致样例的条件属性取值全相同.还有一 信息、知识.但是,那些不一致病例有可能通过增 种就是不一致样例不在两类的边界(如图2中的 加临床症状观察范围即增加条件属性来排除不 A2点和B:点),或所在的两类根本不是相邻类(如 一致情况:而那些又不是由于缺少条件属性引起 图2中的C,和B),.这些不一致样例由于不相邻, 的不一致现象,又怎样通过提高观察精度来消除 所以不可能由于误差引起不一致,只可能是由于 不一致现象呢? 缺少一个或几个条件属性引起不一致,而这些条 3.3用支持向量机判别不一致事例所在类别的 件属性值肯定不同,这些属性就成了区分不一致 位置 事例的依据. 判断不一致样例距离某一类的中心远近并 不能说明其属于或不属哪那一类,而应该看这个 数据在某一类的中心上还是边界上,因为支持向 量在两类数据的边界上,可以通过支持向量机判 定样例是否远离支持向量机决策平面来决定样 例是否在两类边界上, 利用支持向量机训练时,不让不一致样例参 ●C, 加训练,因为一般它们占的比例很小,并且还要 图2不一致样例可能的相互关系 将它们用来测试,以确定它们的类别.即信息表 Fig.2 Relationship in inconsistent case 中给出不一致样例两个或多个类别,无从根据现 3.2判别不一致事例类型的意义 有数据集认定它应该属于哪一类,因此需要用分 对于重复很少的不一致现象,因为没有统计 类手段去判别它在现有数据集的条件下属于哪 学上的意义,以及多属偶然现象,而且多属于人 一类,分类时看这些样例处在哪一类的什么位 为错误造成,因此不予分析处理,即不一致事例 置,也就是让不一致样例作为待测样本,如果不 大于某数量时才进行分析.这样可以节省的精 一致样本通过分类发现在某类的边界上,则样本 力,并提高分析问题的准确性. 因为不属于另一类,所以也处于另一类的边界 不论是决策表中的样本互相有冲突还是待 上.由条件属性值或结论属性值的微小误差引起 识样本和决策表中的样本有冲突,不外乎上述提 的不一致造成的矛盾或不相容并不严重,是一种 到的前两种情况,即条件属性不充分,或人为误 正常的测量观察误差引起的.可以寻找哪些属性 差导致的不精确或错误,如果能区分出这两种情 值有误差,通过提高精确度来排除不一致现象, 况,对进一步对信息表进行预处理很有帮助.如 如果将不一致样例作为待识样本,通过分 果是条件属性不充分,就着眼于增加条件属性; 类,发现它是远离某一类边界的点,即远离分类 如果是测量和观察的不精确,就着眼于如何提高 面一定阈值的点.则这将引起较大的误差、矛盾, 属性值的精度, 肯定是由于缺少属性引起的. 比如,在非典型性肺炎的诊断中,具有相同 样例处在两类边界但属于不同的类,有可能 症状的病人,可能最后的诊断结果截然相反:一 出现在诸如疾病的早期诊断等情形中,由于指标 个是非典病人,一个被排除.这就是一种不一致 数值都小,如低烧,咳嗦症状轻,肺部阴影少等, 现象.如果有一定重复,那么,这种不一致现象的 给诊断是否得病或分成不同的类造成困难.但找 解决将对临床有重大意义.这可启发医务人员和 到导致不同疾病的病因对于人类重大疾病的早 研究人员去探究到底缺少哪些诊断因素(条件属 期诊断有重大意义. 性),而这些因素(条件属性)决定了非典型性肺 3.4不一致样例所含信息类型判别算法 炎的确诊.也就是说,缺少的属性是结论的充分 输入:一决策表S=(U,C,D,V,),其中U是论 性属性.或者增加哪些措施,可以使得检验更加 域:C,D分别为条件和决策属性集:V=UV。,其 准确,以体现出样例之间的区别,而不至于混淆, 中,'。是属性a∈A的值域:A=CUD是属性的集 造成不一致样例. 合;∫是信息函数
· 北 京 科 技 大 学 学 报 年 第 期 图 中 的 和 , 由于 人们 认 识上 的差距 , 即模糊 化 概念 上 的错 误 , 以及观 察 、 测 量 上 的误 差 , 使得 这 些 不一致样例 的条 件属 性 取 值 全 相 同 还 有一 种就 是不 一 致样 例 不 在 两 类 的边 界 如 图 中 的 点和 点 , 或 所 在 的两类 根 本 不 是 相 邻类 如 图 中 的 和及 , 这些 不 一 致样 例 由于 不 相邻 , 所 以不 可 能 由于误 差 引起 不 一致 , 只 可 能 是 由于 缺 少一 个或 几个条 件 属性 引起 不一 致 , 而 这 些 条 件属 性值 肯 定不 同 , 这些 属 性就 成 了区 分 不一 致 事例 的依 据 图 不 一 致样例 可 能的相 互 关系 恤 犯 判 别 不 一 致 事例 类型 的意 义 对 于 重 复很 少 的不 一 致 现 象 , 因 为没 有 统 计 学 上 的意义 , 以及 多属 偶然 现 象 , 而 且 多属 于 人 为错 误 造 成 , 因此 不 予 分 析 处 理 , 即不 一 致 事 例 大 于 某 数 量 时才 进 行 分 析 , 这 样 可 以节 省 的精 力 , 并提 高分 析 问题 的准 确 性 不 论 是 决 策 表 中 的样 本 互 相 有 冲 突 还 是 待 识样 本和 决策 表 中 的样本 有 冲 突 , 不外 乎 上述 提 到 的前 两 种 情 况 , 即条 件 属 性 不 充 分 , 或人 为误 差 导致 的不精 确或 错 误 如 果 能 区分 出这 两 种情 况 , 对进 一 步对 信 息 表 进 行 预 处 理 很 有 帮助 如 果是 条件 属 性 不 充 分 , 就 着 眼 于 增 加 条件 属 性 如 果 是测 量 和 观 察 的不精确 , 就着 眼 于 如何提 高 属 性 值 的精 度 比如 , 在 非 典 型 性肺 炎 的诊 断 中 , 具 有 相 同 症 状 的病 人 , 可 能最 后 的诊 断 结 果截 然 相 反 一 个是非 典病 人 , 一 个被 排 除 这 就 是 一 种 不 一 致 现 象 如 果 有 一 定 重 复 , 那 么 , 这种不 一致 现 象 的 解 决将对 临床 有 重大 意义 这 可 启 发 医 务人 员和 研 究人 员去探 究到底 缺 少 哪 些 诊 断 因素 条件 属 性 , 而 这 些 因 素 条 件属 性 决定 了非 典 型 性肺 炎 的确 诊 也 就 是 说 , 缺 少 的属 性 是 结论 的充 分 性 属性 或 者 增 加 哪 些 措 施 , 可 以使得 检 验 更 加 准确 , 以体 现 出样例 之 间 的区 别 , 而 不至 于 混淆 , 造 成 不 一 致 样 例 通 过 增 加 新 的条件 属 性 , 使 得 不 相容 的决策 问题 变 得相 容 、 一 致 , 使 获得 数 据 中隐含 的新 的 信息 、 知 识 但是 , 那 些 不 一致病 例 有可 能通过 增 加 临床 症 状 观 察 范 围 即 增 加 条 件 属 性 来 排 除 不 一致情 况 而那 些又 不 是 由于缺 少 条件属 性 引起 的不一 致现 象 , 又 怎样通 过提 高观 察精度 来消除 不 一 致现 象 呢 用 支持 向量机 判 别 不 一 致 事例 所 在 类别 的 位 里 判 断 不 一 致 样 例 距 离 某 一 类 的 中心 远 近 并 不 能说 明其 属 于 或 不属 哪 那 一类 , 而 应 该看这 个 数 据在某 一类 的 中心上 还 是 边 界上 , 因为支持 向 量 在 两类 数据 的边 界上 , 可 以通 过支持 向量 机 判 定 样例 是 否 远 离 支 持 向量 机 决 策 平 面来 决 定 样 例 是 否 在 两类 边 界 上 利用 支 持 向量 机 训 练 时 , 不 让 不一 致样例 参 加 训 练 , 因 为一 般它 们 占的 比例 很 小 , 并且 还 要 将它 们 用 来 测 试 , 以确 定 它 们 的类 别 即信 息表 中给 出不 一致 样 例 两 个 或 多个类 别 , 无从根 据现 有数 据 集 认 定它应 该属 于 哪 一类 , 因此 需要用 分 类 手 段 去 判 别 它 在 现 有 数 据 集 的条 件 下 属 于 哪 一 类 分 类 时看 这 些 样 例 处 在 哪 一 类 的什 么 位 置 , 也 就 是让 不 一 致 样例 作 为待 测 样 本 如 果 不 一致样本 通 过分 类 发现 在 某类 的边 界上 , 则样 本 因 为 不 属 于 另 一 类 , 所 以也 处 于 另一 类 的边 界 上 由条件 属 性值 或 结论 属 性值 的微 小误 差 引起 的不 一致 造 成 的矛盾 或 不 相 容 并不严 重 , 是 一 种 正 常 的测 量观 察 误差 引起 的 可 以寻 找哪 些属 性 值 有 误 差 , 通 过提 高精 确度 来排 除不 一致现 象 如 果 将 不 一 致 样 例 作 为 待 识 样 本 , 通 过 分 类 , 发 现 它 是远 离 某一类 边 界 的点 , 即远 离分 类 面 一 定 阐值 的点 则这将 引起 较大 的误 差 、 矛盾 , 肯 定 是 由于 缺 少属 性 引起 的 样 例 处在 两类边 界但 属 于 不 同的类 , 有 可 能 出现 在诸 如疾 病 的早期 诊 断等情形 中 , 由于指标 数值 都 小 , 如 低 烧 , 咳 嗦 症 状 轻 , 肺 部 阴影 少等 , 给 诊 断是 否得病 或 分成 不 同 的类造成 困难 但 找 到 导 致 不 同疾 病 的病 因对 于 人 类 重 大疾 病 的早 期 诊 断有 重 大 意 义 不 一 致 样 例 所 含信 息 类型 判别 算法 输入 一 决策表 , , , ,力 , 其 中 是 论 域 , 分 别 为 条件 和 决策 属 性 集 “ 代 , 其 中 , 是 属 性 任 的值 域 是 属 性 的集 合 厂是 信 息 函 数
VoL.26 No.5 张德政等:基于支持向量机挖据不一致事例隐含的异常信息 ·567· 输出:不一致样例是由于缺少条件属性引 试.发现,2,,山为支持向量,有可能由误差引 起,因而需添加条件属性:如是由于在边界区由 起,可以先进行误差分析.而,6,,4远离两类 误差引起,因而需提高精度, 边界,因此,不一致有可能因缺少属性引起,不用 3.5举例 进行误差分析 给定初始信息表1,其中包含,2:,44:, 对一致信息表中的20个点用SVM分类,支 6;,为四对不一致样本点.先将一致信息进行 持向量为9个,见表2、图3和图4.表中框内点以 支持向量机分类,然后再对不-一致样例进行测 及图中两条虚线之内的点为支持向量. 表1初始信息表(包含,:,4:功,4:4,四对不一致样本点) Table 1 Initial values(Four inconsistent information samples includied) U 1 3 45 6 7 910 U U U U X 0.30.60.80.9 0.80.60.80.9 0.90.8 0.40.4 0.3 0.3 0.9 0.6 0.4 0.5 0.60.90.80.70.8 0.9 0.7 0.7 0.8 0.8 D 1 1 1 1 1 1 I 1 -1 1 -1 U 11 12 13 14 151617 18 1920 UU U U X 0.20.4④0.5☐0.40.30.20.10.10.2 0.10.1 0.10.90.9 人 0.7 0.5 0.10.10.20.30.40.20.2 0.1 0.3 0.3 0.9 0.9 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 表2一致信息表样本点及其SVM子集 Table 2 Consistent information samples and its SVM subset U 2 3 4 5 6 7 8 9 10 X 0.30.6 0.8 0.90.8 0.60.8 0.9 0.9 0.8 Y 0.9 0.6 0.4 0.5 0.6 0.9 0.8 0.7 0.8 0.9 D 1 1 1 1 1 1 1 U 11 12 1314 15 1617 18 19 20 0.20.40.50.40.3 0.2 0.1 0.1 0.2 0.1 0.7 0.5 0.1 0.1 0.2 0.3 0.4 0.2 0.2 0.1 D -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1.0 0.8 0.6 l 毫04 0.2 Lo 0 0 0.2 0.4 0.6 0.8 1.0 样本区间 图320个点SVM训练结果(9个支持向量) 图420个样本点的位置 Fig.3 SVM training result of twenty samples Fig.4 Scatter of twenty samples 3.6解决不一致现象可以增加的属性 症时间或长短、发病时刻等 (1)某条件属性的原因或条件.如高烧作为诊 (2)某属性导致的结果.如某项病毒指标会导 断非典型性肺炎的一个条件属性,但它和其他条 致什么后果,如果这些后果不同,也是区分二不 件属性结合并不能确定非典的诊断,那么就增加 一致样例的原因. 条件属性的形成条件或原因作为新的条件属性, (3)那些与约简后主要属性性质较远或相反 例如高烧的起始时间、已发烧的时间、肺部阴影 的属性可能是造成二事例不一致的原因,如二学 的起症时间或肺部阴影的已发生时间、咳嗦的起 生在数理化方面成绩一样,而结论属性一个为
张德政 等 基 于 支持 向量机 挖 掘 不 一 致 事例 隐含 的异常信息 输 出 不 一 致 样 例 是 由于 缺 少 条 件 属 性 引 起 , 因而 需添 加 条件 属 性 如 是 由于 在 边 界 区 由 误 差 引起 , 因而 需提 高精 度 举 例 给 定 初 始信 息表 , 其 中包 含 ,, , , 姚 铸 , 为 四对 不 一致样本 点 先将 一 致信 息进 行 支 持 向量 机 分 类 , 然 后 再 对 不 一 致 样 例 进 行 测 试 发 现 , , , 为 支 持 向量 , 有 可 能 由误 差 引 起 , 可 以先 进 行 误 差 分 析 而 “ ,, , ,, 远 离两类 边 界 , 因此 , 不一 致 有 可 能 因缺 少 属性 引起 , 不用 进 行 误 差 分 析 对 一 致 信 息 表 中 的 个 点用 分 类 , 支 持 向量 为 个 , 见表 、 图 和 图 表 中框 内点 以 及 图 中两 条 虚 线 之 内 的点 为支 持 向量 表 初 始 信 息 表 包 含 ,, ,, 一 ,, ,, 价 四 对不 一 致样 本点 川 伊 加 ,, “ 场 , 一 ,, 岭 ,, 酥 队 认 认 区亘口 匡亘口 画国 · 一 一 认 认 匡亘 匡 〕 匡困 匡到 · · · · · · · · 一 一 一 一 一 一 一 一 一 一 一 一 表 一 致 信息 表样 本 点 及 其 子 集 洛 带 带举 卜 图 个 点 训 练 结 果 个 支持 向且 · 恤 幻泞 样 本 区 间 图 个 样本点的位 · 幻即 解 决 不 一 致 现 象 可 以增 加 的属 性 某 条件 属 性 的原 因或 条件 如 高烧 作 为诊 断非 典 型性肺 炎 的一 个 条件 属 性 , 但 它 和 其他 条 件 属性 结合 并不 能确 定 非 典 的诊 断 , 那 么 就 增 加 条件属 性 的形 成 条件 或 原 因作 为新 的条件 属 性 , 例 如 高烧 的起 始 时 间 、 己 发烧 的 时 间 、 肺 部 阴影 的起 症 时 间或肺 部 阴影 的 已 发 生 时 间 、 咳嗦 的起 症 时 间或 长 短 、 发 病 时刻 等 某 属 性 导致 的结 果 如 某 项 病 毒 指标 会 导 致 什 么 后 果 , 如 果这 些 后 果 不 同 , 也 是 区 分 二 不 一 致 样 例 的原 因 那 些 与 约 简后 主 要 属 性性质 较远 或 相 反 的属 性可 能是造 成 二 事例 不 一 致 的原 因 如 二 学 生 在 数 理 化 方 面 成 绩 一 样 , 而 结 论 属 性 一 个 为
·568 北京科技大学学报 2004年第5期 “优”,一个为“良”,可能是由于文科性质的科目 上的点的误差引起的不一致要占一定数量,对于 差距大,拉开了距离.也就是说,属性之间具有相 这种情况,用提高精度的方法排除不一致有一定 关性.不一致事例之间的区别属性一般是那些与 的合理性。 己有属性相关性小的属性.因此,计算与主要属 (3)结论属性中的相邻概念是针对结论属性 性距离大的属性,这些属性可能造成了二不一致 是由一系列递进的概念组成而言的,诸如病情的 事例的结论不一致, “减轻”和“好转”,而此时病情的“好转”和“加 (4)如样本本身固有的性质能够和某些条件 重”是不相邻概念,是对立概念.当结论属性只有 属性共同作用,则可将这些固有的性质作为可添 两个概念时,如“癌细胞”和“正常细胞”,对立概 加的条件属性.如相同的药物组合对不同的病人 念也成为相邻概念, 的效果不一样,可能与病人本身的身体条件有 (4)不相邻概念之间的样例产生不一致或不 关,如性别、年龄、身体健康状况、既往病史等等. 在一个边界上的样例产生的不一致如果有一定 (5)那些与结论属性依赖度大的属性相关度 数量重复,则肯定是由于缺少属性引起, 大的属性,因为依赖度大,说明导出结论的充分 参考文献 性大, 1 Wang G Y,Wu Y,Liu F.Generating rules and reasoning 4讨论与结论 under inconsistencies [A].IEEE International Conference on Industrial Electronics,Control and Instrumentation (1)依据误差理论,由错误引起的误差(粗差) IC1.Nagoya,2000,2536 在重复实验中最多也不超过0.3%,而在非重复实 2 Wang G Y,Liu F.The inconsistency in rough set based rule generation [A].The Second International Conference 验中这种情况的发生要远远低于这个比例,由系 on Rough Sets and Current Trends in Computing [C].Ja- 统误差、偶然误差引起的不一致也只发生在两类 pan,2000.332 边界.由于支持向量数目本身一般很小,再加上 3 Pawlak Z.Rough Sets:Theoretical Aspects of Reasoning 由于误差引起的不一致可能性很小,所以由误差 about Data [M].Amsterdam:Kluwer Academic Publish. 导致的不一致的可能性不大.因此,不一致样例 ers,1991 被分析处理的阈值可取为34. 4 Vapnik V N.The Nature of Statistical Learning Theory (2)支持向量的数目少则可占整个样本量的 [M].NY:Springer-Verlag,1995 4%~5%,.多则可能占整个样本量的40%~50%, 5 Zhang DZ,Yang B R.A new knowledge discovery meth- 因此,当支持向量数目比较大时,有可能由边界 od for saentific and techndogic [J].JUniv Sci Technol Be- jing,2002,9(13):237 Mining Uncommon Information from Inconsistent Samples Based on Support Ve- ctor Machine ZHANG Dezheng,AZIGULI,FENG Honghai,YANG Bingru Information Engineering School,University of Science and Technolgy Beijing,Beijing 100083,China ABSTRACT In current researches of knowledge discovery,inconsistent examples in a decision table are not be analyzed.It is just the place that contradictions would hide interesting and valuable information.A support vector machine based algorithm is proposed to mine kinds of information which hide in inconsistent examples,i.e.,to de- cide whether inconsistency is caused by mistake,the error between a computed or measured value and a true or the- oretically correct value,or missing attributes.Some methods and algorithms which eliminate the inconsistency are presented. KEY WORDS data mining;rough set;support vector machine;inconsistency
北 京 科 技 大 学 学 报 年 第 期 “ 优 ” , 一 个 为 “ 良 ” , 可 能 是 由于 文 科 性 质 的科 目 差距 大 , 拉 开 了距 离 也就 是说 , 属 性 之 间具有相 关性 不 一致事例 之 间 的区 别属 性一般 是那 些 与 己 有 属 性 相 关 性 小 的属 性 因 此 , 计 算 与 主 要 属 性距 离大 的属性 , 这 些 属 性 可 能造 成 了二 不 一致 事例 的结 论 不 一 致 如样本 本 身 固有 的性质 能够 和 某 些 条件 属 性共 同作用 , 则可 将 这 些 固有 的性质 作 为可添 加 的条件 属性 如 相 同的药物 组 合对 不 同 的病 人 的效 果 不 一 样 , 可 能 与 病 人 本 身 的身 体 条 件 有 关 , 如性 别 、 年龄 、 身体健康状 况 、 既往病 史等 等 那 些 与 结 论 属 性 依 赖 度 大 的属 性 相 关度 大 的属 性 因 为依 赖 度 大 , 说 明导 出 结论 的充 分 性 大 讨 论 与结 论 依据误 差 理 论 , 由错误 引起 的误 差 粗 差 在重 复 实验 中最 多也 不超 过 , 而 在 非 重 复实 验 中这种情况 的发 生要 远 远低 于这 个 比例 由系 统误 差 、 偶然 误 差 引起 的不 一致 也只 发 生在 两类 边 界 由于 支 持 向量 数 目本 身 一般 很 小 , 再 加 上 由于 误 差 引起 的不 一致 可 能性 很 小 , 所 以 由误 差 导致 的不 一致 的可 能性 不 大 因此 , 不 一 致 样 例 被 分 析 处 理 的 闽值 可 取 为 支 持 向量 的数 目少 则 可 占整 个样 本量 的 一 ‘叼 多 则 可 能 占整 个 样 本 量 的 一 , 因此 , 当支 持 向量 数 目比较 大 时 , 有 可 能 由边 界 上 的点 的误 差 引起 的不 一致要 占一 定数 量 , 对 于 这种情 况 , 用 提 高精度 的方 法排 除不一致有 一 定 的合 理 性 结论 属 性 中的相邻 概 念 是 针对 结论 属性 是 由一 系列 递进 的概念 组成 而 言 的 , 诸 如病情 的 “ 减 轻 ” 和 “ 好 转 ” , 而 此 时病 情 的 “ 好转 ” 和 “ 加 重 ” 是 不相邻 概念 , 是对 立概 念 当结论属 性只 有 两个 概 念 时 , 如 “ 癌 细 胞 ” 和 “ 正 常细 胞 ” , 对 立 概 念 也成 为相 邻概 念 不 相邻概念 之 间 的样例 产 生 不一 致 或 不 在 一 个 边 界 上 的样 例 产 生 的不 一 致 如 果 有 一 定 数 量 重 复 , 则 肯 定 是 由于缺 少 属 性 引起 参 考 文 献 从 , , 吧 , ” 【 , , , , , 吧 , , 白 , , 叮 乙鱿咬 , 乙凭式尸 四 , 尹“ 犯 , , ℃ 以 田 , , , , 知 加