基于M-3WD的多阶段区域转化策略研究

doi:10.11896/jsjkx.180801609

摘要/Abstract

摘要： 三支决策的基本思想是三分而治。三支决策的提出者加拿大学者姚一豫教授在2018年基于分治模型(Trisecting-and-acting),进一步提出第三个要素——效(Outcome),从而形成了分治效结合的三支决策TAO模型。分、治(施加的策略)、效构成了三支决策的3个基本要素。在基于移动的三支决策模型中,对象在“治”的作用下在3个区域间移动,从而形成3个新区域,形成这3个新区域的过程被称为区域转化。在“治”这一步上,考虑“治”可以是一次性的,也可以是多次性的,具有多次可重入性,从而导致三分区域的转化可以是一次性的转化,也可以是多次性的转化。在这一过程中,涉及到成本或者收益等代价问题,从而需要从经济性的角度进一步考虑“治”。鉴于此,文中从广义三支决策的视角出发,提出了一个带有多阶段区域转化的三支决策模型,通过“治”后效果的度量来寻找最优的“治”。文中研究了最优转化策略,即一次性转化和多次性转化的费用优化问题。在带有多阶段区域转化的三支决策模型中,分析区域转化的费用,并按照区域转化次数划分阶段数,设计多阶段区域转化“治略”的动态规划算法,寻找最优的转化治略,进而给出在收益最大化的情况下的最优的转化治略。最后通过一个实例分析了区域一次性和多次性转化的费用,进一步得到多阶段区域转化的最佳转化次数以及最优转化费用,实现了转化治略的费用最优,说明了算法的有效性和实用性。

关键词: TAO模型, 基于移动的三支决策, 区域转化, 三支决策, 治略

Abstract: The basic ideas of three-way decisions (3WD) proposed by Prof Yao is dividing a whole set into three parts and developing different strategies on the three parts.Furthermore,Yao proposed the trisecting-acting-outcome model.Trisecting,acting and outcome are three basic elements of 3WD.In the movement-based 3WD model,the movement of objects leads regional changes,and this chang is called regional transformatio.In the step of “acting”,that “acting” can be one-time or multiple times should be conisdered.In this process,costs or benefits are involved,so the “acting” needs to be further considered from the perspective of economy.Based on three-way decisions from the view of generalization,this paper proposed a three-way decisions model with multi-stage regional transformation,and sought the optimal “ac-ting” by measuring the outcome of “acting”.The optimal transformation strategy was studied,that is the cost optimization of one-time transformation and multiple transformation.In the three-way decisions models with multi-stage regional transformation,the cost of regional transformation is analyzed,and the number of stages is divided according to the number of regional transformation times.A dynamic programming algorithm was proposed to find the optimal transformation strategy,and then the optimal transformation strategy was presented in the case of maximizing the benefit.Finally,an example was given to analyze the one-time and multiple transformation costs of the region,and the optimal transformation times and the optimal transformation costs of multi-stage regional transformation were further obtained.This paper illustrated the effectiveness and the practicability of the algorithm by an example.

Key words: Move-based three-way decisions, Region transformation, Strategies and actions, Three-way decisions, Trisecting-acting-outcome model

中图分类号:

TP301

郭豆豆, 姜春茂. 基于M-3WD的多阶段区域转化策略研究[J]. 计算机科学, 2019, 46(10): 279-285. https://doi.org/10.11896/jsjkx.180801609

GUO Dou-dou, JIANG Chun-mao. Multi-stage Regional Transformation Strategy in Move-based Three-way Decisions Model[J]. Computer Science, 2019, 46(10): 279-285. https://doi.org/10.11896/jsjkx.180801609

参考文献

[1]YAO Y Y.Three-Way Decision:An interpretation of rules in rough set theory[M]//Rough Sets and Knowledge Technology.Springer Berlin Heidelberg,2009:642-649.
[2]LIU D,LIANG D C.Generalized Three-way decisions and special three-way decisions [J].Journal of Frontiers of Computer Science and Technology,2017,11(3):502-510.(in Chinese)
刘盾,梁德翠.广义三支决策与狭义三支决策[J].计算机科学与探索,2017,11(3):502-510.
[3]YAO Y Y.An outline of a theory of three-way decisions[C]//Proceedings of the 8th International Conference on Rough Sets and Current Trends in Computing.Chengdu:Springer Berlin Heidelberg,2012:1-17.
[4]YAO Y Y.Three-way decisions with probabilistic rough set[J].Information Sciences,2010,180(3):341-353.
[5]LIU B X,LI Y,SUN J.Three-way decisions and relate theoretical research [J].Microcomputer and Applications,2014(12):1-3.(in Chinese)
刘保相,李言,孙杰.三支决策及其相关理论研究综述[J].微型机与应用,2014(12):1-3.
[6]YIN Y,KE D Y,LIU C Y.Theory of trinary decision and its application [J].Journal of Shanghai normal university(Natural Science),2015,44(1):95-104.(in Chinese)
殷业,柯德营,刘传勇.三支决策理论及应用[J].上海师范大学学报(自然科学版),2015,44(1):95-104.
[7]CAO C,YAO Y Y.Actionable strategies in three-way decisions [J].Knowledge-Based Systems,2017,133(1):141-151.
[8]JIANG C M,YAO Y Y.Effectiveness measures in movement-based three-way decision[J].Knowledge-Based Systems,2018,160(1):136-143.
[9]HU B Q.Three-way decisions space and three-way decisions[J].Information Sciences,2014,281(281):21-52.
[10]HU B Q,WONG H,YIU K F C.On two novel types of three-way decisions in three-way decision spaces [J].International Journal of Approximate Reasoning,2017,82(C):285-306.
[11]LIU D,LIANG D C,WANG C C.A novel three-way decision model based on incomplete information system[J].Knowledge-Based Systems,2016,91(C):32-45.
[12]MA X A,YAO Y Y.Three-way decision perspectives on class-specific attribute reducts[J].Information Sciences,2018,450(1):227-245.
[13]YAO Y Y.The superiority of three-way decisions in probabilistic rough set models [J].Information Sciences,2011,181(6):1080-1096.
[14]ZHAO X R,HU B Q.Fuzzy probabilistic rough sets and their corresponding three-way decisions [J].Knowledge-Based Systems,2016,91(1):126-142.
[15]WANG P X,YAO Y Y.CE3:A Three-way Clustering Method Based on MathematicalMorphology[J].Knowledge-Based Systems,2018,155(1):54-65.
[16]YU H,ZHANG C,WANG G Y.A tree-based incremental overlapping clustering method using the three-waydecision theory[J].Knowledge-Based Systems,2016,91(C):189-203.
[17]YU H,JIAO P,YAO Y Y,et al.Detecting and refining overlapping regions incomplex networks with three-way decisions [J].Information Sciences,2016,373(1):21-41.
[18]HUANG C C,LI J H,MEI C L,et al.Three-way concept lear-ning based oncognitive operators:an information fusion viewpoint[J].International Journal of Approximate Reasoning,2017,84(1):218-242.
[19]LI J H,HUANG C C,QI J J,et al.Three-way cognitive conceptlearning via multi-granularity[J].Information Sciences,2017,378 (1):244-263.
[20]QI J J,TING Q,WEI L,Connections between three-way and classical concept lattices[J].KnowledgeBased-Systems,2016,91(C):143-151.
[21]SINGH P K.Three-way fuzzy concept lattice representation using neutrosophic set [J].International Journal of Machine Learning and Cybernetics,2017,8(1):69-79.
[22]YAO Y Y.Interval sets and three-way concept analysis in incomplete contexts [J].International Journal of Machine Lear-ning and Cybernetics,2017,8(1):3-20.
[23]YU H Y,LI Q G,CAI M J.Characteristics of three-way concept lattices and three-way rough concept lattices [J].Knowledge-Based Systems,2018,146(15):181-189.
[24]AZAMA N,ZHANG Y,YAO J T.Evaluation functions and decision conditions of three-way decisions with game theoreticrough sets [J].European Journal of Operational Research,2017,261(2):704-714.
[25]AZAMA N,YAO J T.Game-theoretic rough sets for recom-mender systems[J].Knowledge-Based Systems,2014,72(1):96-107.
[26]ZHANG H R,MIN F.Three-way recommender systems based on random forests[J].KnowledgeBased Systems,2016,91 (C):275-286.
[27]ZHANG H R,MIN F,SHI B.Regression-based three-way recommendation [J].Information Sciences,2017,378(1):444-461.
[28]D’ANIELLO G,GAETA A,GAETA M,et al.Self-regulated learning with approximate reasoning and situation awareness[J].Journal of Ambient Intelligence and Humanized Computing,2018,9(1):151-164.
[29]YAO J T,AZAM N.Web-based medical decision support sys-tems for three-waymedical decision making with game-theoretic rough sets[J].IEEE Transactions on Fuzzy Systems,2015,23(1):3-15.
[30]YAO Y Y,WANG S,DENG X F.Constructing shadowed sets and three-way approximations of fuzzy sets [J].Information Scie-nces,2017,412(1):132-153.
[31]SHE Y H.On determination of thresholds inthree-way approximation of many-valued NM-logic[J].Rough Sets and Current Trends in Computing,2014,8536(1):136-143.
[32]JIA X,ZHENG K,LI W,et al.Three-Way Decisions Solution to Filter Spam Email:An Empirical Study[M]//Rough Sets and Current Trends in Computing.Springer Berlin Heidelberg,2012:287-296.
[33]ZHOU B,YAO Y Y,LUO J G.Cost-sensitive three-way email spam filtering[J].Journal of Intelligent Information Sciences,2014,42(1):19-45.
[34]LIU D,LI T R,LIANG D C.Three-way government decision analysis with decision theoretic rough sets[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2012,20(supp01):119-132.
[35]LI H X,ZHANG L B,HUANG B,et al.Sequential three-way decision and granulation for cost-sensitive face recognition[J].Knowledge-Based Systems,2016,91(C):241-251.
[36]LI H X,ZHANG L B,ZHOU X Z,et al.Cost-sensitive sequential three-way decision modeling using a deep neural network[J].International Journal of Approximate Reasoning,2017,85(C):68-78.
[37]YANG X,LI T R,FUJITA H,et al.A unified model of sequential three-waydecisions and multilevel incremental processing[J].Knowledge-Based Systems,2017,134(15):172-188.
[38]YAO Y Y.Granular computing and sequential three-way decisions[M]//Rough Sets and Knowledge Technology.Springer Berlin Heidelberg,2013:16-27.
[39]YANG X,LI T R,LIU D,et al.A unified framework of dynamic three-way probabilistic rough sets[J].Information Sciences,2017,420:126-147.
[40]ZHANG Q H,LV G X,CHEN Y H,et al.A dynamic three-way decision model based on the updating of attribute values[J].Knowledge-Based Systems,2018,142(15):71-84.
[41]YAO Y Y.Three-way decisions and granular computing[J].International Journal of Approximate Reasoning,2018,103(1):107-123.
[42]YAO Y Y.Three-way decisions and cognitive computing[J].Cognitive Computation,2016,8(4):543-554.

相关文章 15

[1]	王志成, 高灿, 邢金明. 一种基于正域的三支近似约简 Three-way Approximate Reduction Based on Positive Region 计算机科学, 2022, 49(4): 168-173. https://doi.org/10.11896/jsjkx.210500067
[2]	张师鹏, 李永忠. 基于降噪自编码器和三支决策的入侵检测方法 Intrusion Detection Method Based on Denoising Autoencoder and Three-way Decisions 计算机科学, 2021, 48(9): 345-351. https://doi.org/10.11896/jsjkx.200500059
[3]	王政, 姜春茂. 一种基于三支决策的云任务调度优化算法 Cloud Task Scheduling Algorithm Based on Three-way Decisions 计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023
[4]	辛现伟, 史春雷, 韩雨琦, 薛占熬, 宋继华. 基于三支决策的增量标签传播算法 Incremental Tag Propagation Algorithm Based on Three-way Decision 计算机科学, 2021, 48(11A): 102-105. https://doi.org/10.11896/jsjkx.210300065
[5]	梁伟, 段晓东, 徐健锋. 基于差异性度量的基础聚类三支过滤算法 Three-way Filtering Algorithm of Basic Clustering Based on Differential Measurement 计算机科学, 2021, 48(1): 136-144. https://doi.org/10.11896/jsjkx.200700213
[6]	薛占熬, 张敏, 赵丽平, 李永祥. 集对优势关系下多粒度决策粗糙集的可变三支决策模型 Variable Three-way Decision Model of Multi-granulation Decision Rough Sets Under Set-pair Dominance Relation 计算机科学, 2021, 48(1): 157-166. https://doi.org/10.11896/jsjkx.191200175
[7]	陈玉金, 徐吉辉, 史佳辉, 刘宇. 基于直觉犹豫模糊集的三支决策模型及其应用 Three-way Decision Models Based on Intuitionistic Hesitant Fuzzy Sets and Its Applications 计算机科学, 2020, 47(8): 144-150. https://doi.org/10.11896/jsjkx.190800041
[8]	向伟, 王新维. 基于多类邻域三支决策模型的不平衡数据分类 Imbalance Data Classification Based on Model of Multi-class Neighbourhood Three-way Decision 计算机科学, 2020, 47(5): 103-109. https://doi.org/10.11896/jsjkx.180601099
[9]	李艳, 张丽, 陈俊芬. 动态信息系统中基于序贯三支决策的属性约简方法 Attribute Reduction Method Based on Sequential Three-way Decisions in Dynamic Information Systems 计算机科学, 2019, 46(6A): 120-123.
[10]	薛占熬, 韩丹杰, 吕敏杰, 赵丽平. 一种新的基于粒度重要度的三支决策模型 New Three-way Decisions Model Based on Granularity Importance Degree 计算机科学, 2019, 46(2): 236-241. https://doi.org/10.11896/j.issn.1002-137X.2019.02.036
[11]	李艳, 张丽, 王雪静, 陈俊芬. 优势-等价关系下序贯三支决策的属性约简 Attribute Reduction for Sequential Three-way Decisions Under Dominance-Equivalence Relations 计算机科学, 2019, 46(2): 242-148. https://doi.org/10.11896/j.issn.1002-137X.2019.02.037
[12]	徐健锋, 何宇凡, 刘斓. 三支决策代价目标函数的关系及推理研究 Relationship and Reasoning Study for Three-way Decision Cost Objective Functions 计算机科学, 2018, 45(6): 176-182. https://doi.org/10.11896/j.issn.1002-137X.2018.06.031
[13]	陈玉金, 李续武, 邢瑞康. 基于证据理论的三支决策模型 Three-way Decisions Model Based on Evidence Theory 计算机科学, 2018, 45(6): 241-246. https://doi.org/10.11896/j.issn.1002-137X.2018.06.043
[14]	薛占熬,辛现伟,袁艺林,吕敏杰. 基于直觉模糊可能性分布的三支决策模型的研究 Study on Three-way Decisions Based on Intuitionistic Fuzzy Probability Distribution 计算机科学, 2018, 45(2): 135-139. https://doi.org/10.11896/j.issn.1002-137X.2018.02.024
[15]	张刚强, 刘群, 纪良浩. 基于序贯三支决策的多粒度情感分类方法 Multi-granularity Sentiment Classification Method Based on Sequential Three-way Decisions 计算机科学, 2018, 45(12): 153-159. https://doi.org/10.11896／j.issn.1002-137X.2018.12.024

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed