基于互模拟的粗糙近似理论及其应用

The classical rough set theory treats knowledge as the partition of a universe, granulates the universe into information granules by an equivalence relation, and then characterizes uncertain knowledge by the lower and upper approximations based on information granules. In order to broaden the application scope of classical rough sets, some scholars have proposed the concept of generalized rough sets based on general binary relations and generalized the lower and upper rough approximations in several different ways. A common feature of these generalized approximations is that they are only dependent on “one step” information of the underlying relation, namely, the direct relation between objects. However, in some applications, “one step” information is not sufficient to distinguish objects. In light of this, motivated by a rich notion, bisimulation, appearing in various areas of computer science, we characterize the indiscernibility of objects in a universe by using multi-step information. After reconstructing fundamentally lower and upper approximation operators and giving the related efficient algorithms, we establish a modal logic and a rough set algebra to describe the properties of our rough set model. Furthermore, we systematically and thoroughly explore the generalized rough set model based on bisimulations, related uncertainty measures, and attribute reduction algorithms. In addition, we apply the theoretical results to other fields including topological structure mining of web, graph pattern matching, and graph compression. The research of this project will provide a new theoretical basis for rough data analysis from the perspective of multi-step information and offer a technical support for processing complex relational data.

经典粗糙集将知识看作是关于论域的划分，通过等价关系将论域粒化形成信息粒，用信息粒构造的下近似和上近似去描述概念。为了拓宽其应用范围，学者们提出了基于一般二元关系的广义粗糙集，同时考虑了下近似和上近似的多种推广。我们注意到，这些推广的一个共同特征是，它们仅依赖其二元关系的“一步”信息，即对象之间的直接关系。然而，在一些实际应用中，“一步”信息不足以分辨对象。为此，本课题拟借鉴计算机科学中的互模拟思想，采用“多步”信息来刻画论域中对象的不可分辨性，从根本上重新构造下近似和上近似算子，设计计算下近似和上近似的有效算法，建立描述模型性质的模态逻辑和粗糙集代数，系统而深入地研究基于互模拟的广义粗糙集模型、不确定性度量及属性约简算法，并将理论成果应用于web拓扑结构挖掘、基于互相似的图模式匹配和图压缩等。本课题的研究将从“多步”信息的视角为粗糙数据分析提供新的理论依据，为复杂关系数据处理提供技术支持。

经典粗糙集将知识看作是关于论域的划分，通过等价关系将论域粒化形成信息粒，用信息粒构造的下近似和上近似去描述概念。为了拓宽其应用范围，学者们提出了基于一般二元关系的广义粗糙集，同时考虑了下近似和上近似的多种推广。我们注意到，这些推广的一个共同特征是，它们仅依赖其二元关系的“一步”信息，即对象之间的直接关系。然而，在一些实际应用中，“一步”信息不足以分辨对象。为此，我们借鉴计算机科学并发理论中著名的互相似和互模拟思想，在广义近似空间和标号近似空间中，采用“多步”信息来刻画论域中对象的不可分辨性，从根本上重新构造了下近似和上近似算子，系统而深入地研究了基于互相似的广义粗糙集模型、不确定性度量及属性约简算法，并将这些理论结果成功应用于基于互相似的图模式匹配和社交网络朋友关系识别等。本课题的顺利开展，从“多步”信息的视角为粗糙数据分析提供了新的理论依据，丰富和发展了粗糙数据分析的理论和方法，为复杂关系数据处理提供了技术支持。