降維(數(shù)據(jù)庫)

時(shí)間：2022-12-30 06:30:01 | 來源：信息時(shí)代

時(shí)間：2022-12-30 06:30:01 來源：信息時(shí)代

    降維 : 將高維多媒體數(shù)據(jù)的特征向量映射到一維或者低維空間的過程。在高維特征數(shù)據(jù)庫中,高維數(shù)據(jù)存在數(shù)據(jù)冗余。由于索引結(jié)構(gòu)的性能隨著維數(shù)的增大而迅速降低,在維數(shù)大于10以后,性能還不如順序掃描,形成維數(shù)災(zāi)難(dimensional curse)。降維后,應(yīng)用成熟的低維索引技術(shù),以提高性能。降維技術(shù)可以有效地解決維數(shù)災(zāi)難問題,但是,在降維過程中也可能引起信息丟失,從而影響查詢精度,這是采用降維技術(shù)時(shí)必須關(guān)注的問題。降維技術(shù)是高維數(shù)據(jù)管理領(lǐng)域的研究熱點(diǎn)之一,開始于20世紀(jì)90年代中期,除以下介紹的屬于特征抽取的降維方法外,還有空間填充曲線(space filling curve)、奇異值分解(SVD)、距離映射算法(distance-mapping algorithm)、FastMap算法、pyramid算法等。
1.基于低維投影的降維方法
(1)主成分分析(principal component analysis,PCA): 是使用最為廣泛的線性降維方法之一,它先將數(shù)據(jù)投影到某一個(gè)主成分上,然后丟掉具有較小方差的那些維的信息,尋找具有最大方差的線性特征集,達(dá)到降維的目的。該方法的概念簡單、計(jì)算方便,但是,沒有統(tǒng)一的標(biāo)準(zhǔn)來確定主成分及其數(shù)量。
(2)投影法(projection pursuit,PP):其基本思想是將高維數(shù)據(jù)投影到低維(一般是1～3維)子空間上,通過分析和研究投影數(shù)據(jù)以達(dá)到了解原始數(shù)據(jù)的目的。該方法最早產(chǎn)生于20世紀(jì)70年代初,Kruskal將數(shù)據(jù)投影到低維空間,通過極大化某個(gè)指標(biāo),以發(fā)現(xiàn)數(shù)據(jù)的聚類結(jié)構(gòu)。聚類效果取決于索引函數(shù)的選擇和優(yōu)化算法。該方法可有效排除噪聲數(shù)據(jù)的干擾,但是,計(jì)算量大,不適用于高度非線性數(shù)據(jù)。
2.基于神經(jīng)網(wǎng)絡(luò)的降維方法
(1) 自動(dòng)編碼神經(jīng)網(wǎng)絡(luò)法(auto-encoder networks):是一種前向反饋網(wǎng)絡(luò)。該網(wǎng)絡(luò)把高維空間的輸入向量映射到具有最少神經(jīng)元的一層的激勵(lì)所表示的低維空間中,而具有最少神經(jīng)元的一層的下一層再把低維表示映射到D維空間。
(2) 自組織映射法(self-organizing mapping):對每個(gè)聚類都賦予降維后的空間中的固定位置,并根據(jù)該位置用鄰居函數(shù)來評價(jià)聚類之間的近似度。鄰居函數(shù)的值越大聚類之間的接近程度越高。根據(jù)鄰居函數(shù)值,高維數(shù)據(jù)被映射到最優(yōu)聚類的位置,實(shí)現(xiàn)高維數(shù)據(jù)的降維。該方法能很好地用于高維數(shù)據(jù)可視化。
(3)生成建模法(generative modelling): 是基于混合密度估計(jì)的,所有的聚類都用高斯混合密度表示。
3. 基于數(shù)據(jù)間相關(guān)度的降維方法
(1)多維比例法(multi-dimensional scaling): 是尋找保留了數(shù)據(jù)主要特征的低維空間,在該空間里的數(shù)據(jù)點(diǎn)不僅和高維空間中的原數(shù)據(jù)對應(yīng),并且保持原數(shù)據(jù)點(diǎn)之間的歐式距離的差異度。適用于原始數(shù)據(jù)的距離矩陣已知的情況。
(2) 隨機(jī)鄰居嵌入法(stochastic neighbor embedding): 不直接使用數(shù)據(jù)間的差異,而是用它們定義轉(zhuǎn)換矩陣,該矩陣的每一行都包含了與一個(gè)數(shù)據(jù)點(diǎn)相關(guān)聯(lián)的分布,該矩陣則定義了數(shù)據(jù)點(diǎn)集上的隨機(jī)遍歷。
(3)等容積法(isometric mapping): 是對多維比例法的擴(kuò)展,區(qū)別在于采用測地距離表示兩點(diǎn)的差異。
(4)局部線性嵌入法(locally linear embedding):是非線性降維方法,其中高維空間由許多描述它的本質(zhì)屬性并且相互鄰接的局部線性塊組成。該方法有效地獲取高維數(shù)據(jù)的本質(zhì)特征,計(jì)算方法簡單、直觀。
(5) 拉普拉斯特征映射法(Laplacian eigen maps):拉普拉斯特征映射法首先將數(shù)據(jù)點(diǎn)與其最近鄰居連接起來以構(gòu)建一個(gè)鄰居圖,然后給圖的每條邊均賦予相應(yīng)的權(quán)值,最后尋求數(shù)據(jù)集的嵌入坐標(biāo)表示,并保證嵌入點(diǎn)之間的平方距離最小,從而得到降維空間中的最優(yōu)低維表示向量。
4.基于分形的降維方法
如果一個(gè)數(shù)據(jù)集的部分分布結(jié)構(gòu)或?qū)傩耘c整體分布相似,則稱該數(shù)據(jù)集是分形的。基于分形的降維方法首先要比較準(zhǔn)確地估計(jì)出數(shù)據(jù)的本征維,包括分?jǐn)?shù)維,進(jìn)而進(jìn)行降維處理。