增量形式背景的拓撲坍縮表示

張 濤,李和合,曹海蘭,2,劉夢奇

1(燕山大學 信息科學與工程學院,河北 秦皇島 066004)2(河北東軟軟件有限公司,河北 秦皇島 066004)

1 引 言

形式概念分析[1]是對形式背景中的屬性、對象及其間關系進行分析和研究的理論,其提供了一種與傳統的、統計的數據分析和知識表示完全不同的方法.形式概念分析理論也稱概念格理論,是由德國的WILLE教授于1982年根據概念的哲學思想所提出的一種數學方法[2,3].目前形式概念分析的應用領域已經越來越廣泛,如軟件工程[4],知識發現[5],數據挖掘[6]等.

形式背景的表示方法是該領域的研究熱點之一.在經典的形式概念分析中,一般以Hasse圖為代表的概念格對其進行表示.但概念格表示不但計算復雜,而且表示內容僅限于以概念為單位的數據結構.隨后,以屬性偏序關系為基礎的屬性偏序圖[7]、以圖計算為代表的屬性樹[8]、以Hasse圖進行延展的直觀圖[9]以及以圖論為基礎的屬性拓撲[10]等等表示方法應運而生.

屬性拓撲 (Attribute Topology)是一種新型的形式背景的表示方法,其思想來源于計算機的網絡拓撲結構.在屬性拓撲中,將每一個屬性看作是一個信息終端,則整個的形式背景表現為終端間的信息溝通拓撲結構[3].該結構可以通過加權圖的形式進行直觀展現,使其具有良好的可視化特性.目前屬性拓撲在概念計算[11,12]、關聯關系發現[13]、認知計算等[14]領域都已有所發展.在概念計算中,以屬性拓撲為基礎的概念計算方法主要包括串行概念分析[11]、并行概念分析[15]以及深度優先概念分析[12].但隨著增量式計算的發展,迫切需要一種增量式的形式背景表示方法,為動態概念計算奠定表示基礎.

屬性拓撲的認知模型研究表明[14],對于特定新增對象,屬性拓撲具有局部聚焦特性.因此,對于增量式認知計算任務而言,其只需要對增量相關部分進行聚焦,進行局部計算即可完成增量過程.本文即以局部聚焦特性為基礎,提出拓撲坍縮算法(簡稱坍縮算法),并將其應用于增量式概念搜索,減少增量式概念搜索過程的復雜性,為基于認知模型的概念計算奠定基礎.

2 屬性拓撲的基本概念

一般情況下,增量式運算的增量部分在于形式背景中對象部分.因此需要將屬性拓撲轉化為對象拓撲表示.其基礎定義如下:

定義1.一個形式背景可以表示為K=(G,M,I),其中,G表示形式背景中所有對象的集合,M表示形式背景中所有屬性的集合,I?G×M表示對象與屬性之間的關系,G×M表示集合G與集合M的笛卡爾積.

定義2.設K=(G,M,I)是一個形式背景,若A?G,B?M,定義一對算子

f(A)={m∈M|?g∈A,(g,m)∈I}

g(B)={g∈G|?m∈B,(g,m)∈I}

如果二元組(A,B)滿足f(A)=B且g(B)=A,稱二元組(A,B)是形式背景K中的一個形式概念.A稱為概念(A,B)的外延,稱為概念(A,B)的內涵.通常用B(G,M,I)或B(K)表示形式背景K=(G,M,I)的所有概念構成的集合.

在傳統的屬性拓撲表示中以屬性為圖的頂點,屬性之間的耦合關系作為圖的邊進行表示.針對增量式計算一般為對象增量的情況,本文構造對象拓撲表示方法,將對象作為圖的頂點,對象之間的耦合作為邊進行表示.對象拓撲的定義為:

定義3.對于形式背景K=(G,M,I),對象拓撲的鄰接矩陣表示定義為OT=(V,Edge).其中V=G,為對象拓撲的頂點集合,Edge為對象拓撲邊的集合,稱為該對象拓撲的鄰接矩陣,Edge表示如下:

針對表1所示形式背景,其屬性拓撲與對象拓撲分別如圖1所示.

表1 形式背景Table 1 Formal context

由定義3和圖1可知,對象拓撲實際上為形式背景K轉置后的屬性拓撲,二者具有內在的一致性.因此,可將屬性拓撲中屬性定義與定義引申至對象拓撲.

定義4.根據對象間的不同關系,可以將所有的對象分為頂層對象集合SupObj和伴生對象集合SubObj兩個部分:

定義5.若存在gi,gj∈G,滿足f(gi)?f(gj),則稱對象gi和對象gj構成一組父子對象對,稱對象gj為對象gi的父對象,記做gj=Par(gi);同時稱對象gi為對象gj的子對象,記做gi=Chr(gj).

圖1 屬性拓撲與對象拓撲Fig.1 Attribute topology and object topology

3 對象拓撲的坍縮

人們在對新事物進行認知和決策時,會在大腦原有儲備中進行激活或更新[16].若新增對象為已知對象時,可以直接完成對新增對象的認知.對未知對象的認知學習過程,可以通過類似證據的累積過程完成對其認知,該過程在對象拓撲中表現為增加未知對象對應的頂點與關聯.隨著認知過程的累積,對象拓撲或形式背景將變得越來越復雜,這將使未知對象的認知學習難于處理.為了降低對新增對象認知學習的復雜性,本文給出拓撲坍縮算法,簡稱坍縮算法.

對象拓撲的“坍縮”概念來源于天體物理學上物質在引力作用下坍縮形成黑洞過程.引力坍縮是恒星在自身物質的引力作用下彼此拉近而產生坍縮,從而自身向內坍陷的過程.將坍縮的概念引入到對象拓撲中,“坍縮”形象地表達了在原始形式背景所對應的對象拓撲基礎上,通過對象間的相關性彼此吸引,從而向下一層坍陷的過程,坍縮過程簡化和描述了對未知對象的認知學習過程,同時使對象拓撲的處理過程更加形象.

3.1 對象分類

在對象拓撲中,頂點之間的連線可以清晰地描述兩個對象間的關系.對于一個確定的形式背景可以得到唯一的概念集合和概念格,因此一個確定的形式背景將對應于一個特定的認知能力.考慮到在形式背景中,新對象的加入不會影響原有各個對象之間的關系,因此在某個認知能力的基礎上,實現對新增對象的認知,只需考慮新增對象與原有各個對象之間的關聯性.

設原始形式背景為K=(G,M,I),加入新增對象new后的形式背景為K*=(G*,M*,I*),其中G*=G∪new,M*=M,I*?I;為了區分兩個形式背景下的關系,將在形式背景K*下的算子記為fK*和gK*.

定義6.對于任意的新增對象new,根據新增對象與原有對象之間的關系,可以將新增對象分為三類:

1)若?x∈G,使得f(x)=fK*(new),則稱新對象new為已知對象.

2)若?x∈G,滿足f(x)∩fK*(new)=?,則稱新對象new為完全未知對象.

3)其它,則稱對象new為半未知對象,根據對象間的具體關系可以細化為三種情況:

a)f(x)∩fK*(new)=f(x),對象new其特征可以覆蓋在原始形式背景中對象x的特征,在對象拓撲圖中,二者間存在由對象節點new指向節點x的單向邊,且權值為f(x).

b)f(x)∩fK*(new)=fK*(new),在原始形式背景中存在對象x其特征包含對象new的特征,在對象拓撲圖中,二者間存在由對象節點x指向節點new的單向邊,且權值為fK*(new).

c)f(x)∩fK*(new)≠?且f(x)∩fK*(new)≠f(x)且f(x)∩fK*(new)≠fK*(new),即二者為相容關系,在對象拓撲中,二者之間存在雙向邊,且權值為f(x)∩fK*(new).

根據定義6,若在現有的認知能力下,新增對象new與對象x的特征屬性是相同的,則可以通過x完成對new的準確認識,將其劃為已知對象;若新增對象與任意已知對象之間的關系呈現互斥關系,直觀地看,在對象拓撲圖中表現為二者間不存在任何邊的連接,則新增對象new是一個完全陌生的未知對象.當new為半未知對象時,在原始形式背景中,存在與其關聯的已知對象.由于在現有形式背景的認知能力下,無法直接明確的認識完全未知對象和半未知對象,將它們統稱為未知對象.新增對象的各個類別之間的關系如圖2所示.

圖2 新增的對象各個類別之間的關系Fig.2 Relationship of new objects in the view of categories

例如,在表1的形式背景的基礎上增加一個對象new1,其屬性特征為{c,d,e},易得fK*(new1)=f(7),根據定義此時新增對象new1為已知對象,可以直接由對象7完成對新增對象new1的認知.若在表1所示形式背景的基礎上新增對象new2,其屬性特征為{d,e},易知新增對象new2為半未知對象,此時不能直接對new2作出準確的判斷,且對象8與new2滿足分類3中的條件a,對象2,6,7與new2滿足分類3中的條件b,對象1與new2滿足分類3中的條件c.

性質1.對于形式背景K=(G,M,I),設new為新增的未知對象,若#{fK*(new)}=1,則new與原形式背景K中對象只存在不關聯關系和被包含關系.

證明:因為new為未知對象,所以不存在對象x∈G使得new=x.即若x∈G且#{f(x)}=1,則new與x定不存在關聯.

當x∈G且#{f(x)}>1時,若f(x)∩fK*(new)=?,則不存在關聯;

若f(x)∩fK*(new)≠?,則f(x)∩fK*(new)=fK*(new),即對象new與x為包含關系,且對象x包含對象new.

證畢.

3.2 坍縮過程

按照3.1小節給出的分類方法,新增對象可分為已知對象、完全未知對象和半未知對象,由于已知對象已經可以實現準確的認知,本節算法只針對后兩種情形,討論未知對象的對對象拓撲的影響.設未知對象為new,OT=(V,Edge)為原形式背景K所對應的對象拓撲,對象拓撲坍縮的算法見算法1,坍縮后所得對象拓撲記為OTclp=(Vclp,Edgeclp).

算法1.

算法名:對象拓撲的坍縮

算法功能:簡化未知對象的增量式概念認知過程,減小新

增對象認知學習過程的復雜性.

Step1.Vur={v∈V|f(v)∩fK*(new)=?}

Step2.OTct=(Vct,Edgect),Vct=V-Vur,

?vi,vj∈Vct,Edgect(vi,vj)=Edge(vi,vj)

Step3.若新增對象new為頂層對象,則進入Step 4;否則

跳轉到Step 6

Step4.令Vclp=Vct+{new},?vi,vj∈Vclp,

Edgeclp(vi,vj)=

Step5.跳轉到步驟7

Step6.令Vclp=Vct-Par(new)+{Par(new)∪new},

?vi,vj∈Vclp

Edgeclp(vi,vj)=

Step7.得到坍縮后的對象拓撲OTclp=(Vclp,Edgeclp)

在對象拓撲的坍縮過程中,Step 1-2根據新增對象new與原始對象拓撲OT=(V,Edge)中所有對象間的關聯,對原始對象集合進行了分離,通過刪除與新增對象new不存在關聯的對象集合,得到規模較小的對象拓撲OTct.Step 3中將新增對象按頂層對象和伴生對象分別進行后續的坍縮算法.Step 4-7,完成對象拓撲的坍縮算法.對于新增對象為頂層對象的情形,將新增對象作為新結點加入,并依據對象間的關系完成對新增對象的認知.對于新增對象為伴生對象的情形,將新增對象與其父對象進行合并,然后再與原形式背景中各對象的對應關系,對其進行認知.對于完全未知對象而言,Vur=Vr,則OTct為一空拓撲,此時新增對象加入后成為拓撲中的頂層對象,算法轉入Step 4-5,此時該對象將獨立形成全新的概念,符合認知的原理.

對于表1所示的形式背景K=(G,M,I),對應的對象拓撲如圖1(b)所示,若新增對象為new,滿足fK*(new)={d,e}.直接在原始對象拓撲中進行表示,其結果如圖3(a)所示.根據算法1對其進行拓撲坍縮運算,首先可以獲得與新增對象無關的對象集合為Vur={3,4,5},然后獲得對象拓撲OTct如圖3(b)所示,其中Vct={1,2,6,7,8}.

圖3 坍縮過程示例Fig.3 Example of a collapsing process

可見,加入新增對象new后,完成對原始對象拓撲的坍縮時,若存在與對象new無關的節點,例如圖3(a)所示的節點3、4、5,則通過坍縮可以去除掉原始對象拓撲的冗余部分,得到如圖3(b)所示的OTct,此對象拓撲圖僅與新增對象new存在關聯性,是原始對象拓撲的子對象拓撲.

由于新增對象new滿足fK*(new)={d,e},為一伴生對象,其父對象有{2,6,7},則將新增對象與父對象合并后可以得出Vclp=Vct-Par(new)+{Par(new)∪new}={1,2,6,7,8}-{2,6,7}+{2,6,7,new}={1,8,{2,6,7,new}}.此處為了描述方便,記NEW={2,6,7,new},則Vclp={1,8,NEW}.得到坍縮后的對象拓撲圖3(c)所示.

4 實 驗

為了驗證本文提出的坍縮算法對增量式分析的影響,采用概念搜索算法對其性能進行評估.由于坍縮表示基礎為屬性拓撲,因此選擇的對比算法均以屬性拓撲為基礎的DFFCS、BDAT兩種算法.其中,DFFCS為典型的串行概念搜索算法,BDAT為典型的并行搜索算法.實驗過程中均采用默認參數.

本節實驗中選取5個數據集,除了典型的形式背景生物和水(Living Beings and Water)之外,還選取了四組來自UCI的數據集,Balance scale[17],Tic tactoc[18],Mushroom[19]和Nursery[20].這些數據集大多是多值的,因此實驗前需要首先將它們轉化為二值背景[1],然后經過預處理去除冗余的對象和屬性,得到凈化后的二值形式背景,實驗中使用的各個二值形式背景的基本信息列于表2中.實驗過程中采用的增量方式為按照數據集中默認對象順序由零開始進行增量,至數據集中所有對象完成為止.

由于本實驗主要考察坍縮運算對于運算速度的提升,因此以坍縮前后概念計算時間為評價指標.在進行實驗時,考慮到算法的運行時間將會受到系統中其它進程的影響,為了減小實驗的偶然誤差,提高計算時間記錄的準確性,每種算法分別對每個數據集進行了10次測試,最后對這10次記錄的時間監視數據求取平均值,作為最終的算法運行時間.

表2 實驗中使用的二值形式背景的基本信息Table 2 Information of binary context in experiments

表3 DFFCS算法坍縮前后時間對比Table 3 Comparison before and after collapse to DFFCS intime consuming

表4 BDAT算法坍縮前后時間對比Table 4 Comparison before and after collapse to BDAT in time consuming

綜合表3和表4的實驗結果,可以看到經過坍縮運算后的大多數增量式概念計算速度得到了有效提升.但對于串行計算而言,形式背景“Living Beings and Water”的運算時間反而有所增加.其原因在于該形式背景較小,坍縮運算的帶來的計算量減小不足以抵消坍縮運算本身的時間消耗.但隨著形式背景復雜度的增加,坍縮運算帶來了明顯的速度提升.因此,坍縮運算適用于中等規模以上的形式背景增量式分析.

通過對比表3和表4的實驗結果,可以發現并行運算的速度提升低于串行運算.其主要原因在于本實驗的增量方式為逐個加入.對于串行計算而言,坍縮后的串行表示方式仍維持較大規模,而并行運算經過分解后變為小規模形式背景.通過分析已知:小規模形式背景下坍縮運算對速度提升不如大規模形式背景明顯.因此,并行運算的速度提升要低于串行運算.

5 結 論

本文在屬性拓撲基礎上,提出了拓撲坍縮的增量式形式背景表示方法.該表示方法可以直觀的對新增對象進行聚焦表示,從而降低表示和后期計算的復雜度.實驗表明,經過坍縮運算后的增量式概念計算,對于中等規模以上形式背景具有明顯的速度提升.如何利用拓撲坍縮算法設計一體化的增量式概念搜索算法,是下一步值得研究的方向.

：

[1] Ganter Bernhard,Wille Rudolf.Formal concept analysis:mathematical foundations [M].New York:Springer-Verlag,1999:5-75.

[2] Ma Yuan,Zeng Zi-wei,Chi Cheng-ying,et al.Formal concept andits new development[M].Beijing:Science Press,2011:1-60.

[3] Xu Wei-hua,Li Jin-hai,Wei Ling,et al.Formal concept analysis:theory and application[M].Beijing:Science Press,2016:206-239.

[4] Sun Xiao-bing,Li Yun,Li Bi-xin,et al.A survey of using formal concept analysis for software maintenance[J].Acta Electronica Sinica,2015,43(7):1399-1406.

[5] Shao Ming-wen,Yang Hong-zhi,Wu Wei-zhi,et al.Knowledge reduction in formal fuzzy contexts[J].Knowledge-Based Systems,2015,(73):265-275.

[6] Rodríguez-Jiménez Jose Manuel,Cordero Pablo,Enciso Manuel,et al.Data mining algorithms to compute mixed concepts with negative attributes:an application to breast cancer data analysis[J].Mathematical Methods in the Applied Sciences,2016,39(16):4829-4845.

[7] Hong Wen-xue,Luan Jing-min,Zhang Tao,et al.Knowledge discovery method based on partial order structure theory[J].Journal of Yanshan University,2014,38(5):394-402.

[8] Zhang Tao,Hong Wen-xue,Lu Jing.Attribute tree representation for formal context[J].System Engineering Theory & Practice,2011,31(S2):197-202.

[9] Wei Ling,Wan Qing.Granular transformation and irreducible element judgment theory based on pictorial diagrams[J].IEEE Transactions on Cybernetics,2014,46(2):380-387.

[10] Zhang Tao,Ren Hong-lei.Attribute topology of formal context [J].Journal of Chinese Computer Systems,2014,35(3):590-593.

[11] Zhang Tao,Ren Hong-lei,Hong Wen-xue,et al.The visualizing calculation of formal concept that based on the attribute topologies [J].Acta Electronica Sinica,2014,42(5):925-932.

[12] Zhang Tao,Li Hui,Hong Wen-xue,et al.Deep first formal concept search[J].The Scientific World Journal,2014,2014(8):275-679.

[13] Zhang Tao,Wei Xin-yu.Association rules detecting based on attribute topology[J].Journal of Chinese Computer Systems,2017,38(3):548-552.

[14] Wei Xin-yu,Zhang Tao,Bai Dong-hui.Attribute topology granular analysis based on topology split[J].Journal of Chinese Computer Systems,2016,37(8):1751-1754.

[15] Zhang Tao,Bai Dong-hui,Li Hui.Parallel concepts computing based on bottom-up decomposition of attribute topology[J].Journal of Software,2017,28(12):3129-3145..

[16] Kvam Peter D,Pleskac Timothy J,Yu Shu-li,et al.Interference effects of choice on confidence:quantum characteristics of evidence accumulation [J].Proceedings of the National Academy of Sciences of the United States of America,2015,112(34):10645-10650.

[17] Gharehchopogh Farhad Soleimanian,Khaze Seyyed Reza.Data mining application for cyber space users tendency in blog writing:a case study[J].International Journal of Computer Applications,2013,47(18):40-46.

[18] Klahr David,Siegler Robert S.The representation of children′s knowledge[J].Advances in Child Development & Behavior,1978,(12):61-116.

[19] Lincoff Gary H.The audubon society field guide to north American mushrooms[M].Knopf:Distributed by Random House,1981.

[20] ZupanBlaz,Bohanec Marko,Bratko Ivan,et al.Machine learning by function decomposition[C].Proceedings of the Fourteenth International Conference on Machine Learning,1997:421-429.

附中文參考文獻：

[2] 馬 垣,曾子維,遲呈英,等.形式概念及其新進展[M].北京:科學出版社,2011:1-60.

[3] 徐偉華,李金海,魏 玲,等.形式概念分析理論與應用[M].北京:科學出版社,2016:206-239.

[4] 孫小兵,李 云,李必信,等.形式概念分析在軟件維護中的應用綜述[J].電子學報,2015,43(7):1399-1406.

[7] 洪文學,欒景民,張 濤,等.基于偏序結構理論的知識發現方法[J].燕山大學學報,2014,38(5):394-402.

[8] 張 濤,洪文學,路 靜.形式背景的屬性樹表示[J].系統工程理論與實踐,2011,31(S2):197-202.

[10] 張 濤,任宏雷.形式背景的屬性拓撲表示[J].小型微型計算機系統,2014,35(3):590-593.

[11] 張 濤,任宏雷,洪文學,等.基于屬性拓撲的可視化形式概念計算[J].電子學報,2014,42(5):925-932.

[13] 張 濤,魏昕宇.屬性拓撲關聯規則發現[J].小型微型計算機系統,2017,38(3):548-552.

[14] 魏昕宇,張 濤,白冬輝.基于拓撲分裂的屬性拓撲粒結構分析[J].小型微型計算機系統,2016,37(8):1751-1754.

[15] 張 濤,白冬輝,李 慧.基于屬性拓撲的并行概念計算算法[J].軟件學報,2017,28(12):3129-3145.