Researches On Quick Algorithms For Positive Region Attribute Reduction: A Multi-scaled Granular Perspective

Rough set theory was proposed by Polish scholar professor Pawlak in 1982.It is an efficient soft computing method for analyzing and processing imprecise,uncertain and inconsistent information.Attribute reduction is the most important part of rough set theory,which has attracted wide attention of many scholars.Positive region reduction ensures that the positive region of the information system remains unchanged before and after reduction,thus keeping the deterministic rules unchanged.Due to the explosion of massive data,people's demand for timeliness of information has become more and more intense.Existing heuristic positive domain reduction algorithms face inefficiency and other problems.Therefore,many scholars have done a lot of in-depth research on it.The efficiency of heuristic attribute reduction algorithm is mainly affected by object scale and attribute scale of data set.In rough set theory,a cluster of information granules in a data set can be obtained by granulating specific binary relation information.The information in each information granule is indistinguishable.Not only that,but also the attributes with the same characteristics can be regarded as an information granule.Starting from the object scale and attribute scale,the information granule is zoomed out and zoomed in without affecting the reduction results,which reduces the dimension of the data set and improves the efficiency of the algorithm.From the point of view of multi-scale granulation,this paper optimizes heuristic positive region reduction algorithm from two aspects: object scale granulation and attribute scale granulation.The fast positive region reduction algorithm of set-valued information system,a fast positive region reduction algorithm of multi-scale attribute granulation strategy and a fast positive region reduction algorithm of incomplete information system are proposed respectively.The main research work is as follows:(1)A quick positive reduction algorithm based on the heuristic method is proposed to solve the problem of the efficiency of the set-valued positive reduction algorithm under the large-scale data.By studying the influence of attributes and objects on the efficiency of algorithm in the process of reduction,the relevant definitions of attribute independence and attribute importance isotonicity are introduced in the set-valued information system,and the relevant theorems,fast algorithm and practical examples to improve the efficiency of the algorithm are introduced.Finally,the experimental results show the proposed methods are efficient and effective and the efficiency of the proposed algorithm is better than the original algorithm.(2)A quick positive reduction algorithm based on multi-scale attribute granularity strategy is proposed to solve the problem of running efficiency of positive reduction algorithm under the large-scale data.By studying the relationship of attributes granularity sets relative to the positive region generated,the definition of multi-scale attribute granularity is introduced.It is proposed that the algorithm does not need the set of core attribute sets.Each iteration selects the multi-scale attribute granularity to the candidate attribute set,making the classification ability of candidate attribute sets tends to classify the original features and the number of iterations decreases.At last,the algorithm eliminates the redundancy process and guarantees the correctness of the reduction results.Finally,the efficiency of the proposed algorithm is compared and analyzed by experiments,and the efficiency of the proposed algorithm is verified.(3)A fast positive region reduction algorithm based on incomplete information system is proposed to improve the efficiency of positive region reduction algorithm in large-scale data sets.This algorithm breaks the idea of traditional heuristic algorithm.In the process of heuristic search,the relationship between positive regions is generated by judging conditional attributes and decision attributes.Add one or two attributes to the candidate attribute set,so that the overall iteration number of the algorithm decreases.Moreover,the algorithm does not need to find the set of core attributes,and deletes the positive fields generated by the candidate attributes in each iteration process,so the efficiency of the algorithm is effectively improved.Finally,the experimental results show that the proposed algorithm is more efficient by comparing and analyzing the running time with the existing efficient algorithms.