一种基于顺序三向决策的多尺度决策表最优规模组合选择新方法

《International Journal of Approximate Reasoning》：A new approach to optimal scale combination selection for multi-scale decision tables based on sequential three-way decision

　　•本文提出了一种基于序列三向决策的最优尺度组合选择方法。•通过计算尺度空间的最小元素来加速搜索过程。•该方法能够统一处理一致性与不一致性的多尺度决策表，具有更强的适用性。•显著降低了计算复杂度和数据获取成本。

引言
数据的复杂性给实际应用带来了严峻挑战。例如，人体生理系统、社会经济系统以及自然生态系统都具有多尺度结构与行为特征，不同尺度的数据之间存在关联与互动。仅依靠单一尺度的数据无法完整呈现这些复杂系统的整体面貌。为解决这些问题[1]，Wu和Leung[2]提出了多尺度信息系统（MSISs），用于表示和分析不同粒度级别的数据。这一理论框架很快便受到了研究界的广泛关注。Zhang等人[3]研究了将加权邻域粗糙集与Wu-Leung模型相结合的新多尺度模型。Ma等人[4]对MSISs的基本理论、现有研究方法以及未来面临的挑战进行了全面综述。Xiao等人[5]提出了基于MSISs的共识达成过程方法。文献[6]则从不同角度探讨了如何将异构偏好结构与MSISs结合用于群体决策。

在MSISs中，将讨论域划分为所需区域是一项具有挑战性的任务。三向决策（3WD）最初被提出[7]，旨在通过将讨论域划分为接受、拒绝和暂缓区域来应对信息不确定性。3WD已被广泛应用于医学诊断[8]、推荐系统[9]、项目选址[10]以及金融行业预测[11,12]等领域。作为3WD的扩展，序列三向决策（S3WD）模拟了“从粗到细”的认知过程：在每一轮中，只有那些具备足够信息的对象才会被决策，而不确定的对象则会被推迟到下一轮处理[13]。S3WD已与粗糙集[[14], [15], [16], [17]]、聚类分析[18,19]、模糊集[20]以及遗憾理论[12,21]等框架深度融合。然而，上述大多数研究中的数据表示形式都基于单尺度信息系统，即一个属性下只有一种信息描述方式。此后，研究人员开始将3WD引入MSISs中。Li等人[22]提出了在不完全MSISs环境下的改进型证据三向决策方法。文献[23]则介绍了在不完全MSISs环境下基于量子社交网络的规模化群体决策方法。Xiao等人[24]提出了基于社交网络与3WD的群体共识方法。文献[25]则设计了基于模糊社交网络与操纵行为的、包含3WD的异构群体共识方法。Wang等人[26]提出了一种新的共识模型，该模型整合了异步意见演化机制与动态信任驱动的三向决策机制，用于处理不完全MSISs问题。Huang等人[27]提出了基于前景-遗憾理论与直觉模糊数的不完全MSISs三向决策模型。Zhan等人[28]则给出了基于三角模糊数且结合遗憾理论的不对完全MSISs的三向决策方法。

多尺度决策表（MSDTs）是MSISs在实际场景中的具体体现[29]。在MSDTs中，每个属性都可以在多个粒度级别上被观测到。例如，学生表现既可以以百分比分数精确记录，也可以用“优秀”“良好”“中等”“较差”等等级进行评估，还可以简化为“及格”与“不及格”两类。这种多粒度特性使得数据能够反映不同粒度层面的系统规律，但也带来了一个根本性难题：精细级信息虽然精度高，但数据获取成本高；而粗略级信息虽然成本低，却可能丢失关键信息。因此，为每个属性选择合适的观测尺度这一问题被称为最优尺度组合（OSC）选择问题[30]，它已成为MSISs领域的一个核心挑战。

OSC选择是一种有效的处理工具，可用于消除信息冗余，同时保留数据的核心特征。其成功的关键在于选择合适的尺度级别。值得注意的是，OSC能够提取出具有更强泛化能力的决策规则。目前，OSC选择已成功应用于农业领域[[31], [32], [33]]。根据其特征，MSDTs可分为两类：一致性MSDTs与不一致性MSDTs。早期关于OSC的研究主要集中于一致性MSDTs。Li和Hu等人提出了互补模型[34]、格模型（LM）[34]以及逐步最优尺度选择算法（SOSS）[35]，这些模型有效解决了属性粒度差异带来的问题。Xie等人[36]提出了基于三种新一致性类型及其相互关系的OSC方法。Cheng等人[37]则通过将S3WD模型与扩展后的SOSS方法相结合来获得OSC。此外，还有一些学者将熵[38]与证据理论[39]引入尺度选择过程中。在不一致性MSDTs中，Zhu等人[40]基于正区域一致性，通过互补模型与LM得到了OSC。Wu等人[41]为各种尺度组合的集合定义了下近似与上近似。文献[42]提出了基于Dempster-Shafer证据理论与信息量化方法的广义多尺度集值有序信息系统的OSC。文献[43]则展示了基于3WD与哈塞图的OSC选择方法。另一方面，关于不完全MSDTs中的OSC选择也已有大量研究[44,45]。

通过对上述文献的回顾，仍存在以下几方面的研究空白：
(1)现有方法的适用性有限。大多数现有方法都聚焦于一致性MSDTs中的OSC选择[28,34]，而对不一致性MSDTs的研究相对较少。目前的常用方法[34]会在OSC选择之前先将不一致性MSDTs转换为一致性MSDTs，但这种转换忽略了现实数据中固有的不一致性。因此，迫切需要一种无需区分一致性与不一致性情况的统一算法框架。
(2)现有算法的复杂度较高。Zhu等人[40]提出了针对不一致性MSDTs的OSC模型，但该算法的计算与内存复杂度极高，不适合当前大规模数据处理场景。此外，Li等人[35]开发的SOSS算法虽可用于确定OSC，但在计算属性重要性时会产生较大的计算开销。LM算法[34]以及Li等人[28]开发的OSC方法也存在同样的问题。因此，有必要开发出计算效率更高的算法。
(3)OSC相关的数据获取成本相对较高。在MSDTs中，信息可以通过多种属性粒度级别来表征，但随着粒度从粗略向精细过渡，数据收集成本会呈单调上升趋势。OSC选择的目标就是在最小化成本的同时，找到能够保留数据特征的子系统。然而，现有的算法往往会产生成本过高的OSC结果。例如，Zhang等人的研究[43]就将S3WD引入OSC选择过程，但要求先对决策表进行一致性或不一致性分类，该方法通过构建分类规则来辅助OSC选择，但后续实验结果表明，由此产生的OSC并不能保证最低的数据收集成本。因此，亟需开发出能够确保成本效益的OSC算法。

为解决上述问题，本研究提出了一种基于S3WD与正区域一致性来获取OSC的新方法。其主要贡献如下：
(1)采用改进后的SOSS算法来确定局部尺度空间的OSC。具体而言，我们的方法无需判断各属性的重要性，而是基于正区域一致性来选择尺度。同时，改进后的SOSS也不需要判断决策表的一致性，从而提升了OSC在实际数据集上的应用成功率。
(2)提出了一种计算最小元素的方法。该方法是将S3WD应用于尺度集划分的前提，能够有效减少尺度组合的检验次数，进而降低计算复杂度，提高处理效率。
(3)基于前两种算法，我们提出了一种融合S3WD与正区域一致性的OSC选择方法。为了实现快速且精准的OSC识别，我们设计了明确的分类标准，同时采取了相应策略以尽可能降低OSC的获取成本。在多个数据集上的实验表明，我们的方法显著提高了OSC识别的成功率，同时在计算效率与成本控制方面也取得了显著提升，显示出其在大规模数据环境中的巨大应用潜力。

本文的其余结构如下：第2节回顾了Pawlak粗糙集与MSISs的基本概念；第3节介绍了三种核心算法：(1)改进后的逐步最优尺度选择算法，(2)最小元素计算方法，(3)基于S3WD与正区域一致性的尺度选择方法；第4节通过实际数据集的实验验证了所提方法的可行性与有效性；最后，第5节总结了研究结论、局限性及未来工作方向。

相关工作
本节将对Pawlak粗糙集、信息系统以及MSDTs的一些基本概念进行回顾。

定义1[46]：设U为一个有限的非空集合，称为讨论域；R?U×U是U上的一个等价关系；X是U的任意子集。X的上近似与下近似定义如下：
R￣(X)=∪{[x]R|[x]R?X}，
Rˉ(X)=∪{[x]R|[x]R∩X≠?}，
其中[x]R={y∈U|(x,y)∈R}是包含x的R-等价类。

定义2[2]：信息表是一个二元组(U,A)，其中U={x1,x2,?,xn}是...

基于S3WD的OSC方法
本节我们将提出一种基于正区域一致性与S3WD框架的OSC算法。3.1节介绍用于寻找局部OSC的改进型逐步最优尺度选择方法；3.2节详细阐述确定尺度集最小元素的计算方法；最后，3.3节给出完整的OSC_S3WD_PR算法框架。

实验与分析
本节为进一步展示所提方法的优势，我们选择了加利福尼亚大学欧文分校机器学习仓库((https://archive.ics.uci.edu/ml/index.php)中的数据集以及KEEL数据集(https://sci2s.ugr.es/keel/datasets.php)。这些数据集涵盖了医学诊断、工业检测、交通运输、教育评估以及社会科学等多个领域，其样本规模与属性维度各不相同。

结论
多尺度决策表（MSDTs）的最优尺度组合（OSC）选择长期以来一直受到一种固有矛盾的制约：即在有效消除信息冗余的同时，还要保持决策能力。为解决这一难题，本文提出了一种基于序列三向决策（S3WD）的新型OSC选择方法。具体而言，该方法通过改进的ISOSS算法在局部尺度空间内获得OSC，同时还提供了一种确定最小元素的方法。

CRediT作者贡献声明
Qi Wei：撰写——初稿、可视化、验证、项目管理、方法论、研究、形式分析、数据整理、概念构思。Xiuqin Ma：撰写——审阅与编辑、指导、资金获取、概念构思。Hongwu Qin：撰写——审阅与编辑、指导、资金获取、概念构思。Mengyao Wang：可视化、软件开发。Qi Wei|Xiuqin Ma|Hongwu Qin|Mengyao Wang