一種基于數據驅動的動態時序分類算法

摘要：針對物聯網時序數據中存在的數據冗余現象和動態信息難以捕捉的問題，提出了一種基于數據驅動的動態時序分類算法。通過動態內部主元分析法（dynamic internal principal component analysis，DiPCA）提取傳感設備采集的時間序列中的動態信息，實現降維及提煉動態信息的作用；利用麻雀搜索算法優化分類算法參數，強化支持向量機（support vector machines，SVM）算法性能并使其對含有shapelet局部特征的時序特征進行建模，最終構成雙向演進算法框架，實現時序分類功能。利用UCR時序數據集和邊緣計算模擬數據檢驗該算法的性能，結果表明，與基本算法相比，該算法的綜合性能明顯提高，并驗證算法分類功能在仿真環境中的有效性與優越性。

關鍵詞：數據驅動；動態內部主元分析法；shapelet；麻雀搜索算法；支持向量機；時間序列分類

中圖分類號：U448.213" " " " " 文獻標志碼：A" " " 文章編號：1000-582X（2023）07-063-12

A data-driven dynamic time series classification algorithm

ZHAO Shuxu， ZHANG Jiazhen， WANG Xiaolong， ZHANG Zhanping

（School of Electronic and Information Engineering， Lanzhou Jiaotong University， Lanzhou 730070， P. R. China）

Abstract： Aiming at the problems of data redundancy and difficulty in capturing dynamic information in IoT time series data， this paper proposes a data-driven dynamic time series classification algorithm. The dynamic information in the time series collected by sensing devices is extracted by DiPCA （dynamic internal principal component analysis） to realize the role of dimensionality reduction and refining dynamic information; the parameters of the classification algorithm are optimized by using the sparrow search algorithm to enhance the performance of the SVM algorithm and make it model the temporal features containing shapelet local features， which finally constitutes a two-way evolutionary algorithm framework to realize the temporal classification function. The performance of the algorithm is examined using UCR temporal data set and edge computing simulation data， and the results show that the comprehensive performance of the algorithm is significantly improved compared with the basic algorithm， and the effectiveness and superiority of the classification function of the algorithm in the simulation environment is verified.

Keywords： data-driven; dynamic internal principal component analysis method; shapelet; sparrow search algorithm; support vector machine; time series classification

近年來，物聯網技術飛速發展，如何為物聯網提供高效的時序數據挖掘方案已成為研究熱點。充分地將數據中的重要信息提取、整理，才能規劃出準確，高效的模型。而應用型數據規模正持續地以指數級規模上升，數據的屬性也在不斷的擴張。因而對于數據集，通常采取降低維度的方式，簡化數據規模，主成分分析法（principal component analysis， PCA）通過研究屬性之間的線性關系，篩選出獨立性極強的屬性集，去除了多余的冗余屬性，降低了分析數據的難度，保留了數據的重要信息。基于此原理，Ku等[1]提出了動態主成分分析法（dynamic principal component analysis， DPCA），該方法將原始屬性通過時間窗口迭代讀取，形成增廣數據矩陣，利用PCA進行過程監測，以此達到折疊數據并以時序角度觀察信息；該方法擴張了數據規模，易造成維度災難，且難以挖掘數據相互關聯程度。Li等[2]提出了動態潛變量算法，首次提出自回歸PCA算法，要求最大化自協方差的同時提取潛變量，并以此建立自回歸模型；該方法提取潛變量一階次的自協方差，難以挖掘更深層次的動態關系。Dong等[3] 提出動態內部主元分析算法（dynamic internal principal component analysis， DiPCA），認為優化方向在于通過動態關聯狀態作為分析重心，在已有的動態性數據中，量化數據的自相關性，尋找多維主元內部的相關聯系，建立目標函數，最大化已提取的動態主元與預測的一般時刻動態主元的協方差，最終達到提取動態主元的目標。

2009年Keogh提出shapelet象形子序列，采取信息增益規則提取子序列代表時序的局部關鍵特征，相比于最近鄰算法（nearest neighbor algorithm，NNA） ，以shapelet 構造決策樹的分類方法準確率有所提高，但面對多分類問題仍有不足之處。原繼東等[4]提出了基于shapelet 的剪枝和覆蓋算法，減少不必要的數據特征；閆欣鳴等[5]提出了趨勢特征符號化方法表示時序的趨勢信息，提升運算效率，但是數據分類效果并不穩定。綜上所述，可考慮添加潛在變量信息豐富子序列特征內容，產生更優質的辨識性分類屬性。Coloni等[6]提出的蟻群優化（ant colony optimization，ACO）以信息素的高低指導蟻群尋找最優路徑，魯棒性高，適合求解連續性函數，但因難以統一多樣性信息，極易陷入局部最優狀態。Karaboga等[7]以蜜蜂采蜜的工作習性作為參考，不同分工的工蜂群以正負2種信號反饋獲取最優解位置，但信號傳播較慢，導致算法不易收斂。Xue等 [8]提出的麻雀搜索算法在蜂群算法，基礎上加入新的探測機制，搜索食物密集處的同時，關注安全程度，篩選滿意解集合，獲取全局最優解。

SVM在研究動態數據分類有顯著作用，具有較好的魯棒性和有效規避維數災難等優點，得到了學者重視。多變量問題的解決思想最為直觀的便是統一線性化，但使用簡易的線性化模型有可能出現過擬合現象，或者是過度簡化變量相關性質。文獻[9]提出基于最小二乘支持向量機（least squares support vector machine，LS-SVM）的相關性局部即時模型優化，以解決模型誤差大、訓練學習精度較低等問題。文獻[10]運用遺傳算法（genetic algorithm，GA）優化LS-SVM模型關鍵參數，提高模型的收斂能力，但未深度挖掘數據的時序規律特征。

文獻[11-13]從分解流程、提取惰性信息、時序大數據挖掘3個角度分別研究提取大數據的核心時序信息的方法，有效壓縮了信息容量，但都難以提取典型動態特征支撐分類算法。文獻[14]使用shapelet快速完成分類運算，文獻[15-16]引入了卷積算法有效提取更精準的信息特征，但是忽略了靜態冗余信息可能會影響分類的結果。提出的DiPCA-Shapelet-SSA-SVM組合模型重點研究數據信息的內聯性與外部相關擴展性，按照固定時間單位對時序數據進行劃分，每單位時間內擁有相同的探測數據數量，且探測時間一致；因此，設置探測值作為屬性向量，轉化單維數據為多維數據，提取有效潛變量，并獲取綜合動態指標與靜態檢測指標，提取的動態指標作為新的參考序列供shapelet子序列提取，獲得典型時序特征；受自然界生物世界的啟發，群體智能優化算法模擬生物行為，作為搜索算法的運行機制，達到優化解空間全局的效果；麻雀搜索算法優化向量機核心因子，充分運用動態特征。實驗結果表明本文算法性能指標優于現有常用分類算法，準確率與召回率明顯提升，并在仿真實驗中得到有效驗證。

1 原理介紹

1.1 特征提取方法

1.1.1 DiPCA

PCA難以滿足時序信息的預處理工作，時間序列與時間聯系密切，其動態特性無法只靠特征貢獻率降維和清理數據的方式獲取，DiPCA引入自回歸模型，設立協方差目標函數，在迭代過程中提取有效動態變量，重構新的時序信息，完整保留原有的信息內容。

設置為t時刻采集獲取的時序數據， 作為均衡因子向量，建立動態主元，

。 （1）

引用自回歸模型，劃分已建立的動態主元作為訓練集訓練自回歸模型系數，提取有效動態特征，得模型

， （2）

式中：和為單位向量，即 ，為噪聲向量，為序列階次量。

由此得動態主元預估模型

。 （3）

設置向量組，其中，為序列理想切割劃分單位，通過遞推式建立新的階次向量。

設立目標函數，將預估動態主元與原動態主元兩者間的協方差達到最大化，

，" （4）

。 （5）

采用拉格朗日算子法，確定參數、與之間關聯方程如下：

， （6）

。 （7）

通過迭代循環模型，設置收斂系數，循環計算均衡因子以及自回歸權重系數，直至滿足收斂要求。

1.1.2 Shapelet子序列介紹

有效區分不同類別的序列的算法需要選取最佳子序列，shapelet搜索算法實質是計算子序列與母序列間的最短距離，以此判斷所選序列是否代表典型局部特征。采用歐式距離計算如下：

， （8）

。 （9）

式中： 、為2條時間序列；、分別為前后時間序列的單位時間內有序數列數值。通過公式（9）可確定子序列與母序列的距離，兩者距離數值作為判斷信息熵的重要指標，直接決定了shapelet的匹配程度。

1.2 SVM模型參數優化

1.2.1 麻雀搜索算法（SSA）

受麻雀生活習性啟發，設置為麻雀位置向量，建立3類種族行動群體，分別是發現者、追隨者、偵察者。以下分別介紹其運行原理及特點。

1）發現者模式

（10）

該公式以規劃發現者群體在第t代中第i個單體的第j維位置，根據正態分布矩陣與預定距離的乘積量確定偵察者的大致分布，設ST為警戒閾值，以隨機數值與的對比關系確定單體的行動策略。

2）跟隨者模式

（11）

當小于麻雀總數量的1/2，說明當前的麻雀單位處于缺乏能量的饑餓狀態，因此測定當前最劣單位與自身單位的距離，并將其投射到指數函數中，再根據隨機分布矩陣分配隨機步長向周圍搜尋捕食點。

3）偵察者模式

（12）

式中：為符合標準正態分布的步長參數；為[-1，1]的滿足均勻分布的隨機數。以麻雀單位的適應值、全局最優麻雀的適應值、目前最差位置麻雀的適應值之間的關系直接確定偵察者的移動策略。偵察的麻雀已處于當前的最優位置時，該單位會逃離到自身附近的一個位置；反之，該麻雀并未處于最優位置，它會逃到當前最優位置的鄰域范圍內。

以上3類群體互相牽制，不斷調整、更新最優解位置。與其他群智能算法相比，SSA在集中搜尋滿意解的同時，引入偵察機制，避免陷入局部最優解問題。

1.2.1 SSA-SVM算法

SVM分類數據集時以確定超平面分割數據集。當數據集容量較大或者種類較多時，SVM需要迭代劃分出新的超平面處理信息，準確度會有所下降。SSA算法可通過調整罰函數因子以及核函數參數有效提高該算法的分類效果。SVM算法如式（13）～（15）所示。

； （13）

（14）

。 （15）

式中，為罰函數因子，調控懲罰向量對權重的松弛化操作程度。公式（14）為對目標函數方程的松弛化限制原理介紹。公式（15）為高斯核函數公式，用于擴增數據的屬性維度[17]，在新生成的屬性空間構造超平面，解決多分類數據難分解的問題[18]，參數為高斯核函數因子，決定了維度上升后坐標單位的劃分長度。

2 算法框架介紹

2.1 時序數據預處理

時序數據按組元為單位，以時間作為有序規則，每組數據時序集合同等劃分為相同數量屬性指標，一維傳感信號依照時間進程轉化為不同時刻的狀態數據，再以DiPCA算法剔除多余的靜態數據集合，抽取帶有動態特征的集合（圖1），固定探測信號的準確時刻，不同元組同一時刻采集數據，作為自身屬性衡量分數，再以降維工具對信息集采用一種近似于數據蒸餾的方式，蒸餾靜態信息，以此達到簡化數據量并保留有效信息的目的。該算法在迭代過程中，通過自回歸方程不斷提取動態特征，方程的階次值由數據交叉訓練中確定；數據不斷拋去的靜態數據集在迭代收斂結束后作為重要檢驗指標判斷生成的動態主元能否滿足預估期望。如果剩余數據可達到傳統PCA算法主元貢獻率的理論閾值，則可推算已滿足算法要求。

其中TSD（time series data）為原始時序集，預設置最大主元數目以及自回歸方程階次數，提取部分原始數據集分批訓練模型（如圖1所示），每一次迭代過程中獲取新的主元，直至迭代結束或滿足期望主元數目。為已處理的特征時序集合。

在數據轉化的過程中，元組每單位對應一條時序變量，變量經過統一切割，生成以時間順序作為劃分依據的多維屬性，再經過該算法迭代獲取動態主元屬性。元組會匹配到對應自身的多元變量，其本質仍為時序值，帶有明顯的時間流動規律。

2.2 Shapelet子序列提取

已獲取的新型時間序列采用shapelet搜索算法為單位時間序列提供可靠子序列集合，在該算法中采用歐式距離法衡量序列間的最短距離。計算子序列中可以代表母序列的顯著局部特征的shapelet序列[19]。

首先限制shapelet的長度范圍，經驗上最大長度為數據集中最小長度的序列對應的長度數值。滑動窗口在設定的長度范圍內截取數據集中所有的序列，等效于子序列全集。以信息增益（評價指標為互信息素）作為評判子序列的質量標準，具有最高信息增益值的序列即為，而信息增益最大的那一個便是shapelet。

為支持SSA-SVM模型的訓練學習，計算shapelet集合以與原序列的歐式距離作為投放分類訓練器的時序屬性列表。輸出的為類別數量為k，長度為n的時序屬性數據。

2.3 數據驅動的SSA-SVM分類一體化流程圖

SSA-SVM模型以具有時間序列特征的數據作為多維屬性集劃分超平面邊界，SSA尋找最適合當前數據集的參數因子、懲罰函數因子和核函數因子來構造狀態矩陣，優化目標是最大化由精確率和召回率的調和平均值構成的F1分數，該分數由準確率和召回率組成，同時考慮全局操作精度和計算成本，并在周期內更新參數，調整SVM算法的邊界范圍。

如上所述，在麻雀搜索算法的偵察模型中，由于步長參數不能隨搜索范圍靈活調整，而框架是基于數據驅動的理論優化條件，需要精確定位可行解的鄰域分布，所以調用慣性權重來更新該參數的選擇范圍[20?21]。隨著迭代次數的積累，步長參數會降低選擇范圍，可獲得良好的局部搜索能力，彌補了偵察者參數選擇的不穩定性，有目的地使偵察者行動路徑所傳達的搜索范圍更接近自身的目標函數要求（圖2）。

3 仿真與分析

3.1 實驗說明

選取10類UCR時間序列分類數據集驗證算法效果，抽取顯著異或特征，并與現有6種分類算法對比，驗證新型組合算法的有效性和提升效果；選取中國西北部某城市2018～2020年PM2.5空氣質量序列數據，實驗前已將該數據標簽化，以空氣質量指數劃分為優、良、中、差4類空氣狀況。設計邊緣計算服務器分配布局，模擬序列數據上傳，檢測邊緣服務器數據分類精確度，并衡量整體計算框架的成本與消耗。

3.2 UCR時間序列數據集實驗對比

根據UCR數據分類集，選取能代表序列類別的序列特征，圖3～8分別為數據集Gun_Point、Coffee、MoteStrain原始數據圖像以及經算法獲得的特征序列。

以數據集Gun_Point、Coffee舉例說明，數據集容量較大時難以去除冗余信息，同一時間單位內存在多余的序列信息，復雜的交叉信號點導致難以收集不同種類的典型特征。shapelet可有效抽取局部信息，避免相似數據出現重疊現象。數據集MoteStrain部分數據明顯異與整體序列規律趨勢，無規律異常值不具有代表性，故采用DiPCA可以在完成降維工作的同時，通過統計學指標去除異常數據，達到清洗數據、蒸餾信息的目的。

表3展現的是算法表現最好的6種數據集的F1分數對比結果，其中對比算法包括支持向量機（support vector machine，SVM）、最近鄰算法1NN（1 nearest neighbor）、樸素貝葉斯 （naive Bayes，NB）、決策樹C4.5，以及改進型算法加權隨機森林（weighted random forest，WRF） 與新型深度學習算法CNN-LSTM。通過表3數據可以看出，改進的算法與SVM相比，準確率與召回率整體有明確上升。Coffee數據集容量較大，在這里提取動態變量的效果顯著，提取出重要序列進行比較，F1值提到了1.37%；數據集FaceFour屬于長序列數據，shapelet收集數據間存在的局部差異，分類器集中處理異或特征，F1值提高了2.9%。

3.3 PM2.5空氣質量分類

設計仿真實驗場景，設置100個距基站 200 m范圍內隨機均勻分布傳感器節點，50個邊緣服務器均勻分布在8個相同面積的區域內，假設已知帶寬35 MHz，，傳感器的數據上傳速度為6.8 Mbps，上傳功率為1 800 MW，設備空閑狀態時放電功率為 200 MW，邊緣傳感設備的極限CPU主頻為2 GHz。分配中國西北部某城市2018-2020年PM2.5數據作為傳感節點獲取的時序集合，采用直接傳輸方式與中繼轉發方式將數據傳輸至邊緣服務器，經計算獲取分類結果，傳輸至服務云端。

收集的數據通過DiPCA-Shapelet處理，提取的特征要求明顯異于其他種類數據，相同性質的時序元素無法起到分類作用，因此，需要去除無顯著作用的屬性值。通過DiPCA算法結合文獻[3]使用的3種統計指標（Q統計量，T統計量以及霍林斯指標）確定PM2.5異常情況高發時間段，根據真實空氣質量狀況篩選出誤差型異常點集合，并確定保留異或性明顯的特征因子，處理結果的可視化圖像如圖9和圖10所示。

圖9中的指標自上向下分別為綜合動態指標、霍特林統計指標、靜態統計指標，三者具有相同的異常點高發范圍，聯系實際的空氣質量狀況，區分異常事件數據與錯誤數據。圖10表示典型局部特征，其中對特征量做量綱化處理，在圖中只顯示了單位數值。圖中以橫坐標5.0為起點，數據點逐漸擴散，在此之前，同一橫坐標數據集中于一點，且處于靜止狀態，未隨時間改變。數據出現分散狀態之后，均勻分布于同一時間點，不同時間點序列狀態皆不相同，說明獲取的特征異或性較強，動態性較高，可以有效區分序列類型。

SSA-SVM模型進行分類運算，采用慣性權重原理優化步長參數，當麻雀數量為30，精確度相比較于原算法顯著提升；當麻雀數量為60，精確度已處于收斂狀態并達到92%。算法召回率初期已上升至67%，后期上升趨勢平穩，但最終結果未有大幅度上升，為88.6%，仍有改進前景。

根據仿真場景提供的參數，按經驗緩存數據，按照任務卸載運行流程，采用SVM、樸素貝葉斯（Naive Bayesian，NB）、LSTM神經分類器、以及提出的組合算法對比不同算法的能耗、成本情況。這里的能耗是指傳感設備邊緣端點數據處理的能耗總和，由本地執行的CPU功率能耗以及任務卸載情況下的上傳能耗與CPU空閑放電能耗共同組成；其成本費用是指簡化仿真條件，只考慮任務卸載后的全體邊緣設備的運營費用總和。任務數量相同的前提條件下，提出的算法通過縮小觀察數據的跨度，提取實用信息，有效降低了能耗。從成本的角度看，與其他算法相比基本持平（如表4所示），可以重點考慮從優化任務卸載策略方面降低成本。

4 結" 論

提出了一種新穎的時間序列分類組合算法，可以在壓縮數據的前提下捕捉時間序列異或特征，SSA智能優化SVM算法的罰因子與核函數關鍵參數，充分運用動態信息，獲取關鍵分類差異性特征，分類效果明顯上升；該算法可以嘗試與邊緣計算框架有機結合，規避了復雜的數據重構過程，并從資源消耗的角度分析該算法實用性較高，可行性極強。但由于算法在進行數據壓縮與子序列再提取的過程中，部分數據集容量較小時，可能會出現提取特征不全面的問題，這導致算法運行時間會因未滿足信息增益的最低要求而延長，應思考如何調整算法的步驟使其更加適合不同特性的數據集。并在今后的研究中，重點為智能化任務卸載策略與數據分類功能結合，形成一個完整的智能框架結構。

參考文獻

［1］" Ku W F， Storer R H， Georgakis C. Disturbance detection and isolation by dynamic principal component analysis[J]. Chemometrics and Intelligent Laboratory Systems， 1995， 30（1）： 179-196.

［2］" 李德文， 郭勝均. 中國煤礦粉塵防治的現狀及發展方向[J]. 金屬礦山， 2009（S1）： 747-752.

Li D W， Guo S J. Situation and development direction of dust prevention and treatment for China coal mine[J]. Metal Mine， 2009（S1）： 747-752. （in Chinese）

［3］" Dong Y N， Qin S J. A novel dynamic PCA algorithm for dynamic data modeling and process monitoring[J]. Journal of Process Control， 2018， 67： 1-11.

［4］" 原繼東， 王志海， 韓萌. 基于Shapelet剪枝和覆蓋的時間序列分類算法[J]. 軟件學報， 2015， 26（9）： 2311-2325.

Yuan J D， Wang Z H， Han M. Shapelet pruning and shapelet coverage for time series classification[J]. Journal of Software， 2015， 26（9）： 2311-2325. （in Chinese）

［5］" 閆欣鳴， 孟凡榮， 閆秋艷. 基于趨勢特征表示的shapelet分類方法[J]. 計算機應用， 2017， 37（8）： 2343-2348， 2356.

Yan X M， Meng F R， Yan Q Y. Shapelet classification method based on trend feature representation[J]. Journal of Computer Applications， 2017， 37（8）： 2343-2348， 2356. （in Chinese）

［6］" Dorigo M， Maniezzo V， Colorni A. Ant system： optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B （Cybernetics）， 1996， 26（1）： 29-41.

［7］" Karaboga D， Akay B. A comparative study of artificial bee colony algorithm[J]. Applied Mathematics and Computation， 2009， 214（1）： 108-132.

［8］" Xue J K， Shen B. A novel swarm intelligence optimization approach： sparrow search algorithm[J]. Systems Science amp; Control Engineering， 2020， 8（1）： 22-34.

［9］" 朱清智， 董澤， 馬寧. 基于即時學習算法的短期負荷預測方法[J]. 電力系統保護與控制， 2020， 48（7）： 92-98.

Zhu Q Z， Dong Z， Ma N. Forecasting of short-term power based on just-in-time learning[J]. Power System Protection and Control， 2020， 48（7）： 92-98. （in Chinese）

［10］" 林昶詠， 吳桂聯， 張林垚， 等. 分布式電源接入配電系統優化規劃方案[J]. 現代電力， 2019， 36（6）： 82-87.

Lin C Y， Wu G L， Zhang L Y， et al. Planning scheme optimization for distributed generation accessed in distribution system[J]. Modern Electric Power， 2019， 36（6）： 82-87. （in Chinese）

［11］" Xiao Z W， Xu X， Zhang H X， et al. A new multi-process collaborative architecture for time series classification[J]. Knowledge-Based Systems， 2021， 220： 106934.

［12］" Zhang W， Wang Z H， Yuan J D， et al. Shapelet discovery by lazy time series classification[J]. Computational Intelligence and Neuroscience， 2020， 2020： 1978310.

［13］" Wang W， Hu X H， Wang M Y， et al. Implementation of parallel algorithm technology for time series data mining[J]. Journal of Physics： Conference Series， 2021，2066：012043.

［14］nbsp; Arathi M. An efficient and accurate time series classification using shapelets[J]. International Journal of Information and Electronics Engineering， 2014， 4（5）： 347-353.

［15］" Dempster A， Petitjean F， Webb G I. ROCKET： exceptionally fast and accurate time series classification using random convolutional kernels[J]. Data Mining and Knowledge Discovery， 2020， 34（5）： 1454-1495.

［16］" Alamir M A. A novel acoustic scene classification model using the late fusion of convolutional neural networks and different ensemble classifiers[J]. Applied Acoustics， 2021， 175： 107829.

［17］" Zhang J T， Shen W M， Gao L， et al. Time series classification by shapelet dictionary learning with SVM-based ensemble classifier[J]. Computational Intelligence and Neuroscience， 2021， 2021： 1-13.

［18］" Mahmud M A. Isolated area load forecasting using linear regression analysis： practical approach[J]. Energy and Power Engineering， 2011， 3（4）： 547-550.

［19］" Liang Z Y， Wang H Z. Efficient class-specific shapelets learning for interpretable time series classification[J]. Information Sciences， 2021， 570： 428-450.

［20］" Zheng K D， Chen Q X， Wang Y， et al. A novel combined data-driven approach for electricity theft detection[J]. IEEE Transactions on Industrial Informatics， 2019， 15（3）： 1809-1819.

［21］" Chatterjee A， Siarry P. Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization[J]. Computers amp; Operations Research， 2006， 33（3）： 859-871.

（編輯" 呂建斌）