基于带索引的位图挖掘连续序列的频繁模式.docx

基于带索引的位图挖掘连续序列的频繁模式目录基于带索引的位图挖掘频繁连续序列11.概念11.1 频繁模式11.2 关联规则、支持度和置信度11.3 序列21.3.1 单元序列21.3.2 多元序列21.4 连续子序列21.5 连续序列融合规则22.基于带索引的位图挖掘频繁连续序列32.1IBM数据结构32.1.1 IBM位图32.1.2 SV向量42.1.3 Index索引42.1.4 NB表42.1.5 范例42.2IBM算法流程52.2.1 创建内存数据结构对象52.2.2 挖掘频繁连续序列62.3范例62.3.1创建内存结构对象62.3.2挖掘频繁连续序列82.3.4频繁连续序列结果123 参考131. 概念1.1 频繁模式正如名称所说，频繁模式（frequent pattern）是在数据中频繁出现的模式。存在多种类型的频繁模式，包括频繁项集、频繁子序列（又称序列模式）和频繁子结构。频繁项集一般是指频繁地在事务数据集中一起出现的商品的集合，如小卖部中被许多顾客频繁地一起购买的牛奶和面包。频繁出现的子序列，如顾客倾向于先购买便携机，再购买数码相机，然后再购买内存卡这样的模式就是一个频繁序列模式。子结构可能涉及不同的结构形式（例如：图、树和格），可以与项集或子序列结合在一起。如果一个子结构频繁地出现，则称它为频繁结构模式。挖掘频繁模式导致发现数据中有趣的关联和相关性。1.2 关联规则、支持度和置信度频繁项集挖掘的一个典型例子是购物篮分析，该过程通过发现顾客放入他们“购物篮”中的商品之间的关联，分析顾客的购物习惯。如果我们想象全域是商店中商品的集合，则每种商品有一个布尔变量，表示该商品是否出现。每个购物篮可用一个布尔向量表示。可以分析布尔向量，得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规则（association rule）的形式表示。例如，购买计算机也趋向于同时购买杀毒软件，可以用以下关联规则（6.1）表示：computer = antivirus_softwaresupport = 2%; confidence = 60% （6.1）规则的支持度（support）和置信度（confidence）是规则兴趣度的两种度量，它们分别反映所发现规则的有用性和确定性。关联规则（6.1）中支持度support=2%，意味着所有事务中的2%显示计算机和杀毒软件被同时购买。置信度confidence=60%意味着购买计算机的顾客中又有60%同时购买了杀毒软件。关联规则是形如A=B的蕴含式。support(A=B) = P(A U B)，confidence(A=B) = P(B | A)1.3 序列1.3.1 单元序列形如的序列，注意其中任意一个元素Sk都只有一个子项。1.3.2 多元序列形如，其中任意一个元素Sk本身内部又包含多个子项。规定S1，S2称为序列的元素（element），把a1,a2,，b1,b2，c1,ct等称为序列元素的子项(item)1.4 连续子序列给定一个序列S = , 再给定另外一个序列C，当C满足以下三个条件中任意一个时，称C是S的连续子序列。【1】 删除S的首元素S1后等于c，即c=，【2】 删除S的尾元素Sn后等于c，即c=，【3】 删除S的任意元素Si的任一个子项ak后等于c，即c=，【4】 C是D的连续子序列，同时D又是S的连续子序列。定义当C满足以上任意一个条件时，则称C是S的连续子序列。举例说明：假定S = 时：序列，都是S的连续子序列，但是，都不是S的连续子序列。分析：是S删除中间一个元素(5)得到的，这不符合定义。1.5 连续序列融合规则已经两个长度为k的连续序列S1和S2，他们融合成长度为k+1的连续序列的条件如下：【1】S1删除第一个元素后的序列为S1，或者S1删除第一个元素的第一个子项后得到的序列S1【2】S2删除最后一个元素后的序列S2， 或者S2删除最后一个元素的最后一个子项后得到的序列S2。【3】 当S1=S2时，S1和S2可以融合。【4】融合方法分两种情况：【4.1】当S2删除最后一个元素后的序列S2时，只需要把S2的最后一个元素加入S1尾部，成为新的最后一个独立新元素即可。【4.1】当S2删除最后一个元素的最后一个子项后得到的序列S2时，只需要把S2的最后一个元素的最后一个子项嵌入到S1原来最后一个元素的最后一个子项后面即可。范例1： S1 = ， S2= S1 = ，S2 = 由于S1=S2，同时4是S2最后一个元素(3,4)的最后一子项，所以S1可以融合S2，融合方法是把4嵌入到S1最后一个元素的最后一个子项后面，结果是范例2： S1 = ， S2= S1 = ，S2 = 由于S1=S2，同时(5)是S2最后一个元素，所以S1可以融合S2，融合方法是把(5)嵌入到 S1最后一个元素后面，结果是2. 基于带索引的位图挖掘频繁连续序列本文主要介绍了参考文献【1】中提到的IBM算法的内容，数据序列只考虑序列中每个元素只有一个子项的情况。2.1 IBM数据结构包含如下四个组件：IBM、SV、Index和NB。2.1.1 IBM位图二维矩阵位图，表示了数据库中独立的序列。2.1.2 SV向量为序列的所有可能的有序组合的编码2.1.3 Index索引为位图服务的索引，记录了不同长度序列在位图中存放的行数的开始位置，方便根据索引直接定位到位图的某一行。2.1.4 NB表记录每个独立序列的频繁度。2.1.5 范例使用如下例子说明四个组件的关联关系。 已知事务序列中包含不同类型的行为，用字符标记每种行为：H=Home, W=Work, S=School, M=Market, R=Restaurant数据库循环过程中依次发现如下序列和频率：【1】 HWH，出现15次【2】 HSH，出现10次【3】 HSMH，出现12次【4】 HWMWH，出现1次以上数据存入数据结构后如下图：2.2 IBM算法流程算法分两步完成：创建内存数据结构对象（从上图00行05行），和挖掘频繁连续序列（从上图06行11行）。2.2.1 创建内存数据结构对象对所有事务序列仅遍历一次，在内存分别创建4个组件（Index、IBM、SV和NB）的对象。其中难点是创建SV向量，算法流程如下图：插入每条事务序列时都需要沿用或修改已有的SV向量。循环事务序列中每一个行为动作a【上图02步】：当a在SV中时直接处理下一个行为动作【上图07步】；当a不在SV中时【上图03步】：如果s中a后面存在一个动作b在SV中，同时b在SV中位置是当前位置后面，则把s插入到SV中b之前【上图0405步】如果s中a后面没有一个动作b在SV中则把s插入SV当前遍历的位置【上图06步】。2.2.2 挖掘频繁连续序列从长度为1的频繁连续序列开始，依次创建长度为2、3、4的频繁连续序列。循环k次时，把上一次生成的长度为k-1的所有频繁连续序列作为种子，用这些种子生成长度为k的频繁连续序列。循环结束的条件是不再有更长的频繁连续序列产生时就停止循环过程。2.3 范例已知序列事务依次为：HWH、HWH、HSH、HWH、HSH、HSMH、HWMWH、HSH、HWH、HW。假定支持度最小阈值为0.2。下面按照IBM算法详细介绍创建内存结构对象，然后再挖掘频繁连续序列的过程。2.3.1 创建内存结构对象按照序列事务的顺序依次读取，插入到内存数据结构中。1. 插入HWH2. 插入HWH3. 插入HSH4. 插入HWH5. 插入HSH6. 插入HSMH7. 插入HWMWH8. 插入HSH9. 插入HW2.3.2 挖掘频繁连续序列2.3.2.1.1 频繁1连续序列候选序列分别是：、。计算频率：、所有事务的总频率=NB表所有值之和=1+3+3+1+1=9计算支持度：、。大于最小支持度（0.2）的频繁1连续序列为：序列支持度H1.888W0.666S0.444M0.222细节说明：如何求W的频率=5+1W出现在IBM矩阵的第2列（第1,2,5行，频率分别是1,3,1）和第5列（第5行，频率是1），W的频率是1+3+1+1=6。2.3.2.1 频繁2连续序列2.3.2.1.1 生成候选序列以频繁1序列、为种子，创建候选序列：从4个选项中取2个元素的排列一共12个候选序列，分别是：,2.3.2.1.2 生成频繁连续序列计算频率候选连续序列出现频率支持度大于最小支持度（0.2）的频繁2连续序列1+3+1=5计算过程：查询Index表第2行的值为1，所以从IBM中第1行开始检查是否出现H和W，发现1,2,5行都出现，每行频率分别是1,3,1，所以总频率=55/9=0.5553+1=4计算过程：查询Index表第2行的值为1，所以从IBM中第1行开始检查是否出现W和H，发现2,5行都出现，每行频率分别是3,1，所以总频率=44/9=0.4443+1=4计算过程：IBM中第3行第1、3列, 第4行第1、3列都出现H和S，注意是先出现H，然后是S4/9=0.4443+1=4计算过程：IBM中第3行第3、6列, 第4行第3、6列都出现S和H，注意是先出现S，然后是H4/9=0.4441+1=22/9=0.2221+1=22/9=0.2220001IBM中第5行第2,4列出现。1/9=0.1111IBM中第5行第4,5列出现。1/9=0.11111/9=0.11100总结：频繁2连续序列为：0.5550.4440.4440.4440.2220.2222.3.2.1 频繁3连续序列1.生成候选序列以频繁2连续序列为种子，共6个，生成频繁3连续序列。生成方法不能采用从6个元素中提取3个元素的排列方法了，必须从6个种子中任取2个种子，根据连续序列融合规则的方法生成。从6个种子中任取2个的排列（共30个）如下：-根据连续序列融合规则进行融合：必须满足中间元素相同才可以融合。两个长度为2的序列融合生成长度为3的序列备注-删除首元素为，同时删除尾元素为，由于和相等，所以融合成长度为3的序列-无删除首元素为，但是删除尾元素为，由于和不相等所以无法融合成长度为3的序列-无-无-无-无-无-无-无-无-无-无-无-无-无-无-无-无-无-小结：融合生成的长度为3的序列共12个，如下：2.生成频繁连续序列候选连续序列出现频率支持度大于最小支持度（0.2）的频繁3连续序列3+1=4计算过程：由于是3个元素长度，所以直接查询Index表第3行的值为2，所以从IBM中第2行开始检查是否出现，发现2,5行都出现，所以总频率=3+14/9=0.444003+14/9=0.4440022/9=0.22200000000000000小结：频繁3连续序列: ，2.3.2.1 频繁4连续序列1.生成候选序列把频繁3连续序列（，）作为种子，随意提取2个种子进行融合。两个长度为3的序列融合生成长度为4的序列备注-无-无-无-无-无-无2.生成频繁连续序列由于候选的4连续序列不存在，所以不可能有频繁4连续序列。2.3.4 频繁连续序列结果频繁连续序列长度频繁连续序列支持度1H1.8881W0.6661S0.4441M0.22220.55520.44420.44420.44420.22220.22230.44430.44430.2223 参考1 Lionel Savary and Karine Zeitouni. “Indexed Bit Map (IBM) for Mini