孫 慧,曾繁慧,蒲凌杰
(1.遼寧工程技術(shù)大學(xué) 理學(xué)院,遼寧 阜新 123000;2.遼寧工程技術(shù)大學(xué) 智能工程與數(shù)學(xué)研究院,遼寧 阜新 123000)
1982年汪培莊提出因素空間理論,為概念、判斷、推理等的數(shù)學(xué)描述提供了理論框架,并于1994年與李洪興合寫著作《知識(shí)表示的數(shù)學(xué)理論》[1].因素空間是以因素為軸的坐標(biāo)架,主要有兩大分支,其一是背景基理論.背景基可以生成背景關(guān)系,它是背景關(guān)系的無信息損失的壓縮,對(duì)因素庫(kù)[2]的實(shí)際應(yīng)用具有重要的意義,背景關(guān)系是因素空間的形骸,塑造這個(gè)形骸的工具就是背景基,文獻(xiàn)[3]提出了背景基的概念;文獻(xiàn)[4]針對(duì)隨機(jī)性和模糊性的特點(diǎn),提出了因素空間的背景分布和模糊背景關(guān)系;文獻(xiàn)[5]把由汪培莊提出的鈍角刪除法上升為精確算法.
因素空間另一個(gè)主要分支是因果分析法,因果分析法能在一張因素分析表中自動(dòng)找出表中所含的因果關(guān)系,并畫出因果圖.文獻(xiàn)[6]按照因素空間的理論框架,在離散情形下定義了條件因素對(duì)結(jié)果的決定度及決定域,依次從決定域上提取出相應(yīng)的推理知識(shí),得到一種新算法為因果分析法.文獻(xiàn)[7]為進(jìn)一步提高因素空間中因果分析法的運(yùn)行速度和對(duì)樣本信息的利用,對(duì)文獻(xiàn)[6]給出的因素分析算法進(jìn)行了改進(jìn).文獻(xiàn)[8]為進(jìn)一步擴(kuò)大因素空間中的因果分析法的應(yīng)用領(lǐng)域,提出了多標(biāo)準(zhǔn)因果分析算法.因果分析法可以廣泛地應(yīng)用到各種領(lǐng)域[9-11],特別是數(shù)據(jù)挖掘,與數(shù)據(jù)挖掘決策樹方法相比,因果分析法使用起來更簡(jiǎn)潔、貼切.然而當(dāng)目標(biāo)因素?cái)?shù)量較大,利用多目標(biāo)因果分析法計(jì)算的過程會(huì)十分繁雜,因此,本文提出一種降低目標(biāo)維度的算法.
首先給出多目標(biāo)因素條件下降維映射和鉆入決定度降維的定義,然后將未被選定的目標(biāo)因素進(jìn)行合取,分析合取因素對(duì)選定目標(biāo)因素的鉆入決定度是否為1,進(jìn)行目標(biāo)因素的約簡(jiǎn),得到了目標(biāo)因素的降維算法,接著在目標(biāo)因素的降維算法的基礎(chǔ)上,研究了目標(biāo)因素之間的關(guān)聯(lián)性,給出了關(guān)聯(lián)指標(biāo)定義,又結(jié)合多目標(biāo)因果分析法,得到了多目標(biāo)因果分析降維算法,并作出實(shí)例分析.
首先介紹因素空間的相關(guān)基本理論[3].
定義1因素是映射,把對(duì)象映射到其屬性上.映射是分析,因素是分析的維度.因素是映射,其中D為論域,即討論對(duì)象.I(f)為因素的相域.a1,…,ak是其中的相.
定義2論域D上的一個(gè)集合族 為D上的一個(gè)因素空間.
通常,只要兩個(gè)事物不同,就至少存在一個(gè)因素,使它們的因素狀態(tài)完全不同.
定義3給定D上的定性因素空間,對(duì)任意a=(a1,a,…,an)∈I,記其在D上的原相為[a]=F-1(a)={d∈D|F(d)=a},[a]可能是空集?,若[a]=?,則稱a是一個(gè)虛組態(tài),否則a是一個(gè)實(shí)性狀顆粒.全體實(shí)性狀的集合記為
式中,R為因素f1,…,fn之間的背景關(guān)系.
定義4如果背景關(guān)系
則稱因素f與g獨(dú)立.
定理1背景關(guān)系決定一切恒真推理句:若,則E(x) →E′(y)必是恒真句.恒真句也叫因果規(guī)則律,從因素表提取,因果律也叫規(guī)則提取.
定義5給定因素空間
定義6設(shè)記
如果[s]?,[t] 則稱[s]是因素f的一個(gè)決定類.因素f的所有決定類的并集稱為對(duì)結(jié)果的決定域.因素f的決定域所占行數(shù)h與表的行數(shù)(即全體對(duì)象個(gè)數(shù))m之比稱為其對(duì)結(jié)果的鉆入決定度,記作
因果分析法是因素空間理論下的一種提取規(guī)則的算法,是一種能體現(xiàn)人腦認(rèn)知中歸納和推理的基本方法,因果分析法可以應(yīng)用于離散型數(shù)據(jù)的分類和歸納.
因果分析法的整個(gè)流程可以概括成3步:①選取決定度最高的因素進(jìn)行劃分;②將所有決定類選取出來,并轉(zhuǎn)化為推理句;③將選取的決定類所對(duì)應(yīng)的地址從因素表中刪除,重復(fù)上述步驟,直到表被刪空.
因果分析法是基于樹結(jié)構(gòu)來進(jìn)行規(guī)則提取的,也可以稱為因果樹算法,這也是人類在分析問題時(shí)的一種很自然的處理機(jī)制.例如,某超市要對(duì)“個(gè)人的購(gòu)買力”進(jìn)行分析時(shí),通常會(huì)進(jìn)行一系列的判斷或“子分析”:首先看“這個(gè)人的還貸能力”,如果是“可”,則再看看“他的職業(yè)”,如果是“商”,再判斷“他的年齡是多少”,得出結(jié)果:這個(gè)人會(huì)“購(gòu)買”.分析過程見圖1.
圖1 購(gòu)買問題的一棵因果樹 Fig.1 a causal tree of purchase problem
因果樹是一種有效的分類和歸納方法,它具有很強(qiáng)的概括性,并能將形似信息與效用信息關(guān)聯(lián)起來,提升為全面的語義信息.
因果樹算法是多個(gè)條件因素對(duì)應(yīng)一個(gè)目標(biāo)因素,在條件因素互相關(guān)聯(lián)的條件下,得到條件因素對(duì)目標(biāo)因素的樹狀結(jié)構(gòu),但是這種算法具有局限性,在實(shí)際應(yīng)用中常常需要考慮的是多個(gè)條件因素對(duì)多個(gè)目標(biāo)因素,所以就有了多目標(biāo)因果分析方法,多目標(biāo)因果分析方法是在因果樹算法的基礎(chǔ)上,利用鉆入決定度所得到的.多目標(biāo)因果分析方法避免了因果樹只解決一個(gè)目標(biāo)因素的局限性問題.
定義7如果因果規(guī)則后件中不完整,即因果規(guī)則只能得到條件因素對(duì)應(yīng)不完整的結(jié)果,則稱此因果規(guī)則是殘缺的.
定義8因素fi對(duì)所有目標(biāo)因素的總決定度ci,,其中,hir為第i個(gè)條件因素對(duì)第r個(gè)目標(biāo)因素的決定域所占行數(shù),um為當(dāng)前劃分類所占的總行數(shù).
多目標(biāo)因果分析法步驟如下.
步驟1先將所有連續(xù)型的條件因素和目標(biāo)因素通過等步長(zhǎng)進(jìn)行離散化處理.
步驟2計(jì)算每個(gè)條件因素對(duì)所有的目標(biāo)因素的總決定度ci,找出總決定度最大的條件因素,用此條件因素的相域?qū)⒄撚駾進(jìn)行劃分;若出現(xiàn)決定類,就寫出相應(yīng)的因果規(guī)則,若是因果規(guī)則是不完整的,則繼續(xù)上述步驟,直到因果規(guī)則是完整的或者因素不能再分為止.
步驟3將所有因果規(guī)則進(jìn)行歸納,得到一棵因果樹.
因果分析是多個(gè)條件因素對(duì)單一目標(biāo)所進(jìn)行的規(guī)則提取,多目標(biāo)因果分析是多條件因素對(duì)多個(gè)目標(biāo)所進(jìn)行的規(guī)則提取.目前算法是:對(duì)每個(gè)條件因素求出它對(duì)各個(gè)目標(biāo)因素的鉆入決定度而得到一個(gè)決定度向量.對(duì)這個(gè)向量定義某種范數(shù)(如本文前面所定義的總決定度),根據(jù)這個(gè)范數(shù)來選取因素對(duì)D中對(duì)象分類,將決定類轉(zhuǎn)化為推理句,如此巡回,直到全部論域都轉(zhuǎn)化為推理句.
目標(biāo)因素之間往往不是獨(dú)立的.如果它們不獨(dú)立,則可先在目標(biāo)因素之間進(jìn)行因果分析,如果目標(biāo)甲和乙決定目標(biāo)丙,則目標(biāo)丙就可以先拿開,僅對(duì)甲乙這兩個(gè)目標(biāo)來進(jìn)行因果分析,得到一組推理規(guī)則以后,再把目標(biāo)丙的相值按照目標(biāo)因素之間的關(guān)系填補(bǔ)回去.本文定義了降維映射和鉆入決定度降維,將未被選定的目標(biāo)因素進(jìn)行合取,分析合取因素對(duì)選定的目標(biāo)因素的鉆入決定度是否為1,進(jìn)行目標(biāo)因素的約簡(jiǎn),此算法稱為目標(biāo)因素的降維算法.
(1)算法原理
定義9(降維映射) 論域D中有m個(gè)對(duì)象,r個(gè)目標(biāo)因素,目標(biāo)因素指標(biāo)集J:={1,…,r},目標(biāo)函數(shù)集H0:={g1∧…∧gr},目標(biāo)函數(shù)相I(H0),當(dāng)選出第j個(gè)目標(biāo)因素gj,j∈J,其余目標(biāo)因素的合取因素Hj:= ∧{gi|i∈J,i≠j},如果函數(shù)f(I(Hj))能夠映射到函數(shù)f(I(gj)),即I(Hj)對(duì)I(gj)只有一對(duì)一和多對(duì)一關(guān)系,不存在一對(duì)多關(guān)系,則可以將gj進(jìn)行降維約簡(jiǎn).
其中,
定義10(鉆入決定度降維) 當(dāng)I(Hj)對(duì)I(gj)只有一對(duì)一和多對(duì)一關(guān)系,不存在一對(duì)多關(guān)系時(shí),那么鉆入決定度Zj=1,此時(shí)可以將gj進(jìn)行目標(biāo)降維.
算法核心思想為鉆入決定度為1的時(shí)候,條件因素的取相完全決定了目標(biāo)因素的取相,是目標(biāo)降維的依據(jù).
算法降維原理如下.
① 給定多目標(biāo)因果分析的數(shù)據(jù)表,只看目標(biāo)因素列,記H0:={g1∧…∧gr},將H0中任何一個(gè)拿出來當(dāng)做目標(biāo)因素,考察其余因素的合取因素對(duì)其的決定度是否為1.
求因素Hj對(duì)因素gj的決定度Zj.如果所有Zj<1,則放棄目標(biāo)降維,用常規(guī)的多后件因果分析處理,否則,任意取定一個(gè)具有決定度Zj=1的因素Hj,記下相應(yīng)的函數(shù)關(guān)系式,去掉目標(biāo)因素gj;
③ 對(duì)剩下的因素再重復(fù)這一過程,把Hj中任何一個(gè)因素拿出來當(dāng)做目標(biāo)因素,考察其余因素的合取因素對(duì)它的決定度是否等于1,若有,則繼續(xù)刪除目標(biāo),直到不可再刪為止.
這樣就實(shí)現(xiàn)了目標(biāo)降維的目的.按降維以后的目標(biāo)常用算法求多目標(biāo)因果分析,再按函數(shù)關(guān)系把被刪的目標(biāo)值一一補(bǔ)齊,就得到原多目標(biāo)因果分析算法所要得到的結(jié)果,但計(jì)算量卻減少很多.
(2)算法步驟
多目標(biāo)因果分析降維算法的步驟如下.
將所有連續(xù)型的條件因素和目標(biāo)因素通過等步長(zhǎng)進(jìn)行離散化處理.
設(shè)置目標(biāo)因素指標(biāo)集J:={1,…,r}.
步驟1對(duì)j∈J,記,計(jì)算合取因素Hj對(duì)gj決定度Zj(合因素的決定度怎樣計(jì)算,見下例);若Zj,則在J中更換下一個(gè)指標(biāo),若J中別無其它指標(biāo),則轉(zhuǎn)向步驟2;若Zj=1,則寫出函數(shù)句(函數(shù)句的寫法,見下例);將足碼j從J中刪掉;若|J|=1,則轉(zhuǎn)向步驟2;否則重新執(zhí)行步驟1.
步驟2將J中所剩下指標(biāo)所對(duì)應(yīng)的因素作后件,整理并歸納得到的目標(biāo)取值的函數(shù)關(guān)系句.
根據(jù)上文提出的目標(biāo)因素的降維算法,結(jié)合多目標(biāo)因果分析法,研究了目標(biāo)因素之間的關(guān)聯(lián)性,提出了多目標(biāo)因果分析降維算法.目標(biāo)因素之間的關(guān)聯(lián)性越強(qiáng),算法的效果就越好,多目標(biāo)因果分析降維算法可以反映目標(biāo)因素之間的內(nèi)在聯(lián)系.
定義11(目標(biāo)因素之間的關(guān)聯(lián)性)目標(biāo)因素g1,g2,…,gr的背景關(guān)系R與目標(biāo)因素相域I(g):=I(g1) ×I(g2) × … ×I(gr)(去掉虛組態(tài))是否相等,如果R=I(g),則稱g1,g2,…,gr是相對(duì)獨(dú)立的.如果R≠I(g),則稱目標(biāo)因素g1,g2,…,gr之間有關(guān)聯(lián),關(guān)聯(lián)指標(biāo)σ:= |R|-|I(g)|,σ越大,目標(biāo)因素之間的關(guān)聯(lián)性越強(qiáng),其中|R|,|I(g)|分別為R和 ()Ig的種類個(gè)數(shù).
多目標(biāo)因果分析降維算法步驟如下.
步驟1先將所有連續(xù)型的條件因素和目標(biāo)因素進(jìn)行離散化處理,例如通過等步長(zhǎng)作離散化.
步驟2對(duì)目標(biāo)因素進(jìn)行關(guān)聯(lián)性計(jì)算.
步驟3對(duì)j∈J,記,計(jì)算合取因素Hj對(duì)jg的決定度Zj;若Zj<1,則在J中更換下一個(gè)指標(biāo),若J中別無其它指標(biāo),則轉(zhuǎn)向步驟4;若Zj=1,則寫出目標(biāo)取值的函數(shù)關(guān)系句;將足碼j從J中刪掉;若,則轉(zhuǎn)向步驟4;否則重新執(zhí)行步驟3.
步驟4將J中所剩下指標(biāo)所對(duì)應(yīng)的因素作后件,整理并歸納得到的目標(biāo)取值的函數(shù)關(guān)系句.
步驟5計(jì)算每個(gè)條件因素對(duì)所有的目標(biāo)因素(目標(biāo)因素是步驟4中的降維后的后件)的總決定度ci,找出總決定度最大的條件因素,用此條件因素的相域?qū)⒄撚駾進(jìn)行劃分;若出現(xiàn)決定類,則寫出相應(yīng)的因果規(guī)則,若是因果規(guī)則是不完整的,則繼續(xù)上述步驟,直到因果規(guī)則是完整的或者因素不能再分為止.
步驟6將所有因果規(guī)則進(jìn)行歸納,按照步驟4中的函數(shù)關(guān)系句補(bǔ)齊因果規(guī)則,得到一棵因果樹.
用一個(gè)實(shí)例驗(yàn)證本文給出的多目標(biāo)因果分析降維算法.對(duì)于超市用戶的消費(fèi)情況進(jìn)行因果規(guī)則提取,條件因素有年齡、收入、職業(yè)、還貸能力4個(gè),目標(biāo)因素有消費(fèi)金額、消費(fèi)狀況、消費(fèi)間隔3個(gè).超市用戶的因素分析數(shù)據(jù)見表1.
表1 超市用戶的因素分析 Tab.1 factor analysis of supermarket users
表1有4個(gè)條件因素.
表1有3個(gè)目標(biāo)因素分別具有相域.
(1)多目標(biāo)因果分析降維算法
步驟1首先確定目標(biāo)因素之間的關(guān)聯(lián)性,目標(biāo)因素相域I(g)={(111),(112),(212),(221),(311),(322)}(去掉虛擬態(tài))共有6個(gè)組態(tài),目標(biāo)因素背景關(guān)系
共有12個(gè)相組合,所以|R|,|I(g)|分別為12和6,σ=|R|- |I(g)|= 6,表明這3個(gè)目標(biāo)因素之間有強(qiáng)關(guān)聯(lián)性.
多目標(biāo)因果分析降維算法:設(shè)置目標(biāo)因素指標(biāo)集J:= {1,2,3}.
步驟2取j= 1,記H1=g2∧g3,計(jì)算合取因素H1對(duì)g1的決定度Z1,合取因素g2∧g3的相值是表中右2與右1兩列相值的組合.例如用戶1的合取相值是向量(2,2),用戶2的合取相值是向量(1,2).全體用戶的相應(yīng)相值共有(2,2),(1,2),(2,1)和(1,1)4類.要使11Z=,當(dāng)且僅當(dāng)這4類都能鉆入由1g所分出的類,現(xiàn)在(2,2)類所對(duì)應(yīng)的1g值都是3,(1,2)類所對(duì)應(yīng)的1g值是2,(2,1)類所對(duì)應(yīng)的1g值是2,都鉆入了1g的類,但是,(1,1)類的1g值為1或者3,不能鉆入1g的類,因而11Z<.程序要求在J中更換下一個(gè)指標(biāo)2,重新執(zhí)行步驟1.
取j=2,記H2=g1∧g3,計(jì)算合取因素H2對(duì)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)類所對(duì)應(yīng)的g2值都是1,(2,1)類和(3,2)類所對(duì)應(yīng)的g2值都是2,都鉆入了g2的類,因而Z2= 1.于是,目標(biāo)g2可以被視為g2的函數(shù),寫成目標(biāo)取值的函數(shù)關(guān)系句如下.
記下這組推理句以后,把2從J中刪除,變?yōu)镴= {1 ,3};重新執(zhí)行步驟1.
取j=1,有H1=g3,此時(shí),需要判斷H1=g3對(duì)g1的決定度是否為1,因g3= 2時(shí)g1可以取值為1,也可以取值為2或3,故知決定度不可能等于1;按照程序,從中取出另一個(gè)指標(biāo),取j= 3,有H3=g1,需要判斷H3=g1對(duì)g3的決定度是否為1,因g1=3時(shí)g3有時(shí)取2有時(shí)取1,故知決定度不可能等于1;按照程序,轉(zhuǎn)向步驟3.
步驟3降維后的后件是J中現(xiàn)有的指標(biāo)所對(duì)應(yīng)的目標(biāo)因素g1和g3,前件是f1,f2,f3,f4,目標(biāo)取值的函數(shù)關(guān)系句是(I)~(VI).
步驟4(1)先判斷f1對(duì)g1是否存在決定類.當(dāng)f1以“老”為相,看g1的相是否相同,表1中,用戶1和用戶5的I(f1)為“老”,他們的I(g1)分別為3和2,因?yàn)椴煌?,所以“老”不是f1的一個(gè)決定類;用戶2和用戶4的I(f1)為“中”,他們的I(g1)分別為2和1,所以“中”也不是f1的一個(gè)決定類;用戶3、用戶7、用戶8、用戶10和用戶13的I(f1)為“青”,且I(g1)均為3,所以f1對(duì)g1存在決定類,決定類中的對(duì)象個(gè)數(shù)為5.同理可知,f1對(duì)g3不存在決定類,所以f1一列記為(5,0)=5.類似地,可以判斷f2,f3,f4對(duì)g1和g3是否存在決定類,在此不再細(xì)算,直接給出結(jié)果,f2一列記為(4,0)=4;f3一列記為(4,0)=4;f4一列記為(6,9)=15,由于f4取值最大,所以選擇f4作為下一步劃分.
(2)對(duì)f4進(jìn)行劃分,劃分結(jié)果如下.
(3)重復(fù)第一步,分別計(jì)算I(f4)為“可”和I(f4)為“好”的用戶.
先計(jì)算I(f4)為“可”的那三行的總決定度,直接給出結(jié)果,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進(jìn)行劃分,劃分結(jié)果如下.
繼續(xù)計(jì)算I(f4)為“好”的那六行的總決定度,直接給出結(jié)果,在I(f4)為“好”的前提下,劃分結(jié)果如下.
步驟5將所有因果規(guī)則進(jìn)行歸納,并畫出最后的因果樹.
10條因果規(guī)則:差→32;可青→31;可中→11;可老→21;好青→31;好中高→11;好中平師→22;好中平商→12;好老師→12;好老商→11.
上述得到的因果規(guī)則只包含兩個(gè)目標(biāo)因素,要想得到被約簡(jiǎn)的目標(biāo)的取值情況,參照目標(biāo)取值的函數(shù)關(guān)系句(I-VI)來補(bǔ)齊.例如,把關(guān)系(I)(g1=3且g3=2)→g2=2;連接在因果規(guī)則(1)之后,便有:f4差→g1為3,g3為2→g2=2,寫成補(bǔ)齊式.
(1) I(f4) =差→ I(g1) =3,I(g2) =2,I(g3) =2.(根據(jù)(I))
類似地有
(2) I(f4)=可,I(f1)=青→I(g1)=3,I(g2)=1,I(g3)=1.(根據(jù)(II))
(3) I(f4)=可,I(f1)=中→ I(g1)=1,I(g2)=1,I(g3)=1.(根據(jù)(V))
(4)I(f4)=可,I(f1)=老→I(g1)=2,I(g2)=2,I(g3)=1.(根據(jù)(IV))
(5)I(f4)=好,I(f1)=高→I(g1)=1,I(g2)=1,I(g3)=1.(根據(jù)(V))
多目標(biāo)因果樹,見圖2.
圖2 多目標(biāo)因果樹 Fig.2 multiple target causality tree
(2)算法對(duì)比
利用常規(guī)的多目標(biāo)因果分析法,進(jìn)行超市用戶消費(fèi)情況的因果規(guī)則提取,具體步驟不再描述,得到的結(jié)果與多目標(biāo)因果分析法相同,接下來對(duì)比常規(guī)多目標(biāo)因果分析法和帶有目標(biāo)降維的多目標(biāo)因果分析法的計(jì)算時(shí)間和計(jì)算次數(shù),見表2.
表2 兩種算法的計(jì)算對(duì)比 Tab.2 calculation comparison of two algorithms
從表2中可以看出,多目標(biāo)因果分析降維算法的計(jì)算時(shí)間和計(jì)算次數(shù)均小于多目標(biāo)因果分析,且兩種算法的計(jì)算結(jié)果也相同,表明多目標(biāo)因果分析降維算法的計(jì)算效率更好,有效地降低了計(jì)算的繁雜性.
(1)定義了降維映射和鉆入決定度降維,將未被選定的目標(biāo)因素進(jìn)行合取,做到了目標(biāo)降維,得到了目標(biāo)因素的降維算法.
(2)在目標(biāo)因素降維算法的基礎(chǔ)上,定義總決定度,研究目標(biāo)因素之間的關(guān)聯(lián)性,并給出了關(guān)聯(lián)指標(biāo)的定義,結(jié)合多目標(biāo)因果分析法,提出多目標(biāo)因果分析降維算法.
(3)利用某超市數(shù)據(jù),進(jìn)行實(shí)例分析,證明多目標(biāo)因果分析降維算法具有實(shí)用性和有效性,并為多目標(biāo)優(yōu)化帶來新方法.