Study on the Application of the Theory of Rough Sets to Text Excavation
Dali Yin, Yan Yan · Advances in intelligent systems research/Advances in Intelligent Systems Research · 2014
The rough set theory is a new calculation which deduces the concept categorization rules through attribute reduction with the categorization capacity remaining unchanged, and has wide application to data excavation and text excavation. This paper focuses on the analysis and improvement of the application of the rough set theory to text excavation, embracing the two aspects of attribute reduction based on clear matrix and correlation rules based on the Apriori algorithm. Compared with the classic algorithms, the improved algorithm can cut down a great deal on the expenditure of time and space in its operation, and improves considerably in its performance of processing the large-scale text database excavation. This research result has great theoretical significance to the application of the rough set theory and its algorithm to text excavation. Keywords-rough set; data excavation; text excavation; attribute reduction; correlation rules I.BACKGROUND OF RESEARCH With the rapid development of the database technology and its application in many fields, the accumulated original data is on the sharp rise, and the present database system can realize the function of data saving, testing and so forth, but the present data excavation technology has some defects preventing it from discovering efficiently the relations and rules of data and constituting a practically valuable database. How to excavate valuable and potential knowledge in the mass of irregular data has formed the important research content of data excavation. Text excavation is a key research trend in data excavation, which focuses on a large amount of text data, by means of quantitative calculation and qualitative analysis seeking for useful knowledge in irregular data. In the early of the eighties of the 20th century, Professor Z. Pawlak proposed the theory of rough sets [1], which is a new mathematical tool for dealing with incomplete information and inaccurate questions. The key idea of it is to find out categorization rules of concept through knowledge reduction with the categorization capacity remaining unchanged. The rough set theory has the features of needing no pre-experience, being capable of dealing with incomplete information and easy to be combined with other methods, therefore it is widely applied in the fields of data and text excavation. However, the research on the application of rough set theory to text excavation is now in its primary stage nationally, and many methods remain to be improved urgently. And what is more, it is a focal point in the present research. II.APPLICATION OF THE ROUGH SET THEORY TO TEXT EXCAVATION Text excavation is a major branch of data excavation. With the swelling of text database, how to get useful knowledge through these data with high efficiency and high quality becomes a hot issue in the present research. Therefore, a large number of scholars and enterprises devote themselves in improving the method and efficiency of excavation algorithm. This paper will focus on the analysis and improvement concerning the two aspects of attribute reduction and correlation rules in the excavation in order to make text excavation more efficient. The attribute reduction and correlation rules are the classic algorithms in the rough set theory, whose division and relation are shown in Fig. 1. Fig.1. Division of Text Excavation Process Attribute reduction and correlation rules are different parts of text excavation, but they are closely related in the process of excavation. First, attribute reduction is the precondition for the excavation of correlation rules. The attribute reduction will firstly reduce the attribute of decision list, cutting off the redundancy attribute and extracting a simple and plain reduced decision list, thus the quality of attribute reduction will directly affect the value of rules extracted from the correlation rules; secondly, the correlation rules are the intuitive 2nd International Conference on Information, Electronics and Computer (ICIEAC 2014) © 2014. The authors Published by Atlantis Press 117 demonstration of the effect of attribute reduction. The excavation of correlation rules will extract correlation rules from the reduced decision list. If there are some defects in algorithm, it cannot make the right judgement of the effect of the algorithm of attribute reduction, and even cannot obtain right and useful correlation rules. III.RESEARCH AND IMPROVEMENT ON ALGORITHM The extraction of attribute reduction and correlation rules constitutes the important part of the rough set theory, and in the meantime is an important step in text excavation. Due to the characteristics of multi-source and multi-variety of text data, the data stored in the knowledge base are full of both the good and the bad, therefore before the categorization of knowledge base, the complicated attribute set must be reduced, and the candidate data must be filtered and classified. As a result, on the one hand, the redundancy attribute can be removed reducing their interference with the classification of algorithm; on the other hand, the scale of knowledge is reduced, and the efficiency and quality of categorization of algorithm. A. Attribute reduction algorithm based on clear matrix 1)The advancement of clear matrix and its thoughts In the early 90s of the 20th century, A. Skowron advanced the method of representing knowledge with clear matrix based on the simplicity and plainness of attribute reduction by clear matrix and the capability of finding core attribute with high efficiency. Therefore, during rough set reduction, clear matrix has wide application, whose algorithm has the thoughts shown as follows a) According to the definition, the clear matrix M of decision list is obtained; b) For the non-void element Cij of the clear matrix M, the corresponding extraction is yielded: a L ij j C a ij ; c) do conjunction to the extraction Lij, and the norm form of conjunction is yielded L: ij C L L j 0 ; d) For transformation of expression, transform the conjunction norm form L into the extraction norm form: L=∨Li; e) Finally the output of the reduction result. From the above clear matrix method with attribute reduction and combined with the literature[2][3] we can see that this method has the following defects: a) The traditional attribute reduction algorithm based clear matrix starts from definitions and obtains clear matrix by means of the decision list. The time complexity of this algorithm is O(|C|2|U|2). Therefore, applying this algorithm to solving problems tends to need a mass of space and a long time. Especially in dealing with the large-scale data, problems like storage space insufficiency are likely to arise. Therefore, direct solution to the clear matrix of the decision list and then the realization of attribute reduction algorithm tends to result in unsatisfactory complexity of algorithm time and space. b) From the course of attribute reduction with clear matrix we can see that the processing demands a transitional form to be yielded, which will result in waste in time and space. In addition, the logic expression of extraction yielded will have repeated terms, which will lead to the increase in calculation in the reduction of logical formula. 2) The Heuristic algorithm based on clear matrix In order to raise the efficiency of algorithm, aiming at the deficiency of the traditional attribute reduction algorithm based on clear matrix, the algorithm is improved in the following ways: a) This paper advances that the decision list should be simplified first, whose procedure is realized by quick solution to the algorithm of the division of U/C, and whose time complexity is O(|C||U|) , and then the simplified clear matrix and the attribute reduction based on the simplified clear matrix are found after the decision list is simplified, and the equivalent value is proved between attribute reduction based simplified clear matrix and attribute reduction based on the original clear matrix. Algorithm 1: demands the input: the decision list S=(U,C,D,V,f),U={x1,x2,···,xn},C={c1,c2,···,cn}; The output: U pos,U neg,mi,Mi,MD,MD(i=1,2, ···,k). 1 Find the statistics of every element and decision attribute D in conditional attribute sets, and record the maximum and minimum of f(xj,ci) and f(xj,D)(j=1,2,···,n) with Mi , mi and MD ,mD; 2 put the element x1,x2,···,xn in the domain U in the linked list L one by one, with the pointer pointing to x1; 3 For(i = 1; i < k+1; i++) i Construct the void queue of Mi-mi+1, and put the element x in the linked list L in the corresponding queue of f(x,ci)-mi in turn; ii. Reconstruct the linked list L , revise the head and tail pointers of the linked list L, enabling them to point to the first and the last non-void queue respectively, and consequently rebuild queues amounting to Mi-mi+1 into a new linked list L ; 4 suppose the element sequence in the new linked list L are x 1,x 2,···,x n;t = 1;Bt={x 1}; For(j=2;j < n+1;j++) If any element for the conditional attribute C can fulfill f(x j,ci)= f(x j-1,ci), then Bt=Bt∪{x j};otherwise {t = t+1;Bt={x j} }; 5 let ' pos U = ∅, ' neg U = ∅, For(i =1;i < t+1;i++) If elements contained in Bi have equal value in decision attribute, then extract the first element in Bi and incorporate it intoU’pos, otherwise incorporate it into U’neg b) From the definition of clear matrix we can see that if a certain object in matrix only contains one attribute, then this attribute is the necessary attribute that