模糊減法聚類在時(shí)間序列分段線性表示上的應(yīng)用

孫達(dá)辰 張秀萍 孫常麗

（1.牡丹江醫(yī)學(xué)院圖書館 黑龍江省牡丹江市 157011 2.牡丹江醫(yī)學(xué)院藥學(xué)院 黑龍江省牡丹江市 157011）

時(shí)間序列是一種常見且具有時(shí)間先后順序的數(shù)據(jù)，它具有時(shí)間屬性和其他變量屬性。這類數(shù)據(jù)廣泛存在于各個(gè)領(lǐng)域，如醫(yī)療心電圖、氣象溫度氣候變化、客戶行為和訂單消費(fèi)、金融股票等，近年來，相關(guān)學(xué)者對(duì)時(shí)間序列數(shù)據(jù)的挖 掘利用進(jìn)行了大量研究，在數(shù)據(jù)挖掘領(lǐng)域，時(shí)間序列則是數(shù)據(jù)挖掘的一個(gè)熱門研究領(lǐng)域。時(shí)間序列具有數(shù)據(jù)量大，維數(shù)高和更新速度快等特點(diǎn)，導(dǎo)致一般的分段線性方法難以刻畫原始時(shí)間序列的全局趨勢(shì)特征。當(dāng)前，時(shí)間序列的表示方法，主要有以下四種：基于頻域的表示方法、基于奇異值分解的方法、基于符號(hào)近似聚合的表示方法和分段線性表示方法。時(shí)間序列分段線性表示方法是從原始數(shù)據(jù)中提取重要的特征點(diǎn)，用這些特征點(diǎn)連接起來的直線表示原來的時(shí)間序列，能夠保留原時(shí)間序列的有效特征，并減少數(shù)據(jù)量。目前，時(shí)間序列分段表示中的兩個(gè)經(jīng)典算法有自頂向下的TD 方法尋找關(guān)鍵點(diǎn)和自底向上的BU 方法尋找關(guān)鍵點(diǎn)的方法，但這兩種表示方法的時(shí)間復(fù)雜度較高。近年來，出現(xiàn)很基于重要點(diǎn)的分段線性算法，就是通過考察一個(gè)點(diǎn)的特征值中部域區(qū)間內(nèi)與區(qū)間端點(diǎn)的比值如果超過已經(jīng)設(shè)置的閾值，則認(rèn)為是趨勢(shì)點(diǎn)，或者是根據(jù)序列的中極值點(diǎn)和變化幅度比較大的點(diǎn)來得到關(guān)鍵點(diǎn)的分段線性表示方法，還有基于時(shí)態(tài)邊緣算子的時(shí)間序列分段表示方法，就是根據(jù)時(shí)間序列中的特征，先計(jì)算出時(shí)間序列聽時(shí)態(tài)邊緣算子，進(jìn)而得到時(shí)間序列的邊緣點(diǎn)。以上的方法，直接以一維的時(shí)間序列做為研究對(duì)象，卻沒有充分考慮其在時(shí)間序列上的相關(guān)性。有相關(guān)文獻(xiàn)提出將時(shí)間序列數(shù)據(jù)編碼為不同類型的圖像：格拉姆角場（Gramian Angular Field, GAF）和馬爾可夫域（Markov Transition Fields, MTF）,實(shí)現(xiàn)使用圖像領(lǐng)域的識(shí)別網(wǎng)絡(luò)分類時(shí)間序列數(shù)據(jù)，這種方法需要計(jì)算量較大。基于以上的研究現(xiàn)狀，本文提出了基于模糊減法聚類的時(shí)間序列分段線性表示方法。模糊減法聚類是用來估計(jì)數(shù)據(jù)庫在多層矢量自回歸空間中聚類個(gè)數(shù)和聚類中心位置的快速多狀態(tài)數(shù)據(jù)融合算法，模糊減法聚類將每個(gè)數(shù)據(jù)點(diǎn)作為一個(gè)可能的聚類中心，通過設(shè)置模糊減法聚類函數(shù)，對(duì)數(shù)據(jù)信息流進(jìn)行多層聚焦。

1 基于模糊減法聚類的時(shí)間序列分段線性表示方法的構(gòu)建

1.1 利用模糊關(guān)系進(jìn)行聚類

模糊聚類算法是無監(jiān)督的聚類算法，其聚類結(jié)果是每個(gè)數(shù)據(jù)樣本點(diǎn)對(duì)聚類中心的隸屬度。模糊聚類算法由于可以利用數(shù)學(xué)方法來量化樣本間的模糊關(guān)系，能提高樣本分布特征描述的準(zhǔn)確性。模糊聚類算法直接由計(jì)算樣本的隸屬度來進(jìn)行聚類，隸屬度原則：設(shè)論域 中的M 個(gè)模糊子集w1,w2,...wM，且對(duì)于每一個(gè)wi 都有隸屬度函數(shù)μwi(X0)=max[μw1(X0)，μw2(X0)，...，μwM(X0)]

在實(shí)際的應(yīng)用中，被識(shí)別的對(duì)象往往不是論域中的一個(gè)確定的元素，而是中的一個(gè)字集。這時(shí)，所討論的對(duì)象不是一個(gè)元素對(duì)集合的隸屬程度，而是兩模糊子集間的貼近程度。

設(shè)WA，WB 是上的兩個(gè)模糊子集，則期間的貼近度定義為

分別為A 和B 的內(nèi)積和外積。

1.2 模糊減法聚類

普通的模糊聚類是一種局部搜索算法，如果初始值選擇不當(dāng)，它就會(huì)收斂到局部極小點(diǎn)上，所以本文選用模糊減法聚類。

模糊減法聚類將每個(gè)數(shù)據(jù)作為可能的聚類中心，并根據(jù)各個(gè)數(shù)據(jù)點(diǎn)周圍的數(shù)據(jù)點(diǎn)密度來計(jì)算這個(gè)點(diǎn)作為聚類中心的可能性。被選為聚類中心的數(shù)據(jù)點(diǎn)周圍具有最高的數(shù)據(jù)點(diǎn)密度，同時(shí)，這個(gè)數(shù)據(jù)點(diǎn)附近的數(shù)據(jù)點(diǎn)被排除作為聚類中心的可能性；在選出每一個(gè)聚類中心后，從剩余的可能作為聚類中心的數(shù)據(jù)點(diǎn)中，繼續(xù)采用類似的方法選擇下一個(gè)聚類中心。這個(gè)過程一直持續(xù)到所有剩余的數(shù)據(jù)點(diǎn)做為聚類中心的可能性低于某一閾值。具體算法如下：

步驟1：將樣本點(diǎn)集合X=｛x1,x2,x3,...,xn｝中每個(gè)數(shù)據(jù)作為可能的聚類中中心z1,z2,z3,...,zn。

步驟2：根據(jù)各個(gè)數(shù)據(jù)點(diǎn)周圍的數(shù)據(jù)點(diǎn)密度進(jìn)行計(jì)算，最高密度數(shù)據(jù)中心的點(diǎn){xk1,xk2,xk3,...,xkm}，確定為新的聚類中心{zk1,zk2,zk3,...,zkm}。這些新的聚類中心附近的數(shù)據(jù)點(diǎn)被排除作為聚類中心的可能性。

步驟3：從剩余的可能作為聚類中心的數(shù)據(jù)點(diǎn)中，重復(fù)步驟1 和步驟2，直到所有剩余的數(shù)據(jù)點(diǎn)做為聚類中心的可能性低于閾值d。

1.3 基于模糊減法聚類的時(shí)間序列分段線性表示方法的構(gòu)建

本文在文獻(xiàn)的啟發(fā)下，為達(dá)保留原時(shí)間序列的有效特征，并減少數(shù)據(jù)量目的，對(duì)時(shí)間序列進(jìn)行分段線性表示方法，本文采用模糊減法聚類從原始數(shù)據(jù)中提取重要的特征點(diǎn)，用這些特征點(diǎn)連接起來的直線表示原來的時(shí)間序列。

在利用模糊減法聚類對(duì)時(shí)間序列分段的過程中，閾值d的值越大，保留的關(guān)鍵點(diǎn)就越少，相鄰關(guān)鍵點(diǎn)之間的變化，反映的趨勢(shì)就越是宏觀趨勢(shì)；閾值d 的值越小，保留的關(guān)鍵點(diǎn)就越多，相鄰關(guān)鍵點(diǎn)之間的變化，反映的趨勢(shì)就越是微觀趨勢(shì)。

2 實(shí)驗(yàn)與結(jié)果分析

2.1 實(shí)驗(yàn)數(shù)據(jù)及實(shí)驗(yàn)環(huán)境

本文中的數(shù)據(jù)集選擇來自不同領(lǐng)域的時(shí)間序列數(shù)據(jù)集：隨機(jī)數(shù)數(shù)據(jù)，UCR_TS 中的worm 數(shù)據(jù)和UCR_TS 中的yoga 數(shù)據(jù)。實(shí)驗(yàn)環(huán)境為Windows7 64 位操作系統(tǒng)，處理器Intel(R)Core(TM)i5-3470CPU@3.2GHz，內(nèi)存（RAM）：4.00GB。MATLAB R2016a。

2.2 實(shí)驗(yàn)方法及結(jié)果

以長度相同的隨機(jī)數(shù)數(shù)據(jù)，UCR_TS 中的worm 數(shù)據(jù)和UCR_TS 的yoga 數(shù)據(jù)為數(shù)據(jù)集，分別進(jìn)行實(shí)驗(yàn)。

（1）在閾值d 為0.1 的條件下，對(duì)隨機(jī)數(shù)數(shù)據(jù)，UCR_TS 中的worm 數(shù)據(jù)和UCR_TS 的yoga 數(shù)據(jù)分別運(yùn)行模糊減法聚類程序，圖1，圖2 分別展示了隨機(jī)數(shù)數(shù)據(jù)，UCR_TS中的yoga 數(shù)據(jù)的運(yùn)行結(jié)果。

圖1：數(shù)據(jù)集為隨機(jī)數(shù)，d 為0.1

圖2：數(shù)據(jù)集為yoga 數(shù)據(jù)，d 為0.1

圖2 中的圓圈點(diǎn)，是運(yùn)行程序后得到的聚類中心點(diǎn)，也就是本文采用模糊減法聚類從原始數(shù)據(jù)中提取重要的特征點(diǎn)。按順序用直線連接各個(gè)特征點(diǎn)，可以得到對(duì)于原始數(shù)據(jù)的分段線性表示。在閾值d 為0.1 的條件下，對(duì)于本文中的、數(shù)據(jù)點(diǎn)為100 個(gè)的隨即數(shù)數(shù)據(jù)，得到了包括端點(diǎn)在內(nèi)的55 個(gè)關(guān)鍵點(diǎn)；相同條件下，數(shù)據(jù)點(diǎn)為100 個(gè)的UCR_TS 的yoga 數(shù)據(jù)，得到了包括端點(diǎn)在內(nèi)的22 個(gè)關(guān)鍵點(diǎn)；相同條件下，數(shù)據(jù)點(diǎn)為100 個(gè)的UCR_TS 的worm 數(shù)據(jù)，得到了包括端點(diǎn)在內(nèi)的20 個(gè)關(guān)鍵點(diǎn)。

（2）在閾值d 為0.2 的條件下，對(duì)隨機(jī)數(shù)數(shù)據(jù)，UCR_TS 中的worm 數(shù)據(jù)和UCR_TS 的yoga 數(shù)據(jù)分別運(yùn)行模糊減法聚類程序。

在閾值d 為0.2 的條件下，對(duì)于本文中的、數(shù)據(jù)點(diǎn)為100 個(gè)的隨即數(shù)數(shù)據(jù)，得到了包括端點(diǎn)在內(nèi)的24 個(gè)關(guān)鍵點(diǎn)；相同條件下，數(shù)據(jù)點(diǎn)為100 個(gè)的UCR_TS 的yoga 數(shù)據(jù)，得到了包括端點(diǎn)在內(nèi)的10 個(gè)關(guān)鍵點(diǎn)；相同條件下，數(shù)據(jù)點(diǎn)為100 個(gè)的UCR_TS 的worm 數(shù)據(jù)，得到了包括端點(diǎn)在內(nèi)的12個(gè)關(guān)鍵點(diǎn)。

（3）在閾值d 為0.3 的條件下，對(duì)隨機(jī)數(shù)數(shù)據(jù)，UCR_TS 中的worm 數(shù)據(jù)和UCR_TS 的yoga 數(shù)據(jù)分別運(yùn)行模糊減法聚類程序。

在閾值d 為0.3 的條件下，對(duì)于本文中的、數(shù)據(jù)點(diǎn)為100 個(gè)的隨即數(shù)數(shù)據(jù)，得到了包括端點(diǎn)在內(nèi)的15 個(gè)關(guān)鍵點(diǎn)；相同條件下，數(shù)據(jù)點(diǎn)為100 個(gè)的UCR_TS 的yoga 數(shù)據(jù)，得到了包括端點(diǎn)在內(nèi)的9 個(gè)關(guān)鍵點(diǎn)；相同條件下，數(shù)據(jù)點(diǎn)為100 個(gè)的UCR_TS 的worm 數(shù)據(jù)，得到了包括端點(diǎn)在內(nèi)的8個(gè)關(guān)鍵點(diǎn)。

（4）在閾值d 為0.1，0.2 和0.3 的條件下，以長度為10000 隨機(jī)數(shù)據(jù)為數(shù)據(jù)集，運(yùn)行本方法，進(jìn)行關(guān)鍵點(diǎn)的提取，驗(yàn)證本方法對(duì)時(shí)長時(shí)間序列的運(yùn)行效率。得到的程序運(yùn)行時(shí)間分別為2.768863 秒，2.660376 秒和2.602249 秒。

（5）在相同壓縮率下，與基于PAA 的時(shí)間序列分段線性表示進(jìn)行對(duì)比。基于PAA 的時(shí)間序列分段線性表示方法是Keogh 和Yi 等人分別提出的時(shí)間序列表示方法，用相同長度的窗口分割時(shí)間序列，每個(gè)被分割的時(shí)間序列用平均值來表示。在相同壓縮率下，對(duì)于本文所用到的數(shù)據(jù)集的擬合誤差如表1。

表1：數(shù)據(jù)集的擬合誤差

通過對(duì)比，可以發(fā)現(xiàn)，相同壓縮率下，本文提出的方法，都好于PAA 方法。

2.3 結(jié)果分析

通過實(shí)驗(yàn)結(jié)果數(shù)據(jù)對(duì)比分析，可以得出下面的結(jié)論，閾值d 越小，對(duì)時(shí)間序列運(yùn)行本方法后，得以的關(guān)鍵點(diǎn)就最多，對(duì)原時(shí)間序列的壓縮比數(shù)值就越大，對(duì)序列本身的微觀趨勢(shì)變化信息反映的就越多；閾值d 越大，對(duì)時(shí)間序列運(yùn)行本方法后，得以的關(guān)鍵點(diǎn)就最少，對(duì)原時(shí)間序列的壓縮比數(shù)值就越小，對(duì)序列本身的宏觀趨勢(shì)變化信息反映的就越多；通過閾值d 的設(shè)定，可以反映不同程度的趨勢(shì)變化信息，即，可以多尺度地對(duì)原時(shí)間序列進(jìn)行分段表示。另外，對(duì)于長時(shí)間序列，本方法也具有較高的運(yùn)行效率。

3 結(jié)束語

本文采用模糊減法聚類從原始數(shù)據(jù)中提取重要的特征點(diǎn)，利用得到的特征點(diǎn)對(duì)原時(shí)間序列進(jìn)行分段線性表示，即，基于模糊減法聚類的時(shí)間序列分段線性表示方法，該方法通過對(duì)閾值設(shè)定，可以提取出不同數(shù)量的特征點(diǎn)，進(jìn)行完成對(duì)原時(shí)間序列的不同尺度的劃分，最后，達(dá)到不能尺度的分段線性表示。在以多個(gè)不同的時(shí)間序列數(shù)據(jù)為數(shù)據(jù)集的情況下，驗(yàn)證了本方法的有效性。另外，本文還對(duì)長時(shí)間序列數(shù)據(jù)，在不同閾值的情況下，進(jìn)行試驗(yàn)，驗(yàn)證的本方法具有較高的運(yùn)行效率。