[發明專利]基于稀疏降維的譜哈希索引方法

無效

• 申請號: 201010196539.0
• 申請日: 2010-06-08
• 公開（公告）號: CN101894130A
• 公開（公告）日: 2010-11-24
• 發明（設計）人: 吳飛;張嘯;邵健
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 張法高

技術領域

本發明涉及圖像搜索方法，尤其涉及一種基于稀疏降維的譜哈希索引方法。

背景技術

隨著互聯網的不斷發展，傳統圖像搜索方法中索引機制已很難滿足用戶高層次需求，以指數級迅猛增長的海量數據給提高搜索引擎效率帶來了巨大挑戰。

當前，海量圖像數據呈現高維、多階特性。對于給定的互聯網圖像數據，其中提取的視覺特征等動輒成百上千，這些高維數據給圖像的相似度計算和語義分析帶來了諸多困難。

為了提高高維圖像數據處理效率，下述三種方法被廣泛研究，成為國際國內學術熱點：

1)流形學習。近來，研究者已普遍認識到數據所具有高維特征本質上被有限自由度決定，分析數據幾何拓撲分布結構不僅能優化數據間相似性計算，也能夠大大降低計算復雜度，這一方面代表性工作是“流形學習”。流形學習理論通過構建離散數據間形成的相鄰圖，應用譜分析手段獲得高維特征內嵌子空間，包括等距映射(ISOMAP)、局部線性嵌入(LLE)和保局投影(LPP)等代表性方法。作為一種有效的高維降維手段，流形學習在圖像語義理解和計算機視覺等領域得到了深入研究和廣泛應用。

2)變量選擇(Variable?Selection)。在數據分析過程中，當樣本特征維數遠遠大于樣本數目時，傳統方法難以準確進行數據預測與識別，斯坦福大學Tibshirani和加州大學伯克利分校Breiman幾乎同時提出了對特征系數施以l₁-范式約束的lasso(least?absolution?shrinkage?and?selection?operator)思想，促使被選擇出來的特征盡可能稀疏，以保證結果穩定性和提高數據處理過程的可解釋性(interpretable)。由于從圖像中可提取特征眾多，如何從高維數據中尋找有效稀疏表達，在稀疏表達基礎上理解圖像所蘊含語義，成為當前計算機視覺和模式識別領域一個發展趨勢。

3)高維索引。與海量環境中文本檢索可以按照字典序通過倒排表和Pat數組等模型進行高效索引不同，從多媒體數據提取的無序高維特征難以進行以字典序為基礎高效索引。目前以R樹、K-D-B樹及X樹等樹形結構為代表的多維索引技術雖然取得了一些進展，然而研究表明：大多數多維索引結構的時間開銷為指數級，不適合維數過高的情況(比如幾十維)，其查詢效率甚至低于對原始數據進行順序掃描的查詢效率。同時，如何保證數據的語義索引(SemanticHashing)，即在索引空間中所計算相似度與在原始高維空間中所計算相似度保持一致，成為熱點問題。

如何利用機器學習方法實現高維數據的“語義索引”。

為了提高高維數據相似度匹配的效率，一些索引方法被相繼提出。

在這一方面，LSH(Locality?Sensitive?Hash)是一種代表性的高維特征索引技術。LSH通過一組哈希函數的映射結果達到高維索引目的。在LSH中，所使用的哈希函數必須滿足如下條件：任意兩個高維數據通過哈希函數作映射時發生沖突概率正比于數據點在原始高維空間之間距離。這樣，任意兩個相似的高維數據通過哈希函數會以很大概率被分配到哈希表中同一項中。由于LSH是基于概率模型產生編碼，在實際應用中難以保證穩定的表現，往往會產生令人難以滿意的結果。從圖1可以看出，隨著編碼位數的上升，LSH的準確率提升比較緩慢，而迭代收斂的速度也可能非常慢。

機器學習的思路被引入索引方法后產生了RBM(restricted?Boltzmannmachine——RBM)和stump?Boosting?SSC等方法。RBM利用一種兩層無向圖形學的模型，產生RBM機來處理指數型分布族。該模型最底層代表原空間向量，最高層代表得到的數據二進制編碼，最頂上的兩層形成了一個無向兩偶圖，其余層形成了一個有向的自上而下聯系的信念網絡。每層均通過訓練RBM機，得到隱藏變量。預處理完，每一層各自的RBM展開用以建立一個深的自動編碼器。如果隨機的二進制特征活動是確定的、實值概率，那么我們可以通過整個網絡反向傳播來微調計數數據的最佳重建的權重。為了讓編碼成為二進制編碼，可從底層向高層的輸入加入高斯噪聲，由每個編碼單元接受。圖1顯示了RBM相較于LSH有更好的表現。將RBM應用于海量數據檢索，可較之LSH取得幾個數量級的效率提高。但是由于RBM自身方法的復雜性，在保證精確的同時大大地犧牲了效率。