区间概念格的纵向维护原理与算法

2016-01-08张春英,王立亚,刘保相

计算机工程与科学 2015年6期

区间概念格的纵向维护原理与算法*

张春英，王立亚,刘保相

(华北理工大学理学院，河北唐山 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.