带兴趣度的序列概念格的最大模式挖掘(图文)

1、带兴趣度的序列概念格的最大模式挖掘(图文)论文导读：1.引言序列模式挖掘【1】是数据挖掘领域中重要的研究分支而频繁工程集求解是序列模式挖掘的根底和前提。传统的序列模式挖掘算法如AprioriAll算法【2】、GSP算法【3】、SPADE算法【4】、PrifixSpan算法等在挖掘序列模式时采取了一个多遍扫描候选子序列产生和测试的方法。由于概念格的完备性使其可以在不丧失有效信息的情况下。关键词：数据挖掘，序列模式，概念格1.引言序列模式挖掘【1】是数据挖掘领域中重要的研究分支而频繁工程集求解是序列模式挖掘的根底和前提。传统的序列模式挖掘算法如AprioriAll算法【2】、GSP算法【3】、SP

2、ADE算法【4】、PrifixSpan算法等在挖掘序列模式时采取了一个多遍扫描候选子序列产生和测试的方法，有可能产生大量冗余候选序列，并需要屡次扫描数据库，因而时间开销较大。由于概念格的完备性使其可以在不丧失有效信息的情况下，基于概念格的频繁工程集表示和求解，能有效地压缩频繁工程集的表示规模，这也为挖掘序列模式提供了有利条件，缩小了搜索空间，为序列模式的挖掘效率的提高提供了良好的根底。论文检测。因此，作为序列模式挖掘的数学模型，将大规模数据库中工程集映射到概念格中的概念内涵,那么相应地减小工程集的表示规模，因而有利于提高序列模式挖掘效率的。聂成林【7】首先提出了利用概念格进行序列模式挖掘，从空

3、间上提高了挖掘效率。李云提出带兴趣度的序列概念格模型及其构造算法把概念格的每个结点本质上是一个最大工程集，非常有利于序列模式发现。通过扫描格节点就能能生成商家期望的感兴趣序列，本文在带兴趣度的序列概念格模型上进行最大序列模式挖掘。2.序列概念格模式相关概念给定一个由交易(Transaction)组成的交易数据库DB。论文检测。每个交易描述一位顾客在某时刻的一次买卖行为，内容包含顾客号(Cid)、交易事件(Event)其中，每个交易序列中的事件具有唯一的标识符Eid和交易的物品集合。规定同一个顾客在一个交易时间只能进行一次交易，并且不考虑顾客在一次交易中所购置物品项的数量。定义 1 把每个商品称

4、为一个数据项Item，简称项，令非空集合(i1,i2,im)，其中，ij(j=1,2, ,n)是不同的项，项的集合称为工程集合item set,简称项集，其中每个k(1km)是一个项，长度为k的项集称为k项集。如果把顾客的所有交易事件按交易时间进行排列，将得到一个顾客序列,记作这里Eidi(1in)是某顾客的第i次交易标识符，Event(Eidi)为该次交易中顾客购置的项集。由全部顾客序列组成的数据库称为顾客序列数据库，记作SDB。通常，得到SDB需要对原交易数据库重构。定义 4 顾客支持序列S指序列S包含于该顾客序列中。序列S的支持度指顾客序列数据库SDB中支持S的顾客数(也称的支持数)与S

5、DB中顾客总数量之比。大于最小支持度(minimum support，由用户指定的阈值，记为S)的序列称为SDB上的频繁序列。定义 5 项集的支持度(support)定义为在某次交易中购置了该项集所含物品的顾客数与总顾客数之比。支持度大于最小支持度的项集称为频繁项集。给定交易数据DB和用户指定的最小支持度S，序列模式挖掘的问题就是发现DB中所有满足S的子序列，每一个这样的子序列代表了一个序列模式(a sequential pattern)序列模式挖掘的任务就是找出数据库中所有的序列模式，即那些在序列集合中出现频率超过最小支持度(用户指定最小支持度阈值)的子序列。定义 6 给定两个序列A=和B=

6、，如果存在一组整数使得a1bi1，a2bi2，ambim，那么称序列A被序列B包含。不包含在任何其它序列中的序列称为最大序列(Maximal Sequence)。定义7 在形式背景K(Cid,Eid),Event,SIM|(Event)|)中，t(Cid,Eid)，eEvent，在(Cid,Eid)和Event之间可定义两个映射f和g：定理 1 在形式背景K(Cid,Eid),Event,SIM|(Event)|)上，假设对于，一个三元组，那么C必为一个兴趣序列概念。那么在其形式背景K上，由所有序列概念的超概念-子概念的偏序关系所诱导出的格结构称为兴趣序列概念格这种偏序关系，使用符号;表示，记

7、为IFL(K)。3.带兴趣度的序列概念格的最大模式算法研究对于任意的序列数据库SDB，一旦按照算法SCLI构造好了对应于交易数据库的序列概念格，就可以直接从格中得到所有的用户感兴趣的1-兴趣序列，这个过程对应于AprioriAll算法的第一步，但是对数据库的扫描次数却大大减少了。将得到的1-兴趣序列最为种子集合进行迭代以求得全部的序列模式。然后按照定义8定义9进行k-序列的扩展即可，并不需要屡次扫描原始数据库而只需要扫描候选兴趣序列的位置集合即可。定义 8 给定一个序列S=(其中sk(k=1,2, m)是一个工程集)和一个工程，S的含义是S连接，S在数据库中的位置为(Cidi,Eidi)，在数

8、据库中的位置为(Cidj,Eidj)，当Cidi=Cidj且Eidi，简称运算。例如：假设有项a和b，其中的位置信息为(10,1)(20,1)(20,2)，的位置信息为(10,2)(20,3)(30,2)，那么的位置信息(10,2)匹配的位置信息(10,1)，因为它们有相同的Cid=10，并且前者的Eid=2大于后者的Eid=1。同样地，(20,3)匹配(20,1)，但是的位置信息(30,2)没有与之匹配的位置信息，因为在的位置信息中，不存在位置这样的位置信息使得Cid=30。因此，通过序列扩展可以生成序列，并且序列 的位置信息为(10,2)(20,3)。定义 9 给定一个序列S=(其中sk(

9、k=1,2, m)是一个工程集)和一个工程，S的含义是S连接，S在数据库中的位置为(Cidi,Eidi)，在数据库中的位置为(Cidj , Eidj)，当Cidi=Cidj且Eidi=Eidj时称为项扩展，新序列为S，把作为一个工程并入S的最后一个元素中，新序列S的位置为(Cidi,Eidj)。记为：S=，简称运算。例如：假设有项b和d，其中，的位置信息为(10,1)(20,2)(30,2)，的位置信息为(10,2)(20,2)(30,2)，那么的位置信息(10,2)(30,2)与的位置信息(10,2)(30,2)相匹配，因为它们有相同的Cid及相同的Eid，但是的位置信息(20,2)没有与之

10、匹配的的位置信息，所以，通过项扩展可以生成序列，并且序列的位置信息为(10,2)(30,2)。在基于兴趣的序列概念格的根底上，可以快速地发现最大的序列模式以及用户需求的频繁序列。算法思想如下：(1) 利用算法SCLI生成基于兴趣度的序列概念格IMSL。(2) 把格IMSL节点中各序列的位置信息保存到位置信息表中。格IMSL 中的各序列就是1-兴趣序列。(3) 扫描位置信息表，对位置信息表中的各序列利用运算与运算进行2-序列的扩展，同时判断候选序列S在SDB中的支持兴趣度值SIM|(S)| = SIM(S)*Support(S)是否大于Min-Sim，假设大于那么把生成的2-序列中各序列的位置信

11、息更新到位置信息表中。(4) 扫描2-序列中的位置信息表，对位置信息表中的各序列利用运算与运算进行3-序列的扩展，并把生成的3-序列中各序列的位置信息更新到位置信息表中。同理生成k-序列，直到没有生成新的序列扩展或项扩展为止。(5) 按照定义6扫描位置信息表，生成最大兴趣序列模式。算法IMLSP(Interest Measure LatticeSequence Pattern)实现了挖掘满足用户需求的最大序列模式，具体算法描述如下： 算法 Procedure IMLSP (IMSL (K), IMV,) 输入：序列模糊格IMSL (K)，兴趣序列阈值Min-Sim 输出：满足用户需求的兴趣序列

12、模式集MaxIMseq 1: Begin 2: Maxseq:= 3: For each node of IMSL(K) do 4: Mark:= Eventi 5: Tab(S). Si:= Eventi 6: Tab(S). Eposi := (Cid , Eid) i 7: Tab(S). SIMi := SIMi |( Event)| 8: For two Event of Tab(S) do 9: IF Cidi= Cidj and Eidi针对表1中的序列数据库中构建的基于兴趣度的序列概念格模型进行最大序列模式的挖掘，其中，Min-Sim =0.6。 表1 交易数据库 Cid Se

13、quence 10 20 30 40 (1) 按照算法SCLI生成相应的序列概念格的Hasse图如图1。图1 序列概念格的Hasse图(2) 把图1节点中各序列的位置信息保存到位置信息表中如下表2表2 图1中1-序列的位置信息 1-序列 位置信息 Sim (10,1)(10,2) (20,1) (30,2)(40,1) 1.0 (10,1)(20,1)(30,3)(40,1)(40,3) 2.0 (10,1)(10,2)(10,4)(40,2) 2.0 (10,3)(20,2)(40,2) 1.8 (10,4)(20,2)(30,2) 0.9 (30,1)(40,3) 1.6 (40,4) 1

14、.1 (10,1) (20,1)(40,1) 0.9 (10,1) (10,2) 0.7 (40,3) 1.2 (30,1) 0.8 (3) 对表2中的每个1-序列利用运算与运算进行2-序列的扩展，同时判断候选序列S在SDB中的支持兴趣度值SIM|(S)| = SIM(S)*Support(S)是否大于Min-Sim，本例中Min-Sim=0.6，假设大于那么把生成的2-序列中各序列的位置信息更新到位置信息表中表3。表3 2-序列的位置信息 2-序列 位置信息 Sim (30,3)(40,3) 0.6 (10,2)(10,4)(40,2) 1.05 (10,3)(20,2)(40,2) 1.2

15、 (10,4)(20,2) 0.5 (10,2)(10,4)(40,2) 1.35 (10,3)(20,2)(40,2) 1.5 (10,4)(20,2) 0.7 (10,2)(10,4)(40,2) 1.1 (10,4)(20,2) 0.6 (4) 由2-序列没有生成3-序列，故，最长的序列模式长度为2。(5) 最后生成的最大兴趣序列模式：、，其序列模式的兴趣度值分别为1.1、0.6、1.05、1.2、1.5、1.2、0.75、1.1、0.6。4.结果分析将本文研究的基于序列概念格的挖掘算法与传统的挖掘算法相比拟，我们可以得出以下结论：(1) 由于序列概念格的渐进式构造算法的优点在于可以实现

16、概念格的维护和更新，因此，带兴趣度的序列概念格的挖掘完全适应于增量式挖掘序列模式，当有新数据参加，即数据库规模增大时，不需要重新扫描整个新数据库，只需要在原始序列概念格上进行更新操作，得到新的序列概念格，然后按挖掘过程获取新的序列模式，实现对序列模式发现的增量挖掘。(2) 另外一个问题是由于概念格的节点数量在最坏的情况下是呈指数增长的，因此内存的消耗量有时会到达难以承受的程度，因此可以考虑利用外部存储器和分解格或者采取并行的方法来构格。5.结语基于兴趣度的序列概念格的最大序列模式挖掘完全适应于增量式挖掘序列模式。论文检测。序列概念格构造是建立在序列数据库形式背景的根底上，序列形式背景的复杂性很

17、大程度上制约后续处理的性能，因此如何将序列数据库转化成序列形式背景，并满足用户支持度和置信度的情况下，使序列形式背景进一步优化是一个重要的预处理研究方向。所以，下一步的研究那么需要考虑并行处理以提高挖掘的效率。参考文献【1】 AGRAWAL R，IMIELINSKI T，SWAMI AMining association rulesbetweensets of items in large databasesProceedings of the ACM SIGMOD Conference on Management of DataWashington，DC：ACM Press，1993：207

18、216【2】 Agrawal R ,Srikant R. Mining Sequential Patterns . Proc 1995 Int Conf Data Engineering( ICDE95) .Taipei : IEEE Computer Society ,1995. 3141【3】 Agrawal R ,Srikant R. Mining Sequential Patterns : Generalizationgs and PerformanceImprovments . Proc 5th Int Conf Extending Database Technology ( EDBT) .Avignon : Lecture Notes in Computer Science , 1996. 317.【4】 M. Zaki. SPADE:An Efficient Algorithm for Mining Frequent Sequences. Machine Learning, 2001，411 / 2:31 - 60 .【5】 Han J，Pei J，MortazaviAsl B，et a1Prefixspan：Mining Sequential PatternsEficiently by P