度量空間中逐個支撐點數據劃分方法
2023-10-08 12:07:09
度量空間中逐個支撐點數據劃分方法
【專利摘要】本發明公開一種度量空間中逐個支撐點數據劃分方法，在建立索引時，從數據集內根據起始和終止位置截取需要處理的數據；選擇一種支撐點優化方法，確定支撐點使用次序；選擇一種數據劃分方法，逐個支撐點進行數據劃分；確定每個劃分的上界與下界；確定每個劃分到每個支撐點的距離值的上界與下界；返回劃分結果。減少了搜索時與數據集的比較次數，從而提高了相似性搜索效率。
【專利說明】度量空間中逐個支撐點數據劃分方法
【技術領域】
[0001] 本發明屬於計算機軟體領域，涉及度量空間，相似性搜索和數據挖掘，尤其涉及一 種度量空間中逐個支撐點數據劃分方法。
【背景技術】
[0002] 基於內容的相似性搜索是一種重要的信息檢索類型，廣泛存在於資料庫和數據挖 掘應用中。隨著多媒體技術的發展和推廣普及，基於複雜數據對象（空間數據、文本、圖像、 音頻、視頻、時空序列等）的海量資料庫不斷湧現，相似性搜索已經成為多媒體信息系統基 於內容搜索的基本需求，其性能已經成為衡量多媒體系統查詢功能的重要指標。同時，近年 來生物信息學的蓬勃發展也產生了龐大的複雜生物數據（基因序列、蛋白質譜等），對這些 數據的高效搜索已經成為一個迫切需要解決的問題。據統計，相似性搜索在整個計算生物 學研究任務中所佔比例高達35 %。
[0003] 度量空間索引是一種適用性非常廣的解決相似性搜索的方法。它把複雜的數據對 象抽象成度量空間中的點，利用用戶定義距離函數的三角不等性來去除無關數據並減少直 接距離計算的次數，以實現高速搜索。度量空間索引只要求用戶提供滿足度量空間性質的 距離函數，而距離函數的具體實現和數據的表達都是透明的，同樣的算法可以應用於不同 的數據，因而具備了更廣泛的適用範圍。近年來，多媒體技術的推廣應用和生物學研究的蓬 勃發展產生了大量新型的多媒體和生物數據，度量空間索引技術也因為其不斷體現出的普 遍適應性成為一個國內外較為熱門的研究領域。
[0004] 度量空間索引也被稱為基於距離的索引，主要用於相似性搜索。距離函數是它唯 一需要的相似性定義。樹結構是最流行的度量空間索引結構的一種，在建樹過程中包括了 選取支撐點和逐個支撐點數據劃分兩個步驟。
[0005] 目前，應用與度量空間的樹結構包括BKT(Burkhard-Keller Tree)，FQT(Fixed Queries Tree)，VPT (Vantage Point Tree)和 MVPT (Multi-Vantage Point Tree)等等，在 度量空間建樹的過程中，需要遞歸的根據數據點到給定支撐點的距離進行數據劃分。其中， 支撐點的選擇和數據劃分方法，直接影響了索引的建立，從而影響到相似性搜索的效率。
[0006] 度量空間中支撐點如何選取及數據如何逐個支撐點進行劃分對建立索引具有極 其重要的作用。
[0007] 通過FFT或者Incremental等方法選取的支撐點集合，在逐個支撐點進行數據劃 分時，支撐點使用的順序對相似性搜索的效率具有一定的影響，但是，目前並沒有方法針對 這個問題，提出解決方案；與此同時，數據劃分方法的選擇，也並沒有參考數據集到支撐點 的距離分布情況，而這使得現有的數據劃分方法並不一定能夠提高相似性搜索的效率。
【發明內容】
[0008] 為解決現有技術中存在的問題，本發明提供一種在數據量較大且數據類型較多的 情況下，在度量空間中逐個支撐點進行數據劃分方法。
[0009] 本發明通過以下技術手段實現：
[0010] 為了解決度量空間中相似性搜索的效率問題，本發明採用的技術方案是，一種度 量空間中逐個支撐點數據劃分方法，在建立索引時，包括以下步驟：
[0011] 101)從數據集內根據起始和終止位置截取需要處理的數據；
[0012] 102)選擇一種支撐點優化方法，確定支撐點使用次序；
[0013] 103)選擇一種數據劃分方法，逐個支撐點進行數據劃分；
[0014] 104)確定每個劃分的上界與下界；
[0015] 105)確定每個劃分到每個支撐點的距離值的上界與下界；
[0016] 106)返回劃分結果。
[0017] 以上所述的度量空間中逐個支撐點數據劃分方法，
[0018] 在步驟102中，採用了 Variance方法，即遍歷每一個支撐點並根據該支撐點進行 數據劃分，計算每個劃分中的數據點大小，然後計算每個支撐點對數據劃分大小的方差，對 支撐點按照方差從小到大進行排序。
[0019] 在步驟103中，確定本次劃分要使用的支撐點，然後進行數據劃分，最後對已劃分 部分進行相應的處理。
[0020] 在步驟104與105之間，找到每個任務列表中的子節點及全部的直系父節點並存 儲。
[0021] 以上所述的度量空間中逐個支撐點數據劃分方法，需要從main函數接收四個參 數，分別是 dpm (data partition method)，sop (select optimal pivot)，pbop (partition by one pivot)和tR(trisection Radius)。當tR參數用於逐個支撐點數據劃分方法中的 Trisection方法，其他方法並不使用。
[0022] 所述的數據劃分的方法包含Balance方法、Kmeans方法、DBSCAN方法、Trisection 方法中的任意一種。所述的Balance方法為，找出使數據的numpartition-1個分位值和最 大值，然後將所有數據點與找出來的numpartition個值進行比較，並給其賦值為合適的類 標籤，對於其中與找出來的值相等的數據點先暫時存放起來，然後根據方差賦予它們合適 的類標籤。
[0023] 所述的Kmeans方法為，選擇K個初始質心；每個點指派到最近的質心，而指派到一 個質心的點集為一個簇；根據指派到簇的點，更新每個簇的質心；重複指派和更新步驟，直 到簇不發生變化，或等價地，直到質心不發生變化。
[0024] 所述的DBSCAN方法為，掃描整個數據集，找到任意一個核心點，對該核心點進行 擴充；所述的擴充為尋找從該核心點出發的所有密度相連的數據點，遍歷該核心點的Eps 鄰域內的所有核心點，尋找與這些數據點密度相連的點，直到沒有可以擴充的數據點為止。
[0025] 所述的Trisection方法為，判斷用戶給定的trisectionRadius*2是否小於將數 據點三分的兩個分位數數值的絕對值，如果是，則把使用這兩個分位數將數據集三分；否 貝 1J，找出在數據集中位數，並用減去trisectionRadius和加上trisectionRadius的值當 做將數據集三分的兩個數值點。
[0026] 以上所述的度量空間中逐個支撐點數據劃分方法，包括了對支撐點的處理和逐個 支撐點進行數據劃分。對支撐點處理時，從全局的角度對整個數據集進行劃分求方差，使得 用此方法選取的支撐點建樹時更加的平衡。根據數據集到支撐點分布提出來的數據劃分方 法，則更能將數據相似的點劃分在一起，這樣構建的索引樹無疑會提高搜索的效率。
【專利附圖】
【附圖說明】
[0027] 圖1為度量空間中逐個支撐點數據劃分算法框架；
[0028] 圖2為支撐點優化選取流程；
[0029] 圖3為逐個支撐點數據劃分流程。
【具體實施方式】
[0030] 以下將結合附圖對本發明的【具體實施方式】進行詳細說明。
[0031] 實施方式中使用的相關專業術語描述如下：
[0032] 輸入：metric :該數據類型的距離計算方法；
[0033] Pivots :通過FFT，Incremental或者其他的方法選出的支撐點；
[0034] Data :從原始文件中讀取的數據
[0035] First :本次數據劃分的在Data中的起始點；
[0036] Size :本次數據劃分的數據大小；
[0037] numPartitions :單個pivot將數據劃分成的個數；
[0038] maxLeafSize :葉子節點最大能存放的數據點的個數；
[0039] trisectionRadius :採用Trisection方法時，所採用的半徑值；
[0040] selectOptimalPivots :對pivots集合中的支撐點選擇執行的次序；
[0041] partitionByOnePivot :按單個pivot實現數據劃分的方法；
[0042] 輸出：CPartitionResults :數據劃分的結果；
[0043] 其他offset :數據被劃分後，每個劃分部分大小的上下界；
[0044] Upper:按每個pivot將每個任務劃分為numPartitions個部分，upper中存放每 個部分的上界值；
[0045] Lower:按每個pivot將每個任務劃分為numPartitions個部分，upper中存放每 個部分的下界值。
[0046] 如圖1所示，度量空間中逐個支撐點數據劃分算法：
[0047] 首先，從數據集中根據起始和終止位置截取需要處理的數據；
[0048] 然後，選擇一種支撐點優化方法，確定支撐點使用次序，具體支撐點優化選取過程 如圖2所示；
[0049] 接著，選擇一種數據劃分法，循環地將數據分為若干部分，具體的數據劃分方法如 圖3所示，計算本次任務中全部數據點到指定支撐點的距離，根據距離給數據點分類，並給 每個數據一個類標籤，記錄類標籤的起始值或者下屆、上屆；
[0050] 最後，根據以上劃分的若干數據部分，生成劃分結果並返回。
[0051] 更具體的來說為：
[0052] 1 :從data數據集中根據起始和終止位置截取本次任務需要處理的數據；
[0053] 2 :採用selectOptimalPivotspivots提供的方法對Pivots中點的處理順序進行 優化；
[0054] 3 :根據partitionByOnePivot確定使用的數據劃分方法；
[0055] 4 ：D0
[0056] 5 :在Pivots中按順序選擇一個未被使用的pivot ;
[0057] 6 :根據選出的pivot，利用一種數據劃分方法，將本任務中的數據點進行
[0058] 分類，劃分到若干個子任務中，即每個數據點被賦予了一個類標籤；
[0059] 7 :刪除每個數據量大小為零的子任務；
[0060] 8 :設置子任務是內部任務還是葉子任務；
[0061] 9 :把各個子任務加入到tasklist中；
[0062] 10 :在tasklist中尋找下個需要劃分的任務；
[0063] 11 :While (tasklist沒有被遍歷完| | tasklist最後一個任務不是葉子任務）；
[0064] 12 :在tasklist中將所有的葉子節點中的數據都存入data_temp，並根據
[0065] data_temp 的大小，確定 offset ;
[0066] 13 :找出tasklist中葉子節點的父節點，然後再找父節點的父節點，直到根
[0067] 節點為止，將找出的節點存入fathernode數組；
[0068] 14 :對fathernode數組中的節點，計算到相應的pivot的距離，然後把距離的
[0069] 上下界分別存入upper和lower ;
[0070] 15 :把data_temp賦值給data中相應的部分；
[0071] 16 :利用 offset，upper 和 lower 生成 CPartitionResults，並返回。
[0072] 算法時間複雜度為 0 ((numpartition) pivotSize*partitionByOnePivot)，其 中，numpartition是按單個pivot將數據劃分的個數；pivotSize是pivot的個數； partitionByOnePivot是按單個pivot進行數據劃分的時間複雜度，每個方法的時間複雜 度會在介紹該方法時給出。
[0073] 算法的空間複雜度為 O(partitionByOnePivot)，其中，partitionByOnePivot 是 按單個pivot進行數據劃分的空間複雜度，每個方法的空間複雜度會在介紹該方法時給 出。
[0074] 在按單個Pivot進行數據劃分時，Pivot的使用次序可能對劃分效果產生一定的 影響，從而致使搜索的效率不同。所以，通過FFT，Incremental或者其他的支撐點選擇方法 選出的若干個支撐點有必要再次進行優化，以決定他們在數據劃分中所使用的次序。
[0075] 在UMAD中，目前有兩種不同的優化支撐點的方法：Sequence和Variance。兩種方 法的輸入如下：
[0076] Metric :該數據類型的距離計算方法
[0077] Pivots :通過FFT，Incremental或者其他的方法選出的支撐點
[0078] Data :從原始文件中讀取的數據
[0079] Numpartition :單個pivot將數據劃分成的個數
[0080] maxLeafSize :葉子節點最大能存放的數據點的個數
[0081] 輸出都是已經優化後的Pivot集合。下面分別對他們進行介紹。
[0082] Sequence 方法
[0083] Sequence方法按Pivots本來使用的次序將其輸出，並不做任何的處理。
[0084] Variance 方法
[0085] Variance方法的總體思想是，遍歷每一個pivot並根據該pivot進行數據劃分，計 算每個劃分中的數據點大小，然後計算他們之間的方差，對pivot按照方差從小到大進行 排序。本發明採用該方法進行支撐點優化。
[0086] 算法步驟為：
[0087] 1 :while (Pivots集合中仍然有pivot沒有使用過）
[0088] 2:計算全部數據點到該pivot的距離，並存入getMetricData_Distance中；
[0089] 3:對getMetricData_Distance調用有關方法（如K-means)劃分為幾個部分； [0090] 4:計算它們之間的方差；
[0091] 5:把方差從小到大進行排序，以確定pivot的使用次序。
[0092] 算法的時間複雜度是 0(pivotSize*callMethod_time)，其中，pivotSize 是 pivot 的個數；callMethod_time是所使用的方法的時間複雜度。
[0093] 算法的空間複雜度是0(n+callMethod_space),其中，η為數據集大小； cal lMethod_space是所使用的方法的空間複雜度。
[0094] 數據劃分方法不僅決定了建樹的時空消耗，也決定了相似性搜索的效率，其重要 性可見一斑。目前UMAD中有四種不同的數據劃分方法，包含Balance方法、Kmeans方法、 DBSCAN方法、Trisection方法中的任意一種。但是它們的輸入與輸出都是一致的。
[0095] 輸入：
[0096] Task :本次進行數據劃分的任務
[0097] Metric :該數據類型的距離計算方法
[0098] Numpartition :按pivot對本任務進行數據劃分的數量
[0099] Pivot :進行本次數據劃分的支撐點
[0100] Indictor :指示本次數據劃分所使用的支撐點在pivot集合中的下標
[0101] cluster_Start :數據被劃分為若干個類之後，類的起始標記
[0102] clUSter_end :數據被劃分為若干個類之後，類的終止標記
[0103] 輸出：帶有類標籤數據的任務。下面分別進行詳細闡述。
[0104] Balance 方法
[0105] 此算法的關鍵點是對重複數據的處理。
[0106] 算法的大體思想為：利用平衡的思想，找出使數據的numpartition-Ι個分位值和 最大值，然後將所有數據點與找出來的numpartition個值進行比較，並給其賦值為合適的 類標籤，對於其中與找出來的值相等的數據點先暫時存放起來，然後根據方差賦予它們合 適的類標籤。
[0107] 算法步驟：
[0108] 1 :計算全部數據點到該pivot的距離，並存入task中的getMetricData_ Distance ；
[0109] 2 :選取 getMetricData_Distance 中的第
【權利要求】
1. 一種度量空間中逐個支撐點數據劃分方法，包含以下步驟： 101) 從數據集內根據起始和終止位置截取需要處理的數據； 102) 選擇一種支撐點優化方法，確定支撐點使用次序； 103) 選擇一種數據劃分方法，逐個支撐點進行數據劃分； 104) 確定每個劃分的上界與下界； 105) 確定每個劃分到每個支撐點的距離值的上界與下界； 106) 返回劃分結果。
2. 根據權利要求1所述的度量空間中逐個支撐點數據劃分方法，其特徵在於，所述的 步驟102中，採用了 Variance方法，即遍歷每一個支撐點並根據該支撐點進行數據劃分，計 算每個劃分中的數據點大小，然後計算每個支撐點對數據劃分大小的方差，對支撐點按照 方差從小到大進行排序。
3. 根據權利要求1所述的度量空間中逐個支撐點數據劃分方法，其特徵在於，所述的 步驟103中，所述的數據劃分為，確定本次劃分要使用的支撐點，計算本次任務中全部數據 點到指定支撐點的距離，根據距離給支持點分類，並給每個數據點一個類標籤，記錄類標籤 的起始值及終止值。
4. 根據權利要求1所述的度量空間中逐個支撐點數據劃分方法，其特徵在於，在步驟 104與105之間，找到每個任務列表中的子節點及全部的直系父節點並存儲。
5. 根據權利要求3所述的度量空間中逐個支撐點數據劃分方法，其特徵在於，所述的 數據劃分的方法包含Balance方法、Kmeans方法、DBSCAN方法、Trisection方法中的任意 一種。
6. 根據權利要求5所述的度量空間中逐個支撐點數據劃分方法，其特徵在於，所述的 Balance方法為，找出使數據的numpartition-l個分位值和最大值，然後將所有數據點與 找出來的numpartition個值進行比較，並給其賦值為合適的類標籤，對於其中與找出來的 值相等的數據點先暫時存放起來，然後根據方差賦予它們合適的類標籤。
7. 根據權利要求5所述的度量空間中逐個支撐點數據劃分方法，其特徵在於，所述的 Kmeans方法為，選擇K個初始質心；每個點指派到最近的質心，而指派到一個質心的點集 為一個簇；根據指派到簇的點，更新每個簇的質心；重複指派和更新步驟，直到簇不發生變 化，或等價地，直到質心不發生變化。
8. 根據權利要求5所述的度量空間中逐個支撐點數據劃分方法，其特徵在於，所述的 DBSCAN方法為，掃描整個數據集，找到任意一個核心點，對該核心點進行擴充；所述的擴充 為尋找從該核心點出發的所有密度相連的數據點，遍歷該核心點的Eps鄰域內的所有核心 點，尋找與這些數據點密度相連的點，直到沒有可以擴充的數據點為止。
9. 根據權利要求5所述的度量空間中逐個支撐點數據劃分方法，其特徵在於，所述的 Trisection方法為，判斷用戶給定的trisectionRadius*2是否小於將數據點三分的兩個 分位數數值的絕對值，如果是，則把使用這兩個分位數將數據集三分；否則，找出在數據集 中位數，並用減去trisectionRadius和加上trisectionRadius的值當做將數據集三分的 兩個數值點。
【文檔編號】G06F17/30GK104281652SQ201410472953
【公開日】2015年1月14日 申請日期:2014年9月16日 優先權日:2014年9月16日
【發明者】毛睿, 陸敏華, 蔡曄, 劉剛, 李榮華, 王毅, 羅秋明 申請人:深圳大學