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

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

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

3、結(jié)了國內(nèi)外現(xiàn)階段對數(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í)的能力。如果有，是否可以實現(xiàn)，怎樣實現(xiàn);如果沒有，又是為什么。其次，為了檢驗新學(xué)習(xí)算法或者評估新指標(biāo)的有效性，需要在人工數(shù)據(jù)和真實數(shù)據(jù)上分別進行實驗驗證。人工數(shù)據(jù)在生成

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

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