基于SVM-RFE特征選擇的規(guī)則提取方法

吳 璐

(上海市規(guī)劃和自然資源局 信息中心， 上海 200003)

0 引言

由于支持向量機(jī)(Support Vector Machine, SVM)具有堅(jiān)實(shí)的統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)和良好的泛化性能，已經(jīng)被應(yīng)用到客戶分類和管理、銀行信用風(fēng)險(xiǎn)評(píng)估、故障檢測、地理遙感信息等[1-4]眾多領(lǐng)域中，并取得了較好的成果。然而SVM和人工神經(jīng)網(wǎng)絡(luò)一樣也存在著固有的缺陷，即其“黑箱模型”。人們很難理解其模型代表的意義，也無法對(duì)模型的預(yù)測結(jié)果做出一個(gè)合理的解釋。SVM 學(xué)習(xí)到的知識(shí)蘊(yùn)藏在由占樣本總數(shù)很少的支持向量及其權(quán)重系數(shù)(Lagrange系數(shù))所得到的決策函數(shù)中，用戶無法了解SVM 到底學(xué)到了什么、能處理什么樣的任務(wù)，也無從知道SVM 如何進(jìn)行分類和預(yù)測、為什么得出這樣或那樣的推理結(jié)論。由于缺乏透明性，在數(shù)據(jù)挖掘和決策支持領(lǐng)域、以及在安全性要求很高如醫(yī)療診斷方面等關(guān)鍵應(yīng)用方面，支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)一樣往往被認(rèn)為是不可靠的和難以理解的，使其應(yīng)用受到一定限制。

將支持向量機(jī)訓(xùn)練后生成的決策模型轉(zhuǎn)變成更加直觀、更易理解的知識(shí)的過程被稱為支持向量機(jī)規(guī)則提取方法。它主要分為基于學(xué)習(xí)的方法和基于結(jié)構(gòu)分析的方法兩大類[5]。前者比較典型的算法如TREPAN、GEX、BUR等[6]，后者如SVM + prototypes、RulExSVM算法等[7-9]。雖然這些方法在實(shí)際應(yīng)用中取得了一些成果，但從總體上看，這些規(guī)則提取方法產(chǎn)生的規(guī)則大都數(shù)量比較多、精度不高、規(guī)則的前提條件項(xiàng)數(shù)太多、結(jié)構(gòu)較為復(fù)雜，不便于人們的理解和解釋。此外，這些方法對(duì)于研究領(lǐng)域的數(shù)據(jù)維度較高也不能很好地適應(yīng)。

造成上述問題的主要原因主要在于過于強(qiáng)調(diào)準(zhǔn)確率和忠實(shí)度指標(biāo)，對(duì)可理解性重視不夠以及沒有對(duì)樣本屬性進(jìn)行降維處理提高可理解性。對(duì)此本文提出了一種基于SVM-RFE特征選擇(SVM-BASED Recursive Feature Elimination，SVM-RFE)的序列覆蓋規(guī)則提取方法，將特征選擇作為整個(gè)規(guī)則提取的一部分來進(jìn)行綜合考慮，并在規(guī)則生成和裁剪上通過采取包括生成的規(guī)則必須滿足最低的精度要求、覆蓋率大的規(guī)則優(yōu)先選取、限制搜索深度和采用FOIL增益對(duì)條件項(xiàng)的增加進(jìn)行評(píng)估對(duì)可理解性與準(zhǔn)確率和忠實(shí)度指標(biāo)之間進(jìn)行平衡。

1 SVM-RFE特征選擇算法簡介

SVM-RFE特征選擇算法是一種以支持向量機(jī)的分類性能作為特征選擇評(píng)價(jià)標(biāo)準(zhǔn)的后向遞歸消除特征選擇算法，具有較高的識(shí)別性能。它最早是由Guyon等[10]在基因選擇中首先提出來的，并將其應(yīng)用于癌癥分類問題中進(jìn)行基因選擇，取得了非常好的效果。在這之后許多人又對(duì) SVM-RFE方法進(jìn)行了進(jìn)一步的改進(jìn)以提高它的性能和效率[11-12]，目前已經(jīng)被廣泛應(yīng)用于基因表達(dá)數(shù)據(jù)分析、蛋白質(zhì)功能預(yù)測、圖像檢測、文本挖掘等多個(gè)領(lǐng)域。

SVM-RFE起始于全部特征，然后每次移去一個(gè)特征直到特征集合為空，移去的特征是所有特征中‖w‖2最小的一個(gè)。這樣對(duì)某一變量i，排序評(píng)價(jià)準(zhǔn)則如式(1)。

(1)

SVM-RFE方法通過不斷迭代方式將具有最小排序系數(shù)的特征移除，然后利用SVM對(duì)剩余的特征重新訓(xùn)練以獲取新的特征排序，最后得到一個(gè)特征的排序列表。利用該排序列表，定義若干個(gè)嵌套的特征子集F1?F2?…?F來訓(xùn)練SVM，并以SVM的預(yù)測正確率評(píng)估這些子集的優(yōu)劣，從而獲得最優(yōu)的特征子集。

2 基于SVM-RFE特征選擇的規(guī)則提取方法的實(shí)現(xiàn)

2.1 算法總體框架

基于SVM-RFE特征選擇的規(guī)則提取方法的總體架構(gòu)，如圖1所示。

圖1 基于SVM-RFE特征選擇的規(guī)則提取知識(shí)表示方法的總體框架

主要包括基于SVM-RFE特征選擇、支持向量機(jī)學(xué)習(xí)、規(guī)則生成和規(guī)則集裁剪等3個(gè)階段。

首先，對(duì)初始數(shù)據(jù)集基于SVM-RFE特征選擇算法進(jìn)行屬性約簡。根據(jù)它們?cè)赟VM分類器的權(quán)值進(jìn)行重要性排序，得到最優(yōu)特征子集并去除原屬性集中不相關(guān)和弱相關(guān)的屬性。在使用SVM-RFE算法進(jìn)行特征選擇時(shí)，為了減少SVM-RFE算法對(duì)訓(xùn)練集的選取較為敏感、特征排序不太穩(wěn)定的問題，我們通過在樣本集隨機(jī)生成多個(gè)訓(xùn)練集并綜合排名的方式進(jìn)行了優(yōu)化和改進(jìn)。

其次，用得到屬性減少的樣本集對(duì)支持向量機(jī)進(jìn)行訓(xùn)練和學(xué)習(xí)，得到全部支持向量集。去除其中預(yù)測分類與樣本原有的類標(biāo)簽兩者不一致的支持向量，從而生成清理后的支持向量集。

最后，通過一種變型的順序覆蓋規(guī)則學(xué)習(xí)算法對(duì)這些清理后的支持向量集進(jìn)行歸納學(xué)習(xí)生成規(guī)則集，然后通過AUCs的差異顯著性對(duì)規(guī)則集進(jìn)行裁剪，得到裁剪后的規(guī)則集。用驗(yàn)證集來對(duì)其進(jìn)行驗(yàn)證，以確保其準(zhǔn)確率(accuracy)滿足規(guī)定的要求，通過上述驗(yàn)證后我們就可以使用得到的規(guī)則集來進(jìn)行預(yù)測。本節(jié)后面重點(diǎn)對(duì)上述提到的這兩部分進(jìn)行說明。

2.2 基于優(yōu)化的SVM-RFE算法特征選擇

通過特征選擇可以使提取規(guī)則的可理解性得到很大的改善，還能夠提高分類器的識(shí)別率。這里采用基于支持向量機(jī)的特征選取方法，主要是由于它和支持向量機(jī)算法本身結(jié)合得更好，能夠保證甚至提高支持向量機(jī)的識(shí)別精度。

基于支持向量特征選擇選取方法主要分為Wrapper 、Filter和Embedded等[13]3種方法。考慮到Wrapper方法與學(xué)習(xí)分類器密切相關(guān)，構(gòu)造的特征子集能夠帶來較高的學(xué)習(xí)能力，因此我們選擇SVM-RFE這種方法，它在處理高維方面能力更強(qiáng)。當(dāng)然SVM-RFE這種方法也有不足之處，處理速度相對(duì)比較慢。但是考慮到對(duì)于規(guī)則提取來說，特征選擇的好壞更加重要，因此選擇SVM-RFE這種方法還是比較值得的。

在使用SVM-RFE算法進(jìn)行特征選擇時(shí)，針對(duì) SVM-RFE算法對(duì)訓(xùn)練集的選取較為敏感、特征重要性排序不太穩(wěn)定的問題，我們通過在訓(xùn)練樣本集隨機(jī)生成多個(gè)訓(xùn)練子集并采用綜合排名的方式進(jìn)行了優(yōu)化和改進(jìn)。具體說明如下。

(1) 對(duì)于樣本集{(x1,y1),(x2,y2),…,(xl，yl)}，其中xi∈Rd，yi=±1，隨機(jī)生成m個(gè)訓(xùn)練子集和測試子集對(duì)，其中m的取值根據(jù)樣本的數(shù)量，屬性維度和特征選擇的精度要求等確定。

(2) 對(duì)每一個(gè)訓(xùn)練子集分別用SVM分類器進(jìn)行訓(xùn)練，并用徑向基函數(shù)作為支持向量機(jī)的核函數(shù)，這是由于在很多實(shí)際應(yīng)用中發(fā)現(xiàn)它們具有較好的效果。懲罰參數(shù)和高斯核函數(shù)中的參數(shù)σ的值通過Grid search和10-fold交叉驗(yàn)證來確定。

(4) 對(duì)于每個(gè)特征根據(jù)其在最優(yōu)特征子集出現(xiàn)的頻度和位置，生成一個(gè)新的特征排序表。對(duì)每一個(gè)特征，按照式(2)進(jìn)行加權(quán)求和并按照權(quán)值大小降序排序，得到一個(gè)新的特征排序表。

(2)

其中，Si為第i個(gè)隨機(jī)訓(xùn)練子集上最優(yōu)特征子集中特征的數(shù)量；pi為特征f在第i個(gè)隨機(jī)訓(xùn)練集中最有特征子集中的位置；σ為懲罰系數(shù)(σ≥0)，當(dāng)其值越大特征出現(xiàn)的次數(shù)對(duì)權(quán)值的影響更大。

(5) 根據(jù)新的特征排序列表生成d個(gè)嵌套子集，在所有的隨機(jī)訓(xùn)練子集上用這些嵌套子集重新訓(xùn)練SVM分類器，并將這些嵌套子集所訓(xùn)練的SVM在測試子集上的分類精度進(jìn)行算術(shù)平均，算術(shù)平均值最高的所對(duì)應(yīng)的嵌套子集作為最終的最優(yōu)特征子集。

2.3 基于變型順序覆蓋算法的規(guī)則生成

在規(guī)則生成和裁剪階段，從基于特征選擇的規(guī)則提取的架構(gòu)上來看，原則上基于學(xué)習(xí)的規(guī)則提取方法如TREPAN、C4.5、BUR、CART等和基于結(jié)構(gòu)分析的提取方法如SVM+ prototypes、RulExSVM都可以直接用來進(jìn)行規(guī)則的提取。 基于在規(guī)則提取算法設(shè)計(jì)和實(shí)現(xiàn)上把提高可理解性作為一個(gè)重要目標(biāo)，兼顧可理解性與準(zhǔn)確率和忠實(shí)度之間的平衡原則，我們還提出了一種變型的順序覆蓋算法(Sequentail Covering Algorithm)將前面所述的一些提高可理解性的策略應(yīng)用到該算法的實(shí)現(xiàn)中以提高生成規(guī)則的可理解性。該算法通過對(duì)清理后的支持向量集進(jìn)行歸納學(xué)習(xí)來生成規(guī)則集。

該算法采用從一般到特殊的柱狀搜索方式，它在搜索過程中保留前面k個(gè)性能度量較高的選擇以降低只保留最高性能選擇容易造成的局部最優(yōu)問題。另外它只產(chǎn)生覆蓋正例支持向量的規(guī)則，即對(duì)于規(guī)則沒有覆蓋的實(shí)例默認(rèn)為負(fù)例。為了提高規(guī)則的可理解性，該算法在學(xué)習(xí)單個(gè)規(guī)則的核心子程序Learn-One-Rule的中主要特點(diǎn)說明如下。

(1) 迭代過程中對(duì)屬性值的劃分采用動(dòng)態(tài)方式，隨著約束條件的增加不斷調(diào)整，并且屬性劃分采用信息增益即式(3)進(jìn)行性能評(píng)估選取最佳分割點(diǎn)；另外在同樣性能條件下，離散屬性優(yōu)先，如式(3)。

(3)

(2) 在搜索過程中為了保證生成的規(guī)則有較好的可理解性，強(qiáng)制其最大搜索深度為5，即條件前提項(xiàng)的項(xiàng)數(shù)不能超過5，這是因?yàn)楫?dāng)前提條件項(xiàng)數(shù)超過5個(gè)以后一般情況下人們已經(jīng)不能很好理解。

(3) 在規(guī)則性能的度量上，采用FOIL增益即式(4)評(píng)估約束條件項(xiàng)增加前后的增益，當(dāng)該值大于0時(shí)增加約束項(xiàng)才是有價(jià)值的。在此我們選取該方法的主要原因是與其他性能度量方法相比，F(xiàn)OIL增益更傾向具有高準(zhǔn)確率并且覆蓋許多正例的規(guī)則，這樣有利于提高規(guī)則的可理解性。

(4)

其中,pos(neg)、pos′(neg′) 分別為條件項(xiàng)增加前后規(guī)則覆蓋的正(負(fù))例的數(shù)目。

(4) 生成的每一條規(guī)則都必須滿足一定的精度要求，即其TPR/FPR>(TPR/FPR)min不小于(TPR/FPR)min,從而確保生成的規(guī)則有較高的精度。

Learn-One-Rule整個(gè)規(guī)則生成和裁剪的算法如下。

輸入：

SVs(來自SVM學(xué)習(xí)階段的結(jié)果——調(diào)整后的支持向量集)。

特征排序列表F(按照屬性重要性降序排列，來自SVM-RFE的特征選擇)。

(TPR/FPR)min(最小可接受的正例覆蓋率/負(fù)例覆蓋率比值)。

輸出：

命題規(guī)則集R。

處理：

① 初始化S=SVs。

② 初始化Best_hypothesis=φ，Candidate_hypotheses={Best_hypothesis}。

③ 對(duì)于F中的每一個(gè)屬性fi， 根據(jù)其屬性值在S中的取值范圍，尋找其最佳的閾值aib，它能在所有的樣例S中根據(jù)式(3)得到最大的信息增益。

④ 按照上述排序順序，對(duì)于F中的每一個(gè)屬性fi分別用與其相應(yīng)的在③中得到的閾值aib生成一個(gè)約束ci，生成約束集C。

⑤ 對(duì)Candidate_hypotheses中的每個(gè)假設(shè)h，按照特征排序列表F的順序添加約束集C中沒有添加過的約束，如已無法添加則直接刪除。對(duì)于添加后的規(guī)則用式(4)評(píng)估其添加約束前后的FOIL增益，當(dāng)其小于0時(shí)，將該條規(guī)則予以刪除。這樣得到新的假設(shè)集New_candidate_hypothesis。

⑥ 對(duì)New_candidate_hypothesis中的每個(gè)假設(shè)h，確定該條規(guī)則覆蓋樣本集S上的正例和負(fù)例數(shù)量，并由此計(jì)算它的TPR和FPR。如果假設(shè)h的TPR/FPR大于Best_hypothesis的TPR/FPR，則Best_hypothesis←h。

⑦ 選取New_candidate_hypothesis中TPR/FPR性能最好的k個(gè)規(guī)則來更新Candidate_hypotheses。

⑧ 如果Candidate_hypotheses=φ，返回到⑤。

⑨ 如果Best_hypothesis在樣本集S上的TPR/FPR≤(TPR/FPR)min，將該規(guī)則添加到規(guī)則集R中，并將它所覆蓋的SVs 從S中刪除，并轉(zhuǎn)到②。

⑩ 重復(fù)上述步驟②至⑨直到Stp中的所有SVs被覆蓋或者生成的規(guī)則因不滿足要求而被拒絕，規(guī)則生成算法終止。

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

本節(jié)進(jìn)一步對(duì)本文所提出的基于SVM-RFE特征提取的規(guī)則提取算法的性能進(jìn)行了驗(yàn)證。本算法是用MATLAB 7.8.0 (R2009b) 實(shí)現(xiàn)的，運(yùn)行環(huán)境是一臺(tái)CPU 為 Intel Core 2-Quad processor，主頻2.8 GHz， 內(nèi)存容量為4 GB的PC機(jī)，所用的SVM 軟件工具是較為流行的Libsvm (3.1.7)，其他對(duì)比的分類算法使用的是Weka 3.2相應(yīng)的實(shí)現(xiàn)。

在實(shí)驗(yàn)中我們主要用可理解性(comprehensibility)、正確率(accuracy)和忠實(shí)度(fidelity)等指標(biāo)來進(jìn)行評(píng)價(jià)。可理解性用規(guī)則的數(shù)量以及規(guī)則中前提條件平均項(xiàng)數(shù)來對(duì)其進(jìn)行度量；正確率用被正確識(shí)別的樣本數(shù)占總樣本的比率來度量；忠實(shí)率用抽取的規(guī)則與支持向量機(jī)預(yù)測相一致的樣本數(shù)占總樣本的比率來表示。實(shí)驗(yàn)主要采用了來自UCI庫的10個(gè)數(shù)據(jù)集，在所有的數(shù)據(jù)集上用于訓(xùn)練和測試的數(shù)據(jù)比例為70:30，70%的數(shù)據(jù)通過10折交叉驗(yàn)證法(10-folders cross validation)用來對(duì)分類器進(jìn)行學(xué)習(xí)和提取規(guī)則，剩下的30%用于評(píng)估所產(chǎn)生的規(guī)則集的性能指標(biāo)。

下面以Heart desease數(shù)據(jù)集為例進(jìn)行說明，該數(shù)據(jù)集共有13個(gè)屬性和270個(gè)樣本，其中屬性1,4,5,8,10,12是連續(xù)值屬性，其他則為離散值屬性。在該數(shù)據(jù)集上隨機(jī)生成60個(gè)訓(xùn)練和測試子集對(duì)，然后用SVM-FRE方法分別在這60個(gè)子集對(duì)上進(jìn)行特征排序并確定其對(duì)應(yīng)的最優(yōu)特征子集，并按照式(2)對(duì)每一個(gè)屬性在這60個(gè)子集上的最優(yōu)特征子集中出現(xiàn)的頻度和位置進(jìn)行加權(quán)平均得到屬性排序列表，如表1所示。

表1 Heart disease 數(shù)據(jù)的分析結(jié)果(分類器個(gè)數(shù)M3=60個(gè))

將生成的嵌套特征子集在前面隨機(jī)產(chǎn)生的60個(gè)的測試集上計(jì)算SVM平均分類精度得到最優(yōu)特征子集并最終得到最優(yōu)特征子集{12,7,3,9,6,4,13,1,2}。用包含這些特征子集的數(shù)據(jù)集對(duì)SVM 進(jìn)行訓(xùn)練得到支持向量，并用生成的支持向量機(jī)模型對(duì)這些支持向量進(jìn)行分類預(yù)測，去除預(yù)測分類結(jié)果與樣本原有的分類標(biāo)簽兩者不一致的支持向量，得到清理后的支持向量。采用3.3節(jié)的方法生成5個(gè)規(guī)則(其中含1個(gè)默認(rèn)規(guī)則)，我們分別計(jì)算每條規(guī)則增加前后的AUC的變化，如圖2所示。

圖2 規(guī)則集在Heart desease 數(shù)據(jù)上的ROC圖

分別為：0.69，0.78，0.85，0.87。由于第4條規(guī)則增加后變化不顯著我們將其裁剪，得到規(guī)則集如式(5)。

R1：IFX13=7 ANDX3=4 THEN Occur=2

R2：IFX1≥59 ANDX9=1 THEN Occur=2

(5)

R3：IFX12=1 ANDX2=1 THEN Occur=2

Default: Occur=1

為了更好地對(duì)本文所提出的算法的性能進(jìn)行評(píng)判，我們選取了兩個(gè)有代表性的規(guī)則提取方法，一個(gè)是直接從樣本中提取規(guī)則的C4.5算法，另一個(gè)是基于結(jié)構(gòu)分析的SVM+ prototypes算法與本文提出的基于SVM-FRE特征選擇的規(guī)則提取方法進(jìn)行比較。

這三種算法在5個(gè)數(shù)據(jù)集上的結(jié)果，如表2所示。

表2 本文提出的方法、C4.5算法和SVM+ prototypes算法的性能比較

從表中我們可以看出本文提出的算法在識(shí)別率上基本上和另外兩種相差不大，但所產(chǎn)生規(guī)則集中規(guī)則的數(shù)量以及規(guī)則前提中的條件明顯比另外兩種要小，提高了提取規(guī)則的可理解性。

4 總結(jié)

本文提出了基于SVM-RFE特征選擇的規(guī)則提取方法，該方法采用優(yōu)化的SVM-RFE來獲取重要屬性集，并采用一種變型的順序覆蓋規(guī)則算法結(jié)合AUC進(jìn)行規(guī)則生成和裁剪。實(shí)驗(yàn)表明該方法在保持較高的精確度和忠實(shí)率的前提下提高了提取規(guī)則的可理解性。