随着信息技术的发展，数据的获取变得越来越简单，如何有效地利用数据，从数据海洋中获取有价值的规律、知识、信息成为摆在人们面前的突出问题。一些不依赖于先验知识，单纯以数据驱动的理论和方法在这一背景下产生和发展，如形式概念分析^[1]、粗糙集^[2]、模糊集^[3]、商空间^[4]等理论，这些理论虽然只有30多年甚至更短的时间，但是显示出其强大的生命力，并有相互融合，共同快速发展的趋势^[5]。

形式概念分析(formal concept analysis，FCA)理论由德国数学家Will.R教授于1982年提出。FCA以形式背景为研究对象，通过研究对象和属性之间的二元关系，发现形式背景中蕴含的知识和规则，并通过Hasse图的形式形象地表示出来。因在知识发现、规则提取等领域的优势，使得FCA理论在知识工程、信息检索等领域有效地被利用^[6]。

洪文学等^[7-8]在形式概念分析的基础上，以人类认知机理为出发点，通过对形式背景中属性的属性、对象的对象的研究，提出了偏序结构理论，创新性地提出异于Hasse图的形式背景知识可视化表示方法——偏序结构图。偏序结构图与Hasse图相比，其突出优势表现在支路之间相互无交叉，可以有效解决Hasse图在对象和属性关系复杂时可视化效果变差，失去可视化知识发现利用价值的问题。偏序结构理论已在中医诊疗知识发现^[9]、英语语言学^[10]等领域得以应用。

本文在将决策数据转化为决策模式的基础上，将偏序结构理论的思想应用于决策模式信息表，提出一种完全不依赖先验知识、以数据(决策模式信息表)为驱动的决策知识发现和规则提取可视化新方法——属性偏序决策图(decision diagram of attribute partial ordered structure，DDAPOS)，介绍其生成原理和算法，通过实例分析其使用方法、特点及有效性。

1 基础定义

定义1    形式背景。称三元组(U, A, I)为一个形式背景。其中U是有限非空对象集合，每个x_i∈U为形式背景的一个对象；A为有限非空属性集合，每个a_i∈A为形式背景的一个属性；I表示U与A之间的二元关系，I⊆U×A。

定义2    决策信息表。称五元组(U, C, I, D, J)为一个决策信息表。其中U是有限非空对象集合，即论域，C为有限非空条件属性集合，D为决策属性，I表示论域U与条件属性C之间的映射关系，J表示论域U与决策属性D之间的映射关系。其中三元组(U, C, I)为一形式背景。表 1所示为决策信息表的例子。

在决策信息表中，如存在若干个对象其对应条件属性与决策属性完全相同，称其为同模式对象，同模式对象的个数，称为该模式的度。如表 1中，x₇与x₈即为一组同模式对象，决策信息表中的一个模式记为m，所有的模式构成模式集M。

定义3    决策模式信息表。决策信息表(U, C, I, D, J)对应的六元组(M, C, I′, D, J′, De)称为决策模式信息表。其中M是模式集合，C为条件属性集合，D为决策属性，De为模式的度。I′表示模式集合M与条件属性C之间的映射关系，J′表示模式集合M与决策属性D之间的映射关系。表 1所对应的决策模式信息表如表 2所示。

在决策模式信息表中，若任意两个模式条件属性完全相同时，决策属性亦相同，则此决策模式信息表称决策模式一致信息表。反之，此决策信息表称为决策模式不一致信息表。在决策模式不一致信息表中，条件属性相同的模式是无法区分的，因此需要对决策不一致模式的结果按某种规则进行判别而转化为决策模式一致信息表。

定义4    最大共有条件属性。在决策模式信息表(M, C, I′, D, J′, De)所对应的形式背景(M, C, I′)中，如果条件属性c∈C满足g(c)=U，则称属性c是形式背景(M, C, I′)的最大共有条件属性。

定义5    共有条件属性。在决策模式信息表(M, C, I′, D, J′, De)所对应的形式背景(M, C, I中，如果属性c₀, c₁, …, c_k∈C满足g(c_i)⊆g(c₀)，其中i=1, 2, …, k, k≥2，则称在形式背景(M, C, I′)中，条件属性c₀是条件属性集合{c₁, c₂, …, c_k}的共有条件属性。

2 属性偏序决策图 2.1 属性偏序决策图生成原理

由认知心理学可知：在一定情景和经验的背景下，人类是通过客观事物具有的属性特征来认知事物的。基本的认知原理可以描述为：特征相同靠近相同，特征不同远离相同，在相同特征中找出不同，在不同特征中找出相同。这样的描述蕴含着：相似性原理(相同靠近相同)，相异性原理(不同远离相同)，自上而下感知原理(相同之中找不同)，自下而上感知原理(不同之处找相同)。图 1给出了一般化认知机理模型示意图^[11]。

属性是各类事物特征的表达，属性间的关系表达了研究问题的概念之间的关系。共有属性表达的一定是事物普遍存在的现象，是共性的表达，具有较大的外延和较浅的内涵。从人类认识模式知识的角度来看，可以构造出以属性特征和对象相似性为指标的层次结构图。

2.2 属性偏序决策图生成算法

根据属性偏序决策图的生成原理，构建属性偏序决策图的算法描述如下所示。

构建属性偏序决策图

输入决策一致模式信息表(M, C, I′, D, J′, De)；

输出属性偏序决策图(N, E, R)；

1) 提取决策模式一致信息表(M, C, I′, D, J′, De)中的(M, C, I′)构成形式背景；

2) 生成属性偏序结构图^[12]；

3) 根据属性偏序结构图每一分支对应的模式标注其决策属性，形成决策层；

4) 从根节点由上至下检索各支路，当检索至某节点覆盖之下各支路模式完全一致时，停止检索此节点之下的支路和节点，并将此节点下各支路上的节点标记为隐藏节点；

5) 直至检索完所有支路，所得结果即为属性偏序决策图。

表 2所示决策模式信息表对应的属性偏序决策图如图 2所示。由图可见，属性偏序决策图在结构上分为决策规则表示层和决策规则输出层两个层次。图中虚线表示的节点为隐藏节点，不参与知识发现和规则提取过程。决策表示层是一个典型的树结构，其中每一个节点表示一个条件属性，图中最顶层为最大共有条件属性。树中根据条件属性的偏序关系由上而下形成若干个节点和边构成的支路，其中每一条支路即为一种决策模式。根据属性偏序决策图中支路聚类形成的群结构、子群结构及每条支路对应的决策属性即可完成决策规则的输出。

2.3 基于属性偏序决策图的规则提取方法

基于属性偏序决策图自顶向下的构图原则，条件属性中普遍性强在上层，可以从集群结构、集子群结构、支路和节点等不同角度对原始数据进行知识发现。支路条件属性集合表达的一条决策模式，即一个决策模式具有什么属性。图中同一子群结构表达的为模式间相似性；不同子群结构表达决策模式之间的差异性。综合属性偏序决策图条件属性偏序关系及决策属性，即可得出最终的规则提取。图 2所示的属性偏序决策图决策结果输出可表示为表 3。

3 实例实验结果与分析

下面通过一个医学诊断的实例介绍属性偏序决策图的具体使用方法，并验证其规则提取的有效性。

3.1 实验数据

选用UCI数据库的Breast Cancer Wisconsin Data Set(BCWD)数据集验证属性偏序决策图的有效性，数据集属性组成如表 4所示。该数据集共有699个样本(其中有16个样本存在属性缺失)，9个属性，2个类(良性、恶性)。本实验剔除了这些有属性缺失的样本，因此实际使用了数据集中样本683个。实验采用10折交叉验证的方式对所述方法的可行性进行验证，并与主流的模式分类算法进行了对比分析。

3.2 实验过程

1) 原始数据特征(属性)选择。根据原始数据分布，利用lasso算法完成特征子集选择，特征相关序列为：BN、U_csh、U_csi、CT、BC、NN、MA、SECS、M^[13]。本例选取其中3个属性：BN、U_csh、U_csi参与决策生成。

2) 原始数据粒化，生成决策形式信息表。以数据驱动的决策规则生成中，数据的形式可能是数值型、名义型、布尔型、区间型等。所有的原始数据需根据不同粒化规则，转换为布尔型规则。根据原始数据分布，按表 5规则完成数据粒化生成决策信息表如表 6所示。

3) 根据决策形式信息表生成决策模式信息表。检索决策信息表中的模式，得到乳腺癌数据决策模式信息表如表 7所示。

表 8为决策模式不一致信息表，对条件属性相同但决策属性不同的模式中，按照模式度较小的模式的决策属性服从模式度较大模式的原则进行修正，得到表 8所对应的决策模式一致信息表如表 8。

4) 生成属性偏序决策图。根据表 8决策一致模式信息表生成属性偏序决策图如图 3所示。

5)根据属性偏序决策图，完成决策规则提取任务。由图 3所示属性偏序决策图提取的规则如表 9所示。

3.3 结果分析

应用上述诊断规则对数据集进行诊断，同时与主流模式分类算法(kNN、Naive Bayes、SVM、C5.0、Random Forests)对比结果见表 10。通过对比可以发现，本文所述属性偏序决策图在只有3个属性参与规则提取的条件下，提取的诊断规则在各项指标上均较理想，达到了主流模式分类和知识发现方法的水平。通过增加参与规则提取的属性，改善粒化规则等措施，各项指标仍有提高的空间。与常规模式识别方法(如kNN、SVM等)相比，属性偏序决策图可以将决策规则以图形的方式进行明确地表示，这一特性可以有效地沟通领域专家与数据分析专家，降低其在具体领域的应用门槛。

4 结束语

本文以决策模式信息表为研究对象，提出一种基于属性偏序关系的、不依赖于先验知识完全以数据驱动的规则提取可视化方法——属性偏序决策图。属性偏序决策图通过属性的聚类完成事物“类内紧，类间松”的聚类，并以直观图形的形式进行表示，从中发现事物之间相区别的属性，从而达到提取事物共同特征的目的。属性偏序决策图因不需要进行复杂的浮点运算，其算法运算速度快。另外，该方法在实际应用中还有若干问题有待解决，如如何根据原始属性生成决策模式信息表、如何处理决策过程中的不确定性问题、如何提供人机交互方式完成专家知识与机器学习的融合等，都有待进一步研究。