Efficient parallel boolean matrix based algorithms for computing composite rough set approximations

详细信息    查看全文

• 作者：Junbo Zhang^a ; ^b ; ^{jbzhang@my.swjtu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; ^{jbzhang@cs.gsu.edu" class="auth_mail" title="E-mail the corresponding author} ; Yun Zhu^b ; ^{yzhu7@student.gsu.edu" class="auth_mail" title="E-mail the corresponding author} ; Yi Pan^b ; ^{pan@cs.gsu.edu" class="auth_mail" title="E-mail the corresponding author} ; Tianrui Li ; ^a ; ^{trli@swjtu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; ^{trli30@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Composite rough sets ; Boolean matrix ; CUDA ; Multi-GPU
• 刊名：Information Sciences
• 出版年：2016
• 出版时间：1 February 2016
• 年：2016
• 卷：329
• 期：Complete
• 页码：287-302
• 全文大小：1481 K

文摘

In information systems, there may exist multiple different types of attributes like categorical attributes, numerical attributes, set-valued attributes, interval-valued attributes, missing attributes, etc. Such information systems are called as composite information systems. To process such attributes with rough set theory, composite rough set model and corresponding matrix methods were introduced in our previous study. Calculation of rough set approximations of a concept is the key step for rule acquisition and attribute reduction in rough set based methods. To accelerate the computation process of rough set approximations, this paper first presents the boolean matrix representation of the lower and upper approximations in the composite information system, then designs a parallel method for computing approximations based on matrix, and implements it on Multi-GPU. The experiments on data sets from UCI and user-defined data sets show that the proposed method can accelerate the computation process efficiently. The Multi-GPU implementation achieves up to a speedup of 334.9 over the CPU implementation.