Algorithm For Attribute Reduction And Computing Core In Incomplete Decision Table

Nowdays, waves of IT are raised in the world field one by one, just like cloud computing and the Internet of Things spring up, mobile communication services go to4G times, big data times is coming and so on.. These IT revolutions make humans’lives and works more easy and convinent. Espically the big data times, the processed data have been up to level of PB, so it makes process data more hard. Rough set is a mathmatic tool which is used to process the uncertain, imprecise, inconsistent information. It is one of import research results that is result in research human intelligent and pattern recognition. The most prominent speciality of rough set is that it can achieve the aim of processing data without any transzendental knowledge or other additional information.Attribute reduction and computing the core are one of the most important research hot of rough set theory. Attribute reduction is use for simplifying the original data under the condition which keep the hidden rules and the relation of data. Meanwhile, the attribute reduction can divide into attribute reduction with core and attribute reduction without core. Attribute reduction without core achieve the aim by some model or enlightening information. While attribute reduction with core finish the task which is based on computing the core attribute firstly. The core attribute is the intersecion of all of the attribute reductions. So, the core is one of the most meaningful subjects.At the same time, the research of attribute reduction and computing core in rough set is in complete decision table currently. But in real situation, because of the data losing, uncertain data or the noise data, there are null values or losing information in the information system. Thus, the classic method of attribute reduction and computing the core is not adapt to the situation. So it causes that the research of attribute reduction and computing the core in incomplete decision table is a new trend. Professor Guoyin Wang had a study on incomplete decision table to design the tolerance relation, the limited tolerance relation, the similarity relation and so on. The scholaes from various countries use the positive region, matrix, the quantity information, the granulation to analyse the attribute reduction and core in incomplete decision table.Firstly, the paper gives an outline of the development history of rough set and relative concepts. Then, it uses conflict region and the limited tolerance relation to compute the attribute reduction and core which aims to the incomplete decision table. The following will discuss the paper work from three aspects:(1) At first, we use the method of count by steps which is used to compute the tolerance class in the incomplete decision table, and it is more efficient and clearer than algorithm before. The model of boolean conflict matrix was built by the conflict region definition and matrix ideas. The attributes were found one by one after reducting by logical operation of matrix and the importance of attributes. The method is creative compare to attribute reduction based on discernibility matrix, and the efficience of time is improved. The time complexity is max{O(|K||C||U|),O(|C|2|POSC(D)||U|)}(|K|=max{|TC(x)||x∈U}), the space complexity is O(|C|2|POSC(D)||U|).(2) In the rhe research on core attribute, the definition of conflict region and the judgment method of core based on conflict region are given. Compare to the common positive region method, conflict region can reduce the comparion count of decision values of elements, thus it can make the efficence of algorithm improve. Then, computing toerlance class is used by linked radix rort, the method reduce the time complexity. With analyzing on the algorithm, the time complexity is O(|K||C2|U|)(|K|=max{|TC(x)||x∈U}) and the space complexity is O{|U|).(3) The model of tolerance relation is usually built which have a research on incomplelete decision. But tolerance relation is not precise which is used to divide the objects. After having an research on limited tolerance relation, it can divide the limited tolerance classes that are more precise and more resonable. It can help compute the core attribute. So a binnary discernibility matrix based on limited tolerance relation is designed, then the matrix is good at compute the core. With analysing on the algorthm,the time complexity is O{|C||U|2), and the space complexity is O(|C||U||Upox|).