您好、欢迎来到现金彩票网!
当前位置:刘伯温四肖中特料 > 推理子句 >

模糊Horn子句规则挖掘算法研究

发布时间:2019-05-20 22:43 来源:未知 编辑:admin

  Vol.38No.9Computer Science Sep2011 模糊 Horn 子句规则挖掘算法研究 (华中科技大学计算机科学与技术学院武汉430074 (中国电子设备系统工程研究所北京100141 模糊关联规则可以用自然语言来表达人类知识,受到数据挖掘与知识发现研究人员的广泛关注。但是,目前 大多数模糊关联规则挖掘方法仍然基于经典关联规则的支持度和可信度测度。 从模糊蕴涵的观点出发,定义 Horn子句规则挖掘算法。 该算法可以分解为 骤。首先,将定量数据库转换为模糊数据库。其次,挖掘模糊数据库中所有支持度不小于指定最小支持度阈值的频繁 项目集。 一旦得到了所有频繁项目集,就可以用一种直接的方法生成所有蕴涵强度不小于指定最小蕴涵强度 模糊Horn子句规则。 关键词 模糊关联规则,模糊 Horn子句规则,支持度,蕴涵强度,定量数据库,模糊数据库 中图法分类号 文献标识码 TP182 ResearchonAlgorithmsforMiningFuzzyHornClauseRulesLIU Dong-bo 1,2 LU Zheng-ding Technology,HuazhongUniversityofScience Technology,Wuhan430074,China) (InstituteofChinaElectronicSystemEngineering ,Beijing100141,China) AbstractFuzzyassociationrulescanbeusedtorepresenthumanknowledgeintermsofnaturallanguage andhasat-tractedagrowingamountofattentionfromthecommunitiesofData Miningand KnowledgeDiscovery.However,so ar,mostapproachesofminingfuzzyassociationrulesarebasedonthemeasuresofsupportandconfidenceforclassicalassociationrules.From theviewpointoffuzzyimplications,fuzzy Hornclauserules,degreeofsupport,implication trengthandsomerelatedconceptsweredefined,andanalgorithmwasproposedforminingfuzzy Hornclauserules. hisalgorithmcanbedecomposedintothreesubprocess.Firstofall,aquantitativedatabaseistransformedintoafuzzyda tabase.Secondly ,allfrequentitemsetsinthefuzzydatabasethatarecontainedinasufficientnumberoftransactionsa- bov ethe minimum supportthresholdareidentified.Onceallfrequentitemsetsareobtained,thedesiredfuzzy Horn clau serulesabovetheminimumimplicationstrengththresholdcanbegeneratedinastraightforwardmanner. Keywords Quantitativedata-bases,Fuzzyda tabases 模糊关联规则可以用自然语言来表达人类 受到DMKD 研究人员的普遍关注。 但是,目前大多数模糊 联规则挖掘算法与经典 Apriori算法相似,仍然沿用支持度 引言 关联规则挖掘是数据挖掘与知识发现(DMKD )领域的重 要研究方向。Agrawal,Imeilinski和 Swami于1993 年首先提 出在大型数据库中挖掘关联规则,并给出了第一个关联规则 挖掘算法 AIS FrequentItemsets),进而发现数据库中不同项目之间的 关联关系,为管理人员确定营销策略、提 AIS算法的思路非常清晰,但执行效率很低。经典 Apri- ri算法是Agrawal和 Srikant提出的基于频繁项目集的递归 方法 有支持度(DegreeofSupport )不小于指定最小支持度阈值的 频繁项目集;( )利用频繁项目集生成可信度(DegreeofCon- fidence )不小于指定最小可信度阈值的关联规则。 可信度测度来挖掘数据库中的模 模糊关联规则可以有不同的解释,而且不同的解释对规则掘方法有很大影响。Hllermeier指出,在模糊关 中直接采用可信度会引发逻辑问题[13] 于是,有些学者提了基于蕴涵的模糊关联规则挖掘方法,例 HllermeierBeringer研究了不同类型基于蕴涵的模糊关联规则及其挖 方法 [13,14] 。Dubois,Hllermeier和 Prade探讨了模糊关联 则支持度和可信度的多种计算方法 [15] ,包括引入模糊蕴涵 子。陈国清、闫鹏等引入了蕴涵度概念,提出了基于蕴涵的 糊关联规则挖掘算法 [16,17] ,并指出通过适当限制t-模算子 模糊蕴涵算子,可以提高数据挖掘效率。 高雅、马琳和戴齐 到稿日期:2010-10-24 返修日期:2011-02-23 高级工程师,主要研究方向为模糊逻辑、数据库、数据挖掘与知识发现、信息系统集成等;卢正鼎教授,主要研究方向为数据库、数 挖掘、信息系统集成、计算机安全等。 出的模糊关联规则挖掘 制t-模算子和模糊蕴涵算子的选择,而通过删除冗余候选规则提高挖掘 作者也从模糊逻辑的观点出发,初步研究了基于蕴涵的模糊逻辑规则发现方法 [19] 传统逻辑程序设计理论采用的是一阶谓词逻辑的 Horn 子句规则集合 [20] 模糊Horn子句逻辑是 [21,22],它提供了一种模糊知识表示及其推理方 则,特别是怎样确定规则的蕴涵强度,是制约模糊 Horn子句逻辑应用的“瓶 模糊关联规则挖掘为解决这一知识获取问题提供了可以借鉴的思路和方法。 Horn子句规则可以看成一种 特殊的模糊关联规则。 本文首先定义模糊 Horn 个记录中的模糊属性值。定义3 中的记录数。定义4 ,前提为B1B2 SUPP=SUPPk 模糊Horn子句规则及其相关概念 传统 Horn子句规则是形如 AB1 B2 IMPk=SUPPk 个记录中的支持度,SUPPk 个记录中的支持度,是模糊 蕴涵算子 [21-24] 的逻辑蕴涵式。其中,规则体 B1 B2 Bn称为前 称为结论[20] 模糊Horn子句规则 [21,22] 与传统 Horn子句规则类似,可 描述为 由于本文选用了模糊蕴涵算子x y=min 所以IMPk =min -B1B2 B1B2 B1B2 时,按照模糊集合论的max-min 这里是一个称为“软 乘”的模糊蕴涵算子( FuzzyIm- plicationOperator 时,模糊Horn子句规则可以转化为传统 Horn 子句 规则。 关于模糊蕴涵算子可参阅文献[23,24],本文在不失一般 性的前提下选用x y=min 假设I={i1,i2 Items)组成的项目集( Itemsets ),其中ik 利用每个模糊属性相 应的隶属函数,可以把定量数据库 相关的模糊Horn子句规则。 定义1 的逻辑表达式,其中 ]称为蕴涵强度。下面定义模糊 Horn 子句规则的两个重要测度:支 和蕴涵强度。定义2 条记录中的支持度为 IMP=IMP 个记录中的蕴涵强度。定义 B1B2 Bn且结论为A -B1B2 Bn为强模糊 Horn 模糊Horn子句规则挖掘算法 模糊 Horn子句规则挖掘算法可分解为3 个处理进程: (1)执行算法1,将 在[0,1]上的模糊数据库 )执行算法2,找出模糊数据库 中所有支持度不小于指定的最小支持度阈值 的频繁项目集; Horn子句规则集,进而找出所有蕴涵强度不小于指定的最小蕴涵强度阈值 的强模糊 Horn子句规则。 算法1DB Trans输入:定量数据库 算法:begin foralltD do//t是数据库D 中的记录 forallikIdo//ik (k=1,2,… ,n)是项目集I 的元素 SUPPk forall与ik相关的模糊属性i kj的隶属函数 (ik)do kj 计算i kj的隶属度 [0,1]insert endforendfor endfor returnD end算法2 是一种与经典 Apriori算法类似的算法,它通过扫 描模糊数据库 Apriori算法的区别主要有以下3 少候选项目集的数量。算法2 Frequent_Itemsets_Gen 输入:模糊数据库 珦,最小支持度阈值α输出:频繁项目集 L={L1 ,L2 算法:begin L1=1 元频繁项目集 //Lk 表示k 元频繁项目集 for{k=2;Lk-1Φ +}do//生成k元候选项目集Ck Ck=candidates_ gen(Lk-1 珟,SUPP(A珦)+SUPP(B 珟)-SUPP(A toLk,deleteC fromCkendif foralltD 中的记录forallC Ckdo 计算t对C 根据定义2计算所有SUPPt 珟)的累加和Σendfor 根据定义3计算C 中的支持度SUPP(C 生成k元频繁项目集 Lk=Lk+{C endforreturnL={L1 ,L2 生成所有频繁项目集end Apriori算法的 Apriori Lk-1)类似,主要包括两个步骤: 假定L1 Lk-1中的频繁项目集, Li 项。如果L1 k-1],则做连接操作 L1 L2 连接条件是L1 )剪枝。连接之后的结果 Ck 是Lk Ck任意子集都是频繁项目集”这一性质可以对 Ck k-1中的候选项目集从 Procedurecandidates_gen(Lk-1 //Lk-1是(k-1)元频繁项目集forallL1Lk-1do forallL k-1ifL1 [1]=L2 L1[2]=L2 L1[k-2]=L2 =L1L2 是候选项目集ifhas_infrequent_subset(C 珟,Lk-1 剪枝操作else addC returnCkProcedurehas_infrequent_subset(C 珟,Lk-1 元候选项目集Lk-1 是(k-1)元频繁项目集 doifS Lk-1thenreturntruereturnfalse 算法3 以频繁项目集 的强模糊Horn子句规则。 算法3 Mining Rules输入:频繁项目集 L={L1 ,L2 ,Lk},最小蕴涵强度阈值 输出:强模糊Horn子句规则集 算法:begin Lkdo 的蕴涵强度ff=implication_strength(A endififfβ ntoΓendif endfor returnΓ end 在算法3中调用了计算规则蕴涵强度的过程implicatio strength(A 根据定义5计算候选规则在 的记录t中的蕴涵强度 IMPt 计算所有IMPendfor 根据定义6计算候选规则在 中的蕴涵强度IMP=Σ returnIMP算法复杂度分析 模糊Horn子句规则挖掘算法分为 通过算法1、算法2 和算法3 实现。 算法1 通过一次扫描数据库,将定量数据库 包含的元素数。算法2用来挖掘模糊数据库D 中所有支持度不小于最小支持度阈值的频繁项目集。 该算法与经典 Apriori算法 目集的长度。需要说明的是,为了减少候选项目集的数量,提 高频繁项目集挖掘 础上,算法2又利用了如下剪枝策略: SUPP 珟)-SUPP(A珦),进一步减少了候选项目集 的数量。 算法3 以频繁项目集为基础生成候选规 句规则。该算法通过选择适当的模糊蕴涵算子,将 描次数减少到k-1次,其计算复杂度为 1)),其中k是最大频繁项目集的长度。 综合上述,由于通常|I ,因此模糊Horn V,GoswamiA.MiningFuzzy Quantitative AssociationRules[J].ExpertSystems,2006,23(4):212-225 BerberogluT,Kaya M.HidingFuzzy Association Rulesin Qu- antitativeData[C] Proceedingsofthe3rdInternationalCon- PervasiveComputing Workshop.IEEE ComputerSociety ,2008:387-392 ChenZuo-liang,Chen Guo-qing.Buildingan AssociationClassi- enceSystems,2008,1(3):262-273[10]SheibaniR,Ebrahimzadeh A.An Algorithm For MiningFuzzy AssociationRules[C] ProceedingsoftheInternational Multi ConferenceofEngineersandComputerScientists.Hong Kong NewswoodLimited,2008:486-490[11]Gupta M,JoshiRC.PrivacyPreservingFuzzyAssociationRules Hidingin Quantitative Data[J].Computer Theoryand Engi- eering,2009,1(4):1793-8201 [12] 霍纬纲,邵秀丽.基于 TD-FP-growth 的模糊关联规则挖掘算法 [J].控制与决策,2009,24(10):1504-1508 [13] HllermeierE.Implication-basedfuzzyassociationrules[C] Procedingsofthe5thEuropeanConferenceonPrinciplesofDataMinin andKnowledeDiscover .2001:241252 结束语本文从模糊蕴涵的观点出发,提出了模糊 Horn [14]HllermeierE,BeringerJ.Miningimplication-basedfuzzyasso- ciationrulesindatabases[C] IntelligentSystemsforInforma- tionProcessing :From Representationto Applications.Elsevier, 2003:137-147 [15]DuboisD,HllermeierE,Prade H.A noteonquality measures forfuzzyassociationrules[C] Proceedingsofthe10thInterna- ionalFuzzySystemsAssociationWorldCongressonFuzzySets andSystems.2003:346-353 [16]ChenGuo-qing ,YanPeng ,KerreE E.Computationallyefficient miningforfuzzyimplication-basedassociationrulesinquantita- ti vedatabases[J].GeneralSystems,2004,33(2/3):163-182 [17] 闫鹏,陈国清.发现基于蕴涵的模糊关联规则[J].模糊系统与数 学,2004,18(z1):279-283 [18] 高雅,马琳,戴齐.模糊关联规则的挖掘算法 学报,2005,40(1):26-29[19] 刘东波,卢正鼎.数据库中的模糊逻辑规则发现[J].计算机工程 与应用,2008,44(26):147-153 [20]KowalskiR A.PredicateLogicasaProgrammingLanguage[C] Proceedingsofthe1974IFIPCongress.NorthHolland,Amster-dam,1974:569-574 [21] 数学,2007,21(2):30-39[22]Liu Dong-bo,LuZheng-ding.TheTheoryofFuzzyLogicPro- fFuzzyInformationandEngineering(ICFIE).AdvancesinSoft Computing40.Springer-Verlag ,2007:534-542 [23]RuanD,KerreEE.Fuzzyimplicationoperatorsandgeneralized fuzzymethodofcases[J].FuzzySetsandSystems,1993,54(1): 23-38 [24]BuiCC,LeCN.SomeFuzzyOperatorswithThresholdandAp- plicationto Fuzzy Association Rulesin Data Mining [J].Ad- vancesinFuzzy Mathematics,2010,5(3):245-262 子句规则挖掘方 句逻辑应用的知识获取“瓶颈”问题提供了一条有效的途径。 该算法结合了模糊 蕴涵概念和 Apriori挖 所有支持度不小于指定最小支持度阈值的频繁项目集。为了 进一步减少候选项目集的数量,提高频繁项目集挖掘效率,算 利用了新的剪枝策略SUPP 基础生成候选规则集,进而挖掘出所有蕴涵强度不小于指定最小蕴涵强度阈值的模糊 Horn 子句规则。 适当的模糊蕴涵算子,减少了数据库扫描次数,提高了关联规则生成效率。 AgrawalR,ImeilinskiT,SwamiA.MiningAssociation Rules BetweenSetsofItemsinLargeDatabases[C] Proceedingsof the1993 ACM SIGMOD.1993:207-216 AgrawalR,SrikantR.FastAlgorithmsforMining Association RulesinLargeDatabases[C] Proceedingsofthe20thInterna- ti onalConferenceonVeryLargeDataBases.1994:487-499 CuberoJC,MedinaJM,PonsO,etal.RulesDiscoveryinFuzzyRelationalDatabases[C] Proceedingsofthe3rdInternational Symposiumon Uncertainty Modellingand Analysis.1995:414- 419 ChienBC,LinZ L,Hong P.AnEfficientClustering Algo- ithmforMining Fuzzy Quantitative Association Rules[C] roceedingsoftheJoint9thIFSAWorld Congressand 20th NAFIPSInternationalConference.2001:1306-1311 KayaM,AlhajjR.Genetic Algorithm Based Frameworkfor MiningFuzzy AssociationsRules[J].FuzzySetsandSystems,

http://mojdzwonek.com/tuiliziju/43.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有