時(shí)間序列相關(guān)概念及經(jīng)典聚類算法概述1900字

時(shí)間序列相關(guān)概念及經(jīng)典聚類算法概述綜述1.1時(shí)間序列相關(guān)概念時(shí)間序列(timeseries)是按照時(shí)間順序排列的一組隨機(jī)變量REF_Ref103803264\r\h[4]。時(shí)間序列與隨機(jī)過程緊密相關(guān)，在時(shí)間序列的理論研究過程中經(jīng)常將其理解為一個(gè)隨機(jī)過程。隨機(jī)過程(stochasticprocess)是一組有序的隨機(jī)變量，可以記為{y(t),t∈T}。隨機(jī)過程一般是定義在連續(xù)集合上的，而定義在離散集合上的隨機(jī)過程則通常稱為時(shí)間序列。離散的時(shí)間集合T可以表示為T={……,-2,-1,0,1,2,……}，此時(shí)y(t)是離散時(shí)間t的隨機(jī)函數(shù)，時(shí)間序列通常表示為{y,t=……,-2,-1,0,1,2,……}。時(shí)間序列在特定時(shí)間段上的觀測(cè)樣本可以是隨機(jī)過程的一次實(shí)現(xiàn)，通常稱為樣本序列，記為{yo,y1,y2,…,yT}。理論上說，時(shí)間序列可以有無限個(gè)觀測(cè)時(shí)間點(diǎn),然而從實(shí)際可獲得的樣本數(shù)據(jù)來看，我們所得到的樣本序列都是有限的。更加關(guān)鍵的是，由于時(shí)間的不可重復(fù)性，時(shí)間序列通常僅有一次實(shí)現(xiàn)，即只有一個(gè)樣本序列。因此時(shí)間序列的經(jīng)驗(yàn)研究的一個(gè)顯著特點(diǎn)是，只能在唯一可觀測(cè)到的樣本序列的基礎(chǔ)上來推斷時(shí)間序列的總體特性。時(shí)間序列聚類：給定時(shí)間序列數(shù)據(jù)集D=F1,F2,……,Fn,通過無監(jiān)督的方法將D劃分為C=C1,C2,……,Ck。在這種情況下，其根據(jù)所確定的相似性度量將同質(zhì)的序列元素組合在一起的過程稱之為時(shí)間序列聚類。Ci為一個(gè)聚類，其中 D=i=1可劃分為三類：1)整個(gè)序列聚類：一系列離散的單個(gè)時(shí)間序列的聚類。2)子序列聚類：通過滑動(dòng)窗口在一個(gè)時(shí)間序列中提取的一系列子序列上的聚類3)時(shí)間點(diǎn)聚類：基于時(shí)間點(diǎn)的時(shí)間接近度和對(duì)應(yīng)值的相似性組合的聚類，類似于時(shí)間序列分割，但不需要將所有點(diǎn)都完美分割，部分可視為噪聲。1.2時(shí)間序列特征提取特征提取是對(duì)某一模式的組測(cè)量值進(jìn)行變換，以突出該模式具有代表性特征的一種方法。通過影像分析和變換，以提取所需特征的方法。至今為止特征沒有萬能和精確的定義。特征的精確定義往往由問題或者應(yīng)用類型決定。特征是一個(gè)數(shù)字圖像中“有趣”的部分，它是許多計(jì)算機(jī)圖像分析算法的起點(diǎn)。因此一個(gè)算法是否成功往往由它使用和定義的特征決定。因此特征提取最重要的一個(gè)特性是“可重復(fù)性”：同一場景的不同圖像所提取的特征應(yīng)該是相同的。特征提取與降維有關(guān)，特征的好壞對(duì)泛化能力有至關(guān)重要的影響REF_Ref103803295\r\h[5]。時(shí)間序列特征表示是將原時(shí)間序列轉(zhuǎn)換為另一論域中的數(shù)據(jù)并且起到數(shù)據(jù)降維的作用;同時(shí)，使得在低維空間下的數(shù)據(jù)能盡可能地反映原時(shí)間序列信息。目前已有不少相關(guān)的時(shí)間序列特征表示方法，如分段線性表示、分段聚合近似、符號(hào)化表示方法、基于域變換的表示方法、奇異值分解和基于模型的表示方法等，它們之間存在一定的區(qū)別和聯(lián)系REF_neb7BD59B7E_086A_428D_8C59_753CB88F8DBA\r\h[6]，如圖1.1.所示。圖1.2時(shí)間序列特征表示方法歸類1.3聚類算法概述經(jīng)典的聚類算法可以分為REF_Ref103803352\r\h[7]REF_Ref103803375\r\h[8]1.劃分法（PartitioningMethods）：它用一個(gè)聚類的中心來代表一個(gè)簇，即在迭代過程中選擇的聚點(diǎn)不一定是聚類中的一個(gè)點(diǎn)，該算法只能處理數(shù)值型數(shù)據(jù)。例如k-means算法。1.層次法（HierarchicalMethods）：通過某種相似性測(cè)度計(jì)算節(jié)點(diǎn)之間的相似性，并按相似度由高到低排序，逐步重新連接個(gè)節(jié)點(diǎn)。該方法的優(yōu)點(diǎn)是可隨時(shí)停止劃分，主要步驟如下：（1）移除網(wǎng)絡(luò)中的所有邊，得到有n個(gè)孤立節(jié)點(diǎn)的初始狀態(tài)；（2)計(jì)算網(wǎng)絡(luò)中每對(duì)節(jié)點(diǎn)的相似度；（3）根據(jù)相似度從強(qiáng)到弱連接相應(yīng)節(jié)點(diǎn)對(duì)，形成樹狀圖；(4）根據(jù)實(shí)際需求橫切樹狀圖，獲得社區(qū)結(jié)構(gòu)。例如：BIRCH算法，CURE(ClusteringUsingRepresentatives)算法等等3.基于密度的方法（density-basedmethods）：把臨近的密度高的區(qū)域練成一片形成簇。該方法可以找到各種大小各種形狀的簇,并且具有一定的抗噪音特性。在日常應(yīng)用中,可以用不同的索引方法或用基于網(wǎng)格的方法來加速密度估計(jì),提高聚類的速度。例如DBSCAN算法，OPTICS算法4.基于網(wǎng)格的方法(grid-basedmethods)：采用空間驅(qū)動(dòng)的方法,把嵌入空間劃分成獨(dú)立于輸入對(duì)象分布的單元?；诰W(wǎng)格的聚類方法使用一種多分辨率的網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)。它將對(duì)象空間量化成有限數(shù)目的單元,這些網(wǎng)格形成了網(wǎng)格結(jié)構(gòu),所有的聚類結(jié)構(gòu)都在該結(jié)構(gòu)上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是處理速度快,其處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)象數(shù),而僅依賴于量化空間中的每一維的單元數(shù)。5.基于模型的方法（Model-BasedMethods）：采用基于概率的方法,算法假設(shè)樣例數(shù)據(jù)分布服從某個(gè)未知的概率分布,并試圖從數(shù)據(jù)找出這個(gè)分布。聚類分析使得同類簇的樣本盡可能相似，不同類簇的樣本盡可能不相似。聚類評(píng)價(jià)指標(biāo)是度量聚類結(jié)果有效性的客觀指標(biāo)，也是衡量聚類算法性能的客觀依據(jù)REF_Ref103803397\r\h[9]。一般分為外部指標(biāo)和內(nèi)部指標(biāo)。由于本文采用內(nèi)部指標(biāo)中的CH(Calinski-Harabasz)指標(biāo)，因此在這里著重講述CH指標(biāo)CH指標(biāo)是Calinski和Harabasz提出的最佳聚類數(shù)的指標(biāo)。此指標(biāo)基于樣