高 超

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

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

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

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

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

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

其中:pt表示在第t次獨立隨機試驗中第 t次的概率.

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

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

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

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

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

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

2 誤差分析

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

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

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

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

3 實驗設計與結(jié)果分析

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

實驗環(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ù)據(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ù)據(jù)集描述

3.2 實驗方法的參數(shù)設置及評價指標

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

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

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

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

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

誤差E的計算方法為，

3.3 實驗結(jié)果與分析

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

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

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

4 結(jié)語

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

[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].上海:復旦大學，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]李萬臣，高毓亮，齊 歡.基于LIE-QC結(jié)構(gòu)的速率兼容LDPC碼優(yōu)化構(gòu)造方法[J].哈爾濱商業(yè)大學學報:自然科學版，2012，28(5):546-550.