維數(shù)約減算法研究及其在大規(guī)模文本數(shù)據(jù)挖掘中的應(yīng)用.pdf

1、隨著網(wǎng)絡(luò)的快速發(fā)展，人們處在這個“信息爆炸”的時代，常常面對海量數(shù)據(jù)分析和處理的任務(wù)，且這樣的數(shù)據(jù)仍在以幾何級數(shù)增長。同時，在現(xiàn)實中這些海量數(shù)據(jù)往往又是高維而稀疏的，且存在著大量的冗余。因而能對高維海量數(shù)據(jù)做壓縮處理，且保持其內(nèi)在屬性的有效處理方法成為人工智能、機器學(xué)習、數(shù)據(jù)挖掘等領(lǐng)域的重要研究課題之一。高效的維數(shù)約減算法是對高維海量數(shù)據(jù)處理的一種有效方法，且具有一定的實際應(yīng)用價值。本文的關(guān)注點集中在適用于高維海量數(shù)據(jù)的快速維數(shù)約減算法

2、的研究及其具體應(yīng)用。 本文分別提出了兩種新的維數(shù)約減算法：（1）基于期望擾動的直接隨機映像算法（On the Expected Distortion Bound of Direct Random Projection，簡稱DRP）；（2）基于錨點集的最小平方誤差等距嵌入算法（Anchor points based Isometric Embedding under least square error criterion，簡稱A

3、IE）。 基于期望擾動的直接隨機映像算法DRP具有O（dn）的時間復(fù)雜性，這樣的性能評價是建立在對期望擾動分析的基礎(chǔ)上的。并證明了1）DRP算法的期望擾動的界。2）在適當?shù)慕o定條件下，可在O（1）的隨機時間內(nèi)找到一個將期望擾動限定在一個合適范圍之內(nèi)的DRP映像。進而提出了一種獲得中肯DRP的啟發(fā)式算法。此算法具有穩(wěn)固的漸進加速比，相對于其他隨機映像算法具有更好的穩(wěn)定性。而且在流數(shù)據(jù)模式下，可采用增量策略，DRP算法的時間復(fù)雜性為

4、O（d log d）。 基于錨點集的最小平方誤差等距嵌入算法AIE具有O（n log（n））的時間復(fù)雜性，而且在獲得測地線距離后的計算時間復(fù)雜度達到對嵌入點數(shù)的線性關(guān)系，且可以完全并行實現(xiàn)。與Isomap、LLE等非線性維數(shù)約減算法相比較，具有更優(yōu)化的時間復(fù)雜性。 當前主流的搜索引擎根據(jù)查詢詞在網(wǎng)頁中的出現(xiàn)頻率，輔以網(wǎng)頁權(quán)威性等信息，生成查詢結(jié)果。但用戶提供的查詢詞往往非常簡單，在許多情況下，搜索引擎難以確定用戶的查詢意