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

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

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

3、多類樣本的分類實質上是因為領域覆蓋算法求解的是多個二分類問題的集合。對任意一類樣本的覆蓋都只考慮覆蓋同類樣本而不覆蓋異類樣本，與異類樣本的類別數(shù)無關?？梢詫⑺械漠愵悩颖究醋魇且粋€等價類，它不影響當前類別樣本的覆蓋，因此任意一類樣本的覆蓋計算都是獨立的子問題，與異類樣本覆蓋不構成依賴關系。子問題的獨立性為并行算法的設計提供了理論基礎。實驗中利用三組公開的數(shù)據(jù)集對并行覆蓋算法進行訓練測試，在多核處理機上的實驗結果證明并行的覆蓋算法能成倍地

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

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

6、法。疊覆蓋算法利用一個隊列記錄中間覆蓋的樣本，重復以隊列中記錄的樣本作為覆蓋中心做覆蓋，不斷向隊列中加入新覆蓋的樣本，通過這種不斷重疊的覆蓋方式逐漸擴展覆蓋空間而達到逼近原樣本空間的效果。邊緣樣本的處理以及樣本孤立點的處理進一步對疊覆蓋算法做出優(yōu)化。實驗中同樣利用公用數(shù)據(jù)集對算法進行驗證，結果顯示疊覆蓋算法所求的模型對樣本的分類具有較少的拒識樣本數(shù)、分類精度高的特點，在部分數(shù)據(jù)集上分類效果顯著提升。
　　 4.最后，我們在研究覆