劉寧

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

劉寧

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

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

0 引言

隨著計算機技術特別是互聯(lián)網(wǎng)技術的發(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)。如何快速、準確、方便地從海量的信息庫中獲取感興趣、滿足需要的信息，一直是人們關心的重要課題。在各種復雜的應用環(huán)境下，僅僅通過人工方式對龐大的數(shù)據(jù)進行分析和處理并不現(xiàn)實[1-3]。

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

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

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

本文借鑒協(xié)同學習思想，提出一種兩層結(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 訓練算法

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

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

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

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

第二層結(jié)構(gòu)中，采用基于各分類器分類正確率加權(quán)投票的方法對樣本進行分類, 即加大分類正確率高的分類器的權(quán)值，使其在表決中起較大作用，減小分類正確率低的分類器的權(quán)值，使其在表決中起較小作用。使用分類器C1、C2和C3對訓練集S中的樣本sample類別進行預測，分別比較預測值和實際值（S中樣本的實際類別值已知），得到一個預測正確率，計算各個分類器對應的權(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個分類器對應的權(quán)值如公式（2）：

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

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

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

表1 訓練算法

1.2 測試算法

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

表2 測試算法

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

1.3 算法分析

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

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

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

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)境?；诸惼鞣謩e選用SVM和RBF進行兩次實驗，統(tǒng)計實驗結(jié)果，其中 SVM 采用臺灣大學林智仁等人開發(fā)的libsvm-mat-2.89-3。

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

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

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

表4 分類率提高值 %

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

第二種實驗如表5所示：

表5 分類率提高值 %

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

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

3 總結(jié)

本文借鑒協(xié)同學習思想，提出一種兩層結(jié)構(gòu)、多分類器集成的協(xié)同分類算法，通過雙層條件判斷，分類器協(xié)同投票的方法，實現(xiàn)對數(shù)據(jù)樣本進行分類。實驗表明，算法操作簡單，較容易實現(xiàn)數(shù)據(jù)樣本的分類，性能良好?？梢詫⑵鋺玫綐颖痉诸悺⒉±诸?、入侵檢測、故障檢測等各種分類問題領域，有著廣闊的應用前景。

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

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

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

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

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

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

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

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

[9]李勇,劉戰(zhàn)東,張海軍.不平衡數(shù)據(jù)的集成分類算法綜述[J].計算機應用研究.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].電子學報. 2010,1:185-190.

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

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

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

[15]陸悠,李偉,羅軍舟,等.一種基于選擇性協(xié)同學習的網(wǎng)絡用戶異常行為檢測方法[J].計算機學報, 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

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

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