[發明專利]一種特征評價選擇方法

在審

• 申請號: 201210475431.4
• 申請日: 2012-11-21
• 公開（公告）號: CN103838730A
• 公開（公告）日: 2014-06-04
• 發明（設計）人: 牟向偉
• 申請（專利權）人: 大連靈動科技發展有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 大連東方專利代理有限責任公司 21212
• 代理人: 曲永祚

1.一種特征評價選擇方法，其特征在于：包括以下步驟：

A、信息增益

在信息檢索領域，研究者使用TF，DF，TFIDF來確定特征的相關性；本論文把TFIDF定義為：

TE-IDF=TF*log(NDF)]]>

其中N是語料庫中所有文章的數量；可見特征t在文章d中的TF值越大，而在語料庫所有文章中出現的次數DF越少，TFIDF的值就會越大，則可以為特征t具有很好的區分能力適合用來計算文本相似度；

信息論中的方法考慮了某一特征在不同類別文章中的分布情況；使用最多的方法是信息增益，它包括了特征在某一類別中出現和不出現這兩種情況；本文采用如下的定義式：

IG(t,c)=P(t)P(c|t)log(P(c|t)P(c))+P(t‾)P(c|t‾)log(P(c|t‾)P(c))]]>

其中：P(t)表示文章d包含特征t的概率；P(c|t)表示包含特征t的文章d屬于類別c的概率；表示文章d不包含特征t的概率；表示不包含特征t的文章d屬于類別c的概率；通常而言，IG(t,c)中各個事件的概率可以用其相應的頻率來估算；，條件概率P(c|t)=P(t|c)/P(t)；特征t與類別c的信息增益越大，說明特征t中包含的與類別c有關的鑒別信息就越多，當然應該選擇信息增益值大的特征；

期望交叉熵只包含了特征出現在某一類別中的情況；其數學表達式如下：

CET(t,c)=P(t)P(c|t)log(P(c|t)P(c))]]>

χ²統計量方法的數學表達式如下：

S-χ2(t,c)=P(t,c)·P(t‾,c‾)-P(t,c‾)·P(t‾,c)]]>

這個概念來自聯表檢驗，它可以用來衡量特征t和類別c之間的統計相關性；在此基礎上，提出了一種更為簡化的χ²統計量，被稱為S-χ²；IG的性能要優于CET和S-χ²；

B、基于雜質能級的特征評價選擇

這一類的方法來自于機器學習的領域，它們原本都是用來評價機器學習算法生成的規則質量的；為了能夠將其應用到文本相似度計算的屬性評價和選擇上，本發明要對其進行適當的修改；定義一個組合(t，c)，規則是：如果文章d包含特征t，那么文章d就屬于類別c，本文用t→c來描述；這樣以來，評價特征t在類別c中的重要程度問題就轉換為衡量規則t?→c質量的問題；為了便于進行討論，本文引入如下的符號：

A_t，c表示屬于類別c且包含特征t的文章數量

B_t，c表示不屬于類別c且包含特征t的文章數量

C_t，c表示屬于類別c且不包含特征t的文章數量

D_t，c表示不屬于類別c且不包含特征t的文章數量

通常而言，規則質量的衡量標準是規則在應用過程中的成功率和失敗率；本發明使用最常見的拉普拉斯修正方法修改原始的成功率計算方法，把訓練成功的數量加1除以訓練實例的總數加2所得的商作為新的成功率；計算方法如下：

L(t→c)=At,c+1At,c+Bt,c+2]]>

這個方法只考慮了出現特征t的文章；

其它的方法還有Johannes等人給出的一種差分法的簡化計算方法如下所述：

D(t→c)=A_t，c-B_t,c

它把包含特征t屬于類別的文章數量B_t，c作為包含特征t屬于類別c的文章數量A_t，c的懲罰而減去，目的是為了在A_t，c和B_t，c之間建立一種平衡；

提出了利用雜質能級的衡量方法；該方法不僅考慮到了屬于類別c且包含特征t的文章，而且還考慮了文章在所有類別的分布情況；為了討論文章的分布問題，本文引入無條件規則的概念，符號為→c，它表示屬于類別c的任意一篇文章；這個規則作為其它規則的一個參考；本文要利用規則使用的次數n和規則成功的次數m來計算規則t→c的雜質能級；已知規則t→c的成功率的前提下，可以先求出規則的置信區間：

CIl,u=2·n·p+Zα/22+Zα/2Zα/2+4·n·p-4·n·p22(n+Zα/22)]]>

其中Z是置信水平為1-α的標準正態分布的Z值；p是規則使用的成功率，如下所述：

p=mn=At,cAt,c+Bt,c]]>

因此，雜質能級就可以定義成規則t→c的置信區間和無條件規則→c的重合程度，如下公式所述：

IL(t→c)=CIu(→c)-CIl(t→c)CIu(t→c)-CIl(t→c)]]>

如果雜質能級的值小于零，則說明規則t→c的成功率要高于無條件規則→c，因此要選擇雜質能級小的特征；上面的方法僅僅考慮了包含特征t的文章；如果再考慮屬于類別c但是不包含特征t的那些文章的話，應該會有助于特征的評價和選擇；本文就把這些信息添加進來，可以得到如下計算方法：

Le(t→c)=At,c+1At,c+Bt,c+Ct,c+2]]>

D_e(t→c)=A_t,c-B_t,c-C_t,c

此時規則使用的成功率用公式可以描述如下：

Pe=At,cAt,c+Bt,c+Ct,c]]>

相應的置信區間如下：

CIel,u=2·n·pe+Zα/22+Zα/2Zα/2+4·n·pe-4·n·pe22(n+Zα/22)]]>

就能得到新的雜質能級，如下：

ILe(t→c)=CIeu(→c)-CIel(t→c)CIeu(t→c)-CIel(t→c)]]>

還有一個局部特征集和全局的選擇問題；局部特征集由出現在某一類別文章中的特征組成，而全局特征集是由參與訓練的文章中出現的所有特征組成的；也就是說有多少個類別就會有多少個局部特征集，只會有一個全局特征集；本論文在計算所有詞條評估分數的基礎上，先從每個局部特征集抽取出一定數量的特征作為局部特征子集，再用所有的局部特征子集組合成供計算相似度使用的最終特征集。