基于FDR的證據理論改進算法

侯慶山，邢進生

(山西師范大學 數學與計算機科學學院，山西 臨汾 041000)

0 引 言

證據理論[1]是模糊決策的有效工具，在目標識別、決策、優化[2-3]等問題中得到了廣泛的應用。為了簡化樣本在特征融合過程中的復雜性，往往在特征融合前對原始樣本的特征進行簡單的篩選、降維[4]等一系列處理。此外，樣本特征權重分配對實驗結果的影響較大，對此可以采用這樣的方法：在特征融合時，對于相互矛盾的樣本特征，可以分配較低權重或分配權重為零。但是，當數據樣本特征過多時，這樣的處理方式往往是過于復雜的。

為了減小證據沖突的影響，文獻[5]提出了一種基于將證據交集部分轉化為聯合部分的組合規則。但是，隨著沖突的增加，該方法的性能變得越來越差。文獻[6]提出了一種基于計算所有證據平均值的證據組合方法，但并沒有考慮證據權重對于融合結果的影響，將所有的權重設定為同一值。因此，為了更好地確定每個證據的權重，引入證據相似性來計算每個證據的沖突程度，模糊度較大的證據由于包含的信息少而賦予較小的權重值，這樣的證據權重分配更為合理，因此樣本分類更準確。文獻[7]提出了一種基于文獻[8]模糊度測量方法的證據組合規則，文獻[8]提出了一種改進的基于證據距離測量的平均組合方法，每個證據主體(body of evidence，BOE)的權重都被考慮在內。但文獻[8]的組合規則不能有效地處理高度沖突的證據組合。針對這一問題，文獻[7]提出了一種新的加權平均證據組合方法,一方面利用證據的距離，另一方面利用不確定性度量來確定證據主體的權重，可以得到合理的組合結果。但隨著樣本特征增多，利用不確定性度量來確定證據主體的權重變得困難。文獻[9]提出了另一種基于信息熵的證據組合規則，該方法能有效地處理高沖突證據，具有較好的收斂性能，但信息熵的確定需要經過復雜的計算，隨著樣本的特征數量及分類增多，這種方式的可行性越來越低。文獻[10]提出了一種基于證據相似性和懲罰函數的組合規則，該方法將證據分為可信證據和不可信證據兩部分。然后，用一種新的信息熵來度量證據的信息量。最后，得到每個證據的權值，并在使用Dempster組合規則之前對證據進行修改，該方法能有效地處理沖突證據，具有較好的收斂性，但對證據進行劃分時，由于劃分方法存在不足，容易對證據劃分錯誤。文獻[11]基于不一致測量值的沖突證據組合方法，提出了一種測量兩種證據沖突的新方法，通過選擇折現系數對矛盾證據進行修正，但改進后組合規則的融合效果提升不夠明顯。文獻[12-13]提出了兩種證據理論的組合方法，前者基于證據距離和模糊偏好，后者基于證據相似性和信念函數熵，然而，這兩種方案仍然存在相似性沖突，樣本特征的融合過程仍然復雜。

由于相似性碰撞現象[14]以及原始樣本特征之間存在關聯性，導致現有的證據融合規則過于復雜。此外，現有的融合規則存在無法有效降低沖突證據權重[6]的缺陷。在分析已有算法的基礎上，文中提出一種改進的證據融合算法。在樣本融合之前進行特征篩選，刪除對分類影響較小的特征，簡化初始樣本特征數量，從而降低融合過程的復雜性。相較于其他融合算法在復雜數據集上的融合過程及融合效果，該算法的過程較為簡單，融合效果更好。

1 基礎理論

1.1 D-S證據理論

Dempster和Shafer提出的證據理論是一種從不確定信息中進行決策的有效工具。它在許多領域有著廣泛應用。有關D-S證據理論的相關定義如下：

定義1：證據理論的基礎。在實際應用中，通常2Ω是在空間Ω上的所有子集的集合,2Ω={?,{θ1},{θ2},…,{θn},{θ1,θ2},…,{θ1,θ2,…,θn}}。在D-S理論中,數學基本概率分配[15-16]函數,也稱為質量函數,滿足在2Ω→[0,1]上的映射,滿足式(1)。

(1)

定義2：似然函數。似然函數滿足式(2)：

(2)

m:m(A),m(B),m(C),…,m(AB),…,m(θ)

定義3：基于定義2，m(A)或m(B)是代表A或B的質量函數，根據Dempster提出的組合規則可以組合一組證據，滿足式(3)和式(4)：

(3)

(4)

m是m1和m2的組合結果。當證據數量大于2時，擴展組合規則如式(5)和式(6):

m(A)=

(5)

(6)

運用上述公式可以實現證據融合，但是當某一證據的支持度較小或者不被支持時，組合結果往往是不理想的。為此，一方面可以通過引入證據權值減少此類證據的影響，另一方面可以在樣本融合前進行特征篩選，刪除支持度小的特征。

1.2 特征選擇

在樣本特征中往往存在較高的相關度，導致在計算上產生了較大消耗；此外，部分特征對預測結果往往存在不好的影響，甚至是負影響。因此針對樣本特征進行選擇，即從樣本的所有特征中選擇部分特征作為新的樣本特征，特征值在選擇前后可以改變或者不改變，但是選擇后的特征維數必然會降低。常用的特征選擇方法主要包括以下兩種：

(1)均方差分析法。

該方法一般設置某一特定的方差閾值，刪除低于閾值的特征；若方差閾值未指定，則保留所有非零方差特征，刪除樣本中具有相同值的特征。均方差分析法往往適用于樣本特征較少的數據集，利用方差對樣本數據集進行分析時，與極差和標準差相比較，方差的計算結果能夠將樣本特征的波動性放大，可以準確地觀察出某一樣本特征對于樣本分類結果的影響程度。不足之處在于，利用方差對樣本數據集進行分析要處理數據集上的全部數據，隨著數據量和樣本數的增多，計算過程將變得復雜。因此方差分析常常運用在數據量或樣本特征量較少的數據集上。

(2)主成分分析法。

主成分分析法[17]是一種分析及簡化數據集的方法，其目的是降低數據維數，盡可能地降低原始數據的復雜度并使數據損失盡可能的小。利用主成分分析法可以消減回歸分析或者聚類分析中特征的數量。在高維數據集中，許多特征之間通常是線性相關的，利用主成分分析可以減小相關特征的個數，降低樣本特征間的相關性。但是，對高維數據集進行主成分分析時，首先要確保提取的前幾個主成分的貢獻率之和應當達到較高水平；其次，對于降維后的樣本特征，特征含義一般具有模糊性。在樣本特征數量較少時，一般不采用此類方法，因此只有在高維數據集中才使用主成分分析法。

2 基于特征降維的證據理論的改進算法

原始樣本數據集進行特征降維之后，減少了相關特征的個數，對降維數據生成新的BPA。對于簡單數據集，采用方差分析法，選擇方差大于閾值的特征。對于復雜數據集，采用主成分分析法，對樣本特征進行選擇和降維處理。算法過程描述如下：

輸入：原始數據集矩陣

輸出：降維數據集矩陣

算法步驟描述如下：

(a)將初始數據按行列排成n行m列的矩陣X；

(b)將矩陣X的每一行進行零均值化處理；

(d)將特征向量按對應特征值的大小按行排列成矩陣，取前K行組成矩陣P；

(e)Y=PX即為降維到K維之后的數據，對所得數據集樣本抽樣；

(f)對抽樣樣本進行聚類，標注樣本特征以及樣本所屬類型；

(g)生成區間數模型，針對數據集的某一特征，取所有樣本中的最大值以及最小值分別作為所求區間的上界以及下界；

(h)求解某一測試樣本特征值與區間數的距離。設A=[a1,a2]和B=[b1,b2]是兩個區間數，則區間距離[18]可用式(7)計算：

本工作主要是研究冪零群、內冪零群以及內交換群所對應冪圖的一系列圖論性質.由于這類群結構比較清晰,可以對其相應冪圖或真冪圖的性質作進一步研究,主要從能否為線圖、獨立數性質、可平面性以及連通性等角度討論.特別地,由于一般群G的任意元素都與單位元相連,故在考察連通性時僅對真冪圖P?(G)進行討論.

(7)

(i)求解測試樣本特征值與區間數模型之間的相似度。設A=[a1,a2]和B=[b1,b2]是兩個區間數,相似度計算可采用式(8)：

(8)

其中，α(α>0)為支持度系數。

(j)對求解的相似度進行歸一化處理，將歸一化之后的結果作為最終BPA。

算法流程如圖1所示。

圖1 算法流程

特征選擇和降維是改進算法中的關鍵環節，為了便于理解改進算法中包含的降維算法部分，舉例如下：

原始數據集矩陣X：

去均值：

特征值：

特征向量：

標準化：

選擇大特征值對應的特征向量：

利用公式Y=PX計算經過PCA降維后的數據集矩陣：

3 實 驗

3.1 數據集描述

實驗所采用數據集取自超過200 000名Instacart用戶的300多萬份雜貨訂單的樣本，該數據集是匿名的，描述客戶訂單隨時間變化的關系。主要是為了預測哪些產品更有可能出現在用戶的下一個訂單中。對于每個用戶，提供4到100個訂單，每個訂單中的產品按順序購買。還提供訂單下達的時間，包括星期和小時，以及訂單之間的相對時間度量。

3.2 數據庫介紹

每個實體(客戶、產品和訂單等)都具有關聯的唯一ID。數據表和變量名稱應該是客觀真實的。數據表order_products_prior.csv包含所有客戶的先前訂單內容,數據表orders.csv表明訂單的組別，數據表說明如表1所示。

表1 數據說明

3.3 原始數據降維處理

(1)讀取四張數據表，利用表中的關聯ID將表進行合并處理，然后選取500組合并數據進行實驗，部分合并數據如圖2所示。

圖2 數據表合并處理后部分數據

(2)利用交叉表對每一個用戶所購買的物品進行分組，分組后的部分數據如圖3所示，表中每一行代表一個用戶，每一列代表各用戶購買某物品的個數。

圖3 用戶購買情況部分數據

(3)利用主成分分析算法對數據集進行特征降維，降維后的數據集保存了原數據集90%的信息，特征數量則下降到27個，簡化了原始數據集的復雜度，部分降維后的數據如圖4所示。

圖4 降維后部分數據

(4)對降維后的數據集利用K-means[19-20]算法進行聚類分析，取出數據集中的前500個樣本，劃分為5類用戶，分別由數字0到4表示，聚類結果如圖5和圖6所示。

圖5 樣本聚類結果

圖6 聚類分布

(5)對以上聚類結果進行分析，計算聚類數據集的輪廓系數為0.612 7，因而可以判定聚類效果良好，輪廓系數可以采用式(9)進行計算：

(9)

其中，i為已聚類數據中的樣本，bi為i到其它簇的所有樣本的平均距離，ai為i到本身簇的距離平均值，最終通過計算所有樣本點的輪廓系數平均值對聚類效果進行分析評定。如果sci小于0，說明ai的平均距離大于最近的其它簇；相反的sci的值越大，說明ai的平均距離小于最近的其他簇，輪廓系數的值是介于[-1,1]，越趨近于1代表數據集的內聚度以及分離度都相對良好。

3.4 對降維后的數據集生成BPA進行分類識別

(1)用降維后的樣本數據作為驗證數據庫,選擇5種用戶類型的400個樣本，每種類型各占80個，取樣本中的最大值以及最小值來構造區間數模型，如表2所示。

(2)選取100個測試樣本，5類用戶各占20個，將它們作為類別未知的測試樣本。

(3)通過計算測試樣本與區間數模型之間的相似度，求解出各特征值最終的BPA。進一步通過D-S組合規則進行特征融和，產生最終的融合結果。

(4)對融合結果進行分析，測試樣本的類型由融合結果決定，哪種類型的BPA的值最大，那么這個BPA對應的類別就是待測樣本的類別。

表2 區間數模型

續表2

3.5 實驗結果分析

為了檢驗改進算法在Instacart數據集上的分類效果，選取支持度系數α的值為5，在表2所示的區間數模型的條件下，對500個待測樣本的數據集進行測試，包括400個已知分類的訓練樣本以及100個未知類型的測試樣本。實驗得出最終的平均類型識別率為94%，對0類型以及3類型用戶的識別率達到96%，1類型以及4類型的用戶識別率達到92%，2類型用戶識別率到達94%。

4 結束語

由于傳統證據融合算法在特征融合時過于復雜，樣本間存在相似性碰撞，在復雜數據上融合效果不夠理想，證據之間存在沖突等問題。文中提出了一種基于特征降維的證據理論改進算法，并采用Instacart數據集對改進算法進行檢驗。與其他相關算法相比，改進算法簡化了證據融合過程中的復雜性，降低了原始樣本中特征關聯對于融合結果的影響。由實驗結果可知，改進算法對于分類問題的平均準確率為94%。由于主成分分析存在降維后特征含義不夠明確，證據融合過程中如何將權重合理分配給相關特征等問題，所以下一步工作可以針對特征降維方法以及權重的合理分配做出改進，進一步提高證據融合的效果。