李克文， 呂萌萌， 邵明文

(中國(guó)石油大學(xué)(華東)計(jì)算機(jī)與通信工程學(xué)院，青島 266580)

1 引言

德國(guó)Wille 教授于1982 年提出形式概念分析理論(Formal Concept Analysis， 簡(jiǎn)記為FCA)[1]，用于形式概念(外延(對(duì)象的集合)和內(nèi)涵(屬性的集合)組成的二元組)的發(fā)現(xiàn)、排序和顯示，其核心數(shù)據(jù)結(jié)構(gòu)是概念格結(jié)構(gòu)模型.概念格是知識(shí)表現(xiàn)的一種模型，依據(jù)知識(shí)在內(nèi)涵和外延上的依賴或因果關(guān)系建立概念層次結(jié)構(gòu)，生動(dòng)簡(jiǎn)潔地體現(xiàn)了概念之間的泛化和特化關(guān)系[2-4].形式概念分析是數(shù)據(jù)分析和知識(shí)處理有力的形式化工具，目前已成功應(yīng)用于數(shù)據(jù)挖掘[5-7]、軟件工程[8]等領(lǐng)域.

粒計(jì)算[9，10]起源于人工智能、粗糙集、商空間、概念格、模糊集等領(lǐng)域，通過構(gòu)造和處理信息粒度，將復(fù)雜問題劃分為一系列更容易處理的、更小的子問題，從而降低全局計(jì)算代價(jià)，進(jìn)而從更高層次上對(duì)結(jié)果進(jìn)行綜合分析.Zadeh[11]于1979 年首次提出模糊信息粒后，在模糊集的基礎(chǔ)上提出了粒計(jì)算的基本框架并強(qiáng)調(diào)粒度及其在推理中的重要性.近年來，粒計(jì)算已廣泛應(yīng)用于數(shù)據(jù)挖掘、模式識(shí)別與智能控制、復(fù)雜問題求解等諸多領(lǐng)域[12-16]，及當(dāng)下較為前沿的研究熱點(diǎn)，如時(shí)空、空間研究領(lǐng)域[17-19].

目前，已有許多專家學(xué)者對(duì)粒計(jì)算及相關(guān)領(lǐng)域進(jìn)行了系統(tǒng)的研究，Yao[20-24]討論了粒度的綜合水平和粒計(jì)算理論.作為粒計(jì)算的模型之一，粗糙集理論[25]通過屬性集合對(duì)論域進(jìn)行目標(biāo)概念的刻畫，進(jìn)行屬性約簡(jiǎn)[26]、規(guī)則提取[27]與問題決策[28]等.Qian 等[29]基于多個(gè)粒結(jié)構(gòu)提出了多粒度粗糙集模型，推廣了粒計(jì)算的單粒度粗糙集模型，有助于獲得信息系統(tǒng)的最滿意決策或問題求解，充分體現(xiàn)了粒計(jì)算方法的豐富性和靈活性.Gu 等[30]研究了多粒度標(biāo)記信息系統(tǒng)中的知識(shí)近似問題.Wu 和Leung[31]對(duì)多粒度決策表中的粒度標(biāo)記塊理論和應(yīng)用進(jìn)行了研究.基于多粒度標(biāo)記信息系統(tǒng)對(duì)最優(yōu)粒度的選擇在文獻(xiàn)[31-37]中進(jìn)行了研究.基于多粒度粗糙集模型，Xu 等[38]研究了廣義多粒度粗糙集以及最優(yōu)粒度的選擇問題.由此可知，粒計(jì)算領(lǐng)域的研究熱點(diǎn)已經(jīng)由單粒度問題過渡到更具有現(xiàn)實(shí)意義的多粒度問題.

概念格和粒計(jì)算的方法論在本質(zhì)上具有相似之處，兩種理論的結(jié)合研究已經(jīng)引起了眾多學(xué)者的關(guān)注.Du 等[39]對(duì)概念格與粒度劃分的相關(guān)性進(jìn)行了研究，分析了概念格與論域中的劃分關(guān)系在概念描述與概念層次之間轉(zhuǎn)換的關(guān)系.Belohlavek 和Sklenar[40]對(duì)形式概念格中的屬性粒度進(jìn)行研究.Kang 和Miao[41]對(duì)基于概念庫的形式概念格屬性粒度進(jìn)行了分析，結(jié)合形式概念格的結(jié)構(gòu)信息，在處理屬性粒度時(shí)提出了上下確界，并提出了基于屬性粒度的形式概念格擴(kuò)展模型.張清華等[42]給出了概念知識(shí)粒與概念信息粒的相互轉(zhuǎn)化方法.隨后，Belohlavek 等[43]提出了屬性粒度樹，對(duì)屬性粒度的粗細(xì)進(jìn)行研究，同時(shí)提出了控制經(jīng)典概念格中概念數(shù)量的Zoom 算法以實(shí)現(xiàn)多粒度經(jīng)典概念格的快速構(gòu)造，從而豐富了形式概念格中屬性粒度的研究.Zou 等[44]提出了快速提升形式概念格屬性粒度的“展開算法”.Wang 等[45]的研究?jī)?nèi)容從粒度優(yōu)化問題過渡到多粒度聯(lián)合求解的問題.

假設(shè)用戶想用概念格的方法來分析商品的銷售情況，可以用商品名稱、商品銷售的時(shí)間(上午、下午)、地域(東部、西部)、商品銷售區(qū)域人們的收入水平(高于5000 元、低于5000 元)等描述商品的屬性表示商品銷售.屬性粒度太大，描述對(duì)象太模糊，用戶只得到很少的概念，無法提取有用的知識(shí).類似地，若選擇太小的屬性粒度，可能會(huì)產(chǎn)生冗余概念，增大提取知識(shí)的成本.因此，通過不斷改變屬性的粒度得到不同的概念格，進(jìn)而發(fā)現(xiàn)數(shù)據(jù)中潛在、有趣的知識(shí)自然成為一種迫切的需要.

綜前所述，對(duì)概念格中的屬性粒度進(jìn)行研究具有重要意義.然而，當(dāng)前只有經(jīng)典概念格中的屬性粒度變換研究，因此本文提出面向?qū)ο蠖嗔６雀拍罡竦臉?gòu)造算法-Zoom，從而實(shí)現(xiàn)具有不同屬性粒度組合的面向?qū)ο蟾拍罡竦目焖贅?gòu)造，同時(shí)附上實(shí)例演示幫助讀者理解算法.

2 相關(guān)知識(shí)

2.1 形式背景和面向?qū)ο蟾拍钌伤阕?/h3>

定義1[46]記三元組(G，M，I)是形式背景，其中G 是非空的對(duì)象集合，M 是非空的屬性集合，I 表示G 和M 之間的二元關(guān)系(I 是(G×M)的子集).

形式背景一般用二維表表示，行表示對(duì)象，列表示屬性，行列交叉處的取值表示屬性與對(duì)象的隸屬關(guān)系，1 表示對(duì)象具有屬性，0 表示對(duì)象不具有屬性.

如表1 所示，對(duì)象的全集是{x1，x2，x3，x4，x5，x6}，屬性的全集是{a，b，c，d，e}.第一行數(shù)據(jù)表示對(duì)象x1具有屬性{a，c，d，e}，第一列數(shù)據(jù)表示屬性a 由對(duì)象{x1，x2，x5，x6}所具有.

表1 形式背景(G，M，I)

定義2[46]設(shè)(G，M，I)為形式背景，X ?G， B ?M，定義面向?qū)ο蟾拍钌伤阕?↑，↓)，如下所示.

2G→2M：

其中X↓表示只由X 中的對(duì)象擁有的屬性組成的屬性集合.

2M→2G：

設(shè)X1，X2?G，算子(↑，↓)具有以下性質(zhì)[46]：

2.2 面向?qū)ο蟾拍罡?/h3>

本小節(jié)介紹面向?qū)ο蟾拍罡竦南嚓P(guān)概念.

定義3[46]設(shè)(G，M，I)為形式背景，若對(duì)于任意的(X，B)， X ?G， B ?M， X =B↑， B =X↓，則稱二元組(X，B)為面向?qū)ο蟾拍?

設(shè)C1= (X1，B1)， C2= (X2，B2)是兩個(gè)面向?qū)ο蟾拍睿绻鸛1?X2(B1?B2)，則記(X1，B1) ≤(X2，B2).若?C0= (X0，B0)，使得(X1，B1) ≤(X0，B0) ≤(X2，B2)，則稱(X1，B1)是(X2，B2)的直接子概念，(X2，B2)是(X1，B1)的直接父概念，形式概念之間的這種關(guān)系稱為概念之間的偏序關(guān)系用“≤”表示.

定義4[46]設(shè)(X1，B1)， (X2，B2)為面向?qū)ο蟾拍?，面向?qū)ο蟾拍铋g的交(∧)、并(∨)運(yùn)算如下

由表1 所示的形式背景，得到如圖1 所示的面向?qū)ο蟾拍?格節(jié)點(diǎn))及概念格.其中，概念的外延為對(duì)象(此處用形式背景中對(duì)象的右下數(shù)字表示)集合，內(nèi)涵為屬性(此處用字母表示)集合.

圖1 面向?qū)ο蟾拍罡?/p>

2.3 屬性粒度

在計(jì)算機(jī)領(lǐng)域，粒度是指保存數(shù)據(jù)的細(xì)化或綜合程度.在不同屬性粒度的轉(zhuǎn)換過程中，發(fā)現(xiàn)最優(yōu)粒度是粒計(jì)算的一個(gè)重要應(yīng)用.屬性粒度越小，描述對(duì)象越細(xì)致.例如，一個(gè)屬性“Grade”([0-100] points)可以細(xì)分到另一個(gè)屬性粒度的級(jí)別：{“Fail”([0-60)points)，“Pass”([60-100]points)}，繼續(xù)細(xì)分到下一個(gè)屬性粒度的級(jí)別：{“Worse”([0-30) points)，“Bad”([30-60) points)，“Good”([60-90) points)，“Good”([90-100] points)}.

下面引入粒度樹及相關(guān)定義.

定義5[43]用一個(gè)樹根為Z 的樹形結(jié)構(gòu)表示屬性Z 的粒度等級(jí)，稱具有以下特點(diǎn)的樹形結(jié)構(gòu)為屬性Z 的粒度樹：

1) 樹根是粒度最大的屬性Z，樹的每一個(gè)節(jié)點(diǎn)都有一個(gè)獨(dú)一無二的標(biāo)簽Zi；

3) 如果{z1，z2，··· ，zi，zi+1，··· ，zn}是粒度大小相同的粒子的全集(粒度樹的一個(gè)粒層)，且滿足以下三個(gè)條件，則稱{z1，z2，··· ，zi，zi+1，··· ，zn}是Zi的一個(gè)劃分：

如圖2 所示，屬性成績(jī)的粒度樹共有3 個(gè)粒層，分別是：{{Grade}， {Pass， Fail}，{Worse， Bad， Good， Excellent}}.

圖2 “Good”的粒度樹

設(shè)(G，M，I)為形式背景，

表示由每個(gè)屬性的一個(gè)粒層組合在一起形成的粒層集合，其中ci表示第i 個(gè)屬性的粒度層級(jí)，|M|表示(G，M，I)中屬性的個(gè)數(shù).

同一形式背景中屬性的不同粒層集合之間存在一種偏序關(guān)系，設(shè)

基于屬性不同的粒層組合可以得到不同的形式背景(G，MU，IU)，設(shè)U1={L，R，G}， U2={L，R，{lG，dG}}，由此得到如表2 所示的兩個(gè)形式背景(G，MU1，IU1)(左)、(G，MU2，IU2)(右).其中{G}， {lG，dG}是屬性“Green”的粒度樹的兩個(gè)粒層，且{lG，dG}≤{G}.

表2 形式背景(G，M，I)

3 面向?qū)ο蠖嗔６雀拍罡竦臉?gòu)造算法—Zoom

屬性粒度改變前后，概念格中的概念存在內(nèi)在聯(lián)系，為了方便研究概念格變化的規(guī)律，現(xiàn)作以下定義：

3.1 面向?qū)ο蠖嗔６雀拍罡竦膶傩粤６燃?xì)化算法-Zoom-in

3.2 面向?qū)ο蠖嗔６雀拍罡竦膶傩粤６却只惴?Zoom-out

由此，Zoom-out 的正確性得證.

以上是針對(duì)面向?qū)ο蟾拍钐岢龅腪oom 算法，通過類似于面向?qū)ο蟾拍畹南嚓P(guān)定理易于得到面向?qū)傩愿拍畹南嚓P(guān)定理及面向?qū)傩愿拍罡竦腪oom 算法.在經(jīng)典的概念格構(gòu)造算法中，消耗時(shí)間最多的步驟是每層概念兩兩運(yùn)算得到新概念，設(shè)每層概念的個(gè)數(shù)為N，則經(jīng)典概念格的構(gòu)造算法時(shí)間復(fù)雜度為O(N2)，而Zoom 算法是在原有概念格的基礎(chǔ)上對(duì)每個(gè)概念格的內(nèi)涵與外延單獨(dú)進(jìn)行計(jì)算，所以時(shí)間復(fù)雜度為O(N)，因此，與經(jīng)典概念格的構(gòu)造算法相比，Zoom 算法的時(shí)間復(fù)雜度較低，因此執(zhí)行效率更高，有助于在實(shí)際應(yīng)用中從數(shù)據(jù)中進(jìn)行知識(shí)的挖掘.

4 結(jié)語

屬性粒度對(duì)于從數(shù)據(jù)中提取概念進(jìn)而得到概念格的結(jié)構(gòu)有重要影響，選擇合適的屬性粒度水平進(jìn)行組合，可以有效的控制概念格中概念的數(shù)量，進(jìn)而有助于用戶發(fā)現(xiàn)有趣的知識(shí).對(duì)于屬性粒度水平的選擇依賴于領(lǐng)域?qū)＜业慕?jīng)驗(yàn)知識(shí).通過分析概念內(nèi)涵、外延在屬性粒度變化前后的關(guān)系，對(duì)原概念格的概念進(jìn)行分類，在此基礎(chǔ)上，我們提出的算法-Zoom 可以在已有概念格和粒度樹的基礎(chǔ)上直接實(shí)現(xiàn)面向?qū)ο蟾拍罡竦臉?gòu)造，避免了利用傳統(tǒng)概念格構(gòu)造算法從形式背景生成概念繼而得到概念格的繁重工作量，從而提高了概念格的構(gòu)造效率.下一步，我們將研究面向?qū)傩远嗔６雀拍罡竦臉?gòu)造以及面向?qū)ο蠖嗔６雀拍罡瘛⒚嫦驅(qū)傩远嗔６雀拍罡?、?jīng)典概念格之間的轉(zhuǎn)換關(guān)系，后續(xù)將研究多粒度廣義單邊概念格的快速構(gòu)造算法.