基于垂直數據格式頻繁閉項集的選擇性集成算法的研究

吳陳，楊镕華

（江蘇科技大學 江蘇 鎮江212000）

基于垂直數據格式頻繁閉項集的選擇性集成算法的研究

吳陳，楊镕華

（江蘇科技大學 江蘇 鎮江212000）

集成學習是現今機器學習領域研究的熱點問題，選擇性集成通過對基分類器進行選擇來提高集成分類器的泛化能力，降低預測開銷。模式挖掘是一種將問題轉化為事務數據庫中模式的全新挖掘策略。本文將垂直數據格式頻繁閉項集的模式挖掘方法應用于分類器的選擇過程，利用垂直數據結構、頻繁閉項集及模式挖掘方法的優勢，提出一種預測性能更好、更加高效的選擇性集成分類算法。

選擇性集成；垂直數據格式；頻繁閉項集；模式挖掘；分類器

分類器集成是將若干個學習得到的基分類器以某種方式組合來解決同一個學習任務，國際機器學習界的權威學者Dietterich曾在《AIMagazine》雜志上將集成學習列為機器學習領域的四大研究方向之首，人們發現通過將基學習機集成得到的集成學習機的預測效果顯著優于單個學習機［1］。隨著大批量的學者進行集成學習的研究，人們發現沒有選擇的集成存在一些缺陷，與單個學習機相比，隨著基學習機數量的增加，具有負影響的基分類器存在的可能性增大，冗余基分類器增多，導致它們所需的存儲空間增大，預測速度明顯下降。為了解決這個問題，2002年，周志華等人首先提出了“選擇性集成”的概念，理論分析和實驗研究表明，基于某種衡量標準，通過將效果不好的基學習機剔除能夠得到預測精度高、速度快、存儲消耗少的集成學習機［2］。

1　研究現狀

最早是通過枚舉法得到最優的基分類器集，但是隨著基分類器的數量增加，計算量極大，所以枚舉法不可行，通過近十年的研究，根據算法采用的選擇策略不同將選擇性集成方法分為迭代優化法、排名法、分簇法以及模式挖掘法［3］。趙強利將常用算法GASEN、FS、OO（迭代優化法）、MDSQ（排序法）、CPF（分簇法）和PMEP（模式挖掘法）從預測性能、選擇時間、集成分類器大小三方面進行比較，通過采用十字交叉驗證法進行實驗得出結論PMEP和MDSQ算法精度最佳、分類器選擇時間較少，但是對于實時性要求較高的領域，優先考慮PMEP［4］。由此可見，模式挖掘法作為一種全新的分類器選擇策略，具有明顯的性能優勢，需要我們進行更加深入的研究。

2　基于模式挖掘的選擇性集成算法

模式挖掘是一種將問題轉化為事務數據庫中模式的全新挖掘策略。常用的模式挖掘方法有：Apriori算法、FP-growth算法、Max-Miner算法等，在如此多的算法中，基于內存的算法已經成為主流，為了在內存中完成頻繁模式的挖掘就必須在算法中選擇一種可以將數據集壓縮在內存中的數據結構，目前FP-Tree已經成為最常見的選擇。趙強利提出了一種將模式挖掘應用于選擇性集成的方法，一種基于FP-Tree的快速選擇性集成算法（CPM-EP）算法［5］，與現有的選擇性集成策略相比較，該算法在泛化能力、計算開銷方面具有顯著的優勢。盡管如此，該方法仍存在一定的不足：在基分類器的選取過程中并沒有充分考慮到單個分類器的分類能力以及各成員分類器之間的差異性，造成最終的集成分類器因混入了性能不好的、冗余的分類器導致準確性下降、計算開銷增大；當數據很多、數據庫很大時，構造基于主存的FP樹有時是不現實的；當最小支持度較低或數據集中存在長模式時，頻繁模式挖掘可能產生大量的頻繁項集，如為了得到一個長度為100的頻繁項集，首先必須導出（2^100-1）個頻繁項集，并且很多頻繁模式是沒有區別力的。

基于以上優缺點，文中對基于FP-Tree的快速選擇性集成算法進行改進，研究了一種將垂直數據格式頻繁閉項集的模式挖掘方法［6］應用于選擇性集成的集成策略（ICPM-EP），以提高分類器的泛化能力、降低計算開銷。

2.1算法思想

算法的主要思想是：將對分類器的選擇問題轉換為對頻繁模式的挖掘問題［7］，在挖掘的過程中，首先將事務數據庫用垂直數據格式表示，根據各分類器的準確性與差異性對分類器進行篩選剔除，然后將閉頻繁模式壓縮到一棵FP樹，加快統計、檢索速度，并減少占用的內存空間，最后利用貪婪算法獲得相應的集成分類器。

在該算法中，將所有基分類器對校驗樣本集的分類結果保存在一個預測結果表中，表中的每一行保存著一個分類器的標識號和該基分類器分類正確的樣本標識號。將事務數據庫用垂直格式表示，能夠直觀地觀察出各分類器的準確性及差異性，根據判斷準則，對預測結果表進行精簡，去掉準確性差、差異性小等冗余的分類器；根據閉項集的概念能夠有效的去除冗余頻繁模式，避免了由于數據庫大、數據為長模式而導致FP樹無法實現的問題。

2.2ICPM-EP算法模型

該模型主要包括：用垂直數據格式表示事務表、對分類器進行篩選、獲取閉頻繁項集的FP樹、通過貪婪算法獲取集成分類器幾個步驟。ICPM-EP算法模型如圖1所示。

圖1　ICPM-EP算法模型

算法實現描述如下：

偽代碼：

2.3算法實現過程

在該算法中，首先初始化結果集；然后將各分類器對校驗樣本集分類正確的標識號保存在分類結果表中，并根據分類器的準確性及各分類器的差異性對基分類器進行篩選，去除準確性差、差異性小的冗余分類器；對所有可能的分類器結果k［1，L］，根據閉頻繁項集的概念獲得去除冗余后的FP樹；然后基于獲得的FP-tree獲取k對應的集成分類器的結果；最后從所有結果中選取對校驗樣本集VS預測精度最高的作為最終的輸出結果。

下面將從獲取垂直數據格式事務表，精簡事務表，FP-tree的構建以及分類器的選擇4個步驟進行詳細介紹。

2.3.1獲取垂直數據格式事務表

L個分類器對校驗樣本集VS中的樣本依次進行分類，并將分類正確的樣本標識號及頻繁項目的支持計數保存在預測結果表中。表中的每一行包含3個屬性，分別是分類器標號、該分類器對應的事務列表以及分類正確的樣本個數，分別用Cid、VSset、num表示。據此，即得到垂直數據格式預測結果表。

假設L=10，對應的分類器標號分別為C1，C2，…，C10，校驗樣本集VS中共有12個樣本，標號分別為S1，S2，…，S12，可得垂直數據格式預測結果表如表1所示。

表1　垂直數據格式預測結果表

2.3.2精簡事務表

通過對各分類器進行選取來達到對垂直數據格式事務表進行精簡的目的。實現方法主要分為兩步：一、根據各分類器準確性對分類器進行排序；二、根據分類器的準確性與差異性采用合適的停止準則對分類器進行簡單篩選，首先，如果一個分類器分類正確的樣本集對于另一個分類器均能分類正確，則將這個分類器去除，去除分類器C5；其次，去除分類器準確性較差的分類器，去除掉準確性小于最大分類器一半的分類器，如去除C2、C10；最后，根據差異性準則選擇出差異性小的分類器刪除，如果總的分類器數目少于2 k個，則添加新的基分類器重復此步驟，直到簡化后的基分類器的個數大于2 k為止。差異性準則判斷如下：

將兩個分類器Ci、Cj（i！=j）之間的差異性Div（i，j）定義為兩個分類器均分類正確所占的比例。如果兩分類器的差異性大于平均差異性，則保留兩分類器，若小于平均差異性，則刪除。

2.3.3構建FP樹

根據精簡的垂直數據構建FP樹，首先用垂直數據投影事務，由于各分類器的事物列表遞增排列，所以只需要掃描各項目事務的表頭事務就可以構建最小事務，避免了從頭到尾掃描事務列表。依據垂直數據投影事務的過程如表2所示。

表2　垂直數據投影事務的過程表

然后將滿足支持度的投影事務插入到FP樹中，直到所有滿足支持度的最小事務被插入到FP樹為止，在插入過程中保證所有的頻繁項集都是閉項集。FP樹的存儲結構不同于水平數據格式的結構，其存儲結構分為FP樹本身和垂直頻繁項目頭。FP樹本身與水平數據的FP樹存儲結構中的FP樹本身相同，不同的是頻繁項目頭表，垂直頻繁項目頭表是由分類器名稱（C_name）、支持計數（S_count）、項目對應事務的頭指針（H_link）、項目對應事務的尾指針（T_link）以及FP樹項目鏈頭（N_link）5個域組成。FP樹創建的過程中，垂直項目頭表的變化如下圖所示。其中FP樹創建前，掃描數據庫一次后垂直項目頭表如圖2所示。第一個事務插入FP樹后垂直項目頭表如圖3所示。

圖2　掃描數據庫一次后垂直項目頭表圖

圖3　第一個事務插入FP樹后垂直項目頭表圖

2.3.4選擇基分類器

根據構造的FP樹進行基分類器的選擇采用貪婪方法。主要分為以下幾步：

步驟一：初始化結果集，PR.set=null；PR.correct=0，其中PR.set為入選的基分類器的集合，PR.correct為對應基分類器集合對事務分類正確的數目。

步驟二：創建Path-table表，FP樹按照從左到右的順序將從根節點到葉子節點出現的分類器及該路徑的count值記錄在表中。該表的每一行代表FP樹的一條路徑。原始Pathtable表如表3所示。

表3　原始Path-table表

步驟三：選擇分類器：從Path-table表中選擇出count最大的的路徑對應的分類器，記為classifier［i］，其中i表示行數。

當count［i］+|PR.set|>K（K為選擇的分類器的個數）時，說明選擇K個分類器無法滿足多數投票法的規則，則將該行從表中刪除重復該步驟，直到count［i］+|PR.set|<=K，此時PR. set=PR.set+classifier［i］，PR.correct=PR.correct+count［i］。最后將入選的分類器從該表中刪除得到更新的Path-table表。第一次更新后的Path-table表如表4所示。

表4　第一次更新后的Path-table表

步驟四：重復步驟三直到count［i］+|PR.set|=K或Path-table表為空，返回最終結果PR。

實驗比較：

為了驗證算法的有效性，本課題將對SelectBest，基于水平格式模式挖掘的選擇性集成算法（CPM-EP）以及基于垂直數據格式的頻繁閉項集選擇性集成學習算法（ICPM-EP2）進行比較。

實驗所采用的數據集為 KEEL-dataset中的 Text Classification data sets。

實驗中，利用weka平臺，采用java語言進行編程實現，采用5次交叉驗證的方法，訓練生成5個BP神經網絡、5個C4.5決策樹、5個樸素貝葉斯，5個SVM，在多數據集上比較多種實驗結果，結果用均值表示。為避免單個數據集對結果的影響較大，將對精確度數值的比較轉換為對排名的比較，通過排序比較各分類算法的優缺點，各分類器比較結果如表5所示。

表5　分類器比較結果

3　實驗結果

從實驗的排名中可以看出，CE、ICE的正確率明顯高于SB，ICE的正確率并沒有低于CE，但由于ICE修減了搜索空間，理論上顯著提高了速度。

4　結　論

文中基于垂直數據格式、頻繁閉項集的特點，提出了一種將垂直數據格式和頻繁閉項集的模式挖掘應用于選擇性集成方法。利用垂直數據格式的特點，在模式挖掘前對分類器進行篩選，將準確率更高、差異性更大的分類器應用于選擇的過程，利用頻繁閉項集的特點，選擇出有區別能力的模式，使得在確保準確率的前提下提高了速度，并且避免了由于數據庫過大導致FP樹無法實現的問題。

［1］侯勇，鄭雪峰.集成學習算法的研究與應用［J］.計算機工程與應用，2012（34）:17-22.

［2］張春霞，張講社.選擇性集成學習算法綜述［J］.計算機學報，2011（8）:1399-1410.

［3］張翔，周明全，耿國華.Baggin中文文本分類器的改進方法研究［J］.小型微型計算機系統，2010（2）:281-284.

［4］趙強利，蔣艷凰，除明.選擇性集成算法分類與比較［J］.計算機工程與科學,2012（2）:134-138.

［5］趙強利，蔣艷凰，徐明.基于FP-Tree的快速選擇性集成算法［J］.軟件學報，2011（4）:709-721.

［6］李洪波，周莉，張吉贊.用垂直數據格式構建FP增長樹的算法［J］.計算機工程與應用，2009（8）:161-164.

［7］趙強利.基于選擇性集成的在線機器學習關鍵技術研究［D］.北京：國防科學技術大學，2010.

Research of selective ensemble besed on vertical data and closed pattern

WU Chen，YANG Rong-hua
（Jiangsu University of Science and Technology，Zhenjiang 212000，China）

Ensemble learning is an active research in the machine learning field.Ensemble pruning can improve the generalization ability and reduce the cost forecastby selecting the base classifier.Patternmining isa newminingmethod which can transform the problem into pattern in the database transaction.In this paperwe take fulladvantage of patternmining used vertical data structure and closed pattern to propose a forecasting better performance，more efficient selective ensemble classification algorithm.

ensemble pruning；vertical data structure；closed pattern；patternmining；classifier

TN302

A

1674-6236（2016）19-0069-04

2015-10-12稿件編號：201510066

吳陳（1962—），男，湖北天門人，博士，教授。研究方向：人工智能與模式識別，粗糙集理論及應用，數據挖掘與知識發現。