一種改進的區間概念格漸進式生成算法

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

摘 要 在區間概念格的漸進式生成算法中，由于部分概念的缺失導致多區間概念格的合并過程難以進行。針對這個問題，將區間概念分為存在概念、冗余概念和空概念，進而提出了一種新的區間概念格漸進式生成算法。該算法保證了格結構的完整性，為區間概念格的結構合并與優化奠定了基礎。

【關鍵詞】區間概念格 漸進式生成算法

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