折延宏，胡夢(mèng)婷，賀曉麗，曾望林

1.西安石油大學(xué) 理學(xué)院，西安 710065

2.西安石油大學(xué) 計(jì)算機(jī)學(xué)院，西安 710065

1 引言

形式概念分析[1]是一種進(jìn)行數(shù)據(jù)分析的有效數(shù)學(xué)工具，其核心概念為形式背景、形式概念與概念格。通過概念格所展現(xiàn)出的概念之間的特化與泛化關(guān)系，揭示了數(shù)據(jù)表的內(nèi)在結(jié)構(gòu)，刻畫了對(duì)象與屬性之間的依賴關(guān)系。

近年來，一個(gè)有趣的研究方向是將多粒度計(jì)算的思想融入到形式概念分析之中，由此產(chǎn)生了不同的多粒度形式概念分析模型[2-16]。形式概念分析的粒計(jì)算方法包括形式背景的對(duì)象粒化[2]、屬性?；痆3-8]、關(guān)系?；痆9-11]等，這些方法除了可以緩解龐大的概念個(gè)數(shù)之外，還可以獲取數(shù)據(jù)的多層次概念知識(shí)表示與處理方法[12]。

本文主要關(guān)注的是形式概念分析的屬性?；椒ā傩粤；馕吨鴮傩缘暮喜ⅲɑ蛱嵘⒎纸猓ɑ蚣?xì)化），通過屬性?；蓪?shí)現(xiàn)知識(shí)的粗細(xì)轉(zhuǎn)換，使人們?cè)诓煌６鹊男问奖尘吧线M(jìn)行概念分析。Belohlavek 等人在文獻(xiàn)[3]中提出了基于屬性?；男问礁拍罘治龇椒?，在該方法中，一個(gè)屬性在不同粒度下可劃分為不同的子屬性，利用粒度樹與剪枝（cut）等主要工具可導(dǎo)出不同粒度層次的形式背景，基于此，實(shí)現(xiàn)了在不同粒度層次下對(duì)數(shù)據(jù)的分析[3-5，15]。與此不同的是，基于屬性聚類的多粒度形式概念分析模型是通過屬性集上的先驗(yàn)知識(shí)或先驗(yàn)關(guān)系R實(shí)現(xiàn)的。文獻(xiàn)[6]通過屬性集上的一等價(jià)關(guān)系實(shí)現(xiàn)了屬性的聚類，進(jìn)而研究了聚類前后概念之間的內(nèi)在聯(lián)系與生成方式?？梢哉f，文獻(xiàn)[3]與文獻(xiàn)[6]提出的方法迥然不同，前者通過粒度樹、剪枝等方法實(shí)現(xiàn)，后者通過對(duì)屬性聚類實(shí)現(xiàn)。本文對(duì)這兩種不同的方法進(jìn)行分析對(duì)比。

2 基于屬性聚類與屬性?；男问礁拍罘治龇椒?/h2>

2.1 形式概念分析的基本知識(shí)

三元組(G,M,I)為一形式背景。其中G為一非空有限對(duì)象集，M為一非空有限屬性集，為與M之間的一二元關(guān)系，按如下方式定義兩映射↑:2G→2M與↓:2M→2G:

若X↑=Y,Y↓=X,則稱(X,Y)為一形式概念，也稱為Wille 概念。全體形式概念之集L(G,M,I)在如下偏序關(guān)系下構(gòu)成一格，簡(jiǎn)稱為概念格：

文獻(xiàn)[17-18]通過將粗糙近似算子引入到形式概念分析之中，引入了面向?qū)ο蟮男问礁拍罘治瞿Ｐ?，其概念生成算子是按照如下方式定義的：

若X□=Y,Y?=X,則稱(X,Y)為一形式概念，也稱為面向?qū)ο蟾拍?。全體面向?qū)ο蟾拍钪疞ο(G,M,I)在如下偏序關(guān)系下構(gòu)成一格，簡(jiǎn)稱為概念格：

以下命題給出了如上兩種不同概念的性質(zhì)，這種性質(zhì)在本文的后續(xù)證明中起著重要的作用。

命題1[17-18]設(shè)(G,M,I)為一形式背景，?X?G,Y?M：

（1）(X↑↓,X↑)∈L(G,M,L),(Y↓,Y↓↑)∈L(G,M,L)

（2）(X□?,X□)∈Lο(G,M,L),(Y?,Y?□)∈Lο(G,M,L)

（3）X?X↑↓,Y∈Y↓↑

定義1 若在M1與M2之間的一一映射f:M1→M2,使得 ?g∈G,m1∈M1,gI1m1當(dāng)且僅當(dāng)gI2f(m1),則稱兩形式背景(G,M1,I1)與(G,M2,I2)是同構(gòu)的。

在一一對(duì)應(yīng)關(guān)系中不區(qū)分屬性的情況下，可將兩同構(gòu)的形式背景視為相同的。

2.2 基于屬性聚類的形式概念分析方法

如文獻(xiàn)[6，12]中所述，通常情況下，根據(jù)某個(gè)特定需求，或基于先驗(yàn)知識(shí)，可將形式背景中的屬性集聚在一起，形成更高一級(jí)的屬性。數(shù)學(xué)上，這一想法可通過屬性集上的等價(jià)關(guān)系來實(shí)現(xiàn)?；诘葍r(jià)關(guān)系，可將部分屬性聚合在一起形成一個(gè)新的屬性，由此可導(dǎo)出一個(gè)新的形式背景。與原形式背景相比，對(duì)象集是相同的，但屬性集發(fā)生了變化，由此可在不同層次、不同粒度下進(jìn)行概念分析。

具體地，設(shè)(G,M,I)為一形式背景，R為M上的等價(jià)關(guān)系，[m]R為包含m的屬性等價(jià)類?；?G,M,I)與R，可構(gòu)造如下形式背景(G,MR,IR)，其中：

注意到：[m]R雖然是由形式背景(G,M,I)中的若干屬性組成的，但在形式背景(G,MR,IR)中，它只是作為一個(gè)屬性。此外，IR的定義與I有著密切的聯(lián)系，在新的形式背景(G,MR,IR)中，對(duì)象g與屬性[m]R具有關(guān)系IR當(dāng)且僅當(dāng)g與該等價(jià)類中某一個(gè)屬性在原形式背景中具有關(guān)系I。

在新的形式背景(G,MR,IR)中，可定義如下形式的概念生成算子：

2.3 基于屬性?；男问礁拍罘治龇椒?/h3>

文獻(xiàn)[3]提出了一種基于屬性粒化的形式概念分析方法。在該方法中，原形式背景(G,M,I)中的每一個(gè)屬性在不同的粒度下可分解為不同的子屬性，這些不同粒度的屬性形成了一粒度樹，文獻(xiàn)[3]借助粒度樹以及粒度樹中的剪枝方法，從原背景出發(fā)導(dǎo)出了不同粒度的形式背景，為在不同粒度下進(jìn)行概念分析提供了一個(gè)可能的框架。

定義2[3]設(shè)K=(G,M,I) 為一形式背景，m∈M。屬性m的粒度樹Tm是滿足如下條件的一個(gè)含有根節(jié)點(diǎn)的樹：

（l）樹中的每一個(gè)節(jié)點(diǎn)都用一個(gè)屬性名稱來標(biāo)記，根節(jié)點(diǎn)記作m；

（2）對(duì)于每一個(gè)節(jié)點(diǎn)z，賦予一對(duì)象集合{z}↓?G,該對(duì)象集{z}↓由具有屬性z的對(duì)象所構(gòu)成；

（3）若z1,z2,…,zn是節(jié)點(diǎn)z的子節(jié)點(diǎn)，則 {{z1}↓,{z2}↓,…,{zn}↓}是 {z}↓的一個(gè)劃分。

為方便起見，往往用z↓，而不用{z}↓，其含義是不變的。

定義3[3]粒度樹Tm中的一剪枝（原文稱之為cut）C是滿足如下條件的一節(jié)點(diǎn)集：對(duì)于每一個(gè)葉節(jié)點(diǎn)u而言，在從u到根節(jié)點(diǎn)m的路徑上，存在唯一的節(jié)點(diǎn)v屬于C。

例1 表1給出了一基于屬性?；男问奖尘?，在該表中，屬性G具有兩層粒度，圖1給出了粒度樹TG中的所有剪枝，即{G}與{IG,dG}。注意到C={G,dG}并不是粒度樹TG的一剪枝，其原因在于從葉節(jié)點(diǎn)dG到根節(jié)點(diǎn)G的路徑上，存在兩個(gè)節(jié)點(diǎn)屬于C。同理，{G,IG}也不是一剪枝。

表1 基于屬性?；男问奖尘?/p>

圖1 表1中的粒度樹以及剪枝?z ∈MC,(g,m)∈IC ?g ∈m↓

由定義2、定義3 以及例1 可見，每一個(gè)屬性都有唯一的粒度樹，但每一個(gè)粒度樹上有不同的剪枝。在同一屬性粒度Tm的剪枝集上定義如下偏序關(guān)系：C1={y1,y2,…,yr},C2={z1,z2,…,zs}∈Tm,C1≤C2當(dāng)且僅當(dāng)是的細(xì)化，即=是通過對(duì)中每個(gè)集合進(jìn)一步劃分后得到的。

設(shè)(G,M,I)為一形式背景，對(duì)于每一個(gè)屬性m∈M而言，Tm為其粒度樹，Cm是Tm上的一剪枝，不同屬性粒度樹上的剪枝可導(dǎo)出如下一形式背景(G,MC,IC)，其中。

在每個(gè)屬性的粒度樹上任意選取一剪枝，所有這些剪枝之集C代表了特定的屬性?；瘜哟危℅ranularity Level）。對(duì)于任意兩屬性?；瘜哟蜟1與C2，用C1≤C2表示 ?m∈M，C1m≤C2m,這里C1m與C2m分別表示屬性m在兩?；瘜哟沃械募糁?。換言之，C1是C2的細(xì)化。由此，可在不同的粒化層次上進(jìn)行概念分析。

在新的形式背景(G,MC,IC)中，可定義如下形式的概念生成算子：

為以下討論方便，引入如下記號(hào)：設(shè)C1、C2為滿足C1≤C2的兩剪枝，對(duì)于用表示m1在中的父節(jié)點(diǎn)，用表示中的子節(jié)點(diǎn)集。

3 不同多粒度方法的比較研究

3.1 Wille概念模型框架內(nèi)兩方法的比較研究

由上文的介紹可以看得出，基于屬性?；c基于屬性聚類的多粒度形式概念分析方法有著較為顯著的差異，本節(jié)進(jìn)一步分析兩者的區(qū)別與內(nèi)在聯(lián)系。

定理1 設(shè)(G,M,I)為一形式背景，R為M上的一等價(jià)關(guān)系，則對(duì)于任意(A,B)∈L(G,MR,IR),存在(Ak,Bk)∈L(G,M,I)(k∈K)使得A=∪i∈K Ak。

證明對(duì)于(A,B)∈L(G,MR,IR)，以下分兩種情形進(jìn)行證明。

情形1B≠?：此時(shí)不妨設(shè)B={[y1]R,[y2]R,…,[yn]R}。任意(m1,m2,…,mn)∈[y1]R×[y2]R×…×[yn]R,令(Ak,Bk)=({m1,m2,…,mn}↓，{m1,m2,…,mn}↓↑)。以下證明 (Ak,Bk)為滿足條件的形式概念。

事實(shí)上，由命題1 知(Ak,Bk)∈L(G,M,I)。以下證明A=∪Ak。首先證明∪Ak?A。對(duì)于任意對(duì)象g∈G,若g∈∪Ak,即存在 (m1,m2,…,mn)∈[y1]R×[y2]R×…×[yn]R使得g∈{m1,m2,…,mn}↓,由式（2）知g同時(shí)具有屬性m1,m2,…,mn,結(jié)合式（6）知g同時(shí)具有形式背景中的屬性 [y1]R,[y2]R,…,[yn]R,因此，g∈B↓R={[y1]R,[y2]R,…,[yn]R}↓R,即g∈A。反過來，任取g∈A,由A=B↓R={[y1]R,[y2]R,…,[yn]R}↓R知g同時(shí)具有 (G,MR,LR)中屬性[y1]R,[y2]R,…,[yn]R，由式（6）知必存在 (m1,m2,…,mn)∈[y1]R×[y2]R× … ×[yn]R使得gImi,i=1,2,…,n,因此，g ∈{m1,m2,…,mn}↓,即g屬于某一Ak。綜上A=∪i∈K Ak。

情形2B=?：此時(shí)易知A=G,對(duì)于G中每個(gè)對(duì)象g而言，({g}↑↓,{g}↑)屬于L(G,M,I)，且g∈{g}↑↓（命題1），因此G=∪g∈G{g}↑↓,得證。

以下將說明文獻(xiàn)[3]的概念分解定理可看作定理1的特殊情形。首先注意到如下事實(shí)成立：在文獻(xiàn)[3]中，C1≤C2意味著中每一屬性都在中存在劃分子屬性，即使得從屬性聚類的角度看，可看作是原背景，通過將中每個(gè)屬性的劃分子屬性聚為一類，便可得到形式背景

兩種不同背景下的概念分析算子有著密切的聯(lián)系，這由如下命題可以看得出。

命題2 設(shè)(G,M,I)為一形式背景，C1、C2為兩剪枝且C1≤C2,在上定義二元關(guān)系則：

（1）R為上的一等價(jià)關(guān)系；

（3）在同構(gòu)意義下，?X?G,X↑C2=X↑R。

證明（1）容易驗(yàn)證R滿足自反性、對(duì)稱性以及傳遞性，因此R為一等價(jià)關(guān)系。

（2）定 義 映 射容易驗(yàn)證f為一映射，在不區(qū)分m與f(m)的前提下，以下證明事實(shí)上，對(duì)于G中任意對(duì)象g以及中屬性m2，若，由于中屬性是中相應(yīng)屬性的劃分，因此存在中屬性z1使得，根據(jù)式（6）得故反過來，若由式（6）知存在[z]R中某一屬性z1使得，對(duì)于z1，必然存在中一父節(jié)點(diǎn)z2使得，由于與存在一一對(duì)應(yīng)關(guān)系，在將[z]R與z2不加以區(qū)分的情況下，便有得證。

（3）由（2）可立即推得。

由命題2可得如下推論。

推論1 若C1≤C2,則對(duì)于任一形式概念∈存在形式概念集k∈K使得 ∪k∈K Ak=A。

證明若C1≤C2,由命題2 知形式背景可看作是對(duì)形式背景進(jìn)行屬性聚類后得到的形式背景，則由定理1知結(jié)論成立。

注意到推論1 正是文獻(xiàn)[3]所述的分解定理。綜合以上結(jié)論，文獻(xiàn)[3]給出的基于屬性?；男问礁拍罘治瞿Ｐ褪潜疚奶岢龅幕趯傩跃垲惛拍罘治瞿Ｐ偷奶厥馇樾?。

3.2 面向?qū)ο蟾拍罘治瞿Ｐ椭袃煞N方法的比較

文獻(xiàn)[15]在多粒度形式背景中研究了面向?qū)ο蟮男问礁拍?，將已有的面向?qū)ο蟾拍钣蓡瘟６韧卣怪炼嗔６惹樾?，研究了在不同粒度下，面向?qū)ο蟾拍钪g的內(nèi)在聯(lián)系，證明了在不同粗細(xì)粒度下外延集相等的充分必要條件。

設(shè)(G,M,I)為一形式背景，對(duì)于任意屬性m∈M,有一粒度樹Tm,CM為Tm上一剪枝，不同粒度樹的剪枝（每個(gè)粒度樹上任意挑選一個(gè)剪枝）集可按之前的方式生成一形式背景(G,MC,IC),利用面向?qū)ο蟮母拍钌伤阕樱?）以及（4）可在不同的粒度下生成不同的面向?qū)ο蟾拍罡?。本文用Lο(G,MC,IC)以及EXT(Lο(G,MC,IC))分別表示由形式背景(G,MC,IC)所生成的面向?qū)ο蟾拍罡褚约巴庋蛹?/p>

文獻(xiàn)中主要結(jié)論如下：

命題3[15]若C1≤C2,則

命題4[15]若C1≤C2,則

事實(shí)上，利用屬性聚類方法，可將文獻(xiàn)[15]中的面向?qū)ο蟮亩嗔６刃问礁拍罘治瞿Ｐ屯茝V至更為一般的情形。

定義4 設(shè)(G,M,I)為一形式背景，R為M上的一等價(jià)關(guān)系，(G,MR,IR)為其?；笮问奖尘?，X?G,Z?MR,若X□R=Z且Z?R=X,則稱 (X,Z)為 (G,MR,IR)中一面向?qū)ο蟮母拍睢?/p>

命題5 設(shè)(G,M,I)為一形式背景，R為M上的一等價(jià)關(guān)系，則EXT(Lο(G,MR,IR))?EXT(Lο(G,M,I))。

證明任取X∈EXT(Lο(G,MR,IR)),根據(jù)定義，存在Y ?MR使 (X,Y)∈Lο(G,MR,IR),即X□R=Y且Y?R=X。要證明X∈EXT(Lο(G,M,I)),等價(jià)于證明 (X,X□)∈L(G,M,I),或等價(jià)地，X□?=X。任取g∈X?R,由式（4）知，存在屬性m∈X□使得gIm，結(jié)合式（3）便知g∈X。反過來，任取g∈X，由Y?R=X知g∈Y?R,則存在[m]∈Y使gIR[m] ，結(jié)合IR的定義（即式（6））知存在m1∈[m]R使gIm1。以下說明m1∈X□,事實(shí)上，對(duì)于任意滿足gIm1的對(duì)象g而言，由gIR[m1]=gIR[m] 以及[m]∈Y，X□R=Y知g∈X,從而根據(jù)式（3）可得m1∈X□。再結(jié)合gIm1以及式（4）便知g∈X□?。

命題6 設(shè)(G,M,I)為一形式背景，R為M上的一等價(jià)關(guān)系，則對(duì)于任意X?G,X□R?X□,{[m]R|m∈X?}?X?R。

證明任取y∈X□R，則存在X□R中一等價(jià)類[m]R使得y∈[m]R。對(duì)于滿足gIy的任意對(duì)象g而言，gIR[m]R成立，結(jié)合[m]R∈X□R便知g∈X，因此 ∪X□R?X□。

任取 [y]R∈{[m]R|m∈X?} ，由g∈X?以及（4）知存在X中一對(duì)象g使得gIy，從而gIR[y]R，結(jié)合g∈X便知[y]R∈X?R，從而 {[m]R|m∈X?}?X?R。

命題7 設(shè)(G,M,I)為一形式背景，R為M上的一等價(jià)關(guān)系，則EXT(Lο(G,M,I))=EXT(Lο(G,MR,IR)),當(dāng)且僅當(dāng)對(duì)于任一等價(jià)類[m]R∈MR，存在Z?MR，使得對(duì)于任意。

證明充分性：對(duì)于形式背景(G,M,I)而言，由命題1知，對(duì)于任一外延X∈EXT(L(G,M,I))而言，存在Y?M使得X=∪mi∈Y y↓，又由題設(shè)條件知對(duì)于每一個(gè)屬性mi,存在Z?MR,使得對(duì)于任意，這樣，由命題1知X也屬于EXT(L(G,MR,IR))。結(jié)合命題5便知EXT(Lο(G,M,I))=EXT(Lο(G,MR,IR))。

必要性：若EXT(Lο(G,M,I))=EXT(Lο(G,MR,IR))，則對(duì)于EXT(Lο(G,M,I))中任一外延X,X也一定屬于EXT(Lο(G,MR,IR))，由命題1便知該結(jié)論成立。

事實(shí)上，類似于命題2，可以證明基于屬性?；拿嫦?qū)ο蟾拍罘治瞿Ｐ涂煽醋鳛榛趯傩跃垲惖拿嫦驅(qū)ο蟾拍罘治龅奶厥馇樾巍?/p>

命題8 設(shè)(G,M,I)為一形式背景，C1、C2為兩剪枝且C1≤C2,在上定義二元關(guān)系，則：

（1）R為上的一等價(jià)關(guān)系；

證明可類似于命題2得證。

命題8告訴人們，對(duì)于屬性?；械膬杉糁1、C2而言，若C1≤C2，則C2可看作是經(jīng)過對(duì)C1中的屬性聚類得到的，兩種方法得到的面向?qū)ο蟾拍罱扑阕邮窍嗟鹊?。由命題8知，命題3可看作為命題5的特殊情形，命題7所得結(jié)論要比命題4更具一般性。

4 結(jié)束語

本文對(duì)多粒度形式概念分析中的兩種不同方法進(jìn)行了分析對(duì)比，指出基于屬性?；姆椒煽醋魇且延械幕趯傩跃垲惙椒ǖ奶厥馇樾?。下一步，可基于屬性聚類的方法設(shè)計(jì)有效的概念生成算法，也可以研究基于屬性聚類的多尺度信息表的規(guī)則提取方法。