[發明專利]一種基于多層次shapelet的時間序列數據分類方法

在審

• 申請號: 202010696976.2
• 申請日: 2020-07-20
• 公開（公告）號: CN111814897A
• 公開（公告）日: 2020-10-23
• 發明（設計）人: 丁琳琳;脫乃元;曹魯杰;張翰林;宋寶燕
• 申請（專利權）人: 遼寧大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 沈陽杰克知識產權代理有限公司 21207
• 代理人: 羅瑩

1.一種基于多層次shapelet的時間序列數據分類方法，其特征在于：其步驟為：

步驟1)時間序列數據的預處理：對原始時間序列使用SAX方法進行數據降維處理：

步驟2)時間序列初始子序列的獲取：滑動窗口的方法來提取時間序列中的子序列集合，通過改變和調整窗口的大小，間接控制子序列的提取長度；

步驟3)多層次shapelet候選集的發現與提取：通過提出的多層次shapelet框架對候選集合進行過濾與合并，選擇信息增益大的shapelet作為候選集；

4)Shapelet轉換及分類器構建：

4-1)shapelet分類轉換：首先，將初始的N條時間序列數據集合根據條數建立一個簡單的初始化數據矩陣，同時將通過多層次框架方法得到的所有shapelet候選集合按照所歸屬時間序列的順序進行矩陣生成；其次，根據初始N條時間序列集合與shapelet矩陣之間的多對多映射關系，進行歐式距離的相似度計算，得到每條時間序列的特征值，其中每個特征值的屬性代表一個shapelet，每個屬性的值是從shapelet到原始序列的距離；最后，將特征值構建成N條特征向量，完成時間序列數據集合的特征化向量表示；

4.2)在為時間序列建立完分類器之后，就對后續的訓練樣本數據放入分類器中進行訓練，在訓練過程中，ELM首先隨機產生輸入權重和隱層節點閾值，然后再根據訓練數據計算SLFNs的輸出權重。

2.根據權利要求1所述的一種基于多層次shapelet的時間序列數據分類方法，其特征在于：所述的步驟1)中，具體步驟為：

1.1)數據的歸一化分段近似：采用0均值標準化方法將初始時間序列數據變化為均值為0、方差為1的數據集合；

1.2)處理后的數據進行字符化表示：將每個段中的平均值映射到高斯分布表中，高斯分布表的范圍代表了時間序列降維的表示范圍，根據初始化設置好的w參數指標、字母基r的大小以及分裂點β的范圍進行字符化操作，完成符號聚合近似表示。

3.根據權利要求1所述的一種基于多層次shapelet的時間序列數據分類方法，其特征在于：所述的步驟2)中，具體步驟為：

首先，設置滑動窗口的大小，固定好每次提取子序列的長度和范圍；其次，按照每次向右進1的原則滑動窗口，改變時間序列中窗口的位置，完成時間序列中不同位置的子序列提取；最后，調整并改變窗口的大小，完成所有不同長度子序列提取，并將提取的子序列存入集合中。

4.根據權利要求1所述的一種基于多層次shapelet的時間序列數據分類方法，其特征在于：所述的步驟3)中，具體步驟為：

3.1)基于k-means的初始子序列聚類：在提取出所有時間序列的子序列后，對候選子序列進行聚類，引入DTW距離度量計算方式作為衡量指標，對子序列集合進行的過濾和篩選，DTW距離代表了子序列形狀的相似程度，采用DTW算法將所有備選的shapelet候選集進行劃分，使得在相同簇中的shapelet候選集合在形狀上具有相似的特征；

基于DTW距離的shapelet相似性計算，設有兩個不同的shapelet序列，X1＝{x1,x2,…xM}，Y1＝{y1,y2,…,yN}，首先計算距離矩陣之后計算累積距離矩陣S_ij＝D_ij+min(S_i，j-1，S_i，j-1，S_i-1，j-1)

3.2)聚類結果更新：在子序列候選集合通過k-means方法與DTW方法的結合來進行候選集的聚類后，對得到的聚類結果進行實時性的迭代和更新，以確保子序列的聚類結果滿足形狀近似的特點，從而實現后續shapelet候選提取中明確的類別化；

3.3)建立多層次shapelet提取框架。

5.根據權利要求4所述的一種基于多層次shapelet的時間序列數據分類方法，其特征在于：所述的步驟3.3)中，具體步驟為：

3.3.1)進行層次內候選集合并：首先，根據子序列聚類產生“堆”的情況，完成所有聚類子序列的層次劃分；其次，通過候選集在層次中的內在“近似”關系完成候選集的整合，通過形狀的近似特點進行篩選，形狀相近的候選集合進行合并和整合，形狀特點明顯的候選集更具有區分能力，解釋性更新，因此保留；運用DTW距離作為閾值或者給定閾值，距離小于閾值的兩個候選集，說明其形狀極為相似，保留接近閾值范圍內的候選集進行消減；最后，在每個層次都得到精簡后的shapelet候選集；

3.3.2)進行層次間候選集合并：在SH-ELM模型中使用Levenshtein Distance算法進行多層次間候選集的合并，對于兩個字符串a、b,長度分為為|a|、|b|,它們的LevenshteinDistance計算公式如下：

其中當a_i＝b_j時，lev_a，b(i，j)值為0，否則lev_a，b(i，j)值為1，lev_a，b(i，j)就是的前i個字符與b的前j個字符的編輯距離，a、b的相似度Sim_a，b表示為：

Sim_a，b＝1-lev_a，b(|a|，|b|)/max(|a|，|b|)

在候選集合并的過程中，對框架內相鄰的層次中的候選集進行連接計算，通過使用Levenshtein Distance方法借助字符化的近似距離計算來對層次之間的候選集合進行比較和篩選；

3.3.3)多層次top-k候選集確認：通過信息增益的指標來作為度量分類能力的評判標準，選取單個層次中信息增益最大的k個shapelet，top-k shapelet來完成提取任務；對提取出來的候選集進行最終確認，使用提取出來的候選集合完成候選時間序列的分類任務。該流程即為從數據集中抽取k個最好shapelets的過程；在初始時，k-shapelet集合為空，之后在每一層次中得到一個候選shapelet序列，都需要計算該序列與所在層次的距離；在得到距離值，計算該序列所對應的信息增益大小，根據信息增益的大小進行排序，并完成最佳shapelet的候選替換，最后輸出最佳的k-shapelet。