分布式粗糙集核增量式更新算法

《分布式粗糙集核增量式更新算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4部分信号与数据处理分布式粗糙集核增量式更新算法吴永芬1张健2赵新然3(1解放军理工大学指挥自动化学院计算机系，江苏南京210007；2三江学院计算机基础部，江苏南京210012：3防化指挥工程学院教保处北京)摘要：目前已有很多核的增量式求解算法，但分布式环境下核的增量求解的报导却不多．因此提出一种分布式环境下，多工作站点动态增加数据的全局核更新算法。鉴于网络传榆代价较高，该算法在更新核时，仅需传送各差别矩阵被修改的一行一列内容，因而可有效提高全局核的更新效率．算法分析结果表明，本文的算法是有效可行的．关键

2、词：粗糙集；差别矩阵；多工作站点；核；增量式更新AnIncrementalUpdatingAlgorithmforComputingCoreinDistributedEnvironmentWUYong-fenlZHANGJian：ZHAOXin-ran3(1InstituteofCommandAutomation，PLAUniv．ofSci．&Tech．，N删ing210097，China；2DepartmentofComputerElementaryTraining，saIliiangUnivcrsty,N

3、aIljhag210012，China3DepartmentofTeachingLogistics，CommandingandEngineeringInstituteofChemicalDefence)Abstract：Atpresent，manyalgorithmswereproposedforincrementalupdatingcomputationofacore．However，fewworkhavebeenstudiedindistributedenvironmenLThus，anincrement

4、alupdatingalgorithmisproposedforcomputingaglobalattributecoreofmuliti—workingstationinthecaseofinserting．Onlyarowandcolumnneedtobemodifiedwhenupdatingthelocalindecernibilitymatrix，80theupdatingefficiencyofaglobalattributecoreisremarkablyimproved．Algodthmana

5、lysisresultsshowthealgorithmiseffectiveandefficient．Keywords：roughset；discemibilitymatrix；multi—workingstation；core；incrementalupdating1引言波兰数学家Z．Pawlak80年代初提出的RoughSet(粗糙集)是一种新的处理不精确、不·249·2009年中国信息技术应用学术研讨会论文集完全与不相容知识的数学理论【l】，该理论在机器学习、数据挖掘及模式识别等多个领域得到了广泛的应

6、用∞l。一般情况下，求核是粗糙集属性约简的关键步骤【4】，研究高效的求核算法十分有价值。在核求解问题上已经有大量的研究成果，但是大多是关于单决策表核的求解㈣。然而随着数据库技术和网络技术的快速发展，越来越多工作在分布式环境下进行。因此，探讨分布式环境下的核求解【lo】也变得十分有意义。在分布式环境下，由于数据的动态增加，导致各工作站点的差别矩阵产生变化，若只是简单地将所有工作站点的差别矩阵汇总到一个站点进行求核，必导致巨大的网络通信代价。因此，本文提出一种高效的分布式环境下，动态增加数据的全局核更新算法。鉴于

7、网络传输代价较高，该算法在更新核时，无需传送各工作站点的全部差别矩阵数据，仅需传送各差别矩阵中被修改的一行一列内容，因而可有效提高全局核的更新效率。算法分析结果表明，本文的算法是有效可行的。2相关概念在本文的模型中，多个决策表是按列划分的。设有t个站点Sl，s2，．．．，S。相应的局部决策表为DTl，DT21--,，DTt，各站点的属性列互不相交，将各站点的子决策表合并为～个全局决策表后，只是列进行拼合，行数不变。相当于将一个全局决策表，按列划分存放到各个站点。若U中的两个不同的对象X和Y在条件属性集C上具有

8、相同的条件属性值而具有不同的决策属性，则称X和Y为垒厨不一霉它力够否则称X和Y为至淘’·碧既撬若在站点si，U中的两个不同的对象X和Y在站点Si的条件属性集Ci上具有相同的条件属性而具有不同的分类，则称X和Y为局彩不÷黝；否则称x和Y为厨廖一碧瑚吼定义113J．设xsU为论域的一个子集，P￡C，X的关于P的垒伺烈Z钟为￡x(C)={xeU：[zb∈X)，其中，[工b={yEUlVaEp,舷，a)=坟