一種改進(jìn)的區(qū)間概念格漸進(jìn)式生成算法

張茹++劉保相++王立亞

摘 要 在區(qū)間概念格的漸進(jìn)式生成算法中，由于部分概念的缺失導(dǎo)致多區(qū)間概念格的合并過(guò)程難以進(jìn)行。針對(duì)這個(gè)問(wèn)題，將區(qū)間概念分為存在概念、冗余概念和空概念，進(jìn)而提出了一種新的區(qū)間概念格漸進(jìn)式生成算法。該算法保證了格結(jié)構(gòu)的完整性，為區(qū)間概念格的結(jié)構(gòu)合并與優(yōu)化奠定了基礎(chǔ)。

【關(guān)鍵詞】區(qū)間概念格 漸進(jìn)式生成算法

1 引言

區(qū)間概念格是具備一定數(shù)量或比例的內(nèi)涵中屬性的對(duì)象集合構(gòu)成的格結(jié)構(gòu)。目前，區(qū)間概念格大多采用漸進(jìn)式的生成方法。由形式背景計(jì)算所有屬性構(gòu)成的集合的冪集P（A），將冪集中的每個(gè)元素Y作為內(nèi)涵，按照內(nèi)涵基數(shù)由小到大的順序依次生成初始的結(jié)點(diǎn)集G，并設(shè)定每個(gè)概念節(jié)點(diǎn)用六元組形式表示；掃描每個(gè)對(duì)象的內(nèi)涵，將內(nèi)涵中滿足條件且的對(duì)象并入G的上界外延中，滿足條件且的對(duì)象并入G的β下界外延Mβ中；構(gòu)造出根結(jié)點(diǎn)和末梢結(jié)點(diǎn)，將其他結(jié)點(diǎn)以新增結(jié)點(diǎn)的形式漸進(jìn)式地插入到格中，此過(guò)程中刪除冗余概念和上下界外延為空的概念，進(jìn)而構(gòu)成區(qū)間概念格結(jié)構(gòu)。此算法生成的區(qū)間概念格結(jié)構(gòu)中只保留了部分概念節(jié)點(diǎn)，然而進(jìn)一步的實(shí)現(xiàn)數(shù)據(jù)匯總及關(guān)聯(lián)規(guī)則挖掘等應(yīng)用是針對(duì)全體區(qū)間概念而言的。因此，現(xiàn)有區(qū)間概念格的漸進(jìn)式生成算法不滿足現(xiàn)實(shí)需要，為此，本文對(duì)算法進(jìn)行改進(jìn)，實(shí)現(xiàn)全體概念快速有效的生成并分類存儲(chǔ)。

2 基本概念

定義1對(duì)于形式背景（U，A，R），設(shè)有區(qū)間 ，α上界外延Mα：

β下界外延Mβ：

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

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

定義3用Lβα（U，A，R）表示形式背景（U，A，R）的全體[α，β]區(qū)間概念，記：

，則“≤”是Lβα（U，A，R）上的偏序關(guān)系。

定義4用Lβα（U，A，R）表示形式背景（U，A，R）的全體[α，β]區(qū)間概念，若Lβα（U，A，R）中的所有概念滿足“≤”偏序關(guān)系，則稱Lβα（U，A，R）是形式背景（U，A，R）的區(qū)間概念格。

3 改進(jìn)的漸進(jìn)式生成算法

3.1 基本原理

為了在生成區(qū)間概念格的同時(shí)保留所有區(qū)間概念，根據(jù)區(qū)間概念的存在形式將全體概念進(jìn)行分類，具體分類情況如下：

定義4 設(shè)在形式背景（U，A，R）中有兩個(gè)區(qū)間概念G1=（Mα1，Mβ1，Y1）和G2=（Mα2，Mβ2，Y2），若，，且時(shí)，則稱（Mα1，Mβ1，Y1）為冗余概念。

定義5 設(shè)在形式背景（U，A，R）中有區(qū)間概念（Mα，Mβ，Y），當(dāng)且時(shí)，稱（Mα，Mβ，Y）為空概念。

定義6 設(shè)在形式背景（U，A，R）中有區(qū)間概念C=（Mα，Mβ，Y），此概念既不是冗余概念也不是空概念，則稱存在概念。全體存在概念的集合記為L(zhǎng)βα（U，A，R）。

定義7 用Lβα（U，A，R）表示形式背景的全體[α，β]區(qū)間概念，即包括：存在概念、冗余概念和空概念。記：

，則“≤”是上的偏序關(guān)系。

3.2 算法設(shè)計(jì)

為了區(qū)分不同的區(qū)間概念，定義概念節(jié)點(diǎn)以結(jié)構(gòu)體方式進(jìn)行存儲(chǔ)，表示形式如下：

定義形式為：

Struct concept

{

String Mαi，Mβi，Yi；

Struct Y， parent， children；

Int flag；

}

其中，flag根據(jù)概念所屬類別進(jìn)行標(biāo)記。

當(dāng)flag=1時(shí)，存儲(chǔ)概念為存在概念；

當(dāng)flag=2時(shí)，存儲(chǔ)概念為的冗余概念；

當(dāng)flag=3時(shí)，存儲(chǔ)概念為空概念。

算法：Improved ICAICL

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

輸出：區(qū)間概念格Lβα和

（1）計(jì)算屬性集合冪集P（A）確定概念的內(nèi)涵，生成初始化的概念節(jié)點(diǎn)集G。

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

（3）對(duì)節(jié)點(diǎn)集合G，按照偏序關(guān)系確定節(jié)點(diǎn)的層次及父子關(guān)系，找出冗余概念，將其Flag置為2。

其中找出冗余概念的方法見函數(shù)Romove-redun（Ch，Gi）.

Remove-redun（Ch，Gi） //找出冗余概念，標(biāo)記存儲(chǔ)，并從Lβα中刪除

{ for each children Ch in Gi //Ch指針指向Gi每個(gè)孩子

{

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

{ Flag=2

Delete Gi from Lβα

}

}

}

（4）對(duì)no=1的概念，構(gòu)造出根節(jié)點(diǎn)；然后按No的值逐次將其他節(jié)點(diǎn)按照父子關(guān)系插入到格中，最終形成區(qū)間概念格結(jié)構(gòu)。

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

已知形式背景如表1。設(shè)α=0.6，β=0.7，形成的區(qū)間概念見表2。用Improved ICAICL形成格結(jié)構(gòu)，見圖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：形式背景對(duì)應(yīng)的區(qū)間概念

名稱 區(qū)間概念 名稱 區(qū)間概念

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）

參考文獻(xiàn)

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

作者單位

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