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

（云南電網(wǎng)有限責(zé)任公司信息中心，昆明 650217）

0 前言

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

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

1）雖然研究人員己經(jīng)針對(duì)時(shí)間序列提出許多特征表示（representation）方法，但是每一種方法對(duì)于時(shí)間序列信息的還原都具有片面性，某一種特征表示方法只能提取時(shí)間序列中某些特征信息，并且通常無(wú)法全面地反映出目標(biāo)數(shù)據(jù)集的簇結(jié)構(gòu)信息，有些特征甚至?xí)煜龜?shù)據(jù)的簇結(jié)構(gòu),導(dǎo)致聚類(lèi)算法失效。如何選取最佳的有助于呈現(xiàn)目標(biāo)數(shù)據(jù)集的聚類(lèi)分析的特征表示仍然是一個(gè)棘手的問(wèn)題。

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

3）針對(duì)時(shí)間序列所使用的聚類(lèi)算法普遍具有單一性，沒(méi)有一種聚類(lèi)算法可以普遍適用于各種時(shí)間序列數(shù)據(jù)集所呈現(xiàn)出來(lái)的復(fù)雜簇結(jié)構(gòu)。一種聚類(lèi)算法一般只適合于某種情況的聚類(lèi)分析。此外，在進(jìn)行聚類(lèi)之前都需要用戶(hù)事先確定要得到的聚類(lèi)的數(shù)目（類(lèi)數(shù)）。然而在現(xiàn)實(shí)數(shù)據(jù)中，類(lèi)數(shù)是未知的，通常要經(jīng)過(guò)不斷的實(shí)驗(yàn)來(lái)獲得合適的類(lèi)數(shù)，以得到較好的聚類(lèi)結(jié)果。

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

1）如何在沒(méi)有先驗(yàn)知識(shí)的條件下，合理地組合大量的初始聚類(lèi)分析結(jié)果以達(dá)到最優(yōu)融合，仍然存在諸多亟待解決的問(wèn)題。

2）由于聚類(lèi)集成算法是一種無(wú)監(jiān)督學(xué)習(xí)過(guò)程，因此，如何正確有效地識(shí)別類(lèi)簇的本征類(lèi)數(shù)仍然是一個(gè)棘手的問(wèn)題。

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

1 算法描述

本課題提出的算法模型由三個(gè)模塊組成，包括了特征抽取，初始化聚類(lèi)分析，雙加權(quán)聚類(lèi)集成學(xué)習(xí)。其擬算法流程如圖1 所示。模型構(gòu)建的研究方案如下。

圖1 基于多特征表示的雙加權(quán)聚類(lèi)集成模型

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

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

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

在初始聚類(lèi)分析模塊中，我們?cè)诓煌奶卣骺臻g里，給定不同的初始化設(shè)置，對(duì)目標(biāo)數(shù)據(jù)集進(jìn)行聚類(lèi)分析，如使用k-mean 算法，會(huì)產(chǎn)生多個(gè)不同的劃分。由此可以有效地增加各劃分的差異性（Diversity），從而提高聚類(lèi)集成學(xué)習(xí)的性能。以往的研究證明聚類(lèi)集成學(xué)習(xí)的性能取決于初始聚類(lèi)分析的質(zhì)量和其產(chǎn)生的劃分的差異性。

1.3 雙加權(quán)聚類(lèi)集成(Bi-weighted clustering ensemble)

為了確保類(lèi)簇和它們的劃分根據(jù)其重要性對(duì)融合產(chǎn)生建設(shè)性的貢獻(xiàn)，我們引入了一個(gè)雙權(quán)重方案以?xún)?yōu)化輸入劃分的融合。這樣，不僅將權(quán)重根據(jù)他們的聚類(lèi)質(zhì)量全局地分配到了輸入劃分，而且權(quán)重的局部分配能自適應(yīng)于類(lèi)簇本身產(chǎn)生的對(duì)應(yīng)劃分。

1）雙加權(quán)框架

給出一個(gè)距離變量D，加權(quán)聚類(lèi)集成的融合函數(shù)是為找出接近多重輸入劃分的一個(gè)融合劃分Pr，輸入劃分是從目標(biāo)數(shù)據(jù)集中獲得。因此，融合用公式可以表示為成本函數(shù)的最小化，如下所示：

其中wm指的是劃分Pm的權(quán)重，

在基于模型的聚類(lèi)中，每個(gè)輸入劃分Pm被表示為一個(gè)概率分布的混合其中是混合模型參數(shù)，Km是每個(gè)輸入劃分的類(lèi)簇?cái)?shù)，表示聚類(lèi)，p(km) 表示先驗(yàn)概率。基于KL 距離，公式(5)中的花費(fèi)函數(shù)可以被進(jìn)一步地推導(dǎo)為：

公式(6)中的花費(fèi)函數(shù)可以被分解成兩個(gè)子花費(fèi)函數(shù)J1 和J2，這表明了一個(gè)聚類(lèi)集成算法的性能依賴(lài)于聚類(lèi)集成和輸入劃分的質(zhì)量。其中，第一項(xiàng)J1 對(duì)應(yīng)于輸入劃分的質(zhì)量，J1 的值越小意味著輸入劃分的質(zhì)量越好。事實(shí)上，聚類(lèi)的目的在于將目標(biāo)數(shù)據(jù)集劃分到不同的組或類(lèi)中，使得同一個(gè)分組/類(lèi)中數(shù)據(jù)點(diǎn)具有較高的相似性，相似性由一個(gè)類(lèi)間距離來(lái)確定，不同類(lèi)間的相異性通過(guò)集群(類(lèi)簇)的距離來(lái)確定。也就是說(shuō)，Dlk測(cè)量和劃分Pm中剩余的類(lèi)的集群內(nèi)間距離，其中，表示類(lèi)數(shù)據(jù)點(diǎn)的相似性。因此，輸入劃分Pm的聚類(lèi)質(zhì)量可以用公式表示為：

CQm的最小值標(biāo)識(shí)著輸入劃分的最佳質(zhì)量，其中類(lèi)簇集群內(nèi)部的距離應(yīng)該小，而類(lèi)簇間的聚類(lèi)應(yīng)該大。

直觀地，劃分權(quán)重應(yīng)該由J1 的最小花費(fèi)確定，其中較大的權(quán)重應(yīng)該被分配給較好的劃分質(zhì)量，較好的劃分質(zhì)量由較小的CQm值所決定。然而，這種簡(jiǎn)單的方法可以分配一個(gè)單一的最大權(quán)重給具有最小CQm值的輸入劃分，同時(shí)其他所有的權(quán)重都被置零。在這種情況下，融合函數(shù)轉(zhuǎn)變成了選擇函數(shù)。為了是所有的輸入劃分促成融合劃分，我們?cè)贘1 中引入了一個(gè)表示劃分權(quán)重負(fù)熵的正則項(xiàng)wmlogwm，構(gòu)成了一個(gè)正規(guī)化的花費(fèi)函數(shù)：

其中α≥0 是一個(gè)拉格朗日乘數(shù)，控制著額外正則項(xiàng)的強(qiáng)度，增加它的值將會(huì)加大輸入劃分的enthusiasm。在我們的仿真實(shí)驗(yàn)中設(shè)定α=0.5。

因此，適當(dāng)?shù)膭澐謾?quán)重可以通過(guò)J3 的最小劃分來(lái)確定[51]：

一旦得到了輸入劃分和對(duì)應(yīng)的權(quán)重，J 的第一項(xiàng)J1 就被固定了，所以聚類(lèi)集成的性能主要由J2 控制。因此，J2 的最小值等價(jià)于J 的最小花費(fèi)。為了優(yōu)化這個(gè)過(guò)程，我們引入了雙層加權(quán)方法來(lái)判定接近所有類(lèi)簇的融合劃分。在花費(fèi)函數(shù)J2 中，第一層權(quán)重是通過(guò)公式(9) 得到劃分權(quán)重，第二層權(quán)重是類(lèi)簇的權(quán)重，可以被定義為：

其中是具有劃分Pm的聚類(lèi)中數(shù)據(jù)點(diǎn)的數(shù)目，而N 是所有數(shù)據(jù)點(diǎn)的總數(shù)。2）共識(shí)函數(shù)

現(xiàn)有的聚類(lèi)集成技術(shù)應(yīng)用了三個(gè)hyper graph-based 的融合函數(shù)來(lái)產(chǎn)生融合劃分。因此，需要將大量的輸入劃分通過(guò)連接所有的二進(jìn)制成員指示器映射到一個(gè)hypergraph。指示器是映射每一個(gè)輸入劃分Pm到一個(gè)鄰接矩陣以制作一個(gè)超圖得到，為了進(jìn)一步改進(jìn)在我們?cè)O(shè)計(jì)方案中hypergraph-based 融合劃分，我們提出了一個(gè)加權(quán)的hypergraph，定義如下：

為了導(dǎo)出集成的融合劃分，我們應(yīng)用了三個(gè)融合函數(shù)來(lái)確保不同的視角都被考慮到。包括了基于聚類(lèi)的相似性劃分算法(CSPA)、hypergraph-partitioning algorithm (HGPA)和the meta-clustering algorithm (MCLA)。其中CSPA是一個(gè)簡(jiǎn)單的融合函數(shù)，距離矩陣S 在加權(quán)的hypergraph 中對(duì)所有的劃分進(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ò)鑄造聚類(lèi)集成問(wèn)題，關(guān)于通過(guò)剪切最小加權(quán)超編怎樣劃分加權(quán)的hypergraphy，不像CSPA 把局部分段相似帶入計(jì)算，HGPA 關(guān)心跨域不同劃分序列的相對(duì)全局關(guān)系。最后，元聚類(lèi)算法(MCLA)通過(guò)聚集多個(gè)輸入劃分實(shí)現(xiàn)融合。其基本思想是重新聚類(lèi)加權(quán)的超邊(hyper-edges)，生成融合函數(shù)，聚類(lèi)的總數(shù)減少到由用戶(hù)指定的元聚類(lèi)的一個(gè)小數(shù)目。

3）目標(biāo)函數(shù)

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

其中Pa,Pb表示兩個(gè)劃分的標(biāo)簽，將N 個(gè)對(duì)象的目標(biāo)數(shù)據(jù)集劃分到Ka和Kb兩個(gè)類(lèi)簇中，是類(lèi)簇和之間共享對(duì)象的數(shù)目，和分別表示和的對(duì)象數(shù)目。

根據(jù)公式，最優(yōu)融合劃分通過(guò)搜尋從HMM K-models 聚類(lèi)集成中獲得的M 個(gè)劃分的最大平均互信息來(lái)確定，為此，通過(guò)下面的優(yōu)化方程來(lái)確定這三個(gè)函數(shù)的最佳融合。

其中Pm是HMM 的K-models 生成的第m個(gè)劃分，Pr是第r個(gè)融合函數(shù)產(chǎn)生的融合劃分?？傊?，融合函數(shù)篩選出的劃分Po作為給出時(shí)序數(shù)據(jù)集的最優(yōu)融合劃分。

2 實(shí)驗(yàn)驗(yàn)證

為了評(píng)估總體上對(duì)時(shí)間數(shù)據(jù)進(jìn)行聚類(lèi)的方法的性能，我們通過(guò)使用時(shí)間序列集合作為測(cè)試數(shù)據(jù)集來(lái)進(jìn)行模型驗(yàn)證[52]。該基準(zhǔn)數(shù)據(jù)集包含16 個(gè)合成或真實(shí)時(shí)間序列的數(shù)據(jù)集。表1 中列出了有關(guān)所有16 個(gè)數(shù)據(jù)集的特定信息，包括每個(gè)數(shù)據(jù)集中的類(lèi)數(shù)，時(shí)間序列數(shù)和時(shí)間序列長(zhǎng)。

表1 時(shí)間序列基準(zhǔn)數(shù)據(jù)集信息

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

我們使用最佳參數(shù)設(shè)置將每種算法運(yùn)行10次，表2 中列出了每種經(jīng)過(guò)測(cè)試的算法的最佳結(jié)果，從中可以看出，我們的方法在16 個(gè)數(shù)據(jù)集中的8 個(gè)上獲得了最佳性能。相比之下，基于DTW 的K-mean 可以在三個(gè)數(shù)據(jù)集上獲得最佳結(jié)果，而所有其他數(shù)據(jù)只能分別在一個(gè)數(shù)據(jù)集上獲勝。對(duì)于基準(zhǔn)測(cè)試，這些結(jié)果是在手動(dòng)優(yōu)化和預(yù)先給出初始簇/ 狀態(tài)數(shù)的條件下獲得的，這實(shí)際上使我們提出的算法處于不利的位置。

為了說(shuō)明我們提出的算法在預(yù)先確定給定數(shù)據(jù)集的聚類(lèi)數(shù)方面具有優(yōu)勢(shì)，我們用符號(hào)*報(bào)告了分類(lèi)精度的實(shí)驗(yàn)結(jié)果，以表明在確定正確的聚類(lèi)數(shù)的情況下達(dá)到了準(zhǔn)確性。 可以看出，我們的方法能夠在16 個(gè)數(shù)據(jù)集中的12 個(gè)數(shù)據(jù)集中找到正確的群集編號(hào)，但是標(biāo)準(zhǔn)模型選擇技術(shù)（BIC）只能設(shè)法找到7 個(gè)數(shù)據(jù)集的正確群集編號(hào)。

表2 時(shí)間序列基準(zhǔn)上的聚類(lèi)算法的分類(lèi)準(zhǔn)確性（%）

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

3 結(jié)束語(yǔ)

在本文中，我們報(bào)告了一種新穎的基于HMM 的混合元聚類(lèi)與集成技術(shù)相結(jié)合的時(shí)態(tài)數(shù)據(jù)聚類(lèi)，并進(jìn)一步提出了從對(duì)聚類(lèi)集成的目標(biāo)函數(shù)進(jìn)行形式分析得出的Bi-加權(quán)方案。在各種時(shí)態(tài)數(shù)據(jù)集上的仿真結(jié)果表明，我們的方法在時(shí)態(tài)數(shù)據(jù)聚類(lèi)分析中取得了令人鼓舞的性能，適用于未知環(huán)境中的應(yīng)用。結(jié)果，對(duì)于我們提出的方法，可以突出四個(gè)主要優(yōu)點(diǎn)，包括：（i）通過(guò)基于HMM 的分區(qū)聚類(lèi)的集成來(lái)解決模型初始化問(wèn)題；（ii）可以通過(guò)在與DSPA 關(guān)聯(lián)的共識(shí)分區(qū)上應(yīng)用基于HMM 的層次聚類(lèi)來(lái)自動(dòng)確定適當(dāng)?shù)木垲?lèi)編號(hào)。（iii）根據(jù)分區(qū)和集群之間的最佳協(xié)同作用，研究了一種Bi-weighting方案來(lái)獲得改進(jìn)的集群集成解決方案；最后（iv）通過(guò)應(yīng)用復(fù)合模型來(lái)驅(qū)動(dòng)最終精煉過(guò)程，可以有效地捕獲簇的內(nèi)在結(jié)構(gòu)。

可以考慮進(jìn)一步研究以解決基于HMM 的聚類(lèi)的狀態(tài)發(fā)射概率問(wèn)題。在文獻(xiàn)報(bào)道的現(xiàn)有工作中，通常將狀態(tài)發(fā)射概率建模為多元高斯模型。如何為單個(gè)狀態(tài)發(fā)射函數(shù)選擇高斯分量的數(shù)量仍然是一個(gè)懸而未決的問(wèn)題。通常，已經(jīng)發(fā)現(xiàn)多元高斯比單高斯提供更好的性能[59]，但是由于高計(jì)算需求和對(duì)有限訓(xùn)練數(shù)據(jù)集的過(guò)度擬合，其使用受到限制。此外，如何確定狀態(tài)數(shù)對(duì)于HMM 模型配置也至關(guān)重要?；谀Ｐ偷木垲?lèi)算法的現(xiàn)有工作通常與用于參數(shù)估計(jì)的EM 算法相關(guān)聯(lián)。然而，這種基于EM 的參數(shù)估計(jì)遭受局部最優(yōu)和收斂困難的問(wèn)題。雖然我們提出的算法提供了一個(gè)有前途的解決方案，但它在生成輸入分區(qū)的集合方面非常耗時(shí)，這對(duì)于在線應(yīng)用程序可能至關(guān)重要。因此，如何找到計(jì)算成本與分類(lèi)精度之間的折衷方案仍然是集成技術(shù)研究的一個(gè)有趣的課題。