基于BIG-WFCHI的微博信息關鍵特征選擇方法①

殷仕剛,安 洋,蔡欣華,屈小娥

1(西安理工大學 信息化管理處,西安 710048)

2(西安理工大學 計算機科學與工程學院,西安 710048)

目前,作為現實社會網絡的延伸,微博平臺已經成為網民表達意見、交流信息的熱門網站平臺.據中國互聯網絡信息中心(CNNIC)第45 次《中國互聯網絡發展狀況統計報告》顯示[1],微博是我國三大社交應用之一.在抗擊新冠肺炎疫情過程中,上億用戶通過微博關注最新疫情、獲取防治服務、參與公益捐助.截至2020年2月4日,微博熱搜榜上疫情相關話題的占比超過60%.顯然,新興媒體已經滲透到我們的生活中,給我們的信息獲取和社會互動帶來了巨大的變化.然而,由于缺乏對內容的即時審查,虛假信息極易產生和迅速傳播,給社會帶來負面影響.因此,準確、有效地預測微博的傳播范圍,對于防止虛假信息傳播具有重要意義.

利用機器學習方法預測微博傳播范圍的前提是提取微博轉發特征.因此,選擇有效的特征是提高預測精度和效率的關鍵步驟,通過選擇有效的特征可以在不損失處理速度和性能的前提下消除不相關和冗余的特征.

通過對文獻[2,3] 實驗結果的分析,發現:1)IG和CHI 方法表現良好,表明高頻詞有利于分類;2)相反,MI 有效性較差的原因在于其固有的低頻詞優勢,這一缺陷導致了預測能力差和學習能力差[4].代六玲等[5]在研究中也發現將單一的方法進行組合應用可以提高特征選擇的準確率,并大幅度縮短分類訓練時間.李玉鑑等[6]將DF 和CHI 相結合不僅保留了CHI 方法能夠考慮特征詞項與類別相關的優點,而且利用文檔頻率DF 值來去除掉低頻詞,降低了CHI 對低頻特征詞的權重,增強了對關鍵特征的識別能力.Qian 等[7]將信息理論與集合論理論相結合,解決了特征選擇中的不完全數據問題,但分類數據與數值數據的共存卻懸而未決問題.Wang 等[8]進一步發現,為了克服CHI 的缺陷,CHI 常常與詞頻等其他因素相結合.Guyon 等[9]也發現IG 受到冗余相關特征的影響.

通過以上分析,發現直接簡單的將DF 和CHI 進行結合很難去除冗余特征.相反,它甚至可以忽略低頻詞的關鍵特征.本文對傳統IG 和CHI 特征選擇方法進行了研究分析,針對IG 算法低頻特征詞對運算結果產生干擾的問題,引入平衡因子進行調節;針對CHI 算法存在的負相關問題,引入詞頻因子來提高算法準確率.在此基礎上,根據微博信息傳播特點,結合改進的IG和CHI 算法,提出了一種基于BIG-WFCHI (Balance Information Gain-Word Frequency CHI-square test)的特征選擇方法.最后,以2017年微博數據和Reddit 社區數據,測試BIG-WFCHI 的性能.實驗結果表明BIGWFCHI 特征選擇方法能夠提高信息分類準確率,且降低了運算時間和成本.

1 BIG-WFCHI 微博信息關鍵特征選擇方法

1.1 信息增益

在信息論中,熵表示信息中包含的平均信息量.對于特征,熵度量它們對分類的有用程度.假設特征t有m個可能值,v={v1|v2|…|vm},pi(i=1,2,…,m)是vi的概率,那么t的信息熵可以定義為:

其中,較低的熵表示更簡單的分布.注意,熵為0 意味著所有的樣本都有相同的值.相比之下,熵越大表明無序分布越多.當特征分布均勻時,在log2m處達到最大熵.

信息增益是根據系統的原始熵與系統具有固定特征的條件熵之差定義的,它描述了特征的信息量.一般來說,一個特征越不確定,它包含的信息就越多.特征t的IG 定義為式(2)[3,10].

其中,p(ci)表示類別ci的出現概率,對于特征t和類別集C={ci,i=1,2,…,n},IG 利用類別ci中t出現(p(t))和不出現的概率來度量其在C上的信息增益,因此,較大的信息增益表示t對C的貢獻較大,這使得IG 方法更有可能選擇信息增益較大的特征到一個類別.

1.2 卡方檢驗

卡方檢驗(CHI-square test)[6]又稱為χ2檢驗,是檢驗特征是否服從某一理論分布或假設分布的假設檢驗之一,屬于自由分布的非參數檢驗.

其基本思想是,首先假設H0是真的,然后基于H0計算χ2來描述觀測值與期望值之間的差距.利用χ2分布和自由度,可以得到當前統計量在H0下的概率p.

卡方檢驗可以用來衡量特征t和類別ci之間的相關性.假設t和ci服從單自由度的χ2分布.其中,N表示數據集的大小;B表示ci中具有特征t的子集的大小;D表示ci中不具有特征t的子集的大小;L表示ci中不具有特征t 的子集的大小,M表示ci中不具有特征t的子集的大小.ci中特征t的χ2值為:

當χ2(t,ci)=0 時,特征t和ci是獨立的,χ2的值越大它們的相關性越強.

對于多類問題,首先計算t和ci的χ2值,然后分別在整個數據集上測試特征t的χ2值.

其中,n表示類別數.式(4)是分類特征的平均χ2值,式(5)是最大值.根據χ2值得到排序后的特征列表,然后根據排序后的列表選擇特征.

1.3 基于BIG-WFCHI 的微博信息關鍵特征選擇算法

信息增益和χ2方法只計算整個數據集中每個特征的頻率,而不考慮特定類別的特征(轉發/不轉發).這兩種方法只關注具有一定特征的微博數量,而不關注特定類別微博的頻率.這夸大了低頻特征的作用,導致分類精度下降[11].

因此,除了使用基于微博數量的統計方法外,還需要考慮所有類別特征的概率分布,本文引入詞頻因子E作為標準度量,它表示出現在一個類別中的特征的總頻率.

設在微博數據集中,屬于類別Ci的微博是d1,d2,…,dn,特征t微博dk(1≤k≤n)中出現的次數為fik(t),特征t在Ci中出現的次數為fi(t).詞頻因子E為特征t在某類Ci中出現的總詞頻,如式(6)所示.

除了上述導致結果不理想的原因外,傳統的信息增益方法更有可能選擇在一個特定類別中出現較少而在其他類別中出現較多的特征,而不是在一個特定類別中出現較多而在其他類別中出現較少的有價值特征.為了解決這個問題,需要設置一個平衡因子,以確保當一個特定類別的無關特征(或受影響較小的特征)發生時,該參數變為負值或非常小的正值,表明該特征具有負相關性或貢獻較小.平均值可以是一個簡單有效的標準來衡量特征對類別的影響.因此,本文引入平衡因子F為:

平衡因子F為分類Ci中包含特征t的微博數與各分類出現特征t的微博平均數的差值,如式(7)所示.其中,d fi(t)為在分類Ci中包含特征t的微博數;為數據中各分類出現特征t的微博平均數,=n為數據集的分類個數.

通過式(2)、式(6)和式(7)得出:

因此,IG 避免忽略特定類別中的特征頻率,并選擇在特定類別中出現較少但在其他類別中出現較多的特征.

從式(3)可以看出,D和L變大,而B和M變小.即DL>BM,這意味著由于特定類別的頻率較低,特征的統計值被夸大.因此,這些非最優特征更有可能被選擇.這就是所謂的負相關[12].為了克服這個問題,如式(9)所示,對式(3)進行限定.

基于上述對IG 和CHI 特征選擇方法優缺點的分析,結合兩個引入的詞頻因子E和平衡因子F,提出一種基于BIG-WFCHI 特征選擇算法.其計算方法如式(10)所示.

為了更加準確的描述BIG-WFCHI算法,引入以下兩個定義:BIG-WFCHI離散度和BIG-WFCHI特征類間差值.

定義1.BIG-WFCHI 離散度,記為DpBIG-WFCHI,表示每個類別中特征BIG-WFCHI(以下簡稱IC)值的分散程度,用式(11)中的Dp表示.

其中,m表示特征總數,n表示類別數量,ICij表示第i個特征在第j個分類的BIG-WFCHI值,為第i個特征在所有類中ICij的平均值.

BIG-WFCHI離散度可以用來測量特征的冗余度.具有較大BIG-WFCHI離散度的特征具有較強的識別能力,即它們對分類更具價值.

定義2.BIG-WFCHI 特征類間差值,記為Df表示在類間最大IC值與第二IC值的差值,如式(12)所示.

其中,max(ICi)表示第i個特征在指定類中最大的BIG-WFCHI值,m ax′(ICi)表示第i個特征在指定類中第二大值.Df值越大說明特征越特征在特定類別中的分布越密集.也就是說,這個特征對分類更為關鍵.

利用Dp和Df進一步分析特征的冗余度,可以減少特征的維數,去除冗余特征,縮短運行時間.

BIG-WFCHI 算法的主要步驟如算法1.

在這里,本文利用E和F來減少低頻特征和負相關引起的干擾,然后根據Dp和Df選擇特征.不同的數據集需要不同的閾值?p和?f,其中極小的數據集不利于選擇,而較大的數據集去除了一些關鍵的分類特征.本文分別以Dp和Df的平均值作為閾值?p和?f.

2 實驗分析

2.1 數據集與實驗環境

本文采用2017年新浪微博數據為實驗數據集,并以Reddit 社區的“披薩隨機行為”為樣本1,測試BIGWFCHI 的通用性.這兩個數據集分別命名為WBdataset和PZdataset.它們的屬性如表1所示.

表1 實驗數據集

由于WBdataset 和PZdataset 中只有兩種狀態:retweeted 和not retweeted,successful 和not successful,因此本文將預測視為二值分類.通過分析WBdataset和PZdataset 的數據記錄,分別提取了20 個原始特征[13].采用IG,CHI,BIG-WFCHI,TF-IDF[14,15]分別從這兩個原始特征集中選擇在每個方法中貢獻大多數值的前10 個特征作為主要特征.

為了驗證BIG-WFCHI 方法的有效性,本文選取了LIBSVM(SVM)[16]、MaxEnt(ME)[17]、Naive-Bayes分類器(NBC)、K 近鄰(KNN)和多層感知器(MLP)5 種分類器.這些分類器通常用于機器學習,它們的分類結果在效果上有所不同[17–20].在此,本文簡要說明了這些方法的主要參數選擇.考慮到數據集是稀疏矩陣,本文選擇SMO[19]作為優化算法,在LIBSVM 中選擇RBF 作為核函數,使得數據集有更好的性能.在KNN中,k的值是通過交叉驗證確定的,得到的最佳結果介于100 到150 之間.由于一個分類模型的精度不是本文研究的重點,所以在MLP 中只設置了一個隱藏層.

2.2 實驗結果與分析

實驗中采用10 倍交叉驗證.對于每個特征選擇方法、分類器和數據集,我們執行10 次運行,然后報告結果的平均值、標準差和弗里德曼檢驗.

表2顯示了4 種特征選擇方法的精度.最高的分類精度用粗體加下劃線和突出顯示.從表2可以看出,本文提出的方法在支持向量機、KNN、NBC 和MLP上達到了最佳的精度.該方法在基于ME 的PZdataset和WBdataset 上分別取得了最佳精度和次優精度.

在10 倍交叉驗證中,由于每次運行時都會更改訓練數據集和測試數據集,因此分類精度會有所不同.為了顯示精度之間的差異,表3中執行了10 次運行的標準差.結果表明,在兩個數據集上,基于BIG-WFCHI 的分類精度標準差在KNN 中是最小的.在其他分類器中,基于BIG-WFCHI 的標準差也是小的有理數.

表2 IG、CHI、BIG-WFCHI 和TF-IDF 的分類精度(%)

表3 IG、CHI、BIG-WFCHI 和TF-IDF 的標準偏差

進一步探討10 次運行結果之間是否存在顯著差異,本文對這些分類結果進行了Friedman 檢驗.在所有的測試中,選擇變量無顯著性差異作為零假設,0.05作為置信水平.由于篇幅的限制,本文在只表4中顯示WBdataset 上的測試結果.所有的精確都大于0.05,這意味著我們接受了零假設.10 次10 倍交叉驗證沒有顯著性差異.因此,預測結果的均值是可靠的.在PZdataset上的測試結果顯示了相同的結論.

表5顯示了基于IG、CHI、BIG-WFCHI 和TF-IDF選擇的特征的不同分類器分類結果的AUC 值.從這些AUC 值可以很容易地看出BIG-WFCHI 優于其他3 種選擇方法.

圖1和圖2顯示基于IG、CHI、BIG-WFCHI 和TF-IDF 選擇的特征的不同分類器分類結果的ROC 曲線.可以看出,在4 種分類器中,BIG-WFCHI 選擇的特征具有最好的分類效果.

實驗結果表明,在不同的數據集或分類器下,基于BIG-WFCHI 選擇的特征子集,分類精度可以提高或至少保持在同一個數量級.通過以上討論,BIG-WFCHI方法可以更有效地選擇信息量更大的特征,實現特征選擇具有實際意義.

表4 WBdataset 中IG、CHI、BIG-WFCHI 和TF-IDF 的Friedman 檢驗

表5 IG、CHI、BIG-WFCHI 和TF-IDF 的AUC 值

圖1 基于WBdataset 相關選擇特征的不同分類器的ROC 曲線

3 結論

本文以轉發預測為例,討論了信息增益、互信息和卡方檢驗等方法在特征選擇中的應用,但這些方法存在負相關和可能對計算結果產生干擾等缺陷.本文引入平衡因子和詞頻因子來提高算法準確率;其次,提出了一種BIG-WFCHI 特征選擇方法.實驗結果表明,該方法克服了上述缺陷,消除了冗余貢獻,提高了ME、支持向量機、NBC、KNN 和MLP 等分類器的效率.

隨著網絡數據復雜度和規模的迅速增加,特征選擇變得越來越重要.BIG-WFCHI 特征選擇方法能去除冗余特征,有助于減少計算時間,節省存儲空間,提高機器學習效率.因此,為特征選擇提供了一種有效的方法.

圖2 基于PZdataset 相關選擇特征的不同分類器的ROC 曲線