構造概念格的權值優化改進算法*

朱文君， 王德興， 袁紅春

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

構造概念格的權值優化改進算法*

朱文君， 王德興， 袁紅春

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

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

形式背景； 概念格； 信息熵； 內涵權值； 閾值區間

0 引 言

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

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

1 加權概念格

定義1 在形式概念分析中，加權形式背景定義為一個四元組Kω=(G,M,I,W)，其中,G為對象集合，M為屬性集合，I為G和M間的二元關系，W={w1,w2…wn}，wi∈W(0≤wi≤1)為屬性的權值[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)為一個加權概念，A,B分別是概念cw的對象和屬性集合，w為權值。形式背景K中所有加權概念及其互相關系組成的集合稱為加權概念格。

2 加權概念格的權值獲取

2.1 屬性內涵的權值獲取

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

(1)

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

(2)

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

2.2 多屬性內涵集權值優化改進

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

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

(3)

(4)

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

2.3 多屬性內涵集重要性閾值的優化

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

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

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

(5)

(6)

(7)

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

(8)

該算法無須調整任何參數，通過信息熵的分布生成，因此，具有較好的適應性。

2.4 算法分析

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

3 實驗和分析

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

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

表1 合并形式背景

圖1 合并概念格

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

3)經計算求得θ=4，格結點多屬性內涵集權值weight(B)及閾值區間如表3所示。

4)未能落在閾值區間內結點#1，#5，#6，#7，#13，#14，#18將被篩除，獲得優化加權概念格如圖2所示。

表2 單屬性內涵權值

表3 多屬性內涵集權值及閾值區間

圖2 優化加權概念格

對比采用文獻[10]中權值獲取的方法對多屬性內涵集重要性賦值并構造加權概念格。

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

表4 多屬性內涵集權值及偏差

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

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

圖3 對比加權概念格

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

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

表5 三種算法執行效率對比

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

4 結束語

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

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

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

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

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

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

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

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

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

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

[10] 張繼福,張素蘭,鄭 鏈.基于信息熵和偏差的加權概念格內涵權值獲取[J].北京理工大學學報,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].傳感器與微系統,2012,31(3):116-118.

[13] 閻紅燦,張 奉,王 云,等.基于粒計算的多值屬性概念格約簡[J].計算機應用,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-),女,通訊作者, 碩士，主要研究方向為數據挖掘，E—mail:zwj0956104@163.com。

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