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

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

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

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

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