基于分治法的属性核计算方法  

Algorithm of computing attribute core based on divide and conquer method

作　　者：王俊祥[1] 胡峰[2] 

机构地区：[1]重庆文理学院基础学院,重庆402168 [2]重庆邮电学院计算机科学与技术研究所,重庆400065

出　　处：《计算机工程与设计》2008年第23期6076-6078,6097,共4页Computer Engineering and Design

摘　　要：属性核计算是Rough集理论中的一个重要研究内容。将分治法的思想溶入Rough集算法中,在决策表的属性集上,利用分治法对论域进行划分,给出了基于分治法的正区域计算方法,其时间复杂度分别为×;在此基础上,给出了基于分治法的属性核计算方法,其时间复杂度为×2。两个算法的时间复杂度都保持了与O(|U|×|C|)的线性关系。实验结果表明:文中的算法不仅能高效地处理UCI数据集,且能适合大数据集的处理。The computation of attribute core is an important research part in rough set theory. The idea of divide and conquer is melted into algorithms ofrough set. Two novel algorithras based on divide and conquer method are developed. Oneisthealgorithmofcomputing positive region of decision table, whose time complexity is O（｜U｜×｜C｜）. The other is the algorithm of computing attribute core of decision table, whose time complexity is O（｜U｜×｜C｜^2）. The two algorithms proposed both keep a linear relation with ｜U｜. Simulation experimental results demonstrate that the algorithm is not only process UCI data set quickly, but also is adapted to process efficiently huge data.

关 键 词：粗集 分治 正区域 属性核 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]