不完备异构冲突信息系统中的极大一致联盟区间集族

doi:10.3778/j.issn.1673-9418.2305081

摘要/Abstract

摘要： 作为处理不确定性问题的有效工具，三支决策已被广泛应用于冲突分析研究中。然而，现有的三支冲突分析模型大多基于单一类型的冲突信息系统，难以应对实际应用中代理对议题具有多类型评价值和缺失值的情况。同时，已有联盟集的定义通常基于给定代理，即联盟集中的代理与给定代理具有联盟关系，但不一定两两联盟。为了解决这些问题，构建了基于不完备异构冲突信息系统的三支冲突分析模型，并提出了代理两两相关的极大一致联盟区间集族的定义及其构造算法。首先，通过定义代理不同类型评价值的支持度和反对度，将对单个议题单维度多类型评价值的不完备异构冲突信息系统转化为双维度同类型评价值的二维模糊不完备冲突信息系统。其次，通过定义代理之间的乐观与悲观距离函数，构造了基于代理的联盟、冲突、中立区间集。最后，定义了极大一致联盟区间集族，并利用极大团的枚举算法获取极大一致联盟区间集族。

关键词: 三支决策, 冲突分析, 不完备异构信息系统, 极大团, 极大一致联盟区间集族

Abstract: As effective tools for dealing with uncertainty, three-way decision models have been widely applied in the study of conflict analysis. However, existing three-way conflict analysis models are mostly based on single-type conflict information systems, which fail to address the challenges of practical situations where agents may have missing or multiple types of ratings. Furthermore, the existing definitions of alliance sets are typically based on a given agent. Particularly, agents in an alliance set are allied to the given agent, but they are not necessarily allied with each other. To address these issues, this paper proposes a three-way conflict analysis model in an incomplete heterogeneous conflict information system. Additionally, this paper presents the definition and algorithm of a family of maximal consistent alliance interval sets, where agents are allied with each other. Firstly, the incomplete heterogeneous conflict information system with single-dimensional multi-type ratings is transformed into a two-dimensional fuzzy incomplete conflict information system with two-dimensional single-type ratings. This is achieved by defining the support and opposition degrees for different rating types of agents. Secondly, the agent-based alliance, conflict, and neutral interval sets using optimistic and pessimistic distance functions between agents are defined. Finally, a family of maximal consistent alliance interval sets is defined and obtained by adopting the algorithm of maximal clique enumeration.

Key words: three-way decision, conflict analysis, incomplete heterogeneous information system, maximal clique, family of maximal consistent alliance interval sets

罗珺方, 张硕, 胡梦君. 不完备异构冲突信息系统中的极大一致联盟区间集族[J]. 计算机科学与探索, 2024, 18(5): 1232-1242.

LUO Junfang, ZHANG Shuo, HU Mengjun. Family of Maximal Consistent Alliance Interval Sets in Incomplete Heterogeneous Conflict Information System[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(5): 1232-1242.

参考文献

[1] PAWLAK Z. On conflicts[J]. International Journal of Man- Machine Studies, 1984, 21(2): 127-134.
[2] PAWLAK Z. An inquiry into anatomy of conflicts[J]. Information Sciences, 1998, 109: 65-78.
[3] DEJA R. Conflict analysis[J]. International Journal of Intelligent Systems, 2002, 17: 235-253.
[4] PAWLAK Z. Some remarks on conflict analysis[J]. European Journal of Operational Research, 2005, 166(3): 649-654.
[5] LIU Y, LIN Y. Intuitionistic fuzzy rough set model based on conflict distance and applications[J]. Applied Soft Computing, 2015, 31: 266-273.
[6] SKOWRON A, RAMANNA S, PETERS J F. Conflict analysis and information systems: a rough set approach[C]//Proceeding of the 1st International Conference on Rough Sets and Knowledge Technology, Chongqing, Jul 24-26, 2006. Berlin, Heidelberg: Springer, 2006: 233-240.
[7] LANG G M, MIAO D Q, CAI M J. Three-way decision approaches to conflict analysis using decision-theoretic rough set theory[J]. Information Sciences, 2017, 406/407: 185-207.
[8] FAN Y, QI J J, WEI L. A conflict analysis model based on three-way decisions[C]//Proceeding of the 2018 International Joint Conference on Rough Sets, Quy Nhon, Aug 20-24, 2018. Cham: Springer, 2018: 522-532.
[9] SUN B Z, MA W M, ZHAO H Y. rough set-based conflict analysis model and method over two universes[J]. Information Sciences, 2016, 372: 111-125.
[10] SUN B Z, CHEN X T, ZHANG L Y, et al. Three-way decision making approach to conflict analysis and resolution using probabilistic rough set over two universes[J]. Information Sciences, 2020, 507: 809-822.
[11] YAO Y Y. Three-way conflict analysis: reformulations and extensions of the Pawlak model[J]. Knowledge-Based Systems, 2019, 180: 26-37.
[12] LANG G M, LUO J F, YAO Y Y. Three-way conflict analysis: a unification of models based on rough sets and formal concept analysis[J]. Knowledge-Based Systems, 2020, 194:105556.
[13] ZHI H L, QI J J, QIAN T, et al. Conflict analysis under one-vote veto based on approximate three-way concept lattice [J]. Information Sciences, 2020, 516: 316-330.
[14] 智慧来, 王月, 马一凡, 等. 冲突分析的研究进展[J]. 海南热带海洋学院学报, 2023, 30(2): 62-72.
ZHI H L, WANG Y, MA Y F, et al. Research advances in conflict analysis[J]. Journal of Hainan Tropical Ocean University, 2023, 30(2): 62-72.
[15] LANG G M, MIAO D Q, FUJITA H. Three-way group conflict analysis based on Pythagorean fuzzy set theory[J]. IEEE Transactions on Fuzzy Systems, 2019, 28(3): 447-461.
[16] LI X N, WANG X, LANG G M, et al. Conflict analysis based on three-way decision for triangular fuzzy information systems[J]. International Journal of Approximate Reasoning, 2021, 132: 88-106.
[17] YI H, ZHANG H M, LI X N, et al. Three-way conflict analysis based on hesitant fuzzy information systems[J]. International Journal of Approximate Reasoning, 2021, 139: 11-27.
[18] BASHIR Z, WAHAB A, RASHID T. Three-way decision with conflict analysis approach in the framework of fuzzy set theory[J]. Soft Computing, 2022, 26: 309-326.
[19] DU J L, LIU S F, LIU Y, et al. A novel approach to three-way conflict analysis and resolution with Pythagorean fuzzy information[J]. Information Sciences, 2022, 584: 65-88.
[20] 王艺超, 王振, 魏玲, 等. 多值冲突表的复合冲突程度分析[J]. 西北大学学报(自然科学版), 2022, 52(5): 805-812.
WANG Y C, WANG Z, WEI L, et al. Compound conflict degree analysis of many-valued conflict situation[J]. Journal of Northwest University (Natural Science Edition), 2022, 52(5): 805-812.
[21] FENG X F, YANG H L, GUO Z L. Three-way conflict analysis in dual hesitant fuzzy situation tables[J]. International Journal of Approximate Reasoning, 2023, 154: 109-132.
[22] YANG H L, WANG Y, GUO Z L. Three-way conflict analysis based on hybrid situation tables[J]. Information Sciences, 2023, 628: 522-541.
[23] 常月, 王振，任睿思，等. 基于区间值模糊冲突表的三支冲突分析[J] . 陕西师范大学学报(自然科学版)，2023, 51 (1): 78-86.
CHNAG Y, WANG Z, REN R S, et al. Three-way conflict analysis based on interval-valued fuzzy conflict situation[J]. Journal of Shaanxi Normal University (Natural Science Edition), 2023, 51(1): 78-86.
[24] ZHI H L, LI J H, LI Y N. Multilevel conflict analysis based on fuzzy formal contexts[J]. IEEE Transactions on Fuzzy Systems, 2022, 30(12): 5128-5142.
[25] SUO L W Q, YANG H L. Three-way conflict analysis based on incomplete situation tables: a tentative study[J]. International Journal of Approximate Reasoning, 2022, 145: 51-74.
[26] 杨文听，易黄建，陈跃，等. 基于不完备信息系统的三支冲突分析[J]. 陕西师范大学学报(自然科学版), 2022, 50(3): 43-51.
YANG W T, YI H J, CHEN Y, et al. Three-way conflict analysis based on incomplete information systems[J]. Journal of Shaanxi Normal University (Natural Science Edition), 2022, 50(3): 43-51.
[27] LUO J F, HU M J, LANG G M, et al. Three-way conflict analysis based on alliance and conflict functions[J]. Information Sciences, 2022, 594: 321-359.
[28] 张迎迎, 李天瑞. 区间值信息系统中一种极大相容类的增量更新算法[J]. 小型微型计算机系统, 2017, 38(7): 1572-1579.
ZHANG Y Y, LI T R. Incremental algorithm for updating maximal consistent classes in interval-valued information system[J]. Journal of Chinese Computer Systems, 2017, 38(7): 1572-1579.
[29] TRAN L, DUCKSTEIN L. Comparison of fuzzy numbers using a fuzzy distance measure[J]. Fuzzy Sets Systems, 2002, 130: 331-341.
[30] EPPSTEIN D, LOFFLER M, STRASH D. Listing all maximal cliques in large sparse real-world graphs[J]. Journal of Experi-mental Algorithmics, 2013, 18: 1-21.
[31] BRON C, KERBOSCH J. Algorithm 457: finding all cliques of an undirected graph[J]. Communications of the ACM, 1973, 16(9): 575-577.
[32] TOMITA E, TANAKA A, TAKAHASHI H. The worst-case time complexity for generating all maximal cliques and computational experiments[J]. Theoretical Computer Science, 2006, 363: 28-42.
[33] SCHMIDT M C, SAMATOVA N F, THOMAS K, et al. A scalable, parallel algorithm for maximal clique enumeration[J]. Journal of Parallel and Distributed Computing, 2009, 69: 417-428.
[34] SEGUNDO S P, RODRIGUEZ-LOSADA D, JIMENEZ A. An exact bit-parallel algorithm for the maximum clique pro-blem[J]. Computers & Operations Research, 2011, 38(2): 571-581.