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

吳陳，楊镕華

（江蘇科技大學(xué) 江蘇 鎮(zhèn)江212000）

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

吳陳，楊镕華

（江蘇科技大學(xué) 江蘇 鎮(zhèn)江212000）

集成學(xué)習(xí)是現(xiàn)今機(jī)器學(xué)習(xí)領(lǐng)域研究的熱點(diǎn)問題，選擇性集成通過對基分類器進(jìn)行選擇來提高集成分類器的泛化能力，降低預(yù)測開銷。模式挖掘是一種將問題轉(zhuǎn)化為事務(wù)數(shù)據(jù)庫中模式的全新挖掘策略。本文將垂直數(shù)據(jù)格式頻繁閉項集的模式挖掘方法應(yīng)用于分類器的選擇過程，利用垂直數(shù)據(jù)結(jié)構(gòu)、頻繁閉項集及模式挖掘方法的優(yōu)勢，提出一種預(yù)測性能更好、更加高效的選擇性集成分類算法。

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

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

1　研究現(xiàn)狀

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

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

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

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

2.1算法思想

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

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

2.2ICPM-EP算法模型

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

圖1　ICPM-EP算法模型

算法實(shí)現(xiàn)描述如下：

偽代碼：

2.3算法實(shí)現(xiàn)過程

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

下面將從獲取垂直數(shù)據(jù)格式事務(wù)表，精簡事務(wù)表，F(xiàn)P-tree的構(gòu)建以及分類器的選擇4個步驟進(jìn)行詳細(xì)介紹。

2.3.1獲取垂直數(shù)據(jù)格式事務(wù)表

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

假設(shè)L=10，對應(yīng)的分類器標(biāo)號分別為C1，C2，…，C10，校驗樣本集VS中共有12個樣本，標(biāo)號分別為S1，S2，…，S12，可得垂直數(shù)據(jù)格式預(yù)測結(jié)果表如表1所示。

表1　垂直數(shù)據(jù)格式預(yù)測結(jié)果表

2.3.2精簡事務(wù)表

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

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

2.3.3構(gòu)建FP樹

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

表2　垂直數(shù)據(jù)投影事務(wù)的過程表

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

圖2　掃描數(shù)據(jù)庫一次后垂直項目頭表圖

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

2.3.4選擇基分類器

根據(jù)構(gòu)造的FP樹進(jìn)行基分類器的選擇采用貪婪方法。主要分為以下幾步：

步驟一：初始化結(jié)果集，PR.set=null；PR.correct=0，其中PR.set為入選的基分類器的集合，PR.correct為對應(yīng)基分類器集合對事務(wù)分類正確的數(shù)目。

步驟二：創(chuàng)建Path-table表，F(xiàn)P樹按照從左到右的順序?qū)母?jié)點(diǎn)到葉子節(jié)點(diǎn)出現(xiàn)的分類器及該路徑的count值記錄在表中。該表的每一行代表FP樹的一條路徑。原始Pathtable表如表3所示。

表3　原始Path-table表

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

當(dāng)count［i］+|PR.set|>K（K為選擇的分類器的個數(shù)）時，說明選擇K個分類器無法滿足多數(shù)投票法的規(guī)則，則將該行從表中刪除重復(fù)該步驟，直到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表

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

實(shí)驗比較：

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

實(shí)驗所采用的數(shù)據(jù)集為 KEEL-dataset中的 Text Classification data sets。

實(shí)驗中，利用weka平臺，采用java語言進(jìn)行編程實(shí)現(xiàn)，采用5次交叉驗證的方法，訓(xùn)練生成5個BP神經(jīng)網(wǎng)絡(luò)、5個C4.5決策樹、5個樸素貝葉斯，5個SVM，在多數(shù)據(jù)集上比較多種實(shí)驗結(jié)果，結(jié)果用均值表示。為避免單個數(shù)據(jù)集對結(jié)果的影響較大，將對精確度數(shù)值的比較轉(zhuǎn)換為對排名的比較，通過排序比較各分類算法的優(yōu)缺點(diǎn)，各分類器比較結(jié)果如表5所示。

表5　分類器比較結(jié)果

3　實(shí)驗結(jié)果

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

4　結(jié)　論

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

［1］侯勇，鄭雪峰.集成學(xué)習(xí)算法的研究與應(yīng)用［J］.計算機(jī)工程與應(yīng)用，2012（34）:17-22.

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

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

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

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

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

［7］趙強(qiáng)利.基于選擇性集成的在線機(jī)器學(xué)習(xí)關(guān)鍵技術(shù)研究［D］.北京：國防科學(xué)技術(shù)大學(xué)，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—），男，湖北天門人，博士，教授。研究方向：人工智能與模式識別，粗糙集理論及應(yīng)用，數(shù)據(jù)挖掘與知識發(fā)現(xiàn)。