基于mRMR與因子分解機的分類模型研究

王 美， 龍 華， 邵玉斌， 杜慶治

(昆明理工大學信息工程與自動化學院， 昆明 650000)

1 引 言

對恐怖事件聚集性的研究，前期對其研究多是使用對數(shù)據(jù)匯總統(tǒng)計的方法來顯示事件中特定變量隨時間變化的趨勢.1999年Enders等人使用時間序列模型，分析恐怖事件對國內(nèi)生產(chǎn)總值GDP的影響，得出當恐怖事件減少時GDP呈現(xiàn)增長的結論[1].2002年Major使用博弈論與概率分布量化風險，對恐怖事件具體因素隱藏的信息進行分析[2].2003年Sandler使用博弈論理性分析了恐怖組織與目標國家間的相互作用，得出一個國家的游客、公民和企業(yè)，由于他們威懾能力小，較容易成為攻擊目標的結論[3].Guo等人在文中分析上述章節(jié)所建立的統(tǒng)計與數(shù)學模型是基于先驗假設和完備的數(shù)據(jù)集，然而當下因各種原因，GTD數(shù)據(jù)集所記錄的數(shù)據(jù)往往不完整或是存在不確定值，所以使得制定有效假設和檢驗假設能力受限[4].故需探索新的可視化和計算方法，以得到分析GTD數(shù)據(jù)更好的模型.

在探索新的分析方法中，首先是Wang等人采用協(xié)調(diào)多視圖的方法開發(fā)了用于探索恐怖事件數(shù)據(jù)的可視化分析系統(tǒng)，可揭示一些未知的恐怖襲擊事件發(fā)生趨勢和規(guī)律，但該方法中多是對數(shù)據(jù)匯總統(tǒng)計結果進行可視化，沒有對GTD數(shù)據(jù)本身存在的稀疏性以及高維度多冗余問題進行很好的處理[5].Pagán發(fā)現(xiàn)了該問題，開始引入了數(shù)據(jù)清洗策略，Pagán在文中采用均值替換法MI、中值替換法MDI以及K近鄰填補法KNNI對GTD中的缺失數(shù)據(jù)進行填充[6]，清洗后的數(shù)據(jù)用于線性判別分析LDA、K最近鄰KNN以及分類決策樹RPART分類器GTD中對伊拉克組織的恐怖襲擊事件進行分析.由于GTD中存在大量缺失值和冗余特征，全部采用填充方式使得數(shù)據(jù)集產(chǎn)生了不可忽略的偏差等原因，最終分類效果并不是很理想，交叉驗證錯誤率均在40%左右.為了減小GTD中的冗余特征量以及合理處理缺失數(shù)據(jù)，Iqbal等人[7]對數(shù)據(jù)進行了降維，并對缺失值增加了刪除處理方式，不足的是文中基于主觀對問題的理解，對特征采用了手動選擇特征方式降維，使得分類結果有很強的主觀色彩.在后面的研究中，處理對GTD數(shù)據(jù)的分類多是采用機器學習方法，2016年Muhammad 等人使用監(jiān)督學習方法如貝葉斯分類器和決策樹分類器，對特定巴基斯坦的GTD集進行分析[8]；2017年Dong使用BP神經(jīng)網(wǎng)絡對印度恐怖襲擊事件進行了分析預測[9]；Ding等人采用經(jīng)多途徑選擇的十二個特征，使用神經(jīng)網(wǎng)絡，支持向量機(Support Vector Machine,SVM)和隨機森林(RF)宏觀預測分析2015可能發(fā)生恐怖事件的地方[10].但就恐怖襲擊事件數(shù)據(jù)本身而言，前面實驗中都未有很好的考慮數(shù)據(jù)集高維度稀疏性大的問題，如高維度稀疏數(shù)據(jù)會使得BP預測效果很差等，針對解決手動特征降維問題，Mo等人采用了最大相關性(Max-Relevance)以及最大相關性最小冗余mRMR特征選擇方法獲取特征集[11]，并結合支持向量機(SVM)，樸素貝葉斯(Naive Bayes,NB)和Logistic回歸(LR)分類器對恐怖襲擊事件進行分類研究，文中有效地驗證了將機器學習應用于恐怖主義研究領域的可行性，但文中訓練集是采用專家定義對事件進行分類，且未解決選取后的優(yōu)化特征集仍存在的數(shù)據(jù)稀疏性的問題，這將會影響分類效果不佳.

基于以上問題，同時與文獻[12]提出的混合變量選擇算法相比，因FM往往有很好的通用性能，且常能取得較好的效果且善于處理稀疏數(shù)據(jù)集的特性[13]，故本文提出一種基于“最小冗余最大相關”(Minimal-redundancy maximal-relevancy，mRMR)與“因子分解機”( Factorization Machines， FM )結合的TFM分類模型，mRMR使用增量搜索方法尋找近似最優(yōu)的特征集，找到最佳特征子集以最大化分類精度，并結合因子分解機FM模型對GTD進行量化分類.

2.1 數(shù)據(jù)預處理

公開數(shù)據(jù)集“全球恐怖主義研究數(shù)據(jù)庫”(Global Terrorism Research Database,GTD)[14]具有高維海量數(shù)據(jù)，大數(shù)據(jù)的低價值的特征，存在大量未記錄缺失數(shù)據(jù)，為了提高數(shù)據(jù)的質(zhì)量，所以需要進行數(shù)據(jù)預處理.

文中用二分類法對GTD展開討論，假設GTD數(shù)據(jù)集表示為

Rj,i∈(1,m),j∈(1,n)

其中，m表示總的事件數(shù)；n表示GTD數(shù)據(jù)集總的維度.

定義1定義GTD事件類型為y(i)={0,1}，若此處以1表示A組織所為事件，則0與之相反，則測試集表示為(x(1),y(1)),…,(x(i),y(i)),i∈(1,m)，m表示總的事件數(shù)，因GTD 數(shù)據(jù)具有高損失率的問題，采用數(shù)據(jù)剔除法進行預處理.

定義2定義特征j的缺失率為

(1)

2.2 mRMR特征選擇

mRMR算法[15]是根據(jù)特征與目標分量間相關性以及特征與特征間的冗余性進行特征提取，其中,相關性和冗余性用互信息量(MI)值大小表示；MI與相關性成正比，互信息的定義如下.

(2)

O=MI(xf;c)，f≤n

(3)

Gt中的特征向量xt與Gs中的全部特征向量間的冗余R度計算如下式.

(4)

(5)

當總的特征為N(=s+t)時，mRMR的特征評估將進行N輪.經(jīng)過mRMR評估后原特征集{x1,x2,…,xN}，重新排序后的特征集表示為s如下.

最終最優(yōu)特征集取目標函數(shù)最小損失值對應的s中的H(≤N)個特征.

2.3 TFM分類算法

TFM算法意在構建分類模型，結合了因子分解機算法FM[16]和分類閾值算法.

(6)

式(6) 計算復雜度為O(kn2)，根據(jù)文獻[16]將式(6)計算復雜度化簡為O(kn)后，表達式如下式.

(7)

假設FM中所有參數(shù)Θ={w0,w1,…,wn,v11,…,vkn}，為了避免產(chǎn)生過擬合現(xiàn)象，所以此處FM最優(yōu)化目標選取正則化的最小二乘法.

(8)

其中，x(i)表示第i個事件；loss( )為損失函數(shù)；λθ表示參數(shù)θ的正則化系數(shù).結合以上分析，模型中參數(shù){w0,W,V} 可采用隨機梯度下降法SGD對進行學習，計算偽代碼可見ALGORITHM 1.

分類閾值算法，加入該算法以實現(xiàn)二分類，假設訓練集中屬于A分類的有z件，于A分類的有a件，則取閾值函數(shù)：

(9)

當事件x(i)預測值P>P′時，預測結果屬于A分類，反之不屬于.

TFM模型是將FM計算得到的預測結果，與分類閾值結果比較然后歸類得到分類結果.

2.4 模型評估

2.4.1 logit loss損失函數(shù) logit loss 是普遍認可的一種模型分類效果分類標準[17]，其定義如下.

(10)

2.4.2 分類指標 分類模型性能評價指標中常使用的有準確率、召回率和靈敏度[18]，以及本文采用的馬修斯相關系數(shù)(Matthews Correlation Coefficient,MCC)[19]衡量指標 :

(4) 馬修斯相關系數(shù):MCC=

上式中的TN、FN、TP以及FP定義如表1所示.

表1 分類評價指標定義

TN為被模型預測為負的負樣本；FN為被模型預測為負的正樣本；TP為被模型預測為正的正樣本；FP為被模型預測為正的負樣本.

文中使用了不同的模型進行分類效果比較，鑒于MCC同時考慮了TP、TN、FP和FN，可用來很好的衡量分類效果，MCC越大越好，故本文選用MCC評價指標.

實驗中，我們采用了全球恐怖主義研究數(shù)據(jù)庫GTD數(shù)據(jù)集. GTD記錄了從1970年至今世界各地的恐怖事件信息，并且不斷的更新各種恐怖事件，至今已超過14萬恐怖襲擊事件，且每一個事件超過45個特征記錄值，這使其成為目前是介紹基于恐怖事件的最全面的非機密數(shù)據(jù).文章中選取了2001年至2017年近17年南亞地區(qū)A組織所為事件分別打標簽得到分析數(shù)據(jù)集G.表2列出分析對象近17年的18 737個總事件，其中分別對A組織所為和非其所為事件數(shù)進行統(tǒng)計，并打標簽，A組織所為標記1，反之標記0.

表2 恐怖事件組織和標簽

我們將按照2.1方法對數(shù)據(jù)集G進行處理，處理后的數(shù)據(jù)集G中pj>0有一半特征，說明處理后的GTD數(shù)據(jù)集中仍存在大量未記錄數(shù)據(jù)或空值數(shù)據(jù).

我們于Python 3.6上完成實驗，實驗中首先使用mRMR函數(shù)應用于A組織訓練集，根據(jù)式(5)增量特征選擇方法獲取諸多特征子集，實驗有58個特征故共有58個候選子集.我們對訓練集使用四折交叉檢驗獲取訓練集和驗證集，圖1所示為每一個候選子集對應的FM預測輸出與分類結果的損失值，我們從圖中觀察與后臺計算結果對應取最小損失值6.044 257 3對應的36個特征子集為最優(yōu)特征集.

圖1 mRMR選取特征子集對應的分類損失值Fig.1 Loss value for feature subset based on mRMR

許多方法都用于分類模型中,如文中提到的邏輯回歸(Logistic Regression,LR)、支持向量機SVM和樸素貝葉斯，但是很難說明哪種分類比較好，不同的數(shù)據(jù)集適合不同的分類模型.本文基于mRMR確定的最優(yōu)特征集應用GTD數(shù)據(jù)集對TFM、LR、SVM和NB其分類進行了實驗，實驗中采用了tensorflow框架實現(xiàn)TFM模型，極大化的優(yōu)化了模型的實現(xiàn)，分類具體效果比較見表3.表3中耗時為測試時長T，即測試所用時間.由表3可直觀看出TFM分類準確率與MCC值均優(yōu)于三個模型，LR次之，NB準確率和MCC最為不理想，但就耗時來說TFM相對微大于三個模型，就此問題來分析，分類結果供人為使用分析，故毫秒的差異不足以影響使用效果.結合結果與LR[20]、SVM[21]以及NB[22]模型特點可分析，TFM將特征映射到高維來考慮特征與特征間的關系，且TFM通過引入輔助向量迭代求取兩個特征間的參數(shù)，故效果較好，但也正是引入了輔助向量，故相對于其他三個模型來說耗時略大些.

從表3可知，TFM分類效果較穩(wěn)定，準確率也較高.表4所示事件即為TFM分類正確，但其他三個模型失效的案例.C1是2006年11月19日的一個暴恐事件，屬于A組織所為，正確歸類應是1；C2是2008年7月7日的一個暴恐事件,非A組織所為，正確歸類應是0.TFM的分類錯誤率1.7%低于LR的2.95%、SVM的3.03%以及NB的26.56%，所以在GTD分類模型中可優(yōu)先考慮TFM模型.

表3 TFM與其他模型比較

表4 事件C分類結果

從實驗可知，TFM模型有一定優(yōu)勢，但存在耗時T略大問題，分析是因為TFM模型中引入輔助向量導致.在以下場景中該問題可做如下優(yōu)化：(1) 如類似本文分類結果供人為使用分析的分類中，毫秒的差異不足以影響使用效果可接受；(2) 選擇適合的數(shù)據(jù)集，因為該模型原本就為解決稀疏數(shù)據(jù)分類問題而提出，故合適的數(shù)據(jù)集，即使耗時稍大，但效果明顯，如此處采用一個稀疏度約為0.029 6的0和1組成的數(shù)據(jù)集(此處定義：稀疏度=非零總數(shù)值個數(shù) / 總數(shù)值個數(shù))做個測試實驗，結果如表5所示，值得分析的是從表5中看LR與SVM準確率相同，側面反映出SVM將特征映射到高維部分計算失效，只有線性部分有用，正如文獻[16]說的處理稀疏數(shù)據(jù)時FM比SVM更有優(yōu)勢，當數(shù)據(jù)過于稀疏時SVM失效，所以最終結果與LR一致，同時說明在處理稀疏數(shù)據(jù)集時FM有利于高維部分的計算；(3) 類似醫(yī)學中癌癥癥狀分類，或關鍵時刻的模糊稿件字符識別分類如罪犯筆跡等中，記錄數(shù)據(jù)較為稀疏且更為要求分類性能穩(wěn)定，效果較好的情況，可以一定的時間為代價，得到更準確的分類效果，此時可考慮TFM分類模型.

表5 運用TFM模型稀疏測試數(shù)據(jù)結果

5 結 論

由以上分析可知，類似于TFM和LR類的機器學習方法可用于分析恐怖主義數(shù)據(jù)的特征關系，且具有高準確性和快速性.本文基于GTD數(shù)據(jù)集，使用Python3.6統(tǒng)計數(shù)據(jù)，使用mRMR算法獲取分類損失函數(shù)值最小的優(yōu)選特征子集，對準備好的數(shù)據(jù)集使用不同的分類器進行分析.我們得出結論：TFM優(yōu)于其他三個模型，但其代價是耗時略多，但也有一定的優(yōu)化方案在第四部分中進行了概括.所以總體來說分類GTD時，若需要更為準確的分類效果則選TFM，若更為追求時間成本，則可選用LR或SVM算法.當然在實驗中遇到特別稀疏的數(shù)據(jù)集，TFM模型較合適.總的來說考慮了mRMR特征提取算法，結合了FM模型與分類閾值算法的TFM模型確實量化了對恐怖事件的分類問題，之后可在此基礎上進行更多的研究.如文獻[23]中提出的改進mRMR特征選擇方法，融合多種相關度量方式對特征子集進行特征選擇，可以恐怖主義事件為數(shù)據(jù)集展開優(yōu)化mRMR算法問題以及考慮多分類問題等.