3.4.2　基于證據(jù)理論的填補方法

證據(jù)理論是一種處理不確定性信息的方法，由Dempster首先提出，并經(jīng)Shafer改進，故常被稱為Dempster-Shafer（D-S）理論。D-S理論具備直接表達不確定性的能力，與缺失值的特性相符合，因此可將其應用于缺失值填補等不完整數(shù)據(jù)的分析過程。

與多重填補法相似，基于證據(jù)理論的填補方法對每個缺失值進行多次填補，得到多組填補值，接著根據(jù)若干填補值求解多個分析結果并對其進行融合。不同于多重填補法的合并方式，該方法基于D-S理論合并分析結果，進而處理缺失值對分析產(chǎn)生的不確定性。

首先介紹D-S理論的基本概念。在證據(jù)理論的研究中，識別框架是一個互斥且非空的有限集合，可記為Θ，該集合代表某一問題所有可能的分析結果。冪集2^Θ包含Θ的所有子集，能夠體現(xiàn)出分析結果的不確定性，即有時無法得到某一問題的確切結果，而是會求出多個可能的分析結果。若Θ={a,b}，則其冪集可表示為式（3-120）：

冪集2^Θ內的集合也稱為“假設”（Hypothesis），每個“假設”都會被賦予一個信念值（Belief Mass），用于衡量其可信度。將冪集2^Θ映射為信念值的過程稱為基本概率分配（Basic Probability Assignment，BPA）或者基本信度分配（Basic Belief Assignment，BBA），與其對應的映射函數(shù)稱為mass函數(shù)，記作m(·)，定義見式（3-121）^[26]：

由式（3-121）可知，mass函數(shù)能夠將冪集2^Θ內的每個元素映射為[0,1]范圍內的數(shù)值，并且mass函數(shù)需滿足式（3-122）中的兩個約束：

式（3-122）中，m(?)表示空集的信念值，B表示冪集2^Θ內的元素，即“假設”，m(B)表示B的信念值。由式（3-122）可知，空集的信念值為0，并且冪集內所有元素的信念值總和為1。

信任函數(shù)（Belief Function），或者信度函數(shù)，可定義為式（3-123）：

式（3-123）中，B表示2^Θ內的集合，B₁是集合B中的元素，B的信任函數(shù)值等于該集合內所有元素的信念值總和。

似然度函數(shù)（Plausibility Function）的定義如式（3-124）所示，多數(shù)研究也將該函數(shù)譯為似然函數(shù)，但此處的似然函數(shù)和3.3.1節(jié)的似然函數(shù)，即Likelihood Function，是完全不同的概念。為了對二者做出明確區(qū)分，下面將該函數(shù)統(tǒng)稱為似然度函數(shù)。

式（3-124）中，B和B₂均表示2^Θ內的集合，B的似然度函數(shù)值等于冪集內與B交集不為空的所有集合的信念值總和。

信任區(qū)間用于表示某假設的信任度范圍，根據(jù)信任函數(shù)和似然度函數(shù)的取值情況，信任區(qū)間可表示為式（3-125）：

式（3-125）中，B表示冪集2^Θ內的集合，P(B)表示B的可信程度。

Dempster合成規(guī)則是指對兩個mass函數(shù)進行融合的方法，定義為式（3-126）：

式（3-126）中，B、B₁和B₂均表示2^Θ內的集合，m_1,2(·)表示合成后的mass函數(shù)，⊕表示合成算子，m₁(·)和m₂(·)表示待合成的兩個mass函數(shù)，K'表示歸一化因子，定義如式（3-127）所示：

D-S理論可對多個mass函數(shù)進行合成，從而獲得2^Θ內每個集合的信念值。為實現(xiàn)最終的決策支持，可根據(jù)式（3-128）將這些信念值轉化為識別框架Θ中每個元素的概率：

式（3-127）中，S表示識別框架Θ內的元素，B表示冪集2^Θ內的集合。

下面以一個具體實例闡述D-S理論的計算過程。假設在家庭經(jīng)濟情況數(shù)據(jù)集中，某家庭為貧困戶，則標記為a，否則標記為b。由此，某家庭是否為貧困戶的判定結果可構成識別框架Θ={a,b}，其冪集2^Θ={,{a},,Θ}。兩位專家在對某家庭的各類指標數(shù)據(jù)分析后，得出兩組分析結果，分別為m₁={0,0.3,0.5,0.2}，以及m₂={0,0.4,0.3,0.3}，m₁和m₂是基于mass函數(shù)m₁(·)和m₂(·)所得信念值構成的集合，其中每個位置上的數(shù)值表示2^Θ中相應位置上元素的信念值。例如，專家1認為該家庭是貧困戶這一假設為真的可信度是0.3，專家2認為是此可信度是0.4。綜合兩位專家的分析結果，根據(jù)式（3-126）所示的Dempster合成規(guī)則對結果進行融合。

首先計算歸一化因子，結果如式（3-129）所示：

接著合成兩組分析結果，根據(jù)mass函數(shù)的性質，m_1,2()=0，而合成之后{a}、和Θ的信念值分別如式（3-130）、式（3-131）和式（3-132）所示。

根據(jù)合成后的mass函數(shù)m_1,2(·)計算信念值，并將得到的信念值構成集合m_1,2={0,0.41,0.51,0.08}。為了實現(xiàn)最終的決策支持，采用式（3-128）將這些信念值轉化為如式（3-133）所示的概率：

根據(jù)概率值可知，所研究家庭為貧困戶和非貧困戶的概率分別是0.45和0.55，因此可把該家庭納為非貧困戶。

鑒于D-S理論能夠合成多個mass函數(shù)，利用該理論可有效合并由多組填補值得到的分析結果。與多重填補法類似，基于證據(jù)理論的缺失值填補方法同樣包括3個步驟：填補、分析和合并。填補階段，對缺失值進行多次填補并得到多個完整數(shù)據(jù)集；分析階段，基于填補后的若干完整數(shù)據(jù)集展開分析并求解多個分析結果；合并階段，利用D-S理論對多個分析結果進行融合，以獲得最終的分析結果。接下來詳細介紹基于證據(jù)理論的缺失值填補方法^[27][28][29]。

首先在填補階段，根據(jù)3.4.1節(jié)所述的基于隨機干擾項的多重填補法、貝葉斯多重填補法等為每個缺失值計算多個填補結果。此處采用KNN的思路計算多個填補值，即首先為每個不完整樣本尋找K個近鄰樣本，接著以每個近鄰樣本中的相應屬性值填補缺失值。例如，針對不完整樣本x_i，在填補后可得到K個填補樣本x_i^(k)(k=1,2,…,K)，其中，x_i^(k)表示以第k個近鄰樣本的屬性值填補缺失值后得到的完整樣本。

為了使描述更加清晰，此處假設不完整數(shù)據(jù)集具體分析過程是分類，以此介紹基于多組填補結果的分析與合并過程。令Θ表示識別框架，即類標簽所有可能取值構成的集合，Θ={l₁,l₂,…,l_C}，C表示類標簽可取值的數(shù)量。在分析階段，利用分類算法對填補后的多個完整數(shù)據(jù)集展開分析，從而為不完整樣本x_i計算K個分類結果，P_i^(k)={P_i^(k)(l₁),P_i^(k)(l₂),…,P_i^(k)(l_C)}，其中P_i^(k)(l_c)(k=1,2,…,K；c=1,2,…,C)表示基于第k個填補樣本x_i^(k)將樣本x_i劃入第c類的概率。

令Ω={Θ,{l₁},{l₂},…,{l_C}}，元素Θ的加入是為了使后續(xù)求解的mass函數(shù)滿足式（3-122）的約束，即所有信念值的總和為1。合并過程可分為3步：針對K個分類結果計算K個mass函數(shù)，分別記為m_i^(k)(·)(k=1,2,…,K)；在考慮缺失值的基礎上，進一步處理K個mass函數(shù)，即將其轉化為針對每個類標簽的mass函數(shù)，記為_i^(lc)(·)(c=1,2,…,C)；融合C個mass函數(shù)_i^(lc)(·)(c=1,2,…,C)，得到最終的mass函數(shù)m_i'(·)，對該函數(shù)所得的信念值進行歸一化以計算最終的類標簽。下面介紹具體實施過程。

步驟1：由于填補精度的不同，基于樣本x_i^(k)得到的分類結果具有不同的可信度。若x_i^(k)中填補值與真實值間存在較大誤差，則相應的分類結果P_i^(k)可能并不準確。因此，可在考量填補算法性質的前提下，為每個分析結果計算一個權重，以此衡量結果的可信度。鑒于KNN方法的性質，可根據(jù)不完整樣本與近鄰樣本間的距離求解權重，若距離較遠，則認為填補值的精度相對較低，分類結果的可靠性也相對較低。

令d_ik表示不完整樣本與其近鄰樣本間的距離，則權重可以由式（3-134）求得：

式（3-134）中，w_i^(k)表示第k個近鄰樣本對應的權重。

為使w_i^(k)位于區(qū)間[0,1]內，根據(jù)式（3-135）對上述權重進行歸一化，由此得到相對可信度a_i^(k)：

式中，。

基于D-S理論，為Ω內每個集合分配信念值，相應的mass函數(shù)m_i^(k)(·)可表示為式（3-136）：

式（3-136）中，B_c表示Ω內除Θ以外的集合，所有集合的信念值總和為1，其推導過程如式（3-137）所示。

由此可得到K個mass函數(shù)m_i^(k)(·),k=1,2,…,K。

步驟2：根據(jù)式（3-138）對mass函數(shù)進行分組：

式（3-138）中，G_c表示由mass函數(shù)構成的集合，在mass函數(shù)m_i^(k)(·)的基礎上，計算識別框架Θ中每個元素為真實結果的概率。該函數(shù)已在式（3-128）進行說明，本例中該函數(shù)可進一步表示為式（3-139）：

接著，對分組G_c內的多個mass函數(shù)進行合成，合成后得到的mass函數(shù)可記為m_i^(lc)(·)，計算方法如式（3-140）所示:

式（3-140）所求mass函數(shù)m_i^(lc)(·)具有不同的可信度。分組G_c可視為基于投票機制產(chǎn)生的集合，K個mass函數(shù)m_i^(k)(·)各擁有1票，并且只能為一個分組投票，而投票的表現(xiàn)形式是將自身加入分組。擁有票數(shù)越高的分組，即元素個數(shù)越多的分組，其可信度也越高。

令β_i^(c)表示分組G_c的可信度，其定義為式（3-141）：

式（3-141）中，a₁、a₂和a₃是對數(shù)函數(shù)的參數(shù)，n_c表示分組G_c內元素的個數(shù)，n_max=max(n₁,…,n_C)。利用分組的可信度對m_i^(lc)(·)進行修正，修正后的mass函數(shù)_i^(lc)(·)見式（3-142）：

步驟3：針對集合Ω={Θ,{l₁},{l₂},…,{l_C}}中的每個元素，_i^(lc)(·)為其分配取值在[0,1]區(qū)間的信念值。采用合成規(guī)則將_i^(lc)(·)合為一個mass函數(shù)m'(·)后，即可借鑒式（3-139）設計BetP_m'i(·)函數(shù)，并得到最終的分析結果。然而，基于上述方式所得的最終分析結果僅能從集合Θ={l₁,l₂,…,l_C}中產(chǎn)生，即每個樣本會被明確地指定為某一具體類。鑒于部分不完整樣本的質量較低，分類結果存在不確定性，故無法將其明確指定為一個具體類。與其將樣本誤判為某一具體類，不如將其指定為多個隸屬概率極大的類，由此避免誤判。

基于上述思路，mass函數(shù)_i^(lc)(·)合成前，對集合Ω={Θ,{l₁},{l₂},…,{l_C}}進行擴充。首先采用式（3-143）求解每個mass函數(shù)_i^(lc)(·)最傾向的分類標簽。

隨后，將可能性較大的多個類標簽構成集合Φ_i，該集合的定義見式（3-144）：

式（3-144）中，n_c表示_i^(lc)(·)對應分組G_c的元素個數(shù)，n_max表示分組G^c所含元素個數(shù)的最大值，ε表示閾值。由式（3-144）可知，僅當分組G^c的元素個數(shù)足夠大并滿足閾值限制時，才能將_i^(lc)(·)最傾向的分類標簽l_c^*置入集合Φ_i內。

接著，根據(jù)集合Φ_i對Ω進行擴充，令擴充后的集合記為Ω'，其定義如式（3-145）所示：

式（3-145）中，Φ_i'=2^Φi-{{l_c}|c=1,2,…,C}-，是冪集2^Φi內元素數(shù)量大于1的集合。在集合Ω'的基礎上，對mass函數(shù)_i^(lc)(·)進行合成，合成規(guī)則見式（3-146）。

式（3-146）中，B表示Ω'內的元素，m_i'(B)表示合成后B的信念值，需分兩種情況計算m_i'(B)。若B?Ω，令B_c表示Ω內的任意元素，僅當這些元素的交集等于B時，才可提取mass函數(shù)_i^(lc)(·)關于相應元素的信念值_i^(lc)(B_c)(c=1,2,…,C)，并采用連乘操作求解運算值，由此得到m_i'(B)。若B?Φ_i'，利用B(c)(c=1,2,…,|B|)提取B內第c個元素，從而得到可能性較大的分類標簽lB(c),c=1,2,…,B，并得到相應信念值_i^lB(c)(B_c)。令B=Θ-B，利用B_(g)(g=1,2,…,|B_|)提取集合B_內第g個元素，進而得到可能性較小的分類結果l_{B_(g)}，并獲得相應的信念值_i^lB_(g)(Θ)，接著將所得信念值進行連乘操作以求解運算值，由此獲得信念值m_i'(B)。

最后，采用式（3-147）得到歸一化后的mass函數(shù)m_i(·)。

至此，合并過程結束，m_i(·)為集合Ω'內的每個元素分配了取值范圍在[0,1]內的信念值，最大信念值對應的元素將作為最終的分類標簽。

基于證據(jù)理論的缺失值填補方法通過定義一系列合并規(guī)則對由多組填補值得到的分析結果進行有效融合，以此得到最終的推斷。其與多重填補法存在諸多相似之處，均包括填補、分析與合并過程。多重填補法更加注重填補期間多組填補值的獲取，而本節(jié)所述方法則更加注重多組填補值所得分析結果的合并。因此，可在兩種方法的基礎上設計缺失值填補方法，使得填補與合并過程更加合理，從而有效應對缺失值所導致的不確定性。