决策问题的分解处理方法

闫 硕 张云勇 严斌峰 加雄伟

1中国联合网络通信集团有限公司100033北京

2北京邮电大学计算机学院100876北京

3中国联合网络通信有限公司研究院100176北京

引言

智能信息的处理，常常涉及数据信息的决策问题，使数据信息与决策问题的联系成为关注的课题。数据信息的决策过程往往概括为：在数据满足相关条件的前提下，数据应对结论的判定。这不仅是数据智能处理研究的课题，也在实际当中经常涉及。所以针对数据决策的研究具有理论和应用方面的意义，由此引出本文的讨论，如下的工作将面对数据决策相关的问题。

数据决策问题与数据的性质密切相关，决策过程将根据数据满足的特性，确定数据应对的结论，由此引出的数据决策问题必然涉及数据特性之间的因果关系，以及相关的描述或表示。因此建立数据特性的描述方法，构成讨论的研究环境，是工作得以展开的基础。

实际上，数据处理涉及的决策系统[1-2]是与决策问题密切相关的结构化表示形式。决策系统汇集了数据满足前提，对应结论的决策信息。作为数据处理的研究课题，决策系统的研究涉及属性约简[3-5]、数据关联[6-7]、数据推理[8-10]、数据合并[11]等课题或方向，并获得了有意义的成果。不过这些讨论并不直接针对数据决策的因果联系，如何对决策系统记录的决策信息刻画描述，明确决策概念的含义也未在这些讨论中涉及。因此由数据特性引出的决策问题为决策系统的研究预留了空间，以下针对的正是这方面的问题。

为此，回顾决策系统的结构组成是必要的，即：决策系统汇集了数据以及数据的各类属性信息，构成了相关对象的结构化表示。如果把决策系统作为参照的模型，实施对样本的判定，比对样本数据满足的性质，确定其应对的结论，则决策系统将支撑决策方法的产生，因此对样本给予专门的讨论是需要考虑的问题。尽管样本在机器学习[12-13]中频繁涉及，但因为问题的不同，样本在不同的讨论中具有自身的形式，存在着一定的差异。所以基于决策系统的比对判定，对样本具有结构上的要求，下面的讨论将明确样本的形式。

决策系统记录的数据和相关的性质将体现条件信息和决策信息组合在一起的因果联系。所以与决策系统相关的样本必然基于决策系统包含的信息，由此体现决策信息的组合，刻画决策判定的含义，应对判定方法的建立。进而，为使决策判定清晰简化，判定方法将涉及复杂问题的分解处理。下面的讨论将围绕这些方面展开，由此形成自身的方法体系。

1 决策系统与决策问题

上述的讨论表明决策系统由各类信息组合而成，搭建了数据性质之间的因果联系，形成了决策问题的研究前提。如果把决策系统作为参照的模型，对给定的样本实施决策判定，那么熟悉了解决策系统的构成是必需的。

1.1 决策系统

决策系统以数学结构的形式汇集了数据和数据的属性信息，其通过判定数据的性质，得到相应结论的结构化表示为决策问题智能化处理提供了参照依据。决策系统以DS=(U，A，V，f)的形式进行表示，其中的U、A和V都是集合，f是一函数，其含义解释如下。

U是一有限集，称为论域，U中的元素称为数据。

A也是一有限集，其元素称为属性，所以A称为属性集，满足A=C∪D及C∩D=Ø，这里的C和D也都是属性集，C称为条件属性集，其中的元素称为条件属性；D称为决策属性集，其中的元素称为决策属性。

V是一有限集合，由A中属性取得的值构成。V称为属性值域，其中的元素称为属性值。

f∶U×A→V是从U×A到V的函数，称为信息函数。对于∈U×A，存在唯一的v∈V，使得f(x，a)=v。

对于决策系统DS=(U，A，V，f)，考虑属性a∈A，当x∈U时，有∈U×A，所以存在唯一的v∈V，使得f(x，a)=v。此表达式f(x，a)=v可以记作a(x)=v(=f(x，a))。由此可知属性集A中的属性a是从U到V的函数，称为属性函数。当a是条件属性时，称a为条件属性函数；当a是决策属性时，称a为决策属性函数。

决策系统可以采用表格的形式予以直观的表示，称为决策表，如表1所示。

表1 决策系统DS

该决策表表明了决策系统DS=(U，A，V，f)的各个组成部分，其中论域U={x1，x2，x3，x4，x5}包含5个数据；属性集A=C∪D由条件属性集C={c1，c2}和决策属性集D={d1，d2}构成；属性值域V={0，1，2，3}由有限个数值构成；信息函数f的取值已在表1中展示，如f(x1，c1)=1，f(x4，c2)=1，f(x4，d2)=0等等，这些函数表达式还可表示为c1(x1)=1(=f(x1，c1))；c2(x4)=1(=f(x4，c2))；d2(x4)=0(=f(x4，d2))等。

在表1的决策系统中，论域U={x1，x2，x3，x4，x5}中仅给出5个数据，条件属性集C={c1，c2}和决策属性集D={d1，d2}分别给出了两个条件属性c1和c2，及两个决策属性d1和d2。一般情况下，决策系统DS=(U，A，V，f)的论域U往往包含大量的数据，条件属性和决策属性也非个位数计之，决策系统DS=(U，A，V，f)往往构成庞大的数据库系统。巨大的数据信息可能会对基于决策系统的数据处理或问题决策造成障碍，特别当属性集A=C∪D中的属性众多时，可能使相关的决策变得含混不清，或使决策无所适从。

因此给出一种处理方法，使依据决策系统产生的决策清晰可行，且容易对决策的结果进行判断是值得考虑的课题。如下将展开这方面的讨论，这需要分析决策系统的功能，明确决策系统的作用。为此引入与决策系统相关的概念，以求讨论的严谨分明。

1)条件函数值：对于属性a∈A，若x∈U且a(x)=v，则当a是条件属性函数时，称v为条件函数值。

2)决策函数值：对于属性a∈A，若x∈U且a(x)=v，则当a是决策属性函数时，称v为决策函数值。

3)样本：在决策系统DS=(U，A，V，f)对应的决策表中，U中数据x对应的行称为决策系统的样本，简称样本，并采用向量(x，u1，u2，…，um；v1，v2，…，vn)进行表示，其中x是论域U中的数据，u1，u2，…，um(m≥1)是与x相关的所有条件函数值，v1，v2，…，vn(n≥1)是与x相关的所有决策函数值，并用分号“；”把条件函数值和决策函数值分开。

4)样本数据：在样本(x，u1，u2，…，um；v1，v2，…，vn)中，称x为样本数据，样本数据就是论域U中的数据。

5)同型样本：如果两个样本的条件函数值的个数相同，同时决策函数值的个数也相同，则称这两个样本是同型样本。比如(x，u1，u2，…，um；v1，v2，…，vn)和(y，w1，w2，…，wm；z1，z2，…，zn)是同型样本。决策系统DS=(U，A，V，f)的任意两个样本都是同型样本。

6)条件样本：设(y，w1，w2，…，wm)是一向量，其中y是与论域U中数据同类型的数据，同时w1，w2，…，wm(m个)是与决策系统DS=(U，A，V，f)中任一样本(x，u1，u2，…，um；v1，v2，…，vn)的条件函数值u1，u2，…，um(m个)类型和个数相同的值，此时称(y，w1，w2，…，wm)为决策系统DS=(U，A，V，f)的条件样本，简称条件样本，y称为条件样本数据。显然决策系统DS=(U，A，V，f)的样本(x，u1，u2，…，um；v1，v2，…，vn)的子部分(x，u1，u2，…，um)是决策系统的条件样本。

在表1的决策系统中，x1所在行对应的样本是(x1，1，2；2，1)，其中x1是样本数据，数值1，2是条件函数值，数值2，1是决策函数值，向量(x1，1，2)是条件样本。

给定向量(y，u1，u2)，其中y是与论域U中数据同类型的数据，u1和u2是数值，此时(y，u1，u2)与表1中决策系统的每一条件样本可能不同，但由于数值u1和u2的个数与样本(x1，1，2；2，1)中条件函数值1，2的个数相同，所以(y，u1，u2)是表1中决策系统的条件样本。

上述分析讨论表明，决策系统DS=(U，A，V，f)不仅是集合U，A，V和信息函数f构成的数学结构，也可看做一系列同型样本构成的结构体系。

1.2 基于样本的决策

决策系统DS=(U，A，V，f)汇集了数据满足条件和对应结论的信息，从条件到结论的对应就是决策的过程。如果从样本的角度考虑，决策的过程是根据样本的条件函数值，确定样本数据的性质，并通过决策函数值予以反映。为了直观，通过表1的决策系统进行讨论。

考虑表1的决策系统DS=(U，A，V，f)，其各类信息可与实际问题联系在一起，赋予它们具体的含义。设论域U={x1，x2，x3，x4，x5}中的数据表示5个学生，对于属性集A={c1，c2}∪{d1，d2}，设定c1表示数学，c2表示语文，d1表示等级，d2表示获奖。因此条件属性c1和c2，以及决策属性d1和d2可分别表示学生xi(i=1，2，3，4，5)在学校的数学和语文成绩，以及由此确定的整体学习情况和获奖信息，并通过条件函数值和决策函数值得到反映。表1中的条件函数值和决策函数值与数据xi之间的联系如下：

如果c1(xi)=k，则表示学生xi的数学成绩是第k等；

如果c2(xi)=k，则表示学生xi的语文成绩是第k等；

如果d1(xi)=k，则表示学生xi的整体成绩是第k级；

如果d2(xi)=1，则学生xi获得奖励，如果d2(xi)=0，则学生xi不获得奖励。

于是可对表1决策系统反映的学生信息进行如下分析。考虑x1所在的行，由于c1(x1)=1并且c2(x1)=2，所以学生x1的数学成绩是第1等，语文成绩是第2等，展示了x1满足的条件。同时d1(x1)=2且d2(x1)=1，表明x1的整体成绩是第2级，并且可以获得奖励，确定了对x1的评估结果。这表达了如此的信息：当学生x1的数学和语文成绩一个是1等，一个是2等时，则该生的整体成绩是2级，且可以得到奖励。这样的过程就是根据条件做出的决策，体现了学生x1数学和语文成绩与评判结果之间的联系。学生x2，x3，x4，x5的情况也可利用表1进行评判。

通过对表1各类信息与实际问题的联系，可帮助对决策系统包含的决策信息进行理解。因此对于一般的决策系统DS=(U，A，V，f)，可依据上述直观的解释，对决策系统包含的决策信息给予描述，于是引出如下的概念。

7)设(y，w1，w2，…，wm)是决策系统DS=(U，A，V，f)的条件样本，如果存在DS=(U，A，V，f)的样本(x，u1，u2，…，um；v1，v2，…，vn)，使得w1，w2，…，wm分别与u1，u2，…，um对应相等，则称条件样本(y，w1，w2，…，wm)与样本(x，u1，u2，…，um；v1，v2，…，vn)相匹配。

8)如果决策系统DS=(U，A，V，f)的条件样本(y，w1，w2，…，wm)与决策系统DS=(U，A，V，f)的样本(x，u1，u2，…，um；v1，v2，…，vn)相匹配，则称决策函数值v1，v2，…，vn为条件样本数据y的决策结论。

9)对于条件样本(y，w1，w2，…，wm)，把获得条件样本数据y决策结论的过程称为针对该条件样本的决策。

所以决策系统DS=(U，A，V，f)中针对条件样本的决策与相匹配的样本密切相关。相匹配时，依据决策系统的决策将形成。不匹配时，则不能依据决策系统进行决策。

2 决策的分解处理

把一个决策系统作为参照模型，对于任意的条件样本实施比对判定，如果在决策系统中存在与之相匹配的样本，则该样本的决策函数值作为条件样本数据的决策结论，将确定该数据的性质，从而完成决策的过程。

2.1 决策的确定和不确定性

在一些情况下，对于给定的条件样本，即使在决策系统中存在相匹配的样本，但在确定条件样本数据的决策结论时，可能遇到决策结论选择上的不确定性。不妨通过表1的决策系统进行讨论。

由表1可知，数据x3和x4分别对应样本(x3，3，1；2，0)和(x4，3，1；3，0)，其条件函数值3，1相同，但决策函数值2，0和3，0不完全相同。于是对于表1决策系统的条件样本(y，u1，u2)，如果(y，u1，u2)与(x3，3，1；2，0)相匹配，即数值u1，u2分别与3，1对应相等，则(y，u1，u2)与(x4，3，1；3，0)也相匹配。此时条件样本数据y的决策结论遇到选择2，0还是选择3，0的问题，于是引入如下概念。

10)如果条件样本数据的决策结论仅有唯一一组，则称针对条件样本的决策在DS=(U，A，V，f)中是确定的。

11)如果条件样本数据的决策结论存在多组，则称针对条件样本的决策在DS=(U，A，V，f)中是不确定的。

决策的不确定性可通俗的表述为：相同的条件对应不同的结果。这在实际中也常常遇到，对此人们可通过思维分析，设法应对处理，不过也时常遭遇应对的困难。对于程序设计而言，当涉及决策的不确定性问题时，如果不能有效地应对处理，计算机则无所适从。

当决策系统涉及较多的属性，特别决策属性很多时，条件样本数据的决策结论将涉及很多的决策函数值。因此如果能够对众多的决策属性进行分解，分别考虑每一个决策属性，使对较多决策函数值的考虑分解为对单一决策函数值的讨论，由此对决策的确定或不确定性进行有效的判定，那么该分解方法对决策的确定与否具有清晰化的意义。下文将给出具体的方法，使判定得以分解处理。

2.2 决策的分解

考虑决策系统DS=(U，A，V，f)，其中A=C∪D及C∩D=Ø。下面的讨论主要关注决策属性，所以不妨设D={d1，d2，…，dn}。此时决策系统DS=(U，A，V，f)具有如下形式：

对于di∈{d1，d2，…，dn}(i=1，2，…，n)，构造决策系统如下：

在决策系统DSi=(U，C∪{di}，V，fi)中，论域U、条件属性集C和属性值域V与决策系统DS=(U，C∪{d1，d2，…，dn}，V，f)中的对应部分相同，而决策属性集{di}中仅包含一个决策属性di，此时DSi中的信息函数fi由DS中的信息函数f所确定：使当∈U×(C∪{di})时，满足fi(x，a)=f(x，a)。实际上，fi是f在U×(C∪{di})上的限制，为了简单仍用f表示fi。于是DSi=(U，C∪{di}，V，fi)=(U，C∪{di}，V，f)，并称为决策系统DS=(U，C∪{d1，d2，…，dn}，V，f)的子系统。

因此对于包含n个决策属性的决策系统DS=(U，C∪{d1，d2，…，dn}，V，f)，可以得到n个子系统：

这n个子系统中的每一个仅包含一个决策属性，形成了对决策系统DS=(U，C∪{d1，d2，…，dn}，V，f)的分解。

由于决策系统DS=(U，C∪{d1，d2，…，dn}，V，f)与其子系统DSi=(U，C∪{di}，V，f)(i=1，2，…，n)具有相同的条件属性集C，所以如果(y，w1，w2，…，wm)是决策系统DS=(U，C∪{d1，d2，…，dn}，V，f)的条件样本，则(y，w1，w2，…，wm)也是子系统DSi=(U，C∪{di}，V，f)(i=1，2，…，n)的条件样本。同时当(x，u1，u2，…，um；v1，v2，…，vn)是决策系统DS=(U，C∪{d1，d2，…，dn}，V，f)的样本时，向量(x，u1，u2，…，um；vi)(i=1，2，…，n)是子系统DSn=(U，C∪{di}，V，f)的样本。

进而，当条件样本(y，w1，w2，…，wm)与决策系统DS=(U，C∪{d1，d2，…，dn}，V，f)的样本(x，u1，u2，…，um；v1，v2，…，vn)相匹配时，该条件样本(y，w1，w2，…，wm)与子系统DSi=(U，C∪{di}，V，f)的样本(x，u1，u2，…，um；vi)(i=1，2，…，n)必然相匹配。

于是提出这样的问题：在决策系统DS=(U，A，V，f)中，针对条件样本(y，w1，w2，…，wm)的决策，与在子系统DSi=(U，C∪{di}，V，f)(i=1，2，…，n)中，针对条件样本(y，w1，w2，…，wm)的决策具有怎样的联系？

结论1：针对条件样本(y，w1，w2，…，wm)的决策在决策系统DS=(U，C∪{d1，d2，…，dn}，V，f)中是确定的，当且仅当对于每一子系统DSi=(U，C∪{di}，V，f)(i=1，2，…，n)，针对(y，w1，w2，…，wm)的决策在DSi=(U，C∪{di}，V，f)中是确定的。

结论2：针对条件样本(y，w1，w2，…，wm)的决策在决策系统DS=(U，C∪{d1，d2，…，dn}，V，f)中是不确定的，当且仅当存在一子系统DSi=(U，C∪{di}，V，f)(1≤i≤n)，使针对(y，w1，w2，…，wm)的决策在子系统DSi=(U，C∪{di}，V，f)中是不确定的。

鉴于篇幅，这里不给出这两个结论的证明，仅通过表1的决策系统给予直观的验证。

由于表1中的决策系统包含两个决策属性，按照上述的分解方法，该决策系统DS=(U，C∪{d1，d2}，V，f)对应分解出两个子系统DS1=(U，C∪{d1}，V，f)和DS2=(U，C∪{d2}，V，f)，它们都包含一个决策属性，分别是d1和d2。这两个子系统分别展示在表2和表3中。

表2 子系统DS1

表3 子系统DS2

现考查条件样本(y，1，2)。在表1的决策系统DS=(U，C∪{d1，d2}，V，f)中，条件样本(y，1，2)与表1中的样本(x1，1，2；2，1)和(x2，1，2；2，1)相匹配。由于样本(x1，1，2；2，1)和(x2，1，2；2，1)的决策函数值都是2，1，所以条件样本数据y的决策结论仅有唯一一组(即2，1)。因此针对条件样本(y，1，2)的决策在表1的决策系统DS=(U，C∪{d1，d2}，V，f)中是确定的。另一方面，条件样本(y，1，2)与表2子系统中的样本(x1，1，2；2)和(x2，1，2；2)相匹配，此时条件样本数据y的决策结论是2，唯一确定，因此针对条件样本(y，1，2)的决策在表2的子系统DS1=(U，C∪{d1}，V，f)中是确定的。同样，条件样本(y，1，2)与表3子系统中的样本(x1，1，2；1)和(x2，1，2；1)相匹配，此时条件样本数据y的决策结论是1，也唯一确定，因此针对条件样本(y，1，2)的决策在表3的子系统DS2=(U，C∪{d2}，V，f)中也是确定的。于是针对条件样本(y，1，2)的决策在决策系统DS=(U，C∪{d1，d2}，V，f)中的确定性与在子系统DS1=(U，C∪{d1}，V，f)和DS2=(U，C∪{d2}，V，f)中的确定性是相同的，这是对结论1的验证。

再考虑条件样本(y，3，1)，它与表2子系统DS1=(U，C∪{d1}，V，f)中的样本(x3，3，1；2)和(x4，3，1；3)相匹配，此时条件样本数据y的决策结论涉及两组，分别是2和3，因此针对条件样本(y，3，1)的决策在子系统DS1=(U，C∪{d1}，V，f)中是不确定的。另一方面，条件样本(y，3，1)与表1决策系统DS=(U，C∪{d1，d2}，V，f)中的样本(x3，3，1；2，0)和(x4，3，1；3，0)相匹配，此时条件样本数据y的决策结论涉及两组，分别是2，0和3，0，因此针对条件样本(y，3，1)的决策在决策系统DS=(U，C∪{d1，d2}，V，f)中是不确定的。该讨论表明，针对条件样本(y，3，1)的决策在子系统DS1=(U，C∪{d1}，V，f)中不确定时，在原决策系统DS=(U，C∪{d1，d2}，V，f)中也是不确定的，这是对结论2的验证。

结论1和结论2表明，在决策系统中针对条件样本决策的确定或不确定判定可等价转换到仅包含一个决策属性的子系统中。这种对决策系统的分解处理是其他讨论不曾涉及的方法，达到了清晰或简化判定过程的目的。

在应用方面，文献[14]、[15]的讨论把医学诊断基于数据决策的判定，并与决策属性的分解存在联系。

3 结语

把决策系统分解为一系列仅包含一个决策属性的子系统，将决策系统中针对条件样本的决策等价地转换到子系统中，是本文建立的方法。由此使以决策函数值为判定依据的决策得到了清晰的判定，实现了决策问题分解处理的目的。特别地，当针对条件样本的决策在决策系统中具有不确定性时，由结论2，可通过在一子系统中针对条件样本决策的不确定判定得以完成，这显然简化了判定的过程。

把决策系统作为决策问题判定的参照模型，对条件样本实施比对判定，得到决策结论，形成确定或不确定决策信息的过程体现了机器学习的数据处理思想，同时也有别于传统的机器学习算法。这基于作者对决策问题与机器学习方法的理解，展示了求变的思想。决策的分解处理为决策问题的清晰简化提供了路径，是判定方法的核心。

[1]闫林.数理逻辑基础与粒计算[M].北京:科学出版社,2007

[2]Wang C Z,He Q,Chen D G.A novel method for attribute reduction of covering decision system[J].Information Sciences,2014(254):181-196

[3]Jia X Y,Liao W H,Tang Z M.Minimum cost attribute reduction in decision-theoretic rough set models[J].Information Sciences,2013(219):151-167

[4]Yan L,Yan S.Granular computing and attribute reduction based on a new discernibility function[J].International Journal of Simulation: Systems,Science and Technology,2016,17(33):24.1-24.10

[5]McAllister R A,Angryk R A.Abstracting for dimensionality reduction in text classification[J].International Journal ofintelligent Systems,2013,28(2):115-138

[6]闫硕,闫林.数据关联的粒化树描述方法[J].模式识别与人工智能,2015,28(12):1057-1066

[7]Tagarelli A.Exploring dictionary-based semantic relatedness in labeled tree data[J].Information Sciences,2013,220:244-268

[8]Yan S,Yan L,Wu J Z.Rough data-deduction based on the upper approximation[J].Information Sciences,2016,373:308-320

[9]Yan L,Yan S.Granular reasoning and decision system's decomposition[J].Journal of Software,2012,7(3):683-690

[10]She Y H.On the rough consistency measures of logic theories and approximate reasoning in rough logic[J].International Journal of Approximate Reasoning,2014,55(1):486-499

[11]闫林,高伟,闫硕.数据合并的结构粒化方法与矩阵计算[J].计算机科学,2017,44(9):261-265

[12]Min F,Hu Q H,Zhu W.Feature selection with test cost constraint[J].International Journal of Approximate Reasoning,2014,55(1):167-179

[13]Ma W J,Xiong W,Luo X D.A model for decision making with missing,imprecise,and uncertain evaluations of multiple criteria[J].International Journal ofintelligent Systems,2013,28(2):152-184

[14]Yao J T,Azam N.Web-based medical decision support systems for three-way medical decision making with game-theoretic rough sets[J].IEEE Transactions on Fuzzy Systems,2015,23:3–15

[15]Pauker S G,Kassirer J P.The threshold approach to clinical decision making[J].New England Journal Medicine,1980,302:1109–1117