時(shí)間序列挖掘●聚類山西財(cái)經(jīng)大學(xué)信息管理學(xué)院常新功第六章目錄聚類的概念聚類算法的評價(jià)標(biāo)準(zhǔn)時(shí)間序列聚類概述k-mediods時(shí)間序列聚類基于LB_Hust距離的時(shí)間序列聚類基于SAX表示的聚類聚類的概念聚類（Clustering）是數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)重要分支。所謂聚類，是指將物理或抽象對象的集合分組成為由類似的對象組成的多個(gè)類的過程。聚類是依據(jù)事物的某些屬性將其聚集成類，使類間相似性盡量小，類內(nèi)相似性盡量大。，的深圳舉辦的新一代信息技術(shù)產(chǎn)業(yè)發(fā)展高峰論壇上，中國工程院院士李德毅在發(fā)言中指出，盡管目前對于大數(shù)據(jù)的認(rèn)知存在挑戰(zhàn)，但聚類將會(huì)成為大數(shù)據(jù)認(rèn)知的突破口。通過大數(shù)據(jù)聚類即時(shí)發(fā)現(xiàn)價(jià)值，要充分認(rèn)識大數(shù)據(jù)中的不確定性和價(jià)值的隱蔽性。聚類算法的評價(jià)標(biāo)準(zhǔn)1)可伸縮性：可伸縮性考察聚類算法對于目標(biāo)對象集合的規(guī)模以及目標(biāo)集合潛在的模式數(shù)量的適應(yīng)性。2)處理不同類型屬性的能力：除了通常處理的數(shù)值型數(shù)據(jù)，應(yīng)用當(dāng)中可能要求聚類其它類型的數(shù)據(jù)，如：二元類型，分類/標(biāo)稱類型，序數(shù)型，時(shí)間序列、圖數(shù)據(jù)或者不同數(shù)據(jù)類型的混合。3)發(fā)現(xiàn)任意形狀的聚類：許多聚類算法基于歐幾里德距離或者曼哈頓距離度量來決定聚類?；谶@種距離度量的算法趨向于發(fā)現(xiàn)具有相近尺度和密度的球狀簇。但是一個(gè)簇可能是任意形狀的，提出能發(fā)現(xiàn)任意形狀簇的算法是很重要的。4)交互可視化：高維數(shù)據(jù)和復(fù)雜對象常常使可視化變得困難，而交互性則使算法與人結(jié)合有利于提高聚類的質(zhì)量。聚類算法的評價(jià)標(biāo)準(zhǔn)5)最小化用于決定輸入?yún)?shù)的領(lǐng)域知識和數(shù)據(jù)記錄敏感性：一方面要求降低算法對輸入?yún)?shù)的敏感程度，另一方面要求輸入記錄順序?qū)λ惴ǖ慕Y(jié)果影響小。要求用戶輸入?yún)?shù)不僅會(huì)加重用戶的負(fù)擔(dān)，也使得聚類的質(zhì)量難以控制。6)處理噪聲數(shù)據(jù)的能力：絕大多數(shù)現(xiàn)實(shí)世界中的數(shù)據(jù)庫都包含了孤立點(diǎn)，空缺，未知或者錯(cuò)誤的數(shù)據(jù)。一些聚類算法對于這樣的數(shù)據(jù)敏感，導(dǎo)致聚類質(zhì)量不高。7)高維性：許多聚類算法只擅長處理低維數(shù)據(jù)。在高維空間中聚類數(shù)據(jù)對象是一個(gè)挑戰(zhàn)，特別是在數(shù)據(jù)有可能非常稀疏和偏斜時(shí)。8)可解釋性和可用性：知識發(fā)現(xiàn)過程中，聚類結(jié)果總是需要表現(xiàn)為一定的知識，這就要求聚類結(jié)果可解釋，易理解。時(shí)間序列聚類概述時(shí)間序列聚類是時(shí)間序列數(shù)據(jù)挖掘的一個(gè)非?；A(chǔ)且非?；钴S的研究方向，被廣泛應(yīng)用于包括模式識別、數(shù)據(jù)分析、圖像處理、市場分析等各個(gè)領(lǐng)域：零售數(shù)據(jù)的季節(jié)模式聚類、國家能源消耗聚類分析、心電圖ECG信號聚類分析、股票序列的模式發(fā)現(xiàn)以及個(gè)人收入數(shù)據(jù)的聚類等等(ValkandPinheiro,2012,Rodriguesetal.,2008,CostaSantosetal.,2006,Berkhin,2006,WarrenLiao，2005,BagnallandJanacek,2005)。國內(nèi)外許多研究者提出了很多時(shí)間序列聚類方法，這些方法大致可以分為三種：基于原始序列、基于特征數(shù)據(jù)和基于模型參數(shù)(WarrenLiao,2005)?；谠夹蛄袛?shù)據(jù)的時(shí)間序列聚類直接運(yùn)行在原始時(shí)間序列上的聚類稱為基于原始數(shù)據(jù)的聚類(Zhangetal.,2011,Rodriguesetal.,2008,WarrenLiao,2005)。但在實(shí)踐中，由于時(shí)間序列的高維特點(diǎn)，會(huì)導(dǎo)致大部分的聚類方法失效，具體表現(xiàn)為：(1)時(shí)間序列被看成高維空間中的一個(gè)點(diǎn)，所以數(shù)據(jù)分布會(huì)呈現(xiàn)稀疏性，從而導(dǎo)致歐氏距離不能正確測度對象間的相似程度(Wangetal.,2005,Domeniconietal.,2004)；(2)多數(shù)算法的性能受參數(shù)設(shè)置的影響，在缺乏背景知識時(shí)，用戶可以根據(jù)反饋的算法結(jié)果精調(diào)參數(shù)，但高維數(shù)據(jù)造成聚類結(jié)果無法可視化，使得用戶很難判斷聚類結(jié)果的質(zhì)量，所以很難合理設(shè)置參數(shù)（Jain,2010,Chen,2007,Linetal.,2004，DingandHe,2004)?；谔卣鲾?shù)據(jù)的時(shí)間序列聚類基于特征的表示方法是把原始時(shí)間序列轉(zhuǎn)換到一個(gè)低維的特征空間，然后用傳統(tǒng)的聚類方法對特征向量進(jìn)行聚類(Yangetal.,2009,Xiaozheetal.,2007,Keoghetal.,2007,Chen,2007,Zhangetal.,2006,Wangetal.,2006，CostaSantosetal.,2006，Wangetal.,2005，BagnallandJanacek,2005，Domeniconietal.,2004)。由于基于特征的聚類方法中提取的特征來自序列本身，且具有特定的含義，所以該聚類方法不僅實(shí)現(xiàn)對序列的降維，又使得聚類結(jié)果具有可解釋性。這里，常用的傳統(tǒng)的聚類算法有如下幾種：劃分聚類、層次聚類和密度聚類等等(Jain,2010，ChawlaandGionis,2013,Rodriguesetal.,2008，Labini,2008,Schikuta,1996,Kriegeletal.,2011)?；谀Ｐ偷臅r(shí)間序列聚類基于模型的聚類的基本思想是把原始時(shí)間序列轉(zhuǎn)換成模型的幾個(gè)參數(shù)，比如AR模型或HMM模型等，然后用模型參數(shù)進(jìn)行聚類(JieandQiang,2005，CamastraandVerri,2005,XiongandYeung,2004,Panuccioetal.,2002)。這種方法的不足之處在于需要對數(shù)據(jù)的分布進(jìn)行預(yù)先假設(shè)，此外，對參數(shù)的聚類結(jié)果無法進(jìn)行解釋，使得聚類缺乏可理解性。小結(jié)現(xiàn)有時(shí)間序列聚類方法大致可分成：基于原始序列、基于特征值和基于模型參數(shù)三種?；谠夹蛄械木垲惙椒ㄓ捎凇熬S災(zāi)難”很難產(chǎn)生較好的聚類效果，而基于模型參數(shù)的方法由于需要對數(shù)據(jù)做預(yù)先假設(shè)也使得應(yīng)用受到限制，基于特征值的聚類方法是最有前景的時(shí)間序列聚類算法。靜態(tài)時(shí)間序列列聚類k-medoids時(shí)間序列聚類類基于LB_Hust距離的時(shí)間序序列數(shù)據(jù)聚類類基于SAX表示的聚類k-mediods時(shí)間序列聚類類1、k-中心點(diǎn)聚類基基本原理：k-均值的缺點(diǎn)：：對離群點(diǎn)敏敏感k-中心點(diǎn)：挑選選實(shí)際對象來來代表簇，每每個(gè)簇使用一一個(gè)代表對象象。實(shí)現(xiàn)：圍繞中中心點(diǎn)劃分（（PartitioningAroundMedoids,PAM)算法算法:k-中心點(diǎn)。PAM輸入入：：k：結(jié)結(jié)果果簇簇的的個(gè)個(gè)數(shù)數(shù)D：包包含含n個(gè)對對象象的的數(shù)數(shù)據(jù)據(jù)集集合合輸出出：：k個(gè)簇簇的的集集合合k-mediods時(shí)間間序序列列聚聚類類方法法：：（1）從從D中隨隨機(jī)機(jī)選選擇擇k個(gè)對對象象作作為為初初始始的的代代表表對對象象或或種種子子（2）repeat（3）將將每每個(gè)個(gè)剩剩余余的的對對象象分分配配到到最最近近的的代代表表對對象象所所代代表表的的簇簇（4）隨隨機(jī)機(jī)地地選選擇擇一一個(gè)個(gè)非非代代表表對對象象Orandom（5）計(jì)計(jì)算算用用Orandom代替替代代表表對對象象Oj的總總代代價(jià)價(jià)S（代代價(jià)價(jià)函函數(shù)數(shù)就就是是計(jì)計(jì)算算絕絕對對誤誤差差值值的的差差））（6）ifS<0,thenOrandom替換換Oj，形形成成新新的的k個(gè)代代表表對對象象的的集集合合（7）until不發(fā)發(fā)生生變變化化特點(diǎn)點(diǎn)：：在小小型型數(shù)數(shù)據(jù)據(jù)集集上上運(yùn)運(yùn)行行良良好好，，不不適適合合大大數(shù)數(shù)據(jù)據(jù)集集，，算算法法復(fù)復(fù)雜雜度度太太高高。為為了了處處理理大大數(shù)數(shù)據(jù)據(jù)集集，，可可以以使使用用CLARA:大型型應(yīng)應(yīng)用用聚聚類類，，基基于于抽抽樣樣的的方方法法，，使使用用數(shù)數(shù)據(jù)據(jù)集集的的一一個(gè)個(gè)隨隨機(jī)機(jī)樣樣本本，，然然后后使使用用PAM方法法由由樣樣本本計(jì)計(jì)算算最最佳佳中中心心點(diǎn)點(diǎn)。。（（可可能能在在隨隨機(jī)機(jī)抽抽樣樣時(shí)時(shí)錯(cuò)錯(cuò)過過最最佳佳中中心心點(diǎn)點(diǎn)而而永永遠(yuǎn)遠(yuǎn)找找不不到到最最佳佳聚聚類類））k-mediods時(shí)間間序序列列聚聚類類2、基基于于k中心心點(diǎn)點(diǎn)方方法法的的時(shí)時(shí)間間序序列列聚聚類類見kmedoidtsclustering.cpp基于于LB_Hust距離離的的時(shí)時(shí)間間序序列列聚聚類類層次次聚聚類類方方法法對對給給定定數(shù)數(shù)據(jù)據(jù)對對象象集集合合進(jìn)進(jìn)行行層層次次分分解解。。根根據(jù)據(jù)層層次次的的分分解解如如何何形形成成，，層層次次的的方方法法可可以以分分為為凝凝聚聚的的（（agglomerativeormerging）和和分分裂裂的的（（divisiveorsplitting）兩兩種種類類型型。。凝聚聚的的方方法法，，也也稱稱為為自自底底向向上上的的方方法法，，初初始始化化將將每每個(gè)個(gè)對對象象作作為為單單獨(dú)獨(dú)的的一一個(gè)個(gè)簇簇，，然然后后相相繼繼地地合合并并相相近近的的對對象象或或簇簇，，直直到到所所有有的的簇簇合合并并為為一一個(gè)個(gè)，，或或者者達(dá)達(dá)到到一一個(gè)個(gè)終終止止條條件件。。分裂裂的的方方法法，，也也成成為為自自頂頂向向下下的的方方法法，，初初始始化化將將所所有有的的對對象象置置于于一一個(gè)個(gè)簇簇中中。。在在迭迭代代的的每每一一步步中中，，一一個(gè)個(gè)簇簇被被分分裂裂為為更更小小的的簇簇，，直直到到最最終終每每個(gè)個(gè)對對象象在在單單獨(dú)獨(dú)的的一一個(gè)個(gè)簇簇中中，，或或者者達(dá)達(dá)到到一一個(gè)個(gè)終終止止條條件件。。層次次方方法法的的缺缺陷陷在在于于，，一一旦旦一一個(gè)個(gè)步步驟驟完完成成，，就就不不能能夠夠被被撤撤銷銷。?；谟贚B_Hust距離離的的時(shí)時(shí)間間序序列列聚聚類類層次次聚聚類類算算法法在在聚聚類類算算法法中中不不必必確確定定初初始始聚聚類類中中心心，，對對聚聚類類過過程程中中數(shù)數(shù)據(jù)據(jù)的的輸輸入入順順序序不不敏敏感感，，同同時(shí)時(shí)對對用用戶戶輸輸入入?yún)?shù)數(shù)要要求求較較低低，，本本文文中中層層次次聚聚類類算算法法采采用用設(shè)設(shè)定定聚聚類類最最終終簇簇?cái)?shù)數(shù)的的方方法法終終止止聚聚類類，，從從而而自自發(fā)發(fā)形形成成聚聚類類，，保保證證了了聚聚類類過過程程中中根根據(jù)據(jù)數(shù)數(shù)據(jù)據(jù)之之間間相相似似程程度度進(jìn)進(jìn)行行歸歸并并，，人人為為影影響響因因素素較較小小。。輸入入：：時(shí)間間序序列列數(shù)數(shù)據(jù)據(jù)庫庫：：TSDB；允許許的的彎彎曲曲路路徑徑時(shí)時(shí)間間窗窗：：w；最大大的的簇簇?cái)?shù)數(shù)：：K；輸出出：：K個(gè)簇簇：：{C1，C2、，，···········CK}；LB_Keogh：一種種考考慮慮彎彎曲曲路路徑徑限限制制的的DTW計(jì)算算方方法法對于于彎彎曲曲路路徑徑限限制制為為w的時(shí)時(shí)間間序序列列DTW距離離計(jì)計(jì)算算，，定定義義兩兩個(gè)個(gè)序序列列U和L，其其中中對對于于第第i個(gè)元元素素我我們們有有如如下下的的上上下下界界定定義義：：U和L作為為在在2w時(shí)間間窗窗內(nèi)內(nèi)，，對對于于原原時(shí)時(shí)間間序序列列的的每每個(gè)個(gè)元元素素所所對對應(yīng)應(yīng)的的上上下下界界，，表表現(xiàn)現(xiàn)在在圖圖形形上上實(shí)實(shí)際際上上是是形形成成了了一一個(gè)個(gè)帶帶狀狀的的域域?qū)⒃际紩r(shí)時(shí)間間序序列列包包裹裹在在這這個(gè)個(gè)域域中中，，如如圖圖3-4所示示。。此時(shí)時(shí)，，LB_Keogh距離離定定義義為為：：定理理：：對對于于長長度度為為n的任任何何兩兩個(gè)個(gè)時(shí)時(shí)間間序序列列X和Y，限限定定彎彎曲曲路路徑徑窗窗口口為為w，即即對對于于xi和yj點(diǎn)的的比比較較，，限限定定為為j-wij+w，存存在在如如下下不不等等式式：：LB_Keogh(X,Y)DTW(X,Y)。性質(zhì)質(zhì)：：LB_Keogh距離離不不是是對對稱稱的的。。即即LB_Keogh(X,Y)LB_Keogh(Y,X)。LB_Keogh的Matlab實(shí)現(xiàn)現(xiàn)LB_Keogh=sqrt(sum([[Q>U].*[Q-U];[Q<L].*[L-Q]].^2));LB_Hust距離離---對LB_Keogh距離離的的改改進(jìn)進(jìn)針對對LB_Keogh距離離計(jì)計(jì)算算的的非非對對稱稱性性其中中，，Lxi和Uxi分別別對對應(yīng)應(yīng)時(shí)時(shí)間間序序列列X的第第i個(gè)元元素素在在2w時(shí)間間域域內(nèi)內(nèi)的的最最小小值值和和最最大大值值。。Lyi和Uyi同理理。。距距離離產(chǎn)產(chǎn)生生方方式式如如圖圖3-5所示示。。定理理：：對對于于長長度度為為n的任任何何兩兩個(gè)個(gè)時(shí)時(shí)間間序序列列X和Y，限限定定彎彎曲曲路路徑徑窗窗口口為為w，即即對對于于xi和yj點(diǎn)的的比比較較，，限限定定為為j-wij+w，存存在在如如下下不不等等式式：：LB_Hust(X,Y)Keogh(X,Y)。性質(zhì)質(zhì)1：LB_Hust距離離是是對對稱稱的的。。即即LB_Hust(X,Y)=LB_Hust(Y,X)。這可可以減減少距距離計(jì)計(jì)算的的次數(shù)數(shù)。性質(zhì)2：在LB_Hust距離計(jì)計(jì)算方方式下下，時(shí)時(shí)間復(fù)復(fù)雜度度由傳傳統(tǒng)的的DTW距離計(jì)計(jì)算的的O(nm)縮減到到O(n)?；贚B_Hust距離的的時(shí)間間序列列聚類類算法流流程：：1)初始狀狀態(tài)下下所有有有時(shí)時(shí)間序序列數(shù)數(shù)據(jù)自自成一一簇，，每條條時(shí)間間序列列數(shù)據(jù)據(jù)為各各自的的簇中中心，，循環(huán)環(huán)2）到4）。2)根據(jù)時(shí)時(shí)間序序列數(shù)數(shù)據(jù)上上下界界曲線線形成成方法法求取取當(dāng)前前簇中中心的的上下下界序序列Us和Ls。3)計(jì)算兩兩兩簇簇之間間的距距離，，記錄錄具有有最小小距離離的兩兩個(gè)簇簇，將將兩個(gè)個(gè)簇歸歸并，，根據(jù)據(jù)歸并并算法法更新新聚類類中心心。4)若當(dāng)前前聚類類簇?cái)?shù)數(shù)達(dá)到到K，則終終止，，否則則轉(zhuǎn)到到2)。分析上上述算算法，，存在在的兩兩個(gè)關(guān)關(guān)鍵的的函數(shù)數(shù)是計(jì)計(jì)算兩兩個(gè)序序列的的LB_Hust距離和和求取取新的的簇中中心兩兩個(gè)函函數(shù)。?；贚B_Hust距離矩矩陣的的層次次聚類類基于距距離矩矩陣的的層次次聚類類算法法是以以犧牲牲空間間換取取時(shí)間間的算算法，，存放放n條記錄錄兩兩兩之間間的距距離，，在距距離函函數(shù)計(jì)計(jì)算具具有對對稱性性的情情況下下，實(shí)實(shí)際的的矩陣陣只需需存放放上三三角或或下三三角n*(n+1)/2個(gè)數(shù)據(jù)據(jù)。這這也是是應(yīng)用用LB_Hust距離計(jì)計(jì)算函函數(shù)的的一個(gè)個(gè)重要要原因因。輸入：：時(shí)間間序列列數(shù)據(jù)據(jù)庫：：TSDB；允許的的彎曲曲路徑徑時(shí)間間窗：：w；最大的的簇?cái)?shù)數(shù)：K；輸出：：K個(gè)簇：：{C1，C2、，········CK}；基于LB_Hust距離矩矩陣的的層次次聚類類算法流流程：：1)初始狀狀態(tài)下下所有有時(shí)間間序列列數(shù)據(jù)據(jù)自成成一簇簇，每每條時(shí)時(shí)間序序列數(shù)數(shù)據(jù)為為各自自的簇簇中心心，初初始化化距離離矩陣陣，計(jì)計(jì)算任任意兩兩條時(shí)時(shí)間序序列數(shù)數(shù)據(jù)間間的距距離，，循環(huán)環(huán)2）到5）。2)找到距距離矩矩陣中中的最最小距距離對對應(yīng)的的兩個(gè)個(gè)簇，，合并并，形形成新新的簇簇中心心。3)根據(jù)時(shí)時(shí)間序序列數(shù)數(shù)據(jù)上上下界界曲線線形成成方法法求取取當(dāng)前前簇中中心的的上下下界索索引序序列Us、Ls。4)重新計(jì)計(jì)算當(dāng)當(dāng)前簇簇中心心和其其余簇簇的距距離，，更新新距離離矩陣陣。5)若當(dāng)前前聚類類簇?cái)?shù)數(shù)達(dá)到到K，則終終止，，否則則轉(zhuǎn)到到2)。對于上上述采采用距距離矩矩陣的的層次次聚類類，相相比前前面算算法，，每一一層合合并時(shí)時(shí)，距距離計(jì)計(jì)算次次數(shù)為為c(n,2)次，其其中n表示當(dāng)當(dāng)前層層中的的簇?cái)?shù)數(shù)，時(shí)時(shí)間復(fù)復(fù)雜度度為o(n2)，采用用距離離矩陣陣方法法則每每次僅僅需計(jì)計(jì)算n次距離離。應(yīng)用---股票數(shù)數(shù)據(jù)聚聚類股票數(shù)數(shù)據(jù)作作為典典型的的時(shí)間間序列列數(shù)據(jù)據(jù)，被被眾多多時(shí)間間序列列挖掘掘方法法作為為實(shí)驗(yàn)驗(yàn)性數(shù)數(shù)據(jù)。。典型型的股股票行行情原原始數(shù)數(shù)據(jù)包包括股股票的的開盤盤價(jià)、、最高高價(jià)、、最低低價(jià)、、收盤盤價(jià)、、成交交量、、成交交金額額等，，所有有屬性性的值值對應(yīng)應(yīng)著一一個(gè)特特定時(shí)時(shí)刻，，在固固定時(shí)時(shí)間段段內(nèi)形形成了了典型型的時(shí)時(shí)間序序列數(shù)數(shù)據(jù)。。對于多多支股股票的的聚類類是從從控股股公司司間的的經(jīng)營營狀況況、經(jīng)經(jīng)營手手段及及外界界影響響因素素的相相似程程度進(jìn)進(jìn)行聚聚類。。通過過對多多支股股票的的聚類類，可可以發(fā)發(fā)現(xiàn)股股票運(yùn)運(yùn)動(dòng)規(guī)規(guī)律相相似的的企業(yè)業(yè)，對對中長長期股股票投投資者者選股股提供供一些些參考考。股票數(shù)數(shù)據(jù)聚聚類：：數(shù)據(jù)據(jù)準(zhǔn)備備采用搜搜狐財(cái)財(cái)經(jīng)網(wǎng)網(wǎng)(/)的股票票歷史史行情情數(shù)據(jù)據(jù)作為為實(shí)驗(yàn)驗(yàn)數(shù)據(jù)據(jù)，從從中選選擇29支股票票作為為實(shí)驗(yàn)驗(yàn)數(shù)據(jù)據(jù)：寶寶鋼股股份、、包鋼鋼股份份、上上海電電力、、招商商輪船船、中中國石石油、、中中國銀銀行、、中海海油服服、武武鋼股股份、、東湖湖高新新、萬萬東醫(yī)醫(yī)療、、林海海股份份、中中視傳傳媒等等。在在數(shù)據(jù)據(jù)庫中中，存存儲(chǔ)股股票的的名稱稱采用用字母母代號號表示示，將將29支股票票對應(yīng)應(yīng)到A~A3的29個(gè)字母母串。。抽取從從2010年3月份到到2010年五月月份的的股票票歷史史行情情數(shù)據(jù)據(jù)，將將其中中的每每日收收盤價(jià)價(jià)作為為實(shí)驗(yàn)驗(yàn)數(shù)據(jù)據(jù)。在在提取取的數(shù)數(shù)據(jù)中中發(fā)現(xiàn)現(xiàn)，股股票數(shù)數(shù)據(jù)存存在如如下兩兩個(gè)特特點(diǎn)：：一、由于于股市的的休市，，股票數(shù)數(shù)據(jù)存在在空值；二、股票票之間的的收盤價(jià)價(jià)存在很很大差異異。股票數(shù)據(jù)據(jù)聚類：：數(shù)據(jù)準(zhǔn)準(zhǔn)備股票數(shù)據(jù)據(jù)普遍存存在空值值，主要要是基于于兩種情情況：一一、正常常的股市市休市。。二、個(gè)個(gè)別控股股公司由由于內(nèi)部部整合或或者公司司內(nèi)部事事件出現(xiàn)現(xiàn)停開。。每支股票票數(shù)據(jù)在在休市時(shí)時(shí)都是空空值，因因此可采采用直接接刪除的的方法不不會(huì)影響響到時(shí)間間序列的的時(shí)間對對等性。。針對公司司內(nèi)部事事件引起起的空值值采取填填補(bǔ)處理理。填補(bǔ)補(bǔ)數(shù)據(jù)根根據(jù)線性性化函數(shù)數(shù)取得，，對每個(gè)個(gè)空值，，以空值值上下非非空數(shù)據(jù)據(jù)為端點(diǎn)點(diǎn)得到一一次線性性化函數(shù)數(shù)，通過過線性化化函數(shù)可可以取得得空值對對應(yīng)時(shí)間間點(diǎn)的股股價(jià)。股票數(shù)據(jù)據(jù)聚類：：數(shù)據(jù)準(zhǔn)準(zhǔn)備采用線性性化函數(shù)數(shù)進(jìn)行填填補(bǔ)處理理是基于于兩點(diǎn)考考慮：首先，基基于對LB_Hust距離計(jì)算算的過程程，對于于時(shí)間序序列曲線線，趨勢勢的變動(dòng)動(dòng)和時(shí)間間序列的的連續(xù)能能夠增強(qiáng)強(qiáng)相似性性比較效效果，所所以，對對空值數(shù)數(shù)據(jù)進(jìn)行行線性的的平滑處處理可以以更好地地應(yīng)用LB_Hust距離計(jì)算算方法。。其次，從從實(shí)際意意義來看看，在空空值出現(xiàn)現(xiàn)前的階階段和空空值結(jié)束束后，兩兩者股價(jià)價(jià)一般不不同，可可見在股股價(jià)為空空值的階階段，實(shí)實(shí)際上隱隱藏著一一些影響響股價(jià)變變動(dòng)的因因素發(fā)生生著作用用，通過過線性化化函數(shù)，，將期間間出現(xiàn)的的變化過過程連續(xù)續(xù)的表達(dá)達(dá)出來，，函數(shù)中中的斜率率保持了了股價(jià)在在空值出出現(xiàn)階段段的趨勢勢變動(dòng)變變化規(guī)律律，通過過這種填填補(bǔ)方法法使得股股價(jià)波動(dòng)動(dòng)曲線更更連續(xù)和和平滑股票數(shù)據(jù)據(jù)聚類：：數(shù)據(jù)的的歸一化化除了空值值問題，，股票數(shù)數(shù)據(jù)另一一典型的的特點(diǎn)就就是不同同公司的的股價(jià)在在數(shù)值上上差異很很大。股票數(shù)據(jù)據(jù)聚類：：數(shù)據(jù)的的歸一化化針對股票票數(shù)據(jù)間間的股價(jià)價(jià)差距大大的問題題，采用用歸一化化處理，，歸一化化處理主主要解決決比較數(shù)數(shù)據(jù)間量量綱不統(tǒng)統(tǒng)一的問問題，在在對股票票進(jìn)行聚聚類分析析中，股股票的相相似性集集中于股股價(jià)變化化趨勢的的相似性性，而非非股價(jià)之之間的相相似性，，所以采采用以下下公式對對數(shù)據(jù)據(jù)進(jìn)行歸歸一化處處理。股票數(shù)據(jù)據(jù)聚類：：聚類結(jié)結(jié)果運(yùn)行層次次聚類算算法時(shí)初初始設(shè)定定聚類簇簇?cái)?shù)為4個(gè)，同時(shí)時(shí)設(shè)定時(shí)時(shí)間彎折折窗口w為3。股票數(shù)據(jù)據(jù)聚類：：聚類結(jié)結(jié)果運(yùn)行層次次聚類算算法時(shí)初初始設(shè)定定聚類簇簇?cái)?shù)為4個(gè)，同時(shí)時(shí)設(shè)定時(shí)時(shí)間彎折折窗口w為3。股票數(shù)據(jù)據(jù)聚類：：聚類結(jié)結(jié)果運(yùn)行層次次聚類算算法時(shí)初初始設(shè)定定聚類簇簇?cái)?shù)為4個(gè)，同時(shí)時(shí)設(shè)定時(shí)時(shí)間彎折折窗口w為3。股票數(shù)據(jù)據(jù)聚類：：聚類結(jié)結(jié)果運(yùn)行層次次聚類算算法時(shí)初初始設(shè)定定聚類簇簇?cái)?shù)為4個(gè)，同時(shí)時(shí)設(shè)定時(shí)時(shí)間彎折折窗口w為3?；赟AX表示的聚聚類HierarchicalClusteringComputepairwisedistance,mergesimilarclustersbottom-upComparedwithEuclidean,IMPACTS,andSDA基于SAX表示的距距離PAAdistancelower-boundstheEuclideanDistance

0

20

40

60

80

100

120

-1.5

-1

-0.5

0

0.5

1

1.5

C

Q

0

20

40

60

80

100

120

-1.5

-1

-0.5

0

0.5

1

1.5C

Q

=baabccbcC?=babcaccaQ?EuclideanDistancedist()canbeimplementedusingatablelookup.HierarchicalClusteringWecanobjectivelystatethatSAXissuperior,sinceitcorrectlyassignseachclasstoitsownsubtree.數(shù)據(jù)類別別事先已已知：decreasingtrend,upwardshiftandnormalclassesClusteringHierarchicalClusteringComputepairwisedistance,mergesimilarclustersbottom-upComparedwithEuclidean,IMPACTS,andSDAPartitionalClusteringK-meansOptimizetheobjectivefunctionbyminimizingthesumofsquaredintra-clustererrorsComparedwithRawdata比層次聚聚類具有有更好的的可伸縮縮性Partitional(K-means)ClusteringWorkingwithanapproximationofthedatagivesbetterresultsthanworkingwiththeoriginaldata.Ithasbeenshownthatinitializingtheclusterscentersonalowdimensionapproximationofthedatacanimprovethequality,thisiswhatclusteringwithSAXimplicitlydoes.Acomparisonofthek-meansclusteringalgorithmusingSAXandtherawdata.ThedatasetwasSpaceShuttletelemetry,1,000subsequencesoflength512.Surprisingly,workingwiththesymbolicapproximationproducesbetterresultsthanworkingwiththeoriginaldata動(dòng)態(tài)時(shí)間序列列聚類TimeSeriesEpenthesis:ClusteringTimeSeriesStreamsRequiresIgnoringSomeData動(dòng)態(tài)時(shí)間序列列聚類所謂流數(shù)據(jù)，，是指按照一一定的時(shí)間順順序，以較快快的速度連續(xù)續(xù)到達(dá)的數(shù)據(jù)據(jù)序列，也稱稱為動(dòng)態(tài)時(shí)間間序列。流數(shù)據(jù)聚類的的難點(diǎn)在于：：數(shù)據(jù)流隨著著時(shí)間的推移移近似地等效效于一個(gè)無限的數(shù)據(jù)集合，，因此對流數(shù)數(shù)據(jù)的隨機(jī)訪訪問幾乎是不不可能實(shí)現(xiàn)的的，因此流數(shù)數(shù)據(jù)聚類通常常都要求“一次性掃描數(shù)數(shù)據(jù)”。流數(shù)據(jù)聚類類算法首先對對每個(gè)新到達(dá)達(dá)的數(shù)據(jù)進(jìn)行行訪問處理，，之后數(shù)據(jù)即即被放入隨機(jī)機(jī)訪問代價(jià)較較高的存儲(chǔ)設(shè)設(shè)備，或者直直接被丟棄。。流數(shù)據(jù)聚類算算法通常會(huì)維維護(hù)一個(gè)“概要數(shù)據(jù)結(jié)構(gòu)構(gòu)”，用來保存數(shù)數(shù)據(jù)的摘要信信息，當(dāng)需要要輸出聚類結(jié)結(jié)果時(shí)，以概概要數(shù)據(jù)結(jié)構(gòu)構(gòu)中保存的信信息作為目標(biāo)標(biāo)對象集合，，生成所需要要的結(jié)果。流數(shù)據(jù)實(shí)例商業(yè)領(lǐng)域中，，大型倉儲(chǔ)超超市的交易數(shù)數(shù)據(jù)。超市的的數(shù)據(jù)中心每每天收到各個(gè)個(gè)分店大量的的交易記錄，，包括顧客購購買物品，消消費(fèi)金額等屬屬性，按照時(shí)時(shí)間順序排列列。電信行業(yè)中，，移動(dòng)公司可可采集到用戶戶的通話記錄錄，包括主叫叫號碼，被叫叫號碼，通話話時(shí)間，收費(fèi)費(fèi)金額等若干干屬性。大量量的通話記錄錄以時(shí)間順序序排列，匯集集到移動(dòng)公司司的數(shù)據(jù)中心心，也可以被被抽象為是一一種“流”。醫(yī)療行業(yè)中，，使用生理信信號采集儀器器對患者進(jìn)行行監(jiān)控，心跳跳，脈搏，血血壓等一系列列生理信號實(shí)實(shí)時(shí)地傳送到到分析模塊，，從中推測出出患者每一時(shí)時(shí)段的健康狀狀況。工業(yè)生產(chǎn)中，，一些大型設(shè)設(shè)備的安全檢檢測儀器每時(shí)時(shí)每刻將設(shè)備備的各項(xiàng)運(yùn)轉(zhuǎn)轉(zhuǎn)參數(shù)采集出出來，作為數(shù)數(shù)據(jù)信號進(jìn)行行分析處理。。流數(shù)據(jù)特點(diǎn)首先，數(shù)據(jù)量十分龐龐大，這些數(shù)據(jù)隨隨著時(shí)間的增增長數(shù)量急劇劇上升，如沃沃爾瑪超市的的日交易次數(shù)數(shù)可達(dá)數(shù)十萬萬。其次，這些數(shù)數(shù)據(jù)均按照時(shí)間順序序連續(xù)到達(dá)。另外，數(shù)據(jù)流速很快快，以廣東省移移動(dòng)公司的通通話記錄為例例，高峰時(shí)間間每小時(shí)可達(dá)達(dá)數(shù)千條。流數(shù)據(jù)聚類問問題模型假設(shè)流數(shù)據(jù)由由一系列按照照時(shí)間順序連連續(xù)到達(dá)的數(shù)數(shù)據(jù)點(diǎn)X1,...,Xi...構(gòu)成，其中，，每個(gè)數(shù)據(jù)點(diǎn)點(diǎn)擁有d個(gè)屬性，用d維向量的形式式來表示：那么流數(shù)據(jù)聚聚類問題，就就是將數(shù)據(jù)流流中的某個(gè)特特定的子對象象集合{X1,X2,...,XN}劃分成k個(gè)簇區(qū)間(每個(gè)簇用其均均值中心點(diǎn)來來表示),使目標(biāo)函數(shù)值值:達(dá)到最小。其其中Ci是Xi所在簇的中心心點(diǎn)，D(Xi,Ci)表示兩個(gè)數(shù)據(jù)據(jù)點(diǎn)之間的距距離。流數(shù)據(jù)聚類問問題模型對該問題模型型，有幾點(diǎn)需需要說明：1)目標(biāo)集合中數(shù)數(shù)據(jù)對象的個(gè)個(gè)數(shù)N通常在數(shù)量級級上遠(yuǎn)遠(yuǎn)大于于傳統(tǒng)算法中中的數(shù)據(jù)集合合，通常無法法將全部數(shù)據(jù)據(jù)讀入內(nèi)存進(jìn)進(jìn)行分析，因因此難以利用用傳統(tǒng)的聚類類算法解決這這類問題。2)在流數(shù)據(jù)聚類類問題中，數(shù)數(shù)據(jù)通常只能能按照它們到到達(dá)的順序訪訪問，此后，，數(shù)據(jù)即被存存放于外存或或丟棄，內(nèi)存存中只能保存存已訪問數(shù)據(jù)據(jù)的概要信息息。也就是說說，流數(shù)據(jù)算算法為了避免免高昂的系統(tǒng)統(tǒng)開銷應(yīng)該盡盡可能少地重重復(fù)訪問數(shù)據(jù)據(jù)。事實(shí)上，，“一次掃描描數(shù)據(jù)”已經(jīng)經(jīng)成為幾乎所所有流數(shù)據(jù)算算法都需要實(shí)實(shí)現(xiàn)的目標(biāo)。。流數(shù)據(jù)聚類問問題模型3)流數(shù)據(jù)算法的的目標(biāo)集合是是數(shù)據(jù)流中截截取的某一個(gè)個(gè)時(shí)間段(時(shí)間窗)的對象集合。。定義一個(gè)時(shí)時(shí)間窗需要兩兩個(gè)重要的輸輸入?yún)?shù)：起起始時(shí)刻t和時(shí)間窗口寬寬度h，一個(gè)時(shí)間窗窗口可用W(t,h)來表示。算法法的目標(biāo)集合合即由落入窗窗口W(t,h)的數(shù)據(jù)對象組組成。4)在流數(shù)據(jù)算法法中，任何一一個(gè)時(shí)刻的較較小的誤差，，都有可能隨隨著時(shí)間的推推移而急速擴(kuò)擴(kuò)大，最終造造成錯(cuò)誤或質(zhì)質(zhì)量較低的算算法結(jié)果。因因此，在每一一個(gè)階段都要要將誤差嚴(yán)格格控制在一個(gè)個(gè)較小的區(qū)間間之內(nèi)。5)同時(shí)，算法對對時(shí)間效率的的要求非常高高，當(dāng)需要在在某一個(gè)特定定時(shí)刻輸出聚聚類結(jié)果時(shí)，，如果處理過過程的時(shí)間開開銷過大，則則有可能會(huì)造造成新到數(shù)據(jù)據(jù)的遺漏或丟丟失，這種信信息缺損隨著著數(shù)據(jù)流的不不斷進(jìn)行而加加劇。早期的流數(shù)據(jù)據(jù)聚類早期的流數(shù)據(jù)據(jù)聚類努力將將數(shù)據(jù)流的動(dòng)動(dòng)態(tài)特性轉(zhuǎn)化化為傳統(tǒng)的靜靜態(tài)模式，從從而能夠應(yīng)用用成熟的傳統(tǒng)統(tǒng)方法解決問問題。在這一一階段，算法法研究的重點(diǎn)點(diǎn)是改進(jìn)傳統(tǒng)統(tǒng)算法的性能能，使之能夠夠適應(yīng)流數(shù)據(jù)據(jù)的動(dòng)態(tài)特性性。Small-Space算法正是這類類算法的典型型代表。Small-Space算法輸入：按時(shí)間間順序到達(dá)的的流數(shù)據(jù)序列列輸出：k個(gè)聚類中心點(diǎn)點(diǎn)算法過程：1)首先對初始到到達(dá)的m個(gè)數(shù)據(jù)點(diǎn)進(jìn)行行聚類，得到到O(k)個(gè)1-級聚類中心點(diǎn)點(diǎn)。2)重復(fù)上述步驟驟，當(dāng)處理m2/O(k)個(gè)原始數(shù)據(jù)點(diǎn)點(diǎn)時(shí)，將得到到m個(gè)1-級中心點(diǎn)。3)對這m個(gè)1-級中心點(diǎn)進(jìn)行行聚類得到O(k)個(gè)2-級中心點(diǎn)。4)迭代執(zhí)行上述述過程，每次次迭代至多保保留m個(gè)i-級中心點(diǎn)，否否則進(jìn)行聚類類得到O(k)個(gè)(i+1)-級中心點(diǎn)。5)輸出聚類結(jié)果果時(shí)，對當(dāng)前前所有中心點(diǎn)點(diǎn)進(jìn)行聚類，，得到最終的的k個(gè)聚類中心。?！鯯mall-Space算法的問題算法需要累積積數(shù)據(jù)點(diǎn)，當(dāng)當(dāng)數(shù)據(jù)量達(dá)到到一定限度時(shí)時(shí)進(jìn)行統(tǒng)一處處理，而通常常處理算法較較為復(fù)雜，造造成了數(shù)據(jù)流流在處理節(jié)點(diǎn)點(diǎn)上的延遲。。另一方面，，在累積數(shù)數(shù)據(jù)點(diǎn)的過過程中，算算法處于空空閑狀態(tài)，，在一定程程度上降低低了算法的的效率，增增加了時(shí)間間開銷。雙層流數(shù)據(jù)據(jù)聚類J.Han提出雙層結(jié)結(jié)構(gòu)算法CluStream[12]雙層聚類算算法將處理理工作分為為兩個(gè)層面面：在線層層算法負(fù)責(zé)責(zé)對數(shù)據(jù)進(jìn)進(jìn)行粗糙但但快速的處處理，并負(fù)負(fù)責(zé)保存中中間結(jié)果；；離線層算算法在中間間結(jié)果的基基礎(chǔ)上進(jìn)行行精確而復(fù)復(fù)雜的分析析，此時(shí)目目標(biāo)集合已已成為靜態(tài)態(tài)集合，因因此通常情情況下不必必考慮數(shù)據(jù)據(jù)流速的影影響，并得得到最終結(jié)結(jié)果。CluStream基本思想在線層維護(hù)護(hù)一系列的的“微簇””(Micro-Cluster)作為保存數(shù)數(shù)據(jù)概要信信息的數(shù)據(jù)據(jù)結(jié)構(gòu)。每每個(gè)微簇用用五元組(SS，LS，ST，LT，N)來表示，其其中N為微簇中包包含的數(shù)據(jù)據(jù)點(diǎn)個(gè)數(shù)，，若數(shù)據(jù)維維度為d，則LS，與SS均為d維向量，LS為微簇中數(shù)數(shù)據(jù)點(diǎn)的線線性加和，，SS為微簇中數(shù)數(shù)據(jù)點(diǎn)的平平方和，LT為各個(gè)數(shù)據(jù)據(jù)點(diǎn)時(shí)間標(biāo)標(biāo)簽的線性性加和，ST為各個(gè)數(shù)據(jù)據(jù)點(diǎn)時(shí)間標(biāo)標(biāo)簽的平方方和。以上統(tǒng)計(jì)變變量分別是是關(guān)于數(shù)據(jù)據(jù)集合的零零階矩，一一階矩和二二階矩。這這些信息可可以被用來來推演數(shù)據(jù)據(jù)的分布狀狀態(tài)，可以以用如下公公式計(jì)算數(shù)數(shù)據(jù)集合的的方差J：CluStream基本思想算法在初始始化時(shí)，首首先吸收足足夠的數(shù)據(jù)據(jù)點(diǎn)，利用用k-均值方法對對這些初始始數(shù)據(jù)點(diǎn)進(jìn)進(jìn)行聚類得得到k個(gè)微簇。每當(dāng)新的數(shù)數(shù)據(jù)點(diǎn)到達(dá)達(dá)時(shí)，在線線算法首先先嘗試找到到一個(gè)其均均值中心點(diǎn)點(diǎn)距離該新新到數(shù)據(jù)點(diǎn)點(diǎn)最近的微微簇，如果果這個(gè)距離離小于給定定的閾值，，則微簇將將該點(diǎn)吸收收，修改代代表微簇的的五元組中中每個(gè)變量量的值；否否則，為該該數(shù)據(jù)點(diǎn)開開辟新的微微簇。為了開辟新新的微簇，，需要通過過刪除現(xiàn)有有微簇或合合并兩個(gè)現(xiàn)現(xiàn)有微簇的的方式釋放放內(nèi)存空間間。如果能能夠找到兩兩個(gè)距離最最近的微簇簇，并且其其距離在一一定的閾值值之內(nèi)，則則將其合并并；否則，，刪除一個(gè)個(gè)最久未更更新的微簇簇，這是通通過檢查微微簇的ST與LT屬性得到的的。易見用用戶對最近近數(shù)據(jù)更感感興趣。CluStream基本思想在適當(dāng)?shù)臅r(shí)時(shí)刻對內(nèi)存存中的所有有微簇進(jìn)行行“快照””(snapshots)保存。這些些快照保存存在外存上上，作為離離線算法的的輸入，可可以用來進(jìn)進(jìn)行數(shù)據(jù)流流演化分析析。CluStream基本思想用戶在離線線部分可以以在不同時(shí)時(shí)間幅度內(nèi)內(nèi)發(fā)現(xiàn)簇。。所用的數(shù)數(shù)據(jù)是在線線部分形成成的統(tǒng)計(jì)信信息，這可可以滿足內(nèi)內(nèi)存有限的的需求。用用戶需提供供兩個(gè)參數(shù)數(shù)h和k，，h是時(shí)間間幅度，k是預(yù)定義義的需要形形成的簇的的數(shù)目。離線部分采采用改進(jìn)的的k-means算算法（1）初始始階段不再隨機(jī)地地選取種子子，而是選選擇可能被被劃分到給給定簇的種種子，這些些種子其實(shí)實(shí)是對應(yīng)微微簇的中心心。（2）劃分分階段一個(gè)種子到到一個(gè)“偽偽數(shù)據(jù)點(diǎn)””（也就是是微簇）的的距離就等等于它到““偽數(shù)據(jù)點(diǎn)點(diǎn)”中心的的距離。（3）調(diào)整整階段一個(gè)給定劃劃分的新種種子被定義義成那個(gè)劃劃分中帶權(quán)權(quán)重的微簇簇中心。CluStream示意圖CluStream算法優(yōu)缺缺點(diǎn)優(yōu)點(diǎn)：提出了兩階階段聚類框框架，算法法能適應(yīng)數(shù)數(shù)據(jù)流快速速、有序無無限、單遍遍掃描的特特點(diǎn)。能夠夠發(fā)掘數(shù)據(jù)據(jù)流潛在的的演化特性性。缺點(diǎn)：1、不能發(fā)發(fā)現(xiàn)任意形形狀的簇；；2、不能很很好地識別別離群點(diǎn)；；3、對高維維數(shù)據(jù)聚類類質(zhì)量下降降；謝謝！9、靜靜夜夜四四無無鄰鄰，，荒荒居居舊舊業(yè)業(yè)貧貧。。。。12月月-2212月月-22Saturday,December24,202210、雨雨中中黃黃葉葉樹樹，，燈燈下下白白頭頭人人。。。。07:25:2007:25:2007:2512/24/20227:25:20AM11、以我我獨(dú)沈沈久，，愧君君相見見頻。。。12月月-2207:25:2007:25Dec-2224-Dec-2212、故人江海海別，幾度度隔山川。。。07:25:2007:25:2007:25Saturday,December24,202213、乍乍見見翻翻疑疑夢夢，，相相悲悲各各問問年年。。。。12月月-2212月月-2207:25:2007:25:20December24,202214、他鄉(xiāng)生白發(fā)發(fā)，舊國見青青山。。24十二月月2