一種兩層結(jié)構(gòu)集成的協(xié)同分類算法

劉寧

一種兩層結(jié)構(gòu)集成的協(xié)同分類算法

劉寧

為了提高數(shù)據(jù)分類性能，提出一種雙層分類器集成的協(xié)同分類算法CCTL。算法由訓(xùn)練算法和測試算法兩部分組成。算法采用雙層結(jié)構(gòu)集成，使用多條件進行決策判斷。第一層中采用三分類器協(xié)同投票一致策略實現(xiàn)對未知樣本進行分類，第二層中采用基于正確分類率的分類器加權(quán)投票決策實現(xiàn)數(shù)據(jù)分類，提高分類率高的分類器的權(quán)值，減小分類率低的分類器的權(quán)值。最后，使用UCI數(shù)據(jù)集進行實驗，結(jié)果表明CCTL較好地提高了分類率。

協(xié)同學(xué)習(xí)；分類；集成學(xué)習(xí)；機器學(xué)習(xí)；UCI數(shù)據(jù)集

0 引言

隨著計算機技術(shù)特別是互聯(lián)網(wǎng)技術(shù)的發(fā)展，人們獲取信息的能力和渠道得到了極大的拓寬，各行各業(yè)都積累了大量的數(shù)據(jù)。根據(jù)Netcraft Web Server Survey在2012年8月的統(tǒng)計結(jié)果，全球Web站點已經(jīng)超過628,170,204個，而且每天還有數(shù)以萬計的新站點不斷涌現(xiàn)。同時，各個站點都擁有大量的數(shù)據(jù)。海量的數(shù)據(jù)給人類咨詢帶來極大的便利，然而，信息的組織、查找與分析給數(shù)據(jù)處理和分析人員帶了極大的挑戰(zhàn)。如何快速、準(zhǔn)確、方便地從海量的信息庫中獲取感興趣、滿足需要的信息，一直是人們關(guān)心的重要課題。在各種復(fù)雜的應(yīng)用環(huán)境下，僅僅通過人工方式對龐大的數(shù)據(jù)進行分析和處理并不現(xiàn)實[1-3]。

數(shù)據(jù)挖掘是從海量數(shù)據(jù)中通過算法搜索隱藏在其中的、有用的知識的過程，是數(shù)據(jù)庫技術(shù)自然演化的結(jié)果。數(shù)據(jù)挖掘已廣泛應(yīng)用于金融、醫(yī)療和保險等各個行業(yè)，并展現(xiàn)出了其強大的知識發(fā)現(xiàn)能力。在數(shù)據(jù)挖掘的研究與應(yīng)用中，分類算法是一種有監(jiān)督的學(xué)習(xí)算法，通過對已知類別訓(xùn)練集的分析，從中發(fā)現(xiàn)分類規(guī)則，訓(xùn)練并構(gòu)建一個學(xué)習(xí)模型，以此實現(xiàn)對未知的新數(shù)據(jù)的類別的預(yù)測[4-5]。

經(jīng)典分類方法主要包括：決策樹、貝葉斯、人工神經(jīng)網(wǎng)絡(luò)、K近鄰、支持向量機和基于關(guān)聯(lián)規(guī)則的分類等[6-8]。這些單一的經(jīng)典分類算法都在不同的領(lǐng)域取得了成功，具有較好的分類效果。比如決策樹分類算法用于醫(yī)療診斷、金融分析等廣闊領(lǐng)域; 支持向量機分類算法應(yīng)用于模式識別、語音識別和回歸分析等領(lǐng)域; 神經(jīng)網(wǎng)絡(luò)廣泛應(yīng)用在字符識別、分子生物學(xué)、語音識別和人臉識別等領(lǐng)域。但每種分類算法都存在優(yōu)缺點，加上數(shù)據(jù)的多樣性以及實際問題的復(fù)雜性，使到目前為止，沒有哪一種分類算法優(yōu)于其他分類算法[9]。

集成分類方法是一種被廣泛采用的分類方法，通過學(xué)習(xí)多個分類器，將這些分類器進行組合集成，提高分類性能。它基于這樣一個思想：對于一個復(fù)雜任務(wù)來講，將多個專家的判斷進行適當(dāng)?shù)木C合所得出的判斷，要比其中任何一個專家單獨的判斷要好。Wang[10]等從理論上證明了集成分類器要優(yōu)于單個分類器。在集成分類器方法中，基于權(quán)重的集成分類器被普遍認(rèn)為是具有較高分類精度的方法。文獻[11]和[12]將集成分類應(yīng)用到不平衡數(shù)據(jù)分類領(lǐng)域，實現(xiàn)對信息不均衡數(shù)據(jù)進行分類，取得了較好的分類效果。文獻[13]和[14]將集成分類應(yīng)用到半監(jiān)督學(xué)習(xí)領(lǐng)域，實現(xiàn)對不充分信息數(shù)據(jù)的分類，也取得了較好的實驗效果。文獻[15]將集成學(xué)習(xí)應(yīng)用到網(wǎng)絡(luò)數(shù)據(jù)分類中，有效地提高分類性能。

本文借鑒協(xié)同學(xué)習(xí)思想，提出一種兩層結(jié)構(gòu)集成的協(xié)同分類算法CCTL（Collaborative classification algorithm based two layers structure integration），通過雙層條件判斷，使用多個分類器集成、協(xié)同投票的方法，挖掘待分類樣本的類別信息，實現(xiàn)對數(shù)據(jù)樣本進行分類，降低分類誤差，提高正確分類率。最后，通過 UCI數(shù)據(jù)集進行實驗，驗證算法的有效性。

1 兩層分類器集成的數(shù)據(jù)分類算法

1.1 訓(xùn)練算法

兩層分類器集成的數(shù)據(jù)分類算法CCTL結(jié)構(gòu)如圖1所示：

圖1 CCTL的結(jié)構(gòu)

訓(xùn)練集包括訓(xùn)練集L和訓(xùn)練集S，訓(xùn)練集L用于訓(xùn)練分類器，訓(xùn)練集S用于確定每個分類器的分類正確率，計算單個分類器的權(quán)值。采用隨機抽樣方法對 L進行自助抽樣，產(chǎn)生3個差異性較大的子集L1，L2和L3作為訓(xùn)練集，分別訓(xùn)練生成3個分類器C1、C2和C3。

第一層結(jié)構(gòu)中，使用單分類器C1、C2和C3對訓(xùn)練集S中的樣本sample進行預(yù)測，假設(shè)樣本sample對應(yīng)的預(yù)測標(biāo)記分別為y1、y2和y3，3個分類器采用決策函數(shù)1進行投票決策。決策函數(shù)1采用3個分類預(yù)測一致的方法進行類別決策，即如果3個分類器預(yù)測結(jié)果一致，將該類別作為樣本sample的分類預(yù)測類別。接著，使用判斷條件1對分類結(jié)果進行判斷，對于滿足判斷條件1的分類類別，將其作為sample的最終類別。判斷條件1表示決策函數(shù)1的預(yù)測類別和樣本sample的實際標(biāo)記類別值一致（sample的實際類別已知）。對于不滿足判斷條件1的樣本sample進入第二層結(jié)構(gòu)。

第二層結(jié)構(gòu)中，采用基于各分類器分類正確率加權(quán)投票的方法對樣本進行分類, 即加大分類正確率高的分類器的權(quán)值，使其在表決中起較大作用，減小分類正確率低的分類器的權(quán)值，使其在表決中起較小作用。使用分類器C1、C2和C3對訓(xùn)練集S中的樣本sample類別進行預(yù)測，分別比較預(yù)測值和實際值（S中樣本的實際類別值已知），得到一個預(yù)測正確率，計算各個分類器對應(yīng)的權(quán)值w1、w2和w3，權(quán)值計算公式如式（1）所示。使用決策函數(shù) 2，通過三個分類器的線性組合，計算基于正確率的加權(quán)值，實現(xiàn)對樣本sample類別的最終類別決策。其中決策函數(shù)2的計算方法如公式（3）所示，公式（3）中的 f(x)由公式（2）計算得到如公式（1）：

式中，acci表示第i個分類器的正確分類率， wi為第i個分類器對應(yīng)的權(quán)值如公式（2）：

式中，wi為第i個分類器對應(yīng)的權(quán)值，yi為第i個分類器的預(yù)測類別，f(x)表示集成分類器的預(yù)測值的線性組合，i=1，…N取值為3如公式（3）：

式中，f(x)表示集成分類器的預(yù)測值的線性組合，y為集成分類器的預(yù)測類別。

算法反復(fù)迭代，直到訓(xùn)練集 L為空。最后，使用訓(xùn)練生成的分類器CCTL實現(xiàn)對測試集樣本的分類。具體算法如表1所示：

表1 訓(xùn)練算法

1.2 測試算法

測試算法主要使用表1中生成的分類器CCTL，對測試集中測試樣本的類別進行預(yù)測，通過比較預(yù)測類別和實際類別樣本，并計算正確分類率。具體操作如表2所示：

表2 測試算法

其中，正確分類率的計算公式如公式（4）所示，通過表2算法對測試集的樣本特征值進行預(yù)測，將預(yù)測類別標(biāo)記與測試集的樣本真實類別標(biāo)記進行比較，統(tǒng)計預(yù)測正確的分類樣本數(shù)目，計算分類算法的正確分類率如公式（4）：

1.3 算法分析

本算法中，采用二層結(jié)構(gòu)的主要目的是提高分類器的正確分類率和分類效率。

與單分類器算法相比，本算法CCTL通過多個分類器協(xié)同實現(xiàn)數(shù)據(jù)的分類，能有效提高正確分類率。第一，單分類器只是通過一個分類器實現(xiàn)對數(shù)據(jù)的分類，CCTL算法第一層中當(dāng)3個分類器投票一致時，才使用一致的投票實現(xiàn)對分類類別進行決策,明顯提高了算法的正確分類率；第二，CCTL算法第二層中，通過3個分類器進行加權(quán)投票，增加分類率高的分類器的決策權(quán)，有利于減小分類誤差，提高分類器的正確分類率。所以，CCTL分類性能優(yōu)于單分類器。

與集成分類器算法相比，本算法CCTL能提高效率。當(dāng)3個分類器對樣本的預(yù)測一致時，算法不需要進入第二層。

2 實驗和結(jié)果分析

實驗平臺選用PC，其配置信息如下：AMD FX(tm)-4300 Quad-Core Processor 3.82GHz CPU、3.12GB內(nèi)存。軟件環(huán)境為：安裝Windows XP 操作系統(tǒng)、安裝MATLAB R2009b 編程環(huán)境。基分類器分別選用SVM和RBF進行兩次實驗，統(tǒng)計實驗結(jié)果，其中 SVM 采用臺灣大學(xué)林智仁等人開發(fā)的libsvm-mat-2.89-3。

實驗采用UCI數(shù)據(jù)（http://archive.ics.uci.edu/ml/）中常用的4個數(shù)據(jù)集，如表3所示：

表3 實驗數(shù)據(jù)集

對于表3所選取的樣本，將訓(xùn)練集和測試集的樣本數(shù)目比例設(shè)為1:2。訓(xùn)練集分為兩部分即訓(xùn)練集L和訓(xùn)練集S，其中L和S的數(shù)目比例為設(shè)2:1。訓(xùn)練集中的樣本都是有標(biāo)記樣本數(shù)據(jù)，使用這些有標(biāo)記樣本訓(xùn)練生成分類器，使用新生成的分類器CCTL在測試集上進行分類測試，統(tǒng)計正確分類率。其中，在這里，為了方便統(tǒng)計分類結(jié)果，測試集中的樣本也是有標(biāo)記樣本，作為計算分類器的正確分類率時使用。根據(jù)選用的基分類器不同，實驗分為兩種情況進行，實驗結(jié)果如表4和表5所示。表4表示第一種實驗，即使用SVM作為基分類器時，SVM和CCTL在測試集中的正確分類率。其中，SVM列表示使用訓(xùn)練集訓(xùn)練SVM后，在測試集中的正確分類率，CCTL列表示使用訓(xùn)練集訓(xùn)練CCTL后，在測試集上的正確分類率。如表4所示：

表4 分類率提高值 %

從表4可以看出，CCTL分類算法能較好提高正確分類率，比僅僅使用單分類器SVM進行訓(xùn)練測試，正確分類率提高了6.41%。

第二種實驗如表5所示：

表5 分類率提高值 %

使用RBF作為基分類器時，RBF和CCTL在測試集上正確分類器。其中，RBF列表示使用訓(xùn)練集訓(xùn)練RBF后，在測試集中的正確分類率，CCTL列表示使用訓(xùn)練集訓(xùn)練CCTL后，在測試集上的正確分類率。從表5可以看出，CCTL分類算法能較好提高正確分類率，比僅僅使用單分類器RBF進行訓(xùn)練測試，正確分類率提高了4.83%。從實驗結(jié)果可以看出，文中提出了集成分類器算法CCTL操作簡單，具有較好的分類性能，能較好地提高測試數(shù)據(jù)的正確分類率。

通過多次實驗表明，該算法收斂于多分類器集成的分類算法的分類結(jié)果。由于該算法采用兩層結(jié)構(gòu)，若3個分類器預(yù)測一致時，只執(zhí)行第一層結(jié)構(gòu)，不需要進入第二層結(jié)構(gòu)；若3個分類器預(yù)測不一致時，才進入第二層結(jié)構(gòu)。所以，該算法與單分類器算法相比，提高了分類率；與集成分類算法相比，提高了分類效率。

3 總結(jié)

本文借鑒協(xié)同學(xué)習(xí)思想，提出一種兩層結(jié)構(gòu)、多分類器集成的協(xié)同分類算法，通過雙層條件判斷，分類器協(xié)同投票的方法，實現(xiàn)對數(shù)據(jù)樣本進行分類。實驗表明，算法操作簡單，較容易實現(xiàn)數(shù)據(jù)樣本的分類，性能良好。可以將其應(yīng)用到樣本分類、病例分類、入侵檢測、故障檢測等各種分類問題領(lǐng)域，有著廣闊的應(yīng)用前景。

[1]Vapnik V. The nature of statistical learning theory[M]. springer, 2000.

[2]張晨光,張燕.半監(jiān)督學(xué)習(xí)[M].北京:中國農(nóng)業(yè)科學(xué)技術(shù)出版社,2013.

[3]薛貞霞.支持向量機及半監(jiān)督學(xué)習(xí)中若干問題的研究[D].西安:西安電子科技大學(xué), 2009.

[4]李玲俐.數(shù)據(jù)挖掘中分類算法綜述[J].重慶師范大學(xué)學(xué)報(自然科學(xué)版).2011,28(4):44-47.

[5]劉大有,陳慧靈,齊紅,等.時空數(shù)據(jù)挖掘研究進展[J].計算機研究與發(fā)展, 2013, 50(2): 225-239.

[6]宋全有,王雪瑞,龔志恒.基于共有 GP-LV M 和改進型SVM的數(shù)據(jù)分類算法[J].計算機工程與設(shè)計,2014,35(7): 2412-2414.

[7]李兵,董俊,劉鵬遠(yuǎn),等.模糊格構(gòu)造型形態(tài)神經(jīng)網(wǎng)絡(luò)[J].電子學(xué)報, 2014, 42(2): 319-327.

[8]馮建,邱菀華.一種基于信息熵的金融數(shù)據(jù)神經(jīng)網(wǎng)絡(luò)分類方法[J].控制與決策,2012,27(2):211-215.

[9]李勇,劉戰(zhàn)東,張海軍.不平衡數(shù)據(jù)的集成分類算法綜述[J].計算機應(yīng)用研究.2014,31(5):1287-1291.

[10]H Wang,et al.Mining concept-drifting data streams using ensemble classifiers[A]. Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York: ACM Press,2003.226-235.

[11]歐陽震諍,羅建書,胡東敏,等.一種不平衡數(shù)據(jù)流集成分類模型[J].電子學(xué)報. 2010,1:185-190.

[12]于重重,商利利,譚勵,等.半監(jiān)督學(xué)習(xí)在不平衡樣本集分類中的應(yīng)用研究[J].計算機應(yīng)用研究, 2013,30(4):1085-1089.

[13]趙建華,李偉華.一種協(xié)同半監(jiān)督分類算法 Co-S3OM[J].計算機應(yīng)用研究,2013,30(11):3237-3239.

[14]于重重,商利利,譚勵,等.一種增強差異性的半監(jiān)督協(xié)同分類算法[J].電子學(xué)報,2013,41(1):35-41.

[15]陸悠,李偉,羅軍舟,等.一種基于選擇性協(xié)同學(xué)習(xí)的網(wǎng)絡(luò)用戶異常行為檢測方法[J].計算機學(xué)報, 2014, 37(1):28-40.

A Collaborative Classification Algorithm Based Two Layers Structure Integration

Liu Ning
(School of economics and management, Shangluo University, Shangluo 726000, China)

In order to improve the performance of data classifier, a kind of collaborative classification algorithm CCTL based on two layers structure integration was proposed. The algorithm was composed of training algorithm and test algorithm. CCTL adopted an integration of double layer structure, using multi condition to make a judgment. In the first layer, collaborative voting strategy using three classifiers was to realize the classification of unknown samples. In the second layer, the weighted voting decision strategy based on correct classification rate was used to realize the data classification. The purpose was to improve the weights of classification with higher classification rate and to reduce the weight of classification with lower rate. Finally, experiment was carried out by the UCI data set. The results showed that CCTL could improve the classification rate.

Collaborative Learning; Classification; Ensemble Learning; Machine Learning; UCI Dataset

TP181

A

2014.12.29)

1007-757X(2015)05-0033-03

商洛學(xué)院科研項目資助（項目編號:14SKY006）

劉 寧（1981-），女，陜西商洛，商洛學(xué)院，經(jīng)濟與管理學(xué)院，講師，碩士，研究方向：機器學(xué)習(xí)，商洛，726000