多變量時間序列的相似查詢分析

1 多變量時間序列相似的定義

多變量時間序列的相似查詢，用于描述在給定的多變量時間序列數據庫中查找與待分析多變量時間序列相似或匹配的時間序列段。但與傳統的待分析對象的精確目標查找過程不同，由于時間序列的采集極易收到噪聲污染，加之時間序列本身具有連續性，使得時間序列的精確匹配沒有可能同時也沒有必要。

則稱多變量時間序列X與Y相似，記作Sim(X,Y)。其中，D(X,Y)稱為描述多變量時間序列 X 與 Y 之間距離的函數，也稱為 X 與 Y 之間的相似度量函數。

按照查詢規則的不同，多變量時間序列的相似搜索目前可分為兩種情況:

結構監測數據的相似查詢問題，屬于子序列匹配問題。但在之前的很多研究多元相似查詢文章的子序列匹配過程中，多采用先將多變量時間序列數據庫按照一定的規則平均分段后再進行數據段 Q 的相似查詢過程。這樣計算的優點便是算法簡單，時間成本低，但是卻存在可能性較高的“漏查”問題，如圖 3.8。

(a)單變量樣本數據庫X (b)直間數據庫O

圖3.8 平均分段后的子序列查詢“漏差”情況說明

圖 3.8 中，（a）是已經被平均分段后的單變量樣本數據庫 X，（b）是待查詢的數據段 Q，將 Q 在 X 中進行子序列匹配的相似查詢，由于與 Q 近似的樣本數據段在 X 中被平均分割開，導致查詢結果顯示 X 中無與 Q 相似的數據段，造成了查詢錯誤。

為了避免這樣的錯誤在結構監測數據集的相似查詢過程中產生，我們使用“遞進式分段法”對結構監測樣本數據集進行分段。

2 B+-tree 索引技術的應用

索引是數據表中數列值的集合和指向表中物理標識這些值的數據頁的邏輯指針清單，是對存儲在相應存儲單元中的數據位置信息的映射，用于優化信息檢索過程，是提高數據查詢效率的重要手段。

基于樹形組織的索引技術作為數據索引的重要手段之一，可分為索引順序存取法和多層索引樹的索引。其中多層索引樹法主要包括 B-tree 法和 B+-tree 法。

B-tree 法是一種基于動態調節的平衡多路徑查詢樹，具有較高的隨機查詢效率，但是 B-tree 自身的結構缺陷導致很難只用一次全局查詢遍歷到樹中的所有元素。

B+-tree 是 B-tree 的一種變體形式，滿足以下特征：

⑤ 葉節點存儲著數據信息的關鍵字與指向某一記錄的指針，葉結點按關鍵碼值的大小順序鏈接。每一個葉結點可看作是一個直接指向數據記錄的索引塊；

⑥ 分支結點可以看作是索引的索引。

B+-tree 索引建立的過程如下：

① 首先對待查詢樣本數據集進行基于改進 K-means 算法的聚類處理，得到最佳聚類劃分簇數量，并計算各聚類簇半徑，為每個聚類簇集分配序號；

② 選取全局參考點 O，計算樣本數據集中每個點到 O 的距離，結合各個數據點所屬聚類簇的序號，計算各點的關鍵字，并根據樣本數據對象與 O 的距離建立 B+-tree 索引

③ 根據各樣本數據對應的關鍵字，將所有樣本數據點插入索引的相應位置中。過程如圖 3.10 所示。

B+-tree 索引建立的算法描述如表 3.6：

表 3.6 B+-tree 索引建立算法 BtreeSetup(C,C.X)的算法描述

3 多變量時間序列的相似查詢算法

K 近鄰分類（k-Nearest Neighbour，KNN）算法是基礎機器學習的核心算法之一。該算法的核心思想是：給定一個待查詢樣本點，統計其在特征空間中最鄰近的 k 個樣本數據點，如果這些點的大多數屬于某一個聚類簇，則認為該樣本點在特征空間中也屬于此類別。

K 近鄰分類算法的優點是算法簡單有效， 屬于一種 lazy-learning 算法，對于獨立的K近鄰分類算法來說，其時間復雜度與樣本數據集的大小成正比，為O(n)。但對于基于索引樹的 K 近鄰分類算法，其時間復雜度會根據索引效果的不同而相應程度的降低。 K 近鄰分類算法的重點便是 k 值的選擇，因為該算法中對待查詢點的分類決策規則是服從多數原則，所以不同的 k 值可能對應不同的結果，如圖 3.11。

圖 3.11 中，中心的圓點為待查詢樣本點，圖中的正方形點和三角形點是已知聚類分類的樣本點。可見，當 k=1 時，樣本最近的一個鄰居為紅色三角形，此時可認為樣本屬于三角形一類；當 k=5 時，樣本鄰域中三角形有三個，正方形只有兩個，此時可認為樣本屬于三角形一類；當 k=10 時，樣本鄰域中三角形有四個，而正方形有六個，所以此時可認為樣本屬于正方形一類。因此，一般在 K 近鄰分類算法實驗中，需要采用多次 k 值的賦予來找出最優值。

基于 B+-tree 索引的 K 近鄰分類算法的算法描述如表 3.7。

表 3.7 基于B+-tree 索引的 K 近鄰分類算法 BTKseach(X,q,k)的算法描述

以 3.2.3 中的已使用改進的 K-means 算法進行聚類簇劃分的二維隨機高斯分布散點作為樣本數據集，對于給定的一個點 q，使用基于 B+-tree 索引的 K 近鄰分類算法，對其進行相似查詢。其中樣本數據集分布情況如圖 3.12。

如圖 3.12 可見，待查詢點 q 夾在三個聚類簇中心位置，因此其聚類簇的歸屬問題與 k 值的選取有很大關系。如圖 3.13。

如圖 3.13 可知，當 k=1 時，待查詢點 q 的 k 近鄰范圍內只有聚類簇 B 的一個點，所以若在 k=1 時對 q 進行相似查詢，q 將被分類到聚類簇 B 中；而當 k=9時，q 的 k 近鄰范圍內有聚類簇 A 兩個點，聚類簇 B 三個點，聚類簇 C 四個點，所以若在 k=9 時對 q 進行相似查詢，q 將被分類到聚類簇 C 中。使用基于 B+-tree索引的 k 近鄰法算法，分別對 q 進行 k=1、k=9 的相似查詢，結果如圖 3.14。

《來源科技文獻，經本人分析整理，以技術會友，廣交天下朋友》

總結

以上是生活随笔為你收集整理的时间序列分析 pdf_多变量时间序列的聚类分析与相似查询——多变量时间序列的相似查询分析...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。