王啟君 林藝東 林夢(mèng)雷,2 寇 毅
“概念”一詞來(lái)源于哲學(xué),是外延與內(nèi)涵的統(tǒng)一.概念學(xué)習(xí)理論作為粗糙集理論的高度補(bǔ)充,在規(guī)則提取、對(duì)象分類等領(lǐng)域具有廣泛的應(yīng)用價(jià)值[1-5].經(jīng)典概念通過(guò)內(nèi)涵和外延描述同類事物的本質(zhì)特征,為概念學(xué)習(xí)提供數(shù)學(xué)基礎(chǔ)[6-13].其中,對(duì)象(外延)和屬性(內(nèi)涵)的關(guān)系是分明的,即屬性是否為對(duì)象所擁有.然而在實(shí)際應(yīng)用中,對(duì)象與屬性之間的關(guān)系通常是模糊的、不確定的,連續(xù)型數(shù)據(jù)只有通過(guò)離散化預(yù)處理才能進(jìn)行經(jīng)典概念學(xué)習(xí),這期間往往會(huì)造成信息丟失[8-10].
作為經(jīng)典概念的擴(kuò)展,模糊概念能處理連續(xù)型數(shù)據(jù),通過(guò)把屬性值轉(zhuǎn)換為對(duì)象的隸屬度以刻畫概念,不僅降低由于離散化產(chǎn)生的耗時(shí),并且保留原始信息[2,5,14-15].目前,已有許多學(xué)者在信息描述、模式識(shí)別與概念聚類等方面進(jìn)行相關(guān)研究[2,9,12,14].Cross等[14]對(duì)比單邊閾值方法和模糊閉包算子方法分別產(chǎn)生的模糊概念格,發(fā)現(xiàn)前者概念的外延是后者外延的子集.Xu等[11]基于粒計(jì)算提出雙向概念認(rèn)知模型,能有效處理實(shí)際問(wèn)題中的模糊知識(shí).
隨著科學(xué)技術(shù)的發(fā)展,尤其是數(shù)據(jù)科技和人工智能的興起,概念認(rèn)知學(xué)習(xí)理論(Concept-Cognitive Learning, CCL)逐漸成為認(rèn)知科學(xué)、腦科學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域的研究熱點(diǎn).CCL的主要思想是通過(guò)具體的認(rèn)知模型從給定線索中進(jìn)行概念學(xué)習(xí),揭示人腦概念學(xué)習(xí)的系統(tǒng)性規(guī)律.然而,在自然條件下,概念學(xué)習(xí)容易受到認(rèn)知環(huán)境和個(gè)體認(rèn)知水平等因素的影響[2,16-19].李金海等[17]提出概念的漸進(jìn)式認(rèn)知理論與方法,處理不完全認(rèn)知條件下的概念獲取問(wèn)題.在概念認(rèn)知學(xué)習(xí)理論的發(fā)展過(guò)程中,李金海等[18]對(duì)概念認(rèn)知的公理化、概念認(rèn)知系統(tǒng)、概念認(rèn)知過(guò)程等問(wèn)題進(jìn)行進(jìn)一步思考與研究.徐偉華等[19]提出模糊三支算子,用于討論模糊三支概念的概念認(rèn)知學(xué)習(xí)方法.
為了克服認(rèn)知環(huán)境的限制,一些學(xué)者研究基于進(jìn)化計(jì)算的概念學(xué)習(xí)方法,并通過(guò)實(shí)驗(yàn)驗(yàn)證其有效性[2,3,16,20-28].Mukhopadhyay等[20]提出多目標(biāo)進(jìn)化算法,解決工程中的多目標(biāo)問(wèn)題.Dragoni[21]基于概念域,提出多域情感分析進(jìn)化策略.為了提高概念學(xué)習(xí)的效率和靈活性,Li等[8]從認(rèn)知計(jì)算的角度討論基于粒計(jì)算的概念學(xué)習(xí).Mi等[2]考慮個(gè)體認(rèn)知水平和認(rèn)知環(huán)境的限制,從概念聚類角度闡述模糊概念.
大型數(shù)據(jù)集的時(shí)限性、多樣性、復(fù)雜性等因素使高效計(jì)算概念空間成為必要.為了降低概念認(rèn)知學(xué)習(xí)過(guò)程的復(fù)雜度,Shi等[22]利用并行計(jì)算,提高概念認(rèn)知學(xué)習(xí)效率.Zhang等[23]基于屬性拓?fù)湓O(shè)計(jì)概念更新算法.Tsang等[3]提出多層次認(rèn)知機(jī)制.Wang等[24]利用特征之間的相關(guān)性設(shè)計(jì)具有認(rèn)知推理能力的分類模型.
概念的構(gòu)建和概念空間的更新是概念認(rèn)知學(xué)習(xí)中影響學(xué)習(xí)效率的兩個(gè)重要因素.對(duì)于動(dòng)態(tài)分類問(wèn)題,Yan等[25]基于三支偏序結(jié)構(gòu)圖,提出增量概念認(rèn)知學(xué)習(xí)方法.Mi等[26]從概念認(rèn)知計(jì)算系統(tǒng)的視角出發(fā),實(shí)現(xiàn)對(duì)數(shù)據(jù)的動(dòng)態(tài)分類.Xu等[27]考慮注意力對(duì)概念認(rèn)知的影響,提出多注意概念認(rèn)知學(xué)習(xí)模型.為了去除一些不必要信息的影響,根據(jù)概念內(nèi)涵之間的差異性,Yuan等[28]提出基于漸進(jìn)模糊三支概念的增量學(xué)習(xí)機(jī)制,卻忽略先驗(yàn)決策信息對(duì)概念認(rèn)知的影響,導(dǎo)致部分有效信息的丟失.
受文獻(xiàn)[28]的啟發(fā),本文利用先驗(yàn)決策信息,提出基于決策重要度的概念認(rèn)知學(xué)習(xí)模型.首先,引入余弦相似度構(gòu)造鄰域粒,生成相應(yīng)的模糊概念空間.考慮到個(gè)體認(rèn)知的局限性和認(rèn)知環(huán)境的不完全性,進(jìn)一步構(gòu)建漸進(jìn)模糊概念空間.由于不同決策對(duì)對(duì)象的影響程度不同,通過(guò)漸進(jìn)模糊概念的外延得到某一決策對(duì)該概念的決策重要度和置信度,以此討論概念分類,并設(shè)計(jì)相似性度量指標(biāo).最后,通過(guò)實(shí)驗(yàn)驗(yàn)證本文模型的有效性.
本節(jié)主要回顧模糊形式背景和模糊概念的定義[28].
在形式概念分析中,將概念定義為由內(nèi)涵和外延組成的二元組.符合概念的全體對(duì)象的集合稱為概念的外延,此集合全體對(duì)象共有的屬性稱為概念的內(nèi)涵.然而,經(jīng)典形式背景下只能判斷一個(gè)對(duì)象是否具有某個(gè)屬性.若具有,為1;否則為0.但現(xiàn)實(shí)生活中很多問(wèn)題不能通過(guò)絕對(duì)真1和絕對(duì)假0來(lái)刻畫,而模糊形式背景可通過(guò)對(duì)象對(duì)屬性的擁有程度處理模糊狀態(tài)下的部分問(wèn)題.
?;橇S?jì)算的基本問(wèn)題.在模糊形式背景中,對(duì)象的相似度通常使用其屬性之間的距離進(jìn)行刻畫.本文利用相似度描述對(duì)象之間的鄰域關(guān)系,以此構(gòu)造模糊概念空間.
為對(duì)象xi、xj之間的余弦相似性.顯然,cos(xi,xj)∈[0,1],當(dāng)對(duì)象的余弦相似性大于某值時(shí),認(rèn)為它們相似度較高,越趨近1,表示兩個(gè)對(duì)象的方向越接近.在本文中,引入?yún)?shù)δ,由此得到每個(gè)對(duì)象的鄰域粒.
模糊概念空間為C={C1,C2,…,Cl},每個(gè)Ci稱為C的第i個(gè)子空間.同時(shí),注意到δ值會(huì)影響鄰域粒的大小,不同對(duì)象集的最小隸屬度會(huì)不同,進(jìn)而內(nèi)涵會(huì)隨外延變化而變化,因此模糊概念會(huì)受到δ值的影響.此外,本文提出的對(duì)象分類機(jī)制是基于模糊概念的,因此δ將進(jìn)一步影響模型目標(biāo)分類性能.在算法1中給出模糊概念空間的構(gòu)造過(guò)程.
算法1構(gòu)造模糊概念空間
輸出模糊概念空間C
令Ci←?;
forx∈X
end
例1表1為包含10個(gè)對(duì)象和2個(gè)屬性的模糊決策形式背景,對(duì)象被b1和b2描述.
在模糊決策形式背景下,令δ=0.95,根據(jù)定義5,得到相應(yīng)鄰域粒:
進(jìn)而得到模糊概念子空間:
C1=({x1,x2,x4},(0.04,0.47)),
C2=({x1,x2,x4,x5},(0.04,0.47)),
C3=({x3,x5,x6},(0.28,0.47)),
C4=({x2,x3,x5,x6},(0.11,0.47)),
C5=({x7,x9},(0.68,0.11)),
C6=({x8,x9,x10},(0.75,0.32)),
C7=({x7,x8,x9,x10},(0.68,0.11)).
模糊概念空間C={C1,C2,…,C7}.
表1 模糊決策形式背景Table1 Fuzzy formal decision context
在模糊概念空間中,概念之間相互影響,甚至存在大量的重復(fù)信息.與此同時(shí),由于個(gè)體認(rèn)知的局限性和認(rèn)知環(huán)境的不完全性,概念認(rèn)知通常是漸進(jìn)的.因此,為了提高認(rèn)知的準(zhǔn)確性,在原有模糊概念空間的基礎(chǔ)上構(gòu)建對(duì)應(yīng)的漸進(jìn)模糊概念空間.
稱Pi=(Qi,Gi)為漸進(jìn)模糊概念空間.
在漸進(jìn)概念的學(xué)習(xí)過(guò)程中,不同子概念的內(nèi)涵根據(jù)其相應(yīng)外延大小被賦予不同的權(quán)重.子概念對(duì)新概念生成的影響隨外延的增加而增大.同時(shí),所有概念的權(quán)重之和為1,即總效應(yīng)之和為1.因此,在算法2中給出選擇上確界概念和獲取漸進(jìn)模糊概念空間的詳細(xì)過(guò)程.
算法2構(gòu)造漸進(jìn)模糊概念空間
輸入模糊概念空間C={C1,C2,…,Cl}
輸出漸進(jìn)模糊概念空間P={P1,P2,…,Pl}
投身脫貧攻堅(jiān)的青春身影,把希望和信心帶進(jìn)大山深處;“腦洞”大開(kāi)的創(chuàng)業(yè)團(tuán)隊(duì),為放飛夢(mèng)想努力打拼;風(fēng)華正茂的年輕法官,甘當(dāng)法治建設(shè)的“燃燈者”;激情滿懷的青年人才,扛起航天報(bào)國(guó)的千鈞重?fù)?dān);沙場(chǎng)練兵的勇毅戰(zhàn)士,用方剛血?dú)庵鸨<倚l(wèi)國(guó)的鋼鐵長(zhǎng)城……
for Ci∈C
Ci∈Ci-S;
else
end
end
end
計(jì)算漸進(jìn)模糊概念(Qi,Gi);
Pi←(Qi,Gi);
end
end
例2(接例1) 根據(jù)定義7,由例1中模糊概念進(jìn)一步得到漸進(jìn)模糊概念:
P1=({x1,x2,x4,x5},(0.04,0.47)), P2=({x2,x3,x5,x6},(0.195,0.47)), P3=({x7,x8,x9,x10},(0.6975,0.1625)).
面向動(dòng)態(tài)環(huán)境,如何基于概念空間識(shí)別新增對(duì)象的類標(biāo)簽是一個(gè)值得探討的問(wèn)題.為了解決此問(wèn)題,本文提出決策重要度和置信度,再充分融合二者信息,提出概念認(rèn)知學(xué)習(xí)模型.
在動(dòng)態(tài)環(huán)境中,原有決策信息會(huì)對(duì)新增對(duì)象的學(xué)習(xí)產(chǎn)生影響,然而這部分信息往往被人們忽略.因此,為了充分利用先驗(yàn)決策信息,在漸進(jìn)概念的基礎(chǔ)之上引入決策重要度和置信度,用于刻畫分類指標(biāo).
例3(接例2) 根據(jù)定義1,
則
由于決策重要度有時(shí)會(huì)產(chǎn)生相等的情況,導(dǎo)致無(wú)法確定對(duì)象的決策,因此本文引進(jìn)決策置信度對(duì)其進(jìn)行進(jìn)一步處理.
由于漸進(jìn)模糊概念的初始鄰域粒可能由多個(gè)子鄰域組成,多個(gè)鄰域粒之間相互影響,故需計(jì)算每個(gè)子鄰域的決策置信度,融合后得到最終決策置信度.具體融合方式如下.
若存在
則
算法3構(gòu)造基于漸進(jìn)概念決策重要度
漸進(jìn)模糊概念空間P={P1,P2,…,Pl}
輸出決策重要度sig(Gi,dj)
for Gi∈P
forxi∈X
end
end
end
例4(接例3) 根據(jù)定義8,
其漸進(jìn)模糊概念初始鄰域粒為
則
本文結(jié)合分類機(jī)制與動(dòng)態(tài)更新機(jī)制,構(gòu)建基于決策重要度漸進(jìn)模糊概念的學(xué)習(xí)機(jī)制.首先對(duì)比新增對(duì)象與原漸進(jìn)概念的信息,尋找相似性最大的漸進(jìn)概念,再選取其決策重要度最大的決策更新新增對(duì)象的信息,具體過(guò)程如算法4所示.
算法4基于決策重要度的分類機(jī)制
輸入漸進(jìn)模糊概念空間P={P1,P2,…,Pl},
新增對(duì)象xa
輸出xa的類別
for Pi∈P
計(jì)算cos(Pi,xa);
得到si=index(maxcos(Pi,xa));
forsi∈Pi
xa的類別為max(sig(si,di));
end
end
當(dāng)添加新對(duì)象xa時(shí),X′=X∪{xa},構(gòu)造漸進(jìn)模糊概念空間的時(shí)間成本很高.為了減少耗時(shí),本文設(shè)計(jì)決策重要度的動(dòng)態(tài)更新機(jī)制(Incremental Lear-
ning Mechanism for Fuzzy Concept Based on Decision Significance, FCDS).在此過(guò)程中,只需計(jì)算xa和Ci∈C的相似度以更新模糊概念空間,進(jìn)而更新決策重要度,而不需要計(jì)算與每個(gè)樣本的相似度.決策重要度的動(dòng)態(tài)更新過(guò)程如算法5所示.
算法5決策重要度的動(dòng)態(tài)更新機(jī)制
添加的對(duì)象xa,參數(shù)δ
for Ci∈C
計(jì)算cos(xa,Ci);
xi=index(maxcos(xa,Ci));
end
由于|Ci|為原始概念空間的個(gè)數(shù),算法總的時(shí)間復(fù)雜度為
即為動(dòng)態(tài)更新決策重要度的時(shí)間復(fù)雜度.
為了驗(yàn)證本文提出的決策重要度的動(dòng)態(tài)更新機(jī)制(FCDS)的分類性能,選擇如下對(duì)比算法:ILMPFTC(Incremental Learning Mechanism Based on Progressive Fuzzy Three Way Concept)[28]、KNN(k-Nearest Neighbor)、CART(Classification and Re-gression Trees)、NB(Naive Bayes)、DT(Decision Tree).
根據(jù)定義9的分析可知,參數(shù)δ是影響分類精度的一個(gè)重要參數(shù).在實(shí)驗(yàn)中,F(xiàn)CDS和ILMPFTC根據(jù)添加對(duì)象的分類精度選擇最佳δ,選擇范圍為[0,1],步長(zhǎng)為0.001.其它4種對(duì)比算法都具有相同的鄰域參數(shù)k,本文中k=3.
實(shí)驗(yàn)選擇UCI機(jī)器學(xué)習(xí)庫(kù)上的11個(gè)實(shí)驗(yàn)數(shù)據(jù)集,詳細(xì)信息如表2所示.
表2 數(shù)據(jù)集詳情Table 2 Dataset description
在預(yù)處理階段,對(duì)數(shù)據(jù)集進(jìn)行歸一化,得到區(qū)間[0,1]內(nèi)的隸屬度.本文使用文獻(xiàn)[29]對(duì)這些數(shù)據(jù)集進(jìn)行歸一化:
(1)
其中,f(xi,aj)表示屬性aj中xi的值,max(f(aj))和min(f(aj))表示屬性aj中所有對(duì)象的最大值和最小值.在模糊決策形式背景中,R(xi,aj)反映(xi,aj)對(duì)aj的隸屬度.通常,模糊集可理解為對(duì)象對(duì)屬性的擁有程度.f(xi,aj)的值越大,x擁有屬性a的程度越大.式(1)作為一種模糊化方法,可將原始數(shù)值轉(zhuǎn)換為模糊決策形式背景.
在每個(gè)數(shù)據(jù)集上,70%的數(shù)據(jù)用于訓(xùn)練模型,剩余數(shù)據(jù)均分為10份,逐次添加至測(cè)試集上,由此驗(yàn)證FCDS的分類性能和有效性.
所有算法均在Matlab 2021b上實(shí)現(xiàn),并在配置為Intel(R)Core(TM)i7-7700 CPU@3.60 GHz和8 GB內(nèi)存的個(gè)人計(jì)算機(jī)上執(zhí)行.
各算法在11個(gè)數(shù)據(jù)集上添加對(duì)象時(shí)的分類精度對(duì)比如表3所示,表中,t1~t10表示逐次添加測(cè)試數(shù)據(jù)的時(shí)間,黑體數(shù)字表示最優(yōu)值,-表示該算法在兩周之內(nèi)未輸出結(jié)果.由表可見(jiàn),除了Breast數(shù)據(jù)集,F(xiàn)CDS的分類精度都大于或等于對(duì)比算法,同時(shí),F(xiàn)CDS在8個(gè)數(shù)據(jù)集上的平均分類精度最高,這表明利用決策重要度可提高樣本的分類性能,由此驗(yàn)證FCDS的有效性.利用先驗(yàn)決策信息也可提高分類器性能,使分類更準(zhǔn)確.
表3 各算法添加新對(duì)象時(shí)的分類精度
表3 各算法添加新對(duì)象時(shí)的分類精度(續(xù))
分類精度雖然常用,但不能滿足所有任務(wù)需求.本節(jié)通過(guò)其它性能度量,說(shuō)明FCDS的有效性與優(yōu)越性.
對(duì)于二分類問(wèn)題,可將樣例根據(jù)其真實(shí)類別與學(xué)習(xí)器預(yù)測(cè)類別的組合劃分為真正例(True Positive)、假正例(False Positive)、真反例(True Negative)、假反例(False Negative)4種情形,令TP、FP、TN、FN分別表示其對(duì)應(yīng)的樣例數(shù),顯然有
TP+FP+TN+FN=樣例總數(shù).
查準(zhǔn)率P與查全率R分別定義為
為了更好地刻畫學(xué)習(xí)器的分類效果,F(xiàn)1度量定義如下:
對(duì)于多個(gè)二分類混淆矩陣,如執(zhí)行多分類任務(wù),每?jī)蓛深悇e的組合都對(duì)應(yīng)一個(gè)混淆矩陣.本文先在各混淆矩陣上分別計(jì)算查準(zhǔn)率和查全率,再計(jì)算平均值,得到宏查準(zhǔn)率(macro-P)、宏查全率(macro-R)、相應(yīng)的宏F1(macro-F1):
各算法在11個(gè)數(shù)據(jù)集上的查準(zhǔn)率和查全率對(duì)比如表4所示,表中黑體數(shù)字表示最優(yōu)值,-表示真正例和假反例或假正例和真反例的個(gè)數(shù)都為0.由表可知,F(xiàn)CDS在6個(gè)數(shù)據(jù)集上的查準(zhǔn)率和查全率都大于或等于對(duì)比算法,在Colonstd數(shù)據(jù)集上取得最大查準(zhǔn)率.ILMPFTC只在Zoo數(shù)據(jù)集上取得最大查全率和查準(zhǔn)率;CART在Breast、Gearbox數(shù)據(jù)集上取得最大查全率和查準(zhǔn)率,在Colonstd數(shù)據(jù)集上取得最大查全率,在Rice數(shù)據(jù)集上取得最大查準(zhǔn)率;DT在Congressional Voting Records數(shù)據(jù)集上取得最大查全率和查準(zhǔn)率,在Rice數(shù)據(jù)集上取得最大查準(zhǔn)率;NB在Gearbox數(shù)據(jù)集上取得最大查準(zhǔn)率和查全率.由此說(shuō)明FCDS在分類效果上具有一定的優(yōu)越性.
表4 各算法的查準(zhǔn)率和查全率對(duì)比
各算法在11個(gè)數(shù)據(jù)集上的F1度量如表5所示,表中黑體數(shù)字表示最優(yōu)值.由表可看出,F(xiàn)CDS在11個(gè)數(shù)據(jù)集中獲得8次最大值,說(shuō)明FCDS在分類方面的優(yōu)越性.
表5 各算法的F1度量對(duì)比
為了進(jìn)一步驗(yàn)證分類算法是否性能相同,本節(jié)選擇常用的Friedman檢驗(yàn)[30],驗(yàn)證算法是否存在顯著差異.設(shè)N為數(shù)據(jù)集數(shù),k為算法數(shù)目,Ri為所有數(shù)據(jù)集上第i個(gè)算法平均排名.F遵循自由度為k-1和(k-1)(N-1)的Fisher分布.Friedman檢驗(yàn)定義如下:
由于在NB中有部分?jǐn)?shù)據(jù)未得出結(jié)果,因此在本次檢驗(yàn)中只考慮FCDS與其它四種算法的差異性.對(duì)5種算法的分類精度進(jìn)行排序,詳細(xì)的排序結(jié)果如表6所示.
根據(jù)定義,計(jì)算F=10.28,大于臨界值F=2.090,因此可知這5種算法有一定差異.下面使用Bonfer-
roni-Dunn檢驗(yàn)測(cè)試5種分類算法之間的統(tǒng)計(jì)差異[32].當(dāng)
k=5,N=11,α=0.1
時(shí),q0.1=2.459,得到臨界距離
表6 算法的分類精度排名Table 6 Classification accuracy rank of 5 algorithms
對(duì)于任意兩種算法,如果它們的距離超過(guò)CDα,說(shuō)明這兩種算法的性能具有顯著不同.本文使用Bonferroni-Dunn測(cè)試圖[31]直觀顯示5種算法之間的統(tǒng)計(jì)學(xué)差異,具體如圖1所示.圖中使用灰色線段繪制臨界差CDα=1.11,然后連接距離小于1.11的分類算法,越靠近1說(shuō)明算法性能越優(yōu).由圖可看出,F(xiàn)CDS與其它4種算法的平均排名的差值都大于臨界差1.11,說(shuō)明FCDS的分類性能與其它算法具有顯著差異.
圖1 各算法Bonferroni-Dunn測(cè)試圖對(duì)比Fig.1 Bonferroni-Dunn test graph of different algorithms
本文提出基于決策重要度的概念認(rèn)知學(xué)習(xí)模型,結(jié)合決策信息與漸進(jìn)模糊概念,獲得更優(yōu)的分類性能.隨著更新后的概念被進(jìn)一步學(xué)習(xí),概念空間包含新增對(duì)象的新信息,因此通過(guò)先驗(yàn)決策信息和新信息的結(jié)合可提高分類精度.同時(shí),在11個(gè)公共數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證上述結(jié)論.在現(xiàn)實(shí)生活中,只要能從概念思維上描述對(duì)象,F(xiàn)CDS就可用于解決其相應(yīng)的分類問(wèn)題,如模式識(shí)別和人臉識(shí)別.同時(shí),增量學(xué)習(xí)的思想也可應(yīng)用于動(dòng)態(tài)增加的數(shù)據(jù),如時(shí)間序列數(shù)據(jù).但是,本文算法對(duì)數(shù)據(jù)集決策分布依賴較大,當(dāng)決策分布不均勻時(shí),分類效果無(wú)明顯優(yōu)勢(shì).因此,今后將著重探討決策分布不均勻時(shí)的分類方法.