基于模糊超網(wǎng)絡的知識獲取方法研究

程麟焰，胡峰

（1. 重慶郵電大學 計算機科學與技術學院，重慶 400065; 2. 重慶郵電大學 計算智能重慶市重點實驗室，重慶400065）

模糊粗糙集理論是1990年由D.Dubios和 H.Prade共同提出的處理數(shù)值型數(shù)據(jù)中存在的不一致性的數(shù)學理論[1]。經(jīng)過多年的發(fā)展，模糊粗糙集在理論和應用方面都取得了相當豐富的研究成果，在系統(tǒng)控制、故障診斷、機器學習與數(shù)據(jù)挖掘等眾多領域都有著廣泛的應用。經(jīng)典的粗糙集理論強調的是對象間的不可區(qū)分性，主要用于處理清晰、離散且有限的屬性值，而在實際生活中大部分的數(shù)據(jù)集都具有多種多樣的屬性值，粗糙集在處理這些本身具有模糊性的數(shù)據(jù)和連續(xù)屬性時存在一定的局限性[2]。粗糙集理論中的等效關系是研究模糊粗糙集理論的基礎，將經(jīng)典粗糙集理論中的被近似對象由清晰集轉換為模糊集，并將論域上的分明等效關系弱化為模糊等效關系即可得到模糊粗糙集[3]。

超網(wǎng)絡(hypernetworks)是受生物分子網(wǎng)絡啟發(fā)而建立的一種基于超圖實現(xiàn)的認知學習模型，能夠表示模式特征間的高階關聯(lián)關系[4]。目前，國內的研究者們主要研究演化超網(wǎng)絡模型，探究其應用領域并在此基礎上對超網(wǎng)絡模型進行改進。王進等[5]結合OCDD算法，提出了一種能處理多值數(shù)據(jù)的細粒度超網(wǎng)絡分類方法；王進等[6]在超網(wǎng)絡的演化學習過程中引入遺傳算法，從而得到了一種具有較高的分類準確率的模式識別方法；為了處理多類型癌癥分子問題，王進等[7]提出了一種基于演化超網(wǎng)的多類型癌癥分子分型系統(tǒng)。同時，在中文文本分類[8]、評分預測、道路限速標志識別[9]等方面，演化超網(wǎng)絡模型也得到了很好的應用。超網(wǎng)絡的研究在國內起步較晚，在許多領域都值得研究和學習。

本文結合模糊粗糙集的思想提出了一種模糊超網(wǎng)絡(fuzzy hypernetworks，F(xiàn)-hypernetworks)。在模糊超網(wǎng)絡中，對于連續(xù)型的屬性不需要對其進行離散化處理，解決了傳統(tǒng)超網(wǎng)絡只能處理離散型屬性的問題，并對傳統(tǒng)超網(wǎng)絡訓練過程中具有很大隨機性的超邊替代環(huán)節(jié)進行了改進。

1 相關概念

1.1 模糊等價類

定義1 給定決策表(U, A∪D)，其中：U為非空有限論域；A為條件屬性集合，也稱特征集合；D為決策屬性集合，也稱類別屬性集。在沒有說明的情況下，屬性是指條件屬性。 P ? A 對應一個不可分辨的等效關系，簡記為P。若P滿足：

1) 自反性， ? x ∈U ， μP(x,x)=1；

2) 對稱性， ? x ,y∈U ， μP(x,y)=μP(y,x)；則稱P為U上的模糊相似關系[10]。

定義2 設P是U上的模糊相似關系，對于給定 的 x ∈ U ， 令 [ x ]P=μP(x,y)， y ∈U ， 則 [ x ]P是論域U上的一個模糊集，稱其為x關于P的模糊鄰域[10]。 μP( x,y) 表示由模糊相似關系P確定的對象x和y之間的模糊相似度，可由式(1)確定：

對于屬性 a ∈ P ， 若a為連續(xù)屬性，則μa(x,y)可由式(2)表示的模糊相似度確定：

式中： σa表示所有對象在屬性a上取值的標準方差。若a為離散屬性，{則按式(3)[11]計算模糊相似度：

式中 a (x )、 a ( y) 分別表示對象x、y在屬性a上的屬性值。

定義3 給定決策表(U, A∪D)，P是U上的模糊相似關系，對于給定的 x ∈ U 有式中： [ x ]Pλ稱為x關于P的λ-等價類；實數(shù)λ為模糊相似度閾值。

μP(x,y)由式(1)確定。其中I表示邊緣蘊含算子、T 表 示 t -模[3]：

根據(jù)式(5)，對象x關于模糊正域的隸屬度[13]可表示為

在模糊粗糙集條件下，決策屬性D對條件屬性集P的依賴度[13]為

k值的大小，反映了條件屬性集P的分類能力。決策屬性D對屬性集P的依賴程度越大，以P為依據(jù)進行分類的效果越好。以表1所示的決策信息系統(tǒng)為例計算各個屬性的依賴度。由此可以計算出每個屬性的依賴度，并稱其為屬性的重要度。

表 1 決策信息系統(tǒng)Table 1 Decision information system

1.2 模糊超網(wǎng)絡模型

定義5 設G=是一個模糊超網(wǎng)絡，X={x1,x2,···,xn}表示模糊超網(wǎng)絡的頂點集合，E={e1,e2,···,em}為超網(wǎng)絡的超邊集合，λ為模糊超網(wǎng)絡模型的最優(yōu)模糊相似度閾值。超邊的條件屬性集為 C ={c1,c2,···,cs}， D 為超邊的決策屬性，ei是超邊集E中連接k個頂點 xi1,xi2,···,xik的超邊。其中頂點 xi為樣本，且一條超邊中的樣本具有相同的屬性集。

定義6 模糊超網(wǎng)絡G1=，模糊超網(wǎng)絡 G2=，若 X1=X2則 λ1=λ2。

定義7 模糊超網(wǎng)絡G=，超邊的屬性 集 為 C ={c1,c2,···,cs} ， ? B (B ? C )，在 屬 性 集B上，樣本 x = {c1(x),c2(x),c3(x),···,cp(x),D(x)}，c1(x),c2(x),···,cp(x) 表 示x在屬性 ci上的取值，D(x)表示x的決策分類。

定義8 給定模糊超網(wǎng)絡G=，樣本x在屬性集 B ( B?C) 上的λ-等價類超邊集合為

λ-等價類樣本集合為

定義 9 給定模糊超網(wǎng)絡G=，?e∈E ， 在屬性集 B ( B?C) 上，關聯(lián)超邊e的樣本集合表示為

定義10 給定模糊超網(wǎng)絡G=，?e∈E ， D (e) 表示超邊e的決策分類，在屬性集B(B ? C ) 上 ，關聯(lián)超邊e的樣本集合為 RBλ(e)，當RBλ(e)≠ ? 時，超邊e對樣本分類的置信度為

定義11 給定模糊超網(wǎng)絡G=，C為樣本的條件屬性集，D為樣本的決策屬性，對任意的樣本 x ∈ X 有：

如果 |{ y |μC(x,y)≥ λ }|=0 則 f ( x)=-1。f(x)表示在樣本x的λ-等價類樣本集合中，與x同類的樣本所占的比例。f(x)越大，說明x的模糊等價類與x類別一致的概率越大。

圖1給出了4個樣本的λ-等價類樣本集合，由 式(1 4)可 得： f (x1)=1 ， f ( x2)=0.2 ， f ( x3)=0，f(x4)=-1。 本文實驗選取 α = 1,β=0 ， f ( x1)≥1，故x1是正域樣本； 0 ＜ f(x2)＜1，x2是邊界域樣本；f(x3)≤0 ， x3是負域樣本； f ( x4)=-1，x4沒有 λ -等價類樣本，也是負域樣本。

圖 1 λ-等價類樣本示例Fig. 1 Examples of λ-equivalence class sample

定義12 給定模糊超網(wǎng)絡G=，C為樣本的條件屬性集，D為樣本的決策屬性，任意超邊集關于屬性集B的正域、負域和邊界域可分別定義為

以表1的決策信息系統(tǒng)為例，圖2是表1的一個模糊超網(wǎng)絡模型，超邊集 EY={e1,e2,e3,e4}，假設超邊與各樣本的模糊相似度如表2所示，最優(yōu)模糊相似度閾值為λ=0.5。圖2中實線圓區(qū)域表示超邊的λ-等價類，虛線圓區(qū)域表示該超邊的λ0-等價類，λ0=λ+(1-λ)/2=0.75。

圖 2 模糊超網(wǎng)絡示例Fig. 2 Example of a Fuzzy hypergraph

根據(jù)式(15)、表2與圖2可知，正域超邊需同時滿足兩個條件：

負域超邊需滿足條件：

表 2 樣本-超邊相似度Table 2 Sample_Hyperedge similarity

對于超邊e1，與e1相似度最高的異類樣本為x3，μ(e1, x3)=0.72<0.75，不滿足負域條件，所以 e1不是負域超邊，μ(e1, x3)=0.72>0.5不滿足正域條件1)，所以e1是邊界域超邊。

對于超邊e2，與e2相似度最高的異類樣本為x1，μ(e2, x1)=0.30<0.75，不滿足負域條件，所以 e2不是負域超邊，與e2相似度最高的同類樣本為x2，μ(e2, x2)=0.35<0.5不滿足正域條件2)，所以e2是邊界域超邊。

對于超邊e3，與e3相似度最高的異類樣本為x6，μ(e3, x6)=0.77>0.75，滿足負域條件，所以 e3是負域超邊。

對于超邊e4，與e4相似度最高的異類樣本為x3，μ(e4, x3)=0.34<0.5，與 e4相似度最高的同類樣本為x4，μ(e4, x4)=0.82>0.5滿足正域條件，所以e4是正域超邊。

綜 上 所 述， P OS(EY)={e4}， B N D(EY)={e1,e2}，NEG(EY)={e3}。

2 模糊超網(wǎng)絡分類算法

2.1 算法思路

同傳統(tǒng)超網(wǎng)絡一樣，模糊超網(wǎng)絡生成算法也分為三大步驟：初始化超邊集，訓練樣本分類，超邊替代。超網(wǎng)絡通過迭代訓練的方式進行演化學習，當分類正確率和迭代次數(shù)滿足特定條件時，即可退出迭代，輸出模型。由于傳統(tǒng)超網(wǎng)絡采用隨機生成的方式初始化超邊，增大了超邊替代階段篩選和替換分類能力差的超邊的難度[14]。所以本文提出的模糊超網(wǎng)絡對超邊的初始化隨機生成進行了控制，同時在超邊替代過程中，對不同域中的超邊進行相應的處理以提高超網(wǎng)絡的分類效果。算法流程如圖3所示。

圖 3 分類算法流程Fig. 3 Flow of this algorithm

2.1.1 計算最優(yōu)模糊相似度閾值λ

由定義6可知，每一個訓練樣本集都有且只有一個最優(yōu)模糊相似度閾值λ，所以本文在執(zhí)行分類算法前需要通過循環(huán)迭代的方法計算出最優(yōu)λ，具體流程如圖4所示。初始設置模糊相似度閾值λ0為0，然后通過疊加步長來改變λ0的取值，在不同的λ0值下，采用模糊超網(wǎng)絡分類方法對訓練集進行十折交叉驗證[15]得到相應的分類正確率。將正確率最高的λ0值作為最優(yōu)模糊相似度閾值λ執(zhí)行后續(xù)的分類算法。值得注意之處在于，從理論上說，對于同一個訓練集，λ是唯一的，本方法計算出的結果僅是一個接近的閾值，一般步長設置越短越接近最優(yōu)模糊相似度閾值。本文所設置的步長s=0.01，足以滿足實驗需求。2.1.2 超邊初始化

根據(jù)訓練集中的樣本生成模糊超網(wǎng)絡中的超邊。本文設置每個樣本直接生成5條超邊，超邊的屬性數(shù)目與樣本一致。每條超邊的初始化主要由條件屬性初始化和決策屬性初始化兩部分組成。

1) 條件屬性初始化

條件屬性初始化主要有兩種方式：一種是隨機屬性繼承，超邊從條件屬性集中隨機選擇十分之七的屬性繼承樣本的屬性值，即超邊在這些屬性上的取值與生成該超邊的樣本相同。剩余屬性則根據(jù)訓練集在該屬性上的取值范圍隨機生成屬性值。如圖5所示，x為樣本，e為x按照隨機屬性繼承方式生成的超邊。

圖 5 隨機屬性繼承示例圖Fig. 5 Example of random attribute inheritance

圖 4 計算最優(yōu)λ流程圖Fig. 4 Flow chart for calculating optimal λ

另一種是擇優(yōu)屬性繼承，超邊從所有屬性中選擇重要度較高的前十分之七的屬性繼承樣本的屬性值，剩余屬性上的取值則根據(jù)訓練集中同類樣本在該屬性上的取值范圍隨機生成。如圖6所示，樣本x擁有10個屬性，首先利用樣本x的λ-等價類樣本集合按照定義4所示的方法計算出各個屬性的重要度k，然后重新生成重要度較低的屬性1、2、9對應的屬性值。

圖 6 擇優(yōu)屬性繼承示例圖Fig. 6 Example of preferred attribute inheritance

2) 決策屬性初始化

正域樣本生成的超邊，條件屬性初始化采取隨機屬性繼承方式，決策屬性直接繼承生成該超邊的樣本。邊界域樣本生成的超邊，條件屬性初始化采取擇優(yōu)屬性繼承方式，決策屬性直接繼承生成該超邊的樣本。負域樣本生成的超邊，同樣采取隨機屬性繼承的方式確定條件屬性，因為其決策屬性與原始樣本相同的概率較低，所以該類超邊的決策屬性是根據(jù)整個數(shù)據(jù)集確定的，與關聯(lián)該超邊的樣本集中的大類樣本類別一致。2

.1.3 訓練樣本分類

給定模糊超網(wǎng)絡G=，決策屬性的取值范圍 VD={1,2,···,m} 樣本x在λ下的模糊等價類超邊集合為 [ x ]λ，其中決策屬性為j的超邊集合為

對于每一個樣本x的分類過程如下：

1) 計算出樣本x在λ下的模糊等價類超邊 [ x ]λ；

2) 將 [ x ]λ中的超邊進行分類，將決策屬性為j的超邊歸類到 [ x ]λj中，

4) 若 [ x ]λ= ? ，則選取與樣本x模糊相似度最高的n條超邊 加 入到集合 En(x) 中，類別本文實驗取n=3。

采用上述分類規(guī)則對訓練集的每個樣本進行分類，計算模糊超網(wǎng)絡模型對訓練集的分類正確率。

2.1.4 超邊替代

首先判斷超邊所在區(qū)域，然后不同的區(qū)域采取不同的措施：

若超邊e是正域超邊，則超邊e與訓練集中所有異類樣本相似度較低，與同類樣本相似度較高，該超邊的存在有助于提高分類效果，故選擇保留超邊e；

若超邊e是負域超邊，則超邊e與訓練集中某一異類樣本相似度較高，在分類的過程中超邊e會影響其他類別的分類效果，故需要替換；

若超邊e是邊界域超邊，在衡量超邊e的分類效果時，需要通過置信度ConfB進行判斷，若ConfB＞γ(本文取 γ =0.5)，保留超邊 e ，反之，則替換掉超邊e。其中存在一種特殊情況：當關聯(lián)超邊e的樣本數(shù)為0時，無法計算置信度ConfB。此時，需要查看超邊參與分類的樣本集合 P ( e)，P(e)={x|[x]λ=?∧e∈En(x),x∈X} ， 若 |P ( e)|=0 說 明 超 邊e在超網(wǎng)絡對訓練集的分類過程中沒有起太大的作用，一般選擇將其替換；若，則按式(18)計算置信度：

2.2 算法描述

算法1 初始化超邊庫算法

輸入 訓練樣本集X，最優(yōu)閾值λ；

輸出 超邊集E。

2) 計算每個樣本的λ-等價類樣本集合，根據(jù)定義11判斷樣本所屬區(qū)域

5) while(j<5) /*設置每個樣本生成的超邊數(shù)*/

x∈POS(X)

6) if then

7) 根據(jù)樣本x生成超邊e，e直接繼承x的決策屬性，條件屬性初始化采取隨機屬性繼承方式

10) 根據(jù)樣本x生成超邊e，條件屬性初始化采取隨機屬性繼承方式，決策屬性根據(jù)整個數(shù)據(jù)集確定

13) 根據(jù)x生成超邊e，超邊直接繼承x的決策屬性，計算在x的λ-等價類樣本集合中各條件屬性的依賴度，將條件屬性按依賴度大小從大到小排序，超邊e擇優(yōu)選擇排在前7/10的屬性繼承樣本x的屬性值

算法2 超邊替代算法

輸入 訓練樣本集X，最優(yōu)閾值λ，超邊集E；輸出 超邊集E。

算法3 生成模糊超網(wǎng)絡算法

輸入 訓練樣本集X，最優(yōu)閾值λ；

輸出 超網(wǎng)絡G。

1) 執(zhí)行算法1生成初始超邊集E

2) k=0，Ebest= ? ，Pmax=0 /*用于保存最高分類正確率*/

3) while (k<100)

/*設置最小迭代次數(shù)用以保障超網(wǎng)絡能夠得到充分的演化，可根據(jù)實際演化效果增減次數(shù)*/

4) for each x in X do

5) 計算樣本x在λ下的模糊等價類超邊集合[x]λ， 計算x的類別D(x)

6) end for

7) 根據(jù)訓練樣本的實際類別，計算當前超邊集對訓練集的分類正確率P；k++

8) if P>Pmaxthen

9) Pmax= P，Ebest=E；/*保存當前最優(yōu)超邊集*/

10) end if

11) 執(zhí)行算法2更新超邊集

12) end while

13) m=0

14) while (m<10) /*退出迭代條件 */

15) for each x in X do

16) 計算樣本x在λ下的模糊等價類超邊集合 [ x ]λ， 計算x的類別D(x)

17) end for

18) 根據(jù)訓練樣本的實際類別，計算當前超邊集對訓練集的分類正確率P

19) if P > Pmaxthen

20) Pmax= P，Ebest=E，m=0

21) else m++

22) end if

23) 執(zhí)行算法2更新超邊集

24) end while

26) return G=；/*輸出模糊超網(wǎng)絡*/

令訓練集樣本數(shù)目為n，樣本的屬性數(shù)目為m。算法1的平均時間復雜度為O(m×n2)，算法2的時間復雜度為O(m×n)，算法3的時間復雜度為O(m×n2)，所以建模的時間復雜度為O(m×n2)。

計算最優(yōu)模糊相似度閾值時循環(huán)迭代所用的時間約為建模時間的10×s-1倍，迭代步長s在(0,1)范圍內取值。s值越小，計算所用的時間越長，得到的結果越接近理論上的最優(yōu)閾值。最優(yōu)模糊相似度閾值是一個非常重要的參數(shù)，在部分數(shù)據(jù)集上，略微改變閾值，分類結果就會有較大的改變。對于這類數(shù)據(jù)集而言，計算最優(yōu)模糊相似度閾值是非常重要的環(huán)節(jié)。但也有一些數(shù)據(jù)集，例如大部分的離散型數(shù)據(jù)集，在一定范圍內改變閾值，生成的超網(wǎng)絡的分類效果不變，處理這些數(shù)據(jù)集時，可以通過設置合理的步長和初始閾值，達到既不影響分類效果又能減少迭代時間的目的。

3 實驗評價

3.1 數(shù)據(jù)集及評價指標

為驗證算法的有效性，本文選取機器學習數(shù)據(jù)庫UCI中的15個數(shù)據(jù)集進行實驗，每個數(shù)據(jù)集的詳細信息如表3所示，按數(shù)據(jù)集大小從小到大排序。

表 3 實驗數(shù)據(jù)集Table 3 Experimental data sets

混合矩陣(confusion matrix)[16]是一個常用的評價指標，如表4所示。TP表示正類樣本被正確預測為正類的樣本數(shù)；FN、FP分別表示預測錯誤的實際正類和負類樣本數(shù)目；TN表示負類樣本被正確預測為負類的樣本數(shù)。

表 4 混合矩陣Table 4 Confusion matrix

查準率：表示被分類器預測為正類的樣本中正類樣本所占的比例。計算公式為

查全率：又稱召回率，表示正類樣本被分類器正確預測為正類的比例。計算公式為

F-Measure指標[17]是一種綜合查全率和查準率的分類評價指標：正確率即分類正確樣本數(shù)與分類總數(shù)之比。本文采用正確率、查準率(Precision)、查全率(Recall)、和F-Measure作為評價指標。

3.2 實驗方法

為了考察模糊超網(wǎng)絡分類算法的性能，本文采用Java語言實現(xiàn)算法并將其與NaiveBayes、KNN、J48(C4.5) 、SMO[18]和 BP-KNN[19]5 種算法進行對比。利用Weka[20]平臺，在15個數(shù)據(jù)集上對以上算法進行對比實驗，BP-KNN根據(jù)文獻[19]設置參數(shù)，其余分類器的參數(shù)均為Weka平臺下算法的默認值。實驗中模糊超網(wǎng)絡模型所涉及的隨機種子均設為seed=1 234。所有實驗結果均為采用5-折交叉驗證后的結果。

3.3 實驗結果

本次實驗將模糊超網(wǎng)絡分類算法封裝成Weka平臺可識別的分類器，所有的評價指標均由Weka平臺的評估器計算并輸出。表5～8分別給出了本算法與其他算法的正確率、查準率、查全率和F-Measure的結果。

表 5 正確率值Table 5 Accuracy%

表 6 查準率Table 6 Precision

表 7 查全率Table 7 Recall

表 8 F-Measure值Table 8 F-Measure

圖 7 各項指標平均值柱狀圖Fig. 7 Average value of each indicator

表 9 不同算法在評價指標上的Rank平均值Table 9 Rank mean of differ ent algorithms in evaluation index

由圖7可知，相較于其他5種分類算法，本文提出的模糊超網(wǎng)絡算法在正確率、查準率、查全率上都具有一定的優(yōu)勢。為了進一步考查模糊超網(wǎng)絡分類算法與對比算法之間的比較效果，本文根據(jù)這6種算法在各個評價指標上的實驗結果，按照 1、2、3、4、5、6的次序進行 Rank排序評分，得到了如表9所示的6種算法在15個實驗數(shù)據(jù)集上的各項Rank平均值。據(jù)集上，與分類效果較好的3個算法相比，F(xiàn)-hypernetworks的正確率下降了近13%，查準率、查全率和F-Measure上的結果也相差較大。通過分析可知，在tic-tac-toe數(shù)據(jù)集中，不同類別的樣本之間的相似度較高，約83%的樣本與異類樣本的最大模糊相似度不低于其與同類樣本的最大模糊相似度。而在分類效果較好的BLOGGER數(shù)據(jù)集上，這種樣本的數(shù)目只占總數(shù)的22%，在breastcancer數(shù)據(jù)集上僅有2%。由于超邊對這些樣本的識別率不高，模糊超網(wǎng)絡對其做出誤判的概率較大，如果數(shù)據(jù)集中存在大量的這種樣本，會導致最終的分類結果不理想。

結合圖7與表9可知，模糊超網(wǎng)絡在正確率、查準率、查全率、F-Measure的Rank平均值上均為最優(yōu)。本文選取的對比算法都是應用較為廣泛的分類算法，對實際生活中的大部分數(shù)據(jù)集具有較好分類效果。同這些優(yōu)秀的算法相比，模糊超網(wǎng)絡分類算法仍具有一定的優(yōu)勢，在Recall、Precision等指標上表現(xiàn)出了比較好的結果。

4 結束語

本文結合模糊粗糙集和超網(wǎng)絡的相關知識提出了一種模糊超網(wǎng)絡模型，用于處理分類問題。首先，根據(jù)模型的最優(yōu)模糊相似度閾值λ計算樣本的λ-等價類樣本集合；其次，根據(jù)該集合的分布情況來定義邊界域樣本、正域樣本和負域樣本，對于不同區(qū)域的樣本采取不同的處理方法生成超邊；然后，在超邊替代階段，同樣通過劃分3個區(qū)域來控制超邊的替換；最后，在分類時，會根據(jù)樣本的λ-等價類超邊來判斷樣本的類別。通過在15個UCI數(shù)據(jù)集上的實驗結果表明，模糊超網(wǎng)絡具有較高的適用性，在不同的數(shù)據(jù)集上都能取得較好的分類效果。但是，隨著訓練樣本數(shù)量的增大，模糊超網(wǎng)絡模型在初始化階段生成的超邊越多，模型在演化訓練階段所消耗的時間越長，最終會導致算法的運行時間較長，因此提高算法處理大數(shù)據(jù)的時間效率將是接下來的研究重點。