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

《云计算环境下知识约简算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３４卷第１２期计算机学报Ｖｏｌ．３４Ｎｏ．１２２０１１年１２月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＤｅｃ．２０１１云计算环境下知识约简算法钱进１），２），３）苗夺谦１），３）张泽华１），３）１）（同济大学计算机科学与技术系上海２０１８０４）２）（江苏技术师范学院计算机工程学院江苏常州２１３００１）３）（同济大学嵌入式系统与服务计算教育部重点实验室上海２０１８０４）摘要知识约简是粗糙集理论的重要研究内容之一．经典的知识约简算法是假设所有数据一次性装入内存中，这显然不适合处理海量数据．为此，从属性（集）的可辨识性和不可辨识性出发，给出了

2、可辨识和不可辨识对象对的概念及其性质，并阐述了它们与差别矩阵的关系．利用ＭａｐＲｅｄｕｃｅ设计了并行计算等价类的方法，提出了面向大规模数据的数据并行知识约简算法，讨论并实现了３种并行策略．最后，通过实验表明了云计算环境下知识约简算法是有效可行的，具有较好的可扩展性．关键词云计算；粗糙集；知识约简；数据并行；ＭａｐＲｅｄｕｃｅ中图法分类号ＴＰ３１１犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１１．０２３３２犓狀狅狑犾犲犱犵犲犚犲犱狌犮狋犻狅狀犃犾犵狅狉犻狋犺犿狊犻狀犆犾狅狌犱犆狅犿狆狌狋犻狀犵ＱＩＡＮＪｉｎ１），２），３）ＭＩＡＯＤｕｏＱｉａ

3、ｎ１），３）ＺＨＡＮＧＺｅＨｕａ１），３）１）（犇犲狆犪狉狋犿犲狀狋狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犜狅狀犵犼犻犝狀犻狏犲狉狊犻狋狔，犛犺犪狀犵犺犪犻２０１８０４）２）（犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉犈狀犵犻狀犲犲狉犻狀犵，犑犻犪狀犵狊狌犜犲犪犮犺犲狉狊犝狀犻狏犲狉狊犻狋狔狅犳犜犲犮犺狀狅犾狅犵狔，犆犺犪狀犵狕犺狅狌，犑犻犪狀犵狊狌２１３００１）３）（犓犲狔犔犪犫狅狉犪狋狅狉狔狅犳犈犿犫犲犱犱犲犱犛狔狊狋犲犿牔犛犲狉狏犻犮犲犆狅犿狆狌狋犻狀犵，犕犻狀犻狊狋狉狔狅犳犈犱狌犮犪狋犻狅狀狅犳犆犺犻狀犪，犜狅狀犵犼犻犝狀犻

4、狏犲狉狊犻狋狔，犛犺犪狀犵犺犪犻２０１８０４）犃犫狊狋狉犪犮狋Ｋｎｏｗｌｅｄｇｅｒｅｄｕｃｔｉｏｎｉｓｏｎｅｏｆｔｈｅｉｍｐｏｒｔａｎｔｒｅｓｅａｒｃｈｉｓｓｕｅｓｉｎｒｏｕｇｈｓｅｔｔｈｅｏｒｙ．Ｃｌａｓｓｉｃａｌｋｎｏｗｌｅｄｇｅｒｅｄｕｃｔｉｏｎａｌｇｏｒｉｔｈｍｓａｓｓｕｍｅａｌｌｔｈｅｄａｔａｓｅｔｓｃａｎｂｅｌｏａｄｅｄｉｎｔｏｔｈｅｍａｉｎｍｅｍｏｒｙ，ｗｈｉｃｈａｒｅｉｎｆｅａｓｉｂｌｅｆｏｒｌａｒｇｅｓｃａｌｅｄａｔａｓｅｔｓ．Ｍａｓｓｉｖｅｄａｔａｗｉｔｈｈｉｇｈｄｉｍｅｎｓｉｏｎｓｍａｋｅｓａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉ

5、ｏｎａｃｈａｌｌｅｎｇｉｎｇｔａｓｋ．Ｔｏｔｈｉｓｅｎｄ，ｔｈｅｃｏｎｃｅｐｔｓａｎｄｐｒｏｐｅｒｔｉｅｓｏｆｄｉｓｃｅｒｎｉｂｉｌｉｔｙａｎｄｉｎｄｉｓｃｅｒｎｉｂｉｌｉｔｙｏｂｊｅｃｔｐａｉｒｓａｒｅｇｉｖｅｎｉｎｔｅｒｍｓｏｆｔｈｅｄｉｓｃｅｒｎｉｂｉｌｉｔｙａｎｄｉｎｄｉｓｃｅｒｎｉｂｉｌｉｔｙｏｆｔｈｅａｔｔｒｉｂｕｔｅ（ｓ）．Ｔｈｅｒｅｌａｔｉｏｎｓｈｉｐｂｅｔｗｅｅｎｄｉｓｃｅｒｎｉｂｉｌｉｔｙｍａｔｒｉｘａｎｄｔｈｅｍｉｓｉｌｌｕｓｔｒａｔｅｄｉｎｄｅｔａｉｌ．Ｔｈｅｎ，ａｎａｌｇｏｒｉｔｈｍｏｆｃｏｍｐｕｔｉｎｇｅｑｕｉｖａｌ

6、ｅｎｃｅｃｌａｓｓｅｓｉｓｄｅｓｉｇｎｅｄｆｏｒｌａｒｇｅｓｃａｌｅｄａｔａｉｎｄａｔａｐａｒａｌｌｅｌ，ａｎｄｔｈｅｃｏｒｒｅｓｐｏｎｄｉｎｇｋｎｏｗｌｅｄｇｅｒｅｄｕｃｔｉｏｎａｌｇｏｒｉｔｈｍｓａｒｅｐｒｏｐｏｓｅｄｉｎｃｌｏｕｄｃｏｍｐｕｔｉｎｇ．Ｆｉｎａｌｌｙ，ｔｈｒｅｅｐａｒａｌｌｅｌｉｓｍｓｔｒａｔｅｇｉｅｓａｒｅｉｍｐｌｅｍｅｎｔｅｄａｎｄｄｉｓｃｕｓｓｅｄ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｄｅｍｏｎｓｔｒａｔｅｔｈａｔｋｎｏｗｌｅｄｇｅｒｅｄｕｃｔｉｏｎａｌｇｏｒｉｔｈｍｓｉｎｃｌｏｕｄｃｏｍｐｕｔｉｎｇｃａｎｓｃａ

7、ｌｅｗｅｌｌａｎｄｅｆｆｉｃｉｅｎｔｌｙｐｒｏｃｅｓｓｍａｓｓｉｖｅｄａｔａｓｅｔｓｏｎｃｏｍｍｏｄｉｔｙｃｏｍｐｕｔｅｒｓ．犓犲狔狑狅狉犱狊ｃｌｏｕｄｃｏｍｐｕｔｉｎｇ；ｒｏｕｇｈｓｅｔ；ｋｎｏｗｌｅｄｇｅｒｅｄｕｃｔｉｏｎ；ｄａｔａｐａｒａｌｌｅｌ；ＭａｐＲｅｄｕｃｅ用，各行各业已经积累了大规模数据．大量数据背后１引言隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析．粗糙集理论（ＲｏｕｇｈＳｅｔＴｈｅｏｒｙ）［１］随着数据库技术的发展和信息系统的广泛使是一种新的研究不精确、不确定性知识的数据分析收稿日期：２０１１０３３０；最终修改稿

8、收到日期：２０１１１０３１．本课题得到国家自然科学基金（６０９７００６１，６１０７５０５６，６１１０３０６７）、中央高