陳素芬，曾雪強(qiáng)

(1. 南昌工程學(xué)院 信息工程學(xué)院，江西 南昌 330099；2. 南昌大學(xué) 計(jì)算中心，江西 南昌 330031)

中心修正增量主成分分析及其在文本分類中的應(yīng)用

陳素芬1，曾雪強(qiáng)2

(1. 南昌工程學(xué)院 信息工程學(xué)院，江西 南昌 330099；2. 南昌大學(xué) 計(jì)算中心，江西 南昌 330031)

增量式學(xué)習(xí)模型是挖掘大規(guī)模文本流數(shù)據(jù)的一種有效的數(shù)據(jù)處理技術(shù)。無偏協(xié)方差無關(guān)增量主成分分析(Candid Covariance-free Incremental Principal Component Analysis， CCIPCA)是一種增量主成分分析模型，具有收斂速度快和降維效果好的特點(diǎn)。但是，CCIPCA模型要求訓(xùn)練數(shù)據(jù)是已經(jīng)中心化或中心向量固定的。在實(shí)際的應(yīng)用中，CCIPCA往往采用一種近似的中心化算法對(duì)新樣本進(jìn)行處理，而不會(huì)對(duì)歷史數(shù)據(jù)進(jìn)行中心化修正。針對(duì)這一問題，該文提出了一種中心修正增量主成分分析模型(Centred Incremental Principal Component Analysis， CIPCA)。CIPCA算法不僅對(duì)新樣本進(jìn)行中心化處理，而且會(huì)對(duì)歷史數(shù)據(jù)進(jìn)行準(zhǔn)確的中心化修正。在文本流數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果表明，CIPCA算法的收斂速度和分類性能明顯優(yōu)于CCIPCA算法，特別是在原始數(shù)據(jù)的內(nèi)在模型不穩(wěn)定的情況下，新算法的優(yōu)勢更為明顯。

主成分分析；中心化修正；流數(shù)據(jù)；維數(shù)約減；增量學(xué)習(xí)

1 引言

流數(shù)據(jù)是近年來出現(xiàn)的一種新型的數(shù)據(jù)類型，在許多應(yīng)用領(lǐng)域出現(xiàn)頻繁，表現(xiàn)形式各異。與傳統(tǒng)的數(shù)據(jù)類型相比，流數(shù)據(jù)具有如下特點(diǎn)：實(shí)時(shí)到達(dá)，速率多變；連續(xù)到達(dá)，次序獨(dú)立；規(guī)模宏大，不能預(yù)知其極值；數(shù)據(jù)一經(jīng)處理，除非特意保存，否則不能被再次取出處理[1-3]。由于流數(shù)據(jù)環(huán)境實(shí)際應(yīng)用的需求，在流數(shù)據(jù)上進(jìn)行在線監(jiān)測、相關(guān)趨勢的分析和預(yù)測、聯(lián)機(jī)分析等研究工作受到了越來越多的重視。例如，網(wǎng)頁點(diǎn)擊流的分析，信息系統(tǒng)的入侵檢測以及傳感器網(wǎng)絡(luò)的管理等環(huán)境中，有很大部分的應(yīng)用需要對(duì)流數(shù)據(jù)進(jìn)行及時(shí)的在線處理，從而獲得盡可能短的響應(yīng)時(shí)間。

數(shù)據(jù)的高維性是現(xiàn)代機(jī)器學(xué)習(xí)任務(wù)經(jīng)常要面對(duì)的情況。與傳統(tǒng)機(jī)器學(xué)習(xí)任務(wù)類似，高維或超高維的特征空間會(huì)對(duì)流數(shù)據(jù)的學(xué)習(xí)算法帶來困難。維數(shù)約減(Dimension Reduction)將原始的高維特征變換到低維空間并盡可能降低無關(guān)和冗余特征的影響，可以提高建模的計(jì)算效率和泛化能力。在眾多的維數(shù)約減方法中，主成分分析(Principal Component Analysis: PCA)是其中最為常見并被廣泛應(yīng)用的模型之一[4]。PCA的優(yōu)化目標(biāo)是尋找一個(gè)能盡可能保持原始數(shù)據(jù)信息(方差)的低維空間。傳統(tǒng)的PCA以批量方式(Batch Mode)工作，即需要讀入全部訓(xùn)練數(shù)據(jù)后再進(jìn)行建模。但當(dāng)原始數(shù)據(jù)的特征維數(shù)或樣本數(shù)量過多時(shí)，批量方式的PCA會(huì)因?yàn)橛?jì)算量過大或內(nèi)存不足而無法工作。

解決該問題的一個(gè)可行的辦法是設(shè)計(jì)一種增量式學(xué)習(xí)(Incremental Learning)的增量主成分分析(Incremental PCA: IPCA)模型。關(guān)于IPCA模型，國內(nèi)外已有較多的研究工作[4-6]，現(xiàn)有的工作大致可以分為兩類：協(xié)方差相關(guān)模型和協(xié)方差無關(guān)模型。協(xié)方差相關(guān)IPCA模型，需要隨著樣本的增加而增量的估計(jì)協(xié)方差矩陣，再由此計(jì)算出新的主成分。不同的協(xié)方差相關(guān)IPCA模型的區(qū)別主要在于其估計(jì)協(xié)方差矩陣的計(jì)算方式不同；而協(xié)方差無關(guān)IPCA模型可以避免對(duì)協(xié)方差矩陣的估計(jì)，直接采用新樣本對(duì)得到的PCA主成分進(jìn)行增量式的修正，這樣可以減少模型的計(jì)算和存儲(chǔ)的開銷。在已有的協(xié)方差無關(guān)IPCA模型中，無偏協(xié)方差無關(guān)增量主成分分析(Candid Covariance-free Incremental Principal Component Analysis， CCIPCA)是其中收斂速度最快和效果最好的方法之一[7-8]。

和傳統(tǒng)的PCA模型一樣，CCIPCA方法有一個(gè)很強(qiáng)的假設(shè)前提，要求訓(xùn)練數(shù)據(jù)是已經(jīng)中心化或中心向量固定的。在實(shí)際的應(yīng)用中，CCIPCA一般會(huì)采用一種近似的中心化算法，即只對(duì)新進(jìn)入的樣本進(jìn)行準(zhǔn)確的中心化，而不對(duì)歷史數(shù)據(jù)進(jìn)行中心化修正。這樣的中心化算法在數(shù)據(jù)內(nèi)在模型變化不大的時(shí)候，有較好的效果；但是在其他情況下，數(shù)據(jù)沒有準(zhǔn)確中心化會(huì)明顯降低IPCA模型的性能。目前已經(jīng)有一些研究工作注意到了IPCA模型中的準(zhǔn)確中心化的問題。例如，Ross等人基于SKL(Sequential Karhunen-Loeve)算法提出了一種中心修正的IPCA算法[9]；Duan和Chen提出了一種批量更新的中心修正IPCA算法[10]。但是這些研究工作都是對(duì)協(xié)方差相關(guān)IPCA模型的改進(jìn)。目前還沒有研究工作提出針對(duì)協(xié)方差無關(guān)IPCA模型的準(zhǔn)確中心化修正的改進(jìn)算法。

為了解決這一問題，我們提出了一種中心修正增量主成分分析(Centred Incremental Principal Component Analysis，CIPCA)模型。CIPCA算法不僅對(duì)新進(jìn)入樣本進(jìn)行中心化處理，而且會(huì)對(duì)歷史數(shù)據(jù)進(jìn)行準(zhǔn)確的中心化修正。在文本流數(shù)據(jù)集Reuter-21578上的實(shí)驗(yàn)結(jié)果表明，CIPCA算法的收斂速度和分類性能明顯優(yōu)于CCIPCA算法。新算法的優(yōu)勢在數(shù)據(jù)的內(nèi)在模型不穩(wěn)定的情況下更為明顯。

本文組織如下：第一部分是引言；第二部分介紹IPCA模型的相關(guān)概念；第三部分對(duì)CIPCA模型的原理進(jìn)行詳細(xì)的闡述；實(shí)驗(yàn)結(jié)果與分析在第四部分中說明；最后一部分是結(jié)束語。

2 增量主成分分析

維數(shù)約減將原始數(shù)據(jù)從高維特征空間變換到低維空間，可以提高數(shù)據(jù)挖掘模型的計(jì)算效率和泛化能力。作為一種常見的無監(jiān)督維數(shù)約減模型，主成分分析(Principal Component Analysis， PCA)的優(yōu)化目標(biāo)是尋找一個(gè)能盡可能保持原始訓(xùn)練數(shù)據(jù)信息(方差)的低維空間[11]。給定n個(gè)中心化的p維訓(xùn)練樣本x(1),x(2), …,x(n)，PCA希望找到能保持最多方差信息的方向w。經(jīng)過一些簡單的推導(dǎo)，PCA的優(yōu)化目標(biāo)可以表示為式(1)。

(1)

其中，協(xié)方差矩陣如式(2)所示。

(2)

根據(jù)PCA成分之間的正交性要求，K個(gè)PCA投影方向就是協(xié)方差矩陣C的前K個(gè)特征向量。

作為一種維數(shù)約減方法，PCA將原始數(shù)據(jù)投影到K維子空間(一般K遠(yuǎn)小于p)。我們可以在變換后的低維空間進(jìn)行進(jìn)一步的數(shù)據(jù)挖掘和分析。PCA的具體求解一般采用奇異值分解(Singular Value Decomposition，SVD)[11]，其計(jì)算復(fù)雜度為O(η3)，其中η=min(p,n)。很明顯，在樣本數(shù)量和特征維度都很大的情況下，PCA算法的實(shí)際使用會(huì)由于計(jì)算量過大而出現(xiàn)困難。

為了適應(yīng)大規(guī)模數(shù)據(jù)的應(yīng)用要求，增量主成分分析模型(IncrementalPCA，IPCA)是一個(gè)較好的解決辦法?，F(xiàn)有的IPCA模型的相關(guān)研究工作可以分為協(xié)方差相關(guān)模型和協(xié)方差無關(guān)模型兩大類[4-6]。隨著樣本的增加，協(xié)方差相關(guān)IPCA模型采用增量的方式更新對(duì)協(xié)方差矩陣的估計(jì)，再基于更新后的協(xié)方差矩陣計(jì)算得到新的主成分。不同的協(xié)方差相關(guān)IPCA模型的區(qū)別，主要在于協(xié)方差矩陣的增量計(jì)算方式的不同。無論采用何種計(jì)算方法，這一類模型的缺點(diǎn)是增量計(jì)算協(xié)方差矩陣的計(jì)算和存儲(chǔ)開銷比較大。而協(xié)方差無關(guān)IPCA模型直接用新樣本對(duì)已有的PCA主成分進(jìn)行增量式的修正；可以避免對(duì)協(xié)方差矩陣的重新估計(jì)。在已有的協(xié)方差無關(guān)IPCA模型中，無偏協(xié)方差無關(guān)增量主成分分析(CandidCovariance-freeIncrementalPrincipalComponentAnalysis，CCIPCA)模型是其中降維效果和收斂速度均比較好的方法之一[7-8]。

基于式(1)，CCIPCA定義了一個(gè)新的變量v=λw=Cw。給定n個(gè)樣本的情況下，對(duì)v的估計(jì)v(n)可以按式(3)進(jìn)行近似計(jì)算。

(3)

其中w(i)是對(duì)w的第i步的估計(jì)值。

如果能得到v的值，那么w就可以通過w=v/‖v‖計(jì)算得到，其對(duì)應(yīng)的特征值λ=‖v‖。根據(jù)v和w的關(guān)系，構(gòu)造增量遞推公式的一個(gè)合理做法是用w(i-1)代替w(i)，用來計(jì)算當(dāng)前的v(i)。這樣，CCIPCA將公式(2)改寫為式(4)。

(4)

另外，為了控制當(dāng)前樣本相對(duì)于歷史數(shù)據(jù)的權(quán)重，CCIPCA還引入了一個(gè)遺忘參數(shù)(amnesic parameter)l。對(duì)式(4)進(jìn)行修正后，CCIPCA最終的增量公式如式(5)所示。

(5)

3 中心化修正的增量主成分分析

和傳統(tǒng)PCA模型一樣，CCIPCA假設(shè)訓(xùn)練數(shù)據(jù)是已經(jīng)中心化或中心向量固定的。為了滿足這一要求，在實(shí)際的應(yīng)用中CCIPCA會(huì)采用一種近似的中心化算法，即只對(duì)新進(jìn)入的樣本進(jìn)行準(zhǔn)確的中心化，而不對(duì)歷史數(shù)據(jù)進(jìn)行中心化修正。這樣的中心化算法在數(shù)據(jù)內(nèi)在模型變化不大的時(shí)候，有較好的效果；但是在其他情況下，數(shù)據(jù)沒有準(zhǔn)確中心化會(huì)明顯降低IPCA模型的性能。為了解決這一問題，我們提出一種中心修正增量主成分分析(Centred Incremental Principal Component Analysis，CIPCA)模型。CIPCA算法不僅會(huì)對(duì)新進(jìn)入的樣本進(jìn)行中心化，而且會(huì)對(duì)歷史數(shù)據(jù)進(jìn)行準(zhǔn)確的中心化修正。

(6)

在樣本均值已知的情況下，對(duì)當(dāng)前新進(jìn)入樣本的中心化處理只需要簡單的將樣本向量減去均值向量。但是，對(duì)歷史數(shù)據(jù)的中心化將會(huì)麻煩很多。隨著樣本的不斷增多，當(dāng)前的總體樣本的均值是在不斷的變化的；這樣對(duì)歷史數(shù)據(jù)的中心化就需要進(jìn)行修正。在歷史數(shù)據(jù)不能保存的情況下，我們就需要直接在IPCA的增量遞推公式中考慮歷史樣本的中心化修正問題。

(7)

(8)

增量遞推的式(8)只能解決第一主成分的計(jì)算問題，為了求取高階PCA主成分，我們需要引入新的計(jì)算方法。我們注意到，PCA的各個(gè)主成分之間是相互正交的[11]；那么我們可以利用正交互補(bǔ)空間的性質(zhì)，引入一種快速的計(jì)算方式。相似的計(jì)算方法已經(jīng)被CCIPCA和一些類似的增量學(xué)習(xí)模型采用[7, 13-14]。

(9)

(10)

和CCIPCA算法一樣，我們提出的CIPCA算法的計(jì)算復(fù)雜度是O(NKp)，其中N是樣本數(shù)量，p是樣本的特征維數(shù)，K是要得到的主成分的個(gè)數(shù)。在增量計(jì)算的過程中，CIPCA算法除了要存儲(chǔ)當(dāng)前的特征向量外，只需要存儲(chǔ)樣本均值向量和樣本個(gè)數(shù)。因此，從計(jì)算復(fù)雜度和存儲(chǔ)復(fù)雜度看，CIPCA算法都可以適應(yīng)大規(guī)模數(shù)據(jù)的應(yīng)用任務(wù)。CIPCA算法的具體的偽代碼在圖1中給出。

圖1 中心修正增量主成分分析算法

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

本文采用由路透公司采集的1987年的新聞稿組成的Reuters-21578文集作為實(shí)驗(yàn)數(shù)據(jù)集。Reuters-21578是一個(gè)在文本挖掘領(lǐng)域被廣泛采用的數(shù)據(jù)集[15]。雖然已有的在Reuters-21578文集上的大部分研究工作，只是將其作為一個(gè)普通的數(shù)據(jù)集來使用；但Reuters-21578文集實(shí)際上是一個(gè)典型的流數(shù)據(jù)集，因?yàn)槠渲械拿恳黄臋n都一個(gè)時(shí)間戳。

在除去一些損壞的文檔后，將訓(xùn)練集和測試集合并在一起，我們總共得到了11 359篇文檔。這些文檔分別屬于120個(gè)類別，但文檔的類別分布非常不平均。最常見的類別有3 986篇正例文檔，而大部分類別(97個(gè)類別)的正例文檔不足100篇。在本文的實(shí)驗(yàn)中，我們選用了最常見的兩個(gè)類別earn和acq，他們的正例文檔數(shù)分別為3 986和2 448。

對(duì)文檔的處理步驟包括：去除數(shù)字和停用詞，字母全部轉(zhuǎn)為小寫，采用Porter算法進(jìn)行詞干化處理。最終，我們得到了22 049個(gè)詞，并采用了ltc權(quán)重進(jìn)行文檔的表示。實(shí)驗(yàn)在一臺(tái)DELL的PC工作站上運(yùn)行，硬件配置為24×Intel(R)Xeon(R)CPUX5680 3.33GHz，64G內(nèi)存。實(shí)驗(yàn)的程序采用JAVA語言進(jìn)行編碼，代碼中引用了開源機(jī)器學(xué)習(xí)工具箱WEKA[16]。

4.2 收斂速度分析

我們?cè)趀arn和acq兩個(gè)類別上，對(duì)比了CIPCA和CCIPCA的收斂速度。首先，所有的文檔按照時(shí)間戳的先后進(jìn)行排序；然后，我們從每個(gè)類別中分別選取了前1 000個(gè)正例文檔；最后，這些文檔被等分為20個(gè)數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊有50篇文檔。我們將這些文檔按照順序加入到IPCA模型中，并且為每個(gè)數(shù)據(jù)塊記錄一個(gè)模型的收斂得分。

圖2 CIPCA和CCIPCA的第一特征向量的收斂曲線

從圖2中我們可以看出，CIPCA和CCIPCA總體上都會(huì)隨著數(shù)據(jù)的增加而收斂。在類別earn上，CIPCA表現(xiàn)出比CCIPCA具有更快的收斂速度；而隨著樣本的增多，兩個(gè)算法表現(xiàn)出了基本相同的收斂曲線。這說明，中心化修正的效果在數(shù)據(jù)樣本比較少的情況下具有比較明顯的效果；而當(dāng)數(shù)據(jù)的內(nèi)在模型穩(wěn)定的時(shí)候，中心化修正的效果不明顯。

我們還可以發(fā)現(xiàn)，CIPCA在類別acq上表現(xiàn)出了明顯優(yōu)于CCIPCA收斂性能。我們認(rèn)為這是因?yàn)?，?dāng)數(shù)據(jù)的內(nèi)在模型不是很穩(wěn)定的時(shí)候，樣本均值向量就會(huì)有比較大的變化，那么中心化修正就能明顯提升IPCA算法的性能。就像Weng指出的，IPCA算法在內(nèi)在模型不穩(wěn)定的數(shù)據(jù)流上的性能不佳[7]。因?yàn)閿?shù)據(jù)的內(nèi)在模型的劇烈變化，會(huì)使得IPCA模型的收斂出現(xiàn)問題。我們的實(shí)驗(yàn)結(jié)果也證實(shí)了這一觀點(diǎn)。但是，從實(shí)驗(yàn)結(jié)果看，CIPCA在收斂魯棒性方面要優(yōu)于CCIPCA。

4.3 分類性能分析

在Reuters-21578數(shù)據(jù)集上已有的研究工作，一般會(huì)采用交叉驗(yàn)證或隨機(jī)抽樣的方式將文本的順序打亂，再進(jìn)行文本分類實(shí)驗(yàn)[15]。為了能更好的模擬真實(shí)的數(shù)據(jù)流的情況，我們?cè)O(shè)計(jì)了一個(gè)新的實(shí)驗(yàn)步驟。首先，我們將所有的文檔按照時(shí)間戳的順序等分為20個(gè)數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊大約有577篇文檔；然后將這些數(shù)據(jù)塊依次加入IPCA模型，進(jìn)行模型訓(xùn)練；最后將已經(jīng)加入IPCA模型的數(shù)據(jù)作為訓(xùn)練集，將當(dāng)前的下一個(gè)數(shù)據(jù)塊作為測試集，再采用IPCA進(jìn)行降維、訓(xùn)練分類模型并記錄最終的分類性能。這樣，除了第一個(gè)數(shù)據(jù)塊，我們可以為每一個(gè)數(shù)據(jù)塊記錄一個(gè)分類性能的結(jié)果。

我們采用了k近鄰(kNearestNeighbout，kNN)分類器作為分類模型，其中的參數(shù)k=1。每個(gè)類別均作為一個(gè)二分類(binaryclassification)任務(wù)，正例的類標(biāo)為1，負(fù)例為-1。采用常用的F1值記錄最終的分類性能。我們?cè)趫D3中給出了具體的CIPCA和CCIPCA在類別earn和acq上的分類結(jié)果，其中圖3的上半部分是對(duì)應(yīng)數(shù)據(jù)塊的正例文檔數(shù)。參數(shù)K和l的值分別設(shè)置為5和2。

圖3 中心修正的增量主成分分析算法

我們從圖3的結(jié)果可以發(fā)現(xiàn)，CIPCA在類別earn上的性能與CCIPCA類似；而在類別acq上，CIPCA的性能要明顯優(yōu)于CCIPCA。我們認(rèn)為這是與數(shù)據(jù)的內(nèi)在模型的穩(wěn)定程度相關(guān)的。類別earn的數(shù)據(jù)的內(nèi)在模型較為穩(wěn)定，那么對(duì)歷史數(shù)據(jù)的中心修正的效果會(huì)不明顯。而當(dāng)數(shù)據(jù)的內(nèi)在模型變化較為劇烈的時(shí)候，CIPCA就會(huì)表現(xiàn)出明顯優(yōu)于CCIPCA的性能。這也是我們觀察到CIPCA的性能在類別acq上優(yōu)于CCIPCA的原因。另外，這與我們?cè)谇耙恍」?jié)分析模型的收斂速度時(shí)的結(jié)論是一致的。

另外我們可以發(fā)現(xiàn)，兩個(gè)IPCA模型在類別earn的性能總體上要優(yōu)于在類別acq上的性能。這也說明了類別earn的數(shù)據(jù)內(nèi)在模型較為穩(wěn)定，比較有利于增量學(xué)習(xí)算法的建模。而類別acq的數(shù)據(jù)內(nèi)在模型變化較為劇烈，不利于IPCA模型的收斂。

5 結(jié)束語

無偏協(xié)方差無關(guān)增量主成分分析(CandidCovariance-freeIncrementalPrincipalComponentAnalysis，CCIPCA)是一種協(xié)方差無關(guān)的增量主成分分析模型，具有收斂速度快和降維效果好的特點(diǎn)。但是，CCIPCA模型要求訓(xùn)練數(shù)據(jù)是已經(jīng)中心化或中心向量固定的。在實(shí)際應(yīng)用中，CCIPCA一般會(huì)采用一種近似的中心化算法，只對(duì)新進(jìn)入的樣本進(jìn)行中心化處理，而不對(duì)歷史數(shù)據(jù)進(jìn)行中心化修正。這樣的中心化算法在數(shù)據(jù)的內(nèi)在模型變化不大的時(shí)候，有較好的效果；但是在其他情況下，數(shù)據(jù)沒有準(zhǔn)確中心化會(huì)明顯降低IPCA模型的性能。

為了解決歷史數(shù)據(jù)的中心化修正問題，本文提出了一種中心修正增量主成分分析模型(CentredIncrementalPrincipalComponentAnalysis，CIPCA)。CIPCA算法不僅會(huì)對(duì)當(dāng)前新進(jìn)入樣本進(jìn)行中心化，而且會(huì)對(duì)歷史數(shù)據(jù)進(jìn)行準(zhǔn)確的中心化修正。在文本流數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，CIPCA算法的收斂速度和分類性能優(yōu)于CCIPCA算法。特別是當(dāng)數(shù)據(jù)的內(nèi)在模型不穩(wěn)定的情況下，CIPCA算法的優(yōu)勢更為明顯。

[1]GolabL,JohnsonT,ShkapenyukV.Scalableschedulingofupdatesinstreamingdatawarehouses[J].IEEETransactionsonKnowledgeandDataEngineering, 2012, 24(6): 1092-1105.

[2]AusterberryD.Thetechnologyofvideoandaudiostreaming[M].FocalPress, 2005.

[3]BabcockB,BabuS,DatarM,etal.Modelsandissuesindatastreamsystems[C]//Proceedingsofthe21thACMSIGMOD-SIGACT-SIGARTsymposiumonPrinciplesofdatabasesystems.ACM,2002： 1-16.

[4]ArtacM,JoganM,LeonardisA.IncrementalPCAforon-linevisuallearningandrecognition[C]//Proceedingsofthe16thInternationalConferenceonPatternRecognition.IEEE, 2002, 3: 781-784.

[5]LiY.Onincrementalandrobustsubspacelearning[J].Patternrecognition, 2004, 37(7): 1509-1518.

[6]RenCX,DaiDQ.Incrementallearningofbidirectionalprincipalcomponentsforfacerecognition[J].PatternRecognition, 2010, 43(1): 318-330.

[7]WengJ,ZhangY,HwangWS.Candidcovariance-freeincrementalprincipalcomponentanalysis[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2003, 25(8): 1034-1040.

[8]YanS,TangX.Largest-eigenvalue-theoryforincrementalprincipalcomponentanalysis[C]//Proceedingsofthe12thIEEEInternationalConferenceonImageProcessing(ICIP).IEEE, 2005, 1: 1181-1184.

[9]RossDA,LimJ,LinRS,etal.Incrementallearningforrobustvisualtracking[J].InternationalJournalofComputerVision, 2008, 77(1-3): 125-141.

[10]DuanG,ChenYW.Batch-incrementalprincipalcomponentanalysiswithexactmeanupdate[C]//Proceedingsofthe18thIEEEInternationalConferenceonImageProcessing(ICIP).IEEE, 2011: 1397-1400.

[11]JolliffeIT.PrincipalComponentAnalysis[M],secondeditioned.Springer, 2002.

[12]ChinTJ,SuterD.Incrementalkernelprincipalcomponentanalysis[J].IEEETransactionsonImageProcessing, 2007, 16(6): 1662-1674.

[13]YanJ,ZhangB,YanS,etal.Ascalablesupervisedalgorithmfordimensionalityreductiononstreamingdata[J].InformationSciences, 2006, 176(14): 2042-2065.

[14]YanJ,ZhangB,LiuN,etal.Effectiveandefficientdimensionalityreductionforlarge-scaleandstreamingdatapreprocessing[J].IEEETransactionsonKnowledgeandDataEngineering, 2006, 18(3): 320-333.

[15]YangY,LiuX.Are-examinationoftextcategorizationmethods[C]//Proceedingsofthe22ndannualinternationalACMSIGIRconferenceonResearchanddevelopmentininformationretrieval.ACM, 1999: 42-49.

[16]WittenIH,FrankE.DataMining:Practicalmachinelearningtoolsandtechniques[M].MorganKaufmann,SanFrancisco, 2005.

Centred Incremental Principal Component Analysis and Its Application in Text Classification

CHEN Sufen1, ZENG Xueqiang2

(1. School of Information Engineering, Nanchang Institute of Technology, Nanchang, Jiangxi 330099, China; 2. Computing Center of Nanchang University, Nanchang, Jiangxi 330031，China)

For the data mining of large-scale and streaming text data, incremental dimension reduction is an essential technique. As a state-of-the-art solution, Candid Covariance-free Incremental Principal Component Analysis (CCIPCA) applies an approximate centric alignment on the input data, where only the current sample is centred but all historical data are not updated properly. In this paper, we propose a Centred Incremental Principal Component Analysis (CIPCA) algorithm with exact historical mean update. Compared to CCIPCA, the proposed method not only correctly centered the current sample, but also correctly update all historical data by the current mean. The experiments on text streaming dataset show that CIPCA converges more quickly with the data flows in, and the performance improvement is especially obvious when the data’s inherent covariance is not stable.

principal component analysis; exact mean update; streaming data; dimension reduction; incremental learning

陳素芬(1980—)，碩士，講師，主要研究領(lǐng)域?yàn)樘卣鞒槿?、?yōu)化算法、機(jī)器學(xué)習(xí)。E?mail：sufenchen@foxmail．com曾雪強(qiáng)(1978—)，通信作者，博士，副教授，主要研究領(lǐng)域?yàn)樘卣鞒槿　⑻卣鬟x擇、機(jī)器學(xué)習(xí)。E?mail：xqzeng@ncu．edu．cn

1003-0077(2016)01-0108-07

2013-06-08 定稿日期： 2014-05-06

國家自然科學(xué)基金(61463033)；江西省自然科學(xué)基金(20151BAB207028)

TP391

A