基于粒計(jì)算的概念格拓展模型

康向平, 苗奪謙

(1. 同濟(jì)大學(xué) 電子與信息工程學(xué)院, 上海 201804；2. 同濟(jì)大學(xué) 嵌入式系統(tǒng)與服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室， 上海 201804)

?

基于粒計(jì)算的概念格拓展模型

康向平1,2, 苗奪謙1,2

(1. 同濟(jì)大學(xué) 電子與信息工程學(xué)院, 上海 201804；2. 同濟(jì)大學(xué) 嵌入式系統(tǒng)與服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室， 上海 201804)

摘要：將粒計(jì)算融入到概念格研究中，結(jié)合相似度模型和概念格結(jié)構(gòu)信息，提出一種基于粒計(jì)算的概念格拓展模型，其有助于擴(kuò)展經(jīng)典概念的內(nèi)涵和外延，也有助于壓縮概念的規(guī)模.該模型是概念格和粒計(jì)算融合研究的一次有益探索和嘗試，同時(shí)對(duì)概念格拓展也不失為一種有效手段.

關(guān)鍵詞：概念格； 粒計(jì)算； 關(guān)系粒； ?；拍罡?/p>

德國Wi11e教授于1982年提出了形式概念分析[1]，即概念格理論，該理論是格序論的一個(gè)重要分支，具有良好的數(shù)學(xué)性質(zhì)，主要用于概念的發(fā)現(xiàn)、排序和顯示.在概念格構(gòu)筑的體系中，概念、完備格結(jié)構(gòu)、伽羅瓦連接等是核心要素.從內(nèi)涵和外延2個(gè)不同角度對(duì)概念進(jìn)行刻畫和描述，有助于深化人們對(duì)現(xiàn)實(shí)世界中概念的概要認(rèn)識(shí)和準(zhǔn)確理解；完備格結(jié)構(gòu)作為一種基于序關(guān)系建立起來的概念層次模型，直觀地反映了概念之間的泛化/特化關(guān)系；伽羅瓦連接則是概念格體系的基石.概念格作為一種強(qiáng)有力的數(shù)據(jù)分析工具，受到了學(xué)者的廣泛關(guān)注，其在基礎(chǔ)理論[2-7]、格生成算法[8-9]、規(guī)則獲取[10-14]、屬性約簡[15-16]等方面，以及在不同領(lǐng)域的應(yīng)用[17-18]取得了大量的研究成果.近年來，許多學(xué)者系統(tǒng)研究了概念格與模糊集[19-21]、粗糙集[22-28]、神經(jīng)網(wǎng)絡(luò)[29]、概率論[30]、粒計(jì)算[31-33]等知識(shí)發(fā)現(xiàn)方法之間的聯(lián)系，旨在探索復(fù)雜數(shù)據(jù)處理的新途徑.這種多技術(shù)之間的滲透和交叉，有助于推動(dòng)概念格向深層次和多元化方向發(fā)展.Burusco[21]將模糊集引入概念格，用于度量對(duì)象和屬性之間的不確定性關(guān)系，有助于解決復(fù)雜問題中的模糊信息和不確定信息；Dias等[29]探討了概念格和神經(jīng)網(wǎng)絡(luò)融合理論；Jiang等[30]將概率論引入到概念格中，提出了一種新的數(shù)據(jù)挖掘方法；Yao[28]將粗糙集中的上下近似思想引入到概念格中，探討了概念格中的近似算子；Kang等[32]將粒計(jì)算引入概念格，提出了概念格在不同粒度下的知識(shí)獲取模型，該模型為概念格構(gòu)建和規(guī)則獲取提供了統(tǒng)一的基于模糊?；那蠼夥椒?，不僅可以有效簡化復(fù)雜的概念格結(jié)構(gòu)和壓縮龐大的概念規(guī)模，而且就決策規(guī)則集的完備性和無冗余性做了一些有益的嘗試.關(guān)于概念格的最新相關(guān)研究成果，詳見文獻(xiàn)[34].

在經(jīng)典概念格中，對(duì)于概念的刻畫是精確的.然而，這種精確性在實(shí)際應(yīng)用中可能存在一定的局限性，不利于人們從看似不相關(guān)的數(shù)據(jù)中發(fā)現(xiàn)一些有價(jià)值的信息.在此情況下，就需要考慮進(jìn)一步拓展概念的內(nèi)涵和外延，將概念“可能”包含的一些對(duì)象也納入到其外延中.例如，在地震預(yù)測中，若一些測量結(jié)果符合地震的“大部分”特征而非“全部”特征時(shí)，專家一般提前判定地震可能會(huì)發(fā)生，而不是等到“全部”特征符合后再做出判定.此外，在一些大規(guī)模復(fù)雜的數(shù)據(jù)集中，概念的這種精確性通常會(huì)使知識(shí)獲取過程淹沒在一些不必要的細(xì)節(jié)中，并最終導(dǎo)致海量概念和復(fù)雜的格結(jié)構(gòu)，不利于更好地從整體認(rèn)識(shí)和理解問題.針對(duì)上述問題，本文嘗試引入粒計(jì)算.粒計(jì)算以粒、粒度、粒推理等為核心要素，通過模擬人類思維方式在大規(guī)模復(fù)雜數(shù)據(jù)建模與分析中獨(dú)特的優(yōu)勢(shì)，可以降低知識(shí)獲取的“分辨率”，擴(kuò)大知識(shí)度量的“尺度”，有助于人們對(duì)問題的宏觀認(rèn)識(shí)和理解.

目前，關(guān)于概念格與粒計(jì)算的融合研究還尚不多見[31-33]，據(jù)此，本文將粒計(jì)算融入到概念格研究中，提出了?；拍罡窈土；拍?粒計(jì)算的引入不僅有助于擴(kuò)展經(jīng)典概念的內(nèi)涵和外延，而且也有助于壓縮概念的規(guī)模并簡化復(fù)雜的格結(jié)構(gòu).

1　概念格簡介

形式背景是一個(gè)三元組(G,M,I)，其中G和M是非空有限集，I?G×M是一個(gè)從集合G到集合M的二元關(guān)系.表1是一個(gè)從超市采集的數(shù)據(jù)集，其中1,2,…,9表示顧客編號(hào)；a,b,…,e表示商品編號(hào)，若某位消費(fèi)者購買了某種商品，則用“×”進(jìn)行標(biāo)記.

表1　一個(gè)典型的形式背景

定義1設(shè)K=(G,M,I)是一個(gè)形式背景，A?G,B?M.若A′=B且B′=A，則稱(A,B)是一個(gè)概念，此時(shí)稱A和B分別為概念的外延和內(nèi)涵.其中，算子A′被描述為

相應(yīng)地，算子B′被定義為

對(duì)于任意概念(A1,B1)和(A2,B2)，它們之間的偏序關(guān)系定義為

事實(shí)上，(B(K),≤)是一個(gè)完備格，其中B(K)是一個(gè)由K中所有概念組成的集合.圖1即是表1中的概念格.

圖1　由表1生成的概念格

定義2設(shè)K=(G,M,I)是一個(gè)形式背景，對(duì)于任意g∈G，稱γg為對(duì)象概念，即

對(duì)于任意m∈M，稱μm為屬性概念,即

γ(G)表示由所有對(duì)象概念組成的集合，μ(M)表示由所有屬性概念組成的集合.對(duì)象概念和屬性概念作為概念格中的基礎(chǔ)概念，扮演著重要角色.通常，圖1也可以簡化表示為圖2，其中“m”代表μm，“g”代表γg.

圖2　圖1的簡化概念格

引理2在形式背景K=(G,M,I)中，設(shè)B?M，則

其中，Int(K)是一個(gè)由所有概念內(nèi)涵組成的集合.

關(guān)于概念格的更詳細(xì)介紹，請(qǐng)查閱文獻(xiàn) [2].

2　?；问奖尘?/h2>

概念格的?；举|(zhì)上是形式背景的粒化，據(jù)此，本文探討了形式背景中的對(duì)象粒和關(guān)系粒，并在此基礎(chǔ)上構(gòu)建了?；问奖尘?

2.1相似度模型和對(duì)象粒

在傳統(tǒng)的相似度度量模型中，特征模型是最常見的度量模型之一.特征模型主要包含兩大類，一類是基于公共特征集構(gòu)造的對(duì)稱性特征模型，例如

其中Bi和Bj分別是對(duì)象gi和gj的特征集.另一類是基于差異特征集構(gòu)造的不對(duì)稱性特征模型，例如：

其中，Bi和Bj分別是對(duì)象gi和gj的特征集.該模型同時(shí)引入了共同特征集和差異特征集，相對(duì)于差異特征集，共同特征對(duì)于相似度的影響要更大一些.此外，參數(shù)α和β體現(xiàn)了2個(gè)不同的差異特征集Bi-Bj和Bj-Bi對(duì)于相似度的影響是不對(duì)稱的.

本文研究的重點(diǎn)是對(duì)稱相似度模型，詳見定義3.

定義3在形式背景(G,M,I)中，設(shè)0≤σ≤1，對(duì)于任意gi、gj∈G，定義

表2　模糊相似矩陣

定理1在形式背景(G,M,I)中，對(duì)于任意對(duì)象gi、gj∈G，有下述性質(zhì)成立：

(1) 0≤ρ(gi,gj)≤1.

證明由ρ的定義即得性質(zhì)(1)和(2)成立.

進(jìn)而

顯然，結(jié)論ρ(gi,gj)≤ρ(x,y)成立.

顯然，有結(jié)論ρ(gi,gj)≤ρ(gi,z)成立.類似地，有ρ(gi,gj)≤ρ(gj,z)成立.證畢.

由上述定理可知，本文定義的相似度模型是合理的.事實(shí)上，依據(jù)該模型可以導(dǎo)出一個(gè)模糊相似關(guān)系矩陣

λ的值越小，相應(yīng)G中的對(duì)象粒就越大.一個(gè)從表2導(dǎo)出的模糊等價(jià)矩陣如表3所示.在表3中，當(dāng)λ=0.8時(shí)，有

其中，[1]=[4]=[8]={1,4,8}，[2]=[7]={2,7}，[3]=[6]=[9]={3,6,9}，[5]={5}.

表3　模糊等價(jià)矩陣

2.2關(guān)系粒和粒化形式背景

本節(jié)將重點(diǎn)探討關(guān)系粒和?；尘?，其中關(guān)系粒在粒化背景中扮演了重要角色.

定義4設(shè)K=(G,M,I)是一個(gè)形式背景，對(duì)于任意g∈G,m∈M，稱[g]×m∈Gλ×M是一個(gè)關(guān)系粒；若Iλ?Gλ×M，則稱Kλ=(Gλ,M,Iλ)是K的一個(gè)?；问奖尘?

由上述定義可知，任意關(guān)系粒[g]×m是否滿足([g],m)∈Iλ，對(duì)于構(gòu)造?；尘爸陵P(guān)重要，需要給出科學(xué)合理的判定準(zhǔn)則.據(jù)此，本文提出了兩類不同的判定方法，即一類是基于形式背景K的判定方法，另一類是基于概念格(B(K),≤)的判定方法.

定義5在形式背景(G,M,I)中，對(duì)于任意[g]×m∈Gλ×M，定義

其中ηλ是一個(gè)可信度函數(shù).

顯然，ηλ越大，([g],m)∈Iλ的可信度就越高；ηλ越小，([g],m)?Iλ的可信度就越高.據(jù)此，引入?yún)?shù)0≤δ≤1，并將其作為判定([g],m)∈Iλ是否可信的閾值.依據(jù)實(shí)際需要，用戶可以靈活調(diào)整閾值參數(shù).

準(zhǔn)則1對(duì)于粒[g]×m，若ηλ(g,m)≥δ，則([g],m)∈Iλ；若ηλ(g,m)≥/δ，則([g],m)?Iλ.

例如，基于準(zhǔn)則1，由表1可以導(dǎo)出如表4所示的粒化形式背景，其中λ=0.8且δ=0.6.

表4　基于準(zhǔn)則1導(dǎo)出的表1的粒化背景

引理3設(shè)(G,M,I)是一個(gè)形式背景，對(duì)于任意g∈G和m∈M，(g,m)∈I當(dāng)且僅當(dāng)γg≤μm.

準(zhǔn)則2_a設(shè)[g]×m是一個(gè)關(guān)系粒，對(duì)于?g1∈[g]，如果γg1≤μm，那么([g],m)∈Iλ；如果存在g1∈[g]滿足γg1≤/μm，那么([g],m)?Iλ.

上述準(zhǔn)則等價(jià)于如下關(guān)系：

若ηλ(g,m)=1，則([g],m)∈Iλ；若ηλ(g,m)≠1，則([g],m)?Iλ.

由上述討論可知，準(zhǔn)則2_a是準(zhǔn)則1的一種特殊情況，但其判定條件較準(zhǔn)則1太過苛刻，無助于用戶從看似不相關(guān)的數(shù)據(jù)中發(fā)現(xiàn)有價(jià)值的信息.據(jù)此，可以借助下確界運(yùn)算“∧”將準(zhǔn)則2_a進(jìn)一步弱化為準(zhǔn)則2_b和2_c.

準(zhǔn)則2_b設(shè)[g]×m是一個(gè)關(guān)系粒，若∧γ([g])≤μm，則([g],m)∈Iλ；若∧γ([g]) ≤/μm，則([g],m)?Iλ.

準(zhǔn)則2_c設(shè)[g]×m是一個(gè)關(guān)系粒，若∧γ([g])≤/μm，則([g],m)?Iλ.當(dāng)∧γ([g])≤μm時(shí)，若滿足下述條件：

則([g],m)∈Iλ；若滿足下述條件：

則([g],m)?Iλ，其中|H|=2.

在上述基于概念格結(jié)構(gòu)信息的判定準(zhǔn)則中，由于∧γ([g])≤∧γ(H)≤γg≤μm，其中H?[g]，顯然，若作為判定條件，∧γ(H)≤μm要弱于γg≤μm，但強(qiáng)于∧γ([g])≤μm.即準(zhǔn)則2_c判定條件的強(qiáng)弱介于準(zhǔn)則2_b和準(zhǔn)則2_a之間.尤其是當(dāng)|[g]|較大時(shí)，準(zhǔn)則2_b中的判定條件∧γ([g])≤μm將弱化，此時(shí)相應(yīng)的判定結(jié)果有可能是不合理的.本質(zhì)上，定理2和定理3可以從可信度函數(shù)的角度客觀地反映準(zhǔn)則2_c的合理性.

定理2在K=(G,M,I)中，設(shè)A?G,m∈M，有下述結(jié)論成立：

(1) 若∧γ(A)≤/μm，則(A×m)∩I=?.

(2) 若存在g∈A，滿足(g,m)∈I，則∧γ(A)≤μm.

證明：當(dāng)∧γ(A)≤/μm時(shí)，假設(shè)存在g∈A滿足(g,m)∈I，則由引理3即得γg≤μm，進(jìn)而由∧γ(A)≤/γg可導(dǎo)出∧γ(A)≤μm，與條件∧γ(A)≤/μm相矛盾！故結(jié)論(1)成立.

當(dāng)(g,m)∈I時(shí)，由引理3可知γg≤μm，進(jìn)而由∧γ(A)≤γg即得結(jié)論(2)成立.證畢.

定理3在定理2中，有下述結(jié)論成立：

(1) 若∧γ(A)≤/μm，則ηλ(g,m)=0.

(2) 若ηλ(g,m)>0，則∧γ(A)≤μm.

(3) 設(shè)A、H?G，若H?A，則∧γ(A)≤∧γ(H).

證明：由定義5和定理2即得結(jié)論(1)和(2)成立.結(jié)論(3)由上、下確界的定義即得，在此不再詳述.證畢.

在基于準(zhǔn)則2_a、2_b或2_c的判定過程中，用戶可以借助概念格(B(K),≤)的Hasse圖，即概念格的結(jié)構(gòu)信息，直觀生動(dòng)地判定任意關(guān)系粒[g]×m是否滿足([g],m)∈Iλ.相對(duì)于準(zhǔn)則2_a和準(zhǔn)則2_b，用戶選擇準(zhǔn)則2_c得到的判定結(jié)果可能會(huì)更合理一些，因?yàn)闇?zhǔn)則2_a的判定條件太強(qiáng)，不利于用戶從看似不相關(guān)的數(shù)據(jù)中發(fā)現(xiàn)有價(jià)值的信息，而準(zhǔn)則2_b的判定條件太弱，可能無法為構(gòu)造?；尘疤峁└涌茖W(xué)合理的依據(jù).

以準(zhǔn)則2_c為例，當(dāng)λ=0.8且δ=0.6時(shí)，基于圖2所示的格結(jié)構(gòu)信息，用戶可以從表1導(dǎo)出如表5所示的?；尘?例如，在圖3中，對(duì)于關(guān)系粒[1]×d，由于γ1∧γ8=γ1=γ8、γ1∧γ4=γ1、γ4∧γ8=γ8，且γ1∧γ4、γ1∧γ8、γ4∧γ8均小于μd，由此可以判定([1],d)∈Iλ；對(duì)于關(guān)系粒[3]×e，由于γ3∧γ9=γ3=γ9且γ3∧γ9≤/μe，所以判定([3],e)?Iλ.

表5　基于準(zhǔn)則2_c從表1導(dǎo)出的?；尘?/p>

3　?；拍詈土；拍罡?/h2>

在?；尘癒λ=(Gλ,M,Iλ)中，對(duì)于任意對(duì)象粒集Aλ?Gλ和屬性集B?M，定義1中的算子可以形式化描述為

稱完備格(B(Kλ),≤)是(B(K),≤)的一個(gè)λ?；拍罡瘢渲蠦(Kλ)是Kλ中所有λ?；拍罱M成的集合.例如，由表4可以導(dǎo)出一個(gè)如圖3所示的概念格結(jié)構(gòu)，該結(jié)構(gòu)是圖1所示概念格的一個(gè)?；拍罡?

圖3　由表4生成的?；拍罡?/p>

由上述討論可知，?；问奖尘爸械乃阕邮腔趯?duì)象粒定義的，雖然其與定義1中的算子形式上存在一定差異，但本質(zhì)上它們屬于同一類算子.

4　約簡、核和蘊(yùn)涵規(guī)則

約簡、核、蘊(yùn)涵規(guī)則等是概念格中常見的問題，本節(jié)將重點(diǎn)就上述問題給出一種基于粒化概念的求解方法.

定義6在K=(G,M,I)中，設(shè)B?M，如果m∈B且B′≠(B-m)′，則稱m是B中的核屬性，設(shè)D?B?M，若D是滿足B′=D′的最小屬性子集，則稱D是B的一個(gè)約簡；設(shè)B、D?M，稱B→D是K中的蘊(yùn)涵規(guī)則，簡稱規(guī)則.當(dāng)B′?D′時(shí)，稱B→D是一條確定規(guī)則；當(dāng)B′D′時(shí)，稱B→D是一條不確定規(guī)則.

定理4在Kλ=(Gλ,M,Iλ)中，對(duì)于任意B?M，記

若Int(Kλ)是一個(gè)由所有λ?；拍顑?nèi)涵組成的集合，則B+=B″.

證明：由引理2即得.證畢.

定理5在Kλ=(Gλ,M,Iλ)中，設(shè)m∈B?M，若Eλ≠Fλ，則m是B中的核屬性.其中，(Eλ,B+)∈B(Kλ)且(Fλ,(B-m)+)∈B(Kλ).

證明：由(Eλ,B+)∈B(Kλ)可知Eλ=(B+)′，進(jìn)而由定理4可知Eλ=B?=B′.同理可證Fλ=(B-m)′.由于Eλ≠Fλ，所以B′≠(B-m)′.顯然，由定義6即得結(jié)論成立.證畢.

定理6在Kλ=(Gλ,M,Iλ)中，設(shè)D?B?M，若D是滿足Eλ=Fλ的最小集合，則D是B的一個(gè)約簡，其中(Eλ,B+)∈B(Kλ)且(Fλ,D+)∈B(Kλ).

證明：由(Eλ,B+)∈B(Kλ)可知Eλ=(B+)′，進(jìn)而由定理4可知Eλ=B?=B′.同理可證Fλ=D′.由于Eλ=Fλ，所以B′=D′，又由于D是滿足B′=D′的最小集合，故由定義6即得結(jié)論成立.證畢.

概念格非常適合發(fā)現(xiàn)一些有價(jià)值的規(guī)則型知識(shí)，置信度和支持度是對(duì)規(guī)則的重要補(bǔ)充和定量描述.通常，在形式背景K=(G,M,I)中，就某條規(guī)則B→D而言，其置信度是指在B出現(xiàn)的條件下，D出現(xiàn)的概率，通常被形式化描述為

如果Conf(B→D)=1，則說明當(dāng)B出現(xiàn)時(shí)，D一定會(huì)出現(xiàn).如果置信度太低，則說明B和D之間的關(guān)系較弱，B→D在實(shí)際應(yīng)用中的價(jià)值不高.支持度本質(zhì)上揭示了B與D同時(shí)出現(xiàn)的概率，通常被形式化描述為

如果支持度較高，則說明B與D在一定程度上是相關(guān)的.事實(shí)上，在實(shí)際應(yīng)用中，用戶往往會(huì)對(duì)置信度和支持度提出一定的要求，進(jìn)而獲取置信度和支持度較高的規(guī)則.

基于上述討論，關(guān)于規(guī)則的置信度和支持度，本文給出了基于對(duì)象粒Gλ的定義.

定義7在Kλ=(G,M,Iλ)中，對(duì)于任意規(guī)則B→D，其置信度和支持度分別定義為

其中，(Eλ,B+)∈B(Kλ)且(Fλ,D+)∈B(Kλ).

例如，在表4中，對(duì)于規(guī)則c→de，由于([1][3][5],c)和([1],de)是λ?；拍?，又{c}+={c}且{d,e}+={a,c,d,e}，故有

通常，形式背景中存在著大量的冗余規(guī)則，往往導(dǎo)致一些有價(jià)值的規(guī)則被淹沒在海量的規(guī)則中.一些常見的確定的冗余規(guī)則有：若B?B1且D1?D，則B1→D1相對(duì)于確定規(guī)則B→D是冗余的，此時(shí)稱B1→D1是一條相對(duì)冗余規(guī)則；若D?B，稱B→D是一條絕對(duì)冗余規(guī)則.

基于上述討論，在一個(gè)粒化形式背景中，可以刪除一些絕對(duì)冗余規(guī)則和相對(duì)冗余規(guī)則，并最終得到一個(gè)規(guī)模較小的確定規(guī)則集，稱為源規(guī)則集.例如，表1和4中源規(guī)則集如表6所示.

表6　源規(guī)則集

5　結(jié)論及展望

把粒計(jì)算融入概念格研究中，通過降低知識(shí)獲取的“分辨率”，擴(kuò)大知識(shí)度量的“尺度”，有助于人們從不相關(guān)的數(shù)據(jù)中發(fā)現(xiàn)一些潛在的有價(jià)值信息，而且也能有效簡化復(fù)雜的格結(jié)構(gòu)和壓縮概念的規(guī)模.在?；^程中，提出了一種新的基于概念基的求解思路.所謂概念基是指一個(gè)由低層概念構(gòu)成的集合，其在信息?；恼麄€(gè)過程中扮演了重要的角色.特別地，在信息?；^程中，還提出了一種基于下確界運(yùn)算的求解思路，它與傳統(tǒng)模型最大的區(qū)別是融合了概念格的結(jié)構(gòu)信息.

總之，本文把粒計(jì)算引入到概念格研究中，對(duì)于概念格的拓展不失為一種有效的手段，理論和實(shí)例證明了本文提出的結(jié)論的合理性和有效性.雖然概念格是數(shù)據(jù)分析的有效工具，但面對(duì)規(guī)模龐大的數(shù)據(jù)集以及復(fù)雜的知識(shí)發(fā)現(xiàn)任務(wù)，在實(shí)際應(yīng)用中仍存在著許許多多的問題.本文的研究工作僅僅是一個(gè)嘗試，關(guān)于粒計(jì)算與概念格的融合理論還有待進(jìn)一步深入.

參考文獻(xiàn):

[1]Wille R. Restructuring lattice theory: an approach based on hierarchies of concepts [C]∥Ordered Sets. Dordrecht: Reidel, 1982: 445-470.

[2]Ganter B, Wille R. Formal concept analysis: mathematical foundations [M]. Berlin: Springer-Verlag, 1999.

[3]Li J H, Mei C L, Lü Y J. Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction [J]. International Journal of Approximate Reasoning, 2013, 54(1): 149.

[4]薛金蓉, 安秋生, 鄭軍. 概念格的內(nèi)涵縮減與數(shù)據(jù)庫推理依賴[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(1): 96.

XUE Jinrong, AN Qiusheng, ZHENG Jun. Intent reduction of concept lattice and database inference dependence [J]. Journal of Computer Research and Development, 2014, 51(1): 96.

[5]楊麗, 徐揚(yáng). 基于邏輯合取的語言真值概念格合并算法[J]. 電子學(xué)報(bào), 2013, 41(11): 2149.

YANG Li, XU Yang. Union algorithm of linguistic truth-valued concept lattice based on logical conjunction [J]. ACTA Electronica Sinica, 2013, 41(11): 2149.

[6]智慧來, 智東杰, 劉宗田. 概念格合并原理與算法[J]. 電子學(xué)報(bào), 2010, 38(2): 455.

ZHI Huilai, ZHI Dongjie, LIU Zongtian. Theory and algorithm of concept lattice union [J]. ACTA Electronica Sinica, 2010, 38(2): 455.

[7]張磊, 張宏莉, 殷麗華, 等. 概念格的屬性漸減原理與算法研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(2): 248.

ZHANG Lei, ZHANG Hongli, YIN Lihua,etal. Theory and algorithms of attribute decrement for concept lattice [J]. Journal of Computer Research and Development, 2013, 50(2): 248.

[8]謝志鵬, 劉宗田. 概念格的快速漸進(jìn)式構(gòu)造算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2002, 25(5): 490.

XIE Zhipeng, LIU Zongtian. A fast incremental algorithm for building concept lattice [J]. Chinese Journal of Computers, 2002, 25(5): 490.

[9]劉宗田, 強(qiáng)宇, 周文, 等. 一種模糊概念格模型及其漸進(jìn)式構(gòu)造算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2007, 30(2): 184.

LIU Zongtian, QIANG Yu, ZHOU Wen,etal. A fuzzy concept lattice model and its incremental construction algorithm [J]. Chinese Journal of Computers, 2007, 30(2): 184.

[10]Zhai Y H, Li D Y, Qu K S. Fuzzy decision implications [J]. Knowledge-Based Systems, 2013, 37: 230.

[11]Zhai Y H, Li D Y, Qu K S. Decision implication canonical basis: a logical perspective [J]. Journal of Computer and System Sciences, 2015, 81: 208.

[12]胡可云,陸玉昌,石純一. 基于概念格的分類和關(guān)聯(lián)規(guī)則的集成挖掘方法[J]. 軟件學(xué)報(bào), 2000, 11(11): 1478.

HU Keyun, LU Yuchang, SHI Chunyi. An integrated mining approach for classification and association rule based on concept lattice [J]. Journal of Software, 2000, 11(11): 1478.

[13]梁吉業(yè), 王俊紅. 基于概念格的規(guī)則產(chǎn)生集挖掘算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2004, 41(8): 1339.

LIANG Jiye, WANG Junhong. An algorithm for extracting rule-generating sets based on concept lattice [J]. Journal of Computer Research and Development, 2004, 41(8): 1339.

[14]馬垣, 張學(xué)東, 遲呈英. 緊致依賴與內(nèi)涵虧值[J]. 軟件學(xué)報(bào), 2011, 22(5): 962.

MA Yuan, ZHANG Xuedong, CHI Chengying. Compact dependencies and intent waned values [J]. Journal of Software, 2011, 22(5): 962.

[15]Mi J S, Leung Y, Wu W Z. Approaches to attribute reduction in concept lattices induced by axialities [J]. Knowledge-Based Systems, 2010, 23(6): 504.

[16]張文修, 魏玲, 祁建軍. 概念格的屬性約簡理論與方法[J]. 中國科學(xué): E輯, 2005, 35(6): 628.

ZHANG Wenxiu, WEI Ling, QI Jianjun. Attribute reduction theory and approach to concept lattice [J]. Science in China: Series E, 2005, 35(6): 628.

[17]李沖, 曹吉鳴, 馬騰. 基于形式概念分析的項(xiàng)目成員綜合相似度計(jì)算[J]. 同濟(jì)大學(xué)學(xué)報(bào):自然科學(xué)版, 2014, 42(6): 983.

LI Chong, CAO Jiming, MA Teng. Integrated similarity calculation of project members based on formal concept analysis [J]. Journal of Tongji University: Natural Science, 2014, 42(6): 983.

[18]李立峰, 張東曉. 概念格在二值命題邏輯命題集約簡中的應(yīng)用[J]. 電子學(xué)報(bào), 2007, 35(8): 1538.

LI Lifeng, ZHANG Dongxiao. The application of concept lattice theory in the reduction of the proposition set in two-valued propositional logic [J]. ACTA Electronica Sinica, 2007, 35(8): 1538.

[19]Shao M W, Liu M, Zhang W X. Set approximations in fuzzy formal concept analysis [J]. Fuzzy Sets and Systems, 2007, 158(23): 2627.

[20]Kang X P, Li D Y, Wang S G,etal. Formal concept analysis based on fuzzy granularity base for different granulations [J]. Fuzzy Sets and Systems, 2012, 203: 33.

[21]Burusco A, Fuentes-Gonzales R. Construction of the L-fuzzy concept lattice [J]. Fuzzy Sets and Systems, 1998, 97:109.

[22]Wei L, Qi J J. Relation between concept lattice reduct and rough set reduct [J]. Knowledge-Based Systems, 2010, 23(8): 934.

[23]Kang X P, Li D Y, Wang S G,etal. Rough set model based on formal concept analysis [J]. Information Sciences, 2013, 222: 611.

[24]Chen J K, Li J J, Lin Y J,etal. Relations of reduction between covering generalized rough sets and concept lattices [J]. Information Sciences, 2015, 304: 16.

[25]仇國芳, 張志霞, 張煒. 基于粗糙集方法的概念格理論研究綜述[J]. 模糊系統(tǒng)與數(shù)學(xué), 2014, 28(1): 168.

QIU Guofang, ZHANG Zhixia, ZHANG Wei. A survey for study on concept lattice theory via rough set [J]. Fuzzy Systems and Mathematics, 2014, 28(1): 168.

[26]Lai H L，Zhang D X．Concept lattices of fuzzy contexts: formal concept analysis vs．rough set theory [J]．International Journal of Approximate Reasoning, 2009, 50: 695.

[27]Wang L D, Liu X D. Concept analysis via rough set and AFS algebra [J]. Information Sciences, 2008, 178:4125.

[28]Yao Y Y. Concept lattices in rough set theory [C] // Proceedings of the 2004 IEEE Annual Meeting of the North American Fuzzy Information Processing Society (NAFIPS04). Piscataway: IEEE, 2004: 796.

[29]Dias S M, Nogueira B M, Zarate L E. Adaptation of FCANN method to extract and represent comprehensible knowledge from neural networks [J]. Studies in Computational Intelligence, 2008, 134:163.

[30]Jiang L, Deogun J. SPICE: a new frame work for data mining based on probability logic and formal concept analysis [J]. Fundamenta Informaticae, 2007, 78: 467.

[31]仇國芳, 馬建敏, 楊宏志, 等. 概念粒計(jì)算系統(tǒng)的數(shù)學(xué)模型[J]. 中國科學(xué): E輯, 2009, 39 (12): 1239.

QIU Guofang, MA Jianmin, YANG Hongzhi,etal. Mathematical model of concept granule computing system [J]. Science in China: Series E, 2009, 39(12): 1239.

[32]Kang X P, Li D Y, Wang S G. Research on domain ontology in different granulations based on concept lattice [J]. Knowledge-Based Systems, 2012, 27: 152.

[33]Wu W Z, Leung Y, Mi J S. Granular computing and knowledge reduction in formal contexts [J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(10): 1461.

[34]Sarmah A K, Hazarika S M, Sinha S K. Formal concept analysis: current trends and directions [J]. Artificial Intelligence Review, 2015, 44(1): 47.

[35]Lee H S. An optimal algorithm for computing the max-min transitive closure of a fuzzy similarity matrix [J]. Fuzzy Sets and Systems, 2001, 123: 129.

收稿日期：2015-08-11

基金項(xiàng)目：國家自然科學(xué)基金(61273304,61202170)；中國博士后科學(xué)基金(2014M560352)；教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20130072130004)

通訊作者：苗奪謙(1964─)，男，教授、博士生導(dǎo)師，工學(xué)博士，主要研究方向?yàn)橹悄苄畔⑻幚?、人工智能與模式識(shí)別、數(shù)據(jù)挖掘、粗糙集、粒計(jì)算等.E-mail:miaoduoqian@163.com

中圖分類號(hào)：TP182

文獻(xiàn)標(biāo)志碼：A

Expanded Concept Lattice Based on Granular Computing

KANG Xiangping1,2, MIAO Duoqian1,2

(1. College of Electronics and Information Engineering, Tongji University, Shanghai 201804, China; 2. Key Laboratory of Embedded System and Service Computing of the Ministry of Education, Tongji University, Shanghai 201804, China)

Abstract：By introducing granular computing into concept lattice, and integrating similarity measure model and structure information of concept lattice, the paper proposes an expanded concept lattice model based on granular computing. It can help to expand intent and extent of classical concept, and also can effectively reduce the scale of concepts to some extent. The model is not only a useful attempt and exploration for the fusion of these two theories, but also an effective means of expanding the classical concept lattice.

Key words：concept lattice; granular computing; relation granules; granulation concept lattice

第一作者： 康向平(1982─)，男，工學(xué)博士，主要研究方向?yàn)楦拍罡瘛⒋植诩?、粒?jì)算等.E-mail:tongji_kangxp@sina.com