區間概念格的縱向維護原理與算法

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

張春英，王立亞,劉保相

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

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

關鍵詞：區間概念格；縱向維護；對象-屬性；形式背景

中圖分類號：TP301.6 文獻標志碼：A

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

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

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

作者簡介:

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

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年提出的,在知識管理、信息檢索、軟件工程等方面都有廣泛的應用[2,3]。區間概念格是定義在參數區間上的格結構，其概念外延是區間范圍內滿足內涵屬性的對象集。文獻[4,5]分別給出了其定義、性質及構造算法。

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

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

2相關工作

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

定義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是經典概念的外延，Y是概念的內涵，f是定義1中的算子。|Y|是集合Y中包含的元素個數，即基數。Mα表示可能被Y中至少α×|Y|個內涵屬性覆蓋的對象，Mβ表示可能被Y中至少β×|Y|個內涵屬性所覆蓋的對象。

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

概念格是形式概念分析的核心數據結構，可以根據形式背景建立。格結構的生成是進行數據分析、關聯分析和挖掘關聯規則的前提。文獻[5]提出了區間概念格的生成算法，其設定每個結點為六元組:

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

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

與經典概念格相比，區間概念格的結構更為復雜，且其父子概念的性質與經典概念格差異較大，無法直接將經典概念格的維護算法直接應用于區間概念格的維護中。區間概念格中概念外延是滿足內涵中一定比例屬性的對象集，當屬性變化時引起的更新與概念的增加要比其他的概念格復雜。所以，提出適用于區間概念格的維護算法具有很大的實際意義。

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

3.1縱向維護原理

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

根據格節點的變化特征，將概念分為如下幾種：

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

定義9刪除概念:概念外延僅由刪除對象x構成。

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

定義11無關屬性：如果概念G的內涵中不包含屬性a，則稱屬性a是概念G的無關屬性。此時刪除屬性a，概念G不變。

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

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

性質3在區間概念格中刪除屬性a，如果a?Y，則a是G的無關屬性，對應的概念G為不變概念。

性質4在區間概念格中刪除屬性a，當概念G滿足下列情況之一時，G為刪除概念。

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

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

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

3.2縱向維護算法

{YG=YGnew}

}

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

{ YG=YGnew}

}

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

(1)從概念格的底層逐層向上搜索，當到第i層時，第一次出現內涵中有屬性a的概念；之后，尋找到第i層中所有內涵中有屬性a的概念，轉第(2)步；

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

If (Y-{a}=?)

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

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

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

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

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

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

4實例驗證

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

Table 1　Formal context

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

5結束語

區間概念格中概念外延是滿足一定比例內涵屬性的對象集，所以數據變化時，格結構的更新與變化情況比經典概念格及其它概念格復雜，且其它概念格的維護方法不能直接應用到區間概念中。本文首先分析了增刪屬性產生的五種概念在維護過程中的調整方法；并在此基礎上，設計了區間概念格的縱向維護算法；最后通過實例驗證了其可行性與實用性。下一步的工作主要集中在對區間概念格的約簡、區間[α,β]的變化對概念格結構的影響、基于區間概念格的關聯規則提取及應用等。

參考文獻:

[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]劉保相,張春英.一種新的概念格結構——區間概念格[J].計算機科學,2012,39(8):273-277.

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

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

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

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

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

[12]邵明文,伍席文,郭理.數據變化與概念格結構的關系[J].工程數學學報,2012,29(4):529-539.

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

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

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

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

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

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

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

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