劉文遠(yuǎn)，馮春輝，張　濤，洪文學(xué)

(1. 燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島　066004；2. 燕山大學(xué) 電氣工程學(xué)院 河北 秦皇島　066004)

基于屬性拓?fù)涞膶傩蚤g因果關(guān)系可視化推斷

劉文遠(yuǎn)1，馮春輝1，張濤1，洪文學(xué)2

(1. 燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島066004；2. 燕山大學(xué) 電氣工程學(xué)院 河北 秦皇島066004)

因果關(guān)系推斷是因果順序理論分析的重要研究內(nèi)容之一。本文利用屬性拓?fù)淅碚?，提出基于屬性拓?fù)涞囊蚬P(guān)系可視化推斷方法。該方法利用屬性拓?fù)涞目梢暬攸c，以屬性拓?fù)渲械陌樯P(guān)系為基礎(chǔ)，對屬性對所屬對象集之間的依賴關(guān)系進(jìn)行分析和推理。通過屬性拓?fù)渲袑傩匀コ粩嗟馗滦问奖尘?，從而推斷出各屬性間的因果關(guān)系。該算法使因果關(guān)系計算精準(zhǔn)、可視化且易于實現(xiàn)。

屬性拓?fù)?；形式概念；屬性關(guān)系；因果順序理論；可視化

本文著錄格式：劉文遠(yuǎn)，馮春輝，張濤，等. 基于屬性拓?fù)涞膶傩蚤g因果關(guān)系可視化推斷[J]. 軟件，2016，37（9）：62-67

0　引言

因果關(guān)系是客觀事物普遍聯(lián)系和相互作用的一種表現(xiàn)形式，其特征主要包括因果性、非對稱性和可推理性等。因果關(guān)系大體可分為機(jī)制型和時序型兩種，前者從原因?qū)е陆Y(jié)果的方式和機(jī)制上闡述因果關(guān)系，后者從過程上表述原因和結(jié)果的先后出現(xiàn)關(guān)系。因果關(guān)系的前件“原因”主要包括孤立系統(tǒng)某一時刻的存在狀態(tài)、對某結(jié)果的產(chǎn)生起了作用的內(nèi)外因素之全體等；后件“結(jié)果”主要包括孤立系統(tǒng)某一（后繼）時刻的存在狀態(tài)、一般環(huán)境中的某個原因所產(chǎn)生的全部后效等。因此，可將因果關(guān)系表述為：因果關(guān)系是事物在時間上演化發(fā)展的法則，本質(zhì)上是時序與過程的關(guān)系，即事物引起與被引起、產(chǎn)生與被產(chǎn)生的關(guān)系，具有解釋事物或預(yù)測變化的功能。

因果關(guān)系理論最早于20世紀(jì)50年代由Simon教授所提出[1]。隨著研究的深入，因果關(guān)系理論被廣泛地應(yīng)用到故障預(yù)測與診斷、專家系統(tǒng)的構(gòu)建[2]，約束網(wǎng)絡(luò)模型[3]，人工智能[4]，經(jīng)濟(jì)學(xué)[5-7]，信息學(xué)[8]等領(lǐng)域，成為解釋和診斷大規(guī)模數(shù)據(jù)的一種有效工具。目前，關(guān)于因果關(guān)系推理的方法主要分為因果順序理論，因果推理形式框架和分層因果關(guān)系上的定性推理（LCQR）等方法。因果順序理論是以有限表分析法把物理系統(tǒng)抽象成有關(guān)變量間的約束關(guān)系[9]，隨之用因果結(jié)構(gòu)算法把約束集轉(zhuǎn)化為因果關(guān)系集，但該方法實質(zhì)上是對應(yīng)著高斯消元法，處理過程更趨于定量化且無法處理反饋情況。形式框架對確定性因果關(guān)系、簡化的確定性因果關(guān)系和因果圖關(guān)系進(jìn)行了直觀的解釋，對因果推理的問題和過程進(jìn)行了形式描述。由于該方法給出了一個比較完善的關(guān)于定性推理的形式化框架，所以在因果推理上要優(yōu)于因果順序理論。LCQR采用基于分層因果關(guān)系層次結(jié)構(gòu)表示，將不影響上層變量（結(jié)果）狀態(tài)的下層變量（原因）的可能狀態(tài)變化組合在一起，推理過程自下向上，逐層轉(zhuǎn)換過濾。但由于缺乏一些控制信息和有效的過濾算法，所以得到的結(jié)果并非特別的精確。

然而當(dāng)前研究的方法普遍存在一些問題：因果順序理論處理過程過于復(fù)雜且不能直觀表示各系統(tǒng)變量間的因果關(guān)系；形式框架雖然給出了比較完善的形式化框架，但受限于框架，可視化效果并不明顯。LCQR計算復(fù)雜度高且對層與層之間的過濾算法要求較高。針對上述問題，本文提出基于屬性拓?fù)涞膶傩蚤g因果關(guān)系可視化推斷方法，該算法以半生屬性為紐帶，根據(jù)屬性對所屬對象集合的關(guān)聯(lián)性和形式背景的不斷更新，可視化的推斷出各屬性間的因果關(guān)系。

1　屬性拓?fù)渲袑傩蚤g因果關(guān)系的推斷

1.1實際系統(tǒng)抽象成形式背景

現(xiàn)實生活中，實際系統(tǒng)的內(nèi)部變量對輸入有依賴，內(nèi)部變量對輸出有影響，內(nèi)部變量之間也會相互影響，如何影響，影響程度如何，都需要用數(shù)學(xué)語言來精確地定量、定性描述，只有用數(shù)學(xué)語言描述后，系統(tǒng)特性才得以精確地反映。所以實際系統(tǒng)往往都與相應(yīng)的數(shù)學(xué)模型相對應(yīng)。數(shù)學(xué)模型是描述系統(tǒng)輸入、輸出變量以及內(nèi)部各變量之間關(guān)系的數(shù)學(xué)表達(dá)式。

屬性拓?fù)涮幚淼膶ο鬄樾问奖尘?，所以在推斷實際系統(tǒng)變量之間的因果關(guān)系時，首先需要把描述實際系統(tǒng)的數(shù)學(xué)模型轉(zhuǎn)化成對應(yīng)的形式背景。轉(zhuǎn)化過程如下：

設(shè)有如下數(shù)學(xué)模型描述的實際系統(tǒng)

其中,,abc為描述實際系統(tǒng)的變量。每個方程說明其中的變量之間存在一定的定量關(guān)系，因此可去掉運算，將每一個方程看作是一個對象，即將上式中的（1），（2），（3）分別看作對象1，2，3。將每個方程中的變量看作該對象所擁有的屬性，其中對象1的屬性包括,ab，對象2的屬性包括,ac，對象3的屬性包括,bc。經(jīng)過上面的轉(zhuǎn)化后，便可得到描述該系統(tǒng)數(shù)學(xué)模型的形式背景表示形式，系統(tǒng)經(jīng)轉(zhuǎn)換后的形式背景如表1所示。

表1　系統(tǒng)對應(yīng)形式背景Table 1　System form background

1.2形式背景的屬性拓?fù)浔硎?/p>

形式背景是形式概念分析[10]的研究對象，也是本算法的數(shù)據(jù)表示方式。在形式概念分析[11,12]中，形式背景被定義為一個三元組由一個形式對象集合G、一個形式屬性集合M以及決定一個對象擁有哪些屬性的二元關(guān)系集合I所組成。形式背景各屬性之間存在包含關(guān)系、相容關(guān)系和互斥關(guān)系。由于本文主要利用了屬性間的包含關(guān)系，所以下面僅介紹屬性間的包含關(guān)系。

屬性間的包含關(guān)系指兩個屬性所屬對象集為包含關(guān)系。如下頁表2中，屬性b與屬性c之間即為包含關(guān)系。

表2　屬性間的包含關(guān)系Table 2　include relationship between attributes

由形式背景的預(yù)處理[13]可知，全局屬性、空屬性、等價屬性都可被凈化掉且不影響計算的結(jié)果，去掉上述冗余信息后得到的形式背景稱為凈化背景。如表3中，4為滿行對象，故被刪除。得到凈化背景如表4。為了描述簡便，若不作特殊聲明，下文中提到的所有形式背景均為凈化后的形式背景。

屬性拓?fù)渲饕治鲂问奖尘爸袑傩灾g的關(guān)系，是屬性間關(guān)系的加權(quán)圖表示。因此在存儲上可采用鄰接矩陣的順序存儲與鄰接表的鏈接存儲兩種方式。本文采用鄰接矩陣的存儲方式。表示。V為屬性集合，即

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

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

由上頁式（4）可知，屬性拓?fù)鋱D中任意兩個屬性間的權(quán)值為兩個屬性對應(yīng)的對象集合的交集。

利用該方法得到表4形式背景對應(yīng)的屬性拓?fù)鋱D，如上頁圖1。

圖1　表4對應(yīng)的屬性拓?fù)銯ig.1　Table 4 attribute topology

1.3伴生關(guān)系與因果推斷

性質(zhì)1在形式背景中，如果屬性im是屬性jm的伴生屬性，那么屬性jm是屬性im的必要條件。

證明：因為屬性im是屬性jm的伴生屬性，由可知屬性im所屬對象集為屬性所屬對象集的子集。由大數(shù)據(jù)偏序結(jié)構(gòu)生成原理[14]中的偏序結(jié)構(gòu)圖生成過程可知，對象集多的集合可以推導(dǎo)出其真子集的對象集，反之則不成立。因此，由屬性jm可以推出屬性im，屬性im不可以推出屬性jm，所以屬性jm是屬性im的必要條件。

證明：設(shè)屬性mi所屬對象集為屬性mm所屬對象集為{1,2}，屬性mn所屬對象集為屬性mp所屬對象集為屬性mq所屬對象集為{1,2,4}，此時如果將上面的屬性mn所屬的對象集變?yōu)閧3,4,5}，則上式就變?yōu)榱丝占?。證畢。

性質(zhì)4隨著形式背景的更新，各屬性間的因果關(guān)系可能會由無轉(zhuǎn)化為有。

性質(zhì)5屬性間的純相容關(guān)系包含相容關(guān)系和互斥關(guān)系。

純相容關(guān)系包含相容關(guān)系是指屬性間的相容關(guān)系不會隨著形式背景的更新而變?yōu)橐蚬P(guān)系。在初始形式背景中，如果某個屬性與其它屬性之間的關(guān)系為互斥關(guān)系，那么很顯然這種互斥關(guān)系不會隨著形式背景的更新而改變，所以互斥關(guān)系也屬于純相容關(guān)系。

1.4屬性拓?fù)涓屡c整體因果推斷

屬性拓?fù)涞奶幚韺ο鬄樾问奖尘?，所以屬性拓?fù)鋾S著形式背景的更新而不斷更新。以下分析屬性拓?fù)涞母轮惺∪チ诵问奖尘昂托问奖尘暗母隆?/p>

推斷各屬性間是否存在因果關(guān)系可通過屬性所屬對象集之間的包含關(guān)系進(jìn)行判斷。為了簡便，下面描述的屬性拓?fù)鋱D省去了屬性之間的權(quán)重，同時在各屬性后面添加其所屬的對象集。設(shè)有原始屬性拓?fù)鋱D如圖2所示。

圖2　原始屬性拓?fù)銯ig.2　primitive attribute topology

對屬性間進(jìn)行因果推斷時，可任意選擇其中的一個屬性作為初始屬性，然后推斷其他屬性與該初始屬性間的因果關(guān)系。比如初始屬性選擇圖2中的屬性E,由定義2可知，DE→，EC→。屬性E與屬性A、B為純相容關(guān)系，不存在因果關(guān)系。由EC→可知，屬性C為屬性E的果，所以在屬性拓?fù)鋱D中去除屬性E之前，要首先分析屬性C，否則去除屬性E的同時也去除了屬性C，這就可能導(dǎo)致屬性間的因果推斷不準(zhǔn)確、不完全。為了減少遍歷次數(shù)和避免遺漏屬性間的因果關(guān)系，本文選擇各屬性所屬對象集中對象個數(shù)最少的屬性作為初始屬性。

圖3　更新1次屬性拓?fù)銯ig.3　update 1 times

圖4　更新2次屬性拓?fù)洹ig.4 update 2 times

圖5　更新3次屬性拓?fù)銯ig.5　update 3 times

2　算法實現(xiàn)

本算法可歸結(jié)為以下五步：

步驟1對于任意給定的實際系統(tǒng)的數(shù)學(xué)模型，通過上述方法，將其轉(zhuǎn)化成對應(yīng)的形式背景凈化后，繪制簡化的屬性拓?fù)鋱D，用Sign記錄M。

步驟2對屬性集M中的屬性mi按由小到大排序，由最小的0()Nm得到屬性km。求出km所屬對象集W。對于任意mj屬于求出mj所屬對象集V。如果W包含于V，即可推斷出一個因果關(guān)系為：同時將屬性加入屬性集B中。

步驟3刪去屬性km和km所屬對象集中的對象，并對形式背景進(jìn)行更新。

步驟4重復(fù)步驟2和步驟3，直到形式背景中G與M不存在二元關(guān)系I為止。

步驟5將屬性集Sign賦值為屬性集Sign與屬性集B的差集，如果Sign中存在屬性，則輸出Sign中的所有屬性，此處的屬性與其他屬性為純相容關(guān)系，不存在因果關(guān)系。

Pseudocode表示為：

Input: 形式背景

Output: 各屬性間因果關(guān)系

算法如下：

3　實驗

下面我們以描述行人信號延誤系統(tǒng)為例，該系統(tǒng)可以描述成如下數(shù)學(xué)模型：

式中，pd：行人信號延誤s（）；NUk：非均勻到達(dá)調(diào)整系數(shù)；ER：有效紅燈時間長度s（）；k：紅燈相位到達(dá)的行人平均延誤隨時間的變化率；RN：紅燈期間到達(dá)行人數(shù)（人）；CN：周期到達(dá)行人數(shù)（人）；C：信號周期；G：有效綠燈時間長度s（）；A：凈空時間s（）；wP：違章人數(shù)占總?cè)藬?shù)的比例；q：行人流率。

系統(tǒng)轉(zhuǎn)化后對應(yīng)的形式背景如表5所示，簡化屬性拓?fù)鋱D如圖6所示。

表5　系統(tǒng)對應(yīng)的形式背景Table 5　system form background

圖6　形式背景對應(yīng)的簡化屬性拓?fù)鋱DFig.6　simplified attribute topology for formal context

形式背景帶入算法后便推斷出各系統(tǒng)變量之間的如下因果關(guān)系：

分析結(jié)果可知，系統(tǒng)變量因果關(guān)系中的因即為行人信號延誤的基礎(chǔ)參數(shù)，包括：周期時長（C），有效綠燈時間（G），周期到達(dá)行人數(shù)（NC），紅燈期間到達(dá)行人數(shù)（NR），行人流量（q）和違章比例（PW）。因此，研究行人信號延誤系統(tǒng)時，可將以上基礎(chǔ)參數(shù)作為系統(tǒng)的主要影響因素，以便使數(shù)據(jù)分析過程高效、有序。

4　結(jié)　論

針對目前因果關(guān)系推理方法中存在的趨于定量化，不精確和可視化效果差等問題，本文提出利用屬性拓?fù)溥M(jìn)行因果關(guān)系的推斷方法。該算法結(jié)合了集合和圖的相關(guān)理論，將屬性間的因果關(guān)系直觀的表現(xiàn)在屬性拓?fù)鋱D上。構(gòu)造過程相對直觀，且構(gòu)造步驟簡單，可視化的生成了屬性間的因果關(guān)系。屬性拓?fù)錇橐蚬P(guān)系推理提供了一種新的表示方法，下一步的工作將對本算法進(jìn)行完善和優(yōu)化及對屬性間多對多的因果關(guān)系進(jìn)行證明。

[1] Shi C Y. Qualitative reasoning method [M]. Tsinghua University press, 2002. (石純一. 定性推理方法[M]. 清華大學(xué)出版社, 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. (張濤, 洪文學(xué), 路靜. 形式背景的屬性樹表示[J]. 系統(tǒng)工程理論與實踐, 2011, 系統(tǒng)工程理論與實踐, 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. (洪文學(xué), 李少雄, 張濤,等. 大數(shù)據(jù)偏序結(jié)構(gòu)生成原理[J].燕山大學(xué)學(xué)報, 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