區(qū)間概念格的縱向維護(hù)原理與算法*

張春英，王立亞,劉保相

(華北理工大學(xué)理學(xué)院，河北 唐山 063009)

摘要：區(qū)間概念格是唯一能直接反映具備一定數(shù)量或比例的內(nèi)涵中屬性的對(duì)象集合的格結(jié)構(gòu)。格結(jié)構(gòu)是根據(jù)對(duì)象-屬性的二元關(guān)系構(gòu)造的，形式背景中的屬性是時(shí)刻變化的，為使概念格能反映屬性變化后的數(shù)據(jù)規(guī)律進(jìn)而提取新的規(guī)則，提出了區(qū)間概念格的縱向維護(hù)算法。算法在分析了區(qū)間概念格的概念外延特點(diǎn)及結(jié)構(gòu)特征后，給出了區(qū)間概念格在增加屬性、刪除屬性兩種情況下的維護(hù)算法，進(jìn)而通過算法分析表明了維護(hù)較重構(gòu)在時(shí)間與空間上的高效性，最終用實(shí)例表明了維護(hù)算法的可行性。

關(guān)鍵詞：區(qū)間概念格；縱向維護(hù)；對(duì)象-屬性；形式背景

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A

doi:10.3969/j.issn.1007-130X.2015.06.028

收稿日期：*2014-02-17;修回日期：2014-05-19

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61370168,61472340)；河北省科技廳條件建設(shè)項(xiàng)目(14960112D)

作者簡介:

通信地址：063009 河北省唐山市華北理工大學(xué)理學(xué)院

Address:College of Science,North China University of Science and Technology,Tangshan 063009,Hebei,P.R.China

Longitudinal maintenance theory and algorithm for interval concept lattice

ZHANG Chun-ying，WANG Li-ya,LIU Bao-xiang

(College of Science,North China University of Science and Technology,Tangshan 063009,China)

Abstract:Interval concept lattice is the only lattice structure that can directly reflect the object sets that contain a certain number or percentage of properties in intension. A concept lattice is constructed based on the binary relation between objects and attributes. The attributes of formal context are changing all the time. We propose a longitudinal maintenance algorithm for interval concept lattice to reflect the regularity of the changing attributes and then extract some new rules. We also propose a maintenance algorithm for interval concept lattice under two situations: adding properties and deleting properties. Algorithm analysis demonstrates the higher spatio-temporal efficiency of maintenance than reconstruction, and the feasibility of the algorithm.

Key words:interval concept lattice;longitudinal maintenance;object-attribute; formal context

1引言

概念格理論是由Wille R教授[1]于1982年提出的,在知識(shí)管理、信息檢索、軟件工程等方面都有廣泛的應(yīng)用[2,3]。區(qū)間概念格是定義在參數(shù)區(qū)間上的格結(jié)構(gòu)，其概念外延是區(qū)間范圍內(nèi)滿足內(nèi)涵屬性的對(duì)象集。文獻(xiàn)[4,5]分別給出了其定義、性質(zhì)及構(gòu)造算法。

區(qū)間概念格是基于某已知的形式背景，根據(jù)數(shù)據(jù)的二元關(guān)系構(gòu)造的。形式背景的數(shù)據(jù)每時(shí)每刻都可能發(fā)生變化；如在醫(yī)學(xué)診斷系統(tǒng)中，病人的增加會(huì)引起對(duì)象的增加，同一疾病的影響因素的變化會(huì)引起屬性的變化，如果每次都進(jìn)行概念格的重新生成，將浪費(fèi)大量的人力物力，這樣也就引出了對(duì)概念格的維護(hù)問題。當(dāng)形式背景中的屬性發(fā)生變化時(shí)，必然會(huì)引起區(qū)間概念格結(jié)構(gòu)的變化。區(qū)間概念格中概念外延是滿足一定比例內(nèi)涵屬性的對(duì)象集，所以當(dāng)數(shù)據(jù)變化時(shí)概念的更新、邊的更新、概念的增減要比其他的概念格更復(fù)雜。當(dāng)屬性發(fā)生變化時(shí)，重新構(gòu)造概念格會(huì)浪費(fèi)很多時(shí)間和精力，如何調(diào)整已有的區(qū)間概念格結(jié)構(gòu)而不必重新構(gòu)造？

針對(duì)上述情況，本文分別對(duì)區(qū)間概念格中增加屬性、刪除屬性兩種情況下的縱向維護(hù)進(jìn)行了算法設(shè)計(jì)。算法在保證區(qū)間概念格完備性的前提下實(shí)現(xiàn)了對(duì)格結(jié)構(gòu)的維護(hù)。文中還對(duì)算法從時(shí)間和空間兩個(gè)方面進(jìn)行了分析，最后通過實(shí)例驗(yàn)證了算法的可行性與高效性。

2相關(guān)工作

區(qū)間概念格是在粗糙概念格基礎(chǔ)上進(jìn)行的擴(kuò)展，其定義在參數(shù)區(qū)間[α,β](0≤α≤β≤1)上，概念外延是滿足內(nèi)涵中區(qū)間范圍內(nèi)屬性的對(duì)象集。區(qū)間概念格在特定條件下可以退化為經(jīng)典概念格與粗糙概念格。

定義1[1]對(duì)于形式背景(U,A,R)，算子f、g定義為：

?x∈U，f(x)={y|?y∈A,xRy}，即f是對(duì)象x與其具有的所有屬性的映射；

?y∈A，g(y)={x|?x∈U,xRy}，即g是屬性y與其覆蓋的所有對(duì)象的映射。

(1)

(2)

其中，X是經(jīng)典概念的外延，Y是概念的內(nèi)涵，f是定義1中的算子。|Y|是集合Y中包含的元素個(gè)數(shù)，即基數(shù)。Mα表示可能被Y中至少α×|Y|個(gè)內(nèi)涵屬性覆蓋的對(duì)象，Mβ表示可能被Y中至少β×|Y|個(gè)內(nèi)涵屬性所覆蓋的對(duì)象。

定義3[4]設(shè)形式背景(U,A,R)，三元序偶(Mα,Mβ,Y)稱為區(qū)間概念。

概念格是形式概念分析的核心數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)形式背景建立。格結(jié)構(gòu)的生成是進(jìn)行數(shù)據(jù)分析、關(guān)聯(lián)分析和挖掘關(guān)聯(lián)規(guī)則的前提。文獻(xiàn)[5]提出了區(qū)間概念格的生成算法，其設(shè)定每個(gè)結(jié)點(diǎn)為六元組:

(Mα,Mβ,Y,Parent,Children,No)

形式背景是根據(jù)現(xiàn)實(shí)世界中的數(shù)據(jù)構(gòu)建的。隨著時(shí)間的推移，數(shù)據(jù)是時(shí)刻變化的，所以概念格的維護(hù)、更新是將概念格進(jìn)行應(yīng)用與推廣的關(guān)鍵問題。Sun Ling-yu等人[6]提出的模糊概念格的構(gòu)建算法是基于增加屬性和對(duì)象的，所以可將其應(yīng)用到增加屬性和對(duì)象的維護(hù)中；文獻(xiàn)[7,8]分別提出了屬性刪減時(shí)約簡概念格的維護(hù)算法和對(duì)象刪除時(shí)擴(kuò)展概念格的維護(hù)；文獻(xiàn)[9]討論的是增加屬性或?qū)ο髸r(shí)的增量維護(hù)；文獻(xiàn)[10]將屬性鏈表應(yīng)用于概念格的維護(hù)中，加速了維護(hù)過程。國內(nèi)還有學(xué)者提出了在概念格維護(hù)過程中，其結(jié)構(gòu)變化、產(chǎn)生概念種類等問題的判定方法和判定定理[11～14]。

與經(jīng)典概念格相比，區(qū)間概念格的結(jié)構(gòu)更為復(fù)雜，且其父子概念的性質(zhì)與經(jīng)典概念格差異較大，無法直接將經(jīng)典概念格的維護(hù)算法直接應(yīng)用于區(qū)間概念格的維護(hù)中。區(qū)間概念格中概念外延是滿足內(nèi)涵中一定比例屬性的對(duì)象集，當(dāng)屬性變化時(shí)引起的更新與概念的增加要比其他的概念格復(fù)雜。所以，提出適用于區(qū)間概念格的維護(hù)算法具有很大的實(shí)際意義。

3區(qū)間概念格的縱向維護(hù)原理與算法

3.1縱向維護(hù)原理

概念格的縱向維護(hù)是指增加或刪除屬性時(shí)的維護(hù)。在區(qū)間概念格的縱向維護(hù)中，屬性的增加與刪減必然會(huì)引起概念格結(jié)構(gòu)的變化(此處考慮的屬性是指格中對(duì)象具有的屬性)。

根據(jù)格節(jié)點(diǎn)的變化特征，將概念分為如下幾種：

定義8新增概念:增加對(duì)象(屬性)后，產(chǎn)生的新概念。

定義9刪除概念:概念外延僅由刪除對(duì)象x構(gòu)成。

定義10冗余概念:增加(刪除)對(duì)象(屬性)后，概念外延和父概念外延相同，應(yīng)與父概念合二為一。

定義11無關(guān)屬性：如果概念G的內(nèi)涵中不包含屬性a，則稱屬性a是概念G的無關(guān)屬性。此時(shí)刪除屬性a，概念G不變。

定義12可缺屬性：如果概念G的內(nèi)涵中除了包含a之外，還有其他屬性，則稱a是概念G的可缺屬性。

定義13不可缺屬性：如果概念G的內(nèi)涵中只包含a，則稱a是概念G的不可缺屬性。

性質(zhì)3在區(qū)間概念格中刪除屬性a，如果a?Y，則a是G的無關(guān)屬性，對(duì)應(yīng)的概念G為不變概念。

性質(zhì)4在區(qū)間概念格中刪除屬性a，當(dāng)概念G滿足下列情況之一時(shí)，G為刪除概念。

(1) a∈Y且Y-{a}=?，則a是G的不可缺屬性，節(jié)點(diǎn)G必須刪除，并調(diào)整子概念與父概念的邊。

(2) a∈Y且Y-{a}≠?，則a是G的可缺屬性，此時(shí)當(dāng)Y-{a}與G的某一個(gè)子概念的內(nèi)涵相同，此時(shí)刪除此概念。

性質(zhì)5在區(qū)間概念格中刪除屬性a，當(dāng)a∈Y，Y-{a}≠?，而且Y-{a}與G的任何子概念的內(nèi)涵都不相同，那么將G更新為G′=(Mα′,Mβ′,Y-{a})。

3.2縱向維護(hù)算法

{YG=YGnew}

}

For each B∈P(A∪{a}) /*由原始概念格中的冗余概念產(chǎn)生的新增概念的內(nèi)涵*/

{ YG=YGnew}

}

Figure 1　L β α(U,A,R) 圖1　L β α(U,A,R)

(1)從概念格的底層逐層向上搜索，當(dāng)?shù)降趇層時(shí)，第一次出現(xiàn)內(nèi)涵中有屬性a的概念；之后，尋找到第i層中所有內(nèi)涵中有屬性a的概念，轉(zhuǎn)第(2)步；

(2)對(duì)具有屬性a的概念進(jìn)行維護(hù)，部分代碼如下：

If (Y-{a}=?)

Delete G；//根據(jù)性質(zhì)4(1)得到的刪除概念

If (Y-{a}≠? and YG.children=Y-{a})

Delete G； //根據(jù)性質(zhì)4(2)得到的刪除概念

If (Y-{a}≠? and YG.children≠Y-{a})

G=Mα′,Mβ′,Y-{a}； //性質(zhì)4(1)得刪除概念

(3)掃描第(2)步中維護(hù)過的概念的父概念，并轉(zhuǎn)到第(2)步。

4實(shí)例驗(yàn)證

有如表1所示的形式背景，設(shè)定α=0.5，β=0.6。

Table 1　Formal context

Figure 2　L β α(U,A∪{a},R) 圖2　L β α(U,A∪{a},R)

5結(jié)束語

區(qū)間概念格中概念外延是滿足一定比例內(nèi)涵屬性的對(duì)象集，所以數(shù)據(jù)變化時(shí)，格結(jié)構(gòu)的更新與變化情況比經(jīng)典概念格及其它概念格復(fù)雜，且其它概念格的維護(hù)方法不能直接應(yīng)用到區(qū)間概念中。本文首先分析了增刪屬性產(chǎn)生的五種概念在維護(hù)過程中的調(diào)整方法；并在此基礎(chǔ)上，設(shè)計(jì)了區(qū)間概念格的縱向維護(hù)算法；最后通過實(shí)例驗(yàn)證了其可行性與實(shí)用性。下一步的工作主要集中在對(duì)區(qū)間概念格的約簡、區(qū)間[α,β]的變化對(duì)概念格結(jié)構(gòu)的影響、基于區(qū)間概念格的關(guān)聯(lián)規(guī)則提取及應(yīng)用等。

參考文獻(xiàn):

[1]WilleR.Restructuringlatticetheory:Anapproachbasedonhierarchiesofconcepts[J].NATOAdvancedStudySeries, 1982,83:445-470.

[2]KourieDG,ObiedkovS,WatsonBW,etal.Anincrementalalgorithmtoconstructalatticeofsetintersections[J].ScienceofComputerProgramming, 2009, 74(3):128-142.

[3]ColeR,StummeG.CEM-Aconceptualemailmanager[C]//Procofthe7thInternationalConferenceonConceptualStructures(ICCS’2000), 2000:438-452.

[4]LiuBao-xiang,ZhangChun-ying.Newconceptlatticestructure—intervalconceptlattice[J].ComputerScience, 2012,39(8):273-277.(inChinese)

[6]SunLing-yu,LengMing.Aneffectiveincrementalfuzzyconceptlatticeformationalgorithmbasedonalternateattributeandobject[J].JournalofInformationandComputationalScience,2010,7(5):1023-1030.

[7]WuGang,JianSong-quan,HuXue-gang,etal.Maintenanceofextendedconceptlattice[J].ComputerEngineeringandAapplication, 2002,38(4):76-78.(inChinese)

[8]ZhaoWen-bing,JianSong-quan,JiangMei-hua,etal.Longitudinalmaintenancealgorithmofreducedconceptlattice[J].ComputerEngineeringandApplication, 2002,38(7):209-211.(inChinese)

[9]TuLi,ChenLing,LiYun.Attribute-basedalgorithmforconstructingandmaintenanceofconceptlattice[J].JournalofComputerApplications, 2004,24(10):116-118.(inChinese)

[10]ZhangChun-ying,LiuBao-xiang,GuoJing-feng.Longitudinalandtransversemaintenancealgorithmofconceptlatticebasedonattributelinked-list[J].ComputerEngineeringandApplication,2004,40(5):185-187.(inChinese)

[11]LiuNa,HeFeng.Incrementalalgorithmofmaintainingconceptlattice[J].ComputerandModernization,2010(11):16-23.(inChinese)

[12]ShaoMing-wen,WuXi-wen,GuoLi.Therelationshipbetweendatachangeandconceptlatticestructure[J].ChineseJournalofEngineeringMathematics,2012,29(4):529-539.(inChinese)

[13]ZhiHui-lai,ZhiDong-jie.Theoryandalgorithmofconceptlatticemaintenance[J].ComputerEngineeringandApplication, 2014,50(6):96-101.(inChinese)

[14]ZhangLei,ZhangHong-li,YinLi-hua,etal.Theoryandalgorithmsofattributedecrementforconceptlattice[J].JournalofComputerResearchandDevelopment,2013,50(2):248-259.(inChinese)

參考文獻(xiàn)：附中文

[4]劉保相,張春英.一種新的概念格結(jié)構(gòu)——區(qū)間概念格[J].計(jì)算機(jī)科學(xué),2012,39(8):273-277.

[7]吳剛,簡宋全,胡學(xué)鋼，等.擴(kuò)展概念格的維護(hù)[J].計(jì)算機(jī)工程與應(yīng)用,2002,38(4):76-78.

[8]趙文兵,簡宋全,蔣美華,等.約簡概念格的縱向維護(hù)算法[J].計(jì)算機(jī)工程與應(yīng)用,2002,38(7):209-211.

[9]屠莉,陳崚,李云.一種基于屬性的概念格生成及維護(hù)算法[J].計(jì)算機(jī)應(yīng)用,2004,24(10):116-118.

[10]張春英,劉保相,郭景峰.基于屬性鏈表的概念格的縱橫向維護(hù)算法[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(5):185-187.

[11]劉娜,何豐.概念格的漸進(jìn)式維護(hù)算法[J].計(jì)算機(jī)與現(xiàn)代化,2010(11):16-23.

[12]邵明文,伍席文,郭理.數(shù)據(jù)變化與概念格結(jié)構(gòu)的關(guān)系[J].工程數(shù)學(xué)學(xué)報(bào),2012,29(4):529-539.

[13]智慧來,智東杰.概念格維護(hù)原理與算法[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(6):96-101.

[14]張磊,張宏莉,殷麗華,等.概念格的屬性漸減原理與算法研究[J].計(jì)算機(jī)研究與發(fā)展,2013,50(2):248-259.

張春英(1969-),女,河北唐山人，博士，教授，CCF會(huì)員(E200013476M)，研究方向?yàn)閿?shù)據(jù)挖掘、概念格和社會(huì)網(wǎng)絡(luò)分析。E-mail:zchunying@heuu.edu.cn

ZHANGChun-ying,bornin1969,PhD,professor,CCFmember(E200013476M)，herresearchinterestsincludedatamining,conceptlattice,andsocialnetworkanalysis.

王立亞(1987-),女,河北唐山人，碩士生，研究方向?yàn)閰^(qū)間概念格與數(shù)據(jù)挖掘。E-mail:wang_liya@126.com

WANGLi-ya,bornin1987,MScandidate,herresearchinterestsincludeintervalconceptlattice,anddatamining.

劉保相(1957-),男，河北衡水人，教授，研究方向?yàn)楦拍罡?、?shù)據(jù)挖掘和模糊控制。E-mail:liubx5888@126.com

LIUBao-xiang,bornin1957,professor,hisresearchinterestsincludeconceptlattice,datamining,andfuzzycontrol.