基于屬性拓撲的屬性間因果關系可視化推斷

劉文遠，馮春輝，張　濤，洪文學

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

基于屬性拓撲的屬性間因果關系可視化推斷

劉文遠1，馮春輝1，張濤1，洪文學2

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

因果關系推斷是因果順序理論分析的重要研究內(nèi)容之一。本文利用屬性拓撲理論，提出基于屬性拓撲的因果關系可視化推斷方法。該方法利用屬性拓撲的可視化特點，以屬性拓撲中的伴生關系為基礎，對屬性對所屬對象集之間的依賴關系進行分析和推理。通過屬性拓撲中屬性去除不斷地更新形式背景，從而推斷出各屬性間的因果關系。該算法使因果關系計算精準、可視化且易于實現(xiàn)。

屬性拓撲；形式概念；屬性關系；因果順序理論；可視化

本文著錄格式：劉文遠，馮春輝，張濤，等. 基于屬性拓撲的屬性間因果關系可視化推斷[J]. 軟件，2016，37（9）：62-67

0　引言

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

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

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

1　屬性拓撲中屬性間因果關系的推斷

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

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

屬性拓撲處理的對象為形式背景，所以在推斷實際系統(tǒng)變量之間的因果關系時，首先需要把描述實際系統(tǒng)的數(shù)學模型轉化成對應的形式背景。轉化過程如下：

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

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

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

1.2形式背景的屬性拓撲表示

形式背景是形式概念分析[10]的研究對象，也是本算法的數(shù)據(jù)表示方式。在形式概念分析[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伴生關系與因果推斷

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

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

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

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

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

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

1.4屬性拓撲更新與整體因果推斷

屬性拓撲的處理對象為形式背景，所以屬性拓撲會隨著形式背景的更新而不斷更新。以下分析屬性拓撲的更新中省去了形式背景和形式背景的更新。

推斷各屬性間是否存在因果關系可通過屬性所屬對象集之間的包含關系進行判斷。為了簡便，下面描述的屬性拓撲圖省去了屬性之間的權重，同時在各屬性后面添加其所屬的對象集。設有原始屬性拓撲圖如圖2所示。

圖2　原始屬性拓撲Fig.2　primitive attribute topology

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

圖3　更新1次屬性拓撲Fig.3　update 1 times

圖4　更新2次屬性拓撲　Fig.4 update 2 times

圖5　更新3次屬性拓撲Fig.5　update 3 times

2　算法實現(xiàn)

本算法可歸結為以下五步：

步驟1對于任意給定的實際系統(tǒng)的數(shù)學模型，通過上述方法，將其轉化成對應的形式背景凈化后，繪制簡化的屬性拓撲圖，用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　實驗

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

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

系統(tǒng)轉化后對應的形式背景如表5所示，簡化屬性拓撲圖如圖6所示。

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

圖6　形式背景對應的簡化屬性拓撲圖Fig.6　simplified attribute topology for formal context

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

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

4　結　論

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

[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]. 系統(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. (洪文學, 李少雄, 張濤,等. 大數(shù)據(jù)偏序結構生成原理[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