基于确定性因子的启发式属性值约简模型

余顺坤，闫泓序

（华北电力大学经济与管理学院，北京 102206）

0 引言

作为一种新型软计算理论与智能算法，粗糙集理论可以有效处理具有不确定、不精确或不完整信息的数据［1-2］。它能够在不依靠任何先验知识的情况下，只根据数据本身完成挖掘和推理［3］，是对专家系统进行数据挖掘的强大工具［4-5］。属性值约简是粗糙集理论研究和应用的核心课题之一，也是构建规则提取算法［6-13］和归纳规则分类器［14-15］的重要技术基础。属性值约简是指在不影响决策系统知识表达能力的前提下，去除其中冗余属性值的过程［16］，它不但能够从原始数据库中直接提取出可读性高、便于应用的简约规则，而且还能在不降低专家系统可分辨性的基础上提高其清晰度，并从中揭示出以往未知、有潜在价值的信息，从而实现知识发现［10，16］。

目前，针对构建属性值约简模型这一问题，学术界已经取得一定进展，主要包括基于区分矩阵的属性值约简模型［10，13，17-19］以及启发式属性值约简模型［20-23］两个建模方向。其中，基于区分矩阵的属性值约简模型思想简单，易于理解；但当将其应用于大规模数据集时，往往需要构造与遍历大型矩阵，导致算法的时间与空间复杂度较高。另一方面，大多数启发式属性值约简模型程序复杂，难以实现，且计算复杂度较高。最近，Chen 等［9］提出了一种基于决策依赖度的启发式属性值约简模型，能够有效控制算法的时−空复杂度，但仅适用于具有较高重复性或冗余性的数据集，对数据本身特征要求较高。除此之外，现有属性值约简模型大多倾向于产生极简短规则，导致专家系统的决策能力受到较大程度削弱，并且未能对数据库进行多层次挖掘以获得多元丰富的决策描述，导致数据知识的本质特征和内在规律没有被充分发现与理解。

针对以上问题，在现有研究的基础上，本文提出了一种基于确定性因子的启发式属性值约简模型。首先，简要阐述粗糙集理论的相关理论基础；然后，开发了几种不同性质的属性集工具，用韦恩图的形式直观展示它们的逻辑联系，并提出相关定理与证明；其次，构造一个约简信息函数，为约简属性赋值；再次，将确定性因子作为启发信息，提出一种新的属性值约简模型，简称CerFac 模型，并给出其程序伪代码，以直观展示模型运行路径；最后，采用已有研究中的模拟数据开展模型应用与验证，并对模型特点进行总结与讨论。研究表明，CerFac 模型可以有效去除冗余信息，并能导出多元简约规则，同时易于编程实现。特别地，新模型适用于重复或冗余较少的数据集，对数据结构要求低，且应用范围广泛。

1 理论基础

先简要回顾粗糙集理论的相关理论基础［1-2］。

定义1决策系统。设S=(U，A，V，f)为一个信息系统，其中，U={x1，x2，…，xn}为非空有限对象集，称为论域；A={a1，a2，…，am}为非空有限属性集；V为属性值域，即V=，其中k=1，2，…，m，这里表示属性ak∈A的取值；f：U×A→V称为信息函数，它根据每个属性为每个对象赋予一个信息值，即∀xi∈U，∀ak∈A，f(xi，ak)=。特别地，若A由一个条件属性集C和一个决策属性集D组成，且二者满足C∪D=A，C∩D=∅，则称S为决策系统，表示为S=(U，C∪D，V，f)。当D中只有一个决策属性d时，通常将决策系统表示为S=(U，C∪{d}，V，f)。

定义2等价类。设S=(U，C∪{d}，V，f)为决策系统，∀xi，xj∈U，∀P⊆C，P≠∅，定义对象间关于P的不可分辨关系为：IND(P)={(xi，xj)|(xi，xj)∈U×U，∀ak∈P，f(xi，ak)=f(xj，ak)}。对象x（ii≤n）关于IND（P）的等价类定义为：

[xi]IND(P)={xj|(xi，xj)∈IND(P)}

定义3确定性因子。设S=(U，C∪{d}，V，f)为决策系统，∀xi∈U，∀P⊆C，P≠∅，定义决策对象xi关于不可分辨关系IND（P）与IND（d）的确定性因子为：

显然0

2 CerFac模型

下面先介绍本文CerFac 模型的相关概念与符号。

定义4k-属性集。设S=(U，C∪{d}，V，f)为决策系统，其中：|C|=m；∀aj∈C（j=1，2，…，m），定义含有k个属性的集合为k-属性集，表示为Ak，即Ak={A⊆C||A|=k}，其所含元素总数为从m个属性中随机抽取k个的组合数。A*k={Ak|1≤k≤m，k∈Z}为决策系统中条件属性的全部可能组合，称之为系统属性格结构，k为格结构的层次。

特定对象xi的k-属性集称为k-对象属性集，表示为Ai，k，将Ai，k中的各属性元素ai，k∈Ai，k按照以下标准进行划分：

1）若决策对象xi关于ai，k的信息表达能力与关于属性集C的一致，则将ai，k定义为xi的k-核属性（或集合），全部k-核属性（或集合）称为k-核属性集，表示为coreAi，k，即cer(coreAi，k，xi)=cer(C，xi)。反之，则将ai，k定义为xi的k-非核属性（或集合），全部k-非核属性（或集合）称为k-非核属性集，表示为ncoreAi，k，即cer(ncoreAi，k，xi)≠cer(C，xi)。

2）若ai，k为xi的最小k-核属性（或集合），则将ai，k定义为xi的k-约简属性（或集合），全部k-约简属性（或集合）称为k-约简属性集，表示为redAi，k，即redAi，k=，其中，∀ni，k-1∈ncoreAi，k-1。反之，则将ai，k定义为xi的k-非约简属性（或集合），全部k-非约简属性（或集合）称为k-非约简属性集，表示为nredAi，k。有nredAi，k=ncoreAi，k+sredAi，k，其中，sredAi，k表示xi的k-约简属性集超集，它是一种包含（k-1）层约简属性的k-核属性集，它虽能保持xi的信息表达能力不变，但并非最小集合，因此属于k-非约简属性集。

3）对象xi的k-属性集Ai，k由redAi，k、sredAi，k与ncoreAi，k综合构造而成，即Ai，k=redAi，k+sredAi，k+ncoreAi，k。

为了清晰形象地说明Ai，k、coreAi，k、ncoreAi，k、redAi，k、nredAi，k与sredAi，k之间的逻辑关系，以下进一步给出其韦恩图，如图1 所示的k-对象属性集元素韦恩图，其中redAi，k、sredAi，k与ncoreAi，k不同时为空集。

图1 k-对象属性集元素韦恩图Fig.1 Venn diagram for elements within a k-object attribute set

定义5k-候选约简属性集。定义决策对象的潜在k-约简属性集为k-候选约简属性集，表示为candAi，k，其由（k-1）层非核属性（或集合）构造而成，即candAi，k=，其中，∀ni，k-1∈ncoreAi，k-1。对于candAi，k，有以下定理成立：

定理1对于决策系统S中某对象xi，其k-候选约简属性集由k-约简属性集及k-非核属性集构成，即∀xi∈U，有candAi，k=redAi，k+ncoreAi，k成立。

证明 因为∀xi∈U（k=1，2，…，m），redAi，k-1、sredAi，k-1与ncoreAi，k-1不同时为空集。根据定义4，第k层属性集Ai，k由第k-1 层属性集redAi，k-1、sredAi，k-1与ncoreAi，k-1构成；又因为redAi，k-1或sredAi，k-1将构成sredAi，k，所以Ai，k=sredAi，k+，其中，∀ni，k-1∈ncoreAi，k-1；根据定义4，有Ai，k=sredAi，k+redAi，k+ncoreAi，k，所以=redAi，k+ncoreAi，k；又根据定义5，有candAi，k=，即candAi，k=redAi，k+ncoreAi，k，综上得证。

根据定义5 和定理1，即可构造CerFac 模型，其基本思想是：对于特定决策对象的某一属性格层k，首先应用确定性因子过滤出k-1 层非核属性；然后将其进行组合，构造形成第k层候选约简属性集；据此，再次利用确定性因子进行过滤，即可获取决策对象的第k层约简属性集。

定义6约简信息函数。设S=(U，C∪{d}，V，f)为决策系统，dred(S)=(U，A*∪{d}，V*，f*)为论域属性值约简系统，由每个决策对象xi∈U的属性值约简dred(Si)组合而成。其中：A*i为对象xi的非空有限k-属性组合；V*i为对象xi的约简属性信息值域；f*为约简信息函数，它为决策对象的每个属性组合赋予特定的信息值。∀xi∈U（i=1，2，…，n），A*i=redA*i∪ncoreA*i∪sredA*i，∀a*i∈A*i，∀aj∈a*i（j=1，2，…，m），定义约简信息函数f*如下：

应用CerFac 模型获取的dred（S）中存在大量重复条目信息行，对其执行去重操作，将得到非重复论域属性值约简系统，记为ddred(S)=(U*，A*∪{d}，V*，f*)，系统排列方式按照约简层次k与k-属性组合的形式进行分布，对其依照决策系统的分布形式进行格式标准化，即可得到决策属性值约简系统，记为red(S)=(R，C∪{d}，V*，f*)。

3 CerFac属性值约简模型

应用以上不同性质的属性集工具，将确定性因子作为启发信息，即可自底向上地搜索到决策系统的全部约简属性，再应用约简信息函数对约简属性进行赋值，即可获取决策系统的全体属性值约简。在此，构建基于确定性因子的属性值约简模型CerFac，模型程序伪代码如下所示，其主要包括三大模块：

1）模块A。首先，在k属性格层上，将对象xi的候选约简属性集candAi，k作为中间变量，获取其约简属性集redAi，k；其次，利用约简信息函数f*为redAi，k赋值Vi，k；然后，综合以上结果获取决策对象xi的属性值约简dred（Si）；最后，循环以上步骤，生成论域内每个决策对象的属性值约简，再将其进行组合，形成论域属性值约简系统dred（S）。

2）模块B。对dred（S）执行去重操作，生成非重复论域属性值约简系统ddred（S）。

3）模块C。对ddred（S）进行格式标准化，最终获取决策属性值约简系统red（S）。

模块A 是CerFac 模型的核心模块，其主要功能是对特定决策对象的属性组合类型进行精准划分，通过一个具体例子，来对该模块的执行过程进行形象直观说明，如图2 所示的CerFac 模型中模块A 执行概览。

图2 中展示了某决策对象的属性格结构，其中，自上而下依次为第0 至第m（条件属性总数）层属性格。相邻两属性格层之间的连线代表将多个属性（或集合）组合成为更大的属性集。假设图中某一决策对象xi的条件属性集为｛A，B，C，D｝，其所有可供构造的k-属性组合如图所示。以第k=1 属性格层为例，若属性A经确定性因子检查是核属性（在此，亦为约简属性），那么其超集｛｛A，B｝，｛A，C｝，｛A，D｝｝（格层k=2）、｛｛A，B，C｝，｛A，B，D｝，｛A，C，D｝｝（格层k=3）以及｛A，B，C，D｝（格层k=4）将不再执行算法在高序格层上的循环遍历。同时，在第k=1 格层上的非核属性｛B｝、｛C｝和｛D｝，将构成k=2 格层上的候选约简属性集｛B，C｝、｛B，D｝和｛C，D｝，再次利用确定性因子进行检查，将其中保持对象确定性因子不变的非核属性集标记为此格层的约简属性集，如｛B，C｝、｛B，D｝，其他则仍旧作为本格层的非核属性集，如｛C，D｝。若本格层的非核属性集总数不小于下一格层编码，则继续组合本格层的非核属性集，以作为下一格层的候选约简属性集，进而循环算法；反之，则终止算法。

图2 CerFac模型中模块A执行概览Fig.2 Execution overview of CerFac model-Module A

由此可知，CerFac 模型秉承自下而上的属性值约简策略，即从决策对象的低属性格层出发，一旦在低格层上搜索到约简属性（或集合），那么对于其他所有高格层中包含该约简属性（或集合）的属性组合将不再运行本文算法，这将显著提升算法的时−空效率。

4 仿真算例

以文献［9］中的算例数据为例，举例说明本文模型CerFac 的应用步骤，其中算例数据集、模型应用过程及相应结果如图3 所示的仿真算例分析所示。模型具体应用过程如下：

1）模块A。图3（a）为算例数据集，从中可看出，该数据集为相容决策系统，表示为S=（U，C∪｛e｝，V，f），其中论域U=｛x1，x2，…，x27｝，条件属性集C=｛a，b，c，d｝，决策属性为e。以对象x9为例，展示应用本模型搜索其属性值约简的具体过程。

首先，根据定义4，生成x9的k-对象属性集A9，k，其中k∈{1，2，3，4}，得A*k={A9，1，A9，2，A9，3，A9，4}={{a，b，c，d}，{ab，ac，ad，bc，bd，cd}，{abc，abd，acd，bcd}，{abcd}}。

然后，根据定义5 获取各k层候选约简属性集以及约简属性（或集合）：

当k=1 时，对象x9的候选约简属性集为candA9，1=｛a，b，c，d｝，根据定义3，计算candA9，1内各元素在论域范围内的确定性因子cer（candA9，1，x9）=｛2/9，1，2/3，3/7｝，据此，将确定性因子1 对应的属性反选为对象x9的约简属性，即redA9，1=｛b｝，那么x9的非核属性集为ncoreA9，1=candA9，1-redA9，1=｛a，c，d｝，因为|ncoreA9，1|>k+1，因而进行下一循环。

当k=2 时，同理，对象x9的候选约简属性集由k=1 层的非核属性组合而成，即candA9，2=｛ac，ad，cd｝，其中各元素确定性因子为cer（candA9，2，x9）=｛1，2/5，1｝，则对象x9的约简属性集为redA9，2=｛ac，cd｝，那么对象x9的非核属性集为ncoreA9，2=｛ad｝，由于|ncoreA9，2|

由此获取到对象x9的各层约简属性（或集合），根据定义6，应用约简信息函数为全部所得约简结果赋予约简信息值，即可生成对象x9的各层属性值约简dred（S9）。同理，可搜索到论域范围内其他全部对象的属性值约简dred（Si），再次根据定义6，将其进行组合，即可形成各约简层次上的论域属性值约简系统dred（S），相关结果如图3（b）～（d）所示，其中：图3（b）为决策系统S在k=1 约简层次上的论域属性值约简系统；图3（c）为S在k=2 层的论域属性值约简系统；图3（d）为S在k=3 层的论域属性值约简系统。

2）模块B。经模块A，在dred（S）中生成了较多条目的重复属性值约简信息行，对其执行去重操作，即可得到非重复论域属性值约简系统ddred（S）。图3（e）为决策系统S在各约简层次上的非重复论域属性值约简系统。

3）模块C。经模块B，获取到属性依照约简层次k及属性组合Ak排列的非重复论域属性值约简系统，对其按决策系统S进行格式标准化，最终生成决策属性值约简系统red（S）。图3（f）为决策系统S的决策属性值约简系统。

图3 仿真算例分析Fig.3 Simulation example analysis

5 讨论

与现有研究相比，应用本文CerFac 模型搜索到的属性值约简具有更高预测精度。比如，文献［9］从此算例数据集中先后挖掘得到的、能够匹配对象x19({a3∧b1∧c1∧d2→e3})的属性值约简依次为{a*∧b*∧c1∧d2→e2}与{a*∧b*∧c1∧d*→e3}，它无论基于规则覆盖率（匹配具有更多一致属性值的约简规则），还是规则生成顺序（匹配优先生成的约简规则），都无法准确预测对象x19，但是CerFac 模型所推演出的属性值约简能对文献［9］中的全部算例数据实现精准预测。

CerFac 模型并非一种逐步剪枝策略，即无需一步步地去除约简属性超集，就可直接得到特定对象的属性约简。此外，新模型聚焦于某决策对象较低格层的非核属性集，将确定性因子作为启发信息，经过简单扫描，即可获取较高格层的属性值约简，亦即直接生成多元、简约，且不影响决策对象信息表达能力的规则描述，这些优势使得CerFac 模型易于计算、编程和执行。

CerFac 模型所生成的简明规则具有较强泛化性与描述力，这使得基于CerFac 模型的分类器具有比较高的稳健性。此外，新模型能够深度挖掘出决策对象多种可能的属性值约简结果，利用某些个性化筛选标准对其进行提取，如规则置信度、规则提升度及规则覆盖度等，即可提取出符合需求、有价值的简约规则，因此CerFac 模型为基于确定性因子的粗糙规则提取算法奠定了技术基础。

CerFac 模型的算法复杂度与决策系统中每个实例对象的条件属性取值及数据规模有关，如设某决策系统含有n个对象，m个条件属性，则：当系统中每一条决策对象的条件属性取值均各不相同时，模型处于最好情况，此时算法时间复杂度为O（n2m）；而当系统中每一条决策对象的条件属性取值均相同，而决策属性值不同时（即完全矛盾系统），模型处于最差情况，此时算法时间复杂度为O（2mn2）。由此，当模型应用于海量数据时，对决策系统先行进行纯化处理［24-25］，或基于MapReduce［26-27］并行运算框架，优先完成行（元组）约简与列（属性）约简［28-30］，将使本模型的运行成本得到进一步改善，这也是下一步的研究方向。此外，新模型将为决策系统推导出多元丰富的简约规则，因此，适用于需要全面性规则来指导实践的研究领域，如市场营销［12，31］等，或是针对成熟专家系统，要求较高预测精度的知识发现任务，如医疗诊断［32］等。

6 结语

本文针对现有属性值约简模型的不足，构建了一种基于确定性因子的自底向上型启发式属性值约简模型。首先，根据粗糙集理论，设计了几种不同性质的属性集工具，并将确定性因子作为启发信息，从中分层搜索特定决策对象的约简属性；然后，开发了约简信息函数，从而实现为决策对象的约简属性赋值；其次，以程序伪代码的形式，直观展示了模型的布置路径与运行流程；再次，以现有研究中的仿真数据为载体，对模型进行了应用与验证；最后，讨论了模型的优势、适用性与延展性。研究表明，新模型可行有效、科学先进，同时具有广阔的应用前景。未来的研究将集中于以下几个方面：1）从行、列约简的角度提升算法效率；2）构建基于CercFac 模型的规则提取算法；3）构建基于CercFac 模型的归纳规则分类器。