Research On Granulation Technologies And Problem Solving Methods Based On Quotient Space Theory

In recent years, with the fast development of the internet technologies, internet of Things, intelligent terminal and so on, the scale and variety of data in society are growing in an explosive way. The data scale is expanding everyday and the structure of data is increasingly complex. A main research field of artificial intelligence is how to obtain available information from magnanimity data. Part of the data has definite structure, such as linear structure, tree structure and netted structure. But majority of the data is unstructured, named as unstructured data. For structured data, netted structure is particularly complicated. There are challenges that how accurately to describe structure information of the netted structural problem and how to solve the problem based on this information. For unstructured problem, how to mine underlying structure information also has great guiding significance to solve this kind of problems.Granular Computing Theory solves problems in the same manner as human deal with complex problems based on structure information. This theory utilizes multi-granular analysis method that is from coarse to fine, from fuzzy to accurate. It has lower complexity and higher precision. Granular Computing Theory is regarded as agreeable with the feature of human cognitive which is not agree with traditional solving methods. It is of great significance for solving complex problems and with wide application in computational intelligence, machine discovery, data mining, and image processing, and so on. At present, Granular Computing Theory mainly includes Fuzzy Set theory, Rough Sets Theory and Quotient Space Theory, etc. Quotient Space Theory emphasizes the significance of problem’s structure and describes a problem with a triple(X,f,T), where X is a domain,f is an attribute function and T is the structure of the elements in the domain.In Quotient Space Theory, the methods that how to obtain structure information and how to do granulation and computing after granulation based on that information are not defined. So the key technologies that solve different structural problems based on structure information are the core of this dissertation.In this dissertation, structure information of the problem is obtained based on Quotient Space Theory. Moreover, key technologies of granulation and computing methods after granulation are defined based on problem’s structure information to solve netted structural problems and unstructured problems. Firstly, author defines granulation technology and computing method based on binary relation for netted structural problems in which order relationships are clear among nodes. Secondly, cluster analysis granulation technology and computing method is given for network in which nodes only have connected relation. Finally, for unstructured problems, multilayer granulation technology and computing method based on binary relation is proposed.The dissertation includes:1. Key technologies of granulation and computing methods after granulation based on Quotient Space Theory are analyzed.For netted structural problems and unstructured problems, this dissertation discusses how to define granulation technologies according to structure information of the problem. Then, the corresponding multi-granular model is built based on Quotient Space Theory. The key technologies of granulation and computing methods given for concrete problems are the guidelines for the application of Quotient Space Theory.2. The technology of granulation and computing method based on binary relation is given for netted structural problems in which order relationships are clear among nodes.For this kind of problems, the Ordered AND/OR Graph is defined to transform netted structure to and/or graph. These order relationships are transformed to and/or relationships in the graph. In this dissertation, the Netted Problem Solving method based on Ordered and/or Graph (NPSOG) is proposed. The problem is granulated by and/or relationship. Then, the problem is computed in multi-granular spaces. Experiments show that NPSOG greatly reduces the time complexity and space complexity.3. The technology of granulation and computing method based on cluster analysis is given for network in which nodes only have connected relation.In this dissertation, the technology of granulation based on cluster analysis is defined according to the cluster property of network. The granulation is control by a threshold named as granulation coefficient. The result of granulation of the whole network is viewed as the community partitioning of network. So the Community Detection Algorithm based on Clustering Granulation (CGCDA) is proposed in this dissertation. Experiments on four Benchmark datasets and a practical datasets show that CGCPA has an advantage over other community detection algorithms.4. The multi-layers granulation technology and computing method is given for unstructured problems.For unstructured problems, the hierarchical method based on Quotient Space Theory is given to extract the underling structure information. The multilayer granulation technology based on binary relation is proposed to abstract the essential characteristics of the unstructured problem. Hierarchical covering algorithm (HCA) is proposed which uses Covering Algorithm (CA) as basic granulation method to construct basic granules. Then author defines fuzzy equivalence relation R on categories similarity matrix which is from basic granules. The problem is granulated into multilayer according to R. Experiments on MNIST and LR datasets show that HCA simplifies the complexity of problem and improves the precision of basic granulation method (CA). Furthermore, the granulation result can be adjusted by granular transform of Quotient space theory based on real requirements of the problem. Two granular transform operations are defined:granular composition and granular synthesis. Multi-granulation Solving Algorithm based on Granular Transform of quotient space theory (GTMSA) is given to obtain best granulation result. Results of experiments show that the adjustment of initial hierarchical structure is necessary and efficacious.