朱文君， 王德興， 袁紅春

(上海海洋大學(xué) 信息學(xué)院，上海 201306)

構(gòu)造概念格的權(quán)值優(yōu)化改進算法*

朱文君， 王德興， 袁紅春

(上海海洋大學(xué) 信息學(xué)院，上海 201306)

針對基于信息熵與偏差的加權(quán)概念格在合并加權(quán)概念子格時，所得多屬性內(nèi)涵集權(quán)值較其整體在形式背景中的實際權(quán)重偏大，權(quán)重取值閾值的設(shè)置受主觀因素干擾導(dǎo)致合并后的概念格規(guī)模過大的問題，提出了一種構(gòu)造概念格的權(quán)值優(yōu)化改進算法。以多屬性內(nèi)涵集在形式背景中的整體信息熵來設(shè)置其權(quán)值；采用方差計算各概念結(jié)點屬性內(nèi)涵集權(quán)值的閾值區(qū)間，克服了主觀意識對閾值設(shè)置的影響；通過剪除不滿足閾值區(qū)間的冗余概念結(jié)點，縮小了構(gòu)造概念格的整體規(guī)模，減少了構(gòu)造概念格的時間消耗。實驗結(jié)果表明：對比基于信息熵與偏差的加權(quán)概念格減少了9.87 %的冗余結(jié)點，構(gòu)造整體概念格的時間消耗減少了7.36 %，有效提高了加權(quán)概念格的構(gòu)造效率。

形式背景； 概念格； 信息熵； 內(nèi)涵權(quán)值； 閾值區(qū)間

0 引 言

數(shù)據(jù)挖掘和信息融合是數(shù)據(jù)處理與分析中不可或缺的主要處理過程,二者互相補充為用戶提供準確有效的知識信息。文獻[1]提出了基于數(shù)據(jù)挖掘技術(shù)建立信息融合模型的原理和算法,為兩者相互結(jié)合有效地處理復(fù)雜數(shù)據(jù)的數(shù)據(jù)分析問題打下基礎(chǔ)。文獻[2]首次將概念格應(yīng)用于數(shù)據(jù)融合領(lǐng)域，提出了基于概念格理論的數(shù)據(jù)融合處理機制。然而，隨著形式背景的增長，概念格結(jié)點數(shù)指數(shù)級遞增，合并分布存儲的多個子背景效率變得越來越低，且極易生成過多冗余的信息，這些信息只會增加概念格內(nèi)涵的比較次數(shù)，同時，影響概念格的構(gòu)造效率。因此，減少適量冗余信息，提高概念格構(gòu)造效率尤為重要。文獻[3～5]提出了通過對屬性的主觀加權(quán)構(gòu)造頻繁加權(quán)概念格，使用戶能快速地提取值得關(guān)注的知識。文獻[6～8]在此基礎(chǔ)上對構(gòu)造主觀加權(quán)概念格的時間復(fù)雜度進行了優(yōu)化。但由于受到主觀因素的影響，在專家經(jīng)驗不足時所賦權(quán)值偏差較大。文獻[9]率先提出從客觀角度采用信息熵對條件屬性賦值，提高分類的效率。文獻[10，11]對文獻[9]進一步拓展，提出了一種基于信息熵與偏差的加權(quán)概念格內(nèi)涵權(quán)重賦值方法，采用信息熵計算單屬性內(nèi)涵的權(quán)值，以其算數(shù)平均值表示多屬性內(nèi)涵集的權(quán)值，根據(jù)人工設(shè)定的偏差閾值刪減概念結(jié)點。該算法在合并加權(quán)概念子格時，多屬性內(nèi)涵集權(quán)值較其在整體形式背景中的實際權(quán)值偏大，而且主觀設(shè)置的閾值也導(dǎo)致了過多冗余概念結(jié)點的生成，構(gòu)造概念格的規(guī)模過大，構(gòu)造概念格的時間效率較低。文獻[12，13]對概念格冗余屬性的約簡上做了研究，雖然減少了構(gòu)造加權(quán)概念格的時間消耗，但對原始形式背景中包含的多屬性內(nèi)涵集的整體信息進行了刪改，不利于用戶提取準確有效的知識信息。

針對多屬性內(nèi)涵集的權(quán)值偏大及其閾值設(shè)置受主觀因素干擾，使合并加權(quán)概念格的整體規(guī)模過大的問題，本文提出了以概念結(jié)點的多屬性內(nèi)涵集在原始形式背景中隱含的信息量的大小來設(shè)置其權(quán)值，不刪改整體形式背景中的屬性集，優(yōu)化了構(gòu)造概念格的屬性內(nèi)涵集權(quán)值。采用由方差計算的閾值區(qū)間來約束各概念結(jié)點屬性內(nèi)涵集的重要程度，通過刪減不符合閾值區(qū)間的冗余結(jié)點，縮小了合并概念格的整體規(guī)模，提高了構(gòu)造概念格的時間效率。

1 加權(quán)概念格

定義1 在形式概念分析中，加權(quán)形式背景定義為一個四元組Kω=(G,M,I,W)，其中,G為對象集合，M為屬性集合，I為G和M間的二元關(guān)系，W={w1,w2…wn}，wi∈W(0≤wi≤1)為屬性的權(quán)值[1]。對于一個對象x∈G，屬性m∈M，那么xIm就表示對象x具有屬性m。

定義2 三元組cω=(A,B,w)，其中，A?G，B?M，w=w(B)∈[0,1]，分別定義[1]如下兩個映射：f(A)={m∈M|?x∈A，xIm},g(B)={x∈G|?m∈B,xIm}若兩者之間滿足A=g(B)，B=f(A)，則稱三元組cw=(A,B,w)為一個加權(quán)概念，A,B分別是概念cw的對象和屬性集合，w為權(quán)值。形式背景K中所有加權(quán)概念及其互相關(guān)系組成的集合稱為加權(quán)概念格。

2 加權(quán)概念格的權(quán)值獲取

2.1 屬性內(nèi)涵的權(quán)值獲取

定義3 對于任意對象gi∈G，1≤i≤n，任意屬性m∈M，則P(m/gi)表示對象為gi時具有屬性m的概率，H(m)表示gi提供給屬性m的平均信息量，即單屬性m的權(quán)值wm為

(1)

定義4 若一個形式概念cω=(A,B,ω)，且B={m1,m2,…,mn}，Wqz(mi)=wi(i∈1,2,…,n)，則多屬性內(nèi)涵集B的權(quán)值定義如下[8]，其含義為多屬性內(nèi)涵集中各單屬性權(quán)值的平均數(shù),即

(2)

根據(jù)文獻[10]獲取屬性內(nèi)涵權(quán)值，一定程度上減少了屬性內(nèi)涵權(quán)重設(shè)置的主觀性，然而,由單屬性權(quán)值的平均數(shù)表示多屬性內(nèi)涵集的權(quán)值并未考慮多屬性內(nèi)涵重要性的總體水平,僅反映了各個單屬性對多屬性內(nèi)涵集權(quán)值的貢獻之和，因而,所得權(quán)值比多屬性內(nèi)涵集整體在形式背景中的實際權(quán)值偏大。

2.2 多屬性內(nèi)涵集權(quán)值優(yōu)化改進

多屬性內(nèi)涵的權(quán)值計算方法不僅會影響加權(quán)概念格中的結(jié)點數(shù)目，也會影響其構(gòu)造效率。當概念格結(jié)點內(nèi)涵由多屬性組成時，多屬性整體的不確定性即為內(nèi)涵集權(quán)值的不確定性，本文采用了多屬性內(nèi)涵整體的客觀概率來量化其權(quán)值。而多屬性內(nèi)涵整體信息熵則作為其整體出現(xiàn)概率的度量由形式背景中各對象對多屬性內(nèi)涵集提供信息之和計算，進而以其整體信息熵來表示多屬性內(nèi)涵集的權(quán)值，更準確地反映了多屬性內(nèi)涵集的重要程度。

設(shè)在加權(quán)形式背景Kw=(G,M,I,W)下的一個加權(quán)概念cw=(Ai,Bj,w)，對象集Aj={a1,a2,…,ai} A?G，多屬性內(nèi)涵集Bj={b1,b2,…bj} B?M，H(B)表示對象集合G提供給屬性集Bj信息總量，多屬性內(nèi)涵集Bj的權(quán)值w(Bj)計算公式如下

(3)

(4)

式中 am∈Ai為對象集Ai的一個對象，n為概念結(jié)點數(shù)。當Ai=?或Bj=?，則w(Bj)=1。

2.3 多屬性內(nèi)涵集重要性閾值的優(yōu)化

根據(jù)文獻[10]基于信息熵與偏差的權(quán)值獲取結(jié)果會與實際權(quán)值產(chǎn)生較大偏差，而人工設(shè)定的偏差閾值受主觀經(jīng)驗的影響較大，這會導(dǎo)致提取到的信息難以被采納。因此,本文提出區(qū)間閾值對權(quán)值設(shè)置約束，當計算所獲權(quán)值不在閾值區(qū)間內(nèi)時，則認為此概念結(jié)點是冗余的，從而使得冗余的信息不被用戶提取。

本文用區(qū)間α=[μ-θδ,μ+θδ]表示內(nèi)涵重要性的閾值區(qū)間，其中,μ為多屬性內(nèi)涵集內(nèi)各單屬性權(quán)值的算術(shù)平均值，δ為其方差，θ為內(nèi)涵集權(quán)值偏差的約束。θ的取值通過最小化方差和的方法來獲取。作為測算數(shù)值型數(shù)據(jù)離散程度的重要方法，方差是各變量值與其均值離差平方的平均數(shù)。方差和越大，則形式背景中各個概念結(jié)點的權(quán)值波動性越大，權(quán)值獲取存在的偏差越大。方差和的最小化即可獲取離散分布的屬性權(quán)值的合理分布范圍，使冗余的概念結(jié)點權(quán)值不落在閾值區(qū)間內(nèi)，對該結(jié)點進行刪減進而提高知識提取的準確性。

通過上述分析可以發(fā)現(xiàn)，因子表法在形成和應(yīng)用因子表的過程中并沒有考慮方程組元素本身的對稱性。如果考慮這種對稱性，則求解A(n-1)′陣時所采用的方式、求取A(n-1)′陣中元素的方式、對后續(xù)F陣元素的前代方式等，都將是簡化因子表法的形成過程以及提高因子表法計算速度的關(guān)鍵。

(5)

(6)

(7)

α=[μ-θδ,μ+θδ]

(8)

該算法無須調(diào)整任何參數(shù)，通過信息熵的分布生成，因此，具有較好的適應(yīng)性。

2.4 算法分析

算法根據(jù)重要性閾值區(qū)間判斷概念結(jié)點是否會被刪除。對于符合閾值約束的結(jié)點予以保留并遞歸遍歷其父結(jié)點集和子結(jié)點集，如此循環(huán)直至添加所有數(shù)據(jù)。對于一個概念結(jié)點C(x,k,w)，至多存在2k個內(nèi)涵包含于k的子概念。因此，在概念格的漸進式構(gòu)造過程中，當所有結(jié)點都符合閾值區(qū)間，構(gòu)造一般概念格的Godin算法時間復(fù)雜度[5]為O(2k|n|)(|n|為已有的結(jié)點個數(shù))。而當加權(quán)概念結(jié)點被判斷為冗余結(jié)點需要被刪除時，在概念格的構(gòu)造過程中將不生成該結(jié)點，相應(yīng)的時間復(fù)雜度就會降低。由此，可得本算法的時間復(fù)雜度小于O(2k|n|)，提高了概念格的構(gòu)造效率。

3 實驗和分析

數(shù)據(jù)來源于《上海海洋大學(xué)2009～2013年畢業(yè)生就業(yè)信息數(shù)據(jù)庫》，對數(shù)據(jù)集進行預(yù)處理后構(gòu)成形式背景，其M={a,b,c,d,e}屬性集分別代表5個屬性，應(yīng)屆生、計算機類擇業(yè)傾向、英語六級、英語四級及中級口譯。對象集G={1,2,3,4,5,6}為6位學(xué)生。

實驗一：本算法與文獻[10]算法分別構(gòu)造加權(quán)概念格，比對其刪除合并子格時所生成冗余結(jié)點的有效性。

表1 合并形式背景

圖1 合并概念格

2)表2所示為在未知多屬性內(nèi)涵集M中各單屬性內(nèi)涵重要性的情況下，利用信息熵客觀獲取單屬性的權(quán)值，W={0,0.24,0.32,0.13,0.31}。

3)經(jīng)計算求得θ=4，格結(jié)點多屬性內(nèi)涵集權(quán)值weight(B)及閾值區(qū)間如表3所示。

4)未能落在閾值區(qū)間內(nèi)結(jié)點#1，#5，#6，#7，#13，#14，#18將被篩除，獲得優(yōu)化加權(quán)概念格如圖2所示。

表2 單屬性內(nèi)涵權(quán)值

表3 多屬性內(nèi)涵集權(quán)值及閾值區(qū)間

圖2 優(yōu)化加權(quán)概念格

對比采用文獻[10]中權(quán)值獲取的方法對多屬性內(nèi)涵集重要性賦值并構(gòu)造加權(quán)概念格。

1)根據(jù)文獻[10]獲取多屬性內(nèi)涵集的權(quán)值weight(B)及其標準偏差D(B)如表4所示。

表4 多屬性內(nèi)涵集權(quán)值及偏差

2)設(shè)定內(nèi)涵重要性閾值α=0.15，重要性偏差閾值β=0.18，刪除冗余結(jié)點#1，#13，#19，#17，#2，#4，#12。

圖3中刪除的結(jié)點#1，#13反映了僅通過四級或中級口譯認證的應(yīng)屆畢業(yè)生的并不是值得關(guān)注的人才，這不僅與文獻[10]的算法所得結(jié)論一致也與現(xiàn)實背景相符。刪除結(jié)點#5，#6，#7實現(xiàn)了英語水平有重疊的結(jié)點刪減。對比文獻[10]的加權(quán)方式，此類信息被冗余在了概念格中。#14，#18結(jié)點刪除的意義是忽略有計算機類擇業(yè)傾向的通過中級口譯的應(yīng)屆生，作為一門地方培養(yǎng)項目的英語水平認證考試有其地方局限性，其含金量確實不高。對比文獻[10]的加權(quán)賦值結(jié)果，結(jié)點#4的刪除顯然偏差較大，通過最基本的英語四級還是值得關(guān)注的。由此可以看出，在形式背景屬性集權(quán)值并不清晰的情況下，本算法通過信息熵對屬性內(nèi)涵集重要性及其閾值區(qū)間做出客觀評估可以更有效地提取出值得用戶關(guān)心的信息。

圖3 對比加權(quán)概念格

實驗二:在內(nèi)存為2GB，操作系統(tǒng)為Windows XP的計算機上，在VC6.0的環(huán)境下，用C++語言實現(xiàn)了本文算法、文獻[10]算法及 Godin算法[1]。選用2013屆信息學(xué)院畢業(yè)生就業(yè)信息數(shù)據(jù)集進行實驗，該數(shù)據(jù)集共有236條學(xué)生記錄，38項相關(guān)屬性，通過預(yù)處理后構(gòu)成整體形式背景，以50條學(xué)生記錄為單位將其劃分為5個子形式背景。

將5個子形式背景依次進行合并，分別采用本算法、文獻[10]算法及Godin算法構(gòu)造合并后的整體概念格，對比其時間效率。三種算法構(gòu)造概念格的執(zhí)行效率對比結(jié)果如表5。

表5 三種算法執(zhí)行效率對比

由實驗結(jié)果可知，隨著子形式背景依次合并，學(xué)生記錄數(shù)逐漸遞增，概念格中的概念結(jié)點數(shù)隨之遞增，概念格的構(gòu)造時間也逐漸遞增。由于Godin算法在構(gòu)造概念格的過程中遍歷了所有概念結(jié)點，因此其構(gòu)造時間最長，執(zhí)行效率最低。而文獻[10]算法對部分冗余信息進行了刪減，但其構(gòu)造的概念格規(guī)模仍然較為復(fù)雜，僅減少了8.71 %冗余結(jié)點，構(gòu)造效率較Godin算法提高程度有限，時間消耗縮短了17.13 %。與前兩種算法相比，本算法構(gòu)造概念格消耗的時間最短，時間消耗較文獻[10]算法縮短了7.36 %，較Godin算法縮短了24.49 %，概念格的構(gòu)造效率得到了顯著的提高。此外，本算法較文獻[10]算法進一步剪除了過量的冗余概念，構(gòu)造概念格時生成的格結(jié)點個數(shù)減少了9.87 %，冗余結(jié)點得到了有效的刪減，優(yōu)化了概念格的整體結(jié)構(gòu)，更有利于提取用戶關(guān)心的知識信息。

4 結(jié)束語

本文在多個加權(quán)子格合并而專家或用戶對新增對象缺乏了解時，首先以形式背景對多屬性內(nèi)涵集整體的信息量作為多屬性內(nèi)涵集的權(quán)重取值依據(jù)，解決了多屬性內(nèi)涵集權(quán)值較實際情況偏大的問題。其次，基于信息熵的分布由方差計算其閾值區(qū)間對多屬性內(nèi)涵集權(quán)值的最大及最小取值進行合理的約束。最后通過真實數(shù)據(jù)集驗證了構(gòu)造概念格的權(quán)值優(yōu)化改進算法有效地優(yōu)化了構(gòu)造概念格的權(quán)值。通過對過量冗余概念結(jié)點進行刪減，縮小了概念格的整體規(guī)模，從而提高了概念格的構(gòu)造效率。

[1] 付 華，王雨虹.基于數(shù)據(jù)挖掘的瓦斯災(zāi)害信息融合模型的研究[J].傳感器與微系統(tǒng),2008,27(1):52-54.

[2] 吳桂清,胡 弦,張利民,等.搗固車作業(yè)系統(tǒng)異質(zhì)多傳感器數(shù)據(jù)融合的研究[J].傳感器與微系統(tǒng),2012,31(8):76-78.

[3] 張繼福,張素蘭,鄭 鏈.加權(quán)概念格及其漸進式構(gòu)造[J].計算機學(xué)報,2005,18(2):171-176.

[4] 張素蘭,張繼福,高愫邡.加權(quán)概念格的漸進式構(gòu)造及其關(guān)聯(lián)規(guī)則提取[J].計算機工程與應(yīng)用,2005,41(7):173-175,178.

[5] 孫桂利,張繼福.一種基于加權(quán)概念格的分類規(guī)則提取算法[J].太原科技大學(xué)學(xué)報,2011,32(5):352-357.

[6] 王欣欣,張繼福,張素蘭.一種頻繁加權(quán)概念格的批處理構(gòu)造算法[J].模式識別與人工智能,2010,23(5):678-685.

[7] 馬 洋,張繼福,張素蘭.基于剪枝的約束概念格的漸進式構(gòu)造算法[J].計算機應(yīng)用,2009,29(5):1397-1400.

[8] 翟 悅,郭 楊,王玉姣.一種利用差集的加權(quán)頻繁項集挖掘算法[J].遼寧工程技術(shù)大學(xué)學(xué)報：自然科學(xué)版,2016,35(3):312-317.

[9] 房鵬杰,張素蘭,張繼福.基于概念格和條件信息熵的分類規(guī)則獲取方法[J].計算機工程與應(yīng)用,2010,46(14):148-151,186.

[10] 張繼福,張素蘭,鄭 鏈.基于信息熵和偏差的加權(quán)概念格內(nèi)涵權(quán)值獲取[J].北京理工大學(xué)學(xué)報,2011,31(1):59-63.

[11] Zhang Sulan,Guo Ping,Zhang Jifu,et al.A completeness analysis of frequent weighted concept lattices and their algebraic properties[J].Data & Knowledge Engineering,2012,11(2):246-267.

[12] 謝春麗,劉永闊.概念格理論屬性約簡算法研究[J].傳感器與微系統(tǒng),2012,31(3):116-118.

[13] 閻紅燦,張 奉,王 云,等.基于粒計算的多值屬性概念格約簡[J].計算機應(yīng)用,2015(A02):73-76.

Improved optimization algorithm of weighted concept lattice*

ZHU Wen-jun, WANG De-xing, YUAN Hong-chun

(College of Information Technology,Shanghai Ocean University,Shanghai 201306,China)

Since the multiple attribute intent weight values are slightly bigger than the actual weighted values when weighted concept sub-lattices based on information entropy and deviance being combined,thresholds disturbed by subjective factor directly causes the merged concept lattice size to be exaggerated,an improved optimization algorithm of weighted concept lattices is proposed.Multiple attribute intent weight values are decided by the whole entropy of attributes sets in data sets.Threshold interval of each concept node multiple attribute intent weight value is computed by variance to overcome the subjective factors.The size of the weighted concept lattice construction and time-consuming are reduced by removing redundant nodes which does not satisfy the threshold interval. The experimental results indicate that the proposed algorithm is reduced 9.87 % redundant nodes,the time-consuming of whole concept lattice construction is decreased by 7.36 %.The proposed algorithm apparently improves the efficiency of constructing weighted concept lattices.

formal context; concept lattice; information entropy; intent value; threshold interval

10.13873/J.1000—9787(2017)04—0153—03

2016—06—21

上海市科委科技支撐計劃資助項目(14391901400)

TP 311

A

1000—9787(2017)04—0153—04

朱文君(1991-),女,通訊作者, 碩士，主要研究方向為數(shù)據(jù)挖掘，E—mail:zwj0956104@163.com。

袁紅春(1971-)，男，博士，教授，主要從事人工神經(jīng)網(wǎng)絡(luò)、智能計算工作。