胡健,王海林,肖鵬,尹君
(云南電網(wǎng)有限責(zé)任公司信息中心,昆明 650217)
時間序列是一種廣泛存在的數(shù)據(jù),是由客觀對象的某個物理量在不同時間點的采值按時間順序排列成的序列數(shù)據(jù),時間序列客觀記錄了所觀測的系統(tǒng)在各個單位時間點上的狀態(tài)值,所以可以通過研究時間序列數(shù)據(jù)來辨識、重構(gòu)和預(yù)測所觀測系統(tǒng)的行為模式。時間序列具有普遍存在性,多媒體數(shù)據(jù),金融數(shù)據(jù),氣象數(shù)據(jù),人口普查數(shù)據(jù)都是時間序列數(shù)據(jù)類型。研究如何有效地從這些復(fù)雜的海量時間序列數(shù)據(jù)中挖掘隱藏的、有價值的信息與知識,具有重要的理論價值和現(xiàn)實意義。時間序列數(shù)據(jù)挖掘(Time Series Data Mining)已成為數(shù)據(jù)挖掘研究領(lǐng)域中主要的研究對象[1]。時間序列數(shù)據(jù)挖掘巨大的科學(xué)意義與應(yīng)用價值正在受到世界許多國家學(xué)術(shù)界、工業(yè)界和政府部門的普遍重視。2005 年,香港中文大學(xué)的研究者做了一項關(guān)于數(shù)據(jù)挖掘研究中最具挑戰(zhàn)性問題的研究報告,將時間序列數(shù)據(jù)挖掘列為數(shù)據(jù)挖掘中最具挑戰(zhàn)性的十大研究方向之一[2]。2014 年10 月,Twitter 公司開源了云環(huán)境時間序列數(shù)據(jù)斷層檢測工具Breakout[3]。2012 年,奧巴馬政府投資2 億美金啟動“大數(shù)據(jù)研究和發(fā)展計劃”,并在2017 年發(fā)布了第二輪大數(shù)據(jù)研究項目,其中白宮科技政策辦公室正在建立流行病“天氣預(yù)報”項目,旨在利用大數(shù)據(jù)方法,能夠盡早對流行病作出識別和預(yù)測,以便預(yù)做準(zhǔn)備,減輕癥狀,其本質(zhì)就是時間序列數(shù)據(jù)挖掘[4]。
時間序列數(shù)據(jù)挖掘與傳統(tǒng)的數(shù)據(jù)挖掘最大的區(qū)別在于其數(shù)據(jù)的時效性與有序性,是一個發(fā)現(xiàn)潛在有用的,與時間屬性相關(guān)的信息與知識的過程,其主要包括時間序列相似性挖掘、特異性挖掘與規(guī)律性挖掘。數(shù)據(jù)挖掘技術(shù)大致包括:統(tǒng)計學(xué)方法、聚類分析、決策樹技術(shù)、人工神經(jīng)網(wǎng)絡(luò)、規(guī)則歸納,以及可視化技術(shù)等等,本課題將主要研究時間序列數(shù)據(jù)挖掘的聚類分析技術(shù)。盡管研究人員在時間序列聚類分析的研究上已經(jīng)取得了許多成果,但由于時間序列數(shù)據(jù)本身具有非常復(fù)雜的特性,如:復(fù)雜時間相關(guān)性,高維度,海量性、噪聲干擾,使得時間序列數(shù)據(jù)挖掘的工作充滿挑戰(zhàn),依然面臨以下亟待解決的關(guān)鍵問題[5]:
1)雖然研究人員己經(jīng)針對時間序列提出許多特征表示(representation)方法,但是每一種方法對于時間序列信息的還原都具有片面性,某一種特征表示方法只能提取時間序列中某些特征信息,并且通常無法全面地反映出目標(biāo)數(shù)據(jù)集的簇結(jié)構(gòu)信息,有些特征甚至?xí)煜龜?shù)據(jù)的簇結(jié)構(gòu),導(dǎo)致聚類算法失效。如何選取最佳的有助于呈現(xiàn)目標(biāo)數(shù)據(jù)集的聚類分析的特征表示仍然是一個棘手的問題。
2)現(xiàn)有的時間序列相似性度量用多種距離公式,如,歐氏距離(Euclidean Distance) ,馬氏距離(Mahalanobis Distance) ,對數(shù)似然距離(log-likelihood Distance),動態(tài)時間彎曲距離(Dynamic Time Warping)等[6]。但是在實際操作中,每一種特征表示方法都有其對應(yīng)的最佳相似性度量方法。如何確定最佳的匹配仍需要大量的先驗人為應(yīng)驗。此外,很多相似性度量公式具有較高的計算復(fù)雜度,針對高緯度,海量的時間序列數(shù)據(jù)集進(jìn)行聚類分析時,需要較高的計算資源,而且都含有需要用戶設(shè)置合理的參數(shù),同時在聚類過程中,待聚類的數(shù)據(jù)都是在距離閩值的強(qiáng)制作用下聚合或分離,無法準(zhǔn)確體現(xiàn)數(shù)據(jù)對象間自發(fā),天然的聚散關(guān)系。
3)針對時間序列所使用的聚類算法普遍具有單一性,沒有一種聚類算法可以普遍適用于各種時間序列數(shù)據(jù)集所呈現(xiàn)出來的復(fù)雜簇結(jié)構(gòu)。一種聚類算法一般只適合于某種情況的聚類分析。此外,在進(jìn)行聚類之前都需要用戶事先確定要得到的聚類的數(shù)目(類數(shù))。然而在現(xiàn)實數(shù)據(jù)中,類數(shù)是未知的,通常要經(jīng)過不斷的實驗來獲得合適的類數(shù),以得到較好的聚類結(jié)果。
集成學(xué)習(xí)(Ensemble Learning) 是指利用多個學(xué)習(xí)機(jī)解決一個問題。隨著其飛速發(fā)展,研究人員嘗試使用此類方法解決上述時間序列數(shù)據(jù)挖掘的難點問題,并取得了一系列創(chuàng)新性研究成果。聚類集成學(xué)習(xí)(Clustering Ensemble)的目的是通過集成多個互補(bǔ)的聚類結(jié)果以得到一個高可靠性的聚類分析系統(tǒng),旨在產(chǎn)生泛化能力強(qiáng)、差異大的多個成員聚類器,充分發(fā)揮每個成員聚類器在各自聚類性能上的優(yōu)勢,獲得比單個成員聚類器都要好的聚類集成結(jié)果。與單一的聚類算法相比,聚類集成學(xué)習(xí)具有三大優(yōu)勢[7]:聚類集成結(jié)果具有更高的精確度;聚類集成學(xué)習(xí)可以發(fā)掘單一聚類算法無法發(fā)掘的簇信息;聚類集成學(xué)習(xí)對于復(fù)雜環(huán)境,如:噪聲,異常數(shù)據(jù)點,采樣變化,有較強(qiáng)的抗干擾能力。一般通過提高成員聚類器的聚類性能以及增加成員聚類器的差異性(Diversity)來達(dá)到提高集成性能的目的。但現(xiàn)有的聚類集成學(xué)習(xí)算法依然存在諸多問題[8],具體分析如下:
1)如何在沒有先驗知識的條件下,合理地組合大量的初始聚類分析結(jié)果以達(dá)到最優(yōu)融合,仍然存在諸多亟待解決的問題。
2)由于聚類集成算法是一種無監(jiān)督學(xué)習(xí)過程,因此,如何正確有效地識別類簇的本征類數(shù)仍然是一個棘手的問題。
針對上述問題,本課題在非監(jiān)督學(xué)習(xí)的理論框架內(nèi),深入研究基于生成模型和特征表示的時間序列數(shù)據(jù)挖掘算法,提出兩種新型的雙加權(quán)聚類集成學(xué)習(xí)模型,從不同角度進(jìn)一步提高集成算法在時間序列聚類分析中的性能。本課題將目前時間序列聚類算法以及聚類集成算法中的幾個關(guān)鍵性難點問題(包括:時間序列特征表示和生成模型表示方法;多成員聚類器的產(chǎn)生和融合;以及聚類分析中的類數(shù)自確定)納入統(tǒng)一的算法框架,為復(fù)雜多樣的時間序列數(shù)據(jù)集的聚類分析提供了一套可行的通用技術(shù)路線。
本課題提出的算法模型由三個模塊組成,包括了特征抽取,初始化聚類分析,雙加權(quán)聚類集成學(xué)習(xí)。其擬算法流程如圖1 所示。模型構(gòu)建的研究方案如下。
圖1 基于多特征表示的雙加權(quán)聚類集成模型
時間序列表征通??梢苑譃閮纱箢?分段式的(piecewise)和全局式的(global )。一個分段式的特征表示(piecewise representation)根據(jù)一個分割標(biāo)準(zhǔn)把高維的時間序列向量分解成一系列的分段向量,然后對每個分段做特征提取,所有分段的特征表示按序排列組成一個完整的分段式特征表示(piecewise representation),例如,自適應(yīng)分段常數(shù)近似(Adaptive Piecewise Constant Approximation) 和分段式主成分分析(piecewise Principal Component Analysis)。在全局式特征表征(global representation)中,我們用基函數(shù)來模擬目標(biāo)時間序列數(shù)據(jù)集,因此,基函數(shù)的回歸系數(shù)構(gòu)成了時間序列的特征表示,例如,多項式擬合(polynomial curve fitting),離散傅里葉變換(discrete Fourier transforms),和離散小波變換(discrete wavelet transforms)。一般情況下,分段式(piecewise)和全局式(global)的時間序列特征表征具有一定的互補(bǔ)性。分段式注重局部信息的表述,但容易忽略全局信息。相反,全局式可以很好的還原時間序列的整體特征,但對局部信息的提取不夠完整。在此模塊中我們將選取多個特征表示方法,使其對時間序列的特征描述上具有最大程度的互補(bǔ)性。
在初始聚類分析模塊中,我們在不同的特征空間里,給定不同的初始化設(shè)置,對目標(biāo)數(shù)據(jù)集進(jìn)行聚類分析,如使用k-mean 算法,會產(chǎn)生多個不同的劃分。由此可以有效地增加各劃分的差異性(Diversity),從而提高聚類集成學(xué)習(xí)的性能。以往的研究證明聚類集成學(xué)習(xí)的性能取決于初始聚類分析的質(zhì)量和其產(chǎn)生的劃分的差異性。
為了確保類簇和它們的劃分根據(jù)其重要性對融合產(chǎn)生建設(shè)性的貢獻(xiàn),我們引入了一個雙權(quán)重方案以優(yōu)化輸入劃分的融合。這樣,不僅將權(quán)重根據(jù)他們的聚類質(zhì)量全局地分配到了輸入劃分,而且權(quán)重的局部分配能自適應(yīng)于類簇本身產(chǎn)生的對應(yīng)劃分。
1)雙加權(quán)框架
給出一個距離變量D,加權(quán)聚類集成的融合函數(shù)是為找出接近多重輸入劃分的一個融合劃分Pr,輸入劃分是從目標(biāo)數(shù)據(jù)集中獲得。因此,融合用公式可以表示為成本函數(shù)的最小化,如下所示:
其中wm指的是劃分Pm的權(quán)重,
在基于模型的聚類中,每個輸入劃分Pm被表示為一個概率分布的混合其中是混合模型參數(shù),Km是每個輸入劃分的類簇數(shù),表示聚類,p(km) 表示先驗概率?;贙L 距離,公式(5)中的花費(fèi)函數(shù)可以被進(jìn)一步地推導(dǎo)為:
公式(6)中的花費(fèi)函數(shù)可以被分解成兩個子花費(fèi)函數(shù)J1 和J2,這表明了一個聚類集成算法的性能依賴于聚類集成和輸入劃分的質(zhì)量。其中,第一項J1 對應(yīng)于輸入劃分的質(zhì)量,J1 的值越小意味著輸入劃分的質(zhì)量越好。事實上,聚類的目的在于將目標(biāo)數(shù)據(jù)集劃分到不同的組或類中,使得同一個分組/類中數(shù)據(jù)點具有較高的相似性,相似性由一個類間距離來確定,不同類間的相異性通過集群(類簇)的距離來確定。也就是說,Dlk測量和劃分Pm中剩余的類的集群內(nèi)間距離,其中,表示類數(shù)據(jù)點的相似性。因此,輸入劃分Pm的聚類質(zhì)量可以用公式表示為:
CQm的最小值標(biāo)識著輸入劃分的最佳質(zhì)量,其中類簇集群內(nèi)部的距離應(yīng)該小,而類簇間的聚類應(yīng)該大。
直觀地,劃分權(quán)重應(yīng)該由J1 的最小花費(fèi)確定,其中較大的權(quán)重應(yīng)該被分配給較好的劃分質(zhì)量,較好的劃分質(zhì)量由較小的CQm值所決定。然而,這種簡單的方法可以分配一個單一的最大權(quán)重給具有最小CQm值的輸入劃分,同時其他所有的權(quán)重都被置零。在這種情況下,融合函數(shù)轉(zhuǎn)變成了選擇函數(shù)。為了是所有的輸入劃分促成融合劃分,我們在J1 中引入了一個表示劃分權(quán)重負(fù)熵的正則項wmlogwm,構(gòu)成了一個正規(guī)化的花費(fèi)函數(shù):
其中α≥0 是一個拉格朗日乘數(shù),控制著額外正則項的強(qiáng)度,增加它的值將會加大輸入劃分的enthusiasm。在我們的仿真實驗中設(shè)定α=0.5。
因此,適當(dāng)?shù)膭澐謾?quán)重可以通過J3 的最小劃分來確定[51]:
一旦得到了輸入劃分和對應(yīng)的權(quán)重,J 的第一項J1 就被固定了,所以聚類集成的性能主要由J2 控制。因此,J2 的最小值等價于J 的最小花費(fèi)。為了優(yōu)化這個過程,我們引入了雙層加權(quán)方法來判定接近所有類簇的融合劃分。在花費(fèi)函數(shù)J2 中,第一層權(quán)重是通過公式(9) 得到劃分權(quán)重,第二層權(quán)重是類簇的權(quán)重,可以被定義為:
其中是具有劃分Pm的聚類中數(shù)據(jù)點的數(shù)目,而N 是所有數(shù)據(jù)點的總數(shù)。2)共識函數(shù)
現(xiàn)有的聚類集成技術(shù)應(yīng)用了三個hyper graph-based 的融合函數(shù)來產(chǎn)生融合劃分。因此,需要將大量的輸入劃分通過連接所有的二進(jìn)制成員指示器映射到一個hypergraph。指示器是映射每一個輸入劃分Pm到一個鄰接矩陣以制作一個超圖得到,為了進(jìn)一步改進(jìn)在我們設(shè)計方案中hypergraph-based 融合劃分,我們提出了一個加權(quán)的hypergraph,定義如下:
為了導(dǎo)出集成的融合劃分,我們應(yīng)用了三個融合函數(shù)來確保不同的視角都被考慮到。包括了基于聚類的相似性劃分算法(CSPA)、hypergraph-partitioning algorithm (HGPA)和the meta-clustering algorithm (MCLA)。其中CSPA是一個簡單的融合函數(shù),距離矩陣S 在加權(quán)的hypergraph 中對所有的劃分進(jìn)行加密,派生于鄰接矩陣WH:S=WHWHT,then the similarities yielded from multiple partitions are used to recluster all the sequences to yield a consensus,HGPA 提供了替代的融合函數(shù),通過鑄造聚類集成問題,關(guān)于通過剪切最小加權(quán)超編怎樣劃分加權(quán)的hypergraphy,不像CSPA 把局部分段相似帶入計算,HGPA 關(guān)心跨域不同劃分序列的相對全局關(guān)系。最后,元聚類算法(MCLA)通過聚集多個輸入劃分實現(xiàn)融合。其基本思想是重新聚類加權(quán)的超邊(hyper-edges),生成融合函數(shù),聚類的總數(shù)減少到由用戶指定的元聚類的一個小數(shù)目。
3)目標(biāo)函數(shù)
沒有先驗知識,就不可能提前選擇一個合適的函數(shù)以形成聚類集成。既有的解決辦法都是使用歸一化互信息(NMI)根據(jù)目標(biāo)函數(shù)[45]來測量任何兩個劃分之間的一致性,用公式表述如下:
其中Pa,Pb表示兩個劃分的標(biāo)簽,將N 個對象的目標(biāo)數(shù)據(jù)集劃分到Ka和Kb兩個類簇中,是類簇和之間共享對象的數(shù)目,和分別表示和的對象數(shù)目。
根據(jù)公式,最優(yōu)融合劃分通過搜尋從HMM K-models 聚類集成中獲得的M 個劃分的最大平均互信息來確定,為此,通過下面的優(yōu)化方程來確定這三個函數(shù)的最佳融合。
其中Pm是HMM 的K-models 生成的第m個劃分,Pr是第r個融合函數(shù)產(chǎn)生的融合劃分。總之,融合函數(shù)篩選出的劃分Po作為給出時序數(shù)據(jù)集的最優(yōu)融合劃分。
為了評估總體上對時間數(shù)據(jù)進(jìn)行聚類的方法的性能,我們通過使用時間序列集合作為測試數(shù)據(jù)集來進(jìn)行模型驗證[52]。該基準(zhǔn)數(shù)據(jù)集包含16 個合成或真實時間序列的數(shù)據(jù)集。表1 中列出了有關(guān)所有16 個數(shù)據(jù)集的特定信息,包括每個數(shù)據(jù)集中的類數(shù),時間序列數(shù)和時間序列長。
表1 時間序列基準(zhǔn)數(shù)據(jù)集信息
為了實驗效果比對,我們最初在時間序列的基準(zhǔn)集合上測試了5 種技術(shù),包括K 均值,基于動態(tài)時間規(guī)整(DTW)的K 均值[53],基于HMM 的K 模型,HMM 混合聚類和HMM 混合元聚類,其中K-mean 算法的結(jié)果由基準(zhǔn)收集器提供。為了檢查所提出的雙向加權(quán)方案的有效性,我們還將我們的方法與其HMM 混合元聚類集成體的原型進(jìn)行了比較,并觀察了引入的雙向加權(quán)方案如何能夠有效地提高聚類集成體的性能。對于基于HMM 的聚類算法,HMM 的狀態(tài)數(shù)對于時間序列建模至關(guān)重要。但是,此類信息通常不可用,因此我們只能對一系列狀態(tài)號進(jìn)行窮舉搜索,其中最佳狀態(tài)將最適合估計的HMM,從而導(dǎo)致最大的對數(shù)似然性,即所謂的“前進(jìn)”和“后退”算法[38,39]。在我們的實驗中,每個時間序列的最佳狀態(tài)數(shù)分別確定為6、2、4、9、2、6、3、10、8、8、9、6、7、8、2、3 包括在內(nèi)。每個數(shù)據(jù)集的類別編號K *也用于所選基準(zhǔn)中。由于我們提出的算法具有自動選擇模型的能力,因此我們簡單地將K 值設(shè)為預(yù)設(shè)范圍(K>1)中的簇數(shù)。
我們使用最佳參數(shù)設(shè)置將每種算法運(yùn)行10次,表2 中列出了每種經(jīng)過測試的算法的最佳結(jié)果,從中可以看出,我們的方法在16 個數(shù)據(jù)集中的8 個上獲得了最佳性能。相比之下,基于DTW 的K-mean 可以在三個數(shù)據(jù)集上獲得最佳結(jié)果,而所有其他數(shù)據(jù)只能分別在一個數(shù)據(jù)集上獲勝。對于基準(zhǔn)測試,這些結(jié)果是在手動優(yōu)化和預(yù)先給出初始簇/ 狀態(tài)數(shù)的條件下獲得的,這實際上使我們提出的算法處于不利的位置。
為了說明我們提出的算法在預(yù)先確定給定數(shù)據(jù)集的聚類數(shù)方面具有優(yōu)勢,我們用符號*報告了分類精度的實驗結(jié)果,以表明在確定正確的聚類數(shù)的情況下達(dá)到了準(zhǔn)確性。 可以看出,我們的方法能夠在16 個數(shù)據(jù)集中的12 個數(shù)據(jù)集中找到正確的群集編號,但是標(biāo)準(zhǔn)模型選擇技術(shù)(BIC)只能設(shè)法找到7 個數(shù)據(jù)集的正確群集編號。
表2 時間序列基準(zhǔn)上的聚類算法的分類準(zhǔn)確性(%)
在此實驗?zāi)M中,從不同的角度顯示了許多方法來解決時間數(shù)據(jù)聚類問題。作為基準(zhǔn)算法,K-means 僅使用歐幾里得距離來基于局部比較來測量時間序列之間的相似性,其中時間序列是點對點對齊的。這種基線技術(shù)無法獲得令人滿意的結(jié)果,尤其是當(dāng)時間序列的觀測值發(fā)生偏移時,例如Gun-Point,CBF 和Two Patterns。為了克服這些限制,通過使用動態(tài)編程技術(shù)開發(fā)了動態(tài)時間規(guī)整(DTW)距離[53],該技術(shù)從兩個時間序列之間的最佳對齊中確定了規(guī)整距離。從表2 中所示的結(jié)果可以看出,在16 個數(shù)據(jù)集中的12 個數(shù)據(jù)集中,基于DTW的K 均值優(yōu)于標(biāo)準(zhǔn)K 均值。但是,對于OSU Leaf,Lightning-2 和Yoga 等高維時間序列,基于DTW 的K-mean 所獲得的結(jié)果幾乎沒有改善,但比其他算法花費(fèi)的時間要長得多。盡管基于HMM 的聚類技術(shù)設(shè)法通過考慮時間序列的時間信息來捕獲聚類結(jié)構(gòu),但所取得的進(jìn)步仍然有限。對表2 中列出的結(jié)果進(jìn)行的比較研究表明,我們的方法在模型選擇和分類準(zhǔn)確性方面均達(dá)到了最佳性能。它通常適用于高維時間序列,并在最長的時間序列(包括OSU Leaf,Lighting-2,Lighting-7 和Yoga)上獲得最佳結(jié)果。此外,表2 還表明,我們的方法通過贏得16 個數(shù)據(jù)集中的13 個數(shù)據(jù)集,勝過HMM 混合元聚類集成作為其原型,這顯然證明了擬議的Bi-weighting 方案的有效性。
在本文中,我們報告了一種新穎的基于HMM 的混合元聚類與集成技術(shù)相結(jié)合的時態(tài)數(shù)據(jù)聚類,并進(jìn)一步提出了從對聚類集成的目標(biāo)函數(shù)進(jìn)行形式分析得出的Bi-加權(quán)方案。在各種時態(tài)數(shù)據(jù)集上的仿真結(jié)果表明,我們的方法在時態(tài)數(shù)據(jù)聚類分析中取得了令人鼓舞的性能,適用于未知環(huán)境中的應(yīng)用。結(jié)果,對于我們提出的方法,可以突出四個主要優(yōu)點,包括:(i)通過基于HMM 的分區(qū)聚類的集成來解決模型初始化問題;(ii)可以通過在與DSPA 關(guān)聯(lián)的共識分區(qū)上應(yīng)用基于HMM 的層次聚類來自動確定適當(dāng)?shù)木垲惥幪?。(iii)根據(jù)分區(qū)和集群之間的最佳協(xié)同作用,研究了一種Bi-weighting方案來獲得改進(jìn)的集群集成解決方案;最后(iv)通過應(yīng)用復(fù)合模型來驅(qū)動最終精煉過程,可以有效地捕獲簇的內(nèi)在結(jié)構(gòu)。
可以考慮進(jìn)一步研究以解決基于HMM 的聚類的狀態(tài)發(fā)射概率問題。在文獻(xiàn)報道的現(xiàn)有工作中,通常將狀態(tài)發(fā)射概率建模為多元高斯模型。如何為單個狀態(tài)發(fā)射函數(shù)選擇高斯分量的數(shù)量仍然是一個懸而未決的問題。通常,已經(jīng)發(fā)現(xiàn)多元高斯比單高斯提供更好的性能[59],但是由于高計算需求和對有限訓(xùn)練數(shù)據(jù)集的過度擬合,其使用受到限制。此外,如何確定狀態(tài)數(shù)對于HMM 模型配置也至關(guān)重要?;谀P偷木垲愃惴ǖ默F(xiàn)有工作通常與用于參數(shù)估計的EM 算法相關(guān)聯(lián)。然而,這種基于EM 的參數(shù)估計遭受局部最優(yōu)和收斂困難的問題。雖然我們提出的算法提供了一個有前途的解決方案,但它在生成輸入分區(qū)的集合方面非常耗時,這對于在線應(yīng)用程序可能至關(guān)重要。因此,如何找到計算成本與分類精度之間的折衷方案仍然是集成技術(shù)研究的一個有趣的課題。