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

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

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

3、效率。李云8提出带兴趣度的序列概念格模型及其构造算法把概念格的每个结点本质上是一个最大项目集，非常有利于序列模式发现。通过扫描格节点就能能生成商家期望的感兴趣序列，本文在带兴趣度的序列概念格模型上进行最大序列模式挖掘。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的顾客数(也称的支持数)

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

6、B=，如果存在一组整数使得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(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)