王家琪，張莉，2*

（1. 蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006；2. 蘇州大學(xué) 江蘇省計(jì)算機(jī)信息處理技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 蘇州 215006）

0 引言

文本作為當(dāng)今互聯(lián)網(wǎng)時(shí)代信息的主要載體，可以承載各類(lèi)領(lǐng)域的信息，如新聞報(bào)道、商品評(píng)論、博客文章等，對(duì)文本信息的處理在大數(shù)據(jù)分析中占據(jù)重要地位。作為文本處理的一種技術(shù)，文本分類(lèi)在情感分析、輿情分類(lèi)、垃圾郵件檢測(cè)以及各種現(xiàn)實(shí)領(lǐng)域都有著很重要的作用?；跈C(jī)器學(xué)習(xí)方法的文本分類(lèi)通常使用詞袋模型（bag-of-words）來(lái)將文本數(shù)據(jù)轉(zhuǎn)換為特征矩陣的形式［1］，這樣表示的文本數(shù)據(jù)具有很高的維度。為了避免維數(shù)災(zāi)難問(wèn)題并獲得好的分類(lèi)性能，對(duì)之進(jìn)行特征選擇是非常必要的。

特征選擇的主要任務(wù)是從原有特征集中選取在后續(xù)分類(lèi)任務(wù)中表現(xiàn)最好的特征子集，一般分為封裝法（wrapper method）、篩選法（filter method）以及嵌入法（embedded method）三類(lèi)［2］。最早的封裝法于1997 年由Kohavi 等人［3］提出，是一種與分類(lèi)器相結(jié)合的特征選擇方法，以分類(lèi)器的性能作為選擇標(biāo)準(zhǔn)。由于封裝法直接依賴(lài)于分類(lèi)算法來(lái)選擇特征，因此在分類(lèi)任務(wù)中可以有一個(gè)較好的性能。但是，此類(lèi)算法的復(fù)雜度較高，計(jì)算代價(jià)較大。篩選法是目前最為常用的特征選擇方法。篩選法獨(dú)立于分類(lèi)器算法，通過(guò)某種特征評(píng)價(jià)準(zhǔn)則，選擇最佳特征組合。目前常用的篩選法有互信息［4-5］、信息增益［6］、CHI［7］等。嵌入法結(jié)合了封裝法和篩選法的特點(diǎn)，先使用某些機(jī)器學(xué)習(xí)的算法和模型進(jìn)行訓(xùn)練，得到各個(gè)特征的權(quán)值系數(shù)，根據(jù)系數(shù)從大到小選擇特征。以上篩選法只考慮了特征與決策的相關(guān)性，Peng 等人［8］通過(guò)理論分析證明了一種同時(shí)以相關(guān)性與冗余性為準(zhǔn)則的特征選擇思路的可行性及優(yōu)越性，并提出了一種最小冗余-最大相關(guān)（Minimal Redundancy Maximal Relevancy，mRMR）框架以最小化冗余。

文本數(shù)據(jù)有別于普通的數(shù)值數(shù)據(jù)，有著高維度和高稀疏性的特點(diǎn)，并且每一維特征都有著較直觀(guān)的含義?；谔卣髟~頻的特征選擇方法是文本特征選擇所特有的，Uysal 等人［9］提出了對(duì)于詞語(yǔ)特征的四種評(píng)分標(biāo)準(zhǔn)，并基于這些標(biāo)準(zhǔn)提出了基于詞頻的DFS（Distinguishing Feature Selector）算 法。Rehman 等人［10］提出了相對(duì)判別準(zhǔn)則（Relative Discrimination Criterion，RDC），考慮了每個(gè)特征在正類(lèi)與負(fù)類(lèi)的出現(xiàn)頻率，并將其根據(jù)正類(lèi)以及負(fù)類(lèi)的樣本數(shù)進(jìn)行歸一化，體現(xiàn)了特征與類(lèi)別的相關(guān)性。但是RDC 未考慮特征子集的冗余。Labani 等人［11］將RDC 結(jié)合Pearson 相關(guān)系數(shù)，提出了多變量相對(duì)判別準(zhǔn)則（Multivariate Relative Discrimination Criterion，MRDC），同時(shí)考慮特征子集的冗余性以及特征與類(lèi)別之間的相關(guān)性。但是，MRDC 是建立在文檔頻率基礎(chǔ)上的準(zhǔn)則，沒(méi)有考慮文本特征的語(yǔ)義信息。

為了在選擇相關(guān)特征的同時(shí)有效地去除冗余特征，我們提出了去冗余相對(duì)判別準(zhǔn)則（De-redundantly Relative Discrimination Criterion，DRDC）。該準(zhǔn)則的目的是從候選特征子集中選擇一個(gè)特征，該特征和已有特征子集冗余度最小且與類(lèi)別相關(guān)性最大。為了考慮文本特征的語(yǔ)義信息，DRDC 引入了特征的向量表示，保留了單詞的語(yǔ)義和語(yǔ)法信息。基于特征的向量表示，DRDC 計(jì)算候選特征與所選擇特征子集之間的距離，以此來(lái)量化候選特征與特征子集的冗余度。此外，DRDC 還使用RDC 來(lái)評(píng)價(jià)單個(gè)候選特征與類(lèi)別之間的相關(guān)性。本文在Reuters21589 數(shù)據(jù)集對(duì)所提方法進(jìn)行了實(shí)驗(yàn)，并驗(yàn)證了算法的優(yōu)越性。

本文的行文結(jié)構(gòu)如下：第1 部分，介紹了相關(guān)的工作；第2 部分，描述了所提出的去冗余相對(duì)判別準(zhǔn)則的結(jié)構(gòu)；第3 部分，詳細(xì)介紹了數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置以及結(jié)果。第4 部分，闡明了我們的結(jié)論和未來(lái)的研究方向。

1 相關(guān)工作

1.1 常用文本特征選擇方法

1.1.1 信息增益

在ID3 決策樹(shù)中，信息增益（Information Gain，IG）［6］被用作為特征評(píng)價(jià)準(zhǔn)則。在文本特征選擇中，通過(guò)文檔中特征t的存在與否來(lái)度量為類(lèi)別預(yù)測(cè)而獲得的信息量，特征t的信息增益定義為：

1.1.2 DFS

Uysal 等人［9］根據(jù)對(duì)顯著特征賦高分和不相關(guān)特征賦低分的原則，提出了篩選文本特征選擇的四種評(píng)分標(biāo)準(zhǔn)：

（1）如果一個(gè)特征頻繁出現(xiàn)在某一個(gè)類(lèi)別，并且不出現(xiàn)在其他類(lèi)別，則該特征與該類(lèi)別相關(guān)度高，需對(duì)其賦較高分?jǐn)?shù)；

（2）如果一個(gè)特征很少出現(xiàn)在單個(gè)類(lèi)別，同時(shí)也不常出現(xiàn)其他類(lèi)別，則該特征與類(lèi)別不相關(guān)，需對(duì)其賦較低分?jǐn)?shù)；

（3）如果一個(gè)特征在所有類(lèi)別都經(jīng)常出現(xiàn)，則該特征與類(lèi)別不相關(guān)，應(yīng)對(duì)其賦較低分?jǐn)?shù)；

（4）如果一個(gè)特征只出現(xiàn)在某一些類(lèi)別，則該特征與類(lèi)別相關(guān)，需對(duì)其賦較高分?jǐn)?shù)。

基于這些標(biāo)準(zhǔn)，提出了依賴(lài)詞頻的DFS 特征選擇準(zhǔn)則：

可以證明DFS 滿(mǎn)足以上四種標(biāo)準(zhǔn)。

1.1.3 相對(duì)判別準(zhǔn)則

Rehman 等 人［10］基 于Uysal 等 人 制 定 的 四 條 評(píng)分標(biāo)準(zhǔn)，提出了一種同時(shí)考慮特征計(jì)數(shù)和文檔頻率的相對(duì)判別準(zhǔn)則：

其中，tc表示特征t在一個(gè)樣本中出現(xiàn)的次數(shù)，tprtc是特征t在正類(lèi)中出現(xiàn)tc次的文檔頻率，以及fprtc是特征t在負(fù)類(lèi)中出現(xiàn)tc次的文檔頻率。對(duì)特征t的所有可能的tc取值計(jì)算其相應(yīng)的RDC(tc|t)值，并對(duì)其求曲線(xiàn)下面積（Area Under the Curve，AUC）作為特征t最終的得分：

1.2 詞語(yǔ)的向量表示

在特征工程中，文本一般表示為one-hot 編碼與詞袋模型。One-hot 編碼是將文本表示為二進(jìn)制編碼的形式。隨著語(yǔ)言模型的廣泛使用，文本表示由one-hot 編碼方式逐漸發(fā)展為文本的分布式表示。Word2vec 是 由Google 的Mikolov 等人［12］提出的一種詞嵌入（Word Embedding）的方式，能夠?qū)⒃~語(yǔ)轉(zhuǎn)換成可計(jì)算的向量。Word2vec 使用神經(jīng)網(wǎng)絡(luò)訓(xùn)練語(yǔ)言模型，得到詞語(yǔ)特征的向量表示。相較于one-hot 編碼，Word2vec 極大地減少了向量的維度，同時(shí)也賦予了向量更多詞語(yǔ)上的含義。

GloVe（Global Vectors for Word Representation）是一種基于全局詞頻統(tǒng)計(jì)的詞表征算法［13］。該算法綜合了全局矩陣分解和局部上下文窗口兩種方法，同時(shí)考慮詞的局部信息與全局語(yǔ)料的關(guān)聯(lián)，保留了語(yǔ)義和語(yǔ)法信息。ELMO（Embedding from Language Models）在訓(xùn)練過(guò)程中根據(jù)上下文對(duì)Word Embedding 進(jìn)行動(dòng)態(tài)調(diào)整，調(diào)整后的向量更能表達(dá)出上下文的具體含義，解決了靜態(tài)詞向量未解決的多義詞問(wèn)題［14］。BERT（Bidirectional Encoder Representations from Transformers）是一種預(yù)訓(xùn)練語(yǔ)言模型，使用雙向Transformer［15］對(duì)大量未標(biāo)注文本進(jìn)行訓(xùn)練，訓(xùn)練后需要對(duì)根據(jù)下游具體任務(wù)進(jìn)行微調(diào)［16］。根據(jù)詞語(yǔ)的向量表示來(lái)判斷兩個(gè)詞語(yǔ)間的距離，在機(jī)器翻譯［17］、情感分析［18-20］和問(wèn)答系統(tǒng)［21］等領(lǐng)域都有著廣泛應(yīng)用。

2 去冗余相對(duì)判別準(zhǔn)則

本節(jié)詳細(xì)介紹所提出的去冗余相對(duì)判別準(zhǔn)則DRDC。

2.1 優(yōu)化問(wèn)題

在文本特征選擇中，考慮需要滿(mǎn)足最大相關(guān)最小冗余原則，本文提出的DRDC 可以滿(mǎn)足這樣的原則。在利用DRDC 方法進(jìn)行特征選擇時(shí)，除了考慮特征子集與類(lèi)別的相關(guān)性之外，還考慮了特征子集的冗余性。在相對(duì)判別準(zhǔn)則的基礎(chǔ)上，DRDC 利用下式來(lái)選擇特征：

其中，S?F是特征子集，λ為組合參數(shù)，決定第一項(xiàng)RDC(S) 和第二項(xiàng)在特征選擇中所占比重。RDC(S)代表特征子集與類(lèi)別的相關(guān)性，DIS(S)表示特征子集的冗余性。下面分別討論（5）式中RDC(S)和DIS(S)的計(jì)算，并用S表示目前所選擇的特征子集。

關(guān)于特征子集與類(lèi)別相關(guān)性的衡量，DRDC 推廣了RDC 的衡量方式。RDC 通過(guò)單個(gè)特征的文檔頻率以及其詞頻來(lái)計(jì)算單個(gè)特征與類(lèi)別的相關(guān)性。DRDC 采用簡(jiǎn)單的累加平均方式來(lái)計(jì)算特征子集與類(lèi)別的相關(guān)性。即，對(duì)于特征子集S?F，其與類(lèi)別的相關(guān)性定義為：

其中，RDC(ti)由公式（4）計(jì)算得到。

關(guān)于特征的冗余性，我們認(rèn)為特征與特征越相似，則特征之間的冗余性越高。在衡量特征的相似性時(shí)，不能只依靠特征的頻率。因而，本文引入特征的向量表示，保留了特征的語(yǔ)義和語(yǔ)法信息。DRDC 計(jì)算向量表示之間的相似性，以此來(lái)衡量冗余性。令特征ti的向量表示為vi且tj的向量表示為vj，則特征ti與tj之間的相似性為：

對(duì)于特征子集S?F，其冗余性被定義為：

利用（6）式和（8）式，DRDC 就可以通過(guò)最大化（5）式去尋找具有最大相關(guān)和最小冗余的特征子集。

2.2 優(yōu)化過(guò)程

優(yōu)化問(wèn)題（5）是一個(gè)組合優(yōu)化問(wèn)題，其最優(yōu)解需要遍歷所有可能的組合才能獲得。因此，為節(jié)省計(jì)算資源，可以使用貪心算法來(lái)逐個(gè)選擇特征。假設(shè)在當(dāng)前迭代中，我們已經(jīng)得到了當(dāng)前的最佳子集S。下一步，我們要從候選特征子集F－S中，選擇一個(gè)候選特征加入S，這時(shí)需要考慮候選特征與類(lèi)別的相關(guān)性以及候選特征與特征子集的冗余性。

利用貪心算法，把優(yōu)化問(wèn)題（5）簡(jiǎn)化為

其中，第一項(xiàng)RDC(ti)表示候選特征與類(lèi)別的相關(guān)性，第二項(xiàng)DIS(ti|S)表示候選特征與特征子集的冗余性：

優(yōu)化問(wèn)題（9）中的第一項(xiàng)與優(yōu)化問(wèn)題（5）中的第一項(xiàng)表示方式不完全一致，但是實(shí)際效果是等價(jià)的。 這是因?yàn)槊恳淮蔚际菍ふ易畲蟮腞DC(ti)，因而能保證到目前為止的RDC(S)為最大。對(duì)第二項(xiàng)，也有同樣的結(jié)論。算法1 描述了DRDC 的特征選擇過(guò)程。算法的輸入?yún)?shù)分別為數(shù)據(jù)集、特征的向量表示，選擇特征數(shù)以及組合參數(shù)，算法的返回值是選擇的特征子集。在選擇第一個(gè)特征時(shí)，由于已選擇特征子集為空集，所以不需要判斷冗余，只需要根據(jù)RDC 來(lái)選擇得分最高的特征。

算法1 去冗余相對(duì)判別準(zhǔn)則的特征選擇過(guò)程

3 實(shí)驗(yàn)設(shè)置與結(jié)果分析

3.1 數(shù)據(jù)集與預(yù)處理

本文選取了Reuters21578 的單標(biāo)簽數(shù)據(jù)子集進(jìn)行實(shí)驗(yàn)，并與RDC 以及一些常用文本特征選擇方法進(jìn)行實(shí)驗(yàn)對(duì)比。

Reuters 數(shù)據(jù)集是路透社收集的文本語(yǔ)料，同時(shí)是目前應(yīng)用最廣泛的文本分類(lèi)數(shù)據(jù)集。原始數(shù)據(jù)集類(lèi)別較多，文檔的類(lèi)別分布較為不平衡，并且有部分多標(biāo)簽數(shù)據(jù)，因此本文使用Cardoso-Cachopo①https://ana.cachopo.org/datasets－for－single－label－text－categorization篩選處理的數(shù)據(jù)集［22］。該數(shù)據(jù)集使用了Mod Apté劃分［1］，劃分出了訓(xùn)練集與測(cè)試集，并篩選出單標(biāo)簽的數(shù)據(jù)，生成了R10 子集。在R10 數(shù)據(jù)子集中刪除了訓(xùn)練樣本或者測(cè)試樣本個(gè)數(shù)為0 的類(lèi)別，最終得到了數(shù)據(jù)子集R8。表1 為R8 數(shù)據(jù)集中樣本的分布。

表1 R8樣本分布Table 1 Distribution of R8 samples

由于文本數(shù)據(jù)中特征維度過(guò)大，需要對(duì)文本數(shù)據(jù)進(jìn)行預(yù)處理。首先刪除字符長(zhǎng)度小于3 的單詞以及停用詞，同時(shí)考慮頻率過(guò)高以及過(guò)低的詞語(yǔ)對(duì)分類(lèi)的貢獻(xiàn)都很小，需要選取合適頻率區(qū)域的特征［23］。在本文實(shí)驗(yàn)中選擇保留文檔頻率大于3 的特征，最終保留6 827 個(gè)特征。本文使用詞袋模型將文本數(shù)據(jù)表示為特征矩陣的形式，同時(shí)使用通用的GloVe①http://nlp.stanford.edu/data/glove.840B.300d.zip文件用于表示文本特征，將預(yù)處理后的特征轉(zhuǎn)換為向量表示。

3.2 分類(lèi)器及評(píng)估指標(biāo)

本文對(duì)特征選擇后的數(shù)據(jù)分別使用支持向量機(jī)與K 近鄰算法（KNN）進(jìn)行分類(lèi)，均由Python 中的sklearn 庫(kù)實(shí)現(xiàn)。利用分類(lèi)數(shù)據(jù)準(zhǔn)確度（Accuracy）對(duì)分類(lèi)結(jié)果進(jìn)行評(píng)估［24］，準(zhǔn)確度的計(jì)算方法如下：

其中，TP為預(yù)測(cè)正確的正類(lèi)樣本數(shù)，TN為預(yù)測(cè)正確的負(fù)類(lèi)樣本數(shù)，n為樣本總數(shù)。表2 給出的分類(lèi)混淆矩陣描述了以上數(shù)據(jù)含義。

表2 分類(lèi)混淆矩陣Table 2 Confusion matrix for classification

在多類(lèi)別分類(lèi)過(guò)程中，分別對(duì)每一種類(lèi)別進(jìn)行預(yù)測(cè)結(jié)果的統(tǒng)計(jì)，類(lèi)別ci的準(zhǔn)確度記為acci。本文所用的多分類(lèi)的度量指標(biāo)為：

其中，m為類(lèi)別總數(shù)。

3.3 實(shí)驗(yàn)結(jié)果及分析

為證明本文所提出的去冗余相對(duì)判別準(zhǔn)則的有效性，將本文所提方法與IG、DFS、RDC 以及MRDC 進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)對(duì)R8 進(jìn)行特征選擇，選 擇 的 特 征 數(shù) 分 別 為10，20，50，100，200，500，1 000，1 500，得到特征選擇后的數(shù)據(jù)，使用支持向量機(jī)和K 近鄰算法進(jìn)行分類(lèi)，并使用準(zhǔn)確度對(duì)分類(lèi)結(jié)果進(jìn)行評(píng)估。表3 和表4 分別為使用支持向量機(jī)和K 近鄰算法作為分類(lèi)器的實(shí)驗(yàn)結(jié)果對(duì)比。

表3 支持向量機(jī)的分類(lèi)準(zhǔn)確度Table 3 Accuracy using SVM

表4 K近鄰算法的分類(lèi)準(zhǔn)確度Table 4 Accuracy using KNN

通過(guò)對(duì)比表3 和表4 的數(shù)據(jù)可以看出，DRDC特征選擇方法相較于RDC、MRDC、DFS 和IG 在準(zhǔn)確度上有一定提升。為觀(guān)察DRDC 的去冗余作用，提取出了在特征數(shù)為100 的情況下，被RDC 選擇而未被DRDC 選擇的特征。其中，RDC 選擇了特征詞money 與cash，二者在含義上較為接近，而DRDC 只選擇了特征money，在一定程度上避免了一些冗余。不過(guò)由于在特征選擇過(guò)程中相關(guān)性與冗余性均占一定比重，因此在特征選擇初期更傾向于選擇更為相關(guān)的特征。

為了進(jìn)一步對(duì)比RDC 和DRDC 的特征選擇效果，選取特征數(shù)為1 500 到3 000 之間的特征選擇數(shù)據(jù)。兩種特征選擇方法在不同分類(lèi)器下的分類(lèi)準(zhǔn)確度對(duì)比結(jié)果分別如圖1 和圖2 所示。由圖1 和圖2可以看出，在特征維度較高的情況下，DRDC 的特征選擇效果遠(yuǎn)好于RDC。在特征維度較大的情況下，以相關(guān)性為選擇標(biāo)準(zhǔn)的RDC 方法僅僅傾向于頻次分布不均的特征，未考慮與已選擇特征子集之間的關(guān)系，容易忽略特征子集間的冗余性。而在特征維度增加的情況下無(wú)可避免地會(huì)出現(xiàn)冗余，本文提出的DRDC 方法有效地解決了這一問(wèn)題。DRDC在使用相對(duì)判別準(zhǔn)則的同時(shí)，引入特征的詞嵌入表示，并根據(jù)詞向量之間的距離來(lái)去除冗余。DRDC在特征選擇過(guò)程中，采用特征攜帶的文本信息來(lái)判斷冗余，盡量避免選擇與已選特征子集距離過(guò)小的特征，從而達(dá)到去冗余的目的。

圖1 兩種特征選擇方法在支持向量機(jī)下的準(zhǔn)確度對(duì)比Fig. 1 Comparison of accuracy of two feature selection methods under SVM

圖2 兩種特征選擇方法在K 近鄰分類(lèi)器下的準(zhǔn)確度對(duì)比Fig. 2 Comparison of accuracy of two feature selection methods under KNN

4 結(jié)論

本文在相對(duì)判別準(zhǔn)則的方法上引入文本分布式表示，將文本特征表征為可計(jì)算向量來(lái)去除冗余。在文本多分類(lèi)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，并與一些常用文本特征選擇算法比較，在分類(lèi)準(zhǔn)確度上有一定提高。通過(guò)對(duì)比未去冗余的相對(duì)判別準(zhǔn)則，本文所提方法在選擇特征數(shù)目較大的情況下優(yōu)勢(shì)更為明顯，表明本文方法在選擇特定特征數(shù)的情況下，可以選擇更多相關(guān)的特征，達(dá)到了去冗余的目的。