數(shù)據(jù)復(fù)雜度的增量學(xué)習(xí)方法研究.pdf

1、分類學(xué)習(xí)是模式識(shí)別、機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘的基礎(chǔ)問題。隨著分類學(xué)習(xí)理論及應(yīng)用在深度及廣度上的不斷探索，新的問題與挑戰(zhàn)亦層出不窮，其中有一個(gè)問題比較突出:對(duì)于實(shí)際的任務(wù)，在分類學(xué)習(xí)各環(huán)節(jié)中有如此多的方法和算法可供選擇，應(yīng)該如何衡量問題的難度和數(shù)據(jù)特性，然后依據(jù)這些信息在分類學(xué)習(xí)的各環(huán)節(jié)中選擇適合的方法或方案，從而可以避免不必要的過多試探。在此背景下，數(shù)據(jù)復(fù)雜度概念應(yīng)運(yùn)而生。但在實(shí)際應(yīng)用中，新的數(shù)據(jù)往往會(huì)不斷產(chǎn)生，而現(xiàn)有的數(shù)據(jù)復(fù)雜度算法都是基于

2、批量學(xué)習(xí)思想的，面對(duì)數(shù)據(jù)規(guī)模的動(dòng)態(tài)增加，它又該如何衡量數(shù)據(jù)的特性信息成為數(shù)據(jù)挖掘領(lǐng)域亟待解決的問題。
　　本文圍繞此問題，在深入討論TK Ho等人提出的數(shù)據(jù)復(fù)雜度的基礎(chǔ)上，進(jìn)一步研究其增量學(xué)習(xí)功能。從增量學(xué)習(xí)的角度出發(fā)，這12個(gè)衡量指標(biāo)可劃分為三類進(jìn)行研究，即:基于充分統(tǒng)計(jì)量的、基于經(jīng)典分類器算法的以及二者都不屬于的第三類復(fù)雜度指標(biāo)。本文的研究重點(diǎn)就是從這三類復(fù)雜度指標(biāo)出發(fā)，討論并改進(jìn)相關(guān)算法使其具有增量學(xué)習(xí)的功能。首先，分析和總

3、結(jié)了國(guó)內(nèi)外現(xiàn)階段對(duì)數(shù)據(jù)分類、數(shù)據(jù)復(fù)雜度、增量學(xué)習(xí)方法等問題的研究現(xiàn)狀。討論了分類學(xué)習(xí)領(lǐng)域算法較多，但是選擇算法的指導(dǎo)思想較少的尷尬局面。然后，深入討論數(shù)據(jù)幾何復(fù)雜度指標(biāo)和增量學(xué)習(xí)方法。將數(shù)據(jù)復(fù)雜度從增量學(xué)習(xí)角度劃分歸類，再結(jié)合增量學(xué)習(xí)的研究思想討論這些指標(biāo)是否都有增量學(xué)習(xí)的能力。如果有，是否可以實(shí)現(xiàn)，怎樣實(shí)現(xiàn);如果沒有，又是為什么。其次，為了檢驗(yàn)新學(xué)習(xí)算法或者評(píng)估新指標(biāo)的有效性，需要在人工數(shù)據(jù)和真實(shí)數(shù)據(jù)上分別進(jìn)行實(shí)驗(yàn)驗(yàn)證。人工數(shù)據(jù)在生成

4、前其分布、邊界、可分性都是事先設(shè)計(jì)好的，以使實(shí)驗(yàn)具有很好的可控性，而在真實(shí)數(shù)據(jù)上得到的結(jié)果更具有可信度。所以本文采用兩種數(shù)據(jù)相結(jié)合的方式進(jìn)行實(shí)驗(yàn)，可以更合理地去評(píng)估我們的新算法。再次，通過對(duì)數(shù)據(jù)復(fù)雜度12個(gè)指標(biāo)的研究，可以發(fā)現(xiàn)F1、F2、T2以及N2是基于充分統(tǒng)計(jì)量的學(xué)習(xí)算法。它們是關(guān)于數(shù)據(jù)集的求和、求均值和方差等運(yùn)算，關(guān)于這些運(yùn)算的增量學(xué)習(xí)方法實(shí)際已經(jīng)存在。但是他們是否可以應(yīng)用在數(shù)據(jù)復(fù)雜度方面，就需要對(duì)其進(jìn)行歸納總結(jié)，本文在人工數(shù)據(jù)上

5、檢驗(yàn)了其可行性。最后，根據(jù)對(duì)數(shù)據(jù)復(fù)雜度指標(biāo)的進(jìn)一步研究分析， N3、N4和L2、L3分別是基于KNN分類器(K=1)和線性分類器算法的復(fù)雜度指標(biāo)。那么本文在1-NN分類器的基礎(chǔ)上提出了其增量學(xué)習(xí)算法I1NN，同時(shí)在人工數(shù)據(jù)集和UCI公共數(shù)據(jù)集上驗(yàn)證了其可行性和有效性（見5.2節(jié)）。針對(duì)線性分類器研究分析了一種快速SVM增量學(xué)習(xí)算法（見5.3節(jié)）。在UCI公共數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，對(duì)比實(shí)驗(yàn)結(jié)果，驗(yàn)證了該算法增量學(xué)習(xí)功能的有效性，從而實(shí)現(xiàn)了復(fù)