【作者】 陈洁；

【导师】 张燕平；

【作者基本信息】 安徽大学 ， 计算机应用技术， 2014， 博士

【摘要】 随着网络技术、物联网技术以及智能终端等技术的不断发展,人类社会的数据种类与规模呈爆炸式增长,积累的数据规模不断扩大,结构日趋复杂。如何从海量数据中获取有效信息已成为人工智能重要的研究课题之一。其中,部分数据具有明确的结构特征,如线性结构、树型结构和网状结构。然而,大部分数据没有明确的结构,即无结构数据。在有结构数据中,网状结构信息尤为复杂,如何准确表述其结构信息,并依据结构信息进行问题求解是网状结构问题研究的难点。同样,针对无结构问题,如何挖掘其潜在的结构信息对问题求解具有重要的现实指导意义。粒计算理论利用人类处理复杂问题时的结构化求解思想,采用由粗到细、不断求精的多粒度分析法,可以降低计算复杂度,提高求解精度。粒计算理论被认为符合人类认知的重要特征,改变了传统的求解观念,对复杂问题的求解具有重要的意义,在智能计算、机器发现、数据挖掘和图像处理等领域有着广泛的应用前景。目前,粒计算理论主要有基于模糊逻辑的粒计算理论、基于粗糙集的粒计算理论和基于商空间的粒计算理论等,其中商空间理论以论域、属性和结构三元组(X,f,T)描述问题,更强调结构的重要性。商空间理论引入结构这一重要特征,但并没有提供具体可用的算法用以获取结构信息,和应用结构信息进行的粒化和粒的计算。获取或利用结构信息进行问题求解的粒化关键技术和问题求解方法是本文的研究核心。本文基于商空间理论获取问题的结构信息,给出网状结构及无结构问题的粒化关键技术和粒的计算方法。首先,本文针对节点间序关系明确的网状结构问题给出了基于二元关系的粒化技术及其求解方法。其次,针对节点间仅有连通关系的网络给出了基于聚类分析的粒化技术及其求解方法。最后,针对无结构问题给出了基于二元关系的多层粒化技术及求解方法。本文的主要研究工作概括如下：1.研究商空间理论的粒化关键技术及求解方法；针对网状结构和无结构问题,本文着重研究了依据问题自身的结构信息,如何利用商空间理论进行合理粒化,再根据粒化结果选择相应的多粒度模型进行求解。本文针对具体问题给出了商空间理论的粒化关键技术和求解方法,为商空间理论的实际应用提供了指导。2.研究节点间序关系明确的网状结构问题的关系粒化及求解方法；针对节点间序关系明确的网状结构问题,定义保序性与或图将网状结构转换为与或图表示,将节点间的序关系转化为明确的与或图中的与／或关系。本文设计了网状问题求解算法(NPSOG),根据与或图中节点的与/或关系进行粒化,采用多粒度模型进行求解。模拟实验验证了NPSOG算法大大降低了问题求解的时间和空间复杂度。3.研究节点问仅有连通关系的网络问题的聚类粒化及求解方法；针对节点间不具有序关系的网络问题,因网络结构的聚类特性,定义聚类粒化操作,并给出粒化系数作为阈值,通过粒化系数控制粒化操作,将网络的粒化结果视为对网络的社团划分。本文设计了基于聚类粒化的社团发现算法(CGCDA),选取4组基准数据和一组实际移动基站频点设置数据进行实验,与人工和其他算法的对比结果表明了CGCDA算法的优势。4.研究无结构问题的多层粒化及求解方法。针对无结构问题,基于商空间理论的分层递阶思想挖掘出数据集潜在的结构信息,作者采用基于二元关系的多层粒化技术提取问题的本质特征,层层抽象、层层递进。本文首先设计了分层递阶覆盖算法(HCA),以覆盖算法(CA)为基础粒化算法构造基本粒,定义类别相关性矩阵上的模糊等价关系R实现多层粒化,并按获取的分层递阶结构进行求解。实验表明HCA算法不仅简化了问题的复杂度,而且提升了原基础粒化算法的求解精度。进一步地,根据问题求解过程的实际需求,在定义了两种粒度变换操作的基础上,即粒度分解和粒度合成,本文设计了基于商空间粒度变换的多层粒化求解算法(GTMSA),将分层递阶结构调整成最佳粒度结构。实验对比结果表明分层递阶结构调整的必要性和有效性。更多还原

【Abstract】 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.更多还原