MapReduce based parallel attribute reduction in Incomplete Decision Systems

摘要

The scale of the data collected today from applications in the real-world is massive. Sometimes this data can also include missing (incomplete) values that give rise to large-scale incomplete decision systems (IDS). Parallel attribute reduction in big data is an essential preprocessing step for scalable machine learning model construction. Rough set theory has been used as a powerful tool for attribute reduction in complete decision systems (CDS). Furthermore extensions to classical rough set theory have been proposed to deal with IDS. A lot of research works have been done on efficient attribute reduction in IDS using these extensions, but no parallel/distributed approaches have been proposed for attribute reduction in large-scale IDS. Since, owing to its two challenges, large-scale and incompleteness, the processing of large-scale IDS is difficult. To address these challenges, we propose MapReduce based parallel/distributed approaches for attribute reduction in massive IDS. The proposed approaches resolve the challenge of incompleteness with the existing Novel Granular Framework (NGF). And each proposed approach follows a different data partitioning strategy to handle the data sets that are large-scale in terms of number of objects and attributes. One of the proposed approaches adopts an alternative representation of the NGF and uses a horizontal partitioning (division in object space) of the data to the nodes of cluster. Another approach embraces the existing NGF and uses a vertical partitioning (division in attribute space) of the data. Extensive experimental analysis carried out on various data sets with different percentages of incompleteness in the data. The experimental results show that the horizontal partitioning based approach performs well for the massive object space data sets. And the vertical partitioning based approach is relevant and scales well for extremely high dimensional data sets.