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

《基于矩阵算法的序列模式挖掘研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于矩阵算法的序列模式挖掘研究甄慧玲(2011111286)理学院摘要:序列模式挖掘中几种算法的缺点:都要进行多次扫描数据库,CPU要进行多次I/O操作。这成为序列挖掘中的一人瓶颈，使得算法在实际应用中的效率不高。文中提出一种矩阵算法，即在一次扫描数据库时,根据扫描数据建立由0和1组成的事务矩阵。接下来的大序列、序列模式等都是通过矩阵的列向量对应元素的相乘运算和简单的加法运算而得到。从而使算法得到进一步优化,提高了CPU的使用率，解决了序列挖掘中的瓶颈问题。本算法通过大量的数据实验，证明了算法确实有效地优化了算法

2、的时间复杂度。关键词:序列模式挖掘：序列模式；人序列；矩阵算法；连接运算一、引言随着佶息技术迅速发展，数据库的规模不断扩大，从而产生了大量的数据。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利川这些数据。为给决策者捉供一个统一的全局视角，在许多领域建立了数据仓库。但大量的数据往往使人们无法辨别隐藏在其中的能对决策提供支持的信息，而传统的杏询、报表工具无法满足挖掘这些信息的需求。因此，需要一种新的数据分析技术处理大量数据，并从中抽取有价值的潜在知识，数据挖掘(DntaMinin

3、g)技术由此应运而生。数据挖掘技术也正是伴随着数据仓库技术的发展而逐步完善起来的。数据挖掘是指从数据集合中白动抽取隐藏在数据中的那些有用信息的非平凡过程，这些信息的表现形式为：规则、概念、规律及模式等。它可帮助决策者分析历史数据及当前数据,并从中发现隐藏的关系和模式，进阳预测未来可能发牛的行为。数据挖掘的过程也叫知识发现的过程，它是一门涉及而很广的交叉性新兴学科，涉及到数据库、人工智能、数理统计、可视化、并行计算等领域。数据挖掘是一种新的信息处理技术，其主要特点是对数据廉屮的人量数据进行抽取、转换、分析和其他模型

4、化处理，并从屮提取辅助决策的关键性数据。数据挖掘是KDD(KnowledgeDiscoveryinDatabase)中的重要技术，它并不是用规范的数据库杳询语言(如SQL)进行杏询，而是对杏询的内容进行模式的总结和内在规律的搜索。传统的杳询和报表处理只是得到事件发生的结杲，并没有深入研究发生的原因，而数据挖掘则主要了解发生的原因，并冃以一定的置信度对未来进行预测，川來为决策行为提供有利的支持。随着计算机技术的不断发展，信息量的不断增加，人们对数据挖掘技术不断重视，而数据挖掘的研究本身也融合了多个不同学科领域的技术

5、与成果，使得目前的数据挖掘方法表多种多样的形式。从统计分析类的角度来说，统计分析技术中使用的数据挖掘模型有分析和非线形分析、冋归分析、逻辑冋归分析、单变量分析、多变量分析、吋间序列、最近序列分析、最近邻算法和聚类分析等方法。利用这些技术可以检査那些异常形数据，然后，利用各种统计模型和数学模型解释这些数据，解禅隐藏在这些数据背后场规律和商业机会。知识发现类数据挖掘技术是一种与统计分析类数据挖掘技术完全的挖掘技术，包括人工神经元网络、支持向量机、决策树、遗传算法、粗糙集、规则利关联顺序等。序列模式挖掘乂称序列挖掘［1

6、］,主要是找出序列数据丿牟小那些在序列集合中出现频率超过最小支持度［2］或者川户指定的最小支持阈值［2］的子序列。其口的是想通过在含有交易时间属性的客户交易数据库中发现频繁项目序列，通过频繁项目序列找出一•定的时间段内客八购买活动的规律［2,3］。序列模式的挖掘主要是基于人项集［4］的挖掘，主要思想是：首先，把交易数据库转换为以幺户序列为记录的数据库;其次，利用大项集搜索算法计算大项集，作为一阶大序列;再次，以一阶大序列为基础,依次搜索所有阶的大序列;最后,从大序列中删除子序列,最终得到序列模式。从以上过程可以看

7、出，序列模式挖掘--般分为五个步骤［2,5］,它们分别是排序阶段［5］、大项集阶段［5］、转换阶段［5］、序列阶段［5］、选最大阶段［5］。序列模式挖掘主要来源于关联规则挖掘［3,6,7］,是关联规则应用的延伸。在关联规则挖掘Apriori算法［2,8］的基础上，由Agrawal和Strikant［2］等人提出几种序列模式的挖掘算法，即AprioriAll［5］、AprioriSome⑸及DynamicSome［5］o但这几种算法都耍进行多次扫描数据库，扫描数据库便成为序列模式挖掘中的一人瓶颈，多次扫描数据库更是

8、如此。基于种种対比，本文认为矩阵是瓶颈问题的克星。文中提出的矩阵算法主要是解决多次扫描数据廉的瓶颈问题。在介绍矩阵算法之前先简要介绍Aprio-riAll算法和AprioriSome算法以便进行对比。二、基本概念及示例数据库2.1基本概念基本概念如下：序列:序列是项集的一个非空有序集合，也就是一个集合的集合，记为{si,s2,・・・sn},其中si是一个项的集合,表示在同