论文部分内容阅读
[摘要] 針对序列模式挖掘中出现大量用户不感兴趣的短模式的问题，提出了一种基于长度递减约束的权值序列模式挖掘算法，该算法利用长度递减约束中的最小有效扩展性质，可以对序列进行有效的剪枝，不仅可以获得具有潜在价值的长模式，也可以去除许多无用的短模式。
[关键词] 序列模式 权值约束 长度递减约束
0、引言
序列模式挖掘是数据挖掘中最具挑战性的课题之一，它在交易数据分析、web日志挖掘和DNA序列模式等领域内具有广泛的应用前景。近年来，国外的一些专家学者对序列模式挖掘方面提出了许多解决办法。这些算法减少了挖掘时间和扫描数据库的次数，提高了挖掘的效率。但是这些算法也存在一些局限，因为在现实生活中某些领域中的有些序列虽然是频繁的，但对用户的意义确很小。因此，对不同序列模式赋予不同权值的加权序列模式挖掘算法就被提了出来，从而可以发现更多用户感兴趣的模式，减少了无用模式的产生。
通常，数据库中包含较少项的短序列模式往往具有较高的支持度，但是在很多情况下，一些长序列模式往往也是对用户感兴趣的模式尽管它的支持度相对较低。理想情况下希望发现一个以长度递减函数作为支持度约束的频繁模式挖掘算法，从而避免大量用户不感兴趣的短模式的产生。
因此本文提出了一种基于长度递减约束的权值序列模式挖掘算法WSLPM，该算法利用长度递减约束中的最小有效扩展性质，可以对序列进行有效的剪枝，不仅可以获得具有潜在价值的长模式，也可以去除许多无用的短模式。
1、基本概念
为了挖掘基于长度递减约束加权序列模式，需要权值、权值支持度、长度递减约束、长度递减约束的加权模式等做如下定义。
项的权值代表每一项的价值，序列S表示为，其中sj是项集，表示为，则序列S的权值定义为Weight(S)，其值为序列中各项权值之和与序列长度的比值。
给定一个数据库如表1-1，项的权值如表1-2所示，购物篮中商品项的价格可作为权值因子属性值，对于表1-1中的序列2，它的权值可表示为Weight(S2)=(1+0.8+1.3+0.7)/4=0.95。
表1-1 序列数据库
序列号 序列
1 a(bc)def
2 a(bc)d
3 b(de)f
4 bc(de)
5 f(cd)e
6 a(bc)dfe
表1-2 项标准权值的例子
项 a b c d e f
支持数 3 5 5 6 4 3
权值 1 0.8 1.3 0.7 0.8 1.2
作为数据库中序列项的权值因子，项的权值可以被标准化在一个范围内MinWWeightMaxW，MinW为项的最小权值，MaxW为项的最大权值，项的最大权值用来对非频繁模式进行剪枝，项的最小权值用来平衡支持度和权值。序列S的加权支持度定义为序列的支持度与权值的乘积，权值支持度WSupport=(Weight(S)*support(S))。
给定数据库D和一个满足条件1≥f(l)≥f(l+1)≥0的长度递减约束函数f(l)，模式S是频繁的当且仅当σD(S)f(|S|)，称模式S满足长度递减约束。
给定一个长度递减约束函数f(l)，其反函数f-1(σ)＝min({l|f(l)σ})，其中f-1(σ)是模式满足约束的最小长度。
给定一个长度递减约束函数f(l)，对于项a的投影数据库D’中的序列模式p，则序列sD’将被剪枝如果满足条件f(|s|+|p|)>σD(p)。
定义：序列模式是一个满足长度递减约束的加权序列模式(WSPL)，则其加权支持度不小于长度递减支持度约束并且其权值不小于规定的最小权值。
2、WSLM算法的设计
WSpan算法可以有效的发现用户感兴趣的模式，减少了无用模式的产生，但是此算法也存在局限性，往往不能发现用户感兴趣的长模式。因此需要设计一种算法，使得这些用户感兴趣的但支持度相对较低的长模式能被用户发现。在这方面研究已经取得了一些进展，即通过长度递减约束来实现，越长的模式被赋予越小的支持度阈值，保证了长模式的发现。
2.1算法思想
基于以上原因，本文提出了一种基于长度递减约束的加权序列模式挖掘算法（WSLM），此算法包括两个剪枝步，一个是通过长度递减函数来剪枝，另一个是通过加权约束来剪枝，其中第一个剪枝步要用到一个权值最小有效扩展性质。
2.2 算法描述
根据上面的分析，长度递减约束的加权序列模式挖掘算法(WSLM)描述如下。
算法：WSLM(DB, min_weight, WSPL)。
输入：原始数据库DB，最小权值min_weight；
输出：满足长度递减约束的加权序列模式WSPL。
Begin
(1) Let WSPL be the set of the weighted frequent sequential patterns with length-decreasing constraint, initialize WSPL is null;
(2) Scan DB once, count the weighted support of each item, and find each weighted frequent item, i, if the following pruning condition is satisfied
Condition 1: weightmin_weight
(3)For each weighted frequent item i in DB
Call FWSP(WSPL, s, f(x), Di);
End
算法：FWSP(WSPL, s, f(x), Di)。
输入：序列模式s，长度递减函数f(x)和最小权值min_weight；
输出：满足长度递减约束的加权序列模式WSPL。
Begin
(1) Scan Ds once, count the weighted support of each item, find each weighted frequent item i, if the following pruning conditions are satisfied
Condition 1: weighted supportf(x)
Condition 2: weightmin_weight
(2)For each weighted frequent item i, add it to sequence s to form a sequential pattern s’;
(3)For each s’, construct weighted projected database Ds’ with respect to s’
Call FWSP(WSPL, s, f(x), Di);
(4)For each weighted infrequent item i, add it to the sequence s to form a sequential pattern s’’
(5)Scan Ds’’, get all the itemset of the Ds’’, for each sequence p in the Ds’’;
(6) if f(|s’’|+|p|)>weighted support(s’’), then
(7) sequence p can be pruned;
(8) else Call FWSP(WSPL, s, f(x), Di)
(9) return;
End
3、实验
为了验证本文提出的算法的有效性以及在性能上的优越性，采用WSpan算法使用的数据集，其实验数据集是由IBM Almaden网站上提供的标准数据集合成器生成的。表3-3列出了该数据集合成器中的主要参数以及所表示的含义。
表3-3 主要参数及其含义
参数 参数含义
|N| 不同项的数目
|D| 数据序列的数目
|C| 平均每条数据序列中包含的项集数目
|T| 平均每个项集中包含的数据项的数目
|S| 最大序列模式的平均長度
|I| 最大频繁项集的平均长度
为了对本文提出的WSLM算法的性能进行测试，在P4 3.2GHz/256M/Windows XP操作系统环境下，用C++编程语言实现WSLM算法和WSpan算法的比较，实验数据是采用IBM数据生成工具生成的，采用D10C9T2.5N9S5.5I1.5D的数据集对两种算法进行比较，权值范围从0.8到1.3，在最小支持度取不同值时对WSLM算法和WSpan算法的运行时间进行比较，并且验证WSLM算法生成序列的数量和内存占用情况。
图3-2两种算法的运行时间
从图3-2可见，随着数据量的增大，即当挖掘长序列模式时WSLM算法在运行时间上优于WSpan算法。因为通过WSVE性质，许多用户不感兴趣的短模式被提前剪枝了，而对用户有用的长模式被挖掘出来，从而减少了运行时间。
图3-3算法的运行时间
从图3-3可见，在不同的权值范围下，算法的稳定性还是很高的。另外，权值范围值越小，则算法的运行时间越少。
4、结束语
本文提出了一个基于长度递减约束的加权序列模式挖掘的WSLM算法，通过两个有效的剪枝方法和WSVE性质，非频繁的和用户不感兴趣的短模式被提前剪枝，提高了算法的效率，并且解决了长模式因支持度较低不能被发现的问题，从而挖掘出的都是用户感兴趣的长模式。实验表明该算法对满足用户的需求都是十分有效的。
参考文献：
[1] R.Srikant, R.Agrawal. Mining sequential patterns: Generalizations and performance improvements[C]. EDBT 1996, Avignon, France,1996.pp.3-17.
[2]H.Cheng, X.Yan, J.Han. IncSpan: Incremental Mining of Sequential Patterns in Large Database[J]. In Proc. of the 10th Int. Conf. on Knowledge Discovery and Data Mining, Seattle, WA, USA, 2004.527-532.
[3]C.Yu, Y.Chen. Mining Sequential Patterns from Multidimensional Sequence Data[J]. IEEE Transaction on Knowledge and Data Engineering, 2005,17(1):136-140.
“本文中所涉及到的图表、公式、注解等请以PDF格式阅读”
[关键词] 序列模式 权值约束 长度递减约束
0、引言
序列模式挖掘是数据挖掘中最具挑战性的课题之一，它在交易数据分析、web日志挖掘和DNA序列模式等领域内具有广泛的应用前景。近年来，国外的一些专家学者对序列模式挖掘方面提出了许多解决办法。这些算法减少了挖掘时间和扫描数据库的次数，提高了挖掘的效率。但是这些算法也存在一些局限，因为在现实生活中某些领域中的有些序列虽然是频繁的，但对用户的意义确很小。因此，对不同序列模式赋予不同权值的加权序列模式挖掘算法就被提了出来，从而可以发现更多用户感兴趣的模式，减少了无用模式的产生。
通常，数据库中包含较少项的短序列模式往往具有较高的支持度，但是在很多情况下，一些长序列模式往往也是对用户感兴趣的模式尽管它的支持度相对较低。理想情况下希望发现一个以长度递减函数作为支持度约束的频繁模式挖掘算法，从而避免大量用户不感兴趣的短模式的产生。
因此本文提出了一种基于长度递减约束的权值序列模式挖掘算法WSLPM，该算法利用长度递减约束中的最小有效扩展性质，可以对序列进行有效的剪枝，不仅可以获得具有潜在价值的长模式，也可以去除许多无用的短模式。
1、基本概念
为了挖掘基于长度递减约束加权序列模式，需要权值、权值支持度、长度递减约束、长度递减约束的加权模式等做如下定义。
项的权值代表每一项的价值，序列S表示为
给定一个数据库如表1-1，项的权值如表1-2所示，购物篮中商品项的价格可作为权值因子属性值，对于表1-1中的序列2，它的权值可表示为Weight(S2)=(1+0.8+1.3+0.7)/4=0.95。
表1-1 序列数据库
序列号 序列
1 a(bc)def
2 a(bc)d
3 b(de)f
4 bc(de)
5 f(cd)e
6 a(bc)dfe
表1-2 项标准权值的例子
项 a b c d e f
支持数 3 5 5 6 4 3
权值 1 0.8 1.3 0.7 0.8 1.2
作为数据库中序列项的权值因子，项的权值可以被标准化在一个范围内MinWWeightMaxW，MinW为项的最小权值，MaxW为项的最大权值，项的最大权值用来对非频繁模式进行剪枝，项的最小权值用来平衡支持度和权值。序列S的加权支持度定义为序列的支持度与权值的乘积，权值支持度WSupport=(Weight(S)*support(S))。
给定数据库D和一个满足条件1≥f(l)≥f(l+1)≥0的长度递减约束函数f(l)，模式S是频繁的当且仅当σD(S)f(|S|)，称模式S满足长度递减约束。
给定一个长度递减约束函数f(l)，其反函数f-1(σ)＝min({l|f(l)σ})，其中f-1(σ)是模式满足约束的最小长度。
给定一个长度递减约束函数f(l)，对于项a的投影数据库D’中的序列模式p，则序列sD’将被剪枝如果满足条件f(|s|+|p|)>σD(p)。
定义：序列模式是一个满足长度递减约束的加权序列模式(WSPL)，则其加权支持度不小于长度递减支持度约束并且其权值不小于规定的最小权值。
2、WSLM算法的设计
WSpan算法可以有效的发现用户感兴趣的模式，减少了无用模式的产生，但是此算法也存在局限性，往往不能发现用户感兴趣的长模式。因此需要设计一种算法，使得这些用户感兴趣的但支持度相对较低的长模式能被用户发现。在这方面研究已经取得了一些进展，即通过长度递减约束来实现，越长的模式被赋予越小的支持度阈值，保证了长模式的发现。
2.1算法思想
基于以上原因，本文提出了一种基于长度递减约束的加权序列模式挖掘算法（WSLM），此算法包括两个剪枝步，一个是通过长度递减函数来剪枝，另一个是通过加权约束来剪枝，其中第一个剪枝步要用到一个权值最小有效扩展性质。
2.2 算法描述
根据上面的分析，长度递减约束的加权序列模式挖掘算法(WSLM)描述如下。
算法：WSLM(DB, min_weight, WSPL)。
输入：原始数据库DB，最小权值min_weight；
输出：满足长度递减约束的加权序列模式WSPL。
Begin
(1) Let WSPL be the set of the weighted frequent sequential patterns with length-decreasing constraint, initialize WSPL is null;
(2) Scan DB once, count the weighted support of each item, and find each weighted frequent item, i, if the following pruning condition is satisfied
Condition 1: weightmin_weight
(3)For each weighted frequent item i in DB
Call FWSP(WSPL, s, f(x), Di);
End
算法：FWSP(WSPL, s, f(x), Di)。
输入：序列模式s，长度递减函数f(x)和最小权值min_weight；
输出：满足长度递减约束的加权序列模式WSPL。
Begin
(1) Scan Ds once, count the weighted support of each item, find each weighted frequent item i, if the following pruning conditions are satisfied
Condition 1: weighted supportf(x)
Condition 2: weightmin_weight
(2)For each weighted frequent item i, add it to sequence s to form a sequential pattern s’;
(3)For each s’, construct weighted projected database Ds’ with respect to s’
Call FWSP(WSPL, s, f(x), Di);
(4)For each weighted infrequent item i, add it to the sequence s to form a sequential pattern s’’
(5)Scan Ds’’, get all the itemset of the Ds’’, for each sequence p in the Ds’’;
(6) if f(|s’’|+|p|)>weighted support(s’’), then
(7) sequence p can be pruned;
(8) else Call FWSP(WSPL, s, f(x), Di)
(9) return;
End
3、实验
为了验证本文提出的算法的有效性以及在性能上的优越性，采用WSpan算法使用的数据集，其实验数据集是由IBM Almaden网站上提供的标准数据集合成器生成的。表3-3列出了该数据集合成器中的主要参数以及所表示的含义。
表3-3 主要参数及其含义
参数 参数含义
|N| 不同项的数目
|D| 数据序列的数目
|C| 平均每条数据序列中包含的项集数目
|T| 平均每个项集中包含的数据项的数目
|S| 最大序列模式的平均長度
|I| 最大频繁项集的平均长度
为了对本文提出的WSLM算法的性能进行测试，在P4 3.2GHz/256M/Windows XP操作系统环境下，用C++编程语言实现WSLM算法和WSpan算法的比较，实验数据是采用IBM数据生成工具生成的，采用D10C9T2.5N9S5.5I1.5D的数据集对两种算法进行比较，权值范围从0.8到1.3，在最小支持度取不同值时对WSLM算法和WSpan算法的运行时间进行比较，并且验证WSLM算法生成序列的数量和内存占用情况。
图3-2两种算法的运行时间
从图3-2可见，随着数据量的增大，即当挖掘长序列模式时WSLM算法在运行时间上优于WSpan算法。因为通过WSVE性质，许多用户不感兴趣的短模式被提前剪枝了，而对用户有用的长模式被挖掘出来，从而减少了运行时间。
图3-3算法的运行时间
从图3-3可见，在不同的权值范围下，算法的稳定性还是很高的。另外，权值范围值越小，则算法的运行时间越少。
4、结束语
本文提出了一个基于长度递减约束的加权序列模式挖掘的WSLM算法，通过两个有效的剪枝方法和WSVE性质，非频繁的和用户不感兴趣的短模式被提前剪枝，提高了算法的效率，并且解决了长模式因支持度较低不能被发现的问题，从而挖掘出的都是用户感兴趣的长模式。实验表明该算法对满足用户的需求都是十分有效的。
参考文献：
[1] R.Srikant, R.Agrawal. Mining sequential patterns: Generalizations and performance improvements[C]. EDBT 1996, Avignon, France,1996.pp.3-17.
[2]H.Cheng, X.Yan, J.Han. IncSpan: Incremental Mining of Sequential Patterns in Large Database[J]. In Proc. of the 10th Int. Conf. on Knowledge Discovery and Data Mining, Seattle, WA, USA, 2004.527-532.
[3]C.Yu, Y.Chen. Mining Sequential Patterns from Multidimensional Sequence Data[J]. IEEE Transaction on Knowledge and Data Engineering, 2005,17(1):136-140.
“本文中所涉及到的图表、公式、注解等请以PDF格式阅读”