一种改进的区间概念格渐进式生成算法

张茹++刘保相++王立亚

摘 要 在区间概念格的渐进式生成算法中，由于部分概念的缺失导致多区间概念格的合并过程难以进行。针对这个问题，将区间概念分为存在概念、冗余概念和空概念，进而提出了一种新的区间概念格渐进式生成算法。该算法保证了格结构的完整性，为区间概念格的结构合并与优化奠定了基础。

【关键词】区间概念格 渐进式生成算法

1 引言

區间概念格是具备一定数量或比例的内涵中属性的对象集合构成的格结构。目前，区间概念格大多采用渐进式的生成方法。由形式背景计算所有属性构成的集合的幂集P（A），将幂集中的每个元素Y作为内涵，按照内涵基数由小到大的顺序依次生成初始的结点集G，并设定每个概念节点用六元组形式表示；扫描每个对象的内涵，将内涵中满足条件且的对象并入G的上界外延中，满足条件且的对象并入G的β下界外延Mβ中；构造出根结点和末梢结点，将其他结点以新增结点的形式渐进式地插入到格中，此过程中删除冗余概念和上下界外延为空的概念，进而构成区间概念格结构。此算法生成的区间概念格结构中只保留了部分概念节点，然而进一步的实现数据汇总及关联规则挖掘等应用是针对全体区间概念而言的。因此，现有区间概念格的渐进式生成算法不满足现实需要，为此，本文对算法进行改进，实现全体概念快速有效的生成并分类存储。

2 基本概念

定义1对于形式背景（U，A，R），设有区间 ，α上界外延Mα：

β下界外延Mβ：

X是经典概念外延，Y是概念的内涵。|Y|是集合Y中包含元素个数。Mα表示可能被Y 中至少α×|Y|个内涵属性覆盖的对象。 表示可能被Mβ中至少β×|Y|个内涵属性所覆盖的对象。

定义2设形式背景（U，A，R），三元序偶（Mα，Mβ，Y）称为区间概念。

定义3用Lβα（U，A，R）表示形式背景（U，A，R）的全体[α，β]区间概念，记：

，则“≤”是Lβα（U，A，R）上的偏序关系。

定义4用Lβα（U，A，R）表示形式背景（U，A，R）的全体[α，β]区间概念，若Lβα（U，A，R）中的所有概念满足“≤”偏序关系，则称Lβα（U，A，R）是形式背景（U，A，R）的区间概念格。

3 改进的渐进式生成算法

3.1 基本原理

为了在生成区间概念格的同时保留所有区间概念，根据区间概念的存在形式将全体概念进行分类，具体分类情况如下：

定义4 设在形式背景（U，A，R）中有两个区间概念G1=（Mα1，Mβ1，Y1）和G2=（Mα2，Mβ2，Y2），若，，且时，则称（Mα1，Mβ1，Y1）为冗余概念。

定义5 设在形式背景（U，A，R）中有区间概念（Mα，Mβ，Y），当且时，称（Mα，Mβ，Y）为空概念。

定义6 设在形式背景（U，A，R）中有区间概念C=（Mα，Mβ，Y），此概念既不是冗余概念也不是空概念，则称存在概念。全体存在概念的集合记为Lβα（U，A，R）。

定义7 用Lβα（U，A，R）表示形式背景的全体[α，β]区间概念，即包括：存在概念、冗余概念和空概念。记：

，则“≤”是上的偏序关系。

3.2 算法设计

为了区分不同的区间概念，定义概念节点以结构体方式进行存储，表示形式如下：

定义形式为：

Struct concept

{

String Mαi，Mβi，Yi；

Struct Y， parent， children；

Int flag；

}

其中，flag根据概念所属类别进行标记。

当flag=1时，存储概念为存在概念；

当flag=2时，存储概念为的冗余概念；

当flag=3时，存储概念为空概念。

算法：Improved ICAICL

输入：形式背景（U，A，R）

输出：区间概念格Lβα和

（1）计算属性集合幂集P（A）确定概念的内涵，生成初始化的概念节点集G。

（2）确定α上界外延Mαi和β下界外延Mβi，将空概念的Flag置为3，其它概念均置为1。

（3）对节点集合G，按照偏序关系确定节点的层次及父子关系，找出冗余概念，将其Flag置为2。

其中找出冗余概念的方法见函数Romove-redun（Ch，Gi）.

Remove-redun（Ch，Gi） //找出冗余概念，标记存储，并从Lβα中删除

{ for each children Ch in Gi //Ch指针指向Gi每个孩子

{

If （Gi. Mαi= Ch. Mαi， Gi. Mβi= Ch. Mβi）

{ Flag=2

Delete Gi from Lβα

}

}

}

（4）对no=1的概念，构造出根节点；然后按No的值逐次将其他节点按照父子关系插入到格中，最终形成区间概念格结构。

4 实例验证

已知形式背景如表1。设α=0.6，β=0.7，形成的区间概念见表2。用Improved ICAICL形成格结构，见图1。

表1：Lβα（U，A，R）的形式背景

a b c d

1 1 1 0 0

2 0 0 1 0

3 1 0 1 1

表2：形式背景对应的区间概念

名称 区间概念 名称 区间概念

C0 （1，123，123， φ，φ，2 3 4 5，1） C8 （3，φ，φ，bc，3 4，12 15，9）

C1 （1，13，13，a，1，6 7 8，2） C9 （3，φ，φ，bd，3 5，13 15，10）

C2 （2，1，1，b，1，6 9 10，3） C10 （2，3，3，cd，4 5，14 15，11）

C3 （1，23， 23，c，1，7 9 11，4） C11 （1，13， φ，abc，6 7 9，16，12）

C4 （2，3，3，d，1，8 10 11，5） C12 （1，13， φ，abd，6 8 10，16，13）

C5 （1，1，1，ab，2 3，12 13，6） C13 （2，3，3，acd，7 8 11，16，14）

C6 （2，3，3，ac，2 4，12 14，7） C14 （1，3， φ，bcd，9 10 11，16，15）

C7 （2，3，3，ad，2 5，13 14，8） C15 （1，3， 3，abcd，12 13 14 15， φ，16）

参考文献

[1]刘保相，张春英.一种新的概念格结构——区间概念格[J].计算机科学，2012，39（08）：273-277.

作者单位

华北理工大学理学院 河北省唐山市 063009