基于最優(yōu)密度方向的等距映射降維算法

梁少軍 ,張世榮 ,孫瀾瓊

(1.陸軍工程大學(xué) 軍械士官學(xué)校,湖北 武漢 430075;2.武漢大學(xué) 電氣與自動(dòng)化學(xué)院,湖北 武漢 430072)

1 引言

隨著信息技術(shù)的飛速發(fā)展,數(shù)據(jù)產(chǎn)生與獲取方式的渠道增多,數(shù)據(jù)樣式呈現(xiàn)多樣化,如音視頻數(shù)據(jù)、圖像數(shù)據(jù)、文本數(shù)據(jù)等.眾多研究領(lǐng)域的數(shù)據(jù)維度也越來越高,如人臉識(shí)別[1]、信息檢索[2]、氣候變化、恒星光譜、基因分布[3]等.高維數(shù)據(jù)會(huì)導(dǎo)致數(shù)據(jù)計(jì)算的高度復(fù)雜化,給后期數(shù)據(jù)處理工作帶來巨大挑戰(zhàn),這通常被稱為“維數(shù)災(zāi)難”[4].高維數(shù)據(jù)包含大量的冗余信息,體現(xiàn)為數(shù)據(jù)的稀疏性,數(shù)據(jù)降維是應(yīng)對(duì)高維稀疏數(shù)據(jù)的有效手段.常用的線性降維方法有主成分分析(principal components analysis,PCA)算法[5]、線性判別(linear discriminant analysis,LDA)算法[6]、多維尺度變換(multi-dimensional scaling,MDS)算法[7]等.在實(shí)際應(yīng)用中大多數(shù)數(shù)據(jù)各維度間呈現(xiàn)非線性相關(guān)特征,因此出現(xiàn)了一些非線性降維方法,如拉普拉斯映射(Laplacian eigenmaps,LEIGS)算法[8]、局部線性嵌入(locally linear embedding,LLE)算法[9]、局部切空間排列(local target space alignment,LTSA)算法、等距映射 (isometric mapping,ISOMAP)算法[10]等.其中,ISOMAP算法是一種使用廣泛的典型非線性降維算法,該算法基于局部鄰域距離計(jì)算各數(shù)據(jù)點(diǎn)之間的全局測(cè)地距離,在盡量保持高維數(shù)據(jù)測(cè)地距離與低維數(shù)據(jù)空間距離對(duì)等關(guān)系的基礎(chǔ)上實(shí)現(xiàn)降維.但I(xiàn)SOMAP算法本身缺乏噪聲應(yīng)對(duì)能力,噪聲會(huì)破壞算法的拓?fù)浞€(wěn)定性影響降維效果[11];局部鄰域距離的計(jì)算沒有方向性,當(dāng)高維流形存在較大曲率時(shí)將導(dǎo)致“短路現(xiàn)象”[12],降維后數(shù)據(jù)不能很好保持高維拓?fù)浣Y(jié)構(gòu).

為解決以上問題,提出了一些改進(jìn)方法,例如,監(jiān)督的ISOMAP (supervised isometric mapping,S–ISOMAP)算法[13]、多流形判別ISOMAP (multi-manifold dimensional isometric mapping,MMD–ISOMAP)算法[14]等.但此類方法無法適用于無標(biāo)簽數(shù)據(jù)集.基于密度縮放因子的ISOMAP(density scaling factor based isometric mapping,D–ISOMAP)算 法[15]雖然降低了對(duì)噪聲的敏感性,但仍無法應(yīng)對(duì)較大曲率引起的“短路現(xiàn)象”.本文針對(duì)現(xiàn)有算法存在的上述問題,提出了一種基于最優(yōu)密度方向的流形降維方法(optimal density direction based ISOMAP,ODD–ISOMAP),該算法用向量表征高維數(shù)據(jù)與近鄰關(guān)系,通過尋找高維數(shù)據(jù)最優(yōu)密度方向構(gòu)建距離縮放矩陣,旨在增強(qiáng)算法應(yīng)對(duì)強(qiáng)的噪聲抗干擾的能力并避免高維流形較大曲率導(dǎo)致的“短路現(xiàn)象”.文章將對(duì)比ODD–ISOMAP算法與ISOMAP,HLLE,LTSA,LEIGS,LLE和PCA算法的降維性能,驗(yàn)證了算法的有效性.

2 經(jīng)典ISOMAP算法

設(shè)原始 高維數(shù)據(jù)為X=[x1x2···xm]T∈Rm×n,降維后的數(shù)據(jù)矩陣為Y=[y1y2···ym]T∈Rm×d;其中:m為采樣數(shù),n為原始變量維度,d為降維后變量維度.經(jīng)典的ISOMAP算法包括以下幾個(gè)核心環(huán)節(jié):1) 構(gòu)建無向鄰域距離矩陣;2) 獲取測(cè)地距離矩陣;3) 獲取低維嵌入表示矩陣.

無向鄰域距離的計(jì)算方式有兩種:一種基于距離,將xi與其鄰域半徑r范圍內(nèi)的數(shù)據(jù)間距離作為鄰域距離;另一種基于數(shù)量,將xi與其k個(gè)最近鄰集合k(xi)數(shù)據(jù)間的距離作為鄰域距離.本文選擇后者構(gòu)建鄰域距離矩陣,將xi與X中數(shù)據(jù)間的無向鄰域距離定義為

則X數(shù)據(jù)間的無向鄰域距離矩陣D可表示為

再使用Dijkstra或Floyd最短路徑算法即可得到任意兩個(gè)數(shù)據(jù)間的最短路徑距離,即測(cè)地距離dG(xi,j).

獲取低維嵌入表示可通過求解以下最優(yōu)化問題來實(shí)現(xiàn):

使用MDS算法求解該問題,即得到高維數(shù)據(jù)X的低維嵌入表示矩陣Y.

3 ODD–ISOMAP算法

ODD–ISOMAP算法的基本思想是首先確定每個(gè)高維數(shù)據(jù)xi的最優(yōu)密度方向,然后獲取xi的k個(gè)近鄰在最優(yōu)密度方向上的投影.再以投影角度、方向和相對(duì)大小修訂xi與k個(gè)近鄰的局部鄰域距離,即得到有向鄰域距離,從而引導(dǎo)數(shù)據(jù)沿著流形方向計(jì)算測(cè)地距離,降低短路風(fēng)險(xiǎn),增強(qiáng)算法抵制噪聲干擾的能力.

3.1 基于自然鄰居的最優(yōu)密度方向

高維流形上的任一數(shù)據(jù)xi都有一個(gè)指向局部最高數(shù)據(jù)密度且處于流形表面的方向,將該方向定義為最優(yōu)密度方向,并記為.為了確保最優(yōu)密度方向沿流形方向,同時(shí)具有較強(qiáng)的抗噪聲干擾能力,本文引入自然鄰居(natural neighbor,NN)概念.

先按照經(jīng)典ISOMAP算法計(jì)算高維數(shù)據(jù)X中任一采樣 數(shù)據(jù)xi的k近 鄰集 合k(xi).在k(xi)基 礎(chǔ)上xi的自然鄰居集合定義為上式中ψ(xi)表示xi的自然鄰居集合.由該式可知,數(shù)據(jù)xj屬于ψ(xi)表示xi與xj都在對(duì)方的k近鄰集合中.

圖1展示了三維流形中xi自然鄰居選取過程及自然鄰居的抗干擾能力,此例中近鄰數(shù)k=4.k(xi)包含4個(gè)數(shù) 據(jù)xj,xp,xt與xn,xi與xn由于流 形緊密 折疊出現(xiàn)了短路現(xiàn)象.如圖1(a)所示,在噪聲干擾前xj與xp被選為xi的自然鄰居,xn和xt雖然屬于xi的最近鄰但xt局部范圍內(nèi)有更相近的數(shù)據(jù),xn在流形的另一端其近鄰數(shù)據(jù)大概率也不包含xi,故xn和xt均未入選xi的自然鄰居.可見自然鄰居的選取標(biāo)準(zhǔn)比較嚴(yán)格,這一特征能確保xi篩選出的自然鄰居沿局部最大密度方向,由于數(shù)據(jù)xi的局部最大密度方向一般沿著局部流形的方向分布,故可以基于自然鄰居得到的最優(yōu)密度方 向也會(huì) 沿著局 部流形方向.另一方 面,如 圖1(b)所示,當(dāng)部分?jǐn)?shù)據(jù)受到噪聲干擾發(fā)生位移時(shí),自然鄰居的篩選結(jié)果不容易改變.這是由于自然鄰居選擇過程需要檢查數(shù)據(jù)雙方相互的近鄰關(guān)系,這一近鄰關(guān)系是基于近鄰位置順序而非直接距離的,因此具有一定穩(wěn)定性.所以基于自然鄰居得到的最優(yōu)密度方向也將是穩(wěn)定的.

圖1 自然鄰居的抗干擾能力Fig.1 Resistance of noise of natural neighbors

在示意圖2中,差向量如紅色箭頭所示.

圖2 差向量Fig.2 Difference vector

獲取差向量后,可進(jìn)一步獲得xi對(duì)應(yīng)的最優(yōu)密度方向向量

差向量 的模標(biāo)識(shí)數(shù)據(jù)間距離的遠(yuǎn)近.式(6)中,將差向量的模取平方是為了確保xi的自然鄰居集合中距離其越近的數(shù)據(jù)對(duì)最優(yōu)密度方向的影響越大.在圖3所示示例中,紅色箭頭表示了xi未歸一化的最優(yōu)密度方向,結(jié)合前文分析可知xi的最優(yōu)密度方向?qū)⒅赶騲i的局部流形方向并且具有穩(wěn)定性,下文將利用最優(yōu)密度方向?qū)i與其最近鄰的位置關(guān)系進(jìn)行縮放,并設(shè)計(jì)縮放因子的大小與噪聲對(duì)數(shù)據(jù)的影響程度相關(guān),進(jìn)而降低噪聲影響,還原數(shù)據(jù)與其近鄰間的原始分布情況.

圖3 未歸一化的最優(yōu)密度方向Fig.3 Unnormalized optimal density direction

3.2 基于最優(yōu)密度方向的距離縮放矩陣

式(8)中:abs(·)表示取絕對(duì)值,|·|表示取向量模,ε為系數(shù)調(diào)節(jié)因子.

圖4 K 近鄰在最優(yōu)密度方向上映射Fig.4 Projection ofK -nearest neighbors on optimal density direction

cosγj的符號(hào)代表了k(→xi)中向量與的方向關(guān)系,這里進(jìn)一步定義符號(hào)函數(shù)sg以區(qū)分同向與反向數(shù)據(jù)

其中sgn(·)表示符號(hào)函數(shù)運(yùn)算.

則xi相對(duì)于xj的密度縮放因子可按照下式計(jì)算:

其中:exp(·)表示指數(shù)運(yùn)算,引入密度縮放因子ρ是為了方便控制沿最優(yōu)密度方向的數(shù)據(jù)間距離的縮放程度,ρ越大縮放程度越劇烈.

遍歷X中所有數(shù)據(jù)后,將得到所有數(shù)據(jù)相對(duì)于其k個(gè)最近鄰的密度縮放因子矩陣DM m×n.X中某一數(shù)據(jù)xi相對(duì)于 其k最近鄰xj的密度縮放因子與xj相對(duì)于xi的密度縮放因子并不相同,故DM為非對(duì)稱矩陣.D M需要按下式進(jìn)行對(duì)稱處理:

使用D M ′對(duì)高維數(shù)據(jù)X數(shù)據(jù)間的無向鄰域距離矩陣D進(jìn)行縮放,可得有向鄰域距離矩陣O M

使用密度縮放因子對(duì)高維數(shù)據(jù)的局部鄰域距離進(jìn)行縮放,會(huì)使得與最優(yōu)密度方向同向的近鄰點(diǎn)之間的距離縮小,且投影向量與最優(yōu)密度方向夾角余弦絕對(duì)值越小或與當(dāng)前高維數(shù)據(jù)點(diǎn)距離越近收縮程度越大;相反的,與最優(yōu)密度方向反向的近鄰點(diǎn)之間的距離會(huì)被放大,且投影向量與最優(yōu)密度方向夾角余弦絕對(duì)值越大或與當(dāng)前高維數(shù)據(jù)點(diǎn)距離越遠(yuǎn)則放大程度越大.圖5示例中展示了數(shù)據(jù)縮放后的距離與圖1所示原始距離的對(duì)比.

圖5 縮放后距離Fig.5 Scaled distance

3.3 ODD–ISOMAP算法步驟

步驟1輸入待處理原始高維數(shù)據(jù)矩陣X,設(shè)定最近鄰集合的個(gè)數(shù)k,設(shè)定密度縮放因子ρ及系數(shù)調(diào)節(jié)因子ε(一般取10?4<ε≤ 10?1),設(shè)定密度縮放因子矩陣DM m×n為全1矩陣.從X中任選一高維數(shù)據(jù)xi作為待處理數(shù)據(jù).

步驟2按 照式 (4) 計(jì) 算xi的自然鄰居集 合ψ(xi).若ψ(xi)為空集,則xi為離群點(diǎn),若實(shí)際情況允許可將xi剔除,否則可將k(xi)視為ψ(xi).

步驟3基于ψ(xi)按照式(5)–(6)獲取xi最優(yōu)密度方向向量

步驟4從中任選一向量,計(jì)算的差向量,按照式(7)–(8)分別計(jì)算差向量與最優(yōu)密度方向向量夾角的余弦cosγj及在上的相對(duì)投 影.重復(fù)此步驟,直到獲取中所有向量與夾角的余弦及所有向量在上的相對(duì)投影集合.

步驟5按照式(9)–(10)計(jì) 算xi相對(duì)于k(xi)中每一個(gè)近鄰數(shù)據(jù)的密度縮放因子.

步驟6將xi相對(duì)于k(xi)的密度縮放因子存入矩陣DM對(duì)應(yīng)位置.從X中任選一沒有處理過的高維數(shù)據(jù),重復(fù)步驟2–5,直到X中所有數(shù)據(jù)被處理完畢.

步驟7按照式(11)對(duì)DM對(duì)稱處理,在獲取有向鄰域距離矩陣D基礎(chǔ)上按照式(12)計(jì)算距離縮放后的有向鄰域距離矩陣OD.

步驟8基于O D使用Dijkstra或Floyd最短路徑算法獲取測(cè)地距離矩陣,最后使用多維尺度變換算法MDS得到原始高維數(shù)據(jù)矩陣X降維后數(shù)據(jù)矩陣Y.

需要說明的是,文中最近鄰及自然鄰居的求取仍然使用歐式距離.而隨著數(shù)據(jù)集維度的增加該距離計(jì)算方式將呈現(xiàn)出一定的弊端.

3.4 ODD–ISOMAP算法復(fù)雜度分析

ODD–ISOMAP算法步驟2中需要計(jì)算原空間數(shù)據(jù)的自然鄰居,應(yīng)用了KD樹優(yōu)化后的自然鄰居選擇時(shí)間復(fù)雜度為O(mlogm)[16].步驟3計(jì)算所有數(shù)據(jù)的最優(yōu)密度方向的復(fù)雜度為O(m).步驟4與步驟5中計(jì)算空間所有數(shù)據(jù)與其k個(gè)最近鄰的差向量、相對(duì)最優(yōu)密度方向夾角余弦和投影以及計(jì)算所有數(shù)據(jù)相對(duì)其k個(gè)近鄰的密度縮放因子的復(fù)雜度均為O(km),故此步驟總體時(shí)間復(fù)雜度為O(4km).步驟6中獲取DM矩陣的復(fù)雜度為O(1).步驟7與步驟8是經(jīng)典的ISOMAP算法步驟,該步準(zhǔn)確復(fù)雜度為O(m3+dm2logm)[17].

故ODD–ISOMAP算法準(zhǔn) 確時(shí)間 復(fù)雜度 為O(m·logm+m+4km+1+1 +dm2logm+m3),考慮到k ? m及d ? m,則ODD–ISOMAP總體時(shí)間復(fù)雜度與經(jīng)典ISOMAP算法的時(shí)間復(fù)雜度大致相同,為O(m3).

另外,經(jīng)典ISOMAP算法中獲取無向鄰域矩陣D(也稱為 構(gòu)建鄰域圖)需要篩 選數(shù)據(jù) 的k個(gè)最近 鄰,ODD–ISOMAP算法中自然鄰居的選取只需要在此基礎(chǔ)上進(jìn)一步篩選出自然鄰居即可,額外付出的計(jì)算單位為 O(m).故相對(duì)經(jīng)典 ISOMAP 算法而言,ODD–ISOMAP 算法中 需要額 外付出 的總體 計(jì)算單元為O(2m+4km+1+1).相比O(m3)的總體時(shí)間復(fù)雜度,ODD–ISOMAP算法付出了較少的額外算力消耗取得了較好的噪聲抗干擾能力.

4 實(shí)驗(yàn)及效果分析

為檢驗(yàn)文章 所提算法的算法降 維效 果,本節(jié)在Swiss roll,Gauss,Iris,Seeds,Wine,Vertebral column-2c,QCM sensor alcohol共7種 數(shù)據(jù)集上對(duì)ODD–ISOMAP算法進(jìn)行了測(cè)試,并將降維效果與其他6種常見降維算 法HLLE,LTSA,LEIGS,LLE,PCA,ISOMAP進(jìn)行了對(duì)比,實(shí)驗(yàn)環(huán)境為MATLAB 2019a.

4.1 測(cè)試數(shù)據(jù)集與評(píng)價(jià)指標(biāo)

7種 數(shù)據(jù) 集中 前2種為人工 合成數(shù)據(jù)集,后5種 來自UCI machine learning實(shí)測(cè)數(shù)據(jù)庫(kù),去除異常值后各數(shù)據(jù)集基本參數(shù)如表1所示.

為直觀展示各算法降維效果,將所有數(shù)據(jù)降維為2維,并使用 統(tǒng)一參 數(shù)設(shè)置 的經(jīng)典K-mediods算法對(duì)第2至7種多類別數(shù)據(jù)集降維后數(shù)據(jù)進(jìn)行聚類分析.由于數(shù)據(jù)集的類別數(shù)量已知,因此若降維算法能夠保持高維數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu),經(jīng)各算法降維后的2維數(shù)據(jù)聚類結(jié)果應(yīng)該與真實(shí)數(shù)據(jù)類標(biāo)相同,否則說明算法降維效果較 差.基于以 上規(guī)律,引入聚 類正確 率指標(biāo)(clustering accuracy,CA)定量描述聚類結(jié)果與數(shù)據(jù)真實(shí)類別相似程度,CA表示為

上式中:yi表示高維數(shù)據(jù)xi映射后對(duì)應(yīng)的低維數(shù)據(jù),[xi,yi]表示高低維數(shù)據(jù)對(duì)的數(shù)據(jù)量,Cp表示類標(biāo),t為數(shù)據(jù)簇類別數(shù)量,m為數(shù)據(jù)簇?cái)?shù)據(jù)的總量.CA表示所有類別中映射前后屬于同一個(gè)類標(biāo)的高低維數(shù)據(jù)對(duì)數(shù)據(jù)量總和與數(shù)據(jù)簇總數(shù)據(jù)量的比值.CA的值介于0到1之間,取值越大表示聚類結(jié)果與高維數(shù)據(jù)真實(shí)類別相似度越高,即算法降維效果越好.

表1 測(cè)試數(shù)據(jù)Table 1 Test datasets

4.2 合成數(shù)據(jù)實(shí)驗(yàn)

Swiss roll數(shù)據(jù)為3維人工合成數(shù)據(jù),常用來進(jìn)行流形降維測(cè)試,本節(jié)為了模擬較大曲率及噪聲對(duì)數(shù)據(jù)的影響,對(duì)1000組Swiss roll數(shù)據(jù)的維度3進(jìn)行了適度壓縮,并添加了60%的隨機(jī)噪聲,最終生成的Swiss roll數(shù)據(jù)如圖6(a)所示.使用本文提出的ODD–ISOMAP算法及其他6種降維算法將該數(shù)據(jù)降為2維,其中各算法近鄰數(shù)k取最優(yōu),各算法降維效果如圖6(b)–6(h)所示.

分析圖6 可 知,在模擬強(qiáng)噪聲和大曲率情況下,HLLE算法降維效果出現(xiàn)了重疊,LTSA,LLE,PCA算法降維效果未能保持 3 維數(shù)據(jù)流形,LEIGS 與 ISOMAP算法 的降維效果受到了一定影 響,只 有ODD–ISOMAP保持了較好的降維效果.

Gauss數(shù)據(jù)為3維5簇人工合成數(shù)據(jù),各數(shù)據(jù)簇邊緣貼近但不重疊,如圖7(a)所示.圖7(b)–7(h)展示了各算法在該數(shù)據(jù)上的降維表現(xiàn),從效果來 看 ODD–ISOMAP算法能夠有效促使各數(shù)據(jù)簇向簇中心靠攏,進(jìn)而減少降維后簇間數(shù)據(jù)重疊度,而其他算法降維后都不可避免的出現(xiàn)了數(shù)據(jù)重疊.

圖6 各算法在Swiss roll數(shù)據(jù)上降維表現(xiàn)Fig.6 Dimensionality reduction performance of each algorithm on Swiss roll dataset

圖7 各算法在Gauss數(shù)據(jù)上降維表現(xiàn)Fig.7 Dimensionality reduction performance of each algorithm on Gauss dataset

為進(jìn)一步研究各算法 對(duì)噪聲的敏感 度差別,對(duì)Gauss數(shù)據(jù)集逐步添加3%至15%的高斯噪聲,統(tǒng)計(jì)各算法在各噪聲幅度下的CA值,如表2所示.圖8以曲線形式展示了Gauss數(shù)據(jù)各算法CA值隨噪聲幅度變化規(guī)律,分析表2與圖8可知,隨著高斯噪聲幅度的增加各算法對(duì)應(yīng)的CA值呈下降趨勢(shì),說明噪聲確實(shí)對(duì)降維效果有負(fù)面影響,但不同算法受影響程度不同.在不同幅度噪聲影響 下ODD–ISOMAP算法的CA值 均高于經(jīng)典ISOMAP算法.表明在最優(yōu)密度方向引導(dǎo)下,噪聲干擾被密度縮放因子有效修正,在一定程度上保持了數(shù)據(jù)間的真實(shí)位置關(guān)系.另外,在噪聲幅度不大于15%情況下,只 有LEIGS與ODD–ISOMAP算法的CA值保持在0.8以上,并且總體來看后者優(yōu)于前者;其他算法均受到了較大影響,其中LLE算法效果最差.從噪聲角度來看,只有在添加3%噪聲時(shí)LEIGS算法降維效果略優(yōu)于ODD–ISOMAP算法,其他情況下后者效果均優(yōu)于其他6種算法,說明盡管噪聲影響了數(shù)據(jù)的原始分布,但是多個(gè)數(shù)據(jù)間近鄰關(guān)系存在一定的穩(wěn)定性,而利用了此規(guī)律的ODD–ISOMAP算法對(duì)噪聲有較好的抵抗能力.

表2 Gauss數(shù)據(jù)值隨CA噪聲變化Table 2 CA values of algorithms vary with noises on Gauss dataset

圖8 Gauss數(shù)據(jù)集各算法CA值隨噪聲變化曲線Fig.8 CA curves of algorithms vary with noises on Gauss dataset

圖9展示了ODD–ISOMAP算法與ISOMAP算法在添加3%高斯噪聲的Gauss數(shù)據(jù)上降維后聚類效果.圖中不同形狀表示原始高維數(shù)據(jù)真實(shí)類標(biāo),不同顏色表示降維后數(shù)據(jù)聚類類標(biāo),紅色圈中數(shù)據(jù)為分類錯(cuò)誤數(shù)據(jù).從圖9 中可看出,相比 ISOMAP 算法,ODD–ISOMAP算法能夠有效放大各數(shù)據(jù)簇間距離,并使各簇?cái)?shù)據(jù)向簇心收縮,從而減少分類錯(cuò)誤,較好保持了高維數(shù)據(jù)原始樣式.

4.3 實(shí)測(cè)數(shù)據(jù)實(shí)驗(yàn)

本節(jié)在優(yōu)化近鄰數(shù)值k、系數(shù)調(diào)節(jié)因子ε和密度縮放因子ρ前提下,對(duì)比了 ODD–ISOMAP 算法與 ISOMAP,HLLE,LTSA,LEIGS,LLE,PCA算法在5類 實(shí)測(cè)數(shù)據(jù)上的降維表現(xiàn).表3統(tǒng)計(jì)了各算法在實(shí)測(cè)數(shù)據(jù)集上的CA值,圖10 至圖14分別展示了各數(shù)據(jù)集上CA值最高的前2種算法降維效果.各圖中不同形狀表示原始高維數(shù)據(jù)的真實(shí)類標(biāo),不同顏色表示降維后數(shù)據(jù)聚類類標(biāo),紅色圈中數(shù)據(jù)為錯(cuò)誤分類數(shù)據(jù).

從圖10來看,對(duì)Iris數(shù)據(jù)降維效果最好的為ODD–ISOMAP算法和ISOMAP算法.對(duì)比圖10(a)與圖10(b)的聚類簇1,可以發(fā)現(xiàn)ODD–ISOMAP算法能夠使真實(shí)簇更加聚集.對(duì)比兩圖聚類簇2–3可知,兩種算法降維后聚類效果均出現(xiàn)了重疊,但ODD–ISOMAP算法能夠使兩個(gè)不同簇沿著各自簇內(nèi)數(shù)據(jù)密集方向收攏,從而減少了錯(cuò)分?jǐn)?shù)據(jù),提高了分類正確率.圖11至圖13展示了Seeds,Wine和Vertebral column2c數(shù)據(jù)集的結(jié)果,獲得了與圖10同樣的結(jié)論.這是由 于ODD–ISOMAP算法能夠根據(jù)高維數(shù)據(jù)的原始分布情況沿最優(yōu)密度方向合理縮放了數(shù)據(jù)間距離,使得降維后各數(shù)據(jù)集同一簇內(nèi)數(shù)據(jù)更加緊密,不同簇間距離更加分散,簇邊緣數(shù)據(jù)向簇內(nèi)靠攏,較好保持了高維數(shù)據(jù)真實(shí)簇分類特征,從而有效改善了聚類效果.圖14 中雖然ODD–ISOMAP,ISOMAP 和 PCA 算法都能在 QCM Sensor Alcohol數(shù)據(jù)上取得極高正確率(CA=1),但是前者通過數(shù)據(jù)縮放功能使得分類效果更加顯著.從表3數(shù)據(jù)角 度來看,在Wine數(shù)據(jù)集 上ODD–ISOMAP算法和HLLE算法均能得到最高 的CA值,其 他數(shù)據(jù)集上ODD–ISOMAP算法的CA值為最高,說明本文所提算法降維效果最好.

為進(jìn) 一步研究各算法對(duì) 噪聲的敏感度差 別,在Seeds數(shù)據(jù)集上逐步添加5%至25%的高斯噪聲,統(tǒng)計(jì)各算法在各噪聲幅度下的CA值,如表4所示.圖15以曲線形式展示了Seeds 數(shù)據(jù)集上各算法CA值隨噪聲幅度變化規(guī)律.從表4據(jù)圖15可以看出,除了在25%強(qiáng)噪聲干擾下 ODD–ISOMAP 算法降 維效果 略低于LTSA算法外;在其他情況下ODD–ISOMAP算法都能保持更好的降維效果.

圖9 Gauss數(shù)據(jù)3%噪聲下降維后聚類效果Fig.9 Clustering effect after dimensionality reduction of Gauss dataset with 3% noise

圖10 Iris數(shù)據(jù)二維映射Fig.10 Two-dimensional maps of Iris dataset

圖11 Seeds數(shù)據(jù)二維映射Fig.11 Two-dimensional maps of Seeds dataset

圖12 Wine數(shù)據(jù)二維映射Fig.12 Two-dimensional maps of Wine dataset

圖13 Vertebral column 2c數(shù)據(jù)二維映射Fig.13 Two-dimensional maps of Vertebral column 2c dataset

圖14 QCM Sensor Alcohol數(shù)據(jù)二維映射Fig.14 Two-dimensional maps of QCM Sensor Alcohol dataset

表3 各算法在多個(gè)實(shí)測(cè)數(shù)據(jù)上的CA值Table 3 CA values of algorithms on difference datasets

表4 各算法在不同噪聲幅度Seeds數(shù)據(jù)上的CA值Table 4 CA values of algorithms vary with noises on seeds dataset

圖15 Seeds數(shù)據(jù)集各算法CA值隨噪聲變化曲線Fig.15 CA curves of algorithms vary with noises on Seeds dataset

5 結(jié)論

由于數(shù)據(jù)的多個(gè)近鄰間的關(guān)系能夠反映數(shù)據(jù)的本質(zhì)分布情況,在一定噪聲的影響下,數(shù)據(jù)與其自然鄰居間的關(guān)系存在一定的穩(wěn)定性,并且由于自然鄰居的獲取過程取決于近鄰數(shù)據(jù)間的相互位置關(guān)系,因此數(shù)據(jù)的自然鄰居一般沿著高維流形方向分布.本文利用了此種規(guī)律引入了最優(yōu)密度方向概念,提出了具有較好噪聲抗干擾能力的ODD–ISOMAP算法.該算法從高維數(shù)據(jù)點(diǎn)的k個(gè)最近鄰中篩選出自然鄰居集合,進(jìn)一步得到了各個(gè)數(shù)據(jù)的最優(yōu)密度方向,此最優(yōu)密度方向指向流形方向且不易受噪聲干擾.之后通過計(jì)算高維數(shù)據(jù)的k個(gè)最近鄰在最優(yōu)密度方向上投影的角度、方向和長(zhǎng)度,獲取各近鄰數(shù)據(jù)相對(duì)高維數(shù)據(jù)距離的密度縮放因子.此密度縮放因子的大小與噪聲對(duì)數(shù)據(jù)的影響程度密切相關(guān),因此使用該密度縮放因子對(duì)數(shù)據(jù)間的局部鄰域距離進(jìn)行縮放,能夠在一定程度上還原數(shù)據(jù)與其近鄰間的原始分布情況,從而降低噪聲對(duì)降維過程 的影響.在實(shí)驗(yàn) 環(huán)節(jié)對(duì)比了 ODD–ISOMAP算法與ISOMAP,HLLE,LTSA,LEIGS,LLE和PCA算法在2類人工合成數(shù)據(jù)集和5類實(shí)測(cè)數(shù)據(jù)集上的降維表現(xiàn),并測(cè)試了各算法在不同噪聲壓力下的降維性能,驗(yàn)證了本文所提算法的實(shí)用性和有效性.