一種加入類間因素的曲線聚類算法

許騰騰，王瑞，黃恒君

（蘭州財(cái)經(jīng)大學(xué) 統(tǒng)計(jì)學(xué)院，甘肅 蘭州 730020）

隨著信息技術(shù)的不斷發(fā)展，數(shù)據(jù)獲取越來越便捷，數(shù)據(jù)采集的密集化程度也越來越高。隨之出現(xiàn)了一種具有函數(shù)特征的數(shù)據(jù)類型。如心理學(xué)研究中的腦電信號(hào)數(shù)據(jù)、生物技術(shù)中的基因微序列數(shù)據(jù)、化學(xué)計(jì)量中的光譜分析數(shù)據(jù)、經(jīng)濟(jì)研究中的股票分時(shí)成交價(jià)數(shù)據(jù)、環(huán)境監(jiān)測(cè)中的污染物濃度數(shù)據(jù)等，均隨著時(shí)間變化而表現(xiàn)出明顯的曲線特征。當(dāng)前文獻(xiàn)中將這種數(shù)據(jù)類型稱為函數(shù)型數(shù)據(jù)(functional data)[1]。

一般而言，函數(shù)型數(shù)據(jù)的曲線形式無法直接獲取，通常僅能夠觀測(cè)到其離散樣本點(diǎn)，并針對(duì)離散數(shù)據(jù)進(jìn)行傳統(tǒng)多元統(tǒng)計(jì)分析。當(dāng)然，這種做法由于未能考慮到數(shù)據(jù)的函數(shù)特性(如連續(xù)、可導(dǎo)等)，同時(shí)需要處理高維問題，往往不能取得很好的分析效果[2]。為此，針對(duì)數(shù)據(jù)的曲線特征，人們提出了各種分析方法[3-4]，包括函數(shù)型主成分分析、函數(shù)型線性模型、函數(shù)型聚類分析等，將有限維的多元分析推廣到無限維的函數(shù)型數(shù)據(jù)上來。

聚類分析是數(shù)據(jù)探索、數(shù)據(jù)壓縮和展現(xiàn)的重要工具，本文討論函數(shù)型數(shù)據(jù)的聚類算法。目前，函數(shù)型數(shù)據(jù)聚類分析方法大致分為兩類[3]：一是原始數(shù)據(jù)法，該類方法直接針對(duì)離散樣本點(diǎn)進(jìn)行聚類，屬于高維數(shù)據(jù)分析方法，文獻(xiàn)[5]對(duì)這種做法進(jìn)行了綜述。二是投影方法，即以有限維的基底函數(shù)逼近曲線，將無限維的問題轉(zhuǎn)化為有限維問題展開分析。依據(jù)對(duì)基底函數(shù)所對(duì)應(yīng)的系數(shù)處理方式不同，又可分為濾波法和自適應(yīng)法。濾波法將基底函數(shù)所對(duì)應(yīng)的系數(shù)設(shè)定為固定參數(shù)，分曲線擬合和聚類分析兩步展開：首先以有限維基底擬合曲線，對(duì)估計(jì)的參數(shù)執(zhí)行傳統(tǒng)聚類算法。包括利用自組織映射(SOM)算法進(jìn)行聚類和擬合函數(shù)型數(shù)據(jù)[6]；利用兩階段隨機(jī)過程分別完成數(shù)據(jù)降維和聚類[7]等。根據(jù)基底函數(shù)選擇利用B-樣條基底函數(shù)擬合數(shù)據(jù)并根據(jù)傳統(tǒng)聚類方法分析[8-9]，利用正交基函數(shù)進(jìn)行聚類分析[10]等。自適應(yīng)法是將基底函數(shù)所對(duì)應(yīng)的系數(shù)作為隨機(jī)變量處理，將曲線擬合和聚類分析納入一個(gè)目標(biāo)函數(shù)，采用類似EM的算法，同時(shí)進(jìn)行優(yōu)化。如利用機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)模型SVR分析時(shí)空數(shù)據(jù)[11]、利用STM算法對(duì)時(shí)空數(shù)據(jù)進(jìn)行聚類[12]以及時(shí)間序列數(shù)據(jù)[13]、經(jīng)維度數(shù)據(jù)[14]等的聚類方法；基于K-medoids項(xiàng)目聚類的協(xié)同過濾推薦算法[15]；基于多元函數(shù)型主成分分析(FPCA)方法進(jìn)行的改進(jìn)混合模型同時(shí)進(jìn)行曲線擬合與聚類分析[16]。在隨機(jī)過程中利用K-L散度度量，采用類似于EM算法進(jìn)行聚類的算法[17]等。

盡管有眾多其他的算法[6,18]，目前的函數(shù)型聚類分析僅考慮了類內(nèi)部的差異，而忽視了類間的差異性。對(duì)傳統(tǒng)離散數(shù)據(jù)的聚類研究表明[19]，同時(shí)考慮類內(nèi)與類間差異有助于提升聚類效果。

受此啟發(fā)，本文提出一種加入類間因素的曲線聚類算法。本文的做法屬于濾波法，包括B-樣條基底擬合曲線、曲線距離確定、曲線聚類目標(biāo)函數(shù)設(shè)定，以及加入類間因素的曲線聚類算法等。

1 加入類間因素的曲線聚類

根據(jù)前面的描述，本文討論的曲線聚類分析模型構(gòu)建主要包含3個(gè)方面：1)由觀測(cè)離散數(shù)據(jù)生成函數(shù)型數(shù)據(jù)，這里采用B-樣條基底表述的方法；2)構(gòu)造曲線之間的“距離”的表述，并通過用B-樣條基底系數(shù)，將曲線距離轉(zhuǎn)化為傳統(tǒng)歐氏距離；3)以所構(gòu)造的距離作為親疏程度度量，并構(gòu)建同時(shí)考慮類內(nèi)差異和類間差異的目標(biāo)函數(shù)，完成曲線聚類任務(wù)。

1.1 曲線生成

假 定 數(shù) 據(jù) Yi=[yi1yi2···yim]T(i=1,2,···,n)由 如下模型生成：

式中： Xi(t)表 示待估計(jì)曲線，ε表示服從零均值同方差的獨(dú)立同分布隨機(jī)變量。進(jìn)一步假定 Xi(t)可由一組基底 {φi1(t),φi2(t),···}表示，則有

稱這種做法為基底函數(shù)法，它是一種將離散數(shù)據(jù)轉(zhuǎn)化為曲線的常用平滑技術(shù)[3]。對(duì)待估計(jì)曲線 Xi(t)采取截?cái)嗵幚恚玫饺缡?3)的形式：

從而將無限維問題轉(zhuǎn)化為有限維估計(jì)方式。進(jìn)一步假定[9]：

1) 對(duì)不同曲線 Xi(t)(i=1,2,···,n)采用一組相同的基底表述；

2) 基底函數(shù)設(shè)定為等距節(jié)點(diǎn)B-樣條基底。有

式中： L =K+M ， Bk,M(t)表 示第 k個(gè)內(nèi)部節(jié)點(diǎn)數(shù)量為K 的 M 階 B-樣條基底函數(shù)。 BM(t)表示M階B-樣條基底函數(shù)。對(duì)于參數(shù) αi，我們利用最小二乘法進(jìn)行估計(jì)。

1.2 曲線距離

假定曲線 Xi(t)為 L2空 間的元素。則根據(jù) L2范數(shù)定義，有曲線 Xi(t)和 Xj(t)的距離為

其中 ‖· ‖表示L2范數(shù)，由假定1)及式(4)知

結(jié)合式(6)，式(5)可轉(zhuǎn)化為

式中

其中，K 為 L ×L 實(shí)對(duì)稱矩陣， K中的每一個(gè)元素?Bi,Bj表示 L2空間的內(nèi)積。但是類似于d2(i,j)=[αi-αj]T[αi-αj]這種形式的距離公式并不適用于非正交基底函數(shù)[9]，為將曲線距離用傳統(tǒng)距離公式表示，對(duì) K 作楚列斯基(Cholesky)分解得 K =LLT，其中 L 為上三角矩陣，并令 bi=LTαi，式(7)可表示為

需要說明的是，式(8)完成了從曲線距離到一般距離的轉(zhuǎn)變，構(gòu)成了將曲線聚類轉(zhuǎn)化為傳統(tǒng)多元聚類問題的基礎(chǔ)。利用式(8)，運(yùn)用傳統(tǒng)聚類算法對(duì) bi進(jìn) 行聚類，得到 P 類 ，記為 i ∈ Gp(p ∈ 1,2,···,P)。

由 bi=LTαi得 到 B =AL ， 其中 A =[α1α2···αnp]T，B=[b1b2···bn]T。np表示第 Gp類中的曲線數(shù)量，p令 Xˉ (t0)表示隨機(jī)選取的一條曲線作為初始類中心，ˉ(Gp)(t)表示第 Gp類中的類中心。則有Xˉ(Gp)(t)=np-11TBL-1BM(t)。

1.3 改進(jìn)的曲線聚類算法

聚類分析的目的是將同類型數(shù)據(jù)進(jìn)行歸類，同時(shí)對(duì)不同類型的數(shù)據(jù)進(jìn)行區(qū)分。文獻(xiàn)[19]針對(duì)傳統(tǒng)離散數(shù)據(jù)提出的K-means聚類擴(kuò)展方法兼顧了類內(nèi)、類間差異。具體來講，通過對(duì)數(shù)據(jù)集引入全局中心點(diǎn)實(shí)現(xiàn)類內(nèi)差異最小化的同時(shí)類中心與全局中心點(diǎn)距離最大化。相比于K-means算法，這種做法提高了聚類效果[19]。

受此啟發(fā)，本文將K-means聚類分析擴(kuò)展到函數(shù)型聚類分析上。本文的曲線聚類目標(biāo)函數(shù)為

式中： Φ 表示待估參數(shù)矩陣(A或B)，U表示由uik構(gòu)成的矩陣，其中 uik∈{0,1}，uik=1， Xi(t)表示曲線，(t0)表示隨機(jī)選取的一條曲線作為初始類中心，結(jié)合式(4)的曲線基底表述，得到目標(biāo)函數(shù)：

根據(jù)前面關(guān)于曲線距離的描述將式(7)～(8)代入式(10)得到

式中： b?=LTα?， b0=LTα0， α?表示第k類類中心對(duì)應(yīng)的參數(shù)， α0表示初始類中心曲線的參數(shù)。

目標(biāo)函數(shù)確定后，式(11)中含有兩個(gè)未知參數(shù) α 及 U 。通過固定一項(xiàng)求解另一項(xiàng)的步驟來求解式 (11)，即()

2) 固定U=U，求解函數(shù)FΦ,U。

針對(duì)1)，為使目標(biāo)函數(shù)式(11)達(dá)到最小，當(dāng)目標(biāo)函數(shù)分子中曲線與對(duì)應(yīng)類中心曲線距離小時(shí)uik=1，否則為 0，即

針對(duì)2)，假設(shè) b?已知，對(duì)目標(biāo)函數(shù)式(11)關(guān)于b?求偏導(dǎo)數(shù)：

得出

進(jìn)一步化簡(jiǎn)得到b?

即

在進(jìn)行計(jì)算機(jī)編程時(shí)可以不斷對(duì)步驟1)、2)進(jìn)行迭代，直至找出最優(yōu) U 和 Φ 。算法流程如下：

Input：X={X1,X2,···Xn},k

Initialize： Randomly choose an initialb0=b1,b2,···,bk

Repeat

Fixed Φ, use eq. (12) to solveU

Fixed U, use eq. (13) to solveΦ

Until convergence.

進(jìn)一步，由 b?=LTα?， 求解出 b?可 得到參數(shù) α?，并根據(jù)式(4)還原出類中心曲線。

2 算法效果模擬驗(yàn)證與分析

為驗(yàn)證本文曲線聚類算法的效果，利用模擬數(shù)據(jù)與文獻(xiàn)[9]中曲線聚類方法進(jìn)行比較。模擬數(shù)據(jù)由兩組高斯分布生成兩類曲線構(gòu)成。模擬過程中兩類高斯分布均值取0.5和1，方差取0.7和1。在確定類別的前提下比較本文算法與文獻(xiàn)[9]曲線聚類算法的聚類效果。聚類效果評(píng)價(jià)指標(biāo)采用蘭德指數(shù)(Rand index)評(píng)價(jià)算法的性能[20]。同時(shí)分析兩組高斯分布的參數(shù)(均值和方差)對(duì)聚類的影響。分析結(jié)果顯示：同均值異方差情況下兩種曲線聚類方法聚類結(jié)果均存在一定的誤判，異均值異方差情況下二者聚類也存在誤判，異均值同方差情況下二者聚類未出現(xiàn)誤判。以下針對(duì)這一現(xiàn)象做出分析。

該部分采用R軟件進(jìn)行數(shù)據(jù)模擬分析，每組包含 n條 數(shù)據(jù)，每條數(shù)據(jù)含有 m個(gè)數(shù)據(jù)點(diǎn)，則模擬數(shù)據(jù)中每組高斯分布要生成 m ×n個(gè)隨機(jī)數(shù)。為保證擬合結(jié)果的光滑，內(nèi)部節(jié)點(diǎn)采用等距節(jié)點(diǎn)設(shè)置方式。針對(duì)高斯分布中的均值和方差分別在同均值異方差、同方差異均值、異均值異方差情況下分析本文的曲線聚類方法與已有曲線聚類方法的效果，并對(duì)相應(yīng)結(jié)果進(jìn)行分析。為便于表述，兩類模擬數(shù)據(jù)分別記為1類和2類，生成的區(qū)間長(zhǎng)度設(shè)置為12。為便于展示，本文以圖1異均值異方差條件下兩種聚類方法比較為例。

圖1 模擬數(shù)據(jù)曲線聚類對(duì)比Fig.1 Comparison with simulated data of curve's clustering

圖1 表明：兩組高斯分布參數(shù)不同條件下，本文方法與文獻(xiàn)[9]相比，圖1(b)中1類曲線分布密集程度大于圖1(a)中1類曲線。為避免模擬次數(shù)少或其他原因?qū)垲愋Ч挠绊懀瑢?duì)3種類型的數(shù)據(jù)分別模擬一萬次，比較兩種方法的平均錯(cuò)判率，定義錯(cuò)判率=abs(1類個(gè)數(shù)-n)/n，模擬驗(yàn)證中m=12，n=50，錯(cuò)判率下降比例=文獻(xiàn)[9]方法錯(cuò)判率-本文方法錯(cuò)判率。結(jié)果見表1。

表1、2表明：無論本文的曲線聚類還是文獻(xiàn)[9]中的曲線聚類方法，類中心的變化與高斯分布中均值有關(guān)，而聚類效果好壞與高斯分布的方差有關(guān)。對(duì)比表1、2中的同均值異方差和異均值異方差的錯(cuò)判率及蘭德指數(shù)可以得出：當(dāng)兩類高斯分布均值相同，方差不同時(shí)，兩種方法對(duì)應(yīng)的蘭德指數(shù)相比于其他類型數(shù)據(jù)偏低。同時(shí)方差因素對(duì)聚類效果也會(huì)產(chǎn)生影響。綜合比較表1、2中的3類數(shù)據(jù)錯(cuò)判率及蘭德指數(shù)，可以得到：對(duì)于曲線聚類分析，聚類效果會(huì)同時(shí)受數(shù)據(jù)總體均值和方差的影響，對(duì)比分析表1、2均值相同方差不同的情形，可以得到：均值對(duì)聚類的影響程度要大于方差，同時(shí)表1、2對(duì)兩種方法錯(cuò)判率對(duì)比結(jié)果顯本文的方法能夠降低聚類錯(cuò)判率從而提高聚類效果。

表1 3種類型模擬數(shù)據(jù)平均錯(cuò)判率Table1 Average error rate of three types' simulated data

表2 3種類型模擬數(shù)據(jù)蘭德指數(shù)Table2 Rand index of three types' simulated data

3 NO2小時(shí)濃度曲線聚類效果分析

空氣質(zhì)量，不僅關(guān)乎人類生存質(zhì)量，同時(shí)也是衡量可持續(xù)發(fā)展能力和宜居程度的重要指標(biāo)。NO2是一種重要的機(jī)動(dòng)車尾氣污染物，其污染程度涉及人們生活出行的健康。近年來，空氣質(zhì)量問題引起人們廣泛的關(guān)注，大氣污染監(jiān)測(cè)數(shù)據(jù)成為人們了解空氣質(zhì)量的客觀途徑，也構(gòu)成空氣質(zhì)量統(tǒng)計(jì)分析的數(shù)據(jù)基礎(chǔ)。

作為示例，通過實(shí)時(shí)網(wǎng)絡(luò)爬蟲手段[21]，采集蘭州市鐵路設(shè)計(jì)院空氣質(zhì)量監(jiān)測(cè)站(交通污染控制點(diǎn))的NO2小時(shí)濃度數(shù)據(jù)，采用本文的曲線聚類算法展開大氣污染等級(jí)聚類分析，并與傳統(tǒng)曲線聚類結(jié)果進(jìn)行比較。我們分析的樣本期為2013年6月1日—10月14日。

根據(jù)前面的方法，采用B-樣條基底函數(shù)進(jìn)行曲線聚類分析。為保證擬合結(jié)果光滑，兩種聚類方法樣條基底階數(shù)M均設(shè)置為5，節(jié)點(diǎn)采用等距節(jié)點(diǎn)設(shè)置為11(文中采用廣義交叉驗(yàn)證準(zhǔn)則進(jìn)行節(jié)點(diǎn)數(shù)量選擇)?？紤]相同類中心下，與文獻(xiàn)[9]曲線聚類進(jìn)行聚類效果對(duì)比，如圖2所示。

圖2表明，K=5時(shí)類中心聚類效果優(yōu)于K=4，即隨著類中心個(gè)數(shù)的增加，兩種方法的聚類效果均有所提升，說明類中心個(gè)數(shù)的確定在曲線聚類中起到關(guān)鍵作用。但需要指出的是，本文方法的類中心分布曲線更為平滑，類間的類中心曲線分布更為分散，進(jìn)一步說明本文提出的方法聚類效果優(yōu)于已有聚類方法。此外，考慮到實(shí)際應(yīng)用，可將圖2中的不同類別曲線看作空氣質(zhì)量污染物等級(jí)劃分[20]。對(duì)比圖 2(a)、(c)與圖 2(b)、(d)可以發(fā)現(xiàn)，在空氣質(zhì)量實(shí)時(shí)監(jiān)測(cè)過程中，圖2(a)、(c)出現(xiàn)不同等級(jí)交叉情況，這對(duì)空氣質(zhì)量等級(jí)劃分及應(yīng)對(duì)會(huì)造成影響[22]。圖2(b)、(d)在進(jìn)行空氣質(zhì)量分析過程中能夠較好的對(duì)空氣質(zhì)量進(jìn)行聚類。另外，相比于針對(duì)離散數(shù)據(jù)的傳統(tǒng)K-means聚類分析[23]，本文方法能夠?qū)崟r(shí)檢測(cè)NO2小時(shí)濃度變化趨勢(shì)，并依據(jù)該變化趨勢(shì)對(duì)污染物進(jìn)行等級(jí)劃分。

為便于展示，本文以K=5的曲線聚類結(jié)果為例，結(jié)果見圖3。圖3表明，相比于已有曲線聚類算法，利用本文曲線聚類算法類內(nèi)曲線分布集中，類間差異化明顯。這與圖2中兩種曲線聚類算法類中心比較結(jié)果相一致。說明本文方法具有較好的類間區(qū)分度。

為進(jìn)一步驗(yàn)證本文曲線聚類的聚類效果，對(duì)兩種方法的分類精確度采用公式：類間差異/(類內(nèi)差異+類間差異)進(jìn)行對(duì)比，見圖4。圖4表明，隨著類中心個(gè)數(shù)的增加，兩種曲線聚類算法聚類效果均有所提高。本文曲線聚類的聚類效果要好于文獻(xiàn)[9]的方法。通過與文獻(xiàn)[9]方法進(jìn)行比較，本文方法在4類的聚類效果低于3類聚類效果，隨著類中心個(gè)數(shù)大于4類，聚類效果才逐步隨著類中心個(gè)數(shù)增加聚類效果不斷提升。說明本文方法存在一定的不穩(wěn)定性。

圖2 曲線聚類類中心對(duì)比Fig.2 Comparison with curve cluster's center generated by different algorithms

圖3 NO2小時(shí)濃度數(shù)據(jù)曲線聚類對(duì)比Fig.3 Comparison with curve clustering of NO2 concentration

圖4 聚類效果對(duì)比結(jié)果Fig.4 Comparison with clustering effects

4 結(jié)束語

本文基于已有曲線聚類方法，針對(duì)聚類效果不明顯的問題，提出加入類間因素的擴(kuò)展曲線聚類算法。加入類間因素能夠同時(shí)保證兩類數(shù)據(jù)類內(nèi)差異較小和類間差異較大。模擬數(shù)據(jù)及實(shí)例應(yīng)用表明，本文的曲線聚類算法有助于提高聚類效果。

需要說明的是，本文的目的是將同時(shí)考慮類內(nèi)和類間差異的做法引入曲線聚類算法。但我們的做法屬于兩步法，即首先擬合曲線，然后進(jìn)行聚類。這種做法很難達(dá)到兩部分的統(tǒng)一優(yōu)化[24]。為此，后續(xù)的工作是，在同時(shí)考慮類內(nèi)和類間差異的情況下，進(jìn)行自適應(yīng)算法研究，即將曲線擬合和聚類分析納入一個(gè)目標(biāo)函數(shù)，同時(shí)進(jìn)行優(yōu)化。