分布式概念格的属性约简研究.doc

《分布式概念格的属性约简研究.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分布式概念格的属性约简研究杨彬徐宝文(东南大学计算机科学与工程学院南京210096)(moni.y.b(^；gmail・com)DistributiveReductionofAttributesinConceptLatticeYangBinandXuBaowcn(SchtHtlofComputerSciencearidEngineering9SoutheastUniversity,Nanjing210096)AbstractAttributereductionisoneofthekeyproblemsinformalconceptanalysis.Afewappro

2、acheshavebeenproposedbuttheyareonlyapplicabletoformalcontextinanon-distributedenvironment.Withthewideapplicationofdistributeddatastorageandprocessing,itisnecessarytodevelopamethodtoadapttothisenvironment.Toaddressthisproblem,thecharacterizationsofdifferentkindsofattributesareprovidedfr

3、omthepointofviewofglobalcontextandlocalcontext.Thenotionofsupersetandconsistentsetareintroducedtodeterminewhetheranattributeisreducibleinaglobalcontext.Thedeterminanttheoremofattributereductionsisderivedbasedoncoreattributesanddispensableattributes.Basedontheseresults,twoalgorithmsared

4、esignedtocomputeattributereductionsofcontextinadistributedenvironment.Thefirstalgorithm♦DRCI八determinesattributereductionsofglobalcontext.Thelocalreductionscanbecomputedbyusingtheexistingapproaches.Thesecondalgorithm,AT)S(：I八determinesthesupersetsandallminimalconsistentsetsfortheattrib

5、utesgivenbyacontext.Thisinformationisrequiredbythefirstalgorithm.Theoryanalysisandexperimentalresultsshowthefeasibilityandeffectivenessofthetwoalgorithms.Keywordsconceptlattice；formalcontext；distributedenvironment；attributereduction；attributecharacterization摘要概念格的属性约简是形式化概念分析理论的重要研究内容之

6、一.传统的格属性约简方法主要是针对非分布式环境下单个形式背景的，而随着数据分布存储和处理的广泛应用，研究基于分布式环境下概念格的属性约简具有重要的意义.为此，提出属性的超集和确定集的概念，刻画了形式背景中不同类型属性的局部特征与全局特征，推导出属性约简的判定定理；在此基础上，给出计算分布式环境下概念格属性约简的ADSCL和DRCL算法.ADSCL算法用于计算属性的超集和最小确定集，这些约简信息将作为DRCL算法的输入，以计算得到全局形式背景的约简.理论分析和实验结果表明，该算法是有效可行的.关键词概念格；形式背景；分布式环境；属性约简；属性特征化中图法分类号TP18

7、形式概念分析是以数学化的概念和概念层次结80年代提出形式概念分析以来②，形式概念分析及构为基础的应用数学领域门.口Wille于20世纪其表示工具——概念格——已被深入研究并取得了收稿日期：2007-11-23’修回日期:2008-0325基金项目：国家杰出青年科学基金项目(60425206)；国家自然科学基金项目(60373066)；江苏省自然科学基金项目(BK2OO6O94)许多重要成來.被认为是知识表示和知识处理的一种有效工具，在数据管理、信息检索、机器学习和软件工程等领域得到了广泛的应用"］.概念格的属性约简是形式概念分析的重要研究内容之一〔岂所谓概念格的