在数据库中发现具有时态约束的关联规则.doc

Ξ 在数据库中发现具有时态约束的关联规则 欧阳为民1, 2 蔡庆生2 1 (安徽大学计算中心 合肥 230039) 2 (中国科学技术大学计算机科学系 合肥 230027) E 2m a il: o ywm @m a r s. ah u. edu. cn 摘要 目前, 国际上的关联规则研究尚未考虑时间因素. 然而, 时间是现实世界的固有属性, 许多现实 世界数据库都存在时态语义问题. 该文考察称为有效时间的时态约束问题, 提出了时间区间延展与归 并技术以及新的时态关联规则发现算法, 从而进一步推广了关联规则的应用. 关 键 词 知识发现, 关联规则, 时态约束. 中图法分类号 T P 311 在数据库中发现知识 (k now ledge d isco ve ry in da taba se s, 简称 KDD ) , 亦称为数据发掘 (da ta m in ing) , 是当 今国际上人工智能和数据库研究方面最富活力的新兴领域. 其目标是为了满足用户目标, 自动处理大量的原始 数据, 从中识别重要和有意义的模式, 并将其作为知识加以表达1, 2 . 由于其强???的应用潜力以及广泛可用的存 在于各种数据库中的大量数据, 因此, KDD 成为一个具有迫切现实需要的很有前途的热点研究课题1 . 关联规则是美国 IBM A lm aden R e sea rch C en te r 的 R ak e sh A g raw a l 等人于1993年首先提出的 KDD 研究中 的一个重要课题2 . 所谓关联规则是这样一个逻辑蕴涵式: X →Y , 其中 X 和 Y 是两个不同的属性集. 关联规则 的直观含义是对数据库中的所有元组, 如果 X 中的属性值为真, 那么 Y 中的属性值也为真. 例如, 计算机系30% 的学生是安徽籍, 而数据库中有2% 的学生是计算机系且是安徽籍. 这里, 30% 为关联规则的信任度, 而2% 为关 联规则的支持度. 我们所要发现的关联规则应满足用户指定的最低支持度和最低信任度约束. 关于关联规则的 发现问题, 目前已有若干高效算法3, 4 . 在实践中, 由于时间是现实世界数据库本身固有的因素, 所以在数据中常常会发现时态语义问题. 时态数据 的出现使我们有必要在知识发现过程中考虑时间因素. 在现实世界数据库中可以发现各种各样的时态数据, 例 如, 超市的交易记录有时间标记、病员的病历数据记录、天气数据日志文件等等. 我们这里考察的时态语义是所 谓的时态约束问题, 即如果数据库中的每个元组均有其有效时间, 那么在数据库中所发现的知识也必然有相应 的时态约束, 以表明所发现的知识何时是有效的. 目前, 规则事实上都是假定永远有效的. 在这种情况下, 没有任 何东西表明规则何时变得有效, 何时又被认为无效. 同样, 目前无效的规则也没有说明它在过去或将来是否有 效. 在现实中, 附加上某种时态约束的规则将可以更好地描述客观现实情况, 因而也会更有价值. 在现实生活中 往往存在或希望带有时态约束的规则, 我们称这种关联规则为时态关联规则. 本文第1节给出问题描述. 第2节简要描述关联规则发现算法的主要思想. 第3节提出发现时态关联规则的有 关技术, 并给出相应的算法描述. 第4节是实验结果. 最后是结论与进一步研究方向. 1 问题描述 为了讨论的方便, 我们采用关系型数据模型. 不过, 只需对我们在本文所提出的方法稍加修改即可应用于其 Ξ 本文研究得到国家自然科学基金和安徽省教委科研基金资助. 作者欧阳为民, 1964年生, 博士, 副教授, 主要研究领域为 KDD , 机器学习, 人工智能及其应用. 蔡庆生, 1938年生, 教授, 博士生导师, 主要研究领域为机器学习, 知识发现, 人工智能. 本文通讯联系人: 欧阳为民, 合肥 230039, 安徽大学计算中心 本文1997211220收到原稿, 1998205228收到修改稿  他数据模型, 如扩展的关系模型、面向对象的数据模型. 令 R = { I 1 , I 2 , . . . , Im } 是一值域为{0, 1}的属性集 ( 也称 为项目集). 与知识发现任务相关的数据集 r= { t1 , t2 , . . . , tn }是定义在关系模式{ I 1 , I 2 , . . . , Im }上的一个关系, 即 元素个数为m 的二元向量的集合. 我们称某元组 t 支持 ( suppo r t) 某属性A , 如果元组 t 直接包含属性A , 或者属性A 是元组 t 的某个属性值的 先辈, 记为 t [A = 1. 令 X Α R 是属性子集, t∈r 是关系的某一行或