智慧來，徐 彤，李逸楠

河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454003

概念是人類認(rèn)知活動的基本單位，以概念為基礎(chǔ)的粒計(jì)算方法是實(shí)現(xiàn)可解釋性人工智能的途徑之一[1-5]．粒計(jì)算通過對復(fù)雜數(shù)據(jù)的多粒度化處理得以實(shí)現(xiàn)復(fù)雜問題的簡易求解[6]．多粒度化的數(shù)據(jù)呈現(xiàn)出大小不同的信息粒，從而構(gòu)成了由小到大的粒度鏈條[7]．在粒度鏈條中，小粒是構(gòu)成大粒的基礎(chǔ)，粒度的變化體現(xiàn)著思維過程的泛化和特化，在泛化和特化的雙向思維驅(qū)動下，人們得以解決許多看似無法下手的困難問題[8-9].

形式概念分析(formal concept analysis，F(xiàn)CA)[10]是基于格論建立起來的數(shù)學(xué)方法，已經(jīng)成為一種最有效的粒計(jì)算理論．在應(yīng)用的驅(qū)動下，根據(jù)實(shí)際需求可以通過各種方法構(gòu)造不同類型的形式概念，包括經(jīng)典形式概念、 面向?qū)ο蟾拍睢?面向?qū)傩愿拍睢?對偶概念等[11-14]．最近十年，粗糙集、 粒計(jì)算、 模糊集、 三支決策理論等推動了形式概念分析的發(fā)展，產(chǎn)生了許多有重要理論價值與應(yīng)用價值的成果[15-20]．其中，QI等[21]將三支決策理論(three-way decisions，3WD)中的三分思想引入形式概念分析，提出了三支概念分析(three-way concept analysis，3WCA)．具體就是通過在形式背景上定義負(fù)算子，刻畫對象子集與屬性子集間“共同不具有”的關(guān)系，并構(gòu)造三支算子，將對象集或?qū)傩约郑纬扇Ц拍钆c三支概念格．三支概念分析自2014年提出以來，得到了廣泛的認(rèn)可[22-24].

信息檢索一直是人工智能的重要研究課題，但是，現(xiàn)有的信息檢索方法廣泛采用距離度量相似程度，不能完全客觀精準(zhǔn)地對具有家族相似性的原型范疇進(jìn)行刻畫．如果能夠采用粒計(jì)算思想，從概念的角度對整個粒度鏈條進(jìn)行深入研究，特別是對粒度鏈條頂端的子格進(jìn)行研究，或許可以得到滿意的解決.

現(xiàn)代范疇理論[25-26]強(qiáng)調(diào)相似的傳遞性，使得看似不相關(guān)的對象通過相似的傳遞性聯(lián)系在一起，形成一個個特定的范疇，在同一范疇內(nèi)，成員共享“家族相似性”．顯然，采用距離度量相似程度不能準(zhǔn)確地刻畫這樣的情形．為了解決這一問題，在現(xiàn)代范疇理論的啟發(fā)下，智慧來與李逸楠首次提出了概念簇，用以刻畫一組具有家族相似性的概念，并應(yīng)用于相似對象的檢索[27]．概念簇中的概念包含了對象具有的共同屬性，但忽略了對象都不具有的屬性，不利于解決某些特定的問題.

為了解決上述問題，本文融合現(xiàn)代范疇理論與三支概念分析，提出了用三支概念簇刻畫具有家族相似性的三支概念集合，并對三支概念簇的性質(zhì)、 運(yùn)算以及應(yīng)用進(jìn)行了初步的探討.

1 基本理論

本節(jié)介紹形式概念分析[10]、 概念簇[27]以及三支概念分析[21]的相關(guān)基本概念.

1.1 形式概念分析與概念簇

形式概念分析[10]建立在格論基礎(chǔ)之上，對哲學(xué)中的概念進(jìn)行了高度的數(shù)學(xué)概括，具有良好的性質(zhì)，已經(jīng)廣泛應(yīng)用于知識表示、 數(shù)據(jù)挖掘、 近似推理等諸多領(lǐng)域．形式背景是領(lǐng)域本體的抽象描述，也是形式概念分析研究的具體對象和起點(diǎn).

具體地，形式背景可以抽象為一個三元組K=(G，M，I)，其中，G為對象集合，M為屬性集合，且均非空有限，I為G和M之間的二元關(guān)系．進(jìn)一步，使用I(x，a)=1表示對象x具有屬性a，使用I(x，a)=0表示對象x不具有屬性a．在下文中，為了方便起見，對于單元素集合，只列出其中的元素．例如，用x表示集合{x}.

對于X?G和A?M，分別定義對象集和屬性集上的算子如下：

X*={a∈M|?x∈X，I(x，a)=1}A*={x∈G|?a∈A，I(x，a)=1}

若X*=A且A*=X，則稱(X，A)是形式背景K的一個概念．已經(jīng)證明，形式背景K的全體概念構(gòu)成一個完全格，并稱之為概念格，記做L(K).

現(xiàn)代范疇理論[25-26]著重分析了家族相似概念，從理論上闡述了在同一個范疇中有可能存在一些不具有共同屬性的對象．Wittgenstein通過深入了解許多不同類型的游戲，發(fā)現(xiàn)當(dāng)中的一些游戲并不具有共同點(diǎn)，但是體現(xiàn)出了不可忽視的緊密聯(lián)系．經(jīng)過分析得知，這些游戲是通過相似的傳遞性而密切聯(lián)系在一起，利用這種密切聯(lián)系，Wittgenstein將這些游戲劃分成了多個家族．語言學(xué)家Labov和Rosch在深入研究自然范疇的基礎(chǔ)上，將“家族相似性”解釋為家族成員具有某些相似之處，并將“原型范疇”(prototype category)解釋為具有“家族相似性”的自然范疇，從而奠定了現(xiàn)代范疇理論的基礎(chǔ).

現(xiàn)代范疇理論的主要觀點(diǎn)包括：

1) 范疇內(nèi)的各個成員通過相似的傳遞性聚集在一起，所有成員不一定存在相同的約束；

2) 范疇中可能存在一個或多個中心，形成單一中心結(jié)構(gòu)或多中心結(jié)構(gòu)；

3) 對于一個范疇，最具典型性的成員位于范疇的中心.

現(xiàn)代范疇理論的主要觀點(diǎn)在粒計(jì)算理論中已經(jīng)有大量的體現(xiàn)．在現(xiàn)代范疇理論的啟發(fā)下，智慧來等提出了概念簇，用以刻畫具有某些特定相似之處的概念，并應(yīng)用于基于概念格的相似對象檢索.

定義1[27]給定一個形式背景K=(G，M，I)，X?G和A?M．若

C(X，A)={(Y，B)∈L(K)|Y?X，B?A}≠?

則稱C(X，A)是K的一個概念簇.

文獻(xiàn)[27]已經(jīng)證明，概念簇本質(zhì)上是概念格的子格，位于粒度鏈條的最頂端，使用概念簇代替子格，是為了強(qiáng)調(diào)概念之間的家族相似性，以便于概念格理論的應(yīng)用.

1.2 三支概念分析

三支概念分析[21-22]相比較于經(jīng)典形式概念分析，刻畫了對象共同不具有的屬性，能夠提供經(jīng)典形式概念分析所不能提供的某些細(xì)節(jié)．為了構(gòu)造三支概念，首先需要定義對象集和屬性集上的負(fù)算子.

給定一個形式背景K=(G，M，I)，X?G，B?M，對象集和屬性集上的負(fù)算子分別定義如下：

定義2給定一個形式背景K=(G，M，I)，X?G，A，B?M，定義對象導(dǎo)出三支算子如下：

進(jìn)一步，若X?=(A，B)且(A，B)?=X，則稱(X，(A，B))為對象導(dǎo)出三支概念，簡稱為OE-概念．已經(jīng)證明，形式背景K的全體對象導(dǎo)出三支概念構(gòu)成一個完全格，并稱之為對象導(dǎo)出三支概念格，記做OEL(K).

在OEL(K)中存在一類對象誘導(dǎo)的三支概念，兩類屬性誘導(dǎo)的三支概念，這些概念在基于三支概念分析的應(yīng)用中發(fā)揮著重要作用，具體定義如下.

例1給定一個形式背景K=(G，M，I)，如表1所示，其中共包含4個對象和5個屬性，用符號“×”表示某個對象具有某個屬性．形式背景K的對象導(dǎo)出三支概念格OEL(K)，如圖1所示.

圖1 形式背景K的對象導(dǎo)出三支概念格OEL(K)

表1 例1的形式背景K

形式背景K的對象導(dǎo)出三支概念格OEL(K)中包含4個對象誘導(dǎo)的三支概念，分別為：對象1誘導(dǎo)的(1，(ace，bd))，對象2誘導(dǎo)的(2，(bd，ace))，對象3誘導(dǎo)的(3，(abe，cd))和對象4誘導(dǎo)的(4，(abcd，e)).

此外，OEL(K)中包含5個Ⅰ型屬性誘導(dǎo)的三支概念，分別為：屬性a誘導(dǎo)的(134，(a，?))，屬性b誘導(dǎo)的(234，(b，?))，屬性c誘導(dǎo)的(14，(ac，?))，屬性d誘導(dǎo)的(24，(bd，e))和屬性e誘導(dǎo)的(13，(ae，d)).

再者，OEL(K)中包含5個Ⅱ型屬性誘導(dǎo)的三支概念，分別為：屬性a誘導(dǎo)的(2，(bd，ace))，屬性b誘導(dǎo)的(1，(ace，bd))，屬性c誘導(dǎo)的(23，(b，c))，屬性d誘導(dǎo)的(13，(ae，d))和屬性e誘導(dǎo)的(24，(bd，e)).

2 三支概念簇

概念簇[27]建立于經(jīng)典概念格的基礎(chǔ)之上，只考慮了對象具有的共同屬性．然而，在許多情況下，不僅要考慮對象具有的共同屬性，還需要考慮對象都不具有的屬性．在現(xiàn)代范疇理論的啟發(fā)下，本文在三支概念分析的基礎(chǔ)上提出三支概念簇.

2.1 三支概念簇的定義

本質(zhì)上，概念簇刻畫了一組具有家族相似性的概念．在此基礎(chǔ)上，我們提出三支概念簇，用以描述具有家族相似性的三支概念集合.

定義4給定一個形式背景K=(G，M，I)，x∈G，a∈M．若

t(x，a)={(X，(A，B))∈OEL(K)|(x??，x?)≤(X，(A，B))≤(a*，a*?)}≠?

則稱t(x，a)為對象x和屬性a誘導(dǎo)的Ⅰ型三支概念簇.

定義5給定一個形式背景K=(G，M，I)，x∈G，a∈M．若

則稱t(x，a～)為對象x和屬性a誘導(dǎo)的Ⅱ型三支概念簇.

性質(zhì)1給定一個形式背景K=(G，M，I)，x∈G，a∈M．三支概念簇t(x，a)和t(x，a～)均是OEL(K)的子格.

證首先，由形式背景K=(G，M，I)的有限性可知OEL(K)是有限的，進(jìn)而可知t(x，a)是有限的．其次，t(x，a)中存在唯一的最大元(a*，a*?)，且存在唯一的最小元(x??，x?)．綜上可知，三支概念簇t(x，a)是OEL(K)的一個子格.

同理可證t(x，a～)也是OEL(K)的一個子格．證畢.

定義6給定一個形式背景K=(G，M，I)，x∈G，a∈M．稱t(x，?)為對象x誘導(dǎo)的三支概念簇，稱t(?，a)為屬性a誘導(dǎo)的Ⅰ型三支概念簇，稱t(?，a～)為屬性a誘導(dǎo)的Ⅱ型三支概念簇.

實(shí)際上，對于對象x和屬性a誘導(dǎo)的Ⅰ型三支概念簇t(x，a)，令a=?，即可得到對象x誘導(dǎo)的三支概念簇t(x，?)； 對偶地，令x=?，即可得到屬性a誘導(dǎo)的Ⅰ型三支概念簇t(?，a).

對于對象x和屬性a誘導(dǎo)的Ⅱ型三支概念簇t(x，a～)，令x=?，即可得到屬性a誘導(dǎo)的Ⅱ型三支概念簇t(?，a～).

例2對于例1中的形式背景K，考察其上的三支概念簇如下.

形式背景K中包含4個對象誘導(dǎo)的三支概念簇，分別為：

對象1誘導(dǎo)的t(1，?)={(1，(ace，bd))，(13，(ae，d))，(14，(ac，?))，(134，(a，?))，(1234，(?，?))}；

對象2誘導(dǎo)的t(2，?)={(2，(bd，ace))，(23，(b，c))，(24，(bd，e))，(234，(b，?))，(1234，(?，?))}；

對象3誘導(dǎo)的t(3，?)={(3，(abe，cd))，(13，(ae，d))，(23，(b，c))，(34，(ab，?))，(134，(a，?))，(234，(b，?))，(1234，(?，?))}；

對象4誘導(dǎo)的t(4，?)={(4，(abcd，e))，(14，(ac，?))，(24，(bd，e))，(34，(ab，?))，(134，(a，?))，(234，(b，?))，(1234，(?，?))}.

形式背景K中包含5個屬性誘導(dǎo)的Ⅰ型三支概念簇，分別為：

屬性a誘導(dǎo)的t(?，a)={(134，(a，?))，(34，(ab，?))，(14，(ac，?))，(13，(ae，d))，(3，(abe，cd))，(1，(ace，bd))，(4，(abcd，e))，(?，(abcde，abcde))}；

屬性b誘導(dǎo)的t(?，b)={(234，(b，?))，(23，(b，c))，(34，(ab，?))，(24，(bd，e))，(2，(bd，ace))，(3，(abe，cd))，(4，(abcd，e))，(?，(abcde，abcde))}；

屬性c誘導(dǎo)的t(?，c)={(14，(ac，?))，(1，(ace，bd))，(4，(abcd，e))，(?，(abcde，abcde))}；

屬性d誘導(dǎo)的t(?，d)={(24，(bd，e))，(2，(bd，ace))，(4，(abcd，e))，(?，(abcde，abcde))}；

屬性e誘導(dǎo)的t(?，e)={(13，(ae，d))，(3，(abe，cd))，(1，(ace，bd))，(?，(abcde，abcde))}.

形式背景K中包含5個屬性誘導(dǎo)的Ⅱ型三支概念簇，分別為：

屬性a誘導(dǎo)的t(?，a～)={(2，(bd，ace))，(?，(abcde，abcde))}；

屬性b誘導(dǎo)的t(?，b～)={(1，(ace，bd))，(?，(abcde，abcde))}；

屬性c誘導(dǎo)的t(?，c～)={(23，(b，c))，(3，(abe，cd))，(2，(bd，ace))，(?，(abcde，abcde))}；

屬性d誘導(dǎo)的t(?，d～)={(13，(ae，d))，(1，(ace，bd))，(3，(abe，cd))，(?，(abcde，abcde))}；

屬性e誘導(dǎo)的t(?，e～)={(24，(bd，e))，(4，(abcd，e))，(2，(bd，ace))，(?，(abcde，abcde))}.

2.2 三支概念簇的性質(zhì)

三支概念簇是具有家族相似性的三支概念集合，三支概念簇的運(yùn)算在本質(zhì)上是集合的運(yùn)算，首先給出三支概念簇的運(yùn)算性質(zhì).

性質(zhì)2給定一個形式背景K=(G，M，I)，x∈G，a∈M．以下命題成立：

1)t(x，a)=t(x，?)∩t(?，a)；

2)t(x，a～)=t(x，?)∩t(?，a～).

證1) 一方面，t(x，?)由OEL(K)中所有大于等于(x??，x?)且小于等于(G，G?)的三支概念組成．另一方面，t(?，a)由OEL(K)中所有大于等于(?，??)且小于等于(a*，a*?)的三支概念組成．綜合兩個方面，由t(x，a)的定義可知t(x，a)=t(x，?)∩t(?，a)．命題1)成立.

2) 同理可證命題2成立，證畢.

性質(zhì)2實(shí)際上給出了利用對象誘導(dǎo)和屬性誘導(dǎo)的三支概念簇計(jì)算任意三支概念簇的方法．例如，考慮例2中的三支概念簇，利用性質(zhì)2及例2的計(jì)算結(jié)果可得：

t(1，a)=t(1，?)∩t(?，a)={(1，(ace，bd))，(13，(ae，d))，(14，(ac，?))，(134，(a，?))，(1234，(?，?))}∩{(134，(a，?))，(34，(ab，?))，(14，(ac，?))，(13，(ae，d))，(3，(abe，cd))，(1，(ace，bd))，(4，(abcd，e))，(?，(abcde，abcde))}={(1，(ace，bd))，(13，(ae，d))，(14，(ac，?))，(134，(a，?))}.

性質(zhì)3給定一個形式背景K=(G，M，I)，x∈G，a∈M．以下命題成立：

1) 若I(x，a)=0，則t(x，a)=?；

2) 若I(x，a)=1，則t(x，a～)=?；

證1) 若I(x，a)=0，則概念(x??，x?)與(a*，a*?)是不可比的，所以O(shè)EL(K)中不存在大于等于(x??，x?)且小于等于(a*，a*?)的概念，根據(jù)t(x，a)的定義可得t(x，a)=?．命題1)成立.

2) 同理可證命題2成立.

4) 同理可證命題4成立，證畢.

3 基于三支概念簇的知識發(fā)現(xiàn)

在信息檢索的過程中，經(jīng)常會請求系統(tǒng)推薦一類和某種已知對象類似，且具有或不具有某些特殊限定的對象．如在網(wǎng)上購物系統(tǒng)中，顧客通常會要求客服進(jìn)行產(chǎn)品的合理推薦，如：“請給我推薦一款與2號模特上身穿的相似，并且是深藍(lán)色的，但不含拉鏈的外套”，這種需求可以形式化地表述為：用G表示對象的集合，M表示屬性的集合，在G中查找與對象x相似，且具有屬性a，但不具有屬性b的對象.

基于以上討論，下面提出算法1以實(shí)現(xiàn)符合特定約束條件下的相似對象檢索.

算法1基于三支概念簇的相似對象查找算法.

輸入：形式背景K=(G，M，I)，對象x∈G，屬性a，b∈M.

輸出：與對象x相似，且具有屬性a，但不具有屬性b的所有對象.

步驟1：建立形式背景K的對象導(dǎo)出三支概念格OEL(K)；

步驟2：計(jì)算三支概念簇t(?，a)與t(?，b～)；

步驟3：計(jì)算t(?，a)∩t(?，b～)，并記其中全體對象誘導(dǎo)的三支概念的外延為集合E；

步驟4：從概念(x??，x?)開始，逐層遍歷其父概念：

記當(dāng)前遍歷的概念為(X，(A，B))；

若X∩E≠?，則X∩E中包含的對象即為所求.

步驟5：返回結(jié)果，算法結(jié)束.

例3表2描述了一個由8種生物構(gòu)成的形式背景，也就是在形式概念分析理論研究中廣為熟知的“生物和水”形式背景，其對象導(dǎo)出三支概念格如圖2所示．由于所有的生物都需要水，這里不再考慮“需要水”這個生物屬性，只考慮其余的8種生物屬性．用數(shù)字1到8分別代表螞蝗、 魚、 蛙、 狗、 水草、 蘆葦、 豆與玉米．另外，用小寫字母a到h表示8種生物屬性，即：在水中生活、 在陸地生活、 有葉綠素、 雙子葉、 單子葉、 能運(yùn)動、 有四肢與會哺乳.

圖2 例3的對象導(dǎo)出三支概念格

表2 例3的形式背景

為了更好地說明上述提出的基于三支概念簇的相似對象查找算法，我們將通過實(shí)際案例來進(jìn)一步對基于概念簇和三支概念簇的相似對象查找算法進(jìn)行分析對比.

首先，使用上述算法1，查找和蘆葦(對象6)相似，且有葉綠素(具有屬性c)，但不能在陸地生活(不具有屬性b)的生物.

輸入：“生物和水”形式背景，對象6∈G，屬性c，b∈M.

輸出：與對象6相似，且具有屬性c，但不具有屬性b的所有對象.

步驟1：建立“生物和水”形式背景的對象導(dǎo)出三支概念格，如圖2所示；

步驟2：計(jì)算三支概念簇t(?，c)={(?，(abcdefgh，abcdefgh))，(5，(ace，bdfgh))，(6，(abce，dfgh))，(7，(bcd，aefgh))，(8，(bce，adfgh))，(56，(ace，dfgh))，(68，(bce，dfgh))，(78，(bc，afgh))，(568，(ce，dfgh))，(678，(bc，fgh))，(5678，(c，fgh))}，t(?，b～)={(?，(abcdefgh，abcdefgh))，(1，(af，bcdegh))，(2，(afg，bcdeh))，(5，(ace，bdfgh))，(12，(af，bcdeh))，(15，(a，bdgh))，(125，(a，bdh))}；

步驟3：計(jì)算t(?，c)∩t(?，b～)={(?，(abcdefgh，abcdefgh))，(5，(ace，bdfgh))}，并記其中全體對象誘導(dǎo)的三支概念的外延為集合E={5}；

步驟4：從概念(x??，x?)=(6，(abce，dfgh))開始，逐層遍歷其父概念：

遍歷其第一層父概念得到(56，(ace，dfgh))與(68，(bce，dfgh))，由{5，6}∩{5}={5}≠?可知對象5滿足算法要求； 由{68}∩{5}=?可知不滿足算法要求，舍棄； 綜上可得，對象5即為所求.

步驟5：返回結(jié)果對象5，即符合條件的生物是水草，算法結(jié)束.

接下來，使用文獻(xiàn)[27]所提出的基于對象直觀圖與概念簇的相似對象查找算法，查找和蘆葦(對象6)相似，且有葉綠素(具有屬性c)，但不能在陸地生活(不具有屬性b)的生物.

輸入：“生物和水”形式背景，對象6∈G，屬性c，b∈M.

輸出：與對象6相似且具有屬性c的所有對象.

步驟1：建立“生物和水”形式背景的對象直觀圖與概念格，見文獻(xiàn)[27]；

步驟2：在步驟1的對象直觀圖中查找大于等于(6，6*)的所有二元組，可得最大二元組仍為(6，6*)；

步驟3：計(jì)算AC(6，c)=C(6**，c**)={(6，abce)，(56，ace)，(68，bce)，(568，ce)，(678，bc)，(5678，c)}；

步驟4：對于AC(6，c)中存在的概念(56，ace)=(5**，5*)和(68，bce)=(8**，8*)，可得符合條件的對象為5和8；

步驟5：返回結(jié)果對象5和對象8，即符合條件的生物是水草和玉米，算法結(jié)束.

綜上所述，針對同一個案例，對比兩個算法可知，使用基于對象直觀圖與概念簇的算法只能檢索和蘆葦(對象6)相似且有葉綠素(具有屬性c)的生物，無法檢索其中不能在陸地生活(不具有屬性b)的生物，即屬性b無法被按需使用，最終得到的結(jié)果是水草(對象5)和玉米(對象8)．雖然此算法得到兩種結(jié)果，但是根據(jù)常識可知，算法1得到的結(jié)果水草和基于對象直觀圖與概念簇的算法得到的結(jié)果之一玉米相比較更加符合條件．因此，三支概念簇相比較于概念簇，更加有利于檢索到符合需求的對象.

通過深入思考發(fā)現(xiàn)，三支概念簇之所以更加有利于檢索到符合需求的對象，原因在于三支概念不僅考慮了對象共同具有的屬性，而且還考慮了對象共同不具有的屬性，使得三支概念比經(jīng)典形式概念能夠捕捉到更加精確的對象細(xì)節(jié)，從而發(fā)現(xiàn)更加細(xì)致的對象分類，檢索到更加貼切實(shí)際應(yīng)用場景的相似對象.

4 結(jié) 論

本文融合現(xiàn)代范疇理論與三支概念分析，提出了三支概念簇．研究結(jié)果表明，三支概念簇刻畫了具有“家族相似性”的三支概念集合，是檢索符合特定約束條件下相似對象的有力工具．三支概念簇作為三支概念分析中的重要粒度之一，還有許多值得深入探討的問題．例如：模糊形式背景下的模糊概念簇如何定義，與經(jīng)典二值形式背景下的三支概念簇有何區(qū)別與聯(lián)系； 在動態(tài)環(huán)境下，三支概念簇如何更新； 對于大規(guī)模形式背景，如何提高三支概念簇的計(jì)算效率．最后，需要指出的是概念簇建立在形式概念的基礎(chǔ)之上，構(gòu)造概念格的復(fù)雜性限制了其大規(guī)模應(yīng)用的有效性．因此，如何采用新的思路，從新的角度研究概念簇還需要付出更多的努力.