三元概念分析的聯盟應用研究

王紅敏,張 卓,王黎明

(鄭州大學 信息工程學院,鄭州 450001)

1 引 言

隨著網絡技術的飛速發展,互聯網中涌現出了越來越多的三維數據.1995年,Wille R.等受實用主義哲學的啟發把FCA(形式概念分析)擴展到三元背景下,提出了三元概念分析.Lehmann.和Wille 在文獻[1]中首次定義了三元背景、三元概念和概念三元格.文獻[2]介紹了如何從三元圖中讀出不同的信息.文獻[3]提出了一種構造三支概念的算法CbO3C.文獻[4]介紹了三支概念與經典形式概念的關系,并且在經典形式背景給出了兩種具體的三支概念模型.文獻[5]從三支決策的視野探究不同概念格之間的內在聯系.文獻[6]梳理了三元概念分析的研究現狀及發展趨勢.文獻[7]研究了概念三元格的構造算法及其在folksonomy分類中的應用.文獻[8]研究了三元概念分析在文本分類中的應用.

關于經典的合作博弈,已經存在諸多相關研究并且廣泛的應用在多智能體協作[9,10-12]等領域.合作博弈的第一個主要問題是參與者如何結盟.然而,在大多數情況下,并不是N的所有子集都可以構成一個聯盟或者是可行的,這就意味著效用函數只是映射在2N的子集F上.Aumann和Dreze[13]針對該情況提出了聯盟結構.Faigle和Kern[15]提出了限制合作.F在分布格(在交和并下封閉)[15]、凸代數[16]等一些結構的假設中被研究.與以往研究不同的是,本文基于參與者所擁有的資源,提出受限合作博弈,在這種條件下,經典的Shapley值將不再適用,需要重新定義.2014年,Faigle U[17]等人提出了基于概念格的博弈,但他只是從數學層面給出了一些定理,并沒有指出相關的應用以及算法的實現.因此本文借鑒形式概念分析上的博弈以及結合作為處理分析數據新框架的三元概念分析的特點,提出了受限合作博弈,并且結合三元概念分析與合作博弈的特點,提出了受限合作博弈的聯盟形式的形成算法LMXC,以及效用值分配G-shapley值法.

2 相關理論

2.1 三元概念分析基本理論

三元概念分析作為形式概念分析的推廣,是一種新的信息處理的概念和計算范式,它能夠有效的處理三維數據.網絡上的三維數據可以表示為三維二值表,根據相應算子的計算推理,進而得到所有的三元概念.

定義1.[6](三元背景):三元背景被定義為四元組(G,M,B,Y),其中G是對象集合,M是屬性集合,B是條件集合,Y是G、M和B之間的三元關系,且Y?G×M×B,(g,m,b)∈Y表示對象在條件b下具有屬性m.

定義3.[6]((i)-誘導算子):三元背景K=(K1,K2,K3,Y),{i,j,K}={1,2,3},滿足j

X→X(i):={(aj,ak)∈Kj×Kk|(ai,aj,ak)∈Y,?ai∈X}

Z→Z(i):={ai∈Ki|(ai,aj,ak)∈Y,?(aj,ak)∈Z}

定義4.(預序和等價關系):三元背景K=(K1,K2,K3,Y),S為三元背景下所有三元概念的集合,對于任意的(A1,A2,A3)∈S,(B1,B2,B3)∈S,定義預序關系≤i和等價關系～i為:

(A1,A2,A3)≤i(B1,B2,B3) Ai? Bi,

(A1,A2,A3)～i(B1,B2,B3) Ai= Bi,

i={1,2,3}.

2.2 合作博弈

用N={1,…,n}表示有限個參與者的集合,在這n人的博弈中,N的任何一個子集S就作為一個聯盟,與結盟相關的是特征函數.空集Φ和全集N也可以稱作聯盟,單點集{i}仍是一個聯盟.然而,在多數情況下,合作是受限的,比如當只有他人加入到此聯盟時一些人才加入該聯盟.本文我們考慮一般情況,即合作是受限的.

一個合作博弈(F,ν),對于任意一個S?N的聯盟,一個分配向量就是一個向量x∈Rn,對每個參與人i∈N分配一個實值參數,形成n維向量x={ x1,…,xn}.

3 三元概念分析的聯盟應用

本文首先利用三元概念分析的理論解決受限合作博弈聯盟形式形成問題,然后結合三元概念分析與Shapley值法提出G-shapley值法,進而能夠有效分配聯盟的效用值,得到每個參與者的平均邊際貢獻.

3.1 聯盟形式形成

針對聯盟的形成問題,經典的合作博弈理論假設N局中人任意的子集都成為一個聯盟,比如,有N={A,B,C}三個參與者,那么依據其理論,就形成B={Φ,A,B,C,AB,AC,BC,ABC}八種聯盟形式.然而,實際的很多情況下,參與者并不是一成不變的,即參與者所擁有的資源與它所處的條件息息相關,就比如,參與者A在a條件下有資源1,隨著環境的變化,參與者在條件b下就不一定還擁有資源1,因此,參與者的個體狀況依賴于它所處的環境.針對此種情況,本文結合三元概念分析與合作博弈各自的優勢提出一種新的理論,稱之為受限合作博弈這種合作方式仍然有一定的聯盟優勢.類似于合作博弈聯盟的概念,本文提出如下聯盟形式的概念:

定義5.(聯盟形式)聯盟形式以三元組(A,B,C)的形式刻畫,A代表參與者集合,B表示參與者在條件C下共同擁有的資源集,C表示條件集合.

為有效處理受限合作博弈的聯盟形式形成問題,同時為了清晰描述本文理論,本節借鑒Faigle U[17]提出的基于概念格的博弈論,并結合三元概念分析的特點,以提出問題并解答問題的方式解析聯盟形式的形成過程.

為解決上述問題,首先將上述條件通過三元背景的形式進行描述,利用三元背景的對象集K1代表參與者的集合、屬性集K2代表參與者所擁有的資源或能力、條件集K3表示參與者所屬條件的集合.如果參與者在某個條件下具有某種資源或者能力,在相應的位置上就用1表示,否則用0表示,最終通過三元背景描述了參與者、參與者在特定條件下所擁有的資源、參與者所屬的條件之間的三元關系.聯盟形式的形成借鑒了文獻[18]的CTLA算法的思想,具體的形成過程主要包括兩部分:一:在單個條件下,類似于合作博弈理論中,單點集{i}也稱為聯盟,本文將單個參與者依靠自身所擁有的所有資源或能力也看作一種聯盟形式,多個參與者為形成強強聯合,提高效率,依賴他們共同擁有的資源組成多參與者合作的聯盟形式,基于此就形成了單個條件下所有的聯盟形式.二:在多個條件下,有時參與者在不同的條件下具有某些同種類的資源,為了使本文研究粒度更加細化同時為了對后續聯盟效益分配更加精確,針對此種情況將某些條件下參與者共同擁有某些資源也看作一種聯盟形式,有時還表示在不同的條件下存在相同參與者及同種資源的合作方式,為了減少冗余,將條件進行合并.

定義6.(穩定聯盟):如果一個聯盟是任一三元概念的外延,那么這個聯盟是有效的或者說是穩定的.在相同的條件下(S′′,S′)是一個二元概念,形成的聯盟也是穩定的.

定義7.(受限合作博弈):受限合作的博弈是一個三元組T=(N,F,ν),N是有限個參與者的集合,F是N的子集構成的有效聯盟的集合,ν是F→R的效用值函數,并且ν(Φ)=0.

算法1.LMXC()

輸入:預處理后的三元背景(K1,K2,K3,Y)

輸出:所有的聯盟形式C

1.begin

2. for(every a∈K3)

3. 在模式a下所有的聯盟形式以概念的形式存入f[a]

4. for(every(S,S′)∈f[a]

5. (S,S′)→(S,S′,a)

6. end for

7. end for

8. e=|K3|;

9. for(int i=0;i

10. for(every(A1,B1,C1)∈f[i])

11. for(every(A2,B2,C2)∈f[i])

12. if(A1=A2and B1=B2)

13. Insert((A1,B1,C1∪C2))

14. end if

15. end for

16. end for

17. end for

18.end

算法2到5行,描述在單個條件下,如果不同的參與者擁有相同的能力技能,為了實現強強聯合,獲得更多的利益,就形成該條件下的聯盟形式.單個參與者也可不與其他參與者合作,僅使用自身所有能力形成類似于單點集的聯盟形式.

基于ARIMA-TREND的企業價值評估收益法探析——以A企業價值評估為例 …………… 李保嬋 王思穎 林俊良（4/36）

算法10到13行,算法10到16行,描述在不同的條件下,如果得到相同的參與者組合及相同的資源集組合,就說明此參與者組合存在不同條件下的合作,為提高效率對不同的條件進行合并以及為了使聯盟效益分配更加合理同時使研究粒度更加細化將參與者在不同條件下共同擁有的屬性此種狀態也刻畫為聯盟形式.

為了使上述的聯盟形式的形成更加清晰、直觀,接下來引入一個算例,將該理論用在企業之間的合作.

算法實例1.在2012年在接受訪問的14家通州企業中,有12家與其他企業有合作,以其中三家企業為應用背景,結合企業的行業特點,綜合國內外有關企業能力評價指標已有的結果,建立了企業能力指標體系及其指標量化結果如表1所示,表1列舉了3家企業構成的集合為N={A,B,C},a、b、c、d分別代表技術、生產、銷售、資金四種合作方式,1、2、3、4、5、6分別表示企業在技術力量、售后服務、資產負債、地理位置、市場影響、企業信譽六個方面的能力,用本節提出的聯盟形式的形成理論,依據企業所擁有的能力可以形成哪些聯盟形式.

首先用三元形式背景來刻畫上述問題,如表1所示.

表1 三元背景
Table 1 Triadic concext

abcd123456123456123456123456A111111111B111111111C111111111111111

針對上述問題,根據LMXC算法生成以下聯盟形式:(A,146,d),(AC,126,c)(A,15,a),(B,146,b),(C,12356,b),(BC,16,ab),(C,1246,a),(C,126,abc),(ABC,1,abcd),(B,15,cd),(AC,16,cd),(C,16,abcd),(C,136,bd).

在上述的結果中,通過LMXC算法共生成了13個聯盟形式,將聯盟形式以三元組的形式表示,分別代表企業組合、企業組合共有的技能、合作模式.根據定義2的三元概念的形成理論可知每個聯盟形式都是一個三元概念,因此這些聯盟形式又是穩定聯盟,每個穩定聯盟中的局中人,這里表示每家企業受外界約束不會隨意退出該聯盟.每個三元概念代表一定的合作含義比如概念(AC,126,c)就表示企業A和C在技術力量、售后服務、市場影響三方面較一致,進行銷售合作.企業也有可能不進行合作,(C,136,bd)就表示企業C依靠自身所擁有的技術力量、資產負債情況、企業信譽獨自完成生產與資金模式.每個聯盟形式又是穩定的,比如企業A擁有能力126可以獨自完成生產模式.但為了形成更加穩定的聯盟以獲得更多的利益,它會與擁有同樣能力的企業C合作.

如果運用經典的合作博弈理論針對上述的三家企業的合作問題,它不考慮企業合作模式的種類的狀況以及企業在不同的合作模式下所擁有資源的變化情況,只是簡單的用窮舉的方法產生{?,A,B,C.AB,AC,BC,ABC}所有這8種聯盟形式,如果有N家企業,那么也將用窮舉的方法生成2N種聯盟.顯然,本文提出的聯盟形式形成算法與經典的合作博弈聯盟形成方法相比在粒度上更加細化,不僅考慮到參與者自身擁有的資源狀況還充分的考慮到了參與者所處的條件.

3.2 效用值的分配

效用理論的核心是效用和效用函數,每個聯盟形式的形成都對應一個效用值,效用值由特征函數描述.將聯盟的效用值進行合理的分配,這是聯盟穩定的關鍵因素之一.博弈論Shapley值基于參與人的邊際貢獻來對參與者進行分配,比其它的方法公平.因此本文以經典Shapley值為基礎,又因為本文討論的是受限合作博弈,即特定條件下的合作,那么Shapley值將不在適用.基于此本文將經典的Shapley與三元概念分析相結合提出了G-shapley值法.

定義9.(G-shapley):對于每一個三元博弈(l,V)存在唯一的G-shapley值:Φ(v)={φ1(v),φ2(v),…,φn(v)}.其中:

Φi((l,V))=

(1)

基于G-shapley的特性,可以在條件維上定義G-shapley,依據G-shapley值的最終結果可以對條件的重要程度進行排序和加權.還可以在屬性維上定義G-shapley值,這樣能夠有效的依據其結果對參與者所擁有的屬性的依賴程度進行由經典形式背景向模糊形式背景的轉化.

定義9.(同伴參與者):F是N上的一個閉系統[17].一個子集K?N,對于任意一個不為空的子集S∈F,如果K?S或者K∩S=Φ,那么|K|>1在F上是一個同伴參與者.

定理.l=(K1,K2,K3,Y)是一個三元背景,(l,v)是三元背景l上的博弈,如果K是聯盟S同伴參與者,那么Φi(l,v)=Φj(l,v).

基于上述定理可以在屬性上定義同伴參與者,當兩個屬性滿足同伴關系時,可以有效的進行屬性消減.

算法2.G-shapley值法:

輸入:聯盟形式集合T、概念子節點數組S

輸出:成員利益分配D

//判斷葉子節點和根節點是否唯一,修正概念集

1. for each c∈S

2. if S[c].size==0

3. Leaf.add(c)

4. else

5. Unroot.put(S[c])

6. end if

7. end for

8. if Leaf.size > 1

9. c1 = createConcept(Leaf)

10. T.add(c1)

11. LeafNode = c1

12. else

13. LeafNode = L[0]

14. end if

15. if (T.size - Unroot.size)> 1

16. c2 = createConcept(Root)

17. T.add(c2)

18. end if

19. //重新計算聯盟間關系

20. S′ = computeRealtion(T)

21. //從葉子節點出發向上,遞歸得到所有鏈路

22. Links = constructLinks(T,S′,LeafNode)

23. //根據鏈路計算聯盟成員收益

24. for each p∈RootNode.Extends

25. for each r∈Links

26. for each c∈r

27. c′ = r[c+1]

28. if !c.Extends.contains(p)&

29. c′.Extends.contains(p)

30. profit +=(P[c′] P[c])/

31. (c′.Extends.size-c.Extends.size)

32. end if

33. end for

34. end for

35. D[p]= profit

36. end for

37. Output D

算法第1行到19行,根據A1?B1、A2?B2及A3?B3對所有的聯盟形式進行聯盟形式格結構的構造.

算法第20行到35行,求解參與者i的能力值.如果參與者i屬于擁有全部資源的聯盟,對該聯盟值均分,否則,搜索整個格結構的每條鏈,查找任一條鏈第一個包含i的聯盟形式,以及最后一個不包含鏈的聯盟形式,得到參與者i的平均邊際貢獻.

為了驗證本節提出的G-shapley值的正確性,引用文獻[19]中的背景數據,該文獻將Shapley值應用在在農產品合作供應鏈中,符合本文的研究理論,本文用到的具體數據如圖1所示.

圖1 聯盟形式格結構圖1 Lattice structure of alliance form

在農產品合作供應鏈中有三個參與者,它們分別是:生產者A、物流商B、零售商C,當A、B、C單獨經營時,均能獲得3萬元的收益,若A和B合作獲7萬元,A和C合作獲8萬元、B和C合作獲10萬元,A和B和C合作獲10萬元.

依據上述數據,采用本文提出的G-shapley值法計算三個參與者的分配利益,農產品合作供應鏈可看作單個條件下的合作問題,根據G-shapley值法的主要思想,形成圖1所示的聯盟形式格結構:

圖中的每個節點由聯盟形式及其對應的效用值的有序對組成,按上述聯盟形式的定義,聯盟形式應有參與者組合,共同的資源及條件組合這三部門組成,但此處解決的是單條件在的利益分配問題,為描述簡單又由于文獻[19]未詳細描述參與者的資源信息,因此聯盟形式用參與者集合描述.圖2共有6條鏈路組成:

第1條鏈路:8 5 2 1

第2條鏈路:8 5 3 1

第3條鏈路:8 6 2 1

第4條鏈路:8 6 4 1

第5條鏈路:8 7 3 1

第6條鏈路:8 7 4 1

求解生產者的分配利益ΦA(v)具體過程:

1.在第1條鏈路上找到最后一個不含生產者A的聯盟形式并獲得它的效用值,由圖2可知它為節點8,節點8的聯盟形式是?,效用值為0;

2.在第1條鏈上找到第一個含有參與者A的聯盟形式并獲得它的效用值,由圖2可知它為節點5,節點5的聯盟形式為A,效用值為3.

3.計算聯盟形式A與聯盟形式?參與者差值的模|A?|=1.

同理可得物流商分配利益ΦB(v)=8.5萬元;零售商分配利益ΦC(v)=9萬元.與文獻[19]中通過經典Shapley值計算的結果是一樣的,具體的計算過程文獻[19]已展示,這里不再贅述.

本文提出的G-shapley值適合任何使用經典Shapley值計算利益分配問題,但如果是多條件下的利益分配問題,就不能再使用經典Shapley值計算.

3.3 算法的時間復雜度分析

本文提出的模型主要包括兩個部分:LMXC()算法和G-shapley()值法,對每個部分進行時間復雜度分析.LMXC()和G-shapley()的時間復雜度與三元概念中的外延、內涵和條件都有關系,LMXC()算法的執行時間主要取決于聯盟形式的形成,聯盟形式由參與者數量,參與者擁有的資源和條件種類共同決定,而在滿足三元關系的情況下,這三者可分別看作三元背景的對象數目、屬性數目和條件個數.在計算每個條件下形成聯盟形式的時間復雜度時,需要考慮到所有參與者的所有資源.因此,每個條件下聯盟形式的時間復雜度為O(‖L1‖*‖L2‖),那么在所有條件下形成聯盟形式的時間復雜度為O(‖L1‖*‖L2‖*‖L3‖).G-shapley值法的時間復雜度取決于LMXC()算法生成的聯盟形式的數量,假設由LMXC形成的聯盟形式個數為‖A‖,在G-shapley的格構建過程中,在判斷任意一個聯盟形式與其他聯盟形式的關系時,需要搜索除它以外所有的聯盟形式,因此格構建的時間復雜度為O(‖A‖*‖A‖).對參與者的效用分配,需要考慮三個階段:聯盟形式的形成、聯盟形式格的構建,格的搜索,在格的搜索過程中,考慮極限情況,在評估每個參與者復雜度為O(‖L1‖*‖A‖).綜上所述,總的時間復雜度為:O(‖L1‖*‖L2‖*‖L3‖+‖A‖*‖A‖+‖L1‖*‖A‖)

4 實驗結果與分析

文章的第三部分已對提出的理論進行了有效性的分析與驗證,因此本節分別測試LMXC和G-shapley值法的性能,由于本文是從參與者所擁有資源層面進行受限合作研究的,與經典的合作博弈不同,由于沒有權威的聯盟形式形成算法以及效用分配算法作比較分析,因此本文的算法沒有與其它文獻的算法進行對比.

實驗環境:3.4GHz CPU,4GB內存,Win10操作系統,使用Java實驗平臺對LMXC()算法及G-shapley值法的性能進行驗證.針對本文的研究內容,由于沒有典型的數據集,因此實驗用到的數據是隨機生成的.

4.1 聯盟形式構造

實驗中分別將參與者數量、參與者向量維度作為變量執行LMXC算法.

實驗1.a.在參與者能力向量維度為10,條件種類為5的條件下使參與者的個數不斷增加,實驗結果如圖2所示.

圖2 實驗a參與者數量作為變量實驗分析圖Fig.2 Performance of experiment a where as variable

實驗結果表明,固定參與者能力向量維度以及條件種類的條件下,隨著參與者數量的增多,運行時間也隨之增加.這是因為當參與者的個數增多時,參與者的組合方式隨之增加,在單個條件下形成的聯盟形式也增加.在多個下進行聯盟形式的合并時,需要對比的聯盟形式的數量也會增加,從而導致算法的執行時間增長.

b.參與者數量為30,條件種類為8的條件下,使參與者向量維度不斷增加,實驗結果如圖3所示.

圖3 實驗b參與者向量維度作為變量實驗分析圖Fig.3 Performance of experiment b where attribute as variable

實驗結果表明,隨著參與者能力向量維度的增加,運行時間也隨之增加.這是因為當參與者的能力向量維度增加時,參與者的合作方式種類會增加,相應的聯盟形式的個數也會增長.通過圖2和圖3觀察到,算法的執行時間都有所增加,原因是無論是增加參與者的數量還是增加參與者的向量維度,最終都會導致聯盟形式的增多,從而影響算法的性能.

4.2 聯盟效用分配

實驗中將LMXC算法得到的聯盟形式作為輸入執行G-shapley值法并進行分析,通過觀察該算法的運行時間來衡量算法的性能.

實驗2.a.在參與者能力向量維度為6,條件種類為3的條件下,參與者個數不斷增加,實驗結果如圖4所示.

圖4 實驗a G-shapley分配實驗分析圖Fig.4 Performance of experiment a G-shapley

b.在參與者數量為30,條件種類為3的條件下,參與者向量維度不斷增加,實驗結果如圖5所示.

圖5 實驗b G-Shapley分配實驗分析圖Fig.5 Performance of experiment b G-shapley

從圖4和圖5的實驗結果觀察到如果將LMXC的運行結果傳送給G-shapley,它的運行時間隨著參與者數目的增加或者參與者向量維度的增加而有所上升這是因為在求解G-shapley值的過程中,首先要構建聯盟形式的格結構,隨著輸入的聯盟形式的數量的增多,所構建的格會變大,在計算參與者的平均邊際貢獻時,要搜索所構建格的每條鏈,在每條鏈上查找其對應聯盟形式的效用值時,每個環節都會隨著聯盟形式數量的增多,算法的執行時間也會增加,實驗結果表明,只要聯盟形式的數量增多,在執行G-shapley進行分配時所需時間就會增大.

5 總 結

本文在三元概念分析理論的基礎上引入了受限博弈,主要研究了如何運用三元概念分析解決受限合作的聯盟形成以及為了得到參與者的分配值,結合三元概念分析的理論提出了G-shapley算法,同時通過實驗測試了本文模型的效率.該理論的提出是對三元概念分析的擴展,同時也為三元概念的應用奠定了基礎.雖然三元概念分析有很大的發展空間,但本文提出的理論是三元概念分析在受限合作博弈上的初步探索,仍有許多不足之處,如本文提出的G-shapley值法,隨著參與者人數的增多,算法的運行時間有待進一步研究以及LMXC算法也要進一步優化.