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

在数据库中发现具有时态约束的关联规则欧阳为民1, 2 蔡庆生21 (安徽大学计算中心 合肥 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 是属性子集, tr 是关系的某一行或元组. 如果对每个属性A X 均有 t A = 1,那么我们称 t 支持 X , 记 t X = 1. 与属性集 X 匹配的元组集记为 sup p or t (X ) = tr| t X = 1. 关系 r 中的广 义关联规则形如 X Y , 其中 X R , Y R X . 设最低信任阈值 (m in im um co nf idence th re sho d) 和最低支持阈值(m in im um suppo r t th re sho d) 分别为 和 , 如果有| sup p or t (X Y ) | n 且| sup p or t (X Y ) | | sup p or t (X ) | , 我们称关系 r 关于最低信任阈值 和最低支持阈值 满足关联规则X Y. 这就是说, 关系 r 中至少有 n 行元 组对 X 和 Y 中的所有属性均为1, 且在对属性集 X 为1的元组中有比例为 的元组对属性集 Y 也为1. 对任意给 定的属性集 X , 如果| sup p or t (X ) | n, 其中 n 为数据库中的元组数, 为最低支持阈值, 那么我们称 X 是频繁 的. 也就是说数据库中至少有比例为 的元组对属性集 X 为1.由于时间是现实世界的固有属性, 许多信息系统都存在时态语义问题. 本文所考虑的时态语义是所谓的有效时间 (va lid t im e) , 即在某段时间内, 某元组是有效的或合法的. 这样, 我们在具有有效时间的元组集中发现的 关联规则也必然同样具有相应的有效时间, 关联规则因而就有了时效性. 为此, 我们在对上述问题进行描述的基 础上增加了有效时间约束一项, 即在关系模式中增加一个有效时间 v a l id - t im e 属性, 规定每个元组均必须附加 有效时间 v a l id - t im e 属性. 于是, 当判断某元组是否支持某属性 A 时, 由于属性 A 是附加有效时间约束的, 所 以, 我们必须首先判断该元组的有效时间是否与属性A 的有效时间匹配. 只有两者的有效时间是匹配的, 才可以进一步考虑是否支持的问题. 也就是说, 我们将判断某元组是否支持某属性A的问题分为两个子问题: ( 1) 元组的有效时间与属性A 的有效时间是否匹配; (2) 未附加有效时间的普通元组是否支持属性A . 对于第2个子问题, 我们可以采用任何一种关联规则发现算法, 如 R. A g raw a l 提出的 A p r io r i 算法中的方法. 第1个子问题则是 本文要解决的问题.关联规则发现算法 A pr ior i 简介关联规则的发现可分为如下两个子问题3 :(1) 寻找所有支持度不低于用户指定的最低支持的属性组合. 我们称这种属性组合为频繁属性序列集;(2) 利用频繁属性序列集生成所期望的规则. 基本方法是这样的, 比如说A B CD 是频繁属性序列, 如果 sup2 p or t (A B CD ) sup p or t (A B ) 不低于用户指定的最低信任度 , 那么规则A B CD 成立. 注意, 由于A B CD 是频繁 属性序列, 上述规则必定具有用户指定的最低支持.现在, 我们简要描述 R. A g raw a l 提出的寻找所有频繁属性序列集的A p r io r i 算法. 我们以该算法作为发现 具有时态约束的关联规则的基础. 令 K 2属性序列为具有 K 个属性的集合, F re K 为频繁 K 2属性序列的集合, 而 C K 为候选 K 2属性序列 (即可能的频繁属性序列) 的集合. A p r io r i 算法需对数据库作多次遍历, 每次遍历均 由两个阶段构成. 第1, 利用上次 ( 第 K - 1次) 遍历所得到的频繁 (K - 1) 2属性序列集 F re K - 1 生成候选 K 2属2性序列集 C K .候选生成算法A p r io r i- gen 3保证 C K 是所有频繁 K 2属性序列集的超集. 第2, 对数据库作一次遍历, 对其中的每个元组确定它支持 C K 中的哪些候选, 并在相应候选的 co un t 域中累计支持数. 遍历结束后, 检查候选集 C K , 确定哪些候选是频繁的, 从而构成频繁 K 2属性序列集 F re K .F re K 为空时为止.该算法反复进行, 直到已知频繁 (K - 1) 2属性序列集 F re K - 1 , 候选生成算法A p r io r i- gen 返回所有频繁 K 2属性序列集的超集. 该候选生成的算法思想是基于这样一个观察: 频繁属性序列的任何一个子集均是频繁的. 该候选生成算法也 分为如下两步:(1) 链接 ( jo in ) , 即 F re L , K - 1 与自己链接生成 C L , K .In se r t in to C L , K Se lec t p. item 1 , p. item 2 , . . . , p. item k - 1 , q. item k - 1F rom p F re L , K - 1 , qF re L , K - 1W h e re p. item 1 = q. item 1 , p. item 2 = q. item 2 , . . . , p. item k - 2 = q. item k - 2 , p. item k - 1 q. item k - 1 ,(2) 修剪 (p rune) , 删除 C L , K 中的任何一个候选 c, 如果 c 中存在一个长度 K - 1属性子集不属于 F re K- 1 , 即不是频繁的.上述候选生成算法的正确性请参阅文献2 .3带时态约束的关联规则发现算法我们在现有的关联规则发现算法A p r io r i 的基础上进行扩展, 以处理数据的时态约束问题, 从而提出时态关联规则的发现算法. 在本文的扩展的数据库中, 与普通数据库相比, 这里的元组均多了一个属性值为时间区间的 有效时间属性, 以体现时态约束. 与A p r io r i 算法相比, 我们的算法所用的候选生成方法与 A p r io r i- gen 大体相同, 不同之处在于, 当遍历数据库以进行候选计数时, 两个项目序列要匹配, 两者的相关有效时间也需可归并. 我们的方法是首先按照一定比例 (由用户根据特定的应用领域确定该比例) 延展时间区间, 然后再按照不同情况对 时间区间进行归并, 累计支持数. 注意, 此时候选的数据结构中除了项目序列域 item se t 和计数器域 sup p or t 外, 还要增加一个有效时间域 v a l id - t im e, 以表示其有效的时间区间.3. 1 时间区间的延展时间区间的延展是指将其两个端点向外扩张, 以期使两个时间区间能够相遇或交叠, 然后再归并为同一个 时间区间. 其问题在于如何延展时间区间. 一种方法是将所有时间区间的两个端点均向外延伸固定的长度, 另一 种方法是按一定比例延展时间区间. 当采用前一方法时, 我们无法考虑时间区间本身的长度, 每个时间区间一律 延伸了固定的长度. 其结果是, 有的区间可能扩展了20 , 而有的区间却可能扩展了100 . 于是, 与原来较大的 时间区间相比, 原来较小的时间区间的细节信息损失较大. 这不甚合理. 因此, 我们采用后者按一定比例延展时 间区间的方法, 以使细节信息损失对不同大小的时间区间是均衡的. 在时间区间的延展过程中, 细节信息的损失 是不可避免的, 这与在利用概念层次关系进行推广时细节信息也有损失是一致的.时间区间的两端点向外延伸的程度由表示时间区间延展程度的推广因子 f 确定. 该推广因子 f的值既可以由算法自动设置, 也可在调用本算法时指定. 然而, 不管怎样, 推广因子 f的值应根据特定应用领域凭经验选取.f 的值越大, 时间区间的延展就越快, 结果规则中细节信息的损失就越多; 反之, f越小, 时间区间的延展就越慢,结果规则中细节信息的损失就越少, 并且由于因此而需要更多的独立的延展, 算法效率就降低了. 如果时间区间在时间轴上的分布是稀疏的, 那么在归并时间区间之前要对其作较大的延展. 如果时间区间在时间轴上的分布 是稠密的, 那么即使对时间区间作不算大的延展, 也很可能引起细节信息的迅速损失. 这些问题在确定推广因子f 的值时应认真加以考虑. 事实上, 由于事先并不知道推广因子 f 的值多少才是合适的, 因此, 我们一般采取试 探性的办法. 这样, 推广因子 f 的值若设定得不合适也就在所难免. 为了发现用户真正感兴趣的模式, 必然要不 断地调整推广因子 f 的值.3. 2 时间区间的归并给定一项目序列集合, 该集合中的所有项目序列的项目集均相同, 但各自的有效时间区间未必相同, 我们的 目标是将可以归并的时间区间分别合并起来, 并累计归并后在同一时间区间内彼此匹配的项目序列的个数. 两 个时间区间的归并可按如下4种基本情况分别进行:(1) 区间 a 与区间 b 相同, 这两个区间自然地可并为一个区间 a , 且其两个端点不变;(2) 区间 a ( i, j ) 与区间 b (m , n ) 相遇, 即 j = m , 这两个区间可由一个新区间 c ( i, n ) 替换;(3) 区间 a ( i, j ) 与区间 b (m , n ) 交叠, 即i m , j m 且 j 1 do x = f irs t- e lem en t (S e t (c) ) ; S e t (c) = S e t (c) -w h ile |S e t (c) | 1 do x ;y = nex t- e lem en t (S e t (c) ) ; S e t (c) = S e t (c) - y ;if y can be m e rged w ith x 3 by th e m e tho d s de sc r ibed in 3. 2 3 th en x. v a l id - t im e= m e rg e (x. v a l id - t im e, y. v a l id - t im e) ;x. sup p or t+ + ; e lse R es t (c) = R es t (c) y ;if x. sup p or tm insup th en L k = L k x ;S e t (c) = S e t (c) ;(24) D iscov e red - R u le- se t= K g e t- ru les (L k , m inconf ) ;E nd.4性能测试为了测试上节所述算法的性能, 我们在 PC 586166 ( 32M 内存) 上用V isua l Fo xP ro 1. 0实现了该算法. 合成数据的生成方法与 IBM A lm aden 研究中心 R ak e sh A g raw a l 教授领导的 KDD 研究小组所采用的方法类似 ( 参 见 h t tp: www. a lm aden. ibm. com c sque stsynda ta. h tm l# A sso cSynD a ta) , 只是增加了一个有效时间属性. 合 成事务数据库的生成参数如下: (1) 事务个数D 为200; (2) 事务所含项目集的平均大小 T 为5; ( 3) 最大频繁项 目序列的平均大小 I 为3; (4) 事务数据库中所含项目的个数N 为20; ( 5) 最低支持m insup 为10%. 为测试算法 的扩放性, 我们逐次递增事务个数, 从500起, 每次递增500, 分6次, 递增到3500, 相应的性能曲线如图1所示. 实验 结果表明, 该算法设计正确, 并具有良好的可扩放性.图1 扩放性能曲线5结论与进一步的工作时间是现实世界的固有属性, 许多现实数据库都存在时态语义问题. 本文考虑的时态语义是所谓的有效时间 (va lid t im e) , 即某元组在某时间区间内是有效的. 这样, 我们在具有有效时间的数据集中发现的关联规则也必 然同样具有相应的有效时间, 关联规则因而也就有了时效性. 为此, 我们在 R ak e sh A g raw a l 提出的A p r io r i 算法 的基础上, 结合我们提出的时间区间延展与归并技术, 得到新的能够处理具有时态约束的关联规则发现算法.本文所考虑的时态语义单一, 仅考虑了时间区间的时态约束问题, 下一步将研究其他类型 ( 如周期性变化)的时态约束问题.致 谢本文工作得到了国际 KDD 研究知名学者加拿大 S im o n F ra ste r 大学 H an J iaw e i 教授和美国 IBMA lm aden R e sea rch C en te r 的 R ak e sh A g raw a l 教授的支持, 他们为笔者提供了有关的研究资料, 特此表示感谢.参考文献1P ia te t sk y2Sh ap iro G. D isco ve ry, ana ly sis, and p re sen ta t io n o f st ro ng ru le s. In: P ia te t sk y2Sh ap iro G, F raw lay W J ed s. Know ledge D isco ve ry in D a taba se s. C am b r idge, M A : A A A IM IT P re ss, 1991. 229 238A g raw a l R , Im ie lin sk i T , Sw am i A. M in ing a sso c ia t io n ru le s be tw een se t s o f item s in la rge da taba se s. In: P ro ceed ing s o f2th e 1993 A CM - S IGM OD In te rna t io na l Co nfe rence o n M anagem en t o f D a ta. W a sh ing to n, D C , 1993.207 2163A g raw a l R , S r ik an t R. F a st a lgo r ithm fo r m in ing a sso c ia t io n ru le s. In: P ro ceed ing s o f th e 1994 In te rna t io na l Co nfe rence o n V e ry L a rge D a ta B a se s. San t iago , C h ile, 1994. 487 499M ann ila H , T o ivo nen H , V e rk am o A Ink e r i. E ff ic ien t a lgo r ithm s fo r d isco ve r ing a sso c ia t io n ru le s. In: P ro ceed ing s o fA A A I W o rk Shop Know ledge D isco ve ry in D a taba se s. 1994. 181 1924D iscovery of A ssoc ia t ion Rule s w ith Tem pora l Con stra in t in D a ta ba se sOU 2YA N G W e i2m in 1, 2 CA I Q ing2sh eng21 (