基于卡方統(tǒng)計(jì)檢驗(yàn)法對文本特征選擇的技術(shù)實(shí)現(xiàn)

摘要：該文主要探討如何從技術(shù)上實(shí)現(xiàn)基于卡方統(tǒng)計(jì)檢驗(yàn)的文本特征選擇，文中提出采用開源的Lucene索引框架對文本分類語料庫進(jìn)行索引，設(shè)計(jì)了在特征值計(jì)算的過程中如何借助語料庫索引快速獲取卡方統(tǒng)計(jì)檢驗(yàn)的相關(guān)參數(shù)，并使用java多線程技術(shù)從整體上優(yōu)化每個(gè)分類下文本特征選擇的計(jì)算效率。

關(guān)鍵詞：特征選擇；卡方統(tǒng)計(jì)；文本分類；JAVA實(shí)現(xiàn)

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）30-7103-03

1 文本特征選擇的必要性

為了能夠有效地對大量文本信息進(jìn)行自動(dòng)分類，先要將文本信息模型化表示，典型的文本建模方法就是向量空間模型（VSM），該模型將文本信息抽象表示為若干相互獨(dú)立的詞匯所構(gòu)成的向量空間，向量空間中每個(gè)分量值使用TF*IDF來度量。其中TF是指詞匯頻率，TF=Nw/N，N表示文本的總詞匯數(shù)，Nw表示詞W在文本中出現(xiàn)的次數(shù)，TF的值越大，詞W與文本的相關(guān)性就越強(qiáng)；IDF是逆文檔頻率，IDF=log（D/Dw），Dw表示包含詞W的文檔數(shù)，D表示語料庫的總文檔數(shù)目，IDF值越大，該詞與文檔的相關(guān)性就越低。假設(shè)有兩個(gè)文本doc1和doc2，那么它們在共同詞匯集合所構(gòu)成的向量空間中具有不同的向量，這兩個(gè)文本的相關(guān)性可以使用兩個(gè)向量的夾角余弦值來表示，夾角余弦值越大說明這兩個(gè)本文越相關(guān)。

由于網(wǎng)頁文本的詞匯相當(dāng)龐雜，包含大量的口語、廣告等噪聲信息，造成文本向量空間的維數(shù)較為龐大，降低了分本分類的效率。因此有必要降低向量空間的維度，剔除噪聲詞匯，保留與當(dāng)前主題相關(guān)的詞匯來構(gòu)成向量空間模型。文本特征選擇就是要在構(gòu)建文本的特征向量時(shí)從文本的詞匯集中選取與主題相關(guān)的詞匯，盡可能地剔除與主題無關(guān)的詞匯，從而提高文本分類的效率與準(zhǔn)確率。

2 文本特征選擇的主要方法

文本特征選擇的方法主要包括信息增益法（IG，Information Gain）、互信息（MI，Mutual Information）、卡方統(tǒng)計(jì)檢驗(yàn)法（CHI，Chi-square Statistic）等，文獻(xiàn)[2]和[4]對這幾種方法在中文網(wǎng)頁的分類效果中進(jìn)行了綜合比較，認(rèn)為CHI、IG的性能要明顯由于MI。

信息增益法（IG）是通過衡量某個(gè)詞匯在出現(xiàn)和不出現(xiàn)兩種情況下對整個(gè)分類系統(tǒng)信息熵的影響程度，影響程度大的詞匯與分類系統(tǒng)的相關(guān)性較大，應(yīng)給予保留；但是信息增益法只能考察特征詞匯對整個(gè)系統(tǒng)的貢獻(xiàn)，不能具體到某個(gè)類別上，這使得該方法只適合做全局的特征選擇。

卡方統(tǒng)計(jì)檢驗(yàn)方法（CHI）是基于數(shù)理統(tǒng)計(jì)中的聯(lián)列表檢驗(yàn)理論判斷某個(gè)詞匯與特定文本類別的相關(guān)性。它先假設(shè)特征詞匯與特定類別是獨(dú)立的，通過計(jì)算觀察值與理論值之間的偏差程度來決定原假設(shè)是否成立。在給定詞匯t和分類c的條件下，CHI的公式簡化如下：

[χ2（t，c=（AD-BC）2（A+B）（C+D）]

其中，A表示包含詞匯t且屬于分類c的文檔數(shù)目，B表示包含詞匯t但不屬于分類c的文檔數(shù)目，C表示不包含詞匯t且屬于分類c的文檔數(shù)目，D表示不包含詞匯t且不屬于分類c的文檔數(shù)目。

從CHI的計(jì)算公式可以看出它能夠檢驗(yàn)特定詞匯與特定類別之間的相關(guān)度，但是CHI方法忽略了詞匯出現(xiàn)的頻率，這使得它對低頻詞有所偏袒，比如分類c的所有文檔都包含了詞A，但是在每篇文檔中詞A只出現(xiàn)1次，而分類c的99%文檔都包含了詞B，并且在每篇文檔中詞B都出現(xiàn)了10次以上。相對于詞A，詞B與分類c相關(guān)性更大，但是由于CHI的計(jì)算公式忽略了詞匯出現(xiàn)的頻率，導(dǎo)致詞匯A比詞匯B具有更大相關(guān)性。

3 文本特征選擇的技術(shù)實(shí)現(xiàn)

3.1 文本語料庫及索引庫

為了進(jìn)行文本特征的選擇，要預(yù)先準(zhǔn)備好中文文本語料庫。搜狗實(shí)驗(yàn)室提供的中文分類語料庫包含環(huán)境、IT、交通、教育、經(jīng)濟(jì)、軍事、體育、醫(yī)藥、藝術(shù)、政治共十個(gè)分類，每個(gè)分類下包含若干相關(guān)文本，共計(jì)八萬篇。該文以搜狗實(shí)驗(yàn)室提供的中文語料庫作為文本特征提取的資料庫，基于卡方統(tǒng)計(jì)檢驗(yàn)方法（CHI）來計(jì)算語料庫中每個(gè)類別所對應(yīng)的特征詞列表，這些不同分類的特征詞列表將作為后續(xù)文本分類的特征向量。

CHI公式的關(guān)鍵是要針對不同的詞匯t和類別c分別計(jì)算出A、B、C、D的值。這里的詞匯需要通過分詞技術(shù)從中文文本中進(jìn)行提取。該文采用了IKAnalyzer開源分詞器，該分詞器使用了正向迭代最細(xì)粒度切分算法，具有60萬字/秒的高速處理能力。文本經(jīng)過分詞器分割后將形成大量的詞匯，直接使用這些詞匯作為CHI的計(jì)算對象將極大的降低計(jì)算效率。為此應(yīng)定義一個(gè)中文停用詞集合，它包含了常用的中文語氣詞、助詞、虛詞等與文本內(nèi)容無關(guān)的詞匯，使用中文停用詞集合對分詞器分割后的詞匯進(jìn)行過濾，同時(shí)過濾掉所有的單字詞匯。

本文采用Lucene工具對文本語料庫中的所有中文文本預(yù)先進(jìn)行索引，Lucene是apache軟件基金會提供的開源全文索引工具包，對文本語料庫建立索引后，借助Lucene提供的API接口可以極大的加快查詢諸如“語料庫中包含某詞匯的文檔數(shù)”的速度。建立的索引記錄結(jié)構(gòu)如下表所示，其中filename表示文本路徑名，該字段被作為一個(gè)整體保留在索引庫中，但不參與索引；content表示該文本的具體內(nèi)容，該字段不僅需要保留文本內(nèi)容，還需要對其進(jìn)行分詞并在索引庫中保存分詞后的詞匯向量，classname表示該文本所屬的分類，該字段作為整體保留在索引庫中參與索引但是不對它進(jìn)行分詞。

表1 文本語料庫的索引結(jié)構(gòu)

[字段名＼&字段值＼&存儲狀態(tài)＼&索引狀態(tài)＼&詞匯向量＼&filename＼&文本的具體路徑＼&Field.Store.YES＼&Field.Index.NO＼&＼&content＼&文本的具體內(nèi)容＼&Field.Store.YES＼&Field.Index.ANALYZED＼&Field.TermVector.YES＼&classname＼&文本所屬的分類名＼&Field.Store.YES＼&Field.Index.NOT_ANALYZED＼&＼&]endprint

3.2 卡方統(tǒng)計(jì)中四個(gè)參數(shù)的計(jì)算

本文使用Java語言來實(shí)現(xiàn)卡方統(tǒng)計(jì)檢驗(yàn)的計(jì)算公式，建立了DataManager類和IndexManager類。DataManager類根據(jù)指定的語料庫存放路徑獲取語料庫的主要狀態(tài)信息，如語料庫的文檔總數(shù)、類別總數(shù)、某個(gè)類別下的文檔數(shù)。IndexManager類根據(jù)指定的語料庫來生成對應(yīng)的索引庫，索引庫的結(jié)構(gòu)如表1所示，并且提供一個(gè)getIndexReader（）方法返回Lucene框架中的IndexReader對象。使用IndexReader對象的方法可以快速的讀取卡方統(tǒng)計(jì)檢驗(yàn)中所需的相關(guān)值。

計(jì)算“整個(gè)語料庫中包含詞w的文檔數(shù)”，記作Nw ，可以直接使用IndexReader的docFreq（new term（“content”，word））方法來獲?。挥?jì)算“類別c中包含單詞w的文檔數(shù)”即卡方統(tǒng)計(jì)中的參數(shù)A，可以采用如圖1所示的算法，IndexReader的termDocs方法可以返回包含詞w的文檔集合，該集合的每一項(xiàng)都包含一個(gè)文檔編號docId，通過IndexrReader的document（int docId）方法可以獲取當(dāng)前項(xiàng)所對應(yīng)的文檔。那么卡方統(tǒng)計(jì)檢驗(yàn)中的參數(shù)B=Nw-A。 計(jì)算“類別c中不包含單詞w的文檔總數(shù)”，即卡方統(tǒng)計(jì)中的參數(shù)C，可直接使用類別c的總文檔數(shù)NC-A，這里NC在給定語料庫路徑情況下可以很方便的獲得。在計(jì)算完參數(shù)A、B、C的值之后，D=N-A-B-C，其中N代表整個(gè)語料庫的文檔數(shù)，在給定的語料庫中N的值是個(gè)常量。至此卡方統(tǒng)計(jì)檢驗(yàn)的參數(shù)已經(jīng)計(jì)算完畢，可以看出這里的關(guān)鍵是借助事先準(zhǔn)備好的索引庫快速計(jì)算出Nw和A的值。

3.3 文本特征選擇計(jì)算的優(yōu)化

當(dāng)文本的詞匯表較大時(shí)采用上述算法其效率依然不能令人滿意。java的多線程技術(shù)可使上述算法獲得更好的效率。首先使用Lucene來獲取類別c下的詞匯表并暫存于LinkedList集合中，這里的詞匯表應(yīng)該是過濾掉了停用詞和單字詞后的詞匯集合。創(chuàng)建一個(gè)實(shí)現(xiàn)了Runnable接口的CHIWorker類，該類具有實(shí)例屬性ThreadPool（線程池），調(diào)用CHIWorker類的start（）方法時(shí)將對線程池進(jìn)行初始化。該類的run（）方法作為線程體被多個(gè)線程調(diào)用。run（）方法也是CHIWorker類的核心，決定了文本特征計(jì)算的效率，具體算法如圖所示。CHIWorker類擁有一個(gè)名為resultMap的HashMap，用于存儲詞匯及其CHI值存儲。采用java的多線程技術(shù)將類別c下所有詞匯的卡方統(tǒng)計(jì)檢驗(yàn)值計(jì)算完畢，并存儲在resultMap中，主程序?qū)⒃诙嗑€程運(yùn)行完畢后獲取到resultMap中存儲的值。

圖2 CHIWorker類的run方法

在獲取了存儲于resultMap中的CHI值之后可以進(jìn)一步按照CHI值的大小進(jìn)行排序，為CHI值確定一個(gè)最低閥值，保留大于閥值的詞匯作為類別c的特征詞匯集合，記為wordList1。借鑒文獻(xiàn)[3]中提出的CHI改進(jìn)算法，在獲取了詞匯集合wordList1之后，再進(jìn)一步計(jì)算每個(gè)詞的頻度、集中度和分散度，其中頻度是用語料索引庫中詞匯w出現(xiàn)的次數(shù)來表示；集中度=A/（A+C）；分散度=A/（A+B） 。對wordList1中每個(gè)詞匯按照頻度、集中度和分散度的乘積進(jìn)行計(jì)算并降序排序，通過設(shè)定一個(gè)閥值來選區(qū)若干詞匯作為類別c的最終特征詞匯集合。至此，完成了對類別c的文本特征選擇，對其他類別也采用相同的計(jì)算過程，即可得到每個(gè)類別下的特征詞匯向量。

4 結(jié)束語

本文分析了文本特征選擇的重要性并比較了文本特征選擇的主要方法，深入探討了卡方統(tǒng)計(jì)檢驗(yàn)法（CHI）的特點(diǎn)，提出了采用Lucene索引工具和Java多線程技術(shù)來優(yōu)化CHI計(jì)算方法的思路。

參考文獻(xiàn)：

[1] 王光.集合CHI與IG的特征選擇方法[J].計(jì)算機(jī)應(yīng)用，2012（7）.

[2] 單松巍.幾種典型特征選取方法在中文網(wǎng)頁分類上的效果比較[J].計(jì)算機(jī)工程與應(yīng)用，2003（22）.

[3] 熊忠陽.基于卡方統(tǒng)計(jì)的文本分類特征選擇方法的研究[J].計(jì)算機(jī)應(yīng)用，2008（2）.

[4] 崔愛國.文本分類中特征提取方法的比較與分析[J].電腦知識與技術(shù)，2009（7）.

3.2 卡方統(tǒng)計(jì)中四個(gè)參數(shù)的計(jì)算

本文使用Java語言來實(shí)現(xiàn)卡方統(tǒng)計(jì)檢驗(yàn)的計(jì)算公式，建立了DataManager類和IndexManager類。DataManager類根據(jù)指定的語料庫存放路徑獲取語料庫的主要狀態(tài)信息，如語料庫的文檔總數(shù)、類別總數(shù)、某個(gè)類別下的文檔數(shù)。IndexManager類根據(jù)指定的語料庫來生成對應(yīng)的索引庫，索引庫的結(jié)構(gòu)如表1所示，并且提供一個(gè)getIndexReader（）方法返回Lucene框架中的IndexReader對象。使用IndexReader對象的方法可以快速的讀取卡方統(tǒng)計(jì)檢驗(yàn)中所需的相關(guān)值。

計(jì)算“整個(gè)語料庫中包含詞w的文檔數(shù)”，記作Nw ，可以直接使用IndexReader的docFreq（new term（“content”，word））方法來獲??；計(jì)算“類別c中包含單詞w的文檔數(shù)”即卡方統(tǒng)計(jì)中的參數(shù)A，可以采用如圖1所示的算法，IndexReader的termDocs方法可以返回包含詞w的文檔集合，該集合的每一項(xiàng)都包含一個(gè)文檔編號docId，通過IndexrReader的document（int docId）方法可以獲取當(dāng)前項(xiàng)所對應(yīng)的文檔。那么卡方統(tǒng)計(jì)檢驗(yàn)中的參數(shù)B=Nw-A。 計(jì)算“類別c中不包含單詞w的文檔總數(shù)”，即卡方統(tǒng)計(jì)中的參數(shù)C，可直接使用類別c的總文檔數(shù)NC-A，這里NC在給定語料庫路徑情況下可以很方便的獲得。在計(jì)算完參數(shù)A、B、C的值之后，D=N-A-B-C，其中N代表整個(gè)語料庫的文檔數(shù)，在給定的語料庫中N的值是個(gè)常量。至此卡方統(tǒng)計(jì)檢驗(yàn)的參數(shù)已經(jīng)計(jì)算完畢，可以看出這里的關(guān)鍵是借助事先準(zhǔn)備好的索引庫快速計(jì)算出Nw和A的值。

3.3 文本特征選擇計(jì)算的優(yōu)化

當(dāng)文本的詞匯表較大時(shí)采用上述算法其效率依然不能令人滿意。java的多線程技術(shù)可使上述算法獲得更好的效率。首先使用Lucene來獲取類別c下的詞匯表并暫存于LinkedList集合中，這里的詞匯表應(yīng)該是過濾掉了停用詞和單字詞后的詞匯集合。創(chuàng)建一個(gè)實(shí)現(xiàn)了Runnable接口的CHIWorker類，該類具有實(shí)例屬性ThreadPool（線程池），調(diào)用CHIWorker類的start（）方法時(shí)將對線程池進(jìn)行初始化。該類的run（）方法作為線程體被多個(gè)線程調(diào)用。run（）方法也是CHIWorker類的核心，決定了文本特征計(jì)算的效率，具體算法如圖所示。CHIWorker類擁有一個(gè)名為resultMap的HashMap，用于存儲詞匯及其CHI值存儲。采用java的多線程技術(shù)將類別c下所有詞匯的卡方統(tǒng)計(jì)檢驗(yàn)值計(jì)算完畢，并存儲在resultMap中，主程序?qū)⒃诙嗑€程運(yùn)行完畢后獲取到resultMap中存儲的值。

圖2 CHIWorker類的run方法

在獲取了存儲于resultMap中的CHI值之后可以進(jìn)一步按照CHI值的大小進(jìn)行排序，為CHI值確定一個(gè)最低閥值，保留大于閥值的詞匯作為類別c的特征詞匯集合，記為wordList1。借鑒文獻(xiàn)[3]中提出的CHI改進(jìn)算法，在獲取了詞匯集合wordList1之后，再進(jìn)一步計(jì)算每個(gè)詞的頻度、集中度和分散度，其中頻度是用語料索引庫中詞匯w出現(xiàn)的次數(shù)來表示；集中度=A/（A+C）；分散度=A/（A+B） 。對wordList1中每個(gè)詞匯按照頻度、集中度和分散度的乘積進(jìn)行計(jì)算并降序排序，通過設(shè)定一個(gè)閥值來選區(qū)若干詞匯作為類別c的最終特征詞匯集合。至此，完成了對類別c的文本特征選擇，對其他類別也采用相同的計(jì)算過程，即可得到每個(gè)類別下的特征詞匯向量。

4 結(jié)束語

本文分析了文本特征選擇的重要性并比較了文本特征選擇的主要方法，深入探討了卡方統(tǒng)計(jì)檢驗(yàn)法（CHI）的特點(diǎn)，提出了采用Lucene索引工具和Java多線程技術(shù)來優(yōu)化CHI計(jì)算方法的思路。

參考文獻(xiàn)：

[1] 王光.集合CHI與IG的特征選擇方法[J].計(jì)算機(jī)應(yīng)用，2012（7）.

[2] 單松巍.幾種典型特征選取方法在中文網(wǎng)頁分類上的效果比較[J].計(jì)算機(jī)工程與應(yīng)用，2003（22）.

[3] 熊忠陽.基于卡方統(tǒng)計(jì)的文本分類特征選擇方法的研究[J].計(jì)算機(jī)應(yīng)用，2008（2）.

[4] 崔愛國.文本分類中特征提取方法的比較與分析[J].電腦知識與技術(shù)，2009（7）.

3.2 卡方統(tǒng)計(jì)中四個(gè)參數(shù)的計(jì)算

本文使用Java語言來實(shí)現(xiàn)卡方統(tǒng)計(jì)檢驗(yàn)的計(jì)算公式，建立了DataManager類和IndexManager類。DataManager類根據(jù)指定的語料庫存放路徑獲取語料庫的主要狀態(tài)信息，如語料庫的文檔總數(shù)、類別總數(shù)、某個(gè)類別下的文檔數(shù)。IndexManager類根據(jù)指定的語料庫來生成對應(yīng)的索引庫，索引庫的結(jié)構(gòu)如表1所示，并且提供一個(gè)getIndexReader（）方法返回Lucene框架中的IndexReader對象。使用IndexReader對象的方法可以快速的讀取卡方統(tǒng)計(jì)檢驗(yàn)中所需的相關(guān)值。

計(jì)算“整個(gè)語料庫中包含詞w的文檔數(shù)”，記作Nw ，可以直接使用IndexReader的docFreq（new term（“content”，word））方法來獲??；計(jì)算“類別c中包含單詞w的文檔數(shù)”即卡方統(tǒng)計(jì)中的參數(shù)A，可以采用如圖1所示的算法，IndexReader的termDocs方法可以返回包含詞w的文檔集合，該集合的每一項(xiàng)都包含一個(gè)文檔編號docId，通過IndexrReader的document（int docId）方法可以獲取當(dāng)前項(xiàng)所對應(yīng)的文檔。那么卡方統(tǒng)計(jì)檢驗(yàn)中的參數(shù)B=Nw-A。 計(jì)算“類別c中不包含單詞w的文檔總數(shù)”，即卡方統(tǒng)計(jì)中的參數(shù)C，可直接使用類別c的總文檔數(shù)NC-A，這里NC在給定語料庫路徑情況下可以很方便的獲得。在計(jì)算完參數(shù)A、B、C的值之后，D=N-A-B-C，其中N代表整個(gè)語料庫的文檔數(shù)，在給定的語料庫中N的值是個(gè)常量。至此卡方統(tǒng)計(jì)檢驗(yàn)的參數(shù)已經(jīng)計(jì)算完畢，可以看出這里的關(guān)鍵是借助事先準(zhǔn)備好的索引庫快速計(jì)算出Nw和A的值。

3.3 文本特征選擇計(jì)算的優(yōu)化

當(dāng)文本的詞匯表較大時(shí)采用上述算法其效率依然不能令人滿意。java的多線程技術(shù)可使上述算法獲得更好的效率。首先使用Lucene來獲取類別c下的詞匯表并暫存于LinkedList集合中，這里的詞匯表應(yīng)該是過濾掉了停用詞和單字詞后的詞匯集合。創(chuàng)建一個(gè)實(shí)現(xiàn)了Runnable接口的CHIWorker類，該類具有實(shí)例屬性ThreadPool（線程池），調(diào)用CHIWorker類的start（）方法時(shí)將對線程池進(jìn)行初始化。該類的run（）方法作為線程體被多個(gè)線程調(diào)用。run（）方法也是CHIWorker類的核心，決定了文本特征計(jì)算的效率，具體算法如圖所示。CHIWorker類擁有一個(gè)名為resultMap的HashMap，用于存儲詞匯及其CHI值存儲。采用java的多線程技術(shù)將類別c下所有詞匯的卡方統(tǒng)計(jì)檢驗(yàn)值計(jì)算完畢，并存儲在resultMap中，主程序?qū)⒃诙嗑€程運(yùn)行完畢后獲取到resultMap中存儲的值。

圖2 CHIWorker類的run方法

在獲取了存儲于resultMap中的CHI值之后可以進(jìn)一步按照CHI值的大小進(jìn)行排序，為CHI值確定一個(gè)最低閥值，保留大于閥值的詞匯作為類別c的特征詞匯集合，記為wordList1。借鑒文獻(xiàn)[3]中提出的CHI改進(jìn)算法，在獲取了詞匯集合wordList1之后，再進(jìn)一步計(jì)算每個(gè)詞的頻度、集中度和分散度，其中頻度是用語料索引庫中詞匯w出現(xiàn)的次數(shù)來表示；集中度=A/（A+C）；分散度=A/（A+B） 。對wordList1中每個(gè)詞匯按照頻度、集中度和分散度的乘積進(jìn)行計(jì)算并降序排序，通過設(shè)定一個(gè)閥值來選區(qū)若干詞匯作為類別c的最終特征詞匯集合。至此，完成了對類別c的文本特征選擇，對其他類別也采用相同的計(jì)算過程，即可得到每個(gè)類別下的特征詞匯向量。

4 結(jié)束語

本文分析了文本特征選擇的重要性并比較了文本特征選擇的主要方法，深入探討了卡方統(tǒng)計(jì)檢驗(yàn)法（CHI）的特點(diǎn)，提出了采用Lucene索引工具和Java多線程技術(shù)來優(yōu)化CHI計(jì)算方法的思路。

參考文獻(xiàn)：

[1] 王光.集合CHI與IG的特征選擇方法[J].計(jì)算機(jī)應(yīng)用，2012（7）.

[2] 單松巍.幾種典型特征選取方法在中文網(wǎng)頁分類上的效果比較[J].計(jì)算機(jī)工程與應(yīng)用，2003（22）.

[3] 熊忠陽.基于卡方統(tǒng)計(jì)的文本分類特征選擇方法的研究[J].計(jì)算機(jī)應(yīng)用，2008（2）.

[4] 崔愛國.文本分類中特征提取方法的比較與分析[J].電腦知識與技術(shù)，2009（7）.