因素空間理論下多目標因果分析的降維算法

孫 慧，曾繁慧，蒲凌杰

（1.遼寧工程技術大學 理學院，遼寧 阜新 123000；2.遼寧工程技術大學 智能工程與數學研究院，遼寧 阜新 123000）

0 引言

1982年汪培莊提出因素空間理論，為概念、判斷、推理等的數學描述提供了理論框架，并于1994年與李洪興合寫著作《知識表示的數學理論》[1].因素空間是以因素為軸的坐標架，主要有兩大分支，其一是背景基理論.背景基可以生成背景關系，它是背景關系的無信息損失的壓縮，對因素庫[2]的實際應用具有重要的意義，背景關系是因素空間的形骸，塑造這個形骸的工具就是背景基，文獻[3]提出了背景基的概念；文獻[4]針對隨機性和模糊性的特點，提出了因素空間的背景分布和模糊背景關系；文獻[5]把由汪培莊提出的鈍角刪除法上升為精確算法.

因素空間另一個主要分支是因果分析法，因果分析法能在一張因素分析表中自動找出表中所含的因果關系，并畫出因果圖.文獻[6]按照因素空間的理論框架，在離散情形下定義了條件因素對結果的決定度及決定域，依次從決定域上提取出相應的推理知識，得到一種新算法為因果分析法.文獻[7]為進一步提高因素空間中因果分析法的運行速度和對樣本信息的利用，對文獻[6]給出的因素分析算法進行了改進.文獻[8]為進一步擴大因素空間中的因果分析法的應用領域，提出了多標準因果分析算法.因果分析法可以廣泛地應用到各種領域[9-11]，特別是數據挖掘，與數據挖掘決策樹方法相比，因果分析法使用起來更簡潔、貼切.然而當目標因素數量較大，利用多目標因果分析法計算的過程會十分繁雜，因此，本文提出一種降低目標維度的算法.

首先給出多目標因素條件下降維映射和鉆入決定度降維的定義，然后將未被選定的目標因素進行合取，分析合取因素對選定目標因素的鉆入決定度是否為1，進行目標因素的約簡，得到了目標因素的降維算法，接著在目標因素的降維算法的基礎上，研究了目標因素之間的關聯(lián)性，給出了關聯(lián)指標定義，又結合多目標因果分析法，得到了多目標因果分析降維算法，并作出實例分析.

1 預備知識

首先介紹因素空間的相關基本理論[3].

定義1因素是映射，把對象映射到其屬性上.映射是分析，因素是分析的維度.因素是映射，其中D為論域，即討論對象.I（f）為因素的相域.a1，…，ak是其中的相.

定義2論域D上的一個集合族 為D上的一個因素空間.

通常，只要兩個事物不同，就至少存在一個因素，使它們的因素狀態(tài)完全不同.

定義3給定D上的定性因素空間，對任意a=（a1，a，…，an）∈I，記其在D上的原相為[a]=F-1（a）={d∈D|F（d）=a}，[a]可能是空集?，若[a]=?，則稱a是一個虛組態(tài)，否則a是一個實性狀顆粒.全體實性狀的集合記為

式中，R為因素f1，…，fn之間的背景關系.

定義4如果背景關系

則稱因素f與g獨立.

定理1背景關系決定一切恒真推理句：若，則E（x） →E′（y）必是恒真句.恒真句也叫因果規(guī)則律，從因素表提取，因果律也叫規(guī)則提取.

定義5給定因素空間

定義6設記

如果[s]?，[t] 則稱[s]是因素f的一個決定類.因素f的所有決定類的并集稱為對結果的決定域.因素f的決定域所占行數h與表的行數（即全體對象個數）m之比稱為其對結果的鉆入決定度，記作

因果分析法是因素空間理論下的一種提取規(guī)則的算法，是一種能體現人腦認知中歸納和推理的基本方法，因果分析法可以應用于離散型數據的分類和歸納.

因果分析法的整個流程可以概括成3步：①選取決定度最高的因素進行劃分；②將所有決定類選取出來，并轉化為推理句；③將選取的決定類所對應的地址從因素表中刪除，重復上述步驟，直到表被刪空.

2 多目標因果分析降維算法

2.1 多目標因果分析法

因果分析法是基于樹結構來進行規(guī)則提取的，也可以稱為因果樹算法，這也是人類在分析問題時的一種很自然的處理機制.例如，某超市要對“個人的購買力”進行分析時，通常會進行一系列的判斷或“子分析”：首先看“這個人的還貸能力”，如果是“可”，則再看看“他的職業(yè)”，如果是“商”，再判斷“他的年齡是多少”，得出結果：這個人會“購買”.分析過程見圖1.

圖1 購買問題的一棵因果樹 Fig.1 a causal tree of purchase problem

因果樹是一種有效的分類和歸納方法，它具有很強的概括性，并能將形似信息與效用信息關聯(lián)起來，提升為全面的語義信息.

因果樹算法是多個條件因素對應一個目標因素，在條件因素互相關聯(lián)的條件下，得到條件因素對目標因素的樹狀結構，但是這種算法具有局限性，在實際應用中常常需要考慮的是多個條件因素對多個目標因素，所以就有了多目標因果分析方法，多目標因果分析方法是在因果樹算法的基礎上，利用鉆入決定度所得到的.多目標因果分析方法避免了因果樹只解決一個目標因素的局限性問題.

定義7如果因果規(guī)則后件中不完整，即因果規(guī)則只能得到條件因素對應不完整的結果，則稱此因果規(guī)則是殘缺的．

定義8因素fi對所有目標因素的總決定度ci，，其中，hir為第i個條件因素對第r個目標因素的決定域所占行數，um為當前劃分類所占的總行數.

多目標因果分析法步驟如下.

步驟1先將所有連續(xù)型的條件因素和目標因素通過等步長進行離散化處理.

步驟2計算每個條件因素對所有的目標因素的總決定度ci，找出總決定度最大的條件因素，用此條件因素的相域將論域D進行劃分；若出現決定類，就寫出相應的因果規(guī)則，若是因果規(guī)則是不完整的，則繼續(xù)上述步驟，直到因果規(guī)則是完整的或者因素不能再分為止.

步驟3將所有因果規(guī)則進行歸納，得到一棵因果樹.

2.2 目標因素的降維算法

因果分析是多個條件因素對單一目標所進行的規(guī)則提取，多目標因果分析是多條件因素對多個目標所進行的規(guī)則提取.目前算法是：對每個條件因素求出它對各個目標因素的鉆入決定度而得到一個決定度向量.對這個向量定義某種范數（如本文前面所定義的總決定度），根據這個范數來選取因素對D中對象分類，將決定類轉化為推理句，如此巡回，直到全部論域都轉化為推理句.

目標因素之間往往不是獨立的.如果它們不獨立，則可先在目標因素之間進行因果分析，如果目標甲和乙決定目標丙，則目標丙就可以先拿開，僅對甲乙這兩個目標來進行因果分析，得到一組推理規(guī)則以后，再把目標丙的相值按照目標因素之間的關系填補回去.本文定義了降維映射和鉆入決定度降維，將未被選定的目標因素進行合取，分析合取因素對選定的目標因素的鉆入決定度是否為1，進行目標因素的約簡，此算法稱為目標因素的降維算法.

（1）算法原理

定義9（降維映射） 論域D中有m個對象，r個目標因素，目標因素指標集J：={1，…，r}，目標函數集H0：={g1∧…∧gr}，目標函數相I（H0），當選出第j個目標因素gj，j∈J，其余目標因素的合取因素Hj：= ∧{gi|i∈J，i≠j}，如果函數f（I（Hj））能夠映射到函數f（I（gj）），即I（Hj）對I（gj）只有一對一和多對一關系，不存在一對多關系，則可以將gj進行降維約簡.

其中，

定義10（鉆入決定度降維） 當I（Hj）對I（gj）只有一對一和多對一關系，不存在一對多關系時，那么鉆入決定度Zj=1，此時可以將gj進行目標降維.

算法核心思想為鉆入決定度為1的時候，條件因素的取相完全決定了目標因素的取相，是目標降維的依據.

算法降維原理如下.

① 給定多目標因果分析的數據表，只看目標因素列，記H0：={g1∧…∧gr}，將H0中任何一個拿出來當做目標因素，考察其余因素的合取因素對其的決定度是否為1.

求因素Hj對因素gj的決定度Zj.如果所有Zj＜1，則放棄目標降維，用常規(guī)的多后件因果分析處理，否則，任意取定一個具有決定度Zj=1的因素Hj，記下相應的函數關系式，去掉目標因素gj；

③ 對剩下的因素再重復這一過程，把Hj中任何一個因素拿出來當做目標因素，考察其余因素的合取因素對它的決定度是否等于1，若有，則繼續(xù)刪除目標，直到不可再刪為止.

這樣就實現了目標降維的目的.按降維以后的目標常用算法求多目標因果分析，再按函數關系把被刪的目標值一一補齊，就得到原多目標因果分析算法所要得到的結果，但計算量卻減少很多.

（2）算法步驟

多目標因果分析降維算法的步驟如下.

將所有連續(xù)型的條件因素和目標因素通過等步長進行離散化處理.

設置目標因素指標集J:={1，…，r}.

步驟1對j∈J，記，計算合取因素Hj對gj決定度Zj（合因素的決定度怎樣計算，見下例）；若Zj，則在J中更換下一個指標，若J中別無其它指標，則轉向步驟2；若Zj=1，則寫出函數句（函數句的寫法，見下例）；將足碼j從J中刪掉；若|J|=1，則轉向步驟2；否則重新執(zhí)行步驟1.

步驟2將J中所剩下指標所對應的因素作后件，整理并歸納得到的目標取值的函數關系句.

2.3 多目標因果分析降維算法

根據上文提出的目標因素的降維算法，結合多目標因果分析法，研究了目標因素之間的關聯(lián)性，提出了多目標因果分析降維算法.目標因素之間的關聯(lián)性越強，算法的效果就越好，多目標因果分析降維算法可以反映目標因素之間的內在聯(lián)系.

定義11（目標因素之間的關聯(lián)性）目標因素g1，g2，…，gr的背景關系R與目標因素相域I（g）:=I（g1） ×I（g2） × … ×I（gr）（去掉虛組態(tài)）是否相等，如果R=I（g），則稱g1，g2，…，gr是相對獨立的.如果R≠I（g），則稱目標因素g1，g2，…，gr之間有關聯(lián)，關聯(lián)指標σ：= |R|-|I（g）|，σ越大，目標因素之間的關聯(lián)性越強，其中|R|，|I（g）|分別為R和 （）Ig的種類個數.

多目標因果分析降維算法步驟如下.

步驟1先將所有連續(xù)型的條件因素和目標因素進行離散化處理，例如通過等步長作離散化.

步驟2對目標因素進行關聯(lián)性計算.

步驟3對j∈J，記，計算合取因素Hj對jg的決定度Zj；若Zj＜1，則在J中更換下一個指標，若J中別無其它指標，則轉向步驟4；若Zj=1，則寫出目標取值的函數關系句；將足碼j從J中刪掉；若，則轉向步驟4；否則重新執(zhí)行步驟3.

步驟4將J中所剩下指標所對應的因素作后件，整理并歸納得到的目標取值的函數關系句.

步驟5計算每個條件因素對所有的目標因素（目標因素是步驟4中的降維后的后件）的總決定度ci，找出總決定度最大的條件因素，用此條件因素的相域將論域D進行劃分；若出現決定類，則寫出相應的因果規(guī)則，若是因果規(guī)則是不完整的，則繼續(xù)上述步驟，直到因果規(guī)則是完整的或者因素不能再分為止.

步驟6將所有因果規(guī)則進行歸納，按照步驟4中的函數關系句補齊因果規(guī)則，得到一棵因果樹.

3 實例驗證

用一個實例驗證本文給出的多目標因果分析降維算法.對于超市用戶的消費情況進行因果規(guī)則提取，條件因素有年齡、收入、職業(yè)、還貸能力4個，目標因素有消費金額、消費狀況、消費間隔3個.超市用戶的因素分析數據見表1.

表1 超市用戶的因素分析 Tab.1 factor analysis of supermarket users

表1有4個條件因素.

表1有3個目標因素分別具有相域.

（1）多目標因果分析降維算法

步驟1首先確定目標因素之間的關聯(lián)性，目標因素相域I（g）={（111），（112），（212），（221），（311），（322）}（去掉虛擬態(tài)）共有6個組態(tài)，目標因素背景關系

共有12個相組合，所以|R|，|I（g）|分別為12和6，σ=|R|- |I（g）|= 6，表明這3個目標因素之間有強關聯(lián)性.

多目標因果分析降維算法：設置目標因素指標集J：= {1，2，3}.

步驟2取j= 1，記H1=g2∧g3，計算合取因素H1對g1的決定度Z1，合取因素g2∧g3的相值是表中右2與右1兩列相值的組合.例如用戶1的合取相值是向量（2，2），用戶2的合取相值是向量（1，2）.全體用戶的相應相值共有（2，2），（1，2），（2，1）和（1，1）4類.要使11Z=，當且僅當這4類都能鉆入由1g所分出的類，現在（2，2）類所對應的1g值都是3，（1，2）類所對應的1g值是2，（2，1）類所對應的1g值是2，都鉆入了1g的類，但是，（1，1）類的1g值為1或者3，不能鉆入1g的類，因而11Z＜.程序要求在J中更換下一個指標2，重新執(zhí)行步驟1.

取j=2，記H2=g1∧g3，計算合取因素H2對g2的決定度Z2，這里合取因素g2∧g3的相值是表中右3與右1兩列相值的組合.全體用戶的相值共有（3，2），（3，1），（2，2），（2，1），（1，1）和（1，2）共6類.（2，2）類、（1，1）類，（3，1）類和（1，2）類所對應的g2值都是1，（2，1）類和（3，2）類所對應的g2值都是2，都鉆入了g2的類，因而Z2= 1.于是，目標g2可以被視為g2的函數，寫成目標取值的函數關系句如下.

記下這組推理句以后，把2從J中刪除，變?yōu)镴= {1 ,3}；重新執(zhí)行步驟1.

取j=1，有H1=g3，此時，需要判斷H1=g3對g1的決定度是否為1，因g3= 2時g1可以取值為1，也可以取值為2或3，故知決定度不可能等于1；按照程序，從中取出另一個指標，取j= 3，有H3=g1，需要判斷H3=g1對g3的決定度是否為1，因g1=3時g3有時取2有時取1，故知決定度不可能等于1；按照程序，轉向步驟3.

步驟3降維后的后件是J中現有的指標所對應的目標因素g1和g3，前件是f1，f2，f3，f4，目標取值的函數關系句是（I）～（VI）.

步驟4（1）先判斷f1對g1是否存在決定類.當f1以“老”為相，看g1的相是否相同，表1中，用戶1和用戶5的I（f1）為“老”，他們的I（g1）分別為3和2，因為不同，所以“老”不是f1的一個決定類；用戶2和用戶4的I（f1）為“中”，他們的I（g1）分別為2和1，所以“中”也不是f1的一個決定類；用戶3、用戶7、用戶8、用戶10和用戶13的I（f1）為“青”，且I（g1）均為3，所以f1對g1存在決定類，決定類中的對象個數為5.同理可知，f1對g3不存在決定類，所以f1一列記為（5，0）=5.類似地，可以判斷f2，f3，f4對g1和g3是否存在決定類，在此不再細算，直接給出結果，f2一列記為（4，0）=4；f3一列記為（4，0）=4；f4一列記為（6，9）=15，由于f4取值最大，所以選擇f4作為下一步劃分.

（2）對f4進行劃分，劃分結果如下.

（3）重復第一步，分別計算I（f4）為“可”和I（f4）為“好”的用戶.

先計算I（f4）為“可”的那三行的總決定度，直接給出結果，f1一列記為（3，3）=6，總決定度為2；f2一列記為（1，3）=4，總決定度為4/3；f3一列記為（1，3）=4，總決定度為4/3；f4一列記為（0，3）=3，總決定度為1.

f1的總決定度最大，在I（f4）為“可”的前提下，繼續(xù)按f1進行劃分，劃分結果如下.

繼續(xù)計算I（f4）為“好”的那六行的總決定度，直接給出結果，在I（f4）為“好”的前提下，劃分結果如下.

步驟5將所有因果規(guī)則進行歸納，并畫出最后的因果樹.

10條因果規(guī)則：差→32；可青→31；可中→11；可老→21；好青→31；好中高→11；好中平師→22；好中平商→12；好老師→12；好老商→11.

上述得到的因果規(guī)則只包含兩個目標因素，要想得到被約簡的目標的取值情況，參照目標取值的函數關系句（I-VI）來補齊.例如，把關系（I）（g1=3且g3=2）→g2=2；連接在因果規(guī)則（1）之后，便有：f4差→g1為3，g3為2→g2=2，寫成補齊式.

（1） I（f4） =差→ I（g1） =3，I（g2） =2，I（g3） =2.（根據（I））

類似地有

（2） I（f4）=可，I（f1）=青→I（g1）=3，I（g2）=1，I（g3）=1.（根據（II））

（3） I（f4）=可，I（f1）=中→ I（g1）=1，I（g2）=1，I（g3）=1.（根據（V））

（4）I（f4）=可，I（f1）=老→I（g1）=2，I（g2）=2，I（g3）=1.（根據（IV））

（5）I（f4）=好，I（f1）=高→I（g1）=1，I（g2）=1，I（g3）=1.（根據（V））

多目標因果樹，見圖2.

圖2 多目標因果樹 Fig.2 multiple target causality tree

（2）算法對比

利用常規(guī)的多目標因果分析法，進行超市用戶消費情況的因果規(guī)則提取，具體步驟不再描述，得到的結果與多目標因果分析法相同，接下來對比常規(guī)多目標因果分析法和帶有目標降維的多目標因果分析法的計算時間和計算次數，見表2.

表2 兩種算法的計算對比 Tab.2 calculation comparison of two algorithms

從表2中可以看出，多目標因果分析降維算法的計算時間和計算次數均小于多目標因果分析，且兩種算法的計算結果也相同，表明多目標因果分析降維算法的計算效率更好，有效地降低了計算的繁雜性.

4 結論

（1）定義了降維映射和鉆入決定度降維，將未被選定的目標因素進行合取，做到了目標降維，得到了目標因素的降維算法.

（2）在目標因素降維算法的基礎上，定義總決定度，研究目標因素之間的關聯(lián)性，并給出了關聯(lián)指標的定義，結合多目標因果分析法，提出多目標因果分析降維算法.

（3）利用某超市數據，進行實例分析，證明多目標因果分析降維算法具有實用性和有效性，并為多目標優(yōu)化帶來新方法.