Study On The Theory And Method Of Scale Selection And Reduction In Multi-Scale Decision Systems

With the acceleration of world digitization,multi-scale data has become an important data resource for knowledge discovery.Scale selection and attribute reduction are the core content of multi-scale rough set.The aim is to remove redundant attributes and select the coarsest scale while keeping the classification ability unchanged,so as to obtain a more concise knowledge representation.However,due to the combinatorial explosion of scales,how to carry out scale selection and attribute reduction efficiently and completely is an urgent issue in complex multi-scale data mining,mainly reflected in the following two aspects.On one hand,in the static environment,the existing methods always select the scale of attributes first and then reduce attributes.The serial processing method has two defects: the first step of serial processing,i.e.,optimal scale combination selection,has high time and space complexity.At the same time,the serial processing could not obtain complete results.On the other hand,in the dynamic environment,rough set usually adopts the sequential three-way decision model to construct a multi-granularity hierarchical space.However,the existing sequential three-way decision models are carried based on the objects,and there are some limitations such as losing the structure information of granules,the large number of subjective parameters and decision conflicts.Therefore,how to avoid decision conflicts,construct a data-driven sequential three-way decision model based on the granules,and apply it to scale selection and reduction of attributes,are the difficult problems of dynamic multi-scale data processing.Therefore,this thesis first introduces the sequential three-way decision model into the optimal scale selection,and establishes the sequential three-way decision model of the scale combination family to reduce its time complexity;Second,the concept of “scale reduction” is introduced to deal with scale selection and attribute reduction simultaneously,and an efficient scale reduction strategy is proposed to reduce the time and space complexity of the algorithm in the static environment;Finally,the basic theoretical framework of α-granular sequential three-way decision is established for dynamic environment,and applied to scale reduction.Specifically,the main contributions of this thesis are as follows:(1)Aiming at the problem of high time consumption in traditional optimal scale combination selection method,an optimal scale combination selection algorithm based on sequential three-way decision is proposed,which significantly reduces the time complexity of the traditional algorithms.First,a fast search method for local optimal scale combination is designed.Second,based on these local optimal scale combinations,a sequential three-way decision model of the scale combination family is established.It is proved that the local optimal scale combination is the global optimal scale combination.Furthermore,a necessary and sufficient condition under which a mult-scale decision system has a unique optimal scale combination is presented.Finally,an optimal scale combination selection algorithm based on sequential three-way decision is proposed based on these above theories.The experiments show that the proposed algorithm can effectively improve the computational efficiency of traditional algorithms.(2)Because the traditional serial processing method(scale selection followed by attribute reduction)may not get all scale reducts,a synchronous optimization strategy of attribute reduction and scale selection is adopted,and then a fast scale reduction algorithm based on sequential three-way decision and simplified multi-scale decision system is proposed.First,introducing the concept of “0” scale,attribute reduction is transformed into scale selection,and then the sequential three-way decision model of scale space is proposed.Second,the formula of calculating maximum element is given.This formula does not need to store the scale combinations,so it can reduce the space complexity of the algorithm.Third,from the perspective of accelerating the granulation efficiency,a fast granulation algorithm based on matrix ranking and simplified multi-scale decision system are proposed to further improve the computational efficiency.Finally,based on the above acceleration strategies and the sequential three-way decision model of scale space,a scale reduction algorithm for multi-scale decision system is proposed.The experimental results show that the algorithm can significantly improve the computational efficiency.(3)Because of the shortcomings of the traditional sequential three-way decision model,such as the loss of structure information of granules,the large number of parameters and decision conflicts,the basic theoretical framework of α-granular threeway decision for single-scale decision system is established.First,the hierarchical granular structure and its matrix representation are proposed.Second,in the hierarchical granularity space,a α-granular three-way decision model is established based on the fine-grained space.In this model,the positive,negative and boundary regions are defined in the form of granule family.This representation not only enhances the semantic interpretation of the model,but also provides a basis for improving the computational efficiency of sequential three-way decision.At the same time,the model only contains one parameter,which reduces the impact of subjectivity on the model and improves the robustness of the model.Finally,a α-granular sequential three-way decision model is proposed and its related properties are analyzed.The three decision regions generated by the model are monotonous with respect to the attribute subsets,which avoids the decision conflicts of traditional sequential three-way decision.(4)To improve the fault tolerance and semantic interpretation of the multi-scale rough set model,a probabilistic granular sequential three-way decision model for multiscale decision system is established and used for scale reduction.First,the α-granular sequential three-way decision model is extended to the multi-scale decision system,and the conceptual representation of multi-scale data under dynamic granularity is studied.Second,the concept and properties of core scale combination are given,and a grouping granulation algorithm for fast finding core scale combination is designed.Finally,a new multi-scale attribute importance is proposed,and an algorithm of scale reduction based on α-granular sequential three-way decision model is designed.Experiments demonstrate the effectiveness and efficiency of the proposed algorithm.