劉寧

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

劉寧

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

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

0 引言

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

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

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

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

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

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

1.1 訓(xùn)練算法

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

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

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

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

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

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

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

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

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

表1 訓(xùn)練算法

1.2 測(cè)試算法

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

表2 測(cè)試算法

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

1.3 算法分析

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

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

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

2 實(shí)驗(yàn)和結(jié)果分析

實(shí)驗(yàn)平臺(tái)選用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)境?；诸?lèi)器分別選用SVM和RBF進(jìn)行兩次實(shí)驗(yàn)，統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果，其中 SVM 采用臺(tái)灣大學(xué)林智仁等人開(kāi)發(fā)的libsvm-mat-2.89-3。

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

表3 實(shí)驗(yàn)數(shù)據(jù)集

對(duì)于表3所選取的樣本，將訓(xùn)練集和測(cè)試集的樣本數(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)練生成分類(lèi)器，使用新生成的分類(lèi)器CCTL在測(cè)試集上進(jìn)行分類(lèi)測(cè)試，統(tǒng)計(jì)正確分類(lèi)率。其中，在這里，為了方便統(tǒng)計(jì)分類(lèi)結(jié)果，測(cè)試集中的樣本也是有標(biāo)記樣本，作為計(jì)算分類(lèi)器的正確分類(lèi)率時(shí)使用。根據(jù)選用的基分類(lèi)器不同，實(shí)驗(yàn)分為兩種情況進(jìn)行，實(shí)驗(yàn)結(jié)果如表4和表5所示。表4表示第一種實(shí)驗(yàn)，即使用SVM作為基分類(lèi)器時(shí)，SVM和CCTL在測(cè)試集中的正確分類(lèi)率。其中，SVM列表示使用訓(xùn)練集訓(xùn)練SVM后，在測(cè)試集中的正確分類(lèi)率，CCTL列表示使用訓(xùn)練集訓(xùn)練CCTL后，在測(cè)試集上的正確分類(lèi)率。如表4所示：

表4 分類(lèi)率提高值 %

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

第二種實(shí)驗(yàn)如表5所示：

表5 分類(lèi)率提高值 %

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

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

3 總結(jié)

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

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

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

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

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

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

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

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

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

[9]李勇,劉戰(zhàn)東,張海軍.不平衡數(shù)據(jù)的集成分類(lèi)算法綜述[J].計(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]歐陽(yáng)震諍,羅建書(shū),胡東敏,等.一種不平衡數(shù)據(jù)流集成分類(lèi)模型[J].電子學(xué)報(bào). 2010,1:185-190.

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

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

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

[15]陸悠,李偉,羅軍舟,等.一種基于選擇性協(xié)同學(xué)習(xí)的網(wǎng)絡(luò)用戶(hù)異常行為檢測(cè)方法[J].計(jì)算機(jī)學(xué)報(bào), 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é)院科研項(xiàng)目資助（項(xiàng)目編號(hào):14SKY006）

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