| Knowledge representation and knowledge discovery are the research hotspots in the field of knowledge engineering.Information derived from Knowledgecan be used for deduction and reasoning in data mining.Among them,rule extraction is an important research orientation.Aiming at the knowledge discovery of imprecise and uncertain data,granular computing(GrC)and formal concept analysis(FCA)are two effective theoretical methods and mathematical tools in recent years.Although the methods of GrC and FCA are different,both of thme can realize knowledge discovery for imprecise and uncertain data.Based on the theory of GrC and FCA,this thesis studies the rule extraction of information system.Then,the concept of formal vector is proposed and the rule extraction algorithm of information system based on formal vector is proposed.The specific work of this article is as follows:(1)According to the FCA method for rule extraction,firstly,the decision information system is transfored into the formal context,then the formal concepts are generated,after which,the rules are acquired by formal concept operation.However,the generation of concepts is a complex computational process,and the concept-based rules are often redundant.Therefore,on the ground of formal context,the formal vector and its properties are proposed and discussed,then,rule extraction algorithm for the consistent decision information system is proposed.The formal vectors in different layers are computed from coarser to finer granularity,and the rules are extracted by the relationship between the conditional formal vectors and the decision formal vectors.(2)Aiming at the rule extraction for inconsistent decision information system,a fast rule extraction algorithm based on formal vector is proposed.The algorithm reduces the complexity of rule extraction calculation by transforming the inconsistent decision information system into a consistent decision information system,and extracts the rules according to the inconsistent rule reduction theorem.The algorithm relies on the binary data structure of the formal vector,which has better rapidity and better recognition rate.(3)Combinatorial logic circuit is an important type of digital circuit.Truth table is a special decision information system.Truth table reduction is of great significance to large-scale digital circuit optimization.Firstly,the existing truth table reduction method is analyzed.Then,the formal vector was applied for truth table reduction,and corresponding theorems are provided.The algorithm defines the heuristic operator to sort the knowledge granularity of the vectors in each layer,which accelerates the convergence speed of the algorithm.In addition,parallel computing also improves the computational efficiency of the algorithm.Finally,the validity and rapidity of the algorithm are verified by theoretical analysis,complexity analysis,parallelism analysis and information loss analysis.(4)Based on the algorithm proposed in this thesis,a knowledge discovery system based on formal vector information system is designed and implemented,which integrates some of the classical algorithms mentioned in the thesis.The system also designs and implements the truth table reduction subsystem.It provides convenient conditions for the follow-up research and experimental work of scholars. |
