第17卷第2期 智能系统学报 Vol.17 No.2 2022年3月 CAAI Transactions on Intelligent Systems Mar.2022 D0:10.11992/tis.202012048 网络出版地址：https:/kns.cnki.net/kcms/detail/23.1538.TP.20211012.1841.002.html 面向混合数据的代价敏感三支决策边界域分类方法 周阳阳'，钱文彬2王映龙，彭莉莎3，曾武序 (1,江西农业大学计算机与信息工程学院，江西南昌330045,2.江西农业大学软件学院，江西南昌330045： 3.南京大学工程管理学院.江苏南京210046) 摘要：针对现有三支决策模型的研究对象多为单一性数据的决策系统，对于混合数据边界域样本处理的研究 相对较少，本文面向混合数据提出了基于核属性的代价敏感三支决策边界域分类方法。该方法基于正域约简 计算混合邻域决策系统的核属性集，在此基础上计算混合邻域类，并利用三支决策规则分别将对象划分到各决 策类的正域、边界域和负域：提出了一种基于代价敏感学习的三支决策边界域分类方法，并构造了误分类代价 的计算方法，以此划分边界域中的对象。通过对UCI上的10个数据集进行实验对比与分析，进一步验证了本 文方法，为处理边界域样本提供了一种可行有效的方法。 关键词：三支决策：粒计算；代价敏感；混合数据：正域约简；边界域样本处理：粗糙集；核属性 中图分类号：TP391 文献标志码：A文章编号：1673-4785(2022)02-0411-09 中文引用格式：周阳阳，钱文彬，王映龙，等.面向混合数据的代价敏感三支决策边界域分类方法J.智能系统学报，2022， 17(2):411-419. 英文引用格式：ZHOU Yangyang,.QIAN Wenbin,WANG Yinglong,etal.Classification method of cost--sensitive three-way de- cision boundary region for hybrid data[Jl.CAAI transactions on intelligent systems,2022,17(2):411-419. Classification method of cost-sensitive three-way decision boundary region for hybrid data ZHOU Yangyang',QIAN Wenbin,WANG Yinglong',PENG Lisha',ZENG Wuxu (1.School of Computer and Information Engineering,Jiangxi Agricultural University,Nanchang 330045,China;2.School of Sof- ware,Jiangxi Agricultural University,Nanchang 330045,China;3.School of Engineering Management,Nanjing University,Nanjing 210046,China) Abstract:The research objects of existing three-way decisions models are mostly decision-making systems with single data.Relatively few studies on the boundary region sample processing of mixed data have been conducted.To address this issue,a classification method of a cost-sensitive three-way decision boundary region based on core attributes for hy- brid data is proposed in this study.This method computes the core attribute set of the hybrid neighborhood decision sys- tem based on positive domain reduction.On this basis,the hybrid neighborhood class is calculated,and the objects are divided into the positive,boundary,and negative regions of each decision-making class through three-way decision rules.The classification method of the three-way decision boundary region based on cost-sensitive learning is proposed. Then,a calculation method of the misclassification cost is constructed to divide the objects in the boundary region.Ex- periments and analyses are performed on 10 datasets of UCI,which show the feasibility and the effectiveness of the pro- posed method for the processing of boundary region samples. Keywords:three-way decisions;granular computing;cost sensitive;hybrid data;positive domain reduction;boundary region sample processing;rough set;core attribute 收稿日期：2020-12-28.网络出版日期：2021-10-13 三支决策是加拿大学者Yao-21提出的一种 基金项目：国家重点研发计划项目(2020Y℉D1100605):国家自 然科学基金项目(61966016)：江西省自然科学基金项 “化繁为简”决策理论，它从粒计算视角将论域划 目(20192BAB207018);江西省研究生创新专项基金 分为三个互不相交的论域子空间，并对其分别采 项目(YC2020-S236). 通信作者：钱文彬.E-mail:qianwenbinl027@l26.com 取不同的应对策略，这种分而治之的思想，可有
DOI: 10.11992/tis.202012048 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20211012.1841.002.html 面向混合数据的代价敏感三支决策边界域分类方法 周阳阳1 ，钱文彬1,2，王映龙1 ，彭莉莎3 ，曾武序1 （1. 江西农业大学 计算机与信息工程学院，江西 南昌 330045; 2. 江西农业大学 软件学院，江西 南昌 330045; 3. 南京大学 工程管理学院，江苏 南京 210046） 摘 要：针对现有三支决策模型的研究对象多为单一性数据的决策系统，对于混合数据边界域样本处理的研究 相对较少，本文面向混合数据提出了基于核属性的代价敏感三支决策边界域分类方法。该方法基于正域约简 计算混合邻域决策系统的核属性集，在此基础上计算混合邻域类，并利用三支决策规则分别将对象划分到各决 策类的正域、边界域和负域；提出了一种基于代价敏感学习的三支决策边界域分类方法，并构造了误分类代价 的计算方法，以此划分边界域中的对象。通过对 UCI 上的 10 个数据集进行实验对比与分析，进一步验证了本 文方法，为处理边界域样本提供了一种可行有效的方法。 关键词：三支决策；粒计算；代价敏感；混合数据；正域约简；边界域样本处理；粗糙集；核属性 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2022)02−0411−09 中文引用格式：周阳阳, 钱文彬, 王映龙, 等. 面向混合数据的代价敏感三支决策边界域分类方法 [J]. 智能系统学报, 2022, 17(2): 411–419. 英文引用格式：ZHOU Yangyang, QIAN Wenbin, WANG Yinglong, et al. Classification method of cost-sensitive three-way decision boundary region for hybrid data[J]. CAAI transactions on intelligent systems, 2022, 17(2): 411–419. Classification method of cost-sensitive three-way decision boundary region for hybrid data ZHOU Yangyang1 ，QIAN Wenbin1,2 ，WANG Yinglong1 ，PENG Lisha3 ，ZENG Wuxu1 (1. School of Computer and Information Engineering, Jiangxi Agricultural University, Nanchang 330045, China; 2. School of Software, Jiangxi Agricultural University, Nanchang 330045, China; 3. School of Engineering Management, Nanjing University, Nanjing 210046, China) Abstract: The research objects of existing three-way decisions models are mostly decision-making systems with single data. Relatively few studies on the boundary region sample processing of mixed data have been conducted. To address this issue, a classification method of a cost-sensitive three-way decision boundary region based on core attributes for hybrid data is proposed in this study. This method computes the core attribute set of the hybrid neighborhood decision system based on positive domain reduction. On this basis, the hybrid neighborhood class is calculated, and the objects are divided into the positive, boundary, and negative regions of each decision-making class through three-way decision rules. The classification method of the three-way decision boundary region based on cost-sensitive learning is proposed. Then, a calculation method of the misclassification cost is constructed to divide the objects in the boundary region. Experiments and analyses are performed on 10 datasets of UCI, which show the feasibility and the effectiveness of the proposed method for the processing of boundary region samples. Keywords: three-way decisions; granular computing; cost sensitive; hybrid data; positive domain reduction; boundary region sample processing; rough set; core attribute 三支决策是加拿大学者 Yao[1-2] 提出的一种 “化繁为简”决策理论，它从粒计算视角将论域划 分为三个互不相交的论域子空间，并对其分别采 取不同的应对策略，这种分而治之的思想，可有 收稿日期：2020−12−28. 网络出版日期：2021−10−13. 基金项目：国家重点研发计划项目 (2020YFD1100605);国家自 然科学基金项目 (61966016); 江西省自然科学基金项 目 (20192BAB207018);江西省研究生创新专项基金 项目（YC2020-S236）. 通信作者：钱文彬. E-mail: qianwenbin1027@126.com. 第 17 卷第 2 期 智 能 系 统 学 报 Vol.17 No.2 2022 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2022
·412· 智能系统学报 第17卷 效提高决策准确度，降低误分类代价。三支决策 相对较少。 理论模拟人类认知、学习和决策的过程，可处理 为此，本文提出了一种面向混合数据的代价 决策过程中出现的不确定性问题。近年来，三支 敏感三支决策边界域分类方法。首先，基于正域 决策理论引起了许多研究者的关注，已成为了粒 约简，提出了面向混合数据的属性约简模型；然 计算和知识发现领域中的一个重要研究方向。目前， 后，提出了一种基于代价敏感的三支决策边界域 三支决策在众多应用领域中得到广泛的应用，如 样本处理方法，在贝叶斯最小风险的基础上构造 人脸识别回、推荐系统、决策系统和邮件过滤可 误分类代价公式，划分边界域中的对象。最后， 等：为了处理复杂的应用场景，提出了不同的计 对UCI上的10个数据集进行实验，结果表明该方 算模型，如序贯三支决策B1、优化三支决策、前 法能够降低误分类代价，而且能较准确地划分边 景三支决策、三支模糊集1和三支约简回等。 界域中的对象；这为三支决策的边界域样本处理 在实际应用中，代价是影响三支决策划分的 提供了一种可借鉴的方法。 重要因素之一。代价敏感学习能够有效缓解分类 过程中的数据不平衡问题，其主要作用是处理决 1基本知识 策过程和结果产生的各类代价问题。代价敏感学 1.1邻域粗糙集 习主要研究两种代价：误分类代价（结果代价）和 在粗糙集理论四中，给定一个四元组决策系统： 测试代价，两者互相关联，呈负相关。如在医疗诊 DS=U,A,=CUD,VlaEA,],(IlaEA,l 断中，患者想要获得更高的诊断准确率（即决策 其中U={x1,2,…,x表示有限非空的对象全集， 代价越低)，就需要做更多的检查（即测试代价越 称为论域或者对象空间：A,表示有限非空的属性 高)。由于代价是数据的内在特征，将其与知识发 全集，由条件属性和决策属性共同组成；C={a, 现结合会使得问题更具有普适性，目前，代价敏 a2,…,an表示有限非空的条件属性全集；D表示决 感学习已经应用到现实生活中的许多领域，如： 策属性；V表示aeC的属性值集；lU×A,→V是一 人脸识别、价格预测和客户信用评价等。 个信息函数，能给每个对象的每个属性赋值，即 因此，基于代价敏感的三支决策算法与模型 la(x)→Vao 引起了许多学者的关注和研究，已取得重要的研 定义12)给定混合邻域决策系统DN={U, 究成果。Fang等81将信息粒度纳入决策分析过 FDUFC,D,Va,Ia,6,距离度量函数△N:U×U,给定 程，同时考虑决策过程和决策结果的代价，分别 属性子集B二C和邻域参数δ，则对象x和y基于B的 设计了两种不同的算法以最小化决策过程和决策 邻域关系为 结果代价。Fang等6提出了一种三支决策和可 NR(B)={(x,y∈U×U1△WB(x,y)≤6 分辨矩阵的框架，在此框架下分别设计了基于删 对Yx∈U,x的邻域粒度可表示为 除和增加的代价敏感近似属性约简算法。Ja等叨 6s(x)=x,y∈U△Ns(xy)≤ 构造了一种可以直接应用于传统的代价敏感学习 式中：FD为离散属性集合；FC为连续属性集合； 问题的三支决策模型，在此基础上，提出基于多 6是邻域参数。 类三支决策模型的多阶段代价敏感学习方法。L 12三支决策粗糙集 等！为从输入图像中顺序提取分层粒度结构，提 三支决策粗糙集2通过2个状态集和3个动 出了一种基于DNN的顺序粒度特征提取方法， 作集来描述其决策过程。其中，状态集S={X,X) 在此基础上，提出一种代价敏感的序贯三支决策 分别表示对象属于概念X和不属于概念X,动作集 模型。Yang等考虑了用户需求，提出一种基 A={ap,as,aw表示对于不同状态分别采取接受、延 于模糊粗糙集的序贯三支决策模型的优化机制， 迟和拒绝3种不同的动作。由于采取不同动作会 用来实现对代价敏感的最优粒度选择。Ma等2o 产生不同的损失，记p、AP、wp表示当x∈X时， 定义了三支特定类的最低代价约简，分别设计了 分别采取动作ap、as和aw产生的风险损失值；同样 基于添加一删除策略和删除策略来构建特定类的 地，记pw、BN、ww表示当x∈X时，分别采取动 最小代价约简算法。以上算法与模型能够最小化 作ap、ag和aw产生的风险损失值；损失之间的关系 结果代价或过程代价。而在许多应用领域中往往 满足：r<r<NP,ww<N<pw。在实际应用 需要从代价敏感视角来分析三支决策边界域样 中，这些损失值通过专家的经验获取。 本，目前三支决策的研究对象多为单一性数据的 定义2川在决策系统DS={U,CUD,V,}中， 决策系统，对于混合数据边界域样本处理的研究 令X为论域U基于决策属性D的划分，α和B为三支
效提高决策准确度，降低误分类代价。三支决策 理论模拟人类认知、学习和决策的过程，可处理 决策过程中出现的不确定性问题。近年来，三支 决策理论引起了许多研究者的关注，已成为了粒 计算和知识发现领域中的一个重要研究方向。目前， 三支决策在众多应用领域中得到广泛的应用，如 人脸识别[3] 、推荐系统[4-5] 、决策系统[6] 和邮件过滤[7] 等；为了处理复杂的应用场景，提出了不同的计 算模型，如序贯三支决策[3,8] 、优化三支决策[9] 、前 景三支决策[10] 、三支模糊集[11] 和三支约简[12] 等。 在实际应用中，代价是影响三支决策划分的 重要因素之一。代价敏感学习能够有效缓解分类 过程中的数据不平衡问题，其主要作用是处理决 策过程和结果产生的各类代价问题。代价敏感学 习主要研究两种代价：误分类代价（结果代价）和 测试代价，两者互相关联，呈负相关。如在医疗诊 断中，患者想要获得更高的诊断准确率（即决策 代价越低），就需要做更多的检查（即测试代价越 高）。由于代价是数据的内在特征，将其与知识发 现结合会使得问题更具有普适性，目前，代价敏 感学习已经应用到现实生活中的许多领域，如： 人脸识别[13] 、价格预测[14] 和客户信用评价[15] 等。 因此，基于代价敏感的三支决策算法与模型 引起了许多学者的关注和研究，已取得重要的研 究成果。Fang 等 [8] 将信息粒度纳入决策分析过 程，同时考虑决策过程和决策结果的代价，分别 设计了两种不同的算法以最小化决策过程和决策 结果代价。Fang 等 [16] 提出了一种三支决策和可 分辨矩阵的框架，在此框架下分别设计了基于删 除和增加的代价敏感近似属性约简算法。Jia 等 [17] 构造了一种可以直接应用于传统的代价敏感学习 问题的三支决策模型，在此基础上，提出基于多 类三支决策模型的多阶段代价敏感学习方法。Li 等 [18] 为从输入图像中顺序提取分层粒度结构，提 出了一种基于 DNN 的顺序粒度特征提取方法， 在此基础上，提出一种代价敏感的序贯三支决策 模型。Yang 等 [19] 考虑了用户需求， 提出一种基 于模糊粗糙集的序贯三支决策模型的优化机制， 用来实现对代价敏感的最优粒度选择。Ma 等 [20] 定义了三支特定类的最低代价约简，分别设计了 基于添加−删除策略和删除策略来构建特定类的 最小代价约简算法。以上算法与模型能够最小化 结果代价或过程代价。而在许多应用领域中往往 需要从代价敏感视角来分析三支决策边界域样 本，目前三支决策的研究对象多为单一性数据的 决策系统，对于混合数据边界域样本处理的研究 相对较少。 为此，本文提出了一种面向混合数据的代价 敏感三支决策边界域分类方法。首先，基于正域 约简，提出了面向混合数据的属性约简模型；然 后，提出了一种基于代价敏感的三支决策边界域 样本处理方法，在贝叶斯最小风险的基础上构造 误分类代价公式，划分边界域中的对象。最后， 对 UCI 上的 10 个数据集进行实验，结果表明该方 法能够降低误分类代价，而且能较准确地划分边 界域中的对象；这为三支决策的边界域样本处理 提供了一种可借鉴的方法。 1 基本知识 1.1 邻域粗糙集 在粗糙集理论[21] 中，给定一个四元组决策系统： DS = { U,At = C ∪ D, { Va|a ∈ At } , { Ia|a ∈ At }} U = {x1, x2,··· , xn} At C = {a1, a2,··· ,an} D Va a ∈ C Ia|U × At → V Ia(x) → Va 其中 表示有限非空的对象全集， 称为论域或者对象空间； 表示有限非空的属性 全集，由条件属性和决策属性共同组成； 表示有限非空的条件属性全集； 表示决 策属性； 表示 的属性值集； 是一 个信息函数，能给每个对象的每个属性赋值，即 。 DN = {U, F D ∪ F C ,D,Va,Ia,δ} ∆N : U ×U B ⊆ C δ x y B 定义 1 [22] 给定混合邻域决策系统 ，距离度量函数 ，给定 属性子集 和邻域参数 ，则对象 和 基于 的 邻域关系为 NRδ (B) = { (x, y) ∈ U ×U|∆NB(x, y) ⩽ δ } 对 ∀x ∈ U，x的邻域粒度可表示为 δB(x) = {y|x, y ∈ U,∆NB(x, y) ⩽ δ} F D F C δ 式中： 为离散属性集合； 为连续属性集合； 是邻域参数。 1.2 三支决策粗糙集 S = {X,¬X} X X A = {aP,aB,aN} λPP、λBP、λNP x ∈ X aP、aB aN λPN、λBN、λNN x ∈ ¬X aP、aB aN λPP < λBP < λNP λNN < λBN < λPN 三支决策粗糙集[23] 通过 2 个状态集和 3 个动 作集来描述其决策过程。其中，状态集 分别表示对象属于概念 和不属于概念 ，动作集 表示对于不同状态分别采取接受、延 迟和拒绝 3 种不同的动作。由于采取不同动作会 产生不同的损失，记 表示当 时， 分别采取动作 和 产生的风险损失值；同样 地，记 表示当 时，分别采取动 作 和 产生的风险损失值；损失之间的关系 满足： ， 。在实际应用 中，这些损失值通过专家的经验获取。 DS = {U,C ∪ D,Va,Ia} X U D α β 定义 2 [1] 在决策系统 中， 令 为论域 基于决策属性 的划分， 和 为三支 ·412· 智 能 系 统 学 报 第 17 卷
第2期 周阳阳，等：面向混合数据的代价敏感三支决策边界域分类方法 ·413· 决策的阈值，P(X[)表示对象x的条件概率，对于 定义4给定混合邻域决策系统DN={U,FDU x∈U,根据贝叶斯决策过程，计算得到最小成本 FC,D,Va,Ia,l,令D为论域U基于决策属性D的划 准则的三支决策规则： 分，则混合邻域决策系统的上下近似表示为： POS(X)={xEUla≤P(XI[x])≤1} AN(D)={x∈Ul6c(x)sDl BND(X)={x∈UlB≤PXI[x)≤a AN(D)={xeUl6c()nD,≠O例 NEG(X)={x∈UIO≤P(XI[x)≤ 通过上下近似集，可知特征子集B上的正域 其中，PX[=XnL国，H表示对象的个数： 如下： Ifll (dPw-Asw)】 POSc(D)=AN(D)=[xEUl6c(x)C D;] a=Cpw-sw-dan-p）】 定义5给定混合邻域决策系统DN={U, B= (ABN -ANN) FDUFC,D,Va,Ia,,令属性a,∈C,则混合邻域决策 (ABN -ANN)-(ANP -ABP) 系统中基于三支决策的核属性集定义为： 其中，正域POS(X)、负域NEG(X)和边界域BNDX) CORE(C)=a llPOSc(D)I-IPOSC-1(D)I>0} 分别对应三支决策规则中的接受、拒绝和不承诺 以表1为例，给出一个混合邻域决策系统， 规则，且满足：POS(X)UBND(X)UNEG(X)=X;仅 其中，U={x,,…,xol为对象集，C={a1,a2,…,a6 当X=U时，POS(X)UBND(X)UNEG(X)=U。 为条件属性集，决策类UID={D,D2},分别为 1.3代价敏感学习 D1={x1,x3,x,x6,7,xg},D2={x2,X4xg,X10l。 代价敏感学习主要研究误分类代价和测试代 表1混合邻域决策系统DN 价，由于本文中考虑了其误分类代价，误分类代 Table 1 Hybrid neighborhood decision system DN 价表示对对象错误划分后的一种惩罚。用Cx表 U a a2 as D 示误分类代价矩阵，其中k表示k分类问题。为方 1 0 0.93 0.73 0.80 0.68 d 便理解，以二分类代价矩阵C=G:为例： C21C22 1 0.64 0.50 0.33 0.48 d 其中c表示将类别为1的对象划分到类别1中， X3 0.58 0.39 0.38 0.29 d 因此c1的值为0，同理cz的值也为0；c2表示将类 XA 02 0.12 0.11 0.18 别为1的对象划分到类别2中，此时属于误分类， d 在划分中需付出惩罚代价，因此c12>0,同理c2:>0。 Xs 4R 0.58 d 0.42 0.62 d 2基于正域约简的代价敏感三支决 0.50 0.73 策边界域分类方法 d X8 0.50 0.62 0.38 0.44 d 2.1面向混合邻域决策系统的正域约简 0 0 0.42 0.62 0.49 0.50 d 由于基于三支决策的粒计算方法大多是处理 X10 0 00.39 0.58 0.29 0.50 连续型数据或离散型数据等单一型数据，但是在 现实生活的应用领域中数据类型通常是既含有连 根据定义5可计算出混合邻域决策系统的核 续型数据又含有离散型数据的混合数据，为此需 属性集，具体的计算过程为：首先，根据定义3，利 对混合数据的三支决策模型展开研究。 用p=2时的欧氏距离计算全体对象的混合邻域粒 定义3给定混合邻域决策系统DN={U,FDU 度，再根据定义5计算出POSc(D)={1,x4,x3,x6 FC,D,Va,Ia,外，V(x)表示对象x在属性a上的属性值： ,同理可计算出POSc-a(D)={1,x4,x5,6,xl,因 对于x,y∈U,Ya∈FD,则x和y基于FD的距离为 为POSc(D)=POSc-a,(D),所以属性a1生CORE(C),同 AN(.)=0.V()=V.) 理可求出{a2,a3,as,a6}CORE(C),只有属性 11,V.(x)≠V.y) a:∈CORE(C)。由此可知核属性集为CORE(C)= 对于Yx,y∈U,Ya∈Fc,则x和y基于Fc的距离为 {a}。下面将在此基础上，提出了代价敏感下的三 支决策边界域分类方法。 △N(x,y)= 22基于核属性集的代价敏感三支决策边界域 其中，当p=1时，△We(y)为曼哈顿距离；当 分类方法 p=2时，△Wx(xy)为欧氏距离；当p→oo时， 定义6给定混合邻域决策系统DN={U, △N(x,y为切比雪夫距离。 FDUFC,D,Va,I,6,设属性子集BCC,a和B为三支
P(X|[x]) x ∀x ∈ U 决策的阈值， 表示对象 的条件概率，对于 ，根据贝叶斯决策过程，计算得到最小成本 准则的三支决策规则： POS(X) = { x ∈ U|α ⩽ P(X |[x]) ⩽ 1 } BND(X) = { x ∈ U|β ⩽ P(X |[x]) ⩽ α } NEG(X) = { x ∈ U|0 ⩽ P(X |[x]) ⩽ β } P(X|[x]) = |X ∩[x]| |[x]| 其中， ，|·| 表示对象的个数； α = (λPN −λBN) (λPN −λBN)−(λBP −λPP) β = (λBN −λNN) (λBN −λNN)−(λNP −λBP) POS(X) NEG(X) BND(X) POS(X)∪BND(X)∪ NEG(X) = X X = U POS(X)∪BND(X) ∪NEG(X) = U 其中，正域 、负域 和边界域 分别对应三支决策规则中的接受、拒绝和不承诺 规则，且满足： ；仅 当 时， 。 1.3 代价敏感学习 Ck×k k k C2×2 = [ c11 c12 c21 c22 ] c11 c11 c22 c12 c12 > 0 c21 > 0 代价敏感学习主要研究误分类代价和测试代 价，由于本文中考虑了其误分类代价，误分类代 价表示对对象错误划分后的一种惩罚。用 表 示误分类代价矩阵，其中 表示 分类问题。为方 便理解，以二分类代价矩阵 为例； 其中 表示将类别为 1 的对象划分到类别 1 中， 因此 的值为 0，同理 的值也为 0； 表示将类 别为 1 的对象划分到类别 2 中，此时属于误分类， 在划分中需付出惩罚代价，因此 ，同理 。 2 基于正域约简的代价敏感三支决 策边界域分类方法 2.1 面向混合邻域决策系统的正域约简 由于基于三支决策的粒计算方法大多是处理 连续型数据或离散型数据等单一型数据，但是在 现实生活的应用领域中数据类型通常是既含有连 续型数据又含有离散型数据的混合数据，为此需 对混合数据的三支决策模型展开研究。 DN = { U,F D∪ F C ,D,Va,Ia,δ} Va(x) x a 定义 3 给定混合邻域决策系统 ， 表示对象 在属性 上的属性值： ∀x, y ∈ U,∀a ∈ F D x y F 对于 D ，则 和 基于 的距离为 ∆NFD (x, y) = { 0, Va(x) = Va(y) 1, Va(x) , Va(y) ∀x, y ∈ U,∀a ∈ F C x y F 对于 C ，则 和 基于 的距离为 ∆NFC (x, y) = ∑m k=1 |Va(x) = Va(y)|p 1 p p = 1 ∆NFC (x, y) p = 2 ∆NFC (x, y) p → ∞ ∆NFC (x, y) 其中，当 时 ， 为曼哈顿距离；当 时 ， 为欧氏距离；当 时 ， 为切比雪夫距离。 DN = { U,F D∪ F C , D,Va,Ia,δ} Di U D 定义 4 给定混合邻域决策系统 ，令 为论域 基于决策属性 的划 分，则混合邻域决策系统的上下近似表示为： AN(D) = { x ∈ U|δC(x) ⊆ Di } AN(D) = { x ∈ U|δC(x)∩ Di , Ø } 通过上下近似集，可知特征子集 B 上的正域 如下： POSC(D) = AN(D) = { x ∈ U|δC(x) ⊆ Di } DN = {U, F D ∪ F C , D,Va,Ia,δ} ai ∈ C 定 义 5 给定混合邻域决策系统 ，令属性 ，则混合邻域决策 系统中基于三支决策的核属性集定义为： CORE(C) = { ai ||POSC(D)| − |POSC−{ai}(D)| > 0 } U = {x1, x2,··· , x10} C = {a1,a2,··· ,a6} U/ D = {D1,D2} D1 = {x1, x3, x5, x6, x7, x9} D2 = {x2, x4, x8, x10} 以表 1 为例，给出一个混合邻域决策系统， 其中， 为对象集， 为条件属性集 , 决策类 ，分别为 ， 。 表 1 混合邻域决策系统 DN Table 1 Hybrid neighborhood decision system DN U a1 a2 a3 a4 a5 a6 D x1 1 0 0.93 0.73 0.80 0.68 d1 x2 1 1 0.64 0.50 0.33 0.48 d2 x3 1 1 0.58 0.39 0.38 0.29 d1 x4 0 1 0.21 0.12 0.11 0.18 d2 x5 1 0 0.63 0.80 0.48 0.58 d1 x6 0 0 0.74 0.78 0.42 0.62 d1 x7 1 0 0.85 0.80 0.50 0.73 d1 x8 1 1 0.50 0.62 0.38 0.44 d2 x9 0 0 0.42 0.62 0.49 0.50 d1 x10 0 0 0.39 0.58 0.29 0.50 d2 p = 2 POSC(D) = {x1, x4, x5, x6, x7} POSC−{a1 }(D) = {x1, x4, x5, x6, x7} POSC(D) = POSC−{a1}(D) a1 < CORE(C) {a2,a3,a5,a6} < CORE(C) a4 ∈ CORE(C) CORE(C) = {a4} 根据定义 5 可计算出混合邻域决策系统的核 属性集，具体的计算过程为：首先，根据定义 3，利 用 时的欧氏距离计算全体对象的混合邻域粒 度，再根据定 义 5 计算出 ，同理可计算出 ,因 为 ,所以属性 ，同 理可求出 , 只有属性 。由此可知核属性集为 。下面将在此基础上，提出了代价敏感下的三 支决策边界域分类方法。 2.2 基于核属性集的代价敏感三支决策边界域 分类方法 DN = {U, F D ∪ F C , D,Va,Ia,δ} B ⊆ C α β 定 义 6 给定混合邻域决策系统 ，设属性子集 ， 和 为三支 第 2 期 周阳阳，等：面向混合数据的代价敏感三支决策边界域分类方法 ·413·
·414- 智能系统学报 第17卷 决策的阈值，D表示不同的决策属性，则不同属性 {x1,3,5,X6,x,xg}和BNDs(D1)={x1,x2,x4,5,X6,x,x8, 子集下的三支决策规则定义为： x9,x10l,根据定义7和性质1可将边界域中的对象 POSs(D)={x∈Ula≤P(Dl6s(x)≤1} 划分到正域和负域，具体的计算过程如下： BNDB(D)=[xEUB<P(D:l6B(x))<a} 对于Yx∈BNDa(D),根据定义7可求出划分 NEGs(D,)={x∈UI0≤P(D,5s(x)≤\ 对象x1产生的两种误分类代价PCB(Dx)=611, 其中，PD,bs(》=D,ns l6s(x)引 NC(Dx)=5I1,因为PCs(Dx)>NCs(Dx),所 以表1为例，可给出混合邻域决策系统代价 以x∈NEG(D),同理可得{，x4,,xg,x9,x1o}∈ 矩阵，如表2所示。结合定义2和表2，可求出三 NEGg(D)和{，x}∈POSs(D)。由此可知，该混合 支决策的阈值a=7/9,B=1/3。 邻域决策系统的正域为POS(D)={,x},负域为 表2误分类代价矩阵 NEGg(D1)=[x1,X2,X3,x4.X6,X8.X9,X10lo Table 2 Misclassification cost matrix 3算法描述及复杂度分析 状态/动作 X(P) -X(N) ap APP=0 入pw=8 针对混合邻域决策系统，为了有效划分其三 aB ABp =2 ABN =1 支决策边界域中的对象，本文提出了一种面向混 合数据的代价敏感三支决策边界域分类方法，该 dN ANP=4 ANN =0 算法主要分为三个部分。首先，针对混合邻域决 令B=CORE(C)={a4l,根据定义3可计算出核 策系统中的数据，通过混合邻域计算公式计算每 属性子集B下的对象之间的邻域粒度；再根据定 个对象的混合邻域粒度，得到混合邻域决策表的 义6计算出核属性集下决策类D的的正域、负域 正域对象集合，由此基于启发式策略计算核属性 和边界域，具体的计算过程为：由定义3可计算出 集。其次，在此基础上，计算混合邻域决策表中 核属性集B下x的邻域粒度6(x1)={x,2,6,x, 每个对象的邻域粒度，从而计算出每个对象属于 xg,,xo,由此求出x的条件概率P(D5s(x)=5/8< 不同决策类的条件概率，利用三支决策规则将对 a,所以x1∈BNDs(D),同理{2，x4,x5,6,,x8,g,xo}∈ 象分别划分到不同决策类的正域、边界域和负域 BND8(D).BNDg(D)={1,,X.s,60l 中；最后，针对边界域中的对象，分别计算其划分 通过相同的计算可求出： 到正域和负域所产生的误分类代价，通过比较这 POS(D)=0,NEG(D1)=(x3) 两种代价的大小，将边界域中的对象划分到正域 定义7在混合邻域决策系统DN={U,FU 或负域中，为此，算法的流程图1所示。 FC,D,Va,I,中，D,为论域U基于决策属性D的划 算法面向混合数据的代价敏感三支决策边 分，给定属性子集BSC,为了简化公式，用CP和 界域分类方法 (1-CPy分别代替1P(D,6s()和1/(1-P(Dbs(x), 输入混合邻域决策系统DN,邻域参数δ和 对于Yx∈BNDa(D),样本简化后的误分类代价计 阈值a,B; 算公式如下： 输出 核属性集下对不同决策类的正域和 CP'x APN PC(D)=(CPxAp)+((1-CPYxAxr) 负域。 (1-CPy×wP 1)对混合邻域决策系统DN做归一化处理： NCx(D.k)=((1-CPyxAwp)+(CP'xArw) 2)计算决策类DsU/D: 其中，PCa(D)表示在决策类D下将对象x划分到 3)计算邻域粒度6c(x),初始化COREc(D)=O: 正域产生的误分类代价，同理，NC(Dx表示在决 4)对于Vx∈U,若满足6c(x)SD,则将对象x存 策类D,下将对象x划分到负域产生的误分类代价。 入到正域POSc(D)←-POSc(D)U{x; Awp和dpv是代价矩阵中的风险损失值，P(D,l5s(x) 5)对于ya:∈C,分别计算去除每个对象之后 表示在决策类D,下对象x的条件概率。 的特征子集的正域集合POSc-a,(D),若满足 性质1在混合邻域决策系统DN={U,FDU POSc(D)≠POSc-a(D),则将属性a存人到核属性集 FC,D,Va,I,6中，D是对决策属性D的划分，假设属 COREc(D)+COREc(D)U(a;l; 性子集BSC,对于Yx∈BNDs(D,),可得出如下推论： 6)基于核属性集COREe(D),计算对象的邻域 1)如果PCs(Dx)>NCs(Dx),则x∈NEGB(D,): 粒度6 COREe(D()r: 2)如果PCB(Dx)≤NCB(Dx),则x∈POSB(D)。 7)对于Hx∈U,计算对象x属于决策类D,的条 以表1为例，令B=Core(C)={aa},已知D1= 件概率P(D,l6 COREUD)():
决策的阈值， Di表示不同的决策属性，则不同属性 子集下的三支决策规则定义为： POSB(Di) = { x ∈ U|α ⩽ P(Di |δB(x) ) ⩽ 1 } BNDB(Di) = { x ∈ U|β < P(Di |δB(x) ) < α} NEGB(Di) = { x ∈ U|0 ⩽ P(Di |δB(x) ) ⩽ β } P(Di |δB(x)) = |Di ∩δB(x)| |δB(x)| 其中， 。 α = 7/ 9, β = 1/ 3 以表 1 为例，可给出混合邻域决策系统代价 矩阵，如表 2 所示。结合定义 2 和表 2，可求出三 支决策的阈值 。 表 2 误分类代价矩阵 Table 2 Misclassification cost matrix 状态/动作 X(P) ¬X(N) aP λPP = 0 λPN = 8 aB λBP = 2 λBN = 1 aN λNP = 4 λNN = 0 B = CORE(C) = {a4} B D1 B x1 δB(x1) = {x1, x2, x5,x6, x7, x8, x9, x10} x1 P(D1 |δB(x1) ) = 5/ 8 < α x1 ∈ BNDB(D1) {x2, x4, x5, x6, x7, x8, x9, x10} ∈ BNDB(D1) BNDB(D1) = {x1, x2, x4, x5, x6, x7, x8, x9, x10} 令 ,根据定义 3 可计算出核 属性子集 下的对象之间的邻域粒度；再根据定 义 6 计算出核属性集下决策类 的的正域、负域 和边界域，具体的计算过程为：由定义 3 可计算出 核属性集 下 的邻域粒度 ,由此求出 的条件概率 ，所以 ，同理 ，即 。 通过相同的计算可求出： POSB(D1) = Ø，NEGB(D1) = {x3} DN = { U,F D∪ F C , D,Va,Ia,δ} Di U D B ⊆ C CPr (1−CP)r 1 / P(Di δB(xj) ) 1 / (1− P(Di δB(xj) )) ∀xj ∈ BNDB (Di) 定义 7 在混合邻域决策系统 中 ， 为论域 基于决策属性 的划 分，给定属性子集 ，为了简化公式，用 和 分别代替 和 ， 对于 ，样本简化后的误分类代价计 算公式如下： PCB(Di |xj) = CPr ×λPN (CPr ×λPN)+((1−CP)r ×λNP) NCB(Di |xj) = (1−CP)r ×λNP ((1−CP)r ×λNP)+(CPr ×λPN) PCB(Di |x) Di x NCB(Di |x) Di x λNP λPN P(Di |δB(x)) Di x 其中， 表示在决策类 下将对象 划分到 正域产生的误分类代价，同理， 表示在决 策类 下将对象 划分到负域产生的误分类代价。 和 是代价矩阵中的风险损失值， 表示在决策类 下对象 的条件概率。 DN = { U,F D∪ F C , D,Va,Ia,δ} Di D B ⊆ C ∀x ∈ BNDB(Di) 性质 1 在混合邻域决策系统 中， 是对决策属性 的划分，假设属 性子集 ，对于 ，可得出如下推论： PCB(Di |x) > NCB(Di 1) 如果 |x) ，则x ∈NEGB(Di) ； PCB(Di |x) ⩽ NCB(Di 2 ) 如 果 |x) ， 则x ∈POSB(Di) 。 以 表 1 为例，令 B = Core(C) = {a4} ，已知 D1 = {x1, x3, x5, x6, x7, x9} BNDB(D1) = {x1, x2, x4, x5, x6, x7, x8, x9, x10} 和 ，根据定义 7 和性质 1 可将边界域中的对象 划分到正域和负域，具体的计算过程如下： ∀x ∈ BNDB(D1) x1 PCB(D1|x1) = 6/ 11 NCB(D1|x1) = 5/ 11 PCB(D1|x1) > NCB(D1|x1) x1 ∈ NEGB(D1) {x2, x4, x6, x8, x9, x10} ∈ NEGB(D1) {x5, x7} ∈ POSB(D1) POSB(D1) = {x5, x7} NEGB(D1) = {x1, x2, x3, x4, x6, x8, x9, x10} 对于 ，根据定义 7 可求出划分 对象 产生的两种误分类代价 ， ，因为 ， 所 以 ，同理可得 和 。由此可知，该混合 邻域决策系统的正域为 ，负域为 。 3 算法描述及复杂度分析 针对混合邻域决策系统，为了有效划分其三 支决策边界域中的对象，本文提出了一种面向混 合数据的代价敏感三支决策边界域分类方法，该 算法主要分为三个部分。首先，针对混合邻域决 策系统中的数据，通过混合邻域计算公式计算每 个对象的混合邻域粒度，得到混合邻域决策表的 正域对象集合，由此基于启发式策略计算核属性 集。其次，在此基础上，计算混合邻域决策表中 每个对象的邻域粒度，从而计算出每个对象属于 不同决策类的条件概率，利用三支决策规则将对 象分别划分到不同决策类的正域、边界域和负域 中；最后，针对边界域中的对象，分别计算其划分 到正域和负域所产生的误分类代价，通过比较这 两种代价的大小，将边界域中的对象划分到正域 或负域中，为此，算法的流程图 1 所示。 算法 面向混合数据的代价敏感三支决策边 界域分类方法 DN δ α β 输入 混合邻域决策系统 ，邻域参数 和 阈值 ， ； 输出 核属性集下对不同决策类的正域和 负域。 1）对混合邻域决策系统 DN 做归一化处理； 2）计算决策类 Di ⊆ U/ D ； 3）计算邻域粒度 δC(x),初始化 COREC(D)= Ø ； ∀x ∈ U δC(x) ⊆ Di x POSC(D) ← POSC(D)∪{x} 4）对于 ，若满足 ，则将对象 存 入到正域 ； ∀ai ∈ C POSC−{ai}(D) POSC(D) , POSC−{ai}(D) ai COREC(D) ← COREC(D)∪{ai} 5）对于 ，分别计算去除每个对象之后 的特征子集的正域集合 ，若满足 ，则将属性 存入到核属性集 ； COREC(D) δCOREC (D)(x) 6）基于核属性集 ，计算对象的邻域 粒度 ； ∀x ∈ U x Di P(Di |δCOREC (D)(x)) 7）对于 ，计算对象 属于决策类 的条 件概率 ： ·414· 智 能 系 统 学 报 第 17 卷
第2期 周阳阳，等：面向混合数据的代价敏感三支决策边界域分类方法 ·415· ①若a≤P(D6 CORE(Dy(x)≤1，则将对象x划分 计算每个对象的混合邻域粒度，其时间复杂度为 到决策类D:的正域POSCORE(D:); O(UPICOREc(D)D;7)计算各决策类正域、边界域 ②否则，若0≤P(D6 CORE(D(x)≤B,则将对象 和负域，其时间复杂度为OUD;8)结合代价敏感 x划分到决策类D,的负域NEGcoREe(D); 划分边界域中的对象，其时间复杂度为 ③否则将对象x划分到决策类D:的边界域 O(BNDCORE(D,)D。综上所述，算法最坏情况下的 BNDCOREe(D:); 时间复杂度是OUIC);由于存储空间主要用于 8)对于Yx∈BNDCORE,(D)计算PCCORE(Dx)和 存放数据，因此算法的空间复杂度为OU川C)。 NCCORE (D) ①若满足PCCORE.(Dx)>NCcoRee(D,,),则将 4实验比较与分析 对象x划分到决策类D,的负域NEGcoRES(D,); 为了验证本文方法对边界域对象划分的可行 ②否则将对象x划分到决策类D,的正域 性和有效性，实验从UCI中选取了10个混合数据 POSCORE(D:); 集进行实验测试与分析；选用分类准确率、权衡 9)输出划分结果正域POSCOREe(D,),负域 因子、误分类损失和时间作为评价指标，对实验 NEgCoRE(D,)。I算法结束。 结果进行对比与分析。 4.1数据集与实验设置 混合邻域决策 系统DN 为了更好地说明所提出算法的普适性，本文 根据数据集的来源和规模两个方面，从国际公开 归一化混合邻域决策系统DN 计算决策类D: 的机器学习UCI数据库中选取了10个数据集进 计算混合邻域粒度x) 行实验结果的对比和分析，数据集的信息描述如 表3所示。表中Speaker Accent和Ionosphere数据 计算正域POSc(D)、POSc4(D) 集中包含连续型数据，Phishing Websites和Stu- 和核属性集CORE(D) dent Evaluation数据集中包含离散型数据；其余数 据集均包含连续型和离散型数据；这些数据集来 计算条件概率 自欺诈分析、医学诊断、信号处理和教育评价等 P (D.16CORE(x)) 应用领域。同时为了消除量纲的影响，对所有数 据集中的连续型数据进行归一化处理。本次实验 P(Dl5coRE》≥a> 的运行环境为：Winl0,Intel(R)Core(TM,i5-6500 N CPU@3.20GHz3.19GHz和8GB内存，用Py- thon编程语言实现算法设计。 P(D.lcoRE(x))p 4.2评价指标 实验将从准确率、权衡因子、误分类损失和 运行时间4种度量指标2对划分结果进行分析， 边界域BNDE(D, 计算误分类代价 定义如下： PC和NC POS(D)nD 准确率：Acc= POS(D,) 正域 负域 POScoRE(D) PC>NC NEGcRE(D,) 权衡因子：F=2 xAccxCov Acc+Cov 误分类损失：Cost=b×hp+nn×drp 图1算法流程图 式中：POS(D)和D表示正域和决策类，nb和nn分别 Fig.1 The flowchart of algorithm 表示边界域、负域中的对象个数；p和dnp分别表 算法时间复杂度分析： 示将属于某一决策类的对象错误划分到该类别的 1)算法的时间复杂度为OIUI川C:2)划分决 边界域和负域中产生的损失；由于本文算法的输 策类所需的时间复杂度为OU);3)在属性全集 出只包含正域和负域，因此Cov=1。本实验的风 下，通过混合邻域计算公式得出每个对象的混合 险损失参数为p=0.3,dp=0.7。 邻域粒度，其时间复杂度为OUIC);4)计算正域 4.3实验结果与分析 对象的时间复杂度为OU0;5)计算核属性集的 4.3.1参数pw和wp对划分结果的影响 时间复杂度为OQUPIC);6)在核属性集CORE下， 在混合邻域决策系统中，参数dpw和dwP通过影
α ⩽ P(Di |δCOREC (D)(x)) ⩽ 1 x Di POSCOREC (Di) ①若 ，则将对象 划分 到决策类 的正域 ； 0 ⩽ P(Di |δCOREC (D)(x)) ⩽ β x Di NEGCOREC (Di) ②否则，若 ，则将对象 划分到决策类 的负域 ； x Di BNDCOREC (Di) ③否则将对象 划分到决策类 的边界域 ； ∀xb ∈ BNDCOREC (Di) PCCOREC (Di |xj) NCCOREC (Di |xj) 8）对于 计算 和 ： PCCOREC (Di |xj) > NCCOREC (Di |xj) xj Di NEGCOREC (Di) ①若满足 ，则将 对象 划分到决策类 的负域 ； xb Di POSCOREC (Di) ②否则将对象 划分到决策类 的正域 ； POSCOREC (Di) NEGCOREC (Di) 9 ）输出划分结果正域 ，负域 。//算法结束。 混合邻域决策 系统 DN 归一化混合邻域决策系统 DN; 计算决策类 Di ; 计算混合邻域粒度 δ(xi ) 计算正域 POSC (D)、POSC-(ai} (D) 和核属性集 COREC (D) 计算条件概率 P (Di |δCORE (xi )) P (Di |δCORE (xi ))≥α P (Di |δCORE (xi ))<β 边界域 BNDCORE (Di ) 计算误分类代价 PC 和 NC 正域 POSCORE (Di ) 负域 NEGCORE (Di ) PC>NC N N N Y Y Y 图 1 算法流程图 Fig. 1 The flowchart of algorithm 算法时间复杂度分析： O(|U||C|) O(|U|) O(|U| 2 |C|) O(|U|) O(|U| 2 |C|) CORE 1）算法的时间复杂度为 ；2）划分决 策类所需的时间复杂度为 ；3）在属性全集 下，通过混合邻域计算公式得出每个对象的混合 邻域粒度，其时间复杂度为 ；4）计算正域 对象的时间复杂度为 ；5）计算核属性集的 时间复杂度为 ；6）在核属性集 下 ， O(|U| 2 |COREC(Di)|) O(|U|) O(|BNDCOREC (Di)|) O(|U| 2 |C|) O(|U||C|) 计算每个对象的混合邻域粒度，其时间复杂度为 ；7）计算各决策类正域、边界域 和负域，其时间复杂度为 ；8）结合代价敏感 划分边界域中的对象，其时间复杂度为 。综上所述，算法最坏情况下的 时间复杂度是 ；由于存储空间主要用于 存放数据，因此算法的空间复杂度为 。 4 实验比较与分析 为了验证本文方法对边界域对象划分的可行 性和有效性，实验从 UCI 中选取了 10 个混合数据 集进行实验测试与分析；选用分类准确率、权衡 因子、误分类损失和时间作为评价指标，对实验 结果进行对比与分析。 4.1 数据集与实验设置 为了更好地说明所提出算法的普适性，本文 根据数据集的来源和规模两个方面，从国际公开 的机器学习 UCI 数据库中选取了 10 个数据集进 行实验结果的对比和分析，数据集的信息描述如 表 3 所示。表中 Speaker Accent 和 Ionosphere 数据 集中包含连续型数据，Phishing Websites 和 Student Evaluation 数据集中包含离散型数据；其余数 据集均包含连续型和离散型数据；这些数据集来 自欺诈分析、医学诊断、信号处理和教育评价等 应用领域。 同时为了消除量纲的影响，对所有数 据集中的连续型数据进行归一化处理。本次实验 的运行环境为：Win10, Intel(R)Core(TM), i5-6 500 CPU @ 3.20 GHz 3.19 GHz 和 8 GB 内存，用 Python 编程语言实现算法设计。 4.2 评价指标 实验将从准确率、权衡因子、误分类损失和 运行时间 4 种度量指标[24] 对划分结果进行分析， 定义如下： Acc = POS(Di)∩ Di POS(Di) 准确率： F = 2× Acc×Cov Acc+Cov 权衡因子： 误分类损失： Cost = nb ×λbp +nn ×λnp POS(Di) Di nb nn λbp λnp Cov = 1 λbp = 0.3 λnp = 0.7 式中： 和 表示正域和决策类， 和 分别 表示边界域、负域中的对象个数； 和 分别表 示将属于某一决策类的对象错误划分到该类别的 边界域和负域中产生的损失；由于本文算法的输 出只包含正域和负域，因此 。本实验的风 险损失参数为 ， 。 4.3 实验结果与分析 4.3.1 参数 λPN和 λNP对划分结果的影响 在混合邻域决策系统中，参数 λPN和 λNP通过影 第 2 期 周阳阳，等：面向混合数据的代价敏感三支决策边界域分类方法 ·415·