面向?qū)ο蠖嗔６雀拍罡竦臉?gòu)造

李克文， 呂萌萌， 邵明文

(中國石油大學(華東)計算機與通信工程學院，青島 266580)

1 引言

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

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

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

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

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

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

2 相關(guān)知識

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

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

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

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

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

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

2G→2M：

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

2M→2G：

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

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

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

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

設(shè)C1= (X1，B1)， C2= (X2，B2)是兩個面向?qū)ο蟾拍?，如果X1?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的交(∧)、并(∨)運算如下

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

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

2.3 屬性粒度

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

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

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

1) 樹根是粒度最大的屬性Z，樹的每一個節(jié)點都有一個獨一無二的標簽Zi；

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

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

圖2 “Good”的粒度樹

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

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

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

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

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

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

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

3.1 面向?qū)ο蠖嗔６雀拍罡竦膶傩粤６燃毣惴?Zoom-in

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

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

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

4 結(jié)語

屬性粒度對于從數(shù)據(jù)中提取概念進而得到概念格的結(jié)構(gòu)有重要影響，選擇合適的屬性粒度水平進行組合，可以有效的控制概念格中概念的數(shù)量，進而有助于用戶發(fā)現(xiàn)有趣的知識.對于屬性粒度水平的選擇依賴于領(lǐng)域?qū)＜业慕?jīng)驗知識.通過分析概念內(nèi)涵、外延在屬性粒度變化前后的關(guān)系，對原概念格的概念進行分類，在此基礎(chǔ)上，我們提出的算法-Zoom 可以在已有概念格和粒度樹的基礎(chǔ)上直接實現(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)造算法.