基于矩阵算法的序列模式挖掘研究

基于矩阵算法的序列模式挖掘研究 甄慧玲（2011111286）理学院 摘　要:序列模式挖掘中几种算法的缺点:都要进行多次扫描数据库,CPU要进行多次I/O操作。这成为序列挖掘中的一大瓶颈,使得算法在实际应用中的效率不高。文中提出一种矩阵算法,即在一次扫描数据库时,根据扫描数据建立由0和1组成的事务矩阵。接下来的大序列、序列模式等都是通过矩阵的列向量对应元素的相乘运算和简单的加法运算而得到。从而使算法得到进一步优化,提高了CPU的使用率,解决了序列挖掘中的瓶颈问题。本算法通过大量的数据实验,证明了算法确实有效地优化了算法的时间复杂度。 关键词:序列模式挖掘；序列模式；大序列；矩阵算法；连接运算 引言 随着信息技术迅速发展，数据库的规模不断扩大，从而产生了大量的数据。激增的数 据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ，以便更好地利用 这些数据。为给决策者提供一个统一的全局视角，在许多领域建立了数据仓库。但大量的 数据往往使人们无法辨别隐藏在其中的能对决策提供支持的信息，而传统的查询、报 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 工 具无法满足挖掘这些信息的需求。因此，需要一种新的数据分析技术处理大量数据，并从 中抽取有价值的潜在知识，数据挖掘（Data Mining）技术由此应运而生。数据挖掘技术 也正是伴随着数据仓库技术的发展而逐步完善起来的。 数据挖掘是指从数据集合中自动抽取隐藏在数据中的那些有用信息的非平凡过程，这些信息的表现形式为：规则、概念、规律及模式等。它可帮助决策者分析历史数据及当前数据， 并从中发现隐藏的关系和模式，进而预测未来可能发生的行为。数据挖掘的过程也叫知识 发现的过程，它是一门涉及面很广的交叉性新兴学科，涉及到数据库、人工智能、数理统 计、可视化、并行计算等领域。数据挖掘是一种新的信息处理技术，其主要特点是对数据 库中的大量数据进行抽取、转换、分析和其他模型化处理，并从中提取辅助决策的关键性 数据。 数据挖掘是KDD（Knowledge Discovery in Database）中的重要技术，它并不是用 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 的数据库查询语言（如SQL）进行查询，而是对查询的内容进行模式的总结和内在规律的搜索。传统的查询和报表处理只是得到事件发生的结果，并没有深入研究发生的原因，而数据挖掘则主要了解发生的原因，并且以一定的置信度对未来进行预测，用来为决策行为提供有利的支持。 随着计算机技术的不断发展，信息量的不断增加，人们对数据挖掘技术不断重视，而数据挖掘的研究本身也融合了多个不同学科领域的技术与成果，使得目前的数据挖掘方法表 多种多样的形式。从统计分析类的角度来说，统计分析技术中使用的数据挖掘模型有分析和非线形分析、回归分析、逻辑回归分析、单变量分析、多变量分析、时间序列、最近序列分析、最近邻算法和聚类分析等方法。利用这些技术可以检查那些异常形数据，然后，利用各种统计模型和数学模型解释这些数据，解释隐藏在这些数据背后场规律和商业机会。知识发现类数据挖掘技术是一种与统计分析类数据挖掘技术完全的挖掘技术，包括人工神经元网络、支持向量机、决策树、遗传算法、粗糙集、规则和关联顺序等。 序列模式挖掘又称序列挖掘[1],主要是找出序列数据库中那些在序列集合中出现频率超过最小支持度[2]或者用户指定的最小支持阈值[2]的子序列。其目的是想通过在含有交易时间属性的客户交易数据库中发现频繁项目序列,通过频繁项目序列找出一定的时间段内客户购买活动的规律[2,3]。序列模式的挖掘主要是基于大项集[4]的挖掘,主要思想是: 首先,把交易数据库转换为以客户序列为记录的数据库;其次,利用大项集搜索算法计算大项集,作为一阶大序列;再次,以一阶大序列为基础,依次搜索所有阶的大序列;最后,从大序列中删除子序列,最终得到序列模式。 从以上过程可以看出,序列模式挖掘一般分为五个步骤[2,5],它们分别是排序阶段[5]、大项集阶段[5]、转换阶段[5]、序列阶段[5]、选最大阶段[5]。序列模式挖掘主要来源于关联规则挖掘[3,6,7],是关联规则应用的延伸。 在关联规则挖掘Apriori算法[2,8]的基础上,由Agrawal和Strikant[2]等人提出几种序列模式的挖掘算法,即AprioriAll[5]、AprioriSome[5]及DynamicSome[5]。但这几种算法都要进行多次扫描数据库,扫描数据库便成为序列模式挖掘中的一大瓶颈,多次扫描数据库更是如此。基于种种对比，本文认为矩阵是瓶颈问题的克星。文中提出的矩阵算法主要是解决多次扫描数据库的瓶颈问题。在介绍矩阵算法之前先简要介绍Aprio-riAll算法和AprioriSome算法以便进行对比。 基本概念及示例数据库 2.1 基本概念 基本概念如下: 序列:序列是项集的一个非空有序集合,也就是一个集合的集合,记为{s1, s2,…sn},其中si是一个项的集合,表示在同一条交易中出现的商品。 客户序列:把一个客户的所有交易按照时间的升序排列成一个序列< t1, t2,…, tn>,称为客户序列或顾客序列(customer sequence[9])。 支持阈值[4,10]:主要从统计学的角度来理解,表示项集或客户序列在统计意义上的最低重要性。如果交易数据库的客户数量是固定的,可以用最小支持数[2,6]minsup[9,11]来代替支持阈值。如果项集X的支持数不小于最小支持数,即X. sup≥minsup(文中设最小支持数minsup=2)。则称X是大项集( large item-set)或频繁项集[4](frequent itemset[9,11])。如果序列A的支持数不小于最小支持数,即A. sup≥minsup,则A是大序列[7]( large sequence)或频繁序列( frequent se-quence)。 序列模式[7,12]:具有最小支持数的最大序列称为序列模式。它必须满足两个条件:首先,支持数大于等最小支持数;其次,不是其它大序列的子序列[2]。 数据挖掘算法的一般组成部分：一般分成一下四个部分； (1)模型或模式结构 数据挖掘中的建模是为了捕捉数据中存在的关系。模型或模式结构决定了从数据中寻找的潜在结构或函数形式。模型是对一个数据集的高层次、全局性的描述，可以是描述性的，也可以是推理性的。而模式则是数据的局部特征，或许只支持几条记录或者几个变量。有时候，模式描绘的是和一般行为相背离的。 (2)评分函数 评分函数用于根据观察到的数据判断拟合后的模型或模式的质量。评分函数在反映模型或模式的不同参数化过程的实际效果方面是很重要的。在理想情况下，最佳的评分函数应该精确地反映出特定预测模型的效果，也就是期望模型所带来的真正效益。 （3）优化和搜索方法 优化和搜索方法用于优化评分函数和对模型或模式结构进行搜索，是所有数据挖掘算法的核心部分。通常模型或模式是以各种形式的结构来描述的，有时还带有未知的参数。优化和搜索的目标就是决定这些结构和参数值，以使评分函数达到最优。发现模型中的最佳参数值的任务通常被称为最优问题。从庞大的潜在模式族中发现感兴趣的模式的任务通常被当作组合搜索问题。 （4）数据管理策略 数据管理策略指存储、索引、检索数据的数据管理技术。数据挖掘算法面对的是海量数据集，这使数据挖掘算法的效率问题变得非常重要。尽管主存储器技术在迅速地提高，磁盘、磁带存储技术也在提高，但访问海量数据集仍然要付出一定的开销。数据管理策略的目标就是使对数据集的访问尽可能快，使开销尽可能小。 2.2　示例数据库 客户标识 客户序列 1 <(40),(100)> 2 <(20,30),(40),(50,70,80)> 3 <(40,60,80)> 4 <(40),(50,80),(100)> 5 <(100)> 表1：示例数据库 客户标识 交易标识 项集 1 1 40 1 2 100 2 1 20，30 2 2 40 2 3 50，70，80 3 1 40，60，80 4 1 40 4 2 50，80 4 3 100 5 1 100 表2　预处理后的交易数据库Ds 大项集 支持数 映射后的整数值 （40） 4 1 （50） 2 2 （80） 3 3 （50，80） 2 4 （100） 5 5 表3　大项集的映射(最小支持度minsup=2) 三、对序列模式挖掘常用算法的分析 3.1 AprioriAll算法分析 AprioriAll算法的思想主要来源于关联规则挖掘中的Apriori算法,它是Apriori在序列模式挖掘中的扩展应用。它和Apriori一样,也是一个要进行多次扫描数据库的算法。在每一次扫描中都利用前一遍的大序列来产生候选序列[2,4],在扫描完整个数据库后再来进行支持度的检测。在第一遍的扫描中,大项集阶段的输出被用来初始化1阶大序列的集合。在每次遍历中,从一个由大序列组成的种子集[2,7]开始。利用这个种子集,可以产生新的潜在的大序列。在第一次遍历前,所有在大项集阶段得到的1阶大序列组成了种子集。AprioriAll算法描述如下: 客户标识 客户客户序列 大项集标识的客户序列 转换后的序列 1 <(40),(100)> <{(40)},{(100)}> <{1}, {5}> 2 <(20, 30),(40), (50, 70, 80)> <{(40)}, {(50), (80), (50, 80)}> <{1}, {2, 3, 4}> 3 <(40, 60, 80)> <{(40, 80)}> <{1, 3}> 4 <(40), (50, 80),(100)> <{(40)}, {(50),(80), (50, 80)},{(100)}> <{1}, {2, 3, 4}, {5}> 5 <(100)> <{(100)}> <{5}> 表4　转换后的数据库Dt 输入:序列数据库Dt 输出:所有最长序列[5] 算法具体实现如下： L1={frenquent items}; For (k=2; Lk-1≠Φ; k++) do Ck=Get_candidate(Lk-1); For all customer sequence c∈Dtdo Ct=subset(Ck, c); For all s∈Ctdo s. sup=s. sup+1; end for End for; Lk={s∈Ck|s. sup≥minsup}; End for Lk=UkLk; 本算法中候选序列的调用Get_candidate()[5]函数来实现,这样大大减少候选序列的个数。AprioriAll利用了Apriori算法的思想,但在候选序列的产生和频繁序列生成方面需要考虑序列元素的特点后再作相应的处理。 AprioriAll的算法性能分析如下: 1)缺少时间限制[2]:需要用户的干预来指定序列模式中相邻元素之间的时间间隔[5,7]。 2)严格事务的定义[2]:客户的一次购买行为中所购买的所有物品必须包含在一个事务中。 3)没有分类层次[2]:只能在项目的原始级别上进行挖掘[2,5]。 4)多次扫描数据库:在每一次进行支持度的检测时都要扫描数据库。 基于AprioriAll算法的这些缺点,于是产生了AprioriSome算法。 3.2 Apriorisome 算法分析 AprioriSome算法描述如下: 输入:序列数据库DT； 输出:所有最长序列[5]； 算法具体实现如下： //前向搜索阶段 Lk={frequent items}; C1=L1; Last=1; For (k=2;Ck-1≠Φand Llast≠Φ; k=k+1) do If(Lk-1存在) then Ck=Get_candidate(Ck-1); End if Ifk=nest(last) then For all customer sequence c∈Dtdo Dt=subset(Ck, c); For all s∈Ctdo s. sup=s. sup+1; End for End for End if Lk={s∈Ct| s. sup≥minsup }; Last=k; End for //后向搜索阶段 For(k-1; k≥1; k=k-1) do IfLk不存在then Delete all sequence in Ck contained in Li(i>k); For all customer sequence c∈Dtdo Ct=subset(Ck, c); For all s∈Ctdo s. sup=s. sup+1; end for Lk={s∈Ct| s. sup≥minsup }; End for Else Delete all sequence in Lk contained in Lk(i>k); end if End for Lk=UkLk; 从上面两个算法可以看出, AprioriSome算法是AprioriAll算法的改进,它分为前推和回溯两个阶段。确实时间上比AprioriAll要节省很多,但AprioriSome还是要进行多次扫描数据库。基于以上两个算法都要多次扫描数据库,多次扫描数据库便成为序列挖掘的一大瓶颈。为了解决这一瓶颈问题,文中提出了一种只对数据库进行一次扫描的矩阵算法。 四、矩阵算法 4.1　矩阵生成 本文认为，矩阵是数学上极为有用的工具，不仅因为它的表现形式比较简单，可以用最少的空间最大的整合数据，更重要的是，利用矩阵，我们可以把数学上的运算转换到实际应用中。所生成的矩阵和需要运算处理的矩阵之间可以利用数学上的运算，而运算结果我们只需要把实际的意义代如抽象模型，则得到很精确的结果。 令I= {i1, i2,…in}为映射后的整数值,T = {t1,t2…tm}为转换后的序列。初始矩阵C1按如下规则生成。矩阵C1的元素{eij}定义如下: 其中i=1,2,…m;j=1,2…n。 ,其中j=1,2,…n。 下面通过表4中的数据来说明矩阵的生成过程。映射后的整数值，在文中我们把它称为“上标”，具体 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 我们通过下图进行展示。 在上图中,最上面一行元素是映射后的整数值,把它们称为“上标”,它们不是矩阵的元素。矩阵中最下面一行元素是生成矩阵中每个列向量中前m个元素中“1”的个数,最左边的一列(t1、t2、t3、t4、t5)为转换后的客户序列,中间由“0”和“1”组成的部分为生成矩阵,其生成规则为:当映射后的整数值(1、2、3、4、5)在转换后的客户序列(t1、t2、t3、t4、t5)中出现时对应元素值为“1”,否则为“0”。应用这个矩阵可以产生各阶大序列候选矩阵Ci和各阶大序列矩阵Li,并最终生成序列模式。 4.2　向量的连接运算 规定两个向量的连接运算如下:进行连接运算的两个列向量中,把它们的前m个对应元素进行相乘的积作为所产生的新向量相对应的前m个元素,而新向量的第m +1个元素为新向量中前m个元素中值为“1”的元素的个数,新向量的上标为进行连接运算的所有向量对应的上标。例如上面的矩阵的第一个列向量和第二个列向量,第三个列向量和第五个列向量进行连接运算的过程。具体运算流程见下图： · 连接 产生 向向量的 产生 运算 新向量 连接 新向量 运算 上图：向量的连接运算 4.3 矩阵的算法描述 (1)在初始矩阵C1中找出每个列向量的第m +1个元素值大于或等于最小支持数minsup的这些列向量,把这些满足条件的列向量重新组成1阶大序列矩阵L1。 (2)由Li进行自连接运算产生i+1阶候选矩阵Ci+1,在候选矩阵Ci+1的每个列向量中找出第m +1个元素值大于或等于最小支持数minsup的这些列向量,把这些满足条件的列向量重新组成i+1阶大序列矩阵Li+1。 (3)重复步骤(2)直到Li为空。 用以上矩阵为例,说明一下矩阵算法的过程。假设最小支持数minsup=2,从初始矩阵C1中选出满足最小支持数minsup的列向量,即最后一行元素大于2的列向量组成L ， 由于C1中的每个列向量的最后一个元素的值都大于最小支持数minsup,所以L1=C1。由L1进行自连接运算得出C2。 再由C2中选出满足最小支持数minsup的列向量组成L2。 再由L2进行自连接运算得到C3。 再由上矩阵中满足最小支持数的列向量组成L3。 由L3进行自连接运算得出C4。再由C4中选出满足最小支持数minsup的向量组成L4。由于C4中只有一个列向量,不能产生C5,从而也不能生成L5,所以算法终止。 ， 从以上算法过程可以看出L1、L2、L3、L4四个矩阵的上标就对应着大序列。 4.4 删除子序列 (1)在矩阵L1,L2,L3中去掉矩阵L4中上标的所有子集所对应的上标。L4的上标为“1.2.3.4”,它的所有子序列为“1”、“2”、“3”、“4”、“1.2”、“1.3”、“1.4”“2.3”、“2.4”、“1.2.3”、“1.2.4”、“2.3.4”。这样,L3中的上标全部被去掉。L2中只剩下上标“1.5”;L1中只剩下上标“5”。 (2)在矩阵L1中去掉矩阵L2中剩下的上标“1.5”的所有子集所对应的上标;这样,L1中的所有上标全部被去掉。 (3)在L1、L2、L3、L4四个矩阵的所有上标中只剩下上标“1.2.3.4”和“1.5”。 4.5 大序列的产生 L1、L2、L3、L4中剩下的所有上标的集合就是所要求的序列模式。进行上述操作后,产生的序列模式为:{<1　2　3　4>, <1　5>},执行过程如下所示: 在L3中删除L4的所有子集 在L2中删除L4的所有子集,在L1中删除L4和L2的所有子集，最后结果如下矩阵所示。 实验结果分析 根据以上算法步骤的分析与研究,矩阵算法与传统序列模式挖掘算法相比,主要是矩阵的计算。而对各K阶项集的支持度的计算显得尤其简便,无需对数据库进行多趟扫描。 本算法在联想电脑(T6400—2.0G,2G内存)上使用Java进行实验,采用的数据库是来自某百货销售公司的销售数据,约5万条。同时在同一台计算机上对同样的数据库采用AprioriSome算法进行实验,结果发现两种算法的结果是相同的,这验证了矩阵算法的正确性。但在时间上,矩阵算法的运行时间明显比AprionSome算法少。主要是矩阵算法充分利用向量计算的优势,它只扫描事务数据库库一次且直接通过布尔运算计算项集的支持度,比经典的AprioriSome算法占用内存空间小, I/O操作少,执行速度快。 总结 本文提出了一个新的算法———矩阵算法。在实际的应用中,大型交易事务数据库的使用非常普遍,并且交易数据也非常巨大,扫描数据库成为序列模式挖掘中的一大瓶颈,多次扫描数据库更是如此。 使用矩阵进行序列模式挖掘相对于AprioriAll和AprioriSome算法而言,只对事务数据库进行一次扫描,根据扫描结果建立由0和1组成的初始矩阵。并且计算机在存储初始矩阵时使用的是0和1这种布尔数据(以位方式存储即可),因此在样本记录较大时通常会占用更少的空间。各阶大序列都只在矩阵上进行运算,支持度的检测只要使用矩阵的最后一个行向量的每个元素值与最小支持度minsup进行比较即可。不用再进行多次数据库扫描,从而减少CPU的I/O操作次数,提高了CPU的利用率,使算法在时间复杂度上有了较大的优势。 实验表明,文中提出的算法是有效、可行的。下一步研究的主要目标是在实际应用中对算法进行进一步测试,使其便于推广应用。 参考文献: [1]　夏　岩,倪世宏,王彦鸿.动态划分序列模式挖掘算法[J].计算机仿真,2009(2):127-130. [2]　陈　安,陈　宁,周龙骧,等.数据挖掘技术及应用[M].北京:科学出版社,2006. [3]　AgrawalR, SrikantR. Fast algorithms formining associationrules[C] ∥In Proceedings of the 24th InternationalConferen-ce on Very Large Databases (VLDB 9' 8). San Francisco,CA:MorganKaufmann,1998:478?499. [4]　夏明波,王晓川,孙永强,等.序列模式挖掘算法研究[J].计算机技术与发展,2006,16(4):4-10. [5]　毛国军,段立娟,王　实,等.数据挖掘原理与算法[M].北京:清华大学出版社,2007. [6]　史　原,鲁汉榕,罗　菁,等.基于规模约简和多支持度的关联规则挖掘[J].计算机工程与设 计, 2006(21): 4105-4107. [7]　袁玉波,杨传胜,黄廷祝,等.数据挖掘与最优化技术及其应用[M].北京:科学出版社, 2007 [8]　高　杰,李绍军,钱　锋.挖掘关联规则AprioriTid算法的改进[J].计算机工程与应用, 2007(7):188-190. [9]　AgrawalR, lmielinksiT, SwamiA.Minig association rulesbe-tween sets of items in large database[C]∥The 1993 ACMSIGMOD Conference·WashingtonDC,USA: [s. n. ],1993. [10]刘洪辉,吴岳芬.用户行为模式挖掘问题的研究[J].计算机技术与发展,2006,16(5):85-92. [11] Aleman-Meza B,Halaschek C,Arpinar IB.Context-awaresemantic association ranking[C] //Cruz I F, Kashyap V,DeckerS, et a.l Proc. of the 1st int’lWorkshop on Semantic Web and Databases. Co- located with VLDB2003. Berlin, Gemlany:Humboldt-University,2003:33-50. [12]张　洋,陈未如,陈珊珊.并发序列模式挖掘方法研究[J].计算机应用,2009(11):3096-3099. · 上标 1 2 3 4 5 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 1 1 2 3 4 5 生成矩阵 转换后的 客户序列 每个整数在6中 出现的次数 4 2 3 2 3 上标 上标 3.5 0 0 0 1 0 1 3 0 1 1 1 0 3 5 1 0 0 1 1 3 1.2 0 1 0 1 0 2 2 0 1 0 1 0 2 1 1 1 1 1 0 4 1 _1234567890.unknown