基于图和矩阵的关联规则挖掘算法

《基于图和矩阵的关联规则挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学硕士学位论文基于图和矩阵的关联规则挖掘算法姓名：汪曦曦申请学位级别：硕士专业：计算机软件与理论指导教师：张世栋20090405山东大学硕士学位论文摘要‘数据库中的知识发现(KnowledgeDiscoveryinDatabases，KDD)是利用计算机自动地从海量信息中提取有用的知识，是一种有效利用信息的新方法，目前已成为数据库领域的研究热点之一。KDD的研究焦点在于数据挖掘。社会的发展进入了网络信息时代，各种形式的数据海量产生，在这些数据的背后隐藏着许多重要的信息，如何从这些数据中找出某种规律，发现有用信息，越来越受到关注。为了适应信

2、息处理新需求和社会发展各方面的迫切需要而发展起来一种新的信息分析技术，这种技术称为数据挖掘。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。目前，数据挖掘的主要技术为关联规则、聚类、粗糙集、神经网络和遗传算法等方面。关联规则是反映一个事务与其他事务之间的相互依存性和关联性，关联规则在数据挖掘领域应用很广泛。关联规则是发现交易数据库中不同商品(项)之间的联系，这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响．发现这样的规则可以应用于商品

3、货架设计、货存安排以及根据购买模式对用户进行分类．最经典的关联规则挖掘算法是Apriori算法。它是I扫lLAgrawal等人于1994年在AIS算法基础上提出的改进算法。Apriori算法使用一种称作“逐层搜索的迭代方法”，核心思想是基于频集理论的一种递推方法，目的是从数据库中挖掘出那些支持度和信任度都不低于给定的最小支持度阈值和最小信任度阈值的关联规则。Apriori算法通常分为两步：1)基于支持度，产生频繁项集：2)基于可信度，产生强关联规则。首先，找出频繁1项集集合，该集合记为￡』厶，三J用于寻找频繁2项集的集合幻，L2用于寻找b，如此

4、下去直到不能找到频繁尼项集厶，找出每个厶需要扫描数据库一次。但Apriori算法存在固有的缺点：(1)由频繁k．1项集进行自连接生成的候选频繁k项集数量巨大。(2)在验证候选频繁k项集的时候需要对整个数据库进行扫描，非常耗时。因此，为了解决以上问题，本文分析了Apriori算法的应用示例，并在此基础上提出了改进Apirori的算法。算法的基本思想是首先将项集表示成矩阵的形山东大学硕士学位论文式，对矩阵进行编码，然后利用编码后的项集生成所需的图，达到剪枝效率提高的目的。寻求频繁项目的有效产生算法是问题的关键。本文通过对所给数据库进行矩阵表示，根据

5、矩阵中项集之间的关系形成图，有效的降低了频繁集的个数，减少了扫描数据库的次数，提高了Apriori算法的效率。关键词：数据库的知识发现；数据挖掘；Apfiofi算法；矩阵表示，图。II山东大学硕士学位论文ABSTRACTKnowledgediscoveryindatabasesistousethecomputertoautomaticallyextractinformationfromthemassofusefulknowledge，whichisalleffectivenewapproacht0theuseofinformation，thed

6、atabasehasnOWbecomeoneofthehotestareasofresearch．KDDresearchfocusisondatamining．Socialdevelopmenthasenteredanetworkoftheinformationage，variousformsofdatageneratedmassinthedatabehindalotofimportantinformation．Sohowtofindoutfromthesedatathatcertainlawsandfoundusefulinformation

7、，moreandmoreattention．Inordert0adaptt0newdemandsanddealwithvariousaspectsofsocialdevelopmentandtheurgentneedtodevelopanewanalysisofinformationtechnology,whichiscalleddatamining．DataMiningisfrommany,notcompleteandthereisnoiseandambiguous，thepracticalapplicationofrandomdata，ex

8、tractingimplicitinoneofthepeopledonotknowinadvance，butarepotentiallyusefuli