一種基于混合度的層次粒度SVM算法

程鳳偉,郭虎升

(1.太原學(xué)院 計(jì)算機(jī)工程系,山西 太原 030032;2.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006)

一種基于混合度的層次粒度SVM算法

程鳳偉1,郭虎升2*

(1.太原學(xué)院 計(jì)算機(jī)工程系,山西 太原 030032;2.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006)

隨著現(xiàn)實(shí)生活中數(shù)據(jù)集規(guī)模的不斷增大,設(shè)計(jì)有效的分類(lèi)算法勢(shì)在必行。支持向量機(jī)(Support vector machine,SVM)是一種公認(rèn)的性能較好的分類(lèi)算法，目前一些SVM算法是針對(duì)減少支持向量的數(shù)目來(lái)提高分類(lèi)的效率。文章提出一種基于混合度的層次粒度支持向量機(jī)算法(Hierarchical Granular Support Vector Machine Algorithm based on Mixed,MHG-SVM),利用混合度對(duì)已有的層次粒度SVM分類(lèi)算法進(jìn)行了改進(jìn),該算法通過(guò)定義一個(gè)數(shù)據(jù)置信度和一個(gè)粒度參數(shù)挑選出重要的分類(lèi)信息。從實(shí)驗(yàn)結(jié)果可以看出,提出的算法在處理大規(guī)模數(shù)據(jù)集方面,保持了較高的分類(lèi)精度,而且支持向量機(jī)的學(xué)習(xí)和分類(lèi)速度也取得了大幅度提高。

支持向量; 分類(lèi)精度;混合度;置信度;大規(guī)模數(shù)據(jù)集

0 引言

支持向量機(jī)是一種通用有效的學(xué)習(xí)方法,在處理小規(guī)模二分類(lèi)問(wèn)題時(shí)表現(xiàn)出較好的性能,但在處理大規(guī)模數(shù)據(jù)集時(shí),效率低下[1-2]。2004年Tang提出了一種新的機(jī)器學(xué)習(xí)模型[3-4]——粒度支持向量機(jī)(Granular Support Vector Machine, GSVM),它以粒度計(jì)算理論[5-7]和統(tǒng)計(jì)學(xué)習(xí)理論為基礎(chǔ),有效地克服了傳統(tǒng)支持向量機(jī)在處理大規(guī)模數(shù)據(jù)集時(shí)訓(xùn)練效率低下的問(wèn)題,而且也可保持較高的泛化性能[8-9]。典型的GSVM 模型主要有:基于關(guān)聯(lián)規(guī)則的GSVM[10]、基于聚類(lèi)的GSVM[11-12],此外,也有不少的學(xué)者研究基于粗糙集[13]、決策樹(shù)[14]、商空間[15]以及神經(jīng)網(wǎng)絡(luò)[16]的GSVM 學(xué)習(xí)方法。

本文提出的基于混合度的層次粒度SVM算法不同于傳統(tǒng)層次粒度SVM算法,第一,MHG-SVM算法不建立兩棵層次樹(shù),只構(gòu)建一個(gè);第二,MHG-SVM算法從樹(shù)的頂層開(kāi)始反復(fù)訓(xùn)練支持向量節(jié)點(diǎn),因?yàn)樵绞菢?shù)的頂層,樹(shù)的節(jié)點(diǎn)覆蓋越大的樣本空間,很有可能發(fā)現(xiàn)節(jié)點(diǎn)是混合節(jié)點(diǎn)。對(duì)于混合節(jié)點(diǎn),用k-means聚類(lèi)算法,對(duì)它們進(jìn)行繼續(xù)粒劃,保留純節(jié)點(diǎn),刪除無(wú)效節(jié)點(diǎn),采用此層次粒劃模型對(duì)樣本集進(jìn)行篩選,提取重要的分類(lèi)信息加入到訓(xùn)練集進(jìn)行訓(xùn)練,獲得了較好的泛化能力。

1 基于混合度的層次粒度SVM模型

傳統(tǒng)層次粒度SVM 模型建立兩棵層次樹(shù),分別對(duì)正類(lèi)樣本和負(fù)類(lèi)樣本進(jìn)行操作,一棵樹(shù)上的節(jié)點(diǎn)只包含一類(lèi)分類(lèi)信息,而采用這種傳統(tǒng)層次粒度GVM模型大多在原空間構(gòu)建層次結(jié)構(gòu),而在核空間進(jìn)行SVM訓(xùn)練,會(huì)存在操作前后模型誤差問(wèn)題,而且它的粒劃分過(guò)程是靜態(tài)的,每層粒劃參數(shù)需要由用戶(hù)給出,而不能根據(jù)自身問(wèn)題實(shí)現(xiàn)動(dòng)態(tài)控制。本文提出的MHG-SVM算法,采用動(dòng)態(tài)層次粒劃?rùn)C(jī)制,首先把整個(gè)數(shù)據(jù)集作為樹(shù)的根節(jié)點(diǎn),進(jìn)行混合粒劃分,粒劃后的子粒作為子節(jié)點(diǎn),并計(jì)算子節(jié)點(diǎn)(子粒)的密度與混合度,根據(jù)密度和混合度將子節(jié)點(diǎn)分為三部分:混合節(jié)點(diǎn)、純節(jié)點(diǎn)、無(wú)效節(jié)點(diǎn)。對(duì)于混合節(jié)點(diǎn),由于其含有大量的分類(lèi)信息,需要細(xì)化,將其作為父節(jié)點(diǎn)進(jìn)行下一層次的粒劃分,劃分出的粒作為子節(jié)點(diǎn),重復(fù)此過(guò)程,直到達(dá)到一定的純度,不再分裂節(jié)點(diǎn)。對(duì)于純節(jié)點(diǎn),由于只包含正類(lèi)(或負(fù)類(lèi))的樣本,含有較少的分類(lèi)信息,因此將其作為葉子節(jié)點(diǎn),不再對(duì)其進(jìn)行粒劃分。對(duì)于無(wú)效節(jié)點(diǎn),由于其含有較少的樣本,直接刪除。最后,提取樹(shù)中所有葉子節(jié)點(diǎn)上粒的代表點(diǎn)加入到訓(xùn)練集,進(jìn)行SVM訓(xùn)練。這種基于混合度的層次粒度SVM算法,通過(guò)度量節(jié)點(diǎn)上粒的混合度,壓縮純粒,縮減了訓(xùn)練集,通過(guò)度量粒的混合度和粒密度,細(xì)化信息粒,從而選取更多的支持向量擴(kuò)充到訓(xùn)練集,使得訓(xùn)練集樣本的分布更符合原始數(shù)據(jù)集樣本的分布,這樣訓(xùn)練得出的超平面更加準(zhǔn)確。圖1給出了基于混合度的層次粒度SVM粒劃分的示意圖。 假設(shè)經(jīng)過(guò)對(duì)整個(gè)數(shù)據(jù)集初次粒劃分,得到A、B、C、D、E、F六個(gè)粒,從圖中可以看出,A,B為混合粒,需要進(jìn)行再次粒劃分,挑選更多的分類(lèi)信息加入到訓(xùn)練集;C、D為含有少量異類(lèi)樣本的粒,由于其混合度較低常被看作純粒處理,只需取C、D粒中代表點(diǎn)(粒中心)加入訓(xùn)練集即可;E、F是由分布離群的噪聲樣本在粒劃過(guò)程中單獨(dú)構(gòu)成一個(gè)粒,稱(chēng)為無(wú)效粒,這種粒往往由于密度太低而被安全刪除,這樣就會(huì)減少噪聲對(duì)分布問(wèn)題的影響。

Fig.1 Process of granular division圖1 粒劃分示意圖

MHG-SVM模型在建樹(shù)過(guò)程中需要區(qū)分三種節(jié)點(diǎn):混合節(jié)點(diǎn)、純節(jié)點(diǎn)和無(wú)效節(jié)點(diǎn)。在本文中,無(wú)效節(jié)點(diǎn)由粒的支持度(粒密度)進(jìn)行篩選,混合節(jié)點(diǎn)和純節(jié)點(diǎn)由混合度進(jìn)行篩選區(qū)分。

用Mix(Hk)表示粒Hk的混合度,它反應(yīng)粒中正負(fù)樣本的混合程度,從式(1)可以看出,Mix(Hk)∈[0,1],Mix(Hk)值越大,表示粒Hk的混合度越高,含有的分類(lèi)信息越多;Mix(Hk)值越小,表示粒Hk的混合度越低,粒越純,含有的分類(lèi)信息越少;當(dāng)Mix(Hk)=0時(shí)表示粒Hk是純粒。其定義如下:

(1)

粒中心反映一個(gè)粒的位置,它作為粒中代表點(diǎn)參與訓(xùn)練,其定義如下:

(2)

粒的支持度(粒密度)反映一個(gè)粒的重要程度,決定一個(gè)粒是參與訓(xùn)練還是被刪除。其定義如下:

(3)

MHG?SVM學(xué)習(xí)算法輸入：訓(xùn)練集T={X，Y}={(xi，yi)}li=1，測(cè)試集T′={(xj，yj)}l′j=1，支持度界值 D，混合度界值Mix，粒劃參數(shù)k，核函數(shù)K，正則參數(shù)C。Step1：對(duì)訓(xùn)練集進(jìn)行粒劃，得到一系列粒H={Hk}lk=1，其中Hk為粒劃分后得到的一個(gè)粒。Step2：設(shè)置混合度界值Mix和支持度界值 D。Step3：由公式(1)(2)(3)計(jì)算每個(gè)粒的混合度Mix(Hk)和支持度DHk，根據(jù)混合度界值Mix和支持度界值 D將由Step1得到的一系列粒{Hk}lk=1分為混合粒、純粒和無(wú)效粒。Step4：從粒集H中刪除無(wú)效粒，對(duì)于混合粒，根據(jù)粒劃參數(shù)k進(jìn)行再次粒劃，用粒劃后得到的粒代替原來(lái)的粒放到粒集H中，然后轉(zhuǎn)入Step2，直到所有粒都不滿(mǎn)足粒劃條件，即粒集H中所有粒都是純粒。Step5：取粒集H中的所有粒(純粒)的中心作為訓(xùn)練數(shù)據(jù)進(jìn)行訓(xùn)練，得到分類(lèi)超平面。Step6：返回分類(lèi)超平面f(x)=sgn(W?φ(x)+b)。

就傳統(tǒng)的SVM而言,由于所有的樣本都要加入訓(xùn)練集進(jìn)行訓(xùn)練,因此,訓(xùn)練的空間復(fù)雜度和時(shí)間復(fù)雜度都非常高,而本文采用的MHG-SVM算法采用層次粒劃分模型,細(xì)化重要的分類(lèi)信息,刪除噪聲粒,很大程度上縮減了訓(xùn)練集的規(guī)模,提高了分類(lèi)的速度。

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

對(duì)于傳統(tǒng)的GSVM算法而言,最終粒劃分的個(gè)數(shù)由初始粒劃參數(shù)決定,而MHG-SVM算法根據(jù)每個(gè)粒的混合度和支持度對(duì)數(shù)據(jù)集進(jìn)行動(dòng)態(tài)粒劃分,因此,預(yù)測(cè)初始粒劃參數(shù)對(duì)MHG-SVM算法分類(lèi)正確率的影響相對(duì)較小。為了進(jìn)一步驗(yàn)證初始粒劃參數(shù)K對(duì)MHG-SVM算法影響,在標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)分析。圖2給出了MHG-SVM與GSVM算法測(cè)試結(jié)果的比較。

從實(shí)驗(yàn)結(jié)果可以看出,對(duì)于GSVM算法,影響算法表現(xiàn)的主要因素是初始粒劃參數(shù)的設(shè)定,隨著粒劃參數(shù)K的增加,算法的正確率逐漸升高,對(duì)于MHG-SVM算法,在所有的數(shù)據(jù)集上,正確率都高于GSVM,且正確率并沒(méi)有隨著初始粒劃參數(shù)K的增加呈現(xiàn)明顯變化趨勢(shì),正確率很平穩(wěn),幾乎不受初始粒劃參數(shù)的影響。

表1 實(shí)驗(yàn)采用的數(shù)據(jù)集Table 1 Datasets used in the experiment

Fig.2 Result comparison between MHG-SVM and GSVM圖2 MHG-SVM與GSVM算法測(cè)試結(jié)果的比較

為了進(jìn)一步研究MHG-SVM的性能,本文在幾個(gè)數(shù)據(jù)集上衡量了初始粒劃參數(shù)取值不同的情況下最終參加SVM訓(xùn)練的粒的個(gè)數(shù)。圖3給出了粒劃程度的詳細(xì)信息。

Fig.3 Final number of granularity for MHG-SVM algorithm圖3 采用MHG-SVM算法最終獲得粒的個(gè)數(shù)

從圖3容易看出,對(duì)于German、Image、Diabetis、Heart、Breast-cancer數(shù)據(jù)集,采用MHG-SVM算法后,盡管初始粒劃參數(shù)的值不同,但最終得到支持向量的數(shù)目基本一致;對(duì)于Throid數(shù)據(jù)集,支持向量數(shù)目受初始粒劃參數(shù)影響,原因在于Throid數(shù)據(jù)集本身比較小,粒劃后得到的粒的個(gè)數(shù)少,所以才會(huì)接近初始粒劃參數(shù)。因此,MHG-SVM算法采用混合度層次粒劃分機(jī)制使得訓(xùn)練結(jié)果比較穩(wěn)定,具有較好的魯棒性。

表2是MHG-SVM、DGSVM、GSVM和傳統(tǒng)SVM測(cè)試結(jié)果的比較,初始粒劃參數(shù)分別取10,50和200。從表中可以看出,與傳統(tǒng)SVM算法相比,另外三個(gè)基于GSVM算法的訓(xùn)練效率都提高100倍以上,盡管SVM的泛化性能在所有方法中最好,但其訓(xùn)練時(shí)間太長(zhǎng),無(wú)法進(jìn)行高效學(xué)習(xí)。MHG-SVM算法與GSVM算法相比,運(yùn)算速率雖有所下降,但運(yùn)算正確率有一定提升。MHG-SVM算法與DSVM算法相比,從整體上看,MHG-SVM算法的運(yùn)算效率和正確率都有所提高。

表2 四種方法測(cè)試結(jié)果的比較Table 2 Comparison of four kinds of test results

上述實(shí)驗(yàn)結(jié)果表明,基于MHG-SVM算法能有效提取支持向量信息,減小模型誤差,可以獲得較好的泛化性能,而且采用粒支持度進(jìn)行過(guò)濾,剔除一些不重要的粒,保證樣本處理與訓(xùn)練分布的一致性；另一方面,采用混合度,提取含有重要信息的混合粒;然后再通過(guò)采用動(dòng)態(tài)粒劃分機(jī)制,對(duì)初始超平面進(jìn)行更新,更進(jìn)一步地提高了MHG-SVM的泛化性能。

3 結(jié)束語(yǔ)

本文提出了一個(gè)新的處理大規(guī)模數(shù)據(jù)集的混合度MHG-SVM算法,由于傳統(tǒng)的GSVM算法在處理大數(shù)據(jù)集的分類(lèi)問(wèn)題時(shí)泛化能力有限,MHG-SVM算法通過(guò)設(shè)置混合度和支持度界值,可以有效地挑選出重要的分類(lèi)信息,從而克服了GSVM算法在處理分類(lèi)問(wèn)題時(shí)運(yùn)算精度低下的問(wèn)題。未來(lái)的工作中,考慮將MHG-SVM算法擴(kuò)展到多分類(lèi)分布不均勻的數(shù)據(jù)分類(lèi)問(wèn)題的處理當(dāng)中,此外,可將本文的算法應(yīng)用到網(wǎng)頁(yè)分類(lèi)疾病監(jiān)測(cè)等大規(guī)模分布不均勻的實(shí)際問(wèn)題當(dāng)中。

[1] James M,Mihael C,Brad B,etal.Big Data:The Next Frontier for Innovation,Competition,and Productivity[R].Mckinsey & Company,2011,05.[http:∥www.mckinsey.com/insights/business-technology/big-data-the-next-frontier-for-innovation].DOI:https:∥doi.org/10.1586/17512433.2014.905201.

[2] Tang yukun,Jin bo,Zhang yanqing.Granular Support Vector Machines for Medical Binary Classification Problems[J].ComputationalIntelligenceinBioinformaticsandComputationalBiology,2004:73-78.

[3] Wang wenjian,Guo husheng,Jia yuanfeng,etal.Granular Support Vector Machine based on Mixed Measure[J].Neurocomputing,2013,101(4):116-128.DOI:https:∥doi.org/10.1010/j.neucom.2012.08.006.

[4] Yao Y Y.Perspectives of Granular Computing[C]∥Proceedings of 2005 IEEE International Conference on Granular Computing,2005,1:85-90.DOI:https:∥doi.org/10.1109/wi.2007.159.

[5] Xu C F,Wang J L.An Efficient Incremental Algorithm for Frequent Itemsets Mining in Distorted Databases with Granular Computing[C]∥International Conference on Web Intelligence,2006,37:913-918.

[6] Yao Y Y.Granular Computing for Web Intelligence and Brain Informatics[C]∥International Conference on Web Intelligence,2007,62:1-4.

[7] Guo husheng,Wang wenjian,Men changqian.A Novel Learning Model-kernel Granular Support Vector Machine[C]∥Proceedings of 2009 International Conference on Machine Learning and Cybernetics.Baoding, China,IEEE Press,2009：930-935.DOI:https:∥doi.org/10.1109/icmlc.2009.5212413.

[8] Tang yuchun,Jin bo,Zhang yanqing.Granular Support Vector Machines with Association Rules Mining for Protein Homology Prediction[J].ArtificialIntelligenceinMedicine,2005,35(1):121-134.

[9] Tang Y C,Jin B,Zhang Y Q.Granular Support Vector Machines with Association Rules Mining for Protein Homology Prediction[J].ArtificialIntelligenceinMedicine,2005,35(1):121-134.

[10] Yu H,Yang J,Han J W.Classifying Large Data Sets using SVMs with Hierarchical Clusters[J].KnowledgeDiscoveryandDataMining,2003,9:306-315.

[11] Wang W J,Xu Z B.A Heuristic Training in Support Vector Regression[J].Neurocomputing,2004,61:259-275.

[12] Chen R C,Cheng K F,Hsieh C F.Using Rough Set and Support Vector Machine for Network Intrusion Detection System[J].InternationalJournalofNetworkSecurity&ItsApplications,2009,59:465-470.DOI:https:∥doi.org/10.1109/aciids.2009.59

[13] Arun Kumar M,Gopal V.A Hybrid SVM based Decision Tree[J].PatternRecognition,2010,43(12):3977-3987.DOI:https:∥doi.org/10.1016/j.pat.cog.2010.06.010.

[14] Cui H X,Zhang L B,Kang R Y,etal.Research on Fault Diagnosis for Reciprocating Compressor Valve using Information Entropy and SVM Method[J].JournalofLossPreventionintheProcessIndustries,2009,22(6):864-867.DOI:https:∥doi.org/10.1016/j.jlp.2009.08.012.

[15] Anguita D.Improved Neural Network for SVM Learning[J].NeuralNetwork,2002,13(5):1243-1244.

[16] 程鳳偉,王文劍,郭虎升.動(dòng)態(tài)粒度SVM算法[J].模式識(shí)別與人工智能,2014(4):1799-1802.

AHierarchicalGranularSupportVectorMachineAlgorithmbasedonMixed

CHENG Fengwei1,GUO Husheng2*

(1.DepartmentofComputerEngineeringTaiyuanUniversity,Taiyuan030032,China;2.SchoolofComputerandInformationTechnology,ShanxiUniversity,Taiyuan030006,China)

The increasing size and dimensionality of real-world datasets make it necessary to design efficient classification algorithms.Support vector machine(SVM) is an acknowledged classification algorithm with good performance,and some SVM algorithms are aimed at reducing the number of support vector to improve the efficiency of classification.This paper proposes a hierarchical granularity support vector machine algorithm based on mixed,namely MHG-SVM,using the mixing degree to improve the existing hierarchical granularity support vector machine algorithm.The proposed algorithm defined a data granularity of confidence and a parameter to select important classification information, and then put them in training set to SVM training.The experimental results indicate that the improved algorithm is suitable for processing large number of observations and can effectively accelerate SVM learning while keeping the classification precision.

support vector;classification precision;mixing degree;granularity of confidence;large number of observations

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.04.010

2016-12-30；

2017-02-07

山西省自然科學(xué)基金(2015021096)，山西省高等學(xué)校科技創(chuàng)新項(xiàng)目(2015110)

程鳳偉(1988-),女,河南周口人, 碩士,助教，研究方向:人工智能, 機(jī)器學(xué)習(xí)。E-mail:867964783@qq.com

*通信作者：郭虎升(GUO Husheng)，E-mail:guohusheng@sxu.edu.cn

TP301

A

0253-2395(2017)04-0750-06