不完備數據集的鄰域容差互信息選擇集成分類算法

李麗紅 ,董紅瑤 ,劉文杰 ,李寶霖 ,代 琪

（1.華北理工大學理學院，唐山，063210；2.河北省數據科學與應用重點實驗室，華北理工大學，唐山，063210；3.唐山市工程計算重點實驗室，華北理工大學，唐山，063210；4.華北理工大學人工智能學院，唐山，063210；5.中國石油大學（北京）自動化系,北京，102249；6.首鋼礦業公司職工子弟學校，唐山，064404）

在大數據時代，數據具有不確定性、動態更新、不完備性等特點.其中，數據挖掘領域常用的UCI 數據庫中有40%左右的數據集是不完備的.針對不完備數據集的分類問題，可以通過簡單刪除法或者填充法將不完備數據集進行處理，再用完備的數據集做進一步的分類，但這種方法不能保證數據是否為隨機缺失，從而對分類精度產生影響［1］.盡管近年來對不完備數據集的研究逐漸增多，但目前不完備數據集中的大部分分類算法是針對只含有離散屬性值的數據集設計的［2］.然而，有一種常見的情況是數據集為既含有離散型屬性又含有連續型屬性的混合形式，如從商業、醫療、銀行、人口普查和生物科學中收集的數據，都是混合型的.對于醫學數據，除了血壓和血糖等連續型屬性外，還包括性別和是否對某種藥物過敏等離散型屬性，人口普查收入數據包括職業、教育水平和婚姻狀況等離散型屬性，以及年齡、工資和每周工作時間等連續型屬性.針對連續型屬性值通常采用離散化的計算方式將連續型數值直接轉化為離散型數值，這樣會帶來信息損失，從而影響分類準確率［3］.所以學者提出了直接處理不完備混合型數據集的方式，如利用相容關系［4］、限制鄰域關系［5］和鄰域容差關系［6］等，不同的數據結構采用不同的逼近機制和?；绞綐嫿？臻g再進行下一步數據操作［7］.對于不完備混合型信息系統的分類問題，為進一步提升其分類性能，將集成分類方法引入研究.

目前針對不完備混合型信息系統的集成分類算法研究較少.Krause and Polikar［8］首次提出Learn+MF 集成算法處理不完備數據集的分類問題，子分類器在隨機特征子集上進行訓練，這種方法相對復雜，效率較低.因為集成分類算法針對不完備數據集的分類問題具有較好的冗余性而且適用性廣，它不會因為對數據集假設不當使最終構建的模型產生偏差，而且可以充分利用數據集的信息，所以，用集成算法處理不完備數據集的問題相繼被提出［9］.Chen et al［10］與呂靖和舒禮蓮［11］提出一種基于不完備數據集的不完備特征組合的集成框架，該方法不需要任何關于缺失數據的假設，但沒有考慮不同特征子集重要程度的差異.在一般集成框架的基礎上，通過考慮特征重要度，提出了多粒度集成方法（Multi-Granularity Integration Method，MGNE）［12］，然而，對于含有大量不完整樣本的數據集，該方法性能有待提高，同時，隨著缺失值數量的增加，這些算法非常耗時.為克服傳統集成學習技術的高計算成本的不足，集成剪枝是一種常見提升性能的方法［13-15］.Yan et al［16］針對不完備數據集提出一種選擇性神經網絡集成分類算法，與傳統神經網絡集成算法在保證精度的前提下相比，提高了算法效率.并且針對不完備混合數據集的分類問題，傳統的集成分類算法在賦予各個子分類器權重時，僅考慮數據集中所含樣本的多少和屬性的維數，并沒有考慮不同屬性或屬性組合對最終分類結果的貢獻度.因此，如何有效地衡量不完備混合系統中屬性對分類結果的貢獻度，從而更加合理地計算基分類的權重提高分類的準確率有待進一步完善和解決.

針對上述問題，根據當前利用集成分類算法和粗糙?；枷胩幚聿煌陚浠旌蠑祿牟蛔慵皟瀯?，本文提出基于鄰域容差互信息的選擇集成分類算法（Neighborhood Tolerance Mutual Information Selection Ensemble Classification Algorithm，NTMISECA）.首先定義鄰域容差互信息，并詳細描述基于鄰域容差互信息選擇集成分類算法的思想和步驟，然后介紹驗證該算法采用的實驗數據的詳細信息與仿真環境，最后對實驗結果進行討論和總結以及闡述未來研究的工作重點.

1 基本原理

1.1 不完備混合型信息系統

定義1［17］設一個混合型信息系統為S=(U，A).其中，U為信息系統的論域，A=C∪D稱為信息系統的屬性集合，C=Cd∪Cc稱為信息系統的條件屬性集合，D稱為信息系統的決策屬性集合.這里的Cd為條件屬性值是離散型數值，Cc為條件屬性值是連續型數值.

若?x∈U，x在屬性a(a∈A)上的取值未知，通常用“*”表示，即a(x)=*，那么此時S稱為不完備混合型信息系統.

1.2 粒計算粒計算主要目的在于通過對問題的?；纸?，使復雜問題得以簡單處理，體現問題處理的多維度、多視角、多層次的思想［18］.通過研究粒的產生、粒的性質以及?；绞?，提出數據處理的數學方法，支撐模型的建立，實現計算機程序化處理.

一個本質性問題是基于粒計算理論對信息進行?；?，不同的?；椒梢垣@得不同的粒層信息，?？臻g的結構直接決定目標的求解效率.常用的?；椒ㄒ罁P系，如等價關系、相似關系、領域關系、優勢關系等，同一類樣本分配到同一個信息粒中［19-23］.一般地，存在兩類造粒過程，如功能造粒和關系造粒.如果該構造過程完全基于樣本屬性，稱為功能?；?；如果?；^程基于樣本之間的關系，稱為關系?；?在?；^程中，若給定多個不同的?；巹t，從多角度、多層次可以得到各不相同的粒層.本文針對不完備混合數據集，利用鄰域容差關系對數據集?；幚?

定義2［24］（鄰域容差關系）設S=(U，A)為不完備混合型信息系統，A=C∪D，設B?C為屬性子集，且B=Bd∪Bc.其中，Bd表示屬性子集中屬性值為離散值，Bc表示屬性子集中屬性值為連續值.設鄰域為δ，則在不完備混合信息系統S下，根據屬性子集B確定的鄰域容差關系為：

其中，Δa(x，y)和Δb(x，y)分別表示對于離散屬性和連續屬性對象x與對象y之間的距離度量.那么對于?x∈U，關于的鄰域類定義如下.

1.3 信息論Shannon［25］首次在通信領域提出信息熵的概念，來衡量一個給定的隨機事件所包含信息量的大小.信息熵常被用來作為一個系統信息量的量化指標和屬性的分辨力，也是信息系統中相關性度量的一種常見手段.

互信息是信息論中一種有用的信息度量，可以用來直接衡量兩個變量之間擁有多少相同的信息量.它可以看成一個隨機變量包含另一個隨機變量的信息量，也可以看成一個隨機變量確定的情況下另一個隨機變量減少的不確定性.

定義3（互信息）若有隨機變量X和隨機變量Y，隨機變量X和隨機變量Y之間的互信息I(X，Y)表示如下：

其中，H(X)，H(Y)，H(X，Y)分別表示變量X的信息熵、變量Y的信息熵、變量X和Y的聯合信息熵.

若兩個隨機變量之間的互信息越大，則說明擁有的共同信息越多.反之，這兩個隨機變量之間擁有的共同信息越少.如果有多個隨機變量X1，X2，…，Xn和隨機變量Y，那么這組隨機變量集合與隨機變量Y之間的互信息定義為：

其中，H(X1，X2，…，Xn)，H(Y)，H(X1，X2，…，Xn，Y)分別為變量X1，X2，…，Xn的聯合熵，變量Y的信息熵，變量X1，X2，…，Xn，Y的聯合熵.

定義4［24］（鄰域容差信息熵）給定不完備混合型信息系統S=(U，A)，B?A，鄰域半徑為δ，且定義B的鄰域容差信息熵為：

定義5［24］（鄰域容差聯合熵）給定S=(U，A)為不完備混合型信息系統，A=C∪D，B1，B2?C，設鄰域半徑為δ，并 且則B1和B2的鄰域容差聯合熵記為：

如果設U/NTD={NTD(x1)，NTD(x2)，…，NTD(x|U|)}，對于任意B?C，D和B的鄰域容差聯合熵記為：

1.4 集成學習目前，一般認為集成學習的研究始于1990 年，Hansen 和Salamon 首次提出用神經網絡作為基分類器進行集成，使用該方法可以簡單地通過訓練多個神經網絡將其結果進行結合，從而對比單個神經網絡算法能顯著提高學習系統的泛化能力［23］.在Hansen 和Salamon 之后集成學習得到了廣泛的研究.

與采用單個學習器的機器學習方法不同，集成學習方法通過訓練多個基學習器，并將訓練結果結合考慮來解決一個問題.通常集成學習也稱為多分類器系統或基于委員會的學習.一個集成系統由多個基學習器構成，而基學習器由基學習算法在訓練數據上訓練獲得，如神經網絡、決策樹、樸素貝葉斯或其他學習算法.雖然傳統基分類器的種類繁多，但其分類精度有待提高且容易出現過擬合等.故集成學習方法很受關注.通常，集成學習具有比基學習器更高的預測準確率及更強的泛化能力［6］.圖1 表示一個通用的集成學習框架.

圖1 一個通用的集成學習框架Fig.1 A general purpose integrated learning framework

2 基于鄰域容差互信息的選擇集成分類算法

2.1 問題提出互信息可以衡量兩個離散變量之間擁有相同信息量的差異程度，同樣可以度量離散屬性集X與離散屬性集Y之間的相關程度.與條件熵不同的是，屬性集X與屬性集Y的互信息越大表明其相關性越大，反之，屬性集X與屬性集Y的互信息越小表明其相關性越小.對于既含有離散型屬性又含有連續型屬性的不完備混合型信息系統，引入鄰域容差關系，將鄰域容差關系和互信息結合，定義鄰域容差互信息的概念來衡量不同屬性或屬性組合與類別屬性之間擁有共同信息量的多少，為使最終的加權投票結果更加合理，改進基分類器的預測權重，提出基于鄰域容差互信息的選擇集成分類算法.

2.2 算法思想類比鄰域容差條件熵的相關理論，給出鄰域容差互信息的相關定義.

證明根據定義4 得：

定義7（鄰域容差互信息）設U/NTD={NTD(x1)，NTD(x2)，…，NTD(x|U|)}，對于任意B?C，D和B的鄰域容差互信息記為：

證明若B1?B2，則NTB2(xi)?NTB1(xi).那么，

對于不完備混合型信息系統，鄰域容差互信息可以用來衡量兩個變量X和Y之間共同擁有信息量的多少.若變量X和變量Y之間鄰域容差互信息越小，那么變量X和變量Y所包含的共同信息越少.極端情況下，當變量X和變量Y之間的鄰域容差互信息為0 時，則說明這兩個變量是獨立的，彼此之間沒有任何共同信息.若變量X和變量Y之間的鄰域容差互信息越大，那么變量X和變量Y所包含的共同信息越多，此時變量X和變量Y關系密切，其中一個變量變化會對另一個變量產生較大影響.

同樣，如果類別屬性對于條件屬性的鄰域容差互信息越大，那么它們的相關程度越大，則它們之間一一映射的程度越高.反之，類別屬性和條件屬性的鄰域容差互信息越小，就有理由認為它們之間近似一一映射的程度很低，則說明條件屬性和類別屬性之間的相關程度較小.特別地，如果條件屬性和類別屬性之間的鄰域容差互信息為0，表明條件屬性即便存在，也無法對最終類別的預測提供任何有效信息.

所以針對不完備混合型信息系統的分類問題，對于既含有缺失的離散型屬性又含有缺失的連續型屬性的樣本可以通過引入鄰域容差關系進行處理，結合互信息理論，定義鄰域容差互信息來衡量條件屬性對于類別屬性的重要度，再利用?；枷牒图煞诸愃惴ㄌ岢龌卩徲蛉莶罨バ畔⒌倪x擇集成分類算法.

利用鄰域容差互信息衡量缺失屬性對決策分類結果的貢獻度，在一個完整的數據集上計算缺失屬性與類別屬性的鄰域容差互信息，屬性對類別的貢獻程度越大，其作為條件的鄰域容差互信息越大；對決策分類結果的貢獻度越小，作為條件的鄰域容差互信息越小.使用鄰域容差互信息、信息粒大小和基分類器的預測準確率來衡量由此信息粒構建的分類器的權重，比僅使用屬性維數來衡量基分類器預測的權重更加科學，定義的權重公式如下：

其中，wi為第i個基分類器的預測賦予的權值，acci表示第i個基分類器的準確率，|Grai|表示第i個信息粒的大小，NTIi表示第i個信息粒的缺失屬性集合對應類別屬性的鄰域容差互信息.

2.3 算法流程基于鄰域容差互信息的選擇集成分類訓練流程圖如圖2 所示.基于鄰域容差互信息的選擇集成分類算法具體步驟如下.

圖2 基于鄰域容差互信息的選擇集成分類訓練流程圖Fig.2 Selective integrated classification training flow chart based on neighborhood tolerance mutual information

步驟1.根據不完備混合型數據集中的缺失屬性對樣本進行?；幚?，即把數據集中缺失屬性值相同的樣本劃分到同一信息粒，最終得到若干信息粒.

步驟2.為了提高預測準確率，充分利用含有缺失屬性的數據信息，進行最大化信息粒.首先再次遍歷原始數據集，將那些信息粒不含有缺失屬性集以及含有缺失屬性集的信息粒的屬性集合包含在某個信息粒的屬性集合中時，把此類信息粒中包含的樣本的缺失屬性集設置為該信息粒的缺失屬性集，形成最大化信息粒.

步驟3.首先根據定義劃分鄰域容差類，根據式（5）計算鄰域容差信息熵，根據式（7）計算鄰域容差聯合熵，最后以缺失屬性包括連續屬性和離散屬性作為已知條件，在完整的信息粒上根據式（10）計算基于類別屬性的鄰域容差互信息.

步驟4.在各個最大化信息粒上，以非缺失屬性作為輸入，以BP 算法為基分類器的集成分類算法進行集成學習，得到若干個分類預測模型.

步驟5.使用各個信息粒缺失屬性相應的鄰域容差互信息、信息粒的大小和子分類器的精度，根據式（10）計算各個子分類器的權值.

步驟6.進行預測.假設預測數據集中樣本的缺失屬性集是某個信息粒的缺失屬性集的子集，則可將該樣本與這些信息粒相對應的屬性集作為對應的子分類器的輸入，經過訓練后得出該樣本在這些子分類器上的預測類別，然后再根據這些基分類器的分析結果，按照步驟5 的權值公式進行加權集成，得到最終預測結果.

例給出不完備混合型數據集，如表1 所示，設置閾值δ為0.5（閾值過大或過小都會影響粒度的劃分.若閾值過大，劃分的粒會很粗；若閾值過小，會導致劃分的粒度較細，失去劃分粒層的意義，加大計算難度.合理閾值設置為0.4～0.6，所以選擇0.5 作為閾值）.計算條件屬性集與類別屬性的鄰域容差互信息.

表1 不完備混合型數據集Table 1 Incomplete mixed data set

根據表中不完備混合數據集的定義以及缺失模式的定義，樣本x1，x4，x5無缺失值，樣本x2的缺失屬性為{a4}，x3的缺失屬性為{a2，a3}，x6的缺失屬性為{a3，a4}.

按照缺失屬性進行劃分，則Granule={{x1，x4，x5}，{x2}，{x3}，{x6}}.不含缺 失屬性，則X1={x1，x4，x5}.缺失屬性{a4}，把不含缺失屬性的樣本去掉屬性a4，則X2={x1，x2，x4，x5}.缺失屬性{a2，a3}，把不含缺失屬性的樣本去掉屬性a2，a3，則X3={x1，x3，x4，x5}.若缺失屬性{a3，a4}，把不含缺失屬性的 樣本去掉屬 性a3，a4，把缺失屬性{a4}的樣本去掉屬性a3，則X4={x1，x2，x4，x5，x6}.

首先根據決策屬性D劃分鄰域容差類：

根據所有條件屬性C={a1，a2，a3，a4}劃分鄰域容差類：

根據條件屬性a1劃分鄰域容差類：

根據條件屬性a2劃分鄰域容差類：

根據條件屬性a3劃分鄰域容差類：

根據條件屬性a4劃分鄰域容差類：

根據條件屬性a1和條件屬性a2劃分鄰域容差類：

根據條件屬性a1和條件屬性a3劃分鄰域容差類：

根據條件屬性a1和條件屬性a4劃分鄰域容差類：

根據式（9）計算單個屬性的鄰域容差互信息：

根據式（9）計算屬性集合的鄰域容差互信息：

3 仿真實驗與性能分析

基于Python 實現算法仿真，驗證所提算法的可行性和有效性.實驗設備的基本信息如下.系統環境：CPU Intel i7-10750H；RAM：18 GB；操作系統：Windows 10 專業版；解釋器：Python 3.7.10.在3.1 中簡要介紹實驗使用的數據集和對比方法的基本信息.實驗結果在3.2 中給出并詳細分析實驗結果.3.3 給出非參數統計檢驗的實驗結果，驗證與對比算法之間的統計學差異.

3.1 實驗設置從UCI 數據庫和愛數科公共數據庫中選取七個公開獲取的數據集進行實驗驗證，表2 為實驗數據集的詳細信息，其中有一個數據集只包含離散屬性，一個數據集只包含連續型數據，三個數據集具有混合型屬性.此外，對于數據 集E-commerce transportation 和Shill Bidding，真實獲取的數據集為完備數據集，但為了驗證算法的可行性，通過從原始數據集中隨機選擇5%和10%的已知樣本特征值轉變為缺失值，形成四個人工不完備數據集.

表2 數據集的詳細信息Table 2 Details of the data set

為了降低由于數據劃分帶來的隨機性，采用十折交叉驗證的均值作為模型的最終得分.在所提方法中，采用BP 神經網絡作為集成分類算法的基分類器，學習率為0.1，隱藏層神經元個數為15，迭代訓練次數為15.本實驗使用的對比算法包括：極限梯度提升機（XGBoost）、隨機森林（RF）、梯度提升樹（GBDT）、自適應Boosting（AdaBoost）和Stacking.需要注意的是，實驗使用的分類器均采用Scikit-learn 學習庫的默認參數進行實驗.

3.2 實驗結果與分析

表3 至表6 給出部分數據集通過實驗得到的以各個信息粒缺失屬性作為條件關于類別屬性的鄰域容差互信息，其中信息粒缺失屬性按照缺失屬性從少到多表示.當所有屬性都為離散型屬性時，鄰域容差關系即為容差關系，例如Mushroom數據集，不含有連續型屬性，此時閾值設為0，其缺失屬性為一個.

表3 Housing loan 數據集缺失屬性的鄰域容差互信息Table 3 Neighborhood tolerance mutual information for missing attributes of Housing loan data set

表4 Adult 數據集缺失屬性的鄰域容差互信息Table 4 Neighborhood tolerance mutual information for missing attributes of Adult data set

表5 Credit 數據集缺失屬性的鄰域容差互信息Table 5 Neighborhood tolerance mutual information for missing attributes of Credit data set

表6 Water quality 數據集缺失屬性的鄰域容差互信息Table 6 Neighborhood tolerance mutual information for missing attributes of Water quality data set

由表3 至表6 可以看出，對于同一數據集信息粒中不同的缺失屬性集合作為條件的類別屬性的鄰域容差互信息是不同的，數據集中缺失屬性集合包含元素的數量與計算類別屬性的鄰域容差互信息是無關的.對于沒有缺失屬性的數據集，認為其丟失了一個與類屬性無關的條件屬性，則鄰域容差互信息為0.若以信息粒缺失屬性集合為條件的類別屬性的鄰域容差互信息較大，說明此缺失屬性集合對決策類別的貢獻率較大以及攜帶的信息量較大，對最終的決策類別較為重要.對于表3 的Housing loan 數據集，第二個屬性比第七個屬性鄰域容差互信息大，則認為第七個屬性對類屬性的影響更大，那么對于缺失第二個屬性的預測結果不如缺失第七個屬性的預測結果可信度高.根據實驗過程分析對于基分類器的預測準確率與信息粒包含樣本的多少是高度相關的，所以預測準確率出現很高或很低的情況.因此，在定義基分類器的權重時，充分考慮其鄰域容差條件熵，基分類器準確率以及信息粒的大小會更加合情合理，最終加權集成的分類器預測更加準確，構建的集成分類算法也更具有普適性.

對于處理不完備混合型數據的集成分類算法，最為典型的是XGBoost 算法，可以直接處理不完備數據集.由表7 的實驗結果可以看出，對于不完備混合型數據集的分類問題使用鄰域容差互信息選擇集成分類算法得到的分類結果的準確率普遍要高于傳統的XGBoost 算法的準確率，其中對于Housing loan數據集，用定義的權重公式（10）預測準確率比XGBoost 算法高6.1666%，但對于Adult 數據集，本節提出的算法預測準確率要高于XGBoost 算法，由于Adult 數據集缺失屬性較少，用插補法處理后使用隨機森林、GBDT、Ada-Boost、Stacking 算法預測準確率要高一些.對于其他數據集，本節提出的算法比傳統集成分類算法預測準確率也高，例如，對于Housing loan 數據集，準確率比GBDT 高9.9232%，對于Credit 數據集，準確率比AdaBoost 高6.0379%等.所以本節提出的基于鄰域容差互信息的選擇集成分類算法對于解決不完備混合型數據集的分類問題提供了新的思路，在公開的不完備混合數據集上的實驗結果證實了本節所提算法的有效性和可行性.

表7 不同分類器預測不同數據集準確率的對比Table 7 The accuracy comparison of different classifiers prediciting different datasets

3.3 非參數統計檢驗為了進一步驗證提出的NTMISECA 方法與其他對比方法之間的性能差異，使用Friedman 排名和Holm′s 事后檢驗方法，在所有實驗數據集上，驗證模型之間的統計學差異，結果如表8 所示.

表8 所有分類器的Friedman 排名和事后檢驗結果Table 8 Friedman rankings and postmortem results for all classifiers

根據表8 的非參數統計結果，可以發現提出的方法的Friedman 排名明顯優于其他分類方法.但是，根據常用的顯著性差異度量標準（p＜0.05），提出的方法與使用的對比方法不存在顯著的統計學差異，即提出的方法在所有數據集上的性能與對比方法是相近的，差異并不明顯.

在實驗使用的對比集成學習方法中，均使用決策樹作為模型的基分類器，而在提出的NTMISECA 方法中，使用神經網絡作為基分類器.神經網絡是一種適用性很強的分類方法，適用于大部分數據集，但是，神經網絡對模型的參數很敏感，可以使用經典的參數優化方法或搜索方法選擇最優的參數.此外，在基分類器的參數調整方面與使用決策樹的模型仍然存在差距.然而，提出的NTMISECA 是一種基于粒計算的集成學習框架，其基分類器可以根據實際需要調整.因此，也可以使用單一弱分類器或弱集成學習方法，從而有效地提高提出的方法的分類性能和泛化能力.

4 結論

本章根據粒計算的基本思想，利用集成學習的優勢，將鄰域容差理論和互信息理論結合，提出一種解決不完備混合型信息系統的分類問題的集成算法，即基于鄰域容差互信息的選擇集成分類算法.利用傳統集成算法對不完備數據集進行分類在權衡各個基分類器的權重時僅考慮數據的維度和屬性的多少是不夠科學的，不同的屬性對類別的貢獻程度也是不一樣的，所以提出鄰域容差互信息的概念來衡量.然后根據粒計算的思想按照缺失屬性將數據集劃分為不同的信息粒，為充分利用數據信息，將信息粒最大化，并用集成算法訓練出基分類器，利用信息粒的大小、鄰域容差互信息和基分類器預測準確率來定義基分類器的權重，再次實現加權集成投票.實驗表明該算法普遍比傳統的集成分類算法預測準確率高.

本文所選用數據集全部為靜態數據集，對于動態不完備混合型數據集如何設計集成分類算法，并且對于集成學習算法訓練時間會比較長，如何進一步減少預測時間，提升預測效率也是一個值得研究的問題.