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

張春英，王立亞,劉保相

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

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

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

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

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

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

基金項目：國家自然科學(xué)基金資助項目(61370168,61472340)；河北省科技廳條件建設(shè)項目(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年提出的,在知識管理、信息檢索、軟件工程等方面都有廣泛的應(yīng)用[2,3]。區(qū)間概念格是定義在參數(shù)區(qū)間上的格結(jié)構(gòu)，其概念外延是區(qū)間范圍內(nèi)滿足內(nèi)涵屬性的對象集。文獻[4,5]分別給出了其定義、性質(zhì)及構(gòu)造算法。

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

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

2相關(guān)工作

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

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

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

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

(1)

(2)

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

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

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

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

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

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

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

3.1縱向維護原理

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

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

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

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

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

定義11無關(guān)屬性：如果概念G的內(nèi)涵中不包含屬性a，則稱屬性a是概念G的無關(guān)屬性。此時刪除屬性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)屬性，對應(yīng)的概念G為不變概念。

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

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

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

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

3.2縱向維護算法

{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ù)降趇層時，第一次出現(xiàn)內(nèi)涵中有屬性a的概念；之后，尋找到第i層中所有內(nèi)涵中有屬性a的概念，轉(zhuǎn)第(2)步；

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

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)步中維護過的概念的父概念，并轉(zhuǎn)到第(2)步。

4實例驗證

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

參考文獻:

[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)

參考文獻：附中文

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

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

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

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

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

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

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

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

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

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

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

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

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

劉保相(1957-),男，河北衡水人，教授，研究方向為概念格、數(shù)據(jù)挖掘和模糊控制。E-mail:liubx5888@126.com

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