第14卷第6期 智能系统学报 Vol.14 No.6 2019年11月 CAAI Transactions on Intelligent Systems Nov.2019 D0:10.11992/tis.201905049 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20190830.1438.004.html 基于三支决策的序列数据代价敏感分类算法 刘牧雷，徐菲菲 (上海电力学院计算机科学与技术学院，上海200090)】 摘要：代价敏感分类区别于一般分类方法，更关注高代价类别的分类准确性而容忍全局分类的准确性。三支 决策作为一种代价敏感分类问题的解决思路，缺乏对序列数据的支持。结合LSTM模型处理序列数据的能力， 提出一种使用三支决策(3WD)改进的序列数据分类方法。方法经过LSTM网络对原数据进行粗分类；对分类 结果进行整体代价评估：最终，对高风险分类进行延迟或拒绝处理。方法在4个数据集上进行了测试，并进行 了2组对比实验。实验结果表明：本文方法在不改变LSTM模型的情况下，对LSTM模型的分类结果进行了代 价区分。 关键词：代价敏感：三支决策；长短期记忆网络；序列数据分类；分类算法；高代价类别：代价评估 中图分类号：TP181文献标志码：A文章编号：1673-4785(2019)06-1255-07 中文引用格式：刘牧雷，徐菲菲.基于三支决策的序列数据代价敏感分类算法.智能系统学报，2019,14(6)：1255-1261. 英文引用格式：LIU Mulei,,XU Feifei..A sequence data,cost-sensitive classification algorithm based on three-way decisionsJ. CAAI transactions on intelligent systems,2019,14(6):1255-1261. A sequence data,cost-sensitive classification algorithm based on three-way decisions LIU Mulei,XU Feifei (School of Computer Science and Technology,Shanghai University of Electric Power,Shanghai 200090,China) Abstract:Cost-sensitive classification is different from the general classification method,which pays more attention to the classification accuracy of high-cost categories,but tolerates the accuracy of global classification.Three-way de- cisions are a solution to a cost-sensitive classification problem and lack support for sequence data.Combined with the ability of the LSTM model in sequence data processing,a method for classifying sequence data a using three-way de- cision method (3WD)is proposed.First,a general classification of the original data was done through the LSTM net- work;second,an overall cost estimate was performed on the classification result of step one;finally,the high-risk result was delayed or rejected.Methods were tested on four data sets and two sets of comparative experiments were per- formed.Experimental results showed that the new method distinguished the classification results of the LSTM model without changing the original structure. Keywords:cost-sensitive;three-way decision;LSTM:sequence data classification;classification algorithm;high-cost categorie;cost estimate 当前，LSTM作为深度学习的一种处理序列 方式来使分类器获得对某一类代价敏感类别更高 数据最为流行的解决方案，拥有着较传统方案更 的关注从而实现减少整体的代价。但是这种方 加实用性强且准确率高的特点②。但是，基于深 法的缺点如前文所述。为了训练对高代价分类敏 度学习的代价敏感决策仍未得到主流的研究关 感的模型，筛选出的数据集将会面临严重的数据 注。当前的研究重点多集中于如何更高效的获得 不平衡问题。而无论是填充或者再平衡的方式， 精确的整体准确率。在有关于深度学习的代价敏 都会使原数据集的结构改变。其次，无论是对 感分类或决策问题上，当前的算法常见解决方案 数据集的预处理还是对运行参数或者模型结构的 多集中于通过对数据的预处理和运行参数调整的 调整，都与具体问题相关性较大”。对于不同的 具体问题，数据清洗和参数调整或模型调整的优 收稿日期：2019-05-26.网络出版日期：2019-08-30 通信作者：徐菲菲.E-mail:xufeifeil983@hotmail.com 劣与模型设计者的经验与对问题的了解有着较大
DOI: 10.11992/tis.201905049 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20190830.1438.004.html 基于三支决策的序列数据代价敏感分类算法 刘牧雷，徐菲菲 （上海电力学院 计算机科学与技术学院，上海 200090） 摘 要：代价敏感分类区别于一般分类方法，更关注高代价类别的分类准确性而容忍全局分类的准确性。三支 决策作为一种代价敏感分类问题的解决思路，缺乏对序列数据的支持。结合 LSTM 模型处理序列数据的能力， 提出一种使用三支决策 (3WD) 改进的序列数据分类方法。方法经过 LSTM 网络对原数据进行粗分类；对分类 结果进行整体代价评估；最终，对高风险分类进行延迟或拒绝处理。方法在 4 个数据集上进行了测试，并进行 了 2 组对比实验。实验结果表明：本文方法在不改变 LSTM 模型的情况下，对 LSTM 模型的分类结果进行了代 价区分。 关键词：代价敏感；三支决策；长短期记忆网络；序列数据分类；分类算法；高代价类别；代价评估 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2019)06−1255−07 中文引用格式：刘牧雷, 徐菲菲. 基于三支决策的序列数据代价敏感分类算法 [J]. 智能系统学报, 2019, 14(6): 1255–1261. 英文引用格式：LIU Mulei, XU Feifei. A sequence data, cost-sensitive classification algorithm based on three-way decisions[J]. CAAI transactions on intelligent systems, 2019, 14(6): 1255–1261. A sequence data, cost-sensitive classification algorithm based on three-way decisions LIU Mulei，XU Feifei (School of Computer Science and Technology, Shanghai University of Electric Power, Shanghai 200090, China) Abstract: Cost-sensitive classification is different from the general classification method, which pays more attention to the classification accuracy of high-cost categories, but tolerates the accuracy of global classification. Three-way decisions are a solution to a cost-sensitive classification problem and lack support for sequence data. Combined with the ability of the LSTM model in sequence data processing, a method for classifying sequence data a using three-way decision method (3WD) is proposed. First, a general classification of the original data was done through the LSTM network; second, an overall cost estimate was performed on the classification result of step one; finally, the high-risk result was delayed or rejected. Methods were tested on four data sets and two sets of comparative experiments were performed. Experimental results showed that the new method distinguished the classification results of the LSTM model without changing the original structure. Keywords: cost-sensitive; three-way decision; LSTM; sequence data classification; classification algorithm; high-cost categorie; cost estimate 当前，LSTM 作为深度学习的一种处理序列 数据最为流行的解决方案，拥有着较传统方案更 加实用性强且准确率高的特点[1-2]。但是，基于深 度学习的代价敏感决策仍未得到主流的研究关 注。当前的研究重点多集中于如何更高效的获得 精确的整体准确率。在有关于深度学习的代价敏 感分类或决策问题上，当前的算法常见解决方案 多集中于通过对数据的预处理和运行参数调整的 方式来使分类器获得对某一类代价敏感类别更高 的关注从而实现减少整体的代价[3]。但是这种方 法的缺点如前文所述。为了训练对高代价分类敏 感的模型，筛选出的数据集将会面临严重的数据 不平衡问题。而无论是填充或者再平衡的方式， 都会使原数据集的结构改变[4]。其次，无论是对 数据集的预处理还是对运行参数或者模型结构的 调整，都与具体问题相关性较大[5-7]。对于不同的 具体问题，数据清洗和参数调整或模型调整的优 劣与模型设计者的经验与对问题的了解有着较大 收稿日期：2019−05−26. 网络出版日期：2019−08−30. 通信作者：徐菲菲. E-mail：xufeifei1983@hotmail.com. 第 14 卷第 6 期 智 能 系 统 学 报 Vol.14 No.6 2019 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2019
·1256· 智能系统学报 第14卷 的关系。并且，对于不同的问题，相同的解决方 在决策粗糙集公式化描述中，X是全集U的 案并不能保证稳定的表现。在不同的数据集之 子集，状态集合可以表示为2={X,X,X和X 间，相同的数据清洗和参数调整所带来的模型上 分别表示属于X和不属于X。为了方便，子集和 的改变影响是不同的。 子集的状态都使用X来表示。状态X对应的动 基于此，本文提出的将三支决策运用于深度 作集合为A={PB,N,其中P、B、N分别表示3 学习模型能够一定程度上解决上述问题。1)三支 种判定动作，即x∈POS(X)、x∈BND(X)、x∈NEG(X)。 决策算法的理论基础为粗糙集理论，以分类置信 三支决策的损失函数由各个动作带来的损失决定。 度为基础判断决策或分类代价。从算法逻辑的角 如表1所示，其中p、BP、p表示当x属于X 度，三支决策算法要求更高的全局分类的准确性 时采取动作P、B、N产生的损失，w、BN、w表 而不是对单独高代价类的分类，此特点使得三支 示当对象属于X时采取动作P、B、N时产生的损失。 决策算法与更高的更广泛的分类算法优点相结 合，在前置分类器不用做出改动或者调整的情况 表1三支决策的损失函数 Table 1 Loss function of 3WD 下降低决策的风险。2)三支决策算法倾向于判断 单独决策。因此，新改进的算法将避免在正常预 动作 女 -X 处理的前提下，将避免因平衡特殊分类类别而造 App N 成的数据重新扩展或裁剪，从而进一步影响数据 B ABP ABN 平衡问题。综上，结合三支决策的LSTM模型可 ANP ANN 以在原先的深度模型的基础上，进一步增强模型 根据最小风险决策规则： 在代价敏感问题上的表现。 P)当P,(W[x≥a时，x∈POS(X: 1相关工作 B)当B<P,(X[x)<a时，x∈BND(X): N)当P,(X[x)≤B时，x∈NEG(X): 1.1三支决策 其中 三支决策⑧是Y.Y.Yao由概率粗糙集理论提 APN-ABN Q= (1) 出的一种新决策思想。相较于传统的“是，否”二 (APN-ABN)+(ABP-APP) 支决策而言，三支决策提出了一种不同但是更合 B= ABN -ANN (☑BN-NN)+(Np-p) (2) 理的决策思想，即当对象当前提供的信息不足以 支撑决策时，采用延迟决策，等待更多信息来完 且 成最终决策。所以，三支决策可以规避分类信息 0≤B<a≤1 (3) 不足时盲目决策造成的风险。 1.2长短时记忆网络 三支决策在进行分类决策前，需对样本进行 LSTM是由Hoehreiterhe与Schmiduhber于 域的划分。划分的原理基于粗糙集理论。按照粗 1997年提出后经过大量的改进，目前被广泛应用网， 糙集的定义，根据元素x是否属于概念A,x与A 成为目前处理序列与时序问题上的热门方案。 将分为3种关系：x∈A,x∈A,x∈BND(A)。由此， LSTM是由一般的RNN改进而来。LSTM与一般 考虑一般分类问题，将元素x是否符合概念A作 的RNN的主要区别是在LSTM中的神经元不再 为分类标准，将可能会得到x∈BND(A),即元素x 是由单纯的神经元组成而是由4个功能不同的门 属于概念A的边界域。由此，可得知决策粗糙集 来共同作用。其中包括了输入门、输出门、状态 在代价敏感分类问题上的整体思路。 门，以及遗忘门。具体的结构如图1所示。 tanh (X 中 图1LSTM网络结构 Fig.1 LSTM network structure
的关系。并且，对于不同的问题，相同的解决方 案并不能保证稳定的表现。在不同的数据集之 间，相同的数据清洗和参数调整所带来的模型上 的改变影响是不同的。 基于此，本文提出的将三支决策运用于深度 学习模型能够一定程度上解决上述问题。1) 三支 决策算法的理论基础为粗糙集理论，以分类置信 度为基础判断决策或分类代价。从算法逻辑的角 度，三支决策算法要求更高的全局分类的准确性 而不是对单独高代价类的分类，此特点使得三支 决策算法与更高的更广泛的分类算法优点相结 合，在前置分类器不用做出改动或者调整的情况 下降低决策的风险。2) 三支决策算法倾向于判断 单独决策。因此，新改进的算法将避免在正常预 处理的前提下，将避免因平衡特殊分类类别而造 成的数据重新扩展或裁剪，从而进一步影响数据 平衡问题。综上，结合三支决策的 LSTM 模型可 以在原先的深度模型的基础上，进一步增强模型 在代价敏感问题上的表现。 1 相关工作 1.1 三支决策 三支决策[8] 是 Y.Y.Yao 由概率粗糙集理论提 出的一种新决策思想。相较于传统的“是，否”二 支决策而言，三支决策提出了一种不同但是更合 理的决策思想，即当对象当前提供的信息不足以 支撑决策时，采用延迟决策，等待更多信息来完 成最终决策。所以，三支决策可以规避分类信息 不足时盲目决策造成的风险。 x A x A x ∈ A x ∈ ¬A x ∈ BND(A) x A x ∈ BND(A) x A 三支决策在进行分类决策前，需对样本进行 域的划分。划分的原理基于粗糙集理论。按照粗 糙集的定义，根据元素 是否属于概念 ， 与 将分为 3 种关系： , , 。由此， 考虑一般分类问题，将元素 是否符合概念 作 为分类标准，将可能会得到 ，即元素 属于概念 的边界域。由此，可得知决策粗糙集 在代价敏感分类问题上的整体思路。 X U Ω = {X,¬X} X ¬X X X X X ∧ = {P,B,N} P、B、N x ∈ POS(X) x ∈ BND(X) x ∈ NEG(X) λPP、λBP、λNP x X P、B、N λPN、λBN、λNN ¬X P、B、N 在决策粗糙集公式化描述中， 是全集 的 子集，状态集合可以表示为 ， 和 分别表示属于 和不属于 。为了方便，子集和 子集的状态都使用 来表示。状态 对应的动 作集合为 ，其中 分别表示 3 种判定动作，即 、 、 。 三支决策的损失函数由各个动作带来的损失决定。 如表 1 所示，其中 表示当 属于 时采取动作 产生的损失， 表 示当对象属于 时采取动作 时产生的损失。 表 1 三支决策的损失函数 Table 1 Loss function of 3WD 动作 X ¬X P λPP λPN B λBP λBN N λNP λNN 根据最小风险决策规则： (P) 当 Pr (X|[x]) ⩾ α 时，x ∈ POS(X); (B) 当 β < Pr (X|[x]) < α 时，x ∈ BND(X); (N) 当 Pr (X|[x]) ⩽ β 时，x ∈ NEG(X); 其中 α = λPN −λBN (λPN −λBN)+(λBP −λPP) (1) β = λBN −λNN (λBN −λNN)+(λNP −λNP) (2) 且 0 ⩽ β < α ⩽ 1 (3) 1.2 长短时记忆网络 LSTM 是由 Hoehreiterhe 与 Schmiduhber 于 1997 年提出后经过大量的改进，目前被广泛应用[9] ， 成为目前处理序列与时序问题上的热门方案。 LSTM 是由一般的 RNN 改进而来。LSTM 与一般 的 RNN 的主要区别是在 LSTM 中的神经元不再 是由单纯的神经元组成而是由 4 个功能不同的门 来共同作用。其中包括了输入门、输出门、状态 门，以及遗忘门。具体的结构如图 1 所示。 × × × × × × × × × + + + ht−1 xt−1 xt xt+1 h ht+1 t tanh σ tanh σ σ tanh σ σ σ σ tanh tanh σ σ tanh 图 1 LSTM 网络结构 Fig. 1 LSTM network structure ·1256· 智 能 系 统 学 报 第 14 卷
第6期 刘牧雷，等：基于三支决策的序列数据代价敏感分类算法 ·1257· LSTM的独特结构是为了使其能够解决长期 错误分类的代价；P(x)表示算法将x划分至类别 依赖问题而专门设计的。不同于RNN网络， j的概率；c(亿，》表示将i分类划分至j所产生的 LSTM的重复结构是由更加复杂的3个门相互连 代价。 接而成。包括遗忘门、输人门与输出门。 对于每个类别i,L(x,)表示x所有可能的划 式(4)(9)描述了细胞内各个门的处理流程。 分结果的代价的概率和。故由式(10)知，当分类 f=(W[h-1,x:]+b) (4) 代价最小时，其分类结果P(x)不一定取到最大 i=r(W[h-1,+b) (5) 值。即为了得到更小的分类代价，可能会放弃最 C,tanh(Wc.[h-1.x]+bc) (6) 大的分类结果。 C:=f-C-+iC (7) 在如何使算法获得倾向性的问题上，有两种 o=c(W。·[h-1,x]+bo) (8) 经典算法：1)通过预处理，使算法对某些结果具 h =o-tanh (C) (9) 式(4)描述了遗忘门决定了当细胞更新时细 有敏感性，此方法称为rescaling;2)希望通过以 胞状态会丢弃什么信息。该门会读取h-1和x, 代价为基准修改不同分类在算法中的成员可能 输出在[0，)之间的数值与原先细胞状态C-1相 性，从而产生不同的倾向性。此方法称为rewei-- 结合。其中，1表示完全保留，0表示完全遗忘。 ghted。 其中，h-1表示上一个细胞的输出，x表示当前细 2基于LSTM的三支决策分类算法 胞的输入，c表示sigmod函数。 式(5)描述输入门决定了让多少新的信息 基于三支决策的LSTM算法在原有的 加入到细胞状态中。第一步，细胞输入x与细胞 LSTM基础上，增加了三支决策步骤，对前端分类 的上个输出h,-1会通过sigmod元来决定更新的 器给出的预测结果做出接受、拒绝、延迟3种不 内容。 同的方案，算法流程如图2所示。 式(6)描述了更新内容C。与式（⑤）同时，同 样的输入会通过一个tanh元，生成备用的更新内 容C。 前瓷分类器 式(7)描述了更新内容C,。将式(5)与式 延迟 (6两部分结果相乘，将细胞状态由C-1更新至C。 最终输出数据由式(8)的输出与当前细胞状 拒绝 态的一部分共同决定输出的最终值，如式(9)描述。 以上为LSTM模型的基本工作流。 图2基于LSTM的三支决策算法流程 Fig.2 Flow of 3WD based on LSTM 1.3代价敏感分类 一般的，对于分类算法的研究的核心与重点 算法包括两部分：1)前置分类器，用于初步 为如何取得更高的分类准确率，但事实上，只要 分类：2)三支决策，考虑决策风险，通过算法的判 有误差存在，分类过程总会产生代价。而代价敏 断降低决策风险。 感分类就是关注如何使分类过程中产生的代价最 2.1前置分类器 小。根据问题的难易程度，代价敏感问题常被分 前置分类器的作用主要体现在前置分类器的 为二分类与多分类问题。对于二分类问题，目前 分类精度最终决定了整体上的分类效果。此后的 大部分的代价敏感分类多是从非代价敏感分类算 三支决策对前置分类器的分类结果做出评判，决 法加以转化得到的。 定接受、拒绝、或者延迟推断。对于LSTM分类 结合上述，可将代价敏感分类等价于一个优 器，主要用来解决分类和时序问题预测。输出包 化问题：将实例使用分类算法A划分至类别1时， 括预测结果C和预测的分类概率p。分类概率p 使损失函数L(x,)达到最小o: 用于下一步中三支决策算法来判断是否采纳分类 Lx.=∑PUc6, (10) 结果。 2.2三支决策 式中：x表示一个实例；L(,)表示x的类别为i时 三支决策对前置分类器给出的结果进行分
LSTM 的独特结构是为了使其能够解决长期 依赖问题而专门设计的。不同 于 RNN 网络， LSTM 的重复结构是由更加复杂的 3 个门相互连 接而成。包括遗忘门、输入门与输出门。 式 (4)~(9) 描述了细胞内各个门的处理流程。 ft = σ ( Wf ·[ht−1, xt]+bf ) (4) it = σ(Wi ·[ht−1, xt]+bi) (5) Cet = tanh(WC ·[ht−1 , xt]+bC) (6) Ct = ft ·Ct−1 +it ·Cet (7) ot = σ(Wo ·[ht−1, xt]+bo) (8) ht = ot ·tanh(Ct) (9) ht−1 xt [0,1] Ct−1 ht−1 xt σ 式 (4) 描述了遗忘门决定了当细胞更新时细 胞状态会丢弃什么信息。该门会读取 和 ， 输出在 之间的数值与原先细胞状态 相 结合。其中，1 表示完全保留，0 表示完全遗忘。 其中， 表示上一个细胞的输出， 表示当前细 胞的输入， 表示 sigmod 函数。 xt ht−1 式 (5) 描述输入门决定了让多少新的信息 加入到细胞状态中。第一步，细胞输入 与细胞 的上个输出 会通过 sigmod 元来决定更新的 内容。 Cet Cet 式 (6) 描述了更新内容 。与式 (5) 同时，同 样的输入会通过一个 tanh 元，生成备用的更新内 容 。 Ct Ct−1 Ct 式 (7) 描述了更新内容 。将式 (5) 与式 (6) 两部分结果相乘，将细胞状态由 更新至 。 最终输出数据由式 (8) 的输出与当前细胞状 态的一部分共同决定输出的最终值，如式 (9) 描述。 以上为 LSTM 模型的基本工作流。 1.3 代价敏感分类 一般的，对于分类算法的研究的核心与重点 为如何取得更高的分类准确率，但事实上，只要 有误差存在，分类过程总会产生代价。而代价敏 感分类就是关注如何使分类过程中产生的代价最 小。根据问题的难易程度，代价敏感问题常被分 为二分类与多分类问题。对于二分类问题，目前 大部分的代价敏感分类多是从非代价敏感分类算 法加以转化得到的。 A I L(x,i) 结合上述，可将代价敏感分类等价于一个优 化问题: 将实例使用分类算法 划分至类别 时， 使损失函数 达到最小[10] ： L(x,i) = ∑ j P(j|x) c (i, j) (10) 式中：x 表示一个实例； L(x,i) 表示 x 的类别为 i 时 P(j|x) x j c (i, j) i j 错误分类的代价； 表示算法将 划分至类别 的概率； 表示将 分类划分至 所产生的 代价。 i L(x,i) x P(j|x) 对于每个类别 ， 表示 所有可能的划 分结果的代价的概率和。故由式 (10) 知，当分类 代价最小时，其分类结果 不一定取到最大 值。即为了得到更小的分类代价，可能会放弃最 大的分类结果。 在如何使算法获得倾向性的问题上，有两种 经典算法：1) 通过预处理，使算法对某些结果具 有敏感性，此方法称为 rescaling[11] ；2) 希望通过以 代价为基准修改不同分类在算法中的成员可能 性，从而产生不同的倾向性。此方法称为 reweighted[12]。 2 基于 LSTM 的三支决策分类算法 基于三支决策 的 LST M 算法在原有 的 LSTM 基础上，增加了三支决策步骤，对前端分类 器给出的预测结果做出接受、拒绝、延迟 3 种不 同的方案，算法流程如图 2 所示。 分类 三支决策 结果 前置分类器 延迟 拒绝 接受 图 2 基于 LSTM 的三支决策算法流程 Fig. 2 Flow of 3WD based on LSTM 算法包括两部分：1) 前置分类器，用于初步 分类；2) 三支决策，考虑决策风险，通过算法的判 断降低决策风险。 2.1 前置分类器 C p p 前置分类器的作用主要体现在前置分类器的 分类精度最终决定了整体上的分类效果。此后的 三支决策对前置分类器的分类结果做出评判，决 定接受、拒绝、或者延迟推断。对于 LSTM 分类 器，主要用来解决分类和时序问题预测。输出包 括预测结果 和预测的分类概率 。分类概率 用于下一步中三支决策算法来判断是否采纳分类 结果。 2.2 三支决策 三支决策对前置分类器给出的结果进行分 第 6 期 刘牧雷，等：基于三支决策的序列数据代价敏感分类算法 ·1257·
·1258· 智能系统学报 第14卷 析。根据式(1)(3)，可以得出相应的判断代价O。 数据集均为分类任务。 将根据前置分类器的分类结果X,与由对应 PM2.5数据集来自于UCI数据库，该数据集 的损失函数A计算出的代价，由判断规则(PI)、 记录了从2010年1月1日至2014年12月31日 (Bl)、ND判断，给出相应的决策建议。 北京市的空气质量指数和气象数据。数据集为时 (PIi)FPr(Xu)≥a,THEN 1,∈POS(X) 间序列数据，特征为连续特征，任务可作为分类 (Bli)IF B:Pr(Xlu)pi≥B: iEbnd ELSE: ie neg 6)d=计算整体代价 )Fd>目标值d': GOTO 2 1000 END 500 3实验与结果 20 实验在自建实验平台中运行。实验平台包 括4台服务器，每台服务器均使用相同的配置。 20 每台服务器有6个CPU,主频2.5GHz,运行内存 10000 20000 30000 40000 16GB。 时间/d 测试数据集来自UCI开放数据集中的Beijing 图3原始数据集中的特征分布 PM2.5 Data Set International airline passengerso Fig.3 Frequency of features in this dataset 20 101520 25 30 10152025 30 天数/d 天数/d (a)2010-06 (b)2011-06
析。根据式 (1)~(3)，可以得出相应的判断代价 Ø。 X λ 将根据前置分类器的分类结果 ，与由对应 的损失函数 计算出的代价，由判断规则 (Pli)、 (Bli)、(Nli) 判断，给出相应的决策建议。 (Pli)IF Pr(X|ui) ⩾ αi , THEN ui ∈ POS(X) (Bli) IF βi pi ⩾ β i ∈ bnd ELSE: i ∈ neg 6) d = 计算整体代价 d > d ′ 7) IF 目标值 : GOTO 2 END 3 实验与结果 实验在自建实验平台中运行。实验平台包 括 4 台服务器，每台服务器均使用相同的配置。 每台服务器有 6 个 CPU，主频 2.5 GHz，运行内存 16 GB。 测试数据集来自 UCI 开放数据集中的 Beijing PM2.5 Data Set 与 International airline passengers。 数据集均为分类任务。 PM2.5 数据集来自于 UCI 数据库，该数据集 记录了从 2010 年 1 月 1 日至 2014 年 12 月 31 日 北京市的空气质量指数和气象数据。数据集为时 间序列数据，特征为连续特征，任务可作为分类 或回归任务。数据一共 43 824 条记录，特征共 13 个，部分数据缺失。 tn−i tn 数据集中包括了时间，当日的温度、湿度、气 压、风向、累计风速、累计降雨/降雪量、PM2.5 指 数 共 1 3 个数据。其中 的 PM2. 5 指数为当 日 PM2.5 值，为连续实数。当预测 PM2.5 值时，问题 为回归问题。若以判断 PM2.5 区间作为空气质量 判断时，问题为分类问题。本例中，将原数据集 中的 PM2.5 均分为 4 个区间，从小到大分别标记 为 [ 优，良，一般，差 ]4 类。根据前 的气象数 据，预测 的空气质量。 图 3 表示了原数据集中，PM2.5 与气象数据 的关系。图 4 表示了两段分类结果的分布信息。 0 10 000 20 000 30 000 40 000 时间/d 1 000 0 25 25 1 025 1 000 500 20 20 0 0 0 风速/ (m·s−1 ) 降雪量/ mm 降雨量/ mm −25 0 0 排放量/ (ug·m−3 ) 湿度/ °C 温度/ °C 气压/ hPa 图 3 原始数据集中的特征分布 Fig. 3 Frequency of features in this dataset 20 15 10 5 0 5 10 15 20 25 30 时刻 天数/d 20 15 10 5 0 5 10 15 20 25 30 时刻 天数/d (a) 2010-06 (b) 2011-06 ·1258· 智 能 系 统 学 报 第 14 卷
第6期 刘牧雷，等：基于三支决策的序列数据代价敏感分类算法 ·1259· 20 15 10 1520 25 30 5 10 1520 25 30 天数/d 天数d (a)2012-06 (b)2013-06 100 200 300 400 500 污染程度(gm) 图4原数据集中分类结果与时间的变化关系 Fig.4 Relations between classify result and time change 从图4可以看出，空气质量与时间有明显的 价；b为偏移值。.的计算方式由表1所述代价 关系，并且呈现出一定的周期规律。 函数计算可得。 国际旅行旅客数据集包括了1949一1960年 有毒 0 0 12年之间每个月的国际航线航班旅客人数。共 144个数据，单位为1千人。图5为原数据集中数 效 0 11 82 据的分布。 600 e 31 2593 0 500 400 32239 68 0 0 优 良 有毒 200 测污染指 100 图6分类结果的混淆矩阵 1949195019521954195619581960 年份 Fig.6 Confusion matrix of classification result 0.06 一训练 图51949一1960年国际航班旅客人数 0.05 .测试 Fig.5 Number of international airline traveler between 1949-1960 0.04 3.1PM2.5数据集 0.03 根据前述对数据集的分析，将数据通过前置 0.02 分类器进行回归分析，得到分类结果。此LSTM 分类器在数据集上的分类准确率为0.997。由于 0 10 2030 4050 为多分类问题，参考指标由准确率-召回率改为 训练轮次 混淆矩阵。此分类器在测试数据上的结果混淆矩 图7LSTM训练损失 阵见图6。图7为分类器训练的最终损失函数。 Fig.7 Loss of LSTM training 设代价函数为： 将预测结果代入式(11)后，得到原分类器的 A=∑awa+b (11) 决策代价。 将得到的损失偏差与代入三支决策的决策规 式中：.为判断是否正确；wx为权重；即判断代 则(PIi、Bi、Ni)中，对明显偏离预测中心的值进
从图 4 可以看出，空气质量与时间有明显的 关系，并且呈现出一定的周期规律。 国际旅行旅客数据集包括了 1949—1960 年 12 年之间每个月的国际航线航班旅客人数。共 144 个数据，单位为 1 千人。图 5 为原数据集中数 据的分布。 600 500 400 300 200 100 19501949 1952 1954 1956 1958 1960 年份 人数/千人 图 5 1949—1960 年国际航班旅客人数 Fig. 5 Number of international airline traveler between 1949—1960 3.1 PM2.5 数据集 根据前述对数据集的分析，将数据通过前置 分类器进行回归分析，得到分类结果。此 LSTM 分类器在数据集上的分类准确率为 0.997。由于 为多分类问题，参考指标由准确率−召回率改为 混淆矩阵。此分类器在测试数据上的结果混淆矩 阵见图 6。图 7 为分类器训练的最终损失函数。 设代价函数为： λ = ∑ i λixwix +b (11) 式中： λix 为判断是否正确； wix 为权重；即判断代 价； b 为偏移值。 λix 的计算方式由表 1 所述代价 函数计算可得。 将预测结果代入式 (11) 后, 得到原分类器的 决策代价。 将得到的损失偏差与代入三支决策的决策规 则 (Pli、Bli、Nli) 中，对明显偏离预测中心的值进 20 15 10 5 0 100 200 300 400 500 0 5 10 15 20 25 30 时刻 天数/d 20 15 10 5 0 5 10 15 20 25 30 时刻 天数/d 污染程度/(μg·m−3 ) (a) 2012-06 (b) 2013-06 图 4 原数据集中分类结果与时间的变化关系 Fig. 4 Relations between classify result and time change 有毒 差 良 优 优 良 差 有毒 预测污染指数 实际污染指数 1 11 11 82 31 32 239 2 593 68 0 0 3 0 0 00 0 图 6 分类结果的混淆矩阵 Fig. 6 Confusion matrix of classification result 0.06 0.05 0.04 0.03 0.02 0 10 20 30 40 50 误差 训练轮次 训练 测试 图 7 LSTM 训练损失 Fig. 7 Loss of LSTM training 第 6 期 刘牧雷，等：基于三支决策的序列数据代价敏感分类算法 ·1259·
·1260· 智能系统学报 第14卷 行标记，得到新的分类代价。 数。由此，代入假设条件，可以得到如图9的代价 表2可知，使用三支决策算法进行判断的分 曲线。 类任务在代价优化上有显著作用。 将代入三支决策算法结果如图9。由结果可 表2使用三支决策的分类代价与未使用三支决策的分 知，对于问题中给定时刻t,在t+12时，代价第一 类代价对比 次大于阈值α，故在6,1+12]时刻的数据是可信 Table 2 Compara of cost of classification between 3WD 的。同理，在[t+26时，预测代价第一次大于阈 and non-3WD 值B,所以从t+26时刻起，预测数据不再可信。 代价 APP APB APN ANP ANE ANN 图10表示t与代价之间的关系。 三支决策 07600 099001750 ×109 前置分类器0015201980003500 3.2国际旅行旅客人数数据集 根据前述数据集的基本信息，将数据集进行 3 前期分类。图8为LSTM作为前置分类器的预测 数据。取预测步长为3，预测网络两层，每层含 128个LSTM单元。 x103 6001 一原始数据 ·训练数据 1961-01 500 +测试数据 时间 400， 图9随t而代价越来越大的判断曲线入 Fig.9 Ast increases,the prediction results become more 300 and more inaccurate 200 ×10 6 一原始误差 …a上界 19491950195219541956195819601962 年份 nB上界 4 图8经过前置分类器的预测数据 Fig.8 Predict data after preprocessing 显然，随着时间推移，距预测点较远的点预测 误差越大。在整个数据集上，前置分类器的测试 数据均方误差为28.03。 对于回归问题，由于没有直接的方式判断分 1958-01 1957.07 1958-07 1959.07 1959-01 1960-07 1960-01 1961-01 类的正误，本文使用均方误差来描述对应的置 时间 信度。由此，相应的代价函数可表示为 图10代价判断决定的三支决策结果 1= ∑ww+b (12) Fig.10 Discarding costly predictions given by 3WD iElP.B.V).jelX.-X) 但是与前述判断规则(PIi、Bi、N)不同，此时的 4结束语 分类不再是由有限的状态集合{X,X)描述，而是 本文通过两个实验的验证，提出了基于 由偏差E(⊙-和方差D(@组成的连续集合。 LSTM的三支决策分类算法。实验1在LSTM分 所以，此时的代价，不再是确定的函数而是与由 类的基础上，增加三支决策分类后明显地降低了 均方差MSE(@描述的模型和距离预测点t的两 决策风险：实验2在原先分类器中引入三支决策 者组成的概率分布。 后，也有了代价上的优化。实验表明：1)三支决 f(0t) (13) 策的决策准确率受前端分类器准确率的较大影 式中：f为训练模型的偏差分布；为模型的均方 响；2)三支决策算法可以结合深度学习模型解决 差；tn为当前点距预测点的距离。 代价敏感分类问题，而非仅限于非贝叶斯模型的 本例中，为方便计算，假设分布∫为均匀分 分类器；3)三支决策在解决代价敏感分类问题的 布。此时，代价函数简化为只与时间n相关的函 同时，可以通过扩展代价定义的方式，为回归模
行标记，得到新的分类代价。 表 2 可知，使用三支决策算法进行判断的分 类任务在代价优化上有显著作用。 表 2 使用三支决策的分类代价与未使用三支决策的分 类代价对比 Table 2 Compara of cost of classification between 3WD and non-3WD 代价 λPP λPB λPN λNP λNB λNN λ 三支决策 0 760 0 0 990 0 1 750 前置分类器 0 0 1 520 1 980 0 0 3 500 3.2 国际旅行旅客人数数据集 根据前述数据集的基本信息，将数据集进行 前期分类。图 8 为 LSTM 作为前置分类器的预测 数据。取预测步长为 3，预测网络两层，每层含 128 个 LSTM 单元。 600 ×103 500 400 300 200 100 19501949 1952 1954 1956 1958 1960 1962 年份 人数 原始数据 训练数据 测试数据 图 8 经过前置分类器的预测数据 Fig. 8 Predict data after preprocessing 显然，随着时间推移，距预测点较远的点预测 误差越大。在整个数据集上，前置分类器的测试 数据均方误差为 28.03。 θˆ 对于回归问题，由于没有直接的方式判断分 类的正误，本文使用均方误差 来描述对应的置 信度。由此，相应的代价函数可表示为 λ = ∑ i∈{P,B,N}, j∈{X,¬X} λi, jwi, j +b (12) {X,¬X} E ( θˆ ) −θ D ( θˆ ) λi, j MSE( θˆ ) t 但是与前述判断规则 (Pli、Bli、Nli) 不同，此时的 分类不再是由有限的状态集合 描述，而是 由偏差 和方差 组成的连续集合。 所以，此时的代价 不再是确定的函数而是与由 均方差 描述的模型和距离预测点 的两 者组成的概率分布。 λi, j ∼ f ( θˆ,tn ) (13) f θˆ tn 式中： 为训练模型的偏差分布； 为模型的均方 差； 为当前点距预测点的距离。 f tn 本例中，为方便计算，假设分布 为均匀分 布。此时，代价函数简化为只与时间 相关的函 数。由此，代入假设条件，可以得到如图 9 的代价 曲线。 t t+12 α [t,t+12] [t+26] β t+26 t 将代入三支决策算法结果如图 9。由结果可 知，对于问题中给定时刻 ，在 时，代价第一 次大于阈值 ，故在 时刻的数据是可信 的。同理，在 时，预测代价第一次大于阈 值 ，所以从 时刻起，预测数据不再可信。 图 10 表示 与代价之间的关系。 5 6 4 3 2 1 0 1957-07 1958-01 1958-07 1959-01 1959-07 1960-01 1960-07 1961-01 相对代价 时间 ×103 图 9 随 tn 而代价越来越大的判断曲线 λt Fig. 9 As tn increases, the prediction results become more and more inaccurate 5 6 4 3 2 1 0 1957-07 1958-01 1958-07 1959-01 1959-07 1960-01 1960-07 1961-01 相对代价 时间 原始误差 α上界 β上界 ×103 图 10 代价判断决定的三支决策结果 Fig. 10 Discarding costly predictions given by 3WD 4 结束语 本文通过两个实验的验证，提出了基 于 LSTM 的三支决策分类算法。实验 1 在 LSTM 分 类的基础上，增加三支决策分类后明显地降低了 决策风险；实验 2 在原先分类器中引入三支决策 后，也有了代价上的优化。实验表明：1) 三支决 策的决策准确率受前端分类器准确率的较大影 响；2) 三支决策算法可以结合深度学习模型解决 代价敏感分类问题，而非仅限于非贝叶斯模型的 分类器；3) 三支决策在解决代价敏感分类问题的 同时，可以通过扩展代价定义的方式，为回归模 ·1260· 智 能 系 统 学 报 第 14 卷
第6期 刘牧雷，等：基于三支决策的序列数据代价敏感分类算法 ·1261· 型建立可信度判据。结合三支决策理论，在时间 risk prediction using cost-sensitive with Nonnegativity- 序列分析问题中，三支决策模型可以为预测结果 constrained Autoencoders based on imbalanced naturalist- 增加可信度的判据，使得预测结果更加具有分析 ic driving data[J/OL].IEEE transactions on intelligent 和处理的价值。 transportation systems:(2019-01-17).https://ieeexplore. 但是当前的工作只是初步的验证有关于深度 ieee.org/document/8617709.DOI:10.1109/TITS.2018. 2886280. 学习与三支决策相结合形成新的代价敏感分类的 [8]YAO Yiyu.Three-way decision:an interpretation of rules 初步研究。本文的研究尚处于初步的阶段。未 in rough set theory[C]//Proceedings of the 4th Internation- 来，对于模型的改进仍有许多研究空间。例如， al Conference on Rough Sets and Knowledge Technology. 对于三支决策算法，可以结合新的边界理论，形 Gold Coast,Australia,2009:642-649. 成自动化的边界确定；在整体模型中，可以借助 [9]GERS F A,SCHMIDHUBER J,CUMMINS F.Learning boost或专家分类器等模型，提出更完善的理论； to forget:continual prediction with LSTM[J].Neural com- 以及结合Alex-net等其他更高效的分类器来进一 putation,2000,12(10):2451-2471. 步提高前置分类器的性能等。这些改进都将能够 [10]ELKAN C.The foundations of cost-sensitive learning 进一步提高三支决策在在代价敏感分类领域的应 [C]//Proceedings of the 17th International Joint Confer- 用频率。 ence of Artificial Intelligence.Morgan Kaufmann,Seattle, 2001:973-978 参考文献： [11]LIU Xuying,ZHOU Zhihua.The influence of class im- [1]KARIM F,MAJUMDAR S,DARABI H,et al.LSTM balance on cost-sensitive learning:an empirical study [Cl//Proceedings of the 6th International Conference on fully convolutional networks for time series classification Data Mining.Hong Kong,China,2006:970-974. [J.IEEE access,.2018,6:1662-1669 [12]ZADROZNY B,LANGFORD J,ABE N.Cost-sensitive [2]KARIM F.MAJUMDAR S.DARABI H.et al.Multivari- learning by cost-proportionate example weighting ate LSTM-FCNs for time series classification[J].Neural [C]//Proceedings of the 3rd IEEE International Confer- networks,2019,116:237-245. [3]KHAN S H,HAYAT M,BENNAMOUN M,et al.Cost- ence on Data Mining.Melbourne,FL,USA,2003: 435-442 sensitive learning of deep feature representations from im- balanced data[J].IEEE transactions on neural networks and 作者简介： learning systems,2018,29(8):3573-3587. 刘牧雷，男，1993年生，硕士研究 [4]FERNANDEZ A,GARCiA S,GALAR M,et al.Cost- 生，主要研究方向为三支决策、代价敏 sensitive learning[M]//FERNANDEZ A,GARCIA S. 感分类。 GALAR M,et al.Learning from Imbalanced Data Sets. Cham:Springer,2018:63-78 [5]YAN Ke,MA Lulu,DAI Yuting,et al.Cost-sensitive and sequential feature selection for chiller fault detection and diagnosis[J].International journal of refrigeration,2018, 徐菲菲，女，1983年生，副教授 86:401-409 中国计算机学会和中国人工智能学会 会员，主要研究方向为粒计算理论、粗 [6]JIANG Xinxin,PAN Shirui,LONG Guodong,et al.Cost- 糙集理论、数据挖掘、人工智能与机器 sensitive parallel learning framework for insurance intelli- 学习。主持国家自然科学基金项目 gence operation[J].IEEE transactions on industrial elec- 1项：上海市教育发展基金会和上海 tronics,2019,66(12):9713-9723 市教育委员会“晨光计划”1项、上海市 [7]CHEN Jie,WU Zhongcheng,ZHANG Jun.Driving safety 教育委员会科研创新项目1项等
型建立可信度判据。结合三支决策理论，在时间 序列分析问题中，三支决策模型可以为预测结果 增加可信度的判据，使得预测结果更加具有分析 和处理的价值。 但是当前的工作只是初步的验证有关于深度 学习与三支决策相结合形成新的代价敏感分类的 初步研究。本文的研究尚处于初步的阶段。未 来，对于模型的改进仍有许多研究空间。例如， 对于三支决策算法，可以结合新的边界理论，形 成自动化的边界确定；在整体模型中，可以借助 boost 或专家分类器等模型，提出更完善的理论； 以及结合 Alex-net 等其他更高效的分类器来进一 步提高前置分类器的性能等。这些改进都将能够 进一步提高三支决策在在代价敏感分类领域的应 用频率。 参考文献： KARIM F, MAJUMDAR S, DARABI H, et al. LSTM fully convolutional networks for time series classification [J]. IEEE access, 2018, 6: 1662–1669. [1] KARIM F, MAJUMDAR S, DARABI H, et al. Multivariate LSTM-FCNs for time series classification[J]. Neural networks, 2019, 116: 237–245. [2] KHAN S H, HAYAT M, BENNAMOUN M, et al. Costsensitive learning of deep feature representations from imbalanced data[J]. IEEE transactions on neural networks and learning systems, 2018, 29(8): 3573–3587. [3] FERNÁNDEZ A, GARCÍA S, GALAR M, et al. Costsensitive learning[M]//FERNÁNDEZ A, GARCÍA S, GALAR M, et al. Learning from Imbalanced Data Sets. Cham: Springer, 2018: 63-78. [4] YAN Ke, MA Lulu, DAI Yuting, et al. Cost-sensitive and sequential feature selection for chiller fault detection and diagnosis[J]. International journal of refrigeration, 2018, 86: 401–409. [5] JIANG Xinxin, PAN Shirui, LONG Guodong, et al. Costsensitive parallel learning framework for insurance intelligence operation[J]. IEEE transactions on industrial electronics, 2019, 66(12): 9713–9723. [6] [7] CHEN Jie, WU Zhongcheng, ZHANG Jun. Driving safety risk prediction using cost-sensitive with Nonnegativityconstrained Autoencoders based on imbalanced naturalistic driving data[J/OL]. IEEE transactions on intelligent transportation systems: (2019-01-17). https://ieeexplore. ieee.org/document/8617709. DOI: 10.1109/TITS.2018. 2886280. YAO Yiyu. Three-way decision: an interpretation of rules in rough set theory[C]//Proceedings of the 4th International Conference on Rough Sets and Knowledge Technology. Gold Coast, Australia, 2009: 642–649. [8] GERS F A, SCHMIDHUBER J, CUMMINS F. Learning to forget: continual prediction with LSTM[J]. Neural computation, 2000, 12(10): 2451–2471. [9] ELKAN C. The foundations of cost-sensitive learning [C]//Proceedings of the 17th International Joint Conference of Artificial Intelligence. Morgan Kaufmann, Seattle, 2001: 973–978. [10] LIU Xuying, ZHOU Zhihua. The influence of class imbalance on cost-sensitive learning: an empirical study [C]//Proceedings of the 6th International Conference on Data Mining. Hong Kong, China, 2006: 970–974. [11] ZADROZNY B, LANGFORD J, ABE N. Cost-sensitive learning by cost-proportionate example weighting [C]//Proceedings of the 3rd IEEE International Conference on Data Mining. Melbourne, FL, USA, 2003: 435–442. [12] 作者简介： 刘牧雷，男，1993 年生，硕士研究 生，主要研究方向为三支决策、代价敏 感分类。 徐菲菲，女，1983 年生，副教授， 中国计算机学会和中国人工智能学会 会员，主要研究方向为粒计算理论、粗 糙集理论、数据挖掘、人工智能与机器 学习。主持国家自然科学基金项目 1 项；上海市教育发展基金会和上海 市教育委员会“晨光计划”1 项、上海市 教育委员会科研创新项目 1 项等。 第 6 期 刘牧雷，等：基于三支决策的序列数据代价敏感分类算法 ·1261·
