[發明專利]一種嵌入式多類別屬性標簽動態特征選擇算法

在審

• 申請號: 201710222600.6
• 申請日: 2017-04-06
• 公開（公告）號: CN106991447A
• 公開（公告）日: 2017-07-28
• 發明（設計）人: 黃金杰;孔慶達;潘曉真
• 申請（專利權）人: 哈爾濱理工大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種嵌入式多類別屬性標簽動態特征選擇方法，其特征在于，包括以下步驟：首先介紹傳統基于互信息的特征選擇方法。

1.數據集合預處理

當今在現實世界中數據庫極其容易受到噪聲數據、空缺數據、以及不一致數據的侵擾，現階段有大量的數據預處理技術，大體上可以分為數據清理、數據集成、數據變換和數據規約技術。數據清理可以清除數據中噪聲數據、糾正不一致，自行填補樣本數據的缺失數據，數據變換(數據規范化)可以改進涉及距離度量的算法的精度和有效性。比如人們希望數據滿足某種特定的數據分布，或者希望將每個數據特征映射到某一段特定的數據區間內，都是需要進行數據變換。對于本文而言數據集合的預處理主要分一下幾個部分：第一將數據集合中的噪聲數據和不一致數據空缺數據進行處理。第二將數據集中與分類完全不相關的屬性數據進行刪除。第三將屬性數據進行范數歸一化處理使范數歸一化為1，則有：

${\hat{f}}_i=\frac{f_i}{\left|\right|f_i\left|\right|}---\left(1\right)$

2.互信息的相關知識

特征選擇的選擇目標是選擇出對于分類最有價值的特征屬性，特征選擇中關鍵性需要解決的問題是度量問題，度量問題要考慮屬性集與類別標簽之間的相關性關系、屬性集和屬性集的冗余性關系、以及標簽屬性集內部的相關關系。因此針對這種相互關系問題討論，選擇信息論中的互信息作為度量標準來分析屬性間的相關性。下面介紹一下信息論中相關理論和運算規則。

信息熵是信息論理論中至關重要的概念，信息熵是表征變量的一種不確定程度，目的是表述信息含量的多少。

$H\left(X\right)=-\underset{i=1}{\overset{n}{\Σ}}p\left(x_i\right)\log p\left(x_i\right)---\left(2\right)$

其中，p(x_i)表示變量X取值為xi的概率，變量X的不確定程度就可以用信息熵H(X)來表示,H(X)值的大小只與變量的概率分布有關系，故在信息熵有效的克服了部分噪聲數據的干擾。

條件熵是指已知一個變量的條件下，另一個變量的不確定程度，即一個變量對另一個變量的依賴程度的強弱程度，故隨機變量X對另一個隨機變量Y的依賴程度可以用條件熵來表征。

$H\left(X\right|Y)=-\underset{j=1}{\overset{m}{\Σ}}p\left(y_j\right)\underset{i=1}{\overset{n}{\Σ}}p\left(x_i\right|y_j)log2p\left(x_i\right|y_j)---\left(3\right)$

其中，p(x_i)表示變量X的先驗概率p(x_i|y_j)表示變量Y在已知的條件下變量X的后驗概率。

互信息是表征兩個隨機變量之間的相互依賴程度，表示兩個變量之間的共同擁有的信息量的多少，當互信息的值為0即為最小值表示兩個變量之間不存在相同的信息，當互信息值較大時表示兩個變量所包含的相同信息比較多。定義為：

I(X；Y)＝H(X)-H(X|Y) (4)

互信息能夠非常有效的反映出兩個隨機變量之間的相互關系，并且能通過數值的形式表示出來，用數值的大小來表述兩個隨機變量之間的相互關系的緊密程度，但是在計算兩個隨機變量相互的信息量的同時還要考慮信息的增長情況，如果直接用互信息的大小來選擇特征，將會選擇那些取值比較大的特征，所以將互信息進行歸一化處理，處理過程中采用對稱不確定性SU度量特征變量與特征變量之間的相互關系的程度公式如下：

$SU(X,Y)=\frac{2I(X;Y)}{H\left(X\right)+H\left(Y\right)}---\left(5\right)$

由公式(5)可以看出SU相關度量值的變化范圍是由0到1，如果SU的值為0，表示X與Y不存在相關性，即X與Y是相互獨立的。如果SU的取值為1，表示X與Y存在很強的相關性，如果X與Y分別表示屬性信息和類別信息，SU的值越大則表示特征對于類別的選擇存在強相關性。如果X與Y分別表示兩個屬性信息，SU的值越大則表示特征與特征之間，屬性與屬性之間最在很強的冗余性。

3.基于互信息的度量問題

通過信息論中互信息理論，單一特征屬性與單一特征屬性之間的冗余性、單一特征屬性與單一標簽類別屬性之間的相關性、單一標簽類別屬性之間的相關性可以由如下的公式進行計算：

Redundancy(X_i；X_j)＝SU(X_i,X_j) (6)

Correlation(X_i；Y_j)＝SU(X_i,Y_j) (7)

Correlation(Y_i；Y_j)＝SU(Y_i,Y_j) (8)

通過上式對于單個特征屬性與特征屬性集合之間的冗余性的計算公式可以通過單個屬性特征與特征屬性集合中每一個屬性特征的冗余性求和取平均的方法進行計算,公式如下：

$\mathrm{Re}dundancy(X_i;X)=\frac{1}{\left|X\right|}\underset{X_j\∈X}{\Σ}\mathrm{Re}dundancy(X_i;X_j)---\left(9\right)$

其中，|X|表示特征屬性集合中，特征屬性的個數，X_j表示特征屬性集合中的某個特征屬性。

算法考慮到應用范圍是多標簽的特征選擇算法，所以對單一特征屬性與多標簽類別屬性所構成的集合產生的相關性公式定義為：

$Correlation(X_i;Y)=\frac{1}{\left|Y\right|}\underset{Y_j\∈Y}{\Σ}Correlation(X_i;Y_j)---\left(10\right)$

其中，|Y|表示標簽類別屬性集合中標簽類別屬性的個數，Y_j表示標簽類別屬性集合中的某個標簽類別屬性。

這種嵌入式多類別屬性標簽動態特征選擇算法不但考慮了特征屬性之間的相互關系、特征屬性與標簽類別屬性之間的相互關系、還考慮到多標簽類別屬性內部之間的相互關系對特征選擇的影響，總來說，某類標簽的類別屬性如果與其他標簽的類別屬性具有較強的相關性，那么就此類標簽類別屬性而言，所選擇出來的特征屬性，會對其他與之相關性較強的標簽類別屬性同樣就有較好的分類性能。所以標簽屬性之間的相關性可以由下邊的式子加以求解。

$W\left(Y_i\right)=\frac{1}{\left|Y\right|-1}\underset{Y_j\∈Y,j\≠i}{\Σ}Correlation(Y_i,Y_j)---\left(11\right)$

其中，|Y|表示標簽類別屬性集合中標簽類別屬性的個數，Y_j表示標簽類別屬性集合中的某個標簽類別屬性，W(Y_i)表示Y_i在多標簽類別屬性集合中的先關性的平均值，數值越大表明此標簽類別屬性在標簽類別屬性集合中擁有更多的相關性標簽類別屬性。則對此標簽類別屬性的分類效果有益的特征屬性對相關性較高的標簽類別屬性同樣具有積極正向的影響作用。

基于以上考慮，結合公式(9)和公式(10)相關性度量可以表示為下面的式子：

$CCorrelation(X_i;Y)=\frac{1}{\left|Y\right|}\underset{Y_j\∈Y}{\Σ}\left(Correlation\right(X_i;Y_j)+W(Y_j\left)\right)---\left(12\right)$

4.特征排序與特征選擇

在此ML_NIFS算法中，計算特征屬性與多標簽類別屬性的相關度，計算特征屬性與特征屬性集的冗余度，將特征屬性與多標簽類別屬性之間的相關度與特征屬性與特征屬性集的冗余度結合起來，即為特征的評價準則，進而通過特征的評價準則將特征進行排序，特征的評價準則如下：

W(X_i)＝CCorrelation(X_i；Y)-Redundancy(X_i；H) (13)

其中，H為已經排序的特征屬性集合，X_i為等待選擇的特征屬性，CCorrelation(X_i；Y)表示特征屬性與多標簽類別屬性集合的相關性,Redundancy(X_i；H)表示特征屬性X_i與已排序的特征屬性集的冗余性

特征選擇是將已經經過特征排序的特征進行選擇的過程，一般情況下在多標簽類別屬性的特征選擇算法中，常用的方法是根據后續的分類算法、特征的評價準則，設定特征選擇的閾值，通過閾值來進行特征選擇。本算法特征從分類能力來看，在已經排好的特征序列中排名處于前面的特征和多標簽類別屬性之間的相關性比較強，特征屬性與特征屬性之間的冗余性比較低，對分類的效果更好。同時考慮特征屬性之間的整體性，應將多個特征屬性整體作為分析對象。由公式(10)可以得到已排序特征屬性集合H特征屬性子集與多標簽類別屬性集的相關性。相關度計算公式如下：

$Correlation(H;Y)=\frac{1}{\left|H\right|}\underset{X_i\∈H}{\Σ}\frac{1}{\left|Y\right|}\underset{Y_j\∈Y}{\Σ}Correlation(X_i;Y_j)---\left(14\right)$

其中，H表示候選特征集合，Y表示多標簽類別屬性，|Y|表示多標簽類別屬性集的標簽數目，|H|表示已排序的特征集中特征屬性的個數。

按照已排序的特征屬性的順序，由公式(13)計算出相關度的平均值：

H_j表示對應得前j個特征屬性；如果Correlation(H_j；Y)大于Correlation_平均(H；Y)并且Correlation(H_j+1；Y)小于Correlation_平均(H；Y)，則這j個特征屬性就是所要得到的特征屬性。

5.嵌入式的動態互信息計算方法

基于互信息的度量標準，首先我們要對特征在樣本數據集中的概率分布情況進行合理的計算，對于樣本數據確定以后，特征在所在樣本數據集的概率也就是唯一的確定下來，但隨著特征的不斷被選擇出來，樣本數據集中的樣本數據將被不斷的識別出來，那么在互信息的計算過程中將會有所變化，如果仍然選擇傳統基于互信息的計算方法將會產生較大的誤差，因此，已識別的樣本數據對未被選擇的特征在計算方面提供了一些“虛假信息”。

對于算法中提出的動態的特征選擇，主要的研究內容是如何識別那些可以通過已選特征識別的樣本數據，并將數據從數據集中剔除，并根據剩余的樣本數據從新計算信息熵，本文選擇在算法運行的過程中嵌入一種分類器來進行樣本的識別，本文選擇嵌入KNN分類器來識別可識別樣本，并將經過KNN分類器識別的樣本數據從樣本數據集中的刪除，在不改變特征與類別相關性的同時，降低了數據集的樣本數據的個數和特征的維數。

2.根據權利要求1所述的一種嵌入式多類別屬性標簽動態特征選擇方法，其特征在于：計算特征屬性與多標簽類別屬性的相關度，計算特征屬性與特征屬性集的冗余度，將特征屬性與多標簽類別屬性之間的相關度與特征屬性與特征屬性集的冗余度結合起來，即為特征的評價準則，進而通過特征的評價準則將特征進行排序，特征的評價準則如下：

W(X_i)＝CCorrelation(X_i；Y)-Redundancy(X_i；H) (16)

特征選擇是將已經經過特征排序的特征進行選擇的過程，一般情況下在多標簽類別屬性的特征選擇算法中，常用的方法是根據后續的分類算法、特征的評價準則，設定特征選擇的閾值，通過閾值來進行特征選擇。本方法特征從分類能力來看，在已經排好的特征序列中排名處于前面的特征和多標簽類別屬性之間的相關性比較強，特征屬性與特征屬性之間的冗余性比較低，對分類的效果更好。同時考慮特征屬性之間的整體性，應將多個特征屬性整體作為分析對象。可以得到已排序特征屬性集合H特征屬性子集與多標簽類別屬性集的相關性。

相關度計算公式如下：

$Correlation(H;Y)=\frac{1}{\left|H\right|}\underset{X_i\∈H}{\Σ}\frac{1}{\left|Y\right|}\underset{Y_j\∈Y}{\Σ}Correlation(X_i;Y_j)---\left(17\right)$

按照已排序的特征屬性的順序，由公式(18)計算出相關度的平均值：

H_j表示對應得前j個特征屬性；如果Correlation(H_j；Y)大于Correlation_平均(H；Y)并且Correlation(H_j+1；Y)小于Correlation_平均(H；Y)，則這j個特征屬性就是所要得到的特征屬性。

改進后的一種嵌入式多類別屬性標簽動態特征選擇方法，通過信息論中互信息的相關理論知識，本發明所敘述的基于互信息的多標簽動態特征選擇算法，在合理的分析了特征屬性與特征屬性之間的相互關系、特征屬性與類別屬性的相互關系、類別屬性之間的相互關系，并通過動態的互信息計算方法進行動態的特征選擇，數據結果通過分類的精度、分類的覆蓋率、分類的排名損失3個評價標準對實驗結果進行分析，表明特征選擇算法的可以獲得比較小特征子集，降低特征維度，是分類的效果越來越好，并且具有較好的穩定性。