基于概念格的关联规则挖掘

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

1、华中师范大学硕士学位论文基于概念格的关联规则挖掘姓名：胡睿申请学位级别：硕士专业：电路与系统指导教师：朱绍文2003.5.1⑧硕士学位论文MASIER’S1IIESi，摘要信息时代，数据库积累了海量数据，为从海量数据中发现有用信息，知识发现成为目前紧迫的研究方向。关联规则挖掘是知识发现中应用最广泛，研究最多的任务之一。挖掘关联规则的首要任务则是找到频繁项目集。目前找出频繁项目集的很多算法主要可以分为如下三类：一、以Aprori算法为代表的层次算法，如Mannila的算法，Partition算法，

2、DIC算法。这类算法的主要思想是直接对子集格进行修剪，从尺寸为l的项目集开始，逐层向上对数据库进行遍历，直到找到最大频繁项目集为止，它是目前应用最多的算法，但是对大密度和高关联度的数据库进行采掘时，运行时间将以指数倍增加，运行效率不高，效果不好；二、通过找出最大频繁项目集的方法来得到频繁项目集的算法，如Pincer-Search算法．MaxClique算法和MaxMiner算法。这种算法在一定程度上节省了运行时间和空间消耗，但是由于它的理论基础本身存在的缺陷，所以在生成关联规则时，存在信息丢失的

3、情况：三通过提取频繁封闭项目集来提取频繁项目集的算法，如基于概念格(Galoris格)和J下则概念分析FCA的概念格挖掘算法。这类算法的主要思想是先找到封闭的频繁项目集，然后从中得到全部的频繁项目集。由于将发现频繁项目集的问题转化成为发现封闭概念的问题，该算法减少了空问和时间消耗，尤其是在大密度高关联度的数据库情况下，因为封闭概念的数目大大少于所有频繁项目集的数目，该算法的效果明显优于Apriori算法。同时又能够在没有丢失信息的情况下将关联规则无冗余的挖掘出来。本文通过对几个基于概念格的封闭频

4、繁项目集挖掘算法的时间复杂度的分析，总结出决定此类算法运行效率的因素，即数据库密度和关联度。在数据库关联度小的时候，由于封闭频繁项目集的数目和频繁项目集总数相差不大，使⑧篙姜慧。用概念格进行关联规则挖掘的效果反而不比Apriori类算法更好，某些情况甚至更差。据此提出了一种基于数据库关联度的判断选择算法RelationDesider．能够在对数据库进行关联规则发现之前，通过对数据库的一次先验性遍历，得到数据关联度情况，并根据该情况来选择合适的算法，当数据库关联度高于域值时，采用基于概念格的关联规

5、则挖掘算法，当关联度低于该域值时，采用Apriori算法。最后，本文介绍了基于概念格的关联规则提取，并主要比较了基于概念格的关联规则提取和一般方法提取关联规则的区别。关键词：数据库KDD数据采掘关联规则概念格nAbstractInthisinformationage，databasesarepilinguphugevolumedata．Forgettingusefulinformationfromthis“datasea'’，knowledgediscoveryindatabase(KDD)em

6、ergesasthemosthotresearchfield．Theassociationrule·miningproblemisoneofthemoststudiedandthemostpopularKDDtasks．ThechieftaskofassociationrulesminingistOfindthefrequentitemsets．Thealgorithmsforfindingfrequentitemsetscanbesortasthreegroups：1．Levelwisealg

7、orithms．Apriorialgorithmisamosttypicalalgorithm．OtherthiskindofalgorithmsisMarmila，Partion，DIC，andSOon．Themainideaofthiskindofalgorithmsistoprunethesub-itemsetslattice．Itisstartedfromthe1-sizeitemsets，passingthedatabaselevelbylevel，andstoppedwhenthel

8、argestfrequentitemsetswerefound．Itisamostpopularmethodtofindfrequentitemsets．However’theperformtimewillincreaseinmagnitudelevel，andtheperformefficiencyandeffectwor／’tbeverygood．2．Algorithmsthatthefrequentitemsetsarefoundbyfindingthelargestfrequentite