云计算环境下知识约简算法  

Knowledge Reduction Algorithms in Cloud Computing

作　　者：钱进 苗夺谦[1,3] 张泽华[1,3] 

机构地区：[1]同济大学计算机科学与技术系,上海201804 [2]江苏技术师范学院计算机工程学院,江苏常州213001 [3]同济大学嵌入式系统与服务计算教育部重点实验室,上海201804

出　　处：《计算机学报》2011年第12期2332-2343,共12页Chinese Journal of Computers

基　　金：国家自然科学基金(60970061;61075056;61103067);中央高校基本科研业务费专项资金;江苏省属高校自然科学资金项目(09KJD520004)资助~~

摘　　要：知识约简是粗糙集理论的重要研究内容之一.经典的知识约简算法是假设所有数据一次性装入内存中,这显然不适合处理海量数据.为此,从属性(集)的可辨识性和不可辨识性出发,给出了可辨识和不可辨识对象对的概念及其性质,并阐述了它们与差别矩阵的关系.利用MapReduce设计了并行计算等价类的方法,提出了面向大规模数据的数据并行知识约简算法,讨论并实现了3种并行策略.最后,通过实验表明了云计算环境下知识约简算法是有效可行的,具有较好的可扩展性.Knowledge reduction is one of the important research issues in rough set theory.Classical knowledge reduction algorithms assume all the datasets can be loaded into the main memory,which are infeasible for large-scale datasets.Massive data with high dimensions makes attribute reduction a challenging task.To this end,the concepts and properties of discernibility and indiscernibility object pairs are given in terms of the discernibility and indiscernibility of the attribute（s）.The relationship between discernibility matrix and them is illustrated in detail.Then,an algorithm of computing equivalence classes is designed for large-scale data in data parallel,and the corresponding knowledge reduction algorithms are proposed in cloud computing.Finally,three parallelism strategies are implemented and discussed.The experimental results demonstrate that knowledge reduction algorithms in cloud computing can scale well and efficiently process massive datasets on commodity computers.

关 键 词：云计算 粗糙集 知识约简 数据并行 MAPREDUCE 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]