基于內(nèi)核的低秩逼近算法的改進(jìn)

高 超

(哈爾濱工程大學(xué)信息與通信工程學(xué)院，哈爾濱150001)

分析、提取和處理數(shù)據(jù)集的幾何結(jié)構(gòu)在數(shù)據(jù)挖掘中占有重要的地位[1].多數(shù)情況下，數(shù)據(jù)集(如文本數(shù)據(jù)集)的結(jié)構(gòu)是非線性的，或者數(shù)據(jù)集的運(yùn)算可能不具有線性運(yùn)算的特點(diǎn).此時(shí)，非線性特征更能反映數(shù)據(jù)集的特性[2].低秩逼近技術(shù)是解決非線性模式分析問題的有效途徑之一.文獻(xiàn)[3]提出了一種較有代表性的方法，基于低秩逼近技術(shù)的內(nèi)核算法(KBLA).它從原數(shù)據(jù)矩陣中非均勻地抽取一個(gè)小的樣本矩陣，再用與原數(shù)據(jù)矩陣相關(guān)的概率分布函數(shù)處理該樣本矩陣，接下來構(gòu)建一個(gè)可用于逼近原數(shù)據(jù)矩陣的秩為k的小塊矩陣，最后用此小塊矩陣逼近原數(shù)據(jù)矩陣.

雖然該算法在一定程度上可以較好的逼近原數(shù)據(jù)矩陣，但是該算法的逼近精度還有待提高.本文通過對(duì)原始矩陣的每一列賦予一個(gè)概率，并抽取概率最大的前c列構(gòu)成樣本矩陣，接下來用此樣本矩陣生成小塊逼近矩陣，以提高逼近精度.

1 改進(jìn)的基于內(nèi)核的低秩逼近算法

定義1 假設(shè)W∈?n×n是對(duì)稱半正定矩陣，W(i)表示矩陣W的第i列，與W的列相關(guān)的概率分布函數(shù) pi用下式表示，

定義2 權(quán)值矩陣D:D∈?c×c，是一個(gè)對(duì)角矩陣，對(duì)角線上的元素服從與矩陣列相關(guān)的非均勻分布，且其值依次遞減，

其中:pt表示在第t次獨(dú)立隨機(jī)試驗(yàn)中第 t次的概率.

定義3 采樣矩陣S:S∈?c×c，是一個(gè)由數(shù)字0和1組成的矩陣，且它的每列只有一個(gè)元素是1，其余元素是0.它的前c行也具有相同的特征.后n-c行構(gòu)成全零矩陣.在對(duì)矩陣A的列向量進(jìn)行c次獨(dú)立隨機(jī)抽樣試驗(yàn)時(shí)，如果在第j次抽樣試驗(yàn)中，

記，n×c矩陣C=WSD為經(jīng)過賦權(quán)值后的，從矩陣W中按非均勻概率分布函數(shù)抽取的列向量構(gòu)成的矩陣.再記，c×c方陣=(SD)TWSD為經(jīng)過賦權(quán)值后的，從矩陣W中抽取的列標(biāo)簽和行標(biāo)簽相交的元素構(gòu)成的矩陣.

具體的算法實(shí)現(xiàn)步驟如下.

輸入:數(shù)據(jù) A∈?n×p，采樣點(diǎn)數(shù) c，尺度因子 t.

1)根據(jù)數(shù)據(jù)集A建立相似度矩陣W;

2)分別利用式(1)，(2)和(3)計(jì)算概率分布函數(shù)pi、對(duì)角矩陣D和抽樣矩陣S;

2 誤差分析

定理1[4](標(biāo)準(zhǔn) Nystr?m 方法)在上述假設(shè)條件下，對(duì)任意的c，δ＞0，以下不等式成立的概率至少是1-δ，

定理2[3](KBLA)在上述假設(shè)條件下，如果存在概率分布函數(shù)pi，使得

那么，當(dāng) c≥64kη2/ε4，η =1+(8log(1/δ))1/2，時(shí)，對(duì)任意的ε＞0，不等式以至少1-δ的概率成立，

IKBLA算法的逼近誤差的上界與KBLA的相同，其推導(dǎo)過程與定理2的相同，在此，不再給出(參見文獻(xiàn)[3]的定理3).從上述2個(gè)定理可知，基于低秩逼近技術(shù)的KBLA和IKBLA算法的逼近誤差的上界比標(biāo)準(zhǔn)Nystr?m方法的逼近誤差的上界小得多.

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

為了驗(yàn)證IKBLA的有效性，本文將之與三種逼近算法進(jìn)行了比較.在UCI數(shù)據(jù)庫(kù)中部分?jǐn)?shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性.

實(shí)驗(yàn)環(huán)境:硬件環(huán)境，CPU Intel Core 2 Quad Q6600 2.4G，Internal memory 4G，Hard disk Hitachi HDP 725050GLA360 500G.軟件環(huán)境，Windows 2003+Matlab2007b.

3.1 實(shí)驗(yàn)數(shù)據(jù)集描述

在表1的描述中，Sonar，H.S，L.D，L.M，P.I.D，C.M.C，I.S，W.D.G 分別是如下數(shù)據(jù)集的縮 寫，ConnectionistBench (Sonar， Minesvs.Rocks)，Haberman’s Survival，Liver Disorders，Libras Movement，Pima Indians Diabetes，Contraceptive Method Choice，Image Segmentation，Waveform Database Generator(Version 1).

表1 實(shí)驗(yàn)數(shù)據(jù)集描述

3.2 實(shí)驗(yàn)方法的參數(shù)設(shè)置及評(píng)價(jià)指標(biāo)

以下是實(shí)驗(yàn)中用到的幾種方法及其參數(shù)設(shè)置.

利用Nystr?m方法的譜聚類(NS):是文獻(xiàn)[5]提出的方法.只執(zhí)行NS的逼近程序不執(zhí)行聚類程序.高斯核的尺度因子 t為0.5，采樣點(diǎn)數(shù) c為50個(gè).

基于Nystr?m的核方法(NBKM):是文獻(xiàn)[6-7]提出的逼近方法.采用服從均勻分布的概率分布函數(shù)計(jì)算矩陣D.參數(shù)設(shè)置同上.

KBLA:是文獻(xiàn)[3]提出的逼近算法.與NBKM算法的惟一區(qū)別是采用式(7)計(jì)算矩陣D.參數(shù)設(shè)置同上.

IKBLA:本文提出的算法.與KBLA算法的區(qū)別是IKBLA采用式(1)和(2)計(jì)算矩陣D.參數(shù)設(shè)置同上.

誤差E的計(jì)算方法為，

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

本文將上述四種算法在表1描述的數(shù)據(jù)集上進(jìn)行了測(cè)試.所得的逼近誤差E如表2所示.每次實(shí)驗(yàn)產(chǎn)生的最小逼近誤差E用“粗體+下劃線”標(biāo)出.

表2 四種算法的逼近誤差E

表2指出，NS的逼近誤差最大，其值大致分布在104～106之間.這一點(diǎn)與定理1的結(jié)論吻合.IKBLA，NBKM和KBLA的逼近誤差均比NS的小得多，值大致分布在102～103之間.這表明在用小塊采樣矩陣恢復(fù)大塊原數(shù)據(jù)矩陣的過程中，不宜用基于Nystr?m采樣技術(shù)的 NS.比較 KBLA和 NBKM的逼近誤差.數(shù)據(jù)顯示兩者的逼近誤差不相上下.這說明在聲吶、圖像和波浪等數(shù)據(jù)集上，與原數(shù)據(jù)矩陣所有列向量相關(guān)的，在數(shù)值上無(wú)規(guī)律可循的，服從非均勻分布的，概率分布函數(shù)的引入幾乎沒有改善低秩逼近算法的性能.再分別比較IKBLA和NBKM，IKBLA和KBLA的逼近誤差.可以看到IKBLA取得了最低的逼近誤差.這是因?yàn)樗x的c個(gè)代表點(diǎn)與剩余點(diǎn)間的關(guān)系更密切，更能反映數(shù)據(jù)集的特性.也表明同樣是服從非均勻分布的，但在數(shù)值上呈現(xiàn)遞減規(guī)律的，概率分布函數(shù)的引入在一定程度上改善了低秩逼近算法的性能.綜上所述，IKBLA可以被有效地應(yīng)用于UCI中部分?jǐn)?shù)據(jù)集的逼近中.

4 結(jié)語(yǔ)

針對(duì)KBLA的逼近精度還有待提高的問題，本文提出了一種改進(jìn)的低秩逼近算法.用在數(shù)值上呈遞減規(guī)律的，非均勻概率分布函數(shù)取代在數(shù)值上無(wú)規(guī)律可循的非均勻概率分布函數(shù)，使低秩逼近技術(shù)的逼近精度進(jìn)一步的提高.算法在UCI數(shù)據(jù)庫(kù)中部分?jǐn)?shù)據(jù)集上取得的實(shí)驗(yàn)結(jié)果驗(yàn)證了它的有效性.

[1]TAN P N，STEINBACH M，KUMAR V.Introduction to Data Mining[M].USA:Addison Wesley，2005.

[2]史衛(wèi)亞.大規(guī)模數(shù)據(jù)集下核方法的技術(shù)研究[D].上海:復(fù)旦大學(xué)，2008:5-9.

[3]DRINEAS P，MAHONEY M W.On the nystr?m method for approximating a gram matrix for improved kernel-based learning[J].Journal of Machine Learning Research，2005，6:2153-2175.

[4]KUMAR S，MOHRI M，TALWALKAR A.Ensemble nystr?m method[C]//23rd Conference on Neural Information Processing Systems，Vancouver，BC，Canada:The MIT Press，2009，1060-1068.

[5]FOWLKES C，BELONGIE S，F(xiàn)AN C，et al.Spectral grouping using the nystr?m method[J].IEEE Trans.Pattern Anal.Mach.Intell.，2004，26(2):214-225.

[6]WILLIAMS C，SEEGER M.Using the nystr?m method to speed up kernel machines[C]//Proceedings of the 2000 Conference on Advances in Neural Information Processing Systems，Chicago，USA:The MIT Press，2001:682-688.

[7]李萬(wàn)臣，高毓亮，齊 歡.基于LIE-QC結(jié)構(gòu)的速率兼容LDPC碼優(yōu)化構(gòu)造方法[J].哈爾濱商業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2012，28(5):546-550.