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

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

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

1 引 言

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

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

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

2.1 數據預處理

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

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

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

其中，m表示總的事件數；n表示GTD數據集總的維度.

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

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

(1)

2.2 mRMR特征選擇

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

(2)

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

(3)

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

(4)

(5)

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

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

2.3 TFM分類算法

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

(6)

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

(7)

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

(8)

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

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

(9)

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

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

2.4 模型評估

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

(10)

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

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

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

表1 分類評價指標定義

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

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

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

表2 恐怖事件組織和標簽

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

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

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

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

從表3可知，TFM分類效果較穩定，準確率也較高.表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分類模型中可優先考慮TFM模型.

表3 TFM與其他模型比較

表4 事件C分類結果

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

表5 運用TFM模型稀疏測試數據結果

5 結 論

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