覆蓋算法性能優(yōu)化的若干研究及其實(shí)現(xiàn).pdf

1、覆蓋算法作為一種構(gòu)造型分類(lèi)建模算法，以其訓(xùn)練速度快、分類(lèi)效果好而著稱(chēng)。在現(xiàn)今互聯(lián)網(wǎng)時(shí)代，時(shí)常面對(duì)較大的數(shù)據(jù)集訓(xùn)練和分類(lèi)的挑戰(zhàn)，因此提升機(jī)器學(xué)習(xí)算法的訓(xùn)練速度和分類(lèi)精度具有重要意義。
　　 本文主要研究覆蓋算法CA(CoveringAlgorithm)的樣本訓(xùn)練速度的提升和模型分類(lèi)精度的提升，分別提出并行覆蓋算法ParallelCA和疊覆蓋算法OCA(OverlappedCoveringAlgorithm)。雖然覆蓋算法在訓(xùn)練小數(shù)

2、據(jù)集時(shí)具有較快的速度，但是當(dāng)數(shù)據(jù)集逐漸增大的時(shí)候，覆蓋算法的訓(xùn)練速度會(huì)嚴(yán)重降低。并行覆蓋算法ParallelCA可以利用并行計(jì)算機(jī)的優(yōu)勢(shì)在數(shù)據(jù)集較大的時(shí)候也能快速訓(xùn)練樣本。疊覆蓋算法的提出則是啟發(fā)于計(jì)算機(jī)圖形學(xué)中的形狀顏色填充過(guò)程，它通過(guò)對(duì)樣本的覆蓋而不斷地向周?chē)鷶U(kuò)展而達(dá)到整體覆蓋模型與樣本空間近似的作用，可以較好地提升模型的分類(lèi)能力。
　　 本文的主要工作包括:
　　 1.通過(guò)對(duì)領(lǐng)域覆蓋算法分析，發(fā)現(xiàn)其建立的模型能實(shí)現(xiàn)

3、多類(lèi)樣本的分類(lèi)實(shí)質(zhì)上是因?yàn)轭I(lǐng)域覆蓋算法求解的是多個(gè)二分類(lèi)問(wèn)題的集合。對(duì)任意一類(lèi)樣本的覆蓋都只考慮覆蓋同類(lèi)樣本而不覆蓋異類(lèi)樣本，與異類(lèi)樣本的類(lèi)別數(shù)無(wú)關(guān)?？梢詫⑺械漠愵?lèi)樣本看作是一個(gè)等價(jià)類(lèi)，它不影響當(dāng)前類(lèi)別樣本的覆蓋，因此任意一類(lèi)樣本的覆蓋計(jì)算都是獨(dú)立的子問(wèn)題，與異類(lèi)樣本覆蓋不構(gòu)成依賴(lài)關(guān)系。子問(wèn)題的獨(dú)立性為并行算法的設(shè)計(jì)提供了理論基礎(chǔ)。實(shí)驗(yàn)中利用三組公開(kāi)的數(shù)據(jù)集對(duì)并行覆蓋算法進(jìn)行訓(xùn)練測(cè)試，在多核處理機(jī)上的實(shí)驗(yàn)結(jié)果證明并行的覆蓋算法能成倍地

4、提升樣本的訓(xùn)練速度，且算法本身不依賴(lài)于特定的并行計(jì)算環(huán)境，也適用于分布式集群。
　　 2.覆蓋算法建立分類(lèi)模型的主要思想是“物以類(lèi)聚”，通過(guò)覆蓋中心和半徑概括其附近的樣本區(qū)域，最終整個(gè)樣本集被若干個(gè)覆蓋所泛化。本文從另外一個(gè)角度考慮，認(rèn)為樣本是對(duì)客觀世界的抽象描述，它在空間中的分布具有一定的規(guī)律，覆蓋則是某種程度上對(duì)樣本空間分布的一種近似。覆蓋的空間區(qū)域與樣本的空間分布越近似，其對(duì)樣本的分類(lèi)效果越好。通過(guò)對(duì)同類(lèi)覆蓋是否可重疊的研

5、究，總結(jié)出兩種極端的覆蓋方式:保守型覆蓋和開(kāi)放型覆蓋。前者要求所有的覆蓋必須相互獨(dú)立，不允許重疊;后者允許同類(lèi)覆蓋之間相互重疊。保守型覆蓋對(duì)樣本具有較好的擬合性，對(duì)可識(shí)樣本分類(lèi)效果較好，但是模型中拒識(shí)區(qū)域較多;開(kāi)放型覆蓋中拒識(shí)區(qū)域較少，但是對(duì)于未知區(qū)域樣本具有較高的誤分類(lèi)風(fēng)險(xiǎn)。綜合對(duì)實(shí)驗(yàn)數(shù)據(jù)的分析，發(fā)現(xiàn)開(kāi)放型覆蓋具有較好的泛化能力，其分類(lèi)能力略?xún)?yōu)于保守型覆蓋。
　　 3.在分析保守型覆蓋和開(kāi)放型覆蓋方式的基礎(chǔ)上，我們提出疊覆蓋算

6、法。疊覆蓋算法利用一個(gè)隊(duì)列記錄中間覆蓋的樣本，重復(fù)以隊(duì)列中記錄的樣本作為覆蓋中心做覆蓋，不斷向隊(duì)列中加入新覆蓋的樣本，通過(guò)這種不斷重疊的覆蓋方式逐漸擴(kuò)展覆蓋空間而達(dá)到逼近原樣本空間的效果。邊緣樣本的處理以及樣本孤立點(diǎn)的處理進(jìn)一步對(duì)疊覆蓋算法做出優(yōu)化。實(shí)驗(yàn)中同樣利用公用數(shù)據(jù)集對(duì)算法進(jìn)行驗(yàn)證，結(jié)果顯示疊覆蓋算法所求的模型對(duì)樣本的分類(lèi)具有較少的拒識(shí)樣本數(shù)、分類(lèi)精度高的特點(diǎn)，在部分?jǐn)?shù)據(jù)集上分類(lèi)效果顯著提升。
　　 4.最后，我們?cè)谘芯扛?/p>