用於近似查詢的長序列數據降維方法

2023-04-24 19:07:41

專利名稱：用於近似查詢的長序列數據降維方法
技術領域：
本發明涉及一種用於近似性查詢的長序列數據降維方法，尤其是一種支持高效長序列近似性查詢的序列嵌入(Sequential Embedding)方法，屬於計算機數據管理技術領域。

背景技術：
長序列數據存在於各個科學研究和應用領域，如網際網路上的文本數據、生物領域的基因序列數據等。面向這些長序列數據的近似性查詢，具有十分廣泛的應用需求。如網際網路文本數據的搜索、基因資料庫中基因的相似性探索，以及多媒體領域的序列查詢等。基於長序列數據的近似性查詢已經成為國際數據管理研究領域關注的問題。
目前已存在一些方法和技術支持序列的近似性查詢，但是這些技術在處理序列數據之間的相似性時，多採用傳統的編輯距離度量方法，其效率很低(O(n2)級)，一般而言僅適用於短序列數據集上的近似性查詢。目前，長序列數據之間的相似性度量已經成為制約長序列數據集近似性查詢性能提高的最主要瓶頸問題之一。在傳統的查詢領域，降維技術(如PCA方法)被認為是解決高維數值數據空間近似性查詢效率問題的重要途徑，但該方法並不適用於序列數值環境。目前為止，尚無文獻提出面向長序列數據領域的降維方法，用於支持高效的長序列數據相似性查詢問題。
現有的技術還不能有效解決長序列數據近似性查詢所需要的降維問題，具體如下 首先，傳統的面向高維矢量數據空間的降維(如PCA)方法無法應用於長序列數據集，因為序列數據沒有清晰明確的維度定義； 其次，目前雖然提出了基於參考點的序列數據集空間縮減方法[Reference-based Indexing of Sequence Databases，VLDB』06]，但其本質是通過參考序列數據構造索引查詢空間，從而降低索引查詢空間的範圍，提高查詢的效率，並沒有從序列的本身解決降維的問題。而且這類方法依然無法避免序列之間相似性度量複雜性高的問題，不具有解決問題的普遍性和本質性特徵。
傳統索引方法不能有效解決序列相似性查詢問題。文獻[The X-treeAn indexStructure for High-Dimensional Data，VLDB』96]提出了利用索引樹支持相似性查詢，但是這類方法只在序列長度小於20時才有效，無法解決長序列查詢的問題。
文獻[Linear Pattern Matching Algorithms，IEEE Symposium on Switching andAutomata Theory]提出了通過建立後綴樹提高序列近似性查詢的效率，該方法目前在很多領域得到廣泛應用。但是，該方法的最大缺點是耗費大量的空間，不具有降維方法所特有的空間壓縮性特點。
文獻[Fast MapA fast algorithm for indexing，data mining and visualization oftraditional and multimedia datasets，SIGMOD』95]提出了通過掃描所有序列數據集構造嵌入空間來構造索引支持近似性查詢。但是由於在原始序列空間的距離相似性度量的複雜性，使得構造該嵌入空間的複雜性過高而不可行。
從上面的分析可以看出，目前存在的支持長序列數據進行相似性查詢的方法不能很好的解決當前實際應用中面臨的技術難題，迫切需要提供一種高效的、面向長序列數據的高效降維方法，用於支持長序列數據的相似性查詢。


發明內容
本發明所要解決的技術問題在於提供一種與傳統降維方法功能類似、但卻能服務於長序列數據的高效降維方法，基於該方法可以構造出高效的面向長序列數據近似性查詢的索引結構和查詢方法，填補目前長序列數據近似查詢中面臨的「降維」難題。
本發明解決其技術問題所採用的技術方案是 步驟一、利用序列嵌入技術，把一個輸入的長序列數據轉化為一棵序列嵌入樹(Sequence Embedding Tree)； 步驟二、從序列嵌入樹中，從每一層抽取出由字符序列所組成的字符多集集合，並利用所提出的距離收斂性質，構造多集空間所對應的主成份； 步驟三、在所提出的多集主成份和距離收斂性質的基礎上，構造一個與多集主成份對應的索引結構； 步驟四、基於所提出索引結構基礎上，提出序列距離的雙邊界(距離上界和下界)原理，並提出相應的近似性查詢算法，完成基於序列降維的長序列高效查詢。
本發明提出基於序列嵌入的長序列降維方法，通過構造一棵序列嵌入樹，把長序列從有序的序列空間轉換到了無序的多集集合空間。並根據嵌入樹構造序列降維所需的各個多集主成份，並提出了主成份間距離計算的收斂性質。基於序列降維基礎上構造的索引結構和近似性查詢算法，可以高效的完成長序列的近似性計算問題。
長序列數據的廣泛存在和基於長序列數據近似查詢的廣泛應用，為本專利提供了很廣闊的應用前景和市場空間。目前，隨著基因技術和網際網路技術的快速發展，都迫切需要解決長序列數據的近似查詢問題，如從海量的網際網路文本數據中通過相似性搜索找到查找的目標，從大規模基因數據中對基因片段進行的相似性查詢與分析等。本發明在這些新興高產值領域中的應用，不僅能解決目前遇到的相似性查詢性能瓶頸的難題，而且預見能夠取得明顯的經濟效益和社會效益。



圖1為本發明的長序列嵌入過程圖(嵌入樹)； 圖2為本發明的索引結構圖； 圖3為本發明的索引樹構造過程示意圖； 圖4為本發明的查詢過程示意圖； 圖5(a)、(b)為本發明的基於距離雙邊界的查詢過濾圖； 圖6為本發明的處理過程流程圖。
下面結合附圖和實施例對本發明進一步說明。

具體實施例方式 本發明是針對當前長序列數據近似性查詢效率低下的瓶頸問題而提出的一種解決長序列數據之間相似性度量的序列數據降維方法，它是基於序列嵌入的原理把長序列從有序的序列空間轉換到多集表示的集合空間，並利用所提出的多集主成份距離收斂性原理，給出了序列降維的方法。基於長序列降維原理基礎上，定義了索引結構，並給出了高效的近似性查詢算法。
本發明方法，首先利用序列嵌入技術，把一個輸入的長序列數據轉化為一棵序列嵌入樹(Sequence Embedding Tree)；然後從序列嵌入樹中，從每一層抽取出由字符序列所組成的字符多集集合，並利用所提出的距離收斂性質，構造多集空間所對應的主成份；接下來在所提出的多集主成份和距離收斂性質的基礎上，構造一個與多集主成份對應的索引結構；最後基於所提出索引結構基礎上，提出序列距離的雙邊界(距離上界和下界)原理，並提出相應的近似性查詢算法，從而實現了基於序列降維的長序列高效查詢。
本發明所述的序列嵌入技術與序列嵌入樹，結合圖1為例描述如下對於一個序列S＝cabagehcadbba，標記為ET1(S)，通過一次迭代可以被分解為六個塊，每個塊由2到3個字符組成，標記為ET1(S)[cs，ce]，cs和ce分別表示該塊的開始和結束字符。每個塊ET1(S)[cs，ce]可以通過一個一對一的Karp-Miller哈希函數映射為一個元素。因此，在ET1(S)中所有塊經哈希映射所得到的元素所組成的序列得到一個新的序列，標記為ET2(S)。例如，塊ET1(S)[ca]可以通過哈希函數映射為單個元素k，所有ET1(S)中的元素通過哈希函數映射可以得到新的序列ET2(S)＝komkna。利用同樣的原理，重複上述過程，可以得到圖1所示的序列嵌入樹。
基於嵌入樹的基礎上，可以得到相應的多集集合和相應的用於序列降維的多集主成份，描述如下對於給定的一個序列ET(S)，在對應的序列嵌入樹中的所有字符組成一個多集集合，標記為T(S)。序列嵌入樹中第i層序列ETi(S)所組成的多集標記為Ti(S)。因此，對於圖1中的序列嵌入樹所對應的嵌入子序列和多集可表示為ET(S)＝{ET1(S)，ET2(S)，ET3(S)，ET4(S)}＝{{cabagehcadbba}，{komkno}，{pqr}，{z}}，T(S)＝{T1(S)，T2(S)，T3(S)，T4(S)}＝{{a4，b3，c2，d1，e1，g1，h1}，{k2，m1，n1，o2}，{p1，q1，r1}，{z1}}。其中a4表示該集合中包含4個元素a，序列嵌入過程的複雜性是線性的。
基於多集的序列距離收斂性質定義如下對於任意給定的兩個序列S1和S2，和任意兩個整數i和j，i≤j，滿足如下性質 其中， 基於多集距離收斂性質的基礎上，可以構造出支持序列近似性查詢的索引結構SEM-tree，如圖2所示。SEM-tree結構描述如下SEM-tree是一個多層多節點的樹形結構，每一層的每個索引節點採用相應的多集表示。越靠近根節點的索引節點對應的多集越小，靠近葉節點的索引節點對應的多集越大。也就是說索引中第i層索引節點對應的多集為Ti(S)。葉節點對應相應的序列S。SEM-tree可以整個序列空間劃分成為若干小的聚類空間，然後隨著索引向下遞歸進行，基於多集距離收斂性質的基礎上，查找的索引空間越來越來，直至在葉節點找到所需的序列。
SEM-tree的構造過程如圖3所示，描述如下 表1長序列數據集SD 步驟30把所有需要處理的序列集合SD(如表1所示)，利用前述的序列嵌入技術轉換成為多集集合MS，並初始化SEM-tree的根節點root； 步驟31、如果當前多集空間的規模可以被一個頁塊裝下，則可以直接把該多集集合作為葉節點進行處理；否則把生成一個新的內部節點，並用聚類算法基於當前多集基礎上進行聚類，把多集空間合理的劃分為若干個小的子空間； 步驟32、對於每個經聚類得到的多集子空間，選取子空間中一個多集作為代表，作為該子類索引節點的索引鍵，以該聚類所對應的半徑作為該索引空間的索引半徑； 步驟33對於每個索引子集合，重複上述步驟，直至SEM-tree生成。
如圖4所示，在所構造的索引結構SEM-tree的基礎上，對於給定的查詢序列q和查詢半徑r，序列查詢的目的是在序列集合當中找到所有的距離序列q的距離小於r的序列的集合。查詢過程可描述如下 步驟40首先，利用嵌入技術把序列q轉化為具有多個主成份的多集集合； 步驟41、對於SEM-tree中當前訪問的節點(假設為N)中的任意以cv(以多集主分表示)為中心點標識的子類而言，如果cv與Ti(q)之間距離的下界大於給定查詢半徑r，則該cv被過濾掉，如圖5(a)所示； 步驟42、否則，如果cv與Ti(q)之間距離的上界小於等於給定查詢半徑r，則以cv為根的子樹所對應的所有索引序列，都屬於最終查詢的結果，無序對該子樹進行進一步的遞歸嵌套查詢，如圖5(b)所示； 步驟43、如果上述兩個條件都沒有滿足，則需要對該序列遞歸嵌套查詢，在以cv為根的子樹的內部節點，繼續利用上述方法進行遞歸查詢； 步驟44如果當前訪問的節點是葉子節點，則直接進行距離計算，確定該葉節點所對應的序列是否應該歸屬到最終的查詢結果當中。
在步驟41和步驟42中所述的雙邊界採用如下的方法進行確定 根據序列嵌入理論，對於給定序列s1和s2，它們之間的距離滿足如下關係 其中，n＝max(|s1|，|s2|)，m＝max(card(T(s1))，card(T(s2))) 因此，對於給定的序列s1和s2，它們之間的真實距離

可以在索引樹的第i層節點預測其距離的上界和下界，近似結果如下 圖6給出了本發明的處理流程，描述如下接受輸入的長序列數據集，基於序列嵌入技術進行序列嵌入處理，得到以多集形式表述的多集集合；然後在此基礎上提取多集主成份，形成具有降維特性的序列距離收斂性質；在此基礎上，構造索引結構，在用戶的提供的參數基礎上，執行近似性查詢，輸出最終的查詢結果。
本發明用於對任意序列集合(尤其適用於長序列集合)進行高效的近似性查詢，給出了用於長序列距離相似性度量的高效面向序列數據的高效降維方法，該方法的特徵是把距離計算從有序的、代價昂貴的序列空間轉化到了無序的、空間有效的、計算代價很低的集合空間，而且在以多集集合表示的主成份之間，發現了支持降維特徵的距離計算收斂性質。基於該降維技術的基礎上，發明了高效的索引結構和基於高效雙邊界過濾的查詢方法，從而達到了序列數據高效近似性查詢的目的。
最後所應說明的是以上實施例僅用於說明而非限制本發明的技術方案，儘管參照上述實施例對本發明進行了詳細說明，本領域的普通技術人員應當理解依然可以對本發明進行修改或者等同替換，而不脫離本發明的精神和範圍的任何修改或局部替換，其均應涵蓋在本發明的權利要求範圍當中。
權利要求
1.一種面向近似性查詢的長序列數據降維方法，其特徵是包括如下步驟
步驟一、利用序列嵌入技術，把一個輸入的長序列數據轉化為一棵序列嵌入樹；
步驟二、從序列嵌入樹中，從每一層抽取出由字符序列所組成的字符多集集合，並利用所提出的距離收斂性質，構造多集空間所對應的主成份；
步驟三、在所提出的多集主成份和距離收斂性質的基礎上，構造一個與多集主成份對應的索引結構；
步驟四、基於所提出索引結構基礎上，提出序列距離的雙邊界距離上界和下界原理，並提出相應的近似性查詢算法，完成基於序列降維的長序列高效查詢。
2.根據權利要求1所述的一種面向近似性查詢的長序列數據降維方法，其特徵是對於一個序列S，標記為ET1(S)，通過一次迭代可以被分解為6個塊，每個塊由2到3個字符組成，標記為ET1(S)[cs，ce]，cs和ce分別表示該塊的開始和結束字符；每個塊ET1(S)[cs，ce]通過一個一對一的Karp-Miller哈希函數映射為一個元素；因此，在ET1(S)中所有塊經哈希映射所得到的元素所組成的序列得到一個新的序列，標記為ET2(S)；利用同樣的原理，重複上述過程，可以得到最終的序列嵌入樹。
3.根據權利要求1所述的一種面向近似性查詢的長序列數據降維方法，其特徵是所述步驟二，包括如下步驟
步驟21、把序列嵌入樹中的所有字符組成一個多集集合，標記為T(S)；
步驟22、把多集集合T(S)按照其元素在嵌入樹中所述的層次，分拆成為h(h為嵌入樹的高度)個子多集集合Ti(S)，Ti(S)中的每個元素與嵌入樹中第i層的每個元素一一對應，表示為{Ti(S)|Ti(S)T(S)，i≤h}；每個Ti(S)構成序列S的第i個主成份；
步驟23、利用得到的多集主成份，構造出支持序列降維的距離收斂性質。
4.根據權利要求3所述的一種面向近似性查詢的長序列數據降維方法，其特徵是所述步驟23，包括
基於多集主成份的距離收斂性質定義如下對於任意給定的兩個序列S1和S2，和任意兩個整數i和j，i≤j，滿足如下性質
其中，
5.根據權利要求1所述的一種面向近似性查詢的長序列數據降維方法，其特徵是所述步驟三，包括如下步驟
步驟31把所要處理的序列集合SD利用序列嵌入技術轉換成為具有多個主成份的多集集合MS，並初始化SEM-tree的根節點root；
步驟32、如果當前多集空間的規模可以被一個頁塊裝下，則可以直接把該多集集合作為葉節點進行處理；否則把生成一個新的內部節點，並用聚類算法基於當前多集基礎上進行聚類，把多集空間合理的劃分為若干個小的子空間；
步驟33、對於每個經聚類得到的多集子空間，選取子空間中一個多集作為代表，作為該子類索引節點的索引鍵，以該聚類所對應的半徑作為該索引空間的索引半徑；
步驟34對於每個索引子集合，重複上述步驟，直至SEM-tree生成。
6.根據權利要求1所述的一種面向近似性查詢的長序列數據降維方法，其特徵是所述步驟四，包括如下步驟
步驟41對於給定的查詢序列q和查詢半徑r，序列查詢的目的是在序列集合當中找到所有的距離序列q的距離小於r的序列的集合；首先，利用嵌入技術把序列q轉化為具有多個主成份的多集集合；
步驟42、對於SEM-tree中當前訪問的節點(假設為N)中的任意以cv(以多集主分表示)為中心點標識的子類而言，如果cv與Ti(q)之間距離的下界大於給定查詢半徑r，則該cv被過濾掉；
步驟43、如果cv與Ti(q)之間距離的上界小於等於給定查詢半徑r，則以cv為根的子樹所對應的所有索引序列，都屬於最終查詢的結果，無序對該子樹進行進一步的遞歸嵌套查詢；
步驟44、如果上述兩個條件都沒有滿足，則需要對該序列遞歸嵌套查詢，在以cv為根的子樹的內部節點，繼續利用上述方法進行遞歸查詢；
步驟45如果當前訪問的節點是葉子節點，則直接進行距離計算，確定該葉節點所對應的序列是否應該歸屬到最終的查詢結果當中。
7.根據權利要求6所述的一種面向近似性查詢的長序列數據降維方法，其特徵是所述步驟42和步驟43，包括如下步驟根據序列嵌入理論，對於給定序列S1和S2，它們之間的距離滿足如下關係
其中，n＝max(|S1|，|S2|)，m＝max(card(T(S1))，card(T(S2)))；
因此，對於給定的序列S1和S2，它們之間的真實距離
可以在索引樹的第i層節點預測其距離的上界和下界，結果如下
全文摘要
一種面向近似性查詢的長序列數據降維方法，包括利用序列嵌入技術把序列數據轉化為嵌入樹，並抽取出多集集合；根據嵌入樹和多集集合提取出相應的多集主成份，並在此基礎上提出了基於距離收斂的序列數據降維原理；基於降維性質的基礎上，構造出了面向序列近似查詢的索引結構，SEM-tree，並基於該索引結構基礎上，利用序列距離雙邊界(最大上界和最小下界)原理，提出了高效的面向長序列數據的近似性查詢方法。本發明可以廣泛的應用於面向長序列數據的近似查詢應用中，如從海量的網際網路文本數據中通過相似性搜索找到查找的目標，從大規模基因數據中對基因片段進行的相似性查詢與分析等。本發明而且預見能夠取得明顯的經濟效益和社會效益。
文檔編號G06F17/30GK101196921SQ20071030398
公開日2008年6月11日 申請日期2007年12月24日 優先權日2007年12月24日
發明者宋國傑, 謝昆青 申請人:北京大學