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

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