基于属性拓扑的属性间因果关系可视化推断

刘文远，冯春辉，张　涛，洪文学

(1. 燕山大学 信息科学与工程学院，河北 秦皇岛　066004；2. 燕山大学 电气工程学院 河北 秦皇岛　066004)

基于属性拓扑的属性间因果关系可视化推断

刘文远1，冯春辉1，张涛1，洪文学2

(1. 燕山大学 信息科学与工程学院，河北 秦皇岛066004；2. 燕山大学 电气工程学院 河北 秦皇岛066004)

因果关系推断是因果顺序理论分析的重要研究内容之一。本文利用属性拓扑理论，提出基于属性拓扑的因果关系可视化推断方法。该方法利用属性拓扑的可视化特点，以属性拓扑中的伴生关系为基础，对属性对所属对象集之间的依赖关系进行分析和推理。通过属性拓扑中属性去除不断地更新形式背景，从而推断出各属性间的因果关系。该算法使因果关系计算精准、可视化且易于实现。

属性拓扑；形式概念；属性关系；因果顺序理论；可视化

本文著录格式：刘文远，冯春辉，张涛，等. 基于属性拓扑的属性间因果关系可视化推断[J]. 软件，2016，37（9）：62-67

0　引言

因果关系是客观事物普遍联系和相互作用的一种表现形式，其特征主要包括因果性、非对称性和可推理性等。因果关系大体可分为机制型和时序型两种，前者从原因导致结果的方式和机制上阐述因果关系，后者从过程上表述原因和结果的先后出现关系。因果关系的前件“原因”主要包括孤立系统某一时刻的存在状态、对某结果的产生起了作用的内外因素之全体等；后件“结果”主要包括孤立系统某一（后继）时刻的存在状态、一般环境中的某个原因所产生的全部后效等。因此，可将因果关系表述为：因果关系是事物在时间上演化发展的法则，本质上是时序与过程的关系，即事物引起与被引起、产生与被产生的关系，具有解释事物或预测变化的功能。

因果关系理论最早于20世纪50年代由Simon教授所提出[1]。随着研究的深入，因果关系理论被广泛地应用到故障预测与诊断、专家系统的构建[2]，约束网络模型[3]，人工智能[4]，经济学[5-7]，信息学[8]等领域，成为解释和诊断大规模数据的一种有效工具。目前，关于因果关系推理的方法主要分为因果顺序理论，因果推理形式框架和分层因果关系上的定性推理（LCQR）等方法。因果顺序理论是以有限表分析法把物理系统抽象成有关变量间的约束关系[9]，随之用因果结构算法把约束集转化为因果关系集，但该方法实质上是对应着高斯消元法，处理过程更趋于定量化且无法处理反馈情况。形式框架对确定性因果关系、简化的确定性因果关系和因果图关系进行了直观的解释，对因果推理的问题和过程进行了形式描述。由于该方法给出了一个比较完善的关于定性推理的形式化框架，所以在因果推理上要优于因果顺序理论。LCQR采用基于分层因果关系层次结构表示，将不影响上层变量（结果）状态的下层变量（原因）的可能状态变化组合在一起，推理过程自下向上，逐层转换过滤。但由于缺乏一些控制信息和有效的过滤算法，所以得到的结果并非特别的精确。

然而当前研究的方法普遍存在一些问题：因果顺序理论处理过程过于复杂且不能直观表示各系统变量间的因果关系；形式框架虽然给出了比较完善的形式化框架，但受限于框架，可视化效果并不明显。LCQR计算复杂度高且对层与层之间的过滤算法要求较高。针对上述问题，本文提出基于属性拓扑的属性间因果关系可视化推断方法，该算法以半生属性为纽带，根据属性对所属对象集合的关联性和形式背景的不断更新，可视化的推断出各属性间的因果关系。

1　属性拓扑中属性间因果关系的推断

1.1实际系统抽象成形式背景

现实生活中，实际系统的内部变量对输入有依赖，内部变量对输出有影响，内部变量之间也会相互影响，如何影响，影响程度如何，都需要用数学语言来精确地定量、定性描述，只有用数学语言描述后，系统特性才得以精确地反映。所以实际系统往往都与相应的数学模型相对应。数学模型是描述系统输入、输出变量以及内部各变量之间关系的数学表达式。

属性拓扑处理的对象为形式背景，所以在推断实际系统变量之间的因果关系时，首先需要把描述实际系统的数学模型转化成对应的形式背景。转化过程如下：

设有如下数学模型描述的实际系统

其中,,abc为描述实际系统的变量。每个方程说明其中的变量之间存在一定的定量关系，因此可去掉运算，将每一个方程看作是一个对象，即将上式中的（1），（2），（3）分别看作对象1，2，3。将每个方程中的变量看作该对象所拥有的属性，其中对象1的属性包括,ab，对象2的属性包括,ac，对象3的属性包括,bc。经过上面的转化后，便可得到描述该系统数学模型的形式背景表示形式，系统经转换后的形式背景如表1所示。

表1　系统对应形式背景Table 1　System form background

1.2形式背景的属性拓扑表示

形式背景是形式概念分析[10]的研究对象，也是本算法的数据表示方式。在形式概念分析[11,12]中，形式背景被定义为一个三元组由一个形式对象集合G、一个形式属性集合M以及决定一个对象拥有哪些属性的二元关系集合I所组成。形式背景各属性之间存在包含关系、相容关系和互斥关系。由于本文主要利用了属性间的包含关系，所以下面仅介绍属性间的包含关系。

属性间的包含关系指两个属性所属对象集为包含关系。如下页表2中，属性b与属性c之间即为包含关系。

表2　属性间的包含关系Table 2　include relationship between attributes

由形式背景的预处理[13]可知，全局属性、空属性、等价属性都可被净化掉且不影响计算的结果，去掉上述冗余信息后得到的形式背景称为净化背景。如表3中，4为满行对象，故被删除。得到净化背景如表4。为了描述简便，若不作特殊声明，下文中提到的所有形式背景均为净化后的形式背景。

属性拓扑主要分析形式背景中属性之间的关系，是属性间关系的加权图表示。因此在存储上可采用邻接矩阵的顺序存储与邻接表的链接存储两种方式。本文采用邻接矩阵的存储方式。表示。V为属性集合，即

表3　原始形式背景Table 3　original form background

表4　净化后的形式背景Table 4　form background after purification

由上页式（4）可知，属性拓扑图中任意两个属性间的权值为两个属性对应的对象集合的交集。

利用该方法得到表4形式背景对应的属性拓扑图，如上页图1。

图1　表4对应的属性拓扑Fig.1　Table 4 attribute topology

1.3伴生关系与因果推断

性质1在形式背景中，如果属性im是属性jm的伴生属性，那么属性jm是属性im的必要条件。

证明：因为属性im是属性jm的伴生属性，由可知属性im所属对象集为属性所属对象集的子集。由大数据偏序结构生成原理[14]中的偏序结构图生成过程可知，对象集多的集合可以推导出其真子集的对象集，反之则不成立。因此，由属性jm可以推出属性im，属性im不可以推出属性jm，所以属性jm是属性im的必要条件。

证明：设属性mi所属对象集为属性mm所属对象集为{1,2}，属性mn所属对象集为属性mp所属对象集为属性mq所属对象集为{1,2,4}，此时如果将上面的属性mn所属的对象集变为{3,4,5}，则上式就变为了空集。证毕。

性质4随着形式背景的更新，各属性间的因果关系可能会由无转化为有。

性质5属性间的纯相容关系包含相容关系和互斥关系。

纯相容关系包含相容关系是指属性间的相容关系不会随着形式背景的更新而变为因果关系。在初始形式背景中，如果某个属性与其它属性之间的关系为互斥关系，那么很显然这种互斥关系不会随着形式背景的更新而改变，所以互斥关系也属于纯相容关系。

1.4属性拓扑更新与整体因果推断

属性拓扑的处理对象为形式背景，所以属性拓扑会随着形式背景的更新而不断更新。以下分析属性拓扑的更新中省去了形式背景和形式背景的更新。

推断各属性间是否存在因果关系可通过属性所属对象集之间的包含关系进行判断。为了简便，下面描述的属性拓扑图省去了属性之间的权重，同时在各属性后面添加其所属的对象集。设有原始属性拓扑图如图2所示。

图2　原始属性拓扑Fig.2　primitive attribute topology

对属性间进行因果推断时，可任意选择其中的一个属性作为初始属性，然后推断其他属性与该初始属性间的因果关系。比如初始属性选择图2中的属性E,由定义2可知，DE→，EC→。属性E与属性A、B为纯相容关系，不存在因果关系。由EC→可知，属性C为属性E的果，所以在属性拓扑图中去除属性E之前，要首先分析属性C，否则去除属性E的同时也去除了属性C，这就可能导致属性间的因果推断不准确、不完全。为了减少遍历次数和避免遗漏属性间的因果关系，本文选择各属性所属对象集中对象个数最少的属性作为初始属性。

图3　更新1次属性拓扑Fig.3　update 1 times

图4　更新2次属性拓扑　Fig.4 update 2 times

图5　更新3次属性拓扑Fig.5　update 3 times

2　算法实现

本算法可归结为以下五步：

步骤1对于任意给定的实际系统的数学模型，通过上述方法，将其转化成对应的形式背景净化后，绘制简化的属性拓扑图，用Sign记录M。

步骤2对属性集M中的属性mi按由小到大排序，由最小的0()Nm得到属性km。求出km所属对象集W。对于任意mj属于求出mj所属对象集V。如果W包含于V，即可推断出一个因果关系为：同时将属性加入属性集B中。

步骤3删去属性km和km所属对象集中的对象，并对形式背景进行更新。

步骤4重复步骤2和步骤3，直到形式背景中G与M不存在二元关系I为止。

步骤5将属性集Sign赋值为属性集Sign与属性集B的差集，如果Sign中存在属性，则输出Sign中的所有属性，此处的属性与其他属性为纯相容关系，不存在因果关系。

Pseudocode表示为：

Input: 形式背景

Output: 各属性间因果关系

算法如下：

3　实验

下面我们以描述行人信号延误系统为例，该系统可以描述成如下数学模型：

式中，pd：行人信号延误s（）；NUk：非均匀到达调整系数；ER：有效红灯时间长度s（）；k：红灯相位到达的行人平均延误随时间的变化率；RN：红灯期间到达行人数（人）；CN：周期到达行人数（人）；C：信号周期；G：有效绿灯时间长度s（）；A：净空时间s（）；wP：违章人数占总人数的比例；q：行人流率。

系统转化后对应的形式背景如表5所示，简化属性拓扑图如图6所示。

表5　系统对应的形式背景Table 5　system form background

图6　形式背景对应的简化属性拓扑图Fig.6　simplified attribute topology for formal context

形式背景带入算法后便推断出各系统变量之间的如下因果关系：

分析结果可知，系统变量因果关系中的因即为行人信号延误的基础参数，包括：周期时长（C），有效绿灯时间（G），周期到达行人数（NC），红灯期间到达行人数（NR），行人流量（q）和违章比例（PW）。因此，研究行人信号延误系统时，可将以上基础参数作为系统的主要影响因素，以便使数据分析过程高效、有序。

4　结　论

针对目前因果关系推理方法中存在的趋于定量化，不精确和可视化效果差等问题，本文提出利用属性拓扑进行因果关系的推断方法。该算法结合了集合和图的相关理论，将属性间的因果关系直观的表现在属性拓扑图上。构造过程相对直观，且构造步骤简单，可视化的生成了属性间的因果关系。属性拓扑为因果关系推理提供了一种新的表示方法，下一步的工作将对本算法进行完善和优化及对属性间多对多的因果关系进行证明。

[1] Shi C Y. Qualitative reasoning method [M]. Tsinghua University press, 2002. (石纯一. 定性推理方法[M]. 清华大学出版社, 2002.)

[2] Iwasaki Y, Simon H A. Theories of causal ordering: Reply to de Kleer and Brown[J]. Artificial Intelligence, 1986, 29(1): 63-72.

[3] Angel Fernandez-leal, Vicente Moret-Bonillo, Eduardo Mosqueira-Rey. [J]. Expert Systems with Applications, 2009, 36(1): 27-42.

[4] Zhang H Y, Qiua Z J, Tian X. A Study on Material Functional Connectivity of the Human Brain via Granger Causality[J]. Advanced Materials Research, 2012, 548: 833-838.

[5] Liu Y, Yan B, Yang Z. Urbanization, economic growth, and carbon dioxide emissions in China: A panel cointegration and causality analysis[J]. Journal of Geographical Sciences, 2016, 26(2): 131-152.

[6] Dagher L, Yacoubian T. The causal relationship between energy consumption and economic growth in Lebanon[J]. Energy Policy, 2012, 50(6): 795–801.

[7] Thurston L, Yezer A M J. Causality in the Suburbanization of Population and Employment[J]. Journal of Urban Economics, 2015, 35(1): 105-118.

[8] Hsu L Y. Multipartite information causality[J]. Physical Review A, 2012, 85(3): 102-108.

[9] Iwasaki Y, Simon H A. Retrospective on causality in device behavior[J]. Artificial Intelligence, 1993, 59(1): 141-146.

[10] Medina R, Obiedkov S. Formal Concept Analysis[M]//Handbook on Ontologies. 2008: 180.

[11] Ganter B. Formal Concept Analysis: Mathematical Foundations[C]//Springer-Verlag New York, Inc. 2010.

[12] Stumme G. Formal Concept Analysis[M]// Handbook on Ontologies. 2008:199-200.

[13] Zhang T, Hong W X, Jing L U. Attribute tree representation for formal context[J]. Systems Engineering-Theory & Practice, 2011,31 (Suppl 2): 197-202(S2): 197-202. (张涛, 洪文学, 路静. 形式背景的属性树表示[J]. 系统工程理论与实践, 2011, 系统工程理论与实践, 2011, 31(增刊2): 197-202(S2): 197-202.)

[14] Hong W X, Li S X, Zhang T, et al. Generation principle of partial ordered structure towards big data[J]. Journal of Yanshan University, 2014(5): 388-393. (洪文学, 李少雄, 张涛,等. 大数据偏序结构生成原理[J].燕山大学学报, 2014(5): 388-393.)

Visual Inference of Causal Relationships Between Attributes Based on Attribute Topology

LIU Wen-yuan1, FENG Chun-hui1, ZHANG Tao1and HONG Wen-xue2
(1. College of Information Science and Engineering, Yanshan University, Qinhuangdao, 066004; 2. College of Electrical Engineering, Yanshan University, Qinhuangdao, 066004)

Causal inference is one of the important research contents in the analysis of causal order theory. In this paper, a visual inference method of causal relation is proposed based on the theory of attribute topology. This method makes use of the visual characteristics of attribute topology, based on the companion relation in attribute topology, analyzes and reasoning the dependency between attributes on the set of objects. The formal context is updated by attribute removal in attribute topology, and the causal relationship between attributes is inferred. This algorithm makes the causal relation calculation accurate, visual and easy to implement.

Topological properties; Formal concept; Property relations; Causal ordering theory; Visualization

TP311

A

10.3969/j.issn.1003-6970.2016.09.015