InClosPan：大型数据库中闭序列模式的增量挖掘.pdfVIP

第32卷第1期 南昌大学学报(理科版) V_01．32Ⅳ0．1 2008年2月 Journal of Nanchang University(Natural Science) Feb．2008 文章编号：1006一O464(2008)O1～0096～04 InClosPan：大型数据库中闭序列模式的增量挖掘 白似雪，朱 天 (南昌大学计算机科学与技术系，江西南昌 330031) 摘 要：许多现实数据库都以增量形式增长，不希望在每次更新了数据库之后，又重新挖掘完整数据库，增量算法 成为必需。研究了当初始数据库中增加了新的事务或增加了新的顾客时，增量挖掘闭序列模式的问题。给出了一 个新的频繁闭序列模式增量挖掘算法InClosPan，该算法利用已得到的结果进行增量挖掘，减少了重新挖掘数据库 的费用。 关键词：闭序列模式；增量挖掘；数据挖掘 中图分类号：TP301．6 文献标识码：A 挖掘闭序列模式是数据挖掘中一项很重要的任 定义1l2 J 一个序列．s是指项集的有序表，记 务，有着广泛的应用，如分析顾客的购物习惯，web 为S= s1，s2，…，s )，其中s (i=1，2，…，m)是一 页面的访问顺序，DNA序列分析等等。如今已有许 个项集，且s Io一个序列的长度是指它所包含的 多序列模式及闭序列模式的挖掘算法，它们可以很 项集的长度之和，即f=∑ I s I，记为I．s I。具有 有效地挖掘频繁序列¨ J。这些算法都有一个特 I 三m k长度的序列称为k一序列。 点：它们是一次完成的，挖掘完整的数据库，得到完 定义2 设有两个序列S。=(a ，a ，…，a ) 全的结果。然而许多现实数据库都以增量的形式增 和S =(b ，b ，…，bm)，这里n≤m，当且仅当 (1 长，记录按时间顺序不断更新。例如，顾客的购物事 ≤i】i2… i ≤m)^(a1 b¨a2 bi，，…， 物数据库每日都会有新的购买记录，天气序列以及 医疗序列也会随着时间日益增长。如果每次要重新 a b。 )为真时，称序列．s。包含于序列．s 中，记为 挖掘完整的数据库，效率将非常低，所以我们必须提 ．s。 ．s 。相应地，我们称．s 为．s 的子序列，．s 为．s 出新的增量算法来解决这个问题。一些有效的有关 的超序列。 关联规则的增量算法已经提出了，但是序列模式的 定义3 ] 一个序列．s。在序列数据库．s中的支 问题比关联规则更加复杂，因为必须考虑事务缩减 持度是指．s中包含．s。的元组的数目，记为Sup(S。)。 (transaction cutting)，和序歹0{j}歹0(sequence permuta- 给定一个最小支持度阈值min—sup。若序列s的支持 tion)。目前已有一些有关序列模式的增量挖掘算 度不小于min—sup，则称s为频繁序列，所有频繁序 法『6 ]，但还没有看到有关频繁闭序列模式的增量 列的集合称为FS。 挖掘算法。 定义4[2 对序列s∈FS，若] s (s ∈FS^ 在众多序列模式的形式中，闭序列模式是最重 s ]s^Sup(s)=Sup(s ))为真，则称s为频繁闭 要的一个。闭序列模式包含了完整序列模式的所有 序列，所有频繁闭序列的