一种扩展的否定关联规则形式及其挖掘算法

《一种扩展的否定关联规则形式及其挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、；谥蝣粼鳓溅满逸魏静摘要数据挖掘，又称为数据库中的知识发现(KDD)，出现于“信息丰富而知识贫乏”的二十世纪八十年代后期．之后，倍受关注，并得到广泛研究．关联规则作为数据挖掘中的一种重要模式，在1997年由R．Agrawal等人首次提出【1】，其对应的挖掘算法Apriori[21也被提出．最初提出的关联规则是不带联结词“一”的正关联规则，而且目前大部分工作都集中在正关联规则的研究上．近来，否定关联规则挖掘引起人们的注意，并证明是有用的．1997年，S．Brin等人在(5】中首次提及否定关联．据我们所知，自那以后人们提出了三种有代表性的否定关联

2、规则形式，并提出了三种对应的挖掘方法．但这三种形式都不够一般化，比如它们都不能表达形如“n^书^一(cAd)一eA、，^，(9^h^z)”的规则形式．而且，三种挖掘方法在挖掘能力、精确性和效率上存在一些缺陷。本文提出了一种扩展的否定关联规则形式，并提出了一种相应的挖掘算法AME—NAR以挖掘扩展的否定关联规则．这种扩展形式比以往提出的形式更一般化并具有更强的表达能力，因为以往的形式都是扩展形式的特例．AMENAR是一种基于内存的算法．我们选取一种高度压缩的数据结构Patriciatire将原始数据库存放在内存中．整个挖掘过程在内存中的Patr

3、iciatrie上执行，而且只需扫描两遍数据库．另外，AMENAR算法删除了有冲突的规则和两类冗余规则．我们将AMENAR算法和以往的两种算法运行在两个数据集上．实验结果表明：AMENAll算法在挖掘能力、精确性、空间效率上都优于以前的挖掘方法．而且，当用在稀疏、简单数据库上，当minsup值高到一定程度时，AMENAR算法具有更高的时间效率．我们的工作将把否定关联规则的相关应用推广到更宽的领域．关键词：数据挖掘，否定关联规则，扩展形式，PatriciatireAbstractDatamining，alsocalledknowledgedis

4、coveryindatabases(KDD)，emergedinthesituationof“datarichhutinformationfknowledgelpoor”inthelate1980’S．Sjneethen，ithasattractedagreatdenlofattentionandhasbeenextensivelystudiedAssociationrule，asanimportantpatternindatamining，wasfirstproposedbyR．Agrawaleta1．in1993[1】’andacorre

5、spondingminingalgorithmApriori【2】waspfesentedTheoriginallyproposedassociationruleispositiveassociationrulewithouttheconnective“]11andmostofexistingworkhasconcentratedonpositiveassociations．Recently,miningnegativeassociationruleshasbeengivensomeattentionandhasprovedtobeusefu

6、l．NegativeassociationinassociationruleswasfirstpointedoutbyS．Brineta1．in1997[5]Sincethen，tothebestofourknowledge，threetypicalformsfornegativeassociationrulesandthreecorrespondingminingmethodshavebeenproposed，Butnoneoftheformsisgeneralenoughtorepresentsuchageneralformas“aA_-

7、6^--(c^d)—÷eA一-，A一、(9Ah^z)”，andthecorrespondingminingmethodshavesome[imitationsOnmitringpower，accuracyandefficiencyThisthesisproposesanextendedformfEFlfornegativeassociationrules，andpresentsacorrespondingminingalgorithmfoz’miningextendednegativeassociationrule(AMENAR)．TheEF

8、ismoregeneralandmoreexpressivethanpreviousforms，sincealJpreviousformsfa】1withinspe