針對時間序列數據挖掘的雙加權聚類集成

胡健，王海林，肖鵬，尹君

（云南電網有限責任公司信息中心，昆明 650217）

0 前言

時間序列是一種廣泛存在的數據，是由客觀對象的某個物理量在不同時間點的采值按時間順序排列成的序列數據，時間序列客觀記錄了所觀測的系統在各個單位時間點上的狀態值，所以可以通過研究時間序列數據來辨識、重構和預測所觀測系統的行為模式。時間序列具有普遍存在性，多媒體數據，金融數據，氣象數據，人口普查數據都是時間序列數據類型。研究如何有效地從這些復雜的海量時間序列數據中挖掘隱藏的、有價值的信息與知識，具有重要的理論價值和現實意義。時間序列數據挖掘（Time Series Data Mining）已成為數據挖掘研究領域中主要的研究對象[1]。時間序列數據挖掘巨大的科學意義與應用價值正在受到世界許多國家學術界、工業界和政府部門的普遍重視。2005 年，香港中文大學的研究者做了一項關于數據挖掘研究中最具挑戰性問題的研究報告，將時間序列數據挖掘列為數據挖掘中最具挑戰性的十大研究方向之一[2]。2014 年10 月，Twitter 公司開源了云環境時間序列數據斷層檢測工具Breakout[3]。2012 年，奧巴馬政府投資2 億美金啟動“大數據研究和發展計劃”，并在2017 年發布了第二輪大數據研究項目，其中白宮科技政策辦公室正在建立流行病“天氣預報”項目，旨在利用大數據方法，能夠盡早對流行病作出識別和預測，以便預做準備，減輕癥狀，其本質就是時間序列數據挖掘[4]。

時間序列數據挖掘與傳統的數據挖掘最大的區別在于其數據的時效性與有序性，是一個發現潛在有用的，與時間屬性相關的信息與知識的過程，其主要包括時間序列相似性挖掘、特異性挖掘與規律性挖掘。數據挖掘技術大致包括：統計學方法、聚類分析、決策樹技術、人工神經網絡、規則歸納，以及可視化技術等等，本課題將主要研究時間序列數據挖掘的聚類分析技術。盡管研究人員在時間序列聚類分析的研究上已經取得了許多成果，但由于時間序列數據本身具有非常復雜的特性，如：復雜時間相關性，高維度，海量性、噪聲干擾，使得時間序列數據挖掘的工作充滿挑戰，依然面臨以下亟待解決的關鍵問題[5]：

1）雖然研究人員己經針對時間序列提出許多特征表示（representation）方法，但是每一種方法對于時間序列信息的還原都具有片面性，某一種特征表示方法只能提取時間序列中某些特征信息，并且通常無法全面地反映出目標數據集的簇結構信息，有些特征甚至會混淆數據的簇結構,導致聚類算法失效。如何選取最佳的有助于呈現目標數據集的聚類分析的特征表示仍然是一個棘手的問題。

2）現有的時間序列相似性度量用多種距離公式，如，歐氏距離(Euclidean Distance) ，馬氏距離（Mahalanobis Distance) ，對數似然距離（log-likelihood Distance），動態時間彎曲距離（Dynamic Time Warping）等[6]。但是在實際操作中，每一種特征表示方法都有其對應的最佳相似性度量方法。如何確定最佳的匹配仍需要大量的先驗人為應驗。此外，很多相似性度量公式具有較高的計算復雜度，針對高緯度，海量的時間序列數據集進行聚類分析時，需要較高的計算資源，而且都含有需要用戶設置合理的參數，同時在聚類過程中，待聚類的數據都是在距離閩值的強制作用下聚合或分離，無法準確體現數據對象間自發，天然的聚散關系。

3）針對時間序列所使用的聚類算法普遍具有單一性，沒有一種聚類算法可以普遍適用于各種時間序列數據集所呈現出來的復雜簇結構。一種聚類算法一般只適合于某種情況的聚類分析。此外，在進行聚類之前都需要用戶事先確定要得到的聚類的數目（類數）。然而在現實數據中，類數是未知的，通常要經過不斷的實驗來獲得合適的類數，以得到較好的聚類結果。

集成學習(Ensemble Learning) 是指利用多個學習機解決一個問題。隨著其飛速發展，研究人員嘗試使用此類方法解決上述時間序列數據挖掘的難點問題，并取得了一系列創新性研究成果。聚類集成學習（Clustering Ensemble）的目的是通過集成多個互補的聚類結果以得到一個高可靠性的聚類分析系統，旨在產生泛化能力強、差異大的多個成員聚類器，充分發揮每個成員聚類器在各自聚類性能上的優勢，獲得比單個成員聚類器都要好的聚類集成結果。與單一的聚類算法相比，聚類集成學習具有三大優勢[7]：聚類集成結果具有更高的精確度；聚類集成學習可以發掘單一聚類算法無法發掘的簇信息；聚類集成學習對于復雜環境，如：噪聲，異常數據點，采樣變化，有較強的抗干擾能力。一般通過提高成員聚類器的聚類性能以及增加成員聚類器的差異性（Diversity）來達到提高集成性能的目的。但現有的聚類集成學習算法依然存在諸多問題[8]，具體分析如下：

1）如何在沒有先驗知識的條件下，合理地組合大量的初始聚類分析結果以達到最優融合，仍然存在諸多亟待解決的問題。

2）由于聚類集成算法是一種無監督學習過程，因此，如何正確有效地識別類簇的本征類數仍然是一個棘手的問題。

針對上述問題，本課題在非監督學習的理論框架內，深入研究基于生成模型和特征表示的時間序列數據挖掘算法，提出兩種新型的雙加權聚類集成學習模型，從不同角度進一步提高集成算法在時間序列聚類分析中的性能。本課題將目前時間序列聚類算法以及聚類集成算法中的幾個關鍵性難點問題（包括：時間序列特征表示和生成模型表示方法；多成員聚類器的產生和融合；以及聚類分析中的類數自確定）納入統一的算法框架，為復雜多樣的時間序列數據集的聚類分析提供了一套可行的通用技術路線。

1 算法描述

本課題提出的算法模型由三個模塊組成，包括了特征抽取，初始化聚類分析，雙加權聚類集成學習。其擬算法流程如圖1 所示。模型構建的研究方案如下。

圖1 基于多特征表示的雙加權聚類集成模型

1.1 時間序列特征抽取(representation extraction)

時間序列表征通常可以分為兩大類:分段式的（piecewise）和全局式的（global ）。一個分段式的特征表示(piecewise representation)根據一個分割標準把高維的時間序列向量分解成一系列的分段向量，然后對每個分段做特征提取，所有分段的特征表示按序排列組成一個完整的分段式特征表示(piecewise representation)，例如，自適應分段常數近似(Adaptive Piecewise Constant Approximation) 和分段式主成分分析（piecewise Principal Component Analysis）。在全局式特征表征（global representation）中，我們用基函數來模擬目標時間序列數據集，因此，基函數的回歸系數構成了時間序列的特征表示，例如，多項式擬合(polynomial curve fitting)，離散傅里葉變換(discrete Fourier transforms)，和離散小波變換(discrete wavelet transforms)。一般情況下，分段式(piecewise)和全局式(global)的時間序列特征表征具有一定的互補性。分段式注重局部信息的表述，但容易忽略全局信息。相反，全局式可以很好的還原時間序列的整體特征，但對局部信息的提取不夠完整。在此模塊中我們將選取多個特征表示方法，使其對時間序列的特征描述上具有最大程度的互補性。

1 . 2 初始化聚類分析( initial clustering analysis)

在初始聚類分析模塊中，我們在不同的特征空間里，給定不同的初始化設置，對目標數據集進行聚類分析，如使用k-mean 算法，會產生多個不同的劃分。由此可以有效地增加各劃分的差異性（Diversity），從而提高聚類集成學習的性能。以往的研究證明聚類集成學習的性能取決于初始聚類分析的質量和其產生的劃分的差異性。

1.3 雙加權聚類集成(Bi-weighted clustering ensemble)

為了確保類簇和它們的劃分根據其重要性對融合產生建設性的貢獻，我們引入了一個雙權重方案以優化輸入劃分的融合。這樣，不僅將權重根據他們的聚類質量全局地分配到了輸入劃分，而且權重的局部分配能自適應于類簇本身產生的對應劃分。

1）雙加權框架

給出一個距離變量D，加權聚類集成的融合函數是為找出接近多重輸入劃分的一個融合劃分Pr，輸入劃分是從目標數據集中獲得。因此，融合用公式可以表示為成本函數的最小化，如下所示：

其中wm指的是劃分Pm的權重，

在基于模型的聚類中，每個輸入劃分Pm被表示為一個概率分布的混合其中是混合模型參數，Km是每個輸入劃分的類簇數，表示聚類，p(km) 表示先驗概率。基于KL 距離，公式(5)中的花費函數可以被進一步地推導為：

公式(6)中的花費函數可以被分解成兩個子花費函數J1 和J2，這表明了一個聚類集成算法的性能依賴于聚類集成和輸入劃分的質量。其中，第一項J1 對應于輸入劃分的質量，J1 的值越小意味著輸入劃分的質量越好。事實上，聚類的目的在于將目標數據集劃分到不同的組或類中，使得同一個分組/類中數據點具有較高的相似性，相似性由一個類間距離來確定，不同類間的相異性通過集群(類簇)的距離來確定。也就是說，Dlk測量和劃分Pm中剩余的類的集群內間距離，其中，表示類數據點的相似性。因此，輸入劃分Pm的聚類質量可以用公式表示為：

CQm的最小值標識著輸入劃分的最佳質量，其中類簇集群內部的距離應該小，而類簇間的聚類應該大。

直觀地，劃分權重應該由J1 的最小花費確定，其中較大的權重應該被分配給較好的劃分質量，較好的劃分質量由較小的CQm值所決定。然而，這種簡單的方法可以分配一個單一的最大權重給具有最小CQm值的輸入劃分，同時其他所有的權重都被置零。在這種情況下，融合函數轉變成了選擇函數。為了是所有的輸入劃分促成融合劃分，我們在J1 中引入了一個表示劃分權重負熵的正則項wmlogwm，構成了一個正規化的花費函數：

其中α≥0 是一個拉格朗日乘數，控制著額外正則項的強度，增加它的值將會加大輸入劃分的enthusiasm。在我們的仿真實驗中設定α=0.5。

因此，適當的劃分權重可以通過J3 的最小劃分來確定[51]：

一旦得到了輸入劃分和對應的權重，J 的第一項J1 就被固定了，所以聚類集成的性能主要由J2 控制。因此，J2 的最小值等價于J 的最小花費。為了優化這個過程，我們引入了雙層加權方法來判定接近所有類簇的融合劃分。在花費函數J2 中，第一層權重是通過公式(9) 得到劃分權重，第二層權重是類簇的權重，可以被定義為：

其中是具有劃分Pm的聚類中數據點的數目，而N 是所有數據點的總數。2）共識函數

現有的聚類集成技術應用了三個hyper graph-based 的融合函數來產生融合劃分。因此，需要將大量的輸入劃分通過連接所有的二進制成員指示器映射到一個hypergraph。指示器是映射每一個輸入劃分Pm到一個鄰接矩陣以制作一個超圖得到，為了進一步改進在我們設計方案中hypergraph-based 融合劃分，我們提出了一個加權的hypergraph，定義如下：

為了導出集成的融合劃分，我們應用了三個融合函數來確保不同的視角都被考慮到。包括了基于聚類的相似性劃分算法(CSPA)、hypergraph-partitioning algorithm (HGPA)和the meta-clustering algorithm (MCLA)。其中CSPA是一個簡單的融合函數，距離矩陣S 在加權的hypergraph 中對所有的劃分進行加密，派生于鄰接矩陣WH:S=WHWHT，then the similarities yielded from multiple partitions are used to recluster all the sequences to yield a consensus，HGPA 提供了替代的融合函數，通過鑄造聚類集成問題，關于通過剪切最小加權超編怎樣劃分加權的hypergraphy，不像CSPA 把局部分段相似帶入計算，HGPA 關心跨域不同劃分序列的相對全局關系。最后，元聚類算法(MCLA)通過聚集多個輸入劃分實現融合。其基本思想是重新聚類加權的超邊(hyper-edges)，生成融合函數，聚類的總數減少到由用戶指定的元聚類的一個小數目。

3）目標函數

沒有先驗知識，就不可能提前選擇一個合適的函數以形成聚類集成。既有的解決辦法都是使用歸一化互信息(NMI)根據目標函數[45]來測量任何兩個劃分之間的一致性，用公式表述如下：

其中Pa,Pb表示兩個劃分的標簽，將N 個對象的目標數據集劃分到Ka和Kb兩個類簇中，是類簇和之間共享對象的數目，和分別表示和的對象數目。

根據公式，最優融合劃分通過搜尋從HMM K-models 聚類集成中獲得的M 個劃分的最大平均互信息來確定，為此，通過下面的優化方程來確定這三個函數的最佳融合。

其中Pm是HMM 的K-models 生成的第m個劃分，Pr是第r個融合函數產生的融合劃分。總之，融合函數篩選出的劃分Po作為給出時序數據集的最優融合劃分。

2 實驗驗證

為了評估總體上對時間數據進行聚類的方法的性能，我們通過使用時間序列集合作為測試數據集來進行模型驗證[52]。該基準數據集包含16 個合成或真實時間序列的數據集。表1 中列出了有關所有16 個數據集的特定信息，包括每個數據集中的類數，時間序列數和時間序列長。

表1 時間序列基準數據集信息

為了實驗效果比對，我們最初在時間序列的基準集合上測試了5 種技術，包括K 均值，基于動態時間規整（DTW）的K 均值[53]，基于HMM 的K 模型，HMM 混合聚類和HMM 混合元聚類，其中K-mean 算法的結果由基準收集器提供。為了檢查所提出的雙向加權方案的有效性，我們還將我們的方法與其HMM 混合元聚類集成體的原型進行了比較，并觀察了引入的雙向加權方案如何能夠有效地提高聚類集成體的性能。對于基于HMM 的聚類算法，HMM 的狀態數對于時間序列建模至關重要。但是，此類信息通常不可用，因此我們只能對一系列狀態號進行窮舉搜索，其中最佳狀態將最適合估計的HMM，從而導致最大的對數似然性，即所謂的“前進”和“后退”算法[38,39]。在我們的實驗中，每個時間序列的最佳狀態數分別確定為6、2、4、9、2、6、3、10、8、8、9、6、7、8、2、3 包括在內。每個數據集的類別編號K *也用于所選基準中。由于我們提出的算法具有自動選擇模型的能力，因此我們簡單地將K 值設為預設范圍（K＞1）中的簇數。

我們使用最佳參數設置將每種算法運行10次，表2 中列出了每種經過測試的算法的最佳結果，從中可以看出，我們的方法在16 個數據集中的8 個上獲得了最佳性能。相比之下，基于DTW 的K-mean 可以在三個數據集上獲得最佳結果，而所有其他數據只能分別在一個數據集上獲勝。對于基準測試，這些結果是在手動優化和預先給出初始簇/ 狀態數的條件下獲得的，這實際上使我們提出的算法處于不利的位置。

為了說明我們提出的算法在預先確定給定數據集的聚類數方面具有優勢，我們用符號*報告了分類精度的實驗結果，以表明在確定正確的聚類數的情況下達到了準確性。 可以看出，我們的方法能夠在16 個數據集中的12 個數據集中找到正確的群集編號，但是標準模型選擇技術（BIC）只能設法找到7 個數據集的正確群集編號。

表2 時間序列基準上的聚類算法的分類準確性（%）

在此實驗模擬中，從不同的角度顯示了許多方法來解決時間數據聚類問題。作為基準算法，K-means 僅使用歐幾里得距離來基于局部比較來測量時間序列之間的相似性，其中時間序列是點對點對齊的。這種基線技術無法獲得令人滿意的結果，尤其是當時間序列的觀測值發生偏移時，例如Gun-Point，CBF 和Two Patterns。為了克服這些限制，通過使用動態編程技術開發了動態時間規整（DTW）距離[53]，該技術從兩個時間序列之間的最佳對齊中確定了規整距離。從表2 中所示的結果可以看出，在16 個數據集中的12 個數據集中，基于DTW的K 均值優于標準K 均值。但是，對于OSU Leaf，Lightning-2 和Yoga 等高維時間序列，基于DTW 的K-mean 所獲得的結果幾乎沒有改善，但比其他算法花費的時間要長得多。盡管基于HMM 的聚類技術設法通過考慮時間序列的時間信息來捕獲聚類結構，但所取得的進步仍然有限。對表2 中列出的結果進行的比較研究表明，我們的方法在模型選擇和分類準確性方面均達到了最佳性能。它通常適用于高維時間序列，并在最長的時間序列（包括OSU Leaf，Lighting-2，Lighting-7 和Yoga）上獲得最佳結果。此外，表2 還表明，我們的方法通過贏得16 個數據集中的13 個數據集，勝過HMM 混合元聚類集成作為其原型，這顯然證明了擬議的Bi-weighting 方案的有效性。

3 結束語

在本文中，我們報告了一種新穎的基于HMM 的混合元聚類與集成技術相結合的時態數據聚類，并進一步提出了從對聚類集成的目標函數進行形式分析得出的Bi-加權方案。在各種時態數據集上的仿真結果表明，我們的方法在時態數據聚類分析中取得了令人鼓舞的性能，適用于未知環境中的應用。結果，對于我們提出的方法，可以突出四個主要優點，包括：（i）通過基于HMM 的分區聚類的集成來解決模型初始化問題；（ii）可以通過在與DSPA 關聯的共識分區上應用基于HMM 的層次聚類來自動確定適當的聚類編號。（iii）根據分區和集群之間的最佳協同作用，研究了一種Bi-weighting方案來獲得改進的集群集成解決方案；最后（iv）通過應用復合模型來驅動最終精煉過程，可以有效地捕獲簇的內在結構。

可以考慮進一步研究以解決基于HMM 的聚類的狀態發射概率問題。在文獻報道的現有工作中，通常將狀態發射概率建模為多元高斯模型。如何為單個狀態發射函數選擇高斯分量的數量仍然是一個懸而未決的問題。通常，已經發現多元高斯比單高斯提供更好的性能[59]，但是由于高計算需求和對有限訓練數據集的過度擬合，其使用受到限制。此外，如何確定狀態數對于HMM 模型配置也至關重要。基于模型的聚類算法的現有工作通常與用于參數估計的EM 算法相關聯。然而，這種基于EM 的參數估計遭受局部最優和收斂困難的問題。雖然我們提出的算法提供了一個有前途的解決方案，但它在生成輸入分區的集合方面非常耗時，這對于在線應用程序可能至關重要。因此，如何找到計算成本與分類精度之間的折衷方案仍然是集成技術研究的一個有趣的課題。