1、時(shí)間序列發(fā)掘聚類山西財(cái)經(jīng)大學(xué)信息管理學(xué)院常新功第六章目 錄聚類的概念聚類算法的評(píng)價(jià)規(guī)范時(shí)間序列聚類概述k-mediods時(shí)間序列聚類基于 LB_Hust 間隔的時(shí)間序列聚類基于SAX表示的聚類聚類的概念聚類Clustering是數(shù)據(jù)發(fā)掘領(lǐng)域中的一個(gè)重要分支。所謂聚類，是指將物理或籠統(tǒng)對(duì)象的集合分組成為由類似的對(duì)象組成的多個(gè)類的過程 。聚類是根據(jù)事物的某些屬性將其聚集成類，使類間類似性盡量小，類內(nèi)類似性盡量大。2021.4.19，的深圳舉行的新一代信息技術(shù)產(chǎn)業(yè)開展頂峰論壇上，中國工程院院士李德毅在發(fā)言中指出，雖然目前對(duì)于大數(shù)據(jù)的認(rèn)知存在挑戰(zhàn)，但聚類將會(huì)成為大數(shù)據(jù)認(rèn)知的突破口。經(jīng)過大數(shù)據(jù)聚類即時(shí)發(fā)

2、現(xiàn)價(jià)值，要充分認(rèn)識(shí)大數(shù)據(jù)中的不確定性和價(jià)值的隱蔽性。 聚類算法的評(píng)價(jià)規(guī)范1) 可伸縮性：可伸縮性調(diào)查聚類算法對(duì)于目的對(duì)象集合的規(guī)模以及目的集合潛在的方式數(shù)量的順應(yīng)性。2) 處置不同類型屬性的才干：除了通常處置的數(shù)值型數(shù)據(jù)，運(yùn)用當(dāng)中能夠要求聚類其它類型的數(shù)據(jù)，如：二元類型，分類/標(biāo)稱類型，序數(shù)型，時(shí)間序列、圖數(shù)據(jù)或者不同數(shù)據(jù)類型的混合。3) 發(fā)現(xiàn)任不測(cè)形的聚類：許多聚類算法基于歐幾里德間隔或者曼哈頓間隔度量來決議聚類。基于這種間隔度量的算法趨向于發(fā)現(xiàn)具有相近尺度和密度的球狀簇。但是一個(gè)簇能夠是任不測(cè)形的，提出能發(fā)現(xiàn)任不測(cè)形簇的算法是很重要的。4)交互可視化：高維數(shù)據(jù)和復(fù)雜對(duì)象經(jīng)常使可視化變得困難

3、，而交互性那么使算法與人結(jié)合有利于提高聚類的質(zhì)量。聚類算法的評(píng)價(jià)規(guī)范5) 最小化用于決議輸入?yún)?shù)的領(lǐng)域知識(shí)和數(shù)據(jù)記錄敏感性：一方面要求降低算法對(duì)輸入?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ù)。一些聚類算法對(duì)于這樣的數(shù)據(jù)敏感，導(dǎo)致聚類質(zhì)量不高。7) 高維性：許多聚類算法只擅優(yōu)點(diǎn)理低維數(shù)據(jù)。在高維空間中聚類數(shù)據(jù)對(duì)象是一個(gè)挑戰(zhàn)，特別是在數(shù)據(jù)有能夠非常稀疏和偏斜時(shí)。8) 可解釋性和可用性：知識(shí)發(fā)現(xiàn)過程中，聚類結(jié)果總是需求表現(xiàn)為一定

4、的知識(shí)，這就要求聚類結(jié)果可解釋，易了解。時(shí)間序列聚類概述時(shí)間序列聚類是時(shí)間序列數(shù)據(jù)發(fā)掘的一個(gè)非常根底且非?；顫姷难杏懛较?，被廣泛運(yùn)用于包括方式識(shí)別、數(shù)據(jù)分析、圖像處置、市場(chǎng)分析等各個(gè)領(lǐng)域：零售數(shù)據(jù)的季節(jié)方式聚類、國家能源耗費(fèi)聚類分析、心電圖ECG信號(hào)聚類分析、股票序列的方式發(fā)現(xiàn)以及個(gè)人收入數(shù)據(jù)的聚類等等(Valk and Pinheiro, 2021, Rodrigues et al., 2021, Costa Santos et al., 2006, Berkhin, 2006, Warren Liao，2005, Bagnall and Janacek, 2005)。國內(nèi)外許多研討者提出了

5、很多時(shí)間序列聚類方法，這些方法大致可以分為三種：基于原始序列、基于特征數(shù)據(jù)和基于模型參數(shù)(Warren Liao, 2005)?；谠夹蛄袛?shù)據(jù)的時(shí)間序列聚類直接運(yùn)轉(zhuǎn)在原始時(shí)間序列上的聚類稱為基于原始數(shù)據(jù)的聚類(Zhang et al., 2021, Rodrigues et al., 2021, Warren Liao, 2005)。但在實(shí)際中，由于時(shí)間序列的高維特點(diǎn)，會(huì)導(dǎo)致大部分的聚類方法失效，詳細(xì)表現(xiàn)為：(1)時(shí)間序列被看成高維空間中的一個(gè)點(diǎn)，所以數(shù)據(jù)分布會(huì)呈現(xiàn)稀疏性，從而導(dǎo)致歐氏間隔不能正確測(cè)度對(duì)象間的類似程度(Wang et al., 2005, Domeniconi et al.,

6、 2004)；(2)多數(shù)算法的性能受參數(shù)設(shè)置的影響，在缺乏背景知識(shí)時(shí)，用戶可以根據(jù)反響的算法結(jié)果精調(diào)參數(shù)，但高維數(shù)據(jù)呵斥聚類結(jié)果無法可視化，使得用戶很難判別聚類結(jié)果的質(zhì)量，所以很難合理設(shè)置參數(shù)Jain, 2021, Chen, 2007, Lin et al., 2004，Ding and He, 2004)?；谔卣鲾?shù)據(jù)的時(shí)間序列聚類基于特征的表示方法是把原始時(shí)間序列轉(zhuǎn)換到一個(gè)低維的特征空間，然后用傳統(tǒng)的聚類方法對(duì)特征向量進(jìn)展聚類(Yang et al., 2021, Xiaozhe et al., 2007,Keogh et al., 2007, Chen, 2007, Zhang et

7、al., 2006, Wang et al., 2006，Costa Santos et al., 2006，Wang et al., 2005，Bagnall and Janacek, 2005，Domeniconi et al., 2004)。由于基于特征的聚類方法中提取的特征來自序列本身，且具有特定的含義，所以該聚類方法不僅實(shí)現(xiàn)對(duì)序列的降維，又使得聚類結(jié)果具有可解釋性。這里，常用的傳統(tǒng)的聚類算法有如下幾種：劃分聚類、層次聚類和密度聚類等等(Jain, 2021，Chawla and Gionis, 2021, Rodrigues et al., 2021，Labini, 2021, Sc

8、hikuta, 1996, Kriegel et al., 2021)?；谀Ｐ偷臅r(shí)間序列聚類基于模型的聚類的根本思想是把原始時(shí)間序列轉(zhuǎn)換成模型的幾個(gè)參數(shù)，比如AR模型或HMM模型等，然后用模型參數(shù)進(jìn)展聚類(Jie and Qiang, 2005，Camastra and Verri, 2005, Xiong and Yeung, 2004, Panuccio et al., 2002)。這種方法的缺乏之處在于需求對(duì)數(shù)據(jù)的分布進(jìn)展預(yù)先假設(shè)，此外，對(duì)參數(shù)的聚類結(jié)果無法進(jìn)展解釋，使得聚類缺乏可了解性。小 結(jié)現(xiàn)有時(shí)間序列聚類方法大致可分成：基于原始序列、基于特征值和基于模型參數(shù)三種?；谠夹蛄械木?/p>

9、類方法由于“維災(zāi)難很難產(chǎn)生較好的聚類效果，而基于模型參數(shù)的方法由于需求對(duì)數(shù)據(jù)做預(yù)先假設(shè)也使得運(yùn)用遭到限制，基于特征值的聚類方法是最有前景的時(shí)間序列聚類算法。靜態(tài)時(shí)間序列聚類k-medoids時(shí)間序列聚類基于 LB_Hust 間隔的時(shí)間序列數(shù)據(jù)聚類基于SAX表示的聚類k-mediods時(shí)間序列聚類1、k-中心點(diǎn)聚類根本原理：k-均值的缺陷：對(duì)離群點(diǎn)敏感k-中心點(diǎn)：挑選實(shí)踐對(duì)象來代表簇，每個(gè)簇運(yùn)用一個(gè)代表對(duì)象。實(shí)現(xiàn)：圍繞中心點(diǎn)劃分Partitioning Around Medoids, PAM)算法算法:k-中心點(diǎn)。PAM輸入：k：結(jié)果簇的個(gè)數(shù)D：包含n個(gè)對(duì)象的數(shù)據(jù)集合輸出：k個(gè)簇的集合k-med

10、iods時(shí)間序列聚類方法：1從D中隨機(jī)選擇k個(gè)對(duì)象作為初始的代表對(duì)象或種子2repeat3將每個(gè)剩余的對(duì)象分配到最近的代表對(duì)象所代表的簇4隨機(jī)地選擇一個(gè)非代表對(duì)象Orandom5計(jì)算用Orandom替代代表對(duì)象Oj的總代價(jià)S代價(jià)函數(shù)就是計(jì)算絕對(duì)誤差值的差6if SU.* Q-U; QL.* L-Q.2); LB_Hust 間隔-對(duì)LB_Keogh間隔的改良針對(duì) LB_Keogh間隔計(jì)算的非對(duì)稱性其中，Lxi和 Uxi分別對(duì)應(yīng)時(shí)間序列 X 的第 i 個(gè)元素在 2w 時(shí)間域內(nèi)的最小值和最大值。Lyi和 Uyi同理。間隔產(chǎn)生方式如圖 3-5 所示。定理：對(duì)于長度為 n 的任何兩個(gè)時(shí)間序列 X 和 Y

11、，限定彎曲途徑窗口為w，即對(duì)于 xi和 yj點(diǎn)的比較，限定為 j-w i j+w，存在如下不等式： LB_ Hust(X,Y) Keogh(X,Y) 。性質(zhì)1：LB_Hust 間隔是對(duì)稱的。即 LB_Hust (X,Y) =LB_Hust (Y,X)。這可以減少間隔計(jì)算的次數(shù)。性質(zhì)2：在 LB_Hust 間隔計(jì)算方式下，時(shí)間復(fù)雜度由傳統(tǒng)的 DTW 間隔計(jì)算的 O(nm)縮減到 O(n)?；?LB_Hust 間隔的時(shí)間序列聚類算法流程：1) 初始形狀下一切有時(shí)間序列數(shù)據(jù)自成一簇，每條時(shí)間序列數(shù)據(jù)為各自的簇中心，循環(huán) 2到 4。2) 根據(jù)時(shí)間序列數(shù)據(jù)上下界曲線構(gòu)成方法求取當(dāng)前簇中心的上下界序列

12、Us和 Ls。3) 計(jì)算兩兩簇之間的間隔，記錄具有最小間隔的兩個(gè)簇，將兩個(gè)簇歸并，根據(jù)歸并算法更新聚類中心。4) 假設(shè)當(dāng)前聚類簇?cái)?shù)到達(dá) K，那么終止，否那么轉(zhuǎn)到 2)。分析上述算法，存在的兩個(gè)關(guān)鍵的函數(shù)是計(jì)算兩個(gè)序列的 LB_Hust 間隔和求取新的簇中心兩個(gè)函數(shù)?；?LB_Hust 間隔矩陣的層次聚類基于間隔矩陣的層次聚類算法是以犧牲空間換取時(shí)間的算法，存放 n 條記錄兩兩之間的間隔，在間隔函數(shù)計(jì)算具有對(duì)稱性的情況下，實(shí)踐的矩陣只需存放上三角或下三角 n*(n+1)/2 個(gè)數(shù)據(jù)。這也是運(yùn)用 LB_Hust 間隔計(jì)算函數(shù)的一個(gè)重要緣由。輸入：時(shí)間序列數(shù)據(jù)庫：TSDB；允許的彎曲途徑時(shí)間窗：w

13、；最大的簇?cái)?shù)：K；輸出：K 個(gè)簇：C1， C2、， CK；基于 LB_Hust 間隔矩陣的層次聚類算法流程：1) 初始形狀下一切時(shí)間序列數(shù)據(jù)自成一簇，每條時(shí)間序列數(shù)據(jù)為各自的簇中心，初始化間隔矩陣，計(jì)算恣意兩條時(shí)間序列數(shù)據(jù)間的間隔，循環(huán) 2到 5。2) 找到間隔矩陣中的最小間隔對(duì)應(yīng)的兩個(gè)簇，合并，構(gòu)成新的簇中心。3) 根據(jù)時(shí)間序列數(shù)據(jù)上下界曲線構(gòu)成方法求取當(dāng)前簇中心的上下界索引序列 Us、Ls。4) 重新計(jì)算當(dāng)前簇中心和其他簇的間隔，更新間隔矩陣。5) 假設(shè)當(dāng)前聚類簇?cái)?shù)到達(dá) K，那么終止，否那么轉(zhuǎn)到 2)。對(duì)于上述采用間隔矩陣的層次聚類，相比前面算法，每一層合并時(shí)，間隔計(jì)算次數(shù)為c(n,2)次

14、，其中 n 表示當(dāng)前層中的簇?cái)?shù)，時(shí)間復(fù)雜度為 o(n2)，采用間隔矩陣方法那么每次僅需計(jì)算 n 次間隔。運(yùn)用-股票數(shù)據(jù)聚類股票數(shù)據(jù)作為典型的時(shí)間序列數(shù)據(jù)，被眾多時(shí)間序列發(fā)掘方法作為實(shí)驗(yàn)性數(shù)據(jù)。典型的股票行情原始數(shù)據(jù)包括股票的開盤價(jià)、最高價(jià)、最低價(jià)、收盤價(jià)、成交量、成交金額等，一切屬性的值對(duì)應(yīng)著一個(gè)特定時(shí)辰，在固定時(shí)間段內(nèi)構(gòu)成了典型的時(shí)間序列數(shù)據(jù)。對(duì)于多支股票的聚類是從控股公司間的運(yùn)營情況、運(yùn)營手段及外界影響要素的類似程度進(jìn)展聚類。經(jīng)過對(duì)多支股票的聚類，可以發(fā)現(xiàn)股票運(yùn)動(dòng)規(guī)律類似的企業(yè)，對(duì)中長期股票投資者選股提供一些參考。股票數(shù)據(jù)聚類：數(shù)據(jù)預(yù)備采用搜狐財(cái)經(jīng)網(wǎng)(q.stock.sohu/)的股票歷史

15、行情數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，從中選擇 29 支股票作為實(shí)驗(yàn)數(shù)據(jù)：寶鋼股份、包鋼股份、上海電力、招商輪船、中國石油 、中國銀行、中海油服、武鋼股份、東湖高新、萬東醫(yī)療、林海股份、中視傳媒等。在數(shù)據(jù)庫中，存儲(chǔ)股票的稱號(hào)采用字母代號(hào)表示，將 29 支股票對(duì)應(yīng)到 AA3 的 29 個(gè)字母串。抽取從 2021年3月份到2021年五月份的股票歷史行情數(shù)據(jù)，將其中的每日收盤價(jià)作為實(shí)驗(yàn)數(shù)據(jù)。在提取的數(shù)據(jù)中發(fā)現(xiàn)，股票數(shù)據(jù)存在如下兩個(gè)特點(diǎn)：一、由于股市的休市，股票數(shù)據(jù)存在空值；二、股票之間的收盤價(jià)存在很大差別。股票數(shù)據(jù)聚類：數(shù)據(jù)預(yù)備股票數(shù)據(jù)普遍存在空值，主要是基于兩種情況：一、正常的股市休市。二、個(gè)別控股公司由于內(nèi)部整

16、合或者公司內(nèi)部事件出現(xiàn)停開。每支股票數(shù)據(jù)在休市時(shí)都是空值，因此可采用直接刪除的方法不會(huì)影響到時(shí)間序列的時(shí)間對(duì)等性。針對(duì)公司內(nèi)部事件引起的空值采取填補(bǔ)處置。填補(bǔ)數(shù)據(jù)根據(jù)線性化函數(shù)獲得，對(duì)每個(gè)空值，以空值上下非空數(shù)據(jù)為端點(diǎn)得到一次線性化函數(shù)，經(jīng)過線性化函數(shù)可以獲得空值對(duì)應(yīng)時(shí)間點(diǎn)的股價(jià)。股票數(shù)據(jù)聚類：數(shù)據(jù)預(yù)備采用線性化函數(shù)進(jìn)展填補(bǔ)處置是基于兩點(diǎn)思索：首先，基于對(duì) LB_Hust 間隔計(jì)算的過程，對(duì)于時(shí)間序列曲線，趨勢(shì)的變動(dòng)和時(shí)間序列的延續(xù)可以加強(qiáng)類似性比較效果，所以，對(duì)空值數(shù)據(jù)進(jìn)展線性的平滑處置可以更好地運(yùn)用 LB_Hust 間隔計(jì)算方法。其次，從實(shí)踐意義來看，在空值出現(xiàn)前的階段和空值終了后，兩者股

17、價(jià)普通不同，可見在股價(jià)為空值的階段，實(shí)踐上隱藏著一些影響股價(jià)變動(dòng)的要素發(fā)生著作用，經(jīng)過線性化函數(shù)，將期間出現(xiàn)的變化過程延續(xù)的表達(dá)出來，函數(shù)中的斜率堅(jiān)持了股價(jià)在空值出現(xiàn)階段的趨勢(shì)變動(dòng)變化規(guī)律，經(jīng)過這種填補(bǔ)方法使得股價(jià)動(dòng)搖曲線更延續(xù)和平滑股票數(shù)據(jù)聚類：數(shù)據(jù)的歸一化除了空值問題，股票數(shù)據(jù)另一典型的特點(diǎn)就是不同公司的股價(jià)在數(shù)值上差別很大。股票數(shù)據(jù)聚類：數(shù)據(jù)的歸一化針對(duì)股票數(shù)據(jù)間的股價(jià)差距大的問題，采用歸一化處置，歸一化處置主要處理比較數(shù)據(jù)間量綱不一致的問題，在對(duì)股票進(jìn)展聚類分析中，股票的類似性集中于股價(jià)變化趨勢(shì)的類似性，而非股價(jià)之間的類似性，所以采用以下公式 對(duì)數(shù)據(jù)進(jìn)展歸一化處置。股票數(shù)據(jù)聚類：聚類結(jié)

18、果運(yùn)轉(zhuǎn)層次聚類算法時(shí)初始設(shè)定聚類簇?cái)?shù)為4個(gè)，同時(shí)設(shè)定時(shí)間彎折窗口w為3。股票數(shù)據(jù)聚類：聚類結(jié)果運(yùn)轉(zhuǎn)層次聚類算法時(shí)初始設(shè)定聚類簇?cái)?shù)為4個(gè)，同時(shí)設(shè)定時(shí)間彎折窗口w為3。股票數(shù)據(jù)聚類：聚類結(jié)果運(yùn)轉(zhuǎn)層次聚類算法時(shí)初始設(shè)定聚類簇?cái)?shù)為4個(gè)，同時(shí)設(shè)定時(shí)間彎折窗口w為3。股票數(shù)據(jù)聚類：聚類結(jié)果運(yùn)轉(zhuǎn)層次聚類算法時(shí)初始設(shè)定聚類簇?cái)?shù)為4個(gè)，同時(shí)設(shè)定時(shí)間彎折窗口w為3?；赟AX表示的聚類Hierarchical ClusteringCompute pairwise distance, merge similar clusters bottom-upCompared with Euclidean, IMPACTS,

19、and SDA基于SAX表示的間隔PAA distance lower-bounds the Euclidean Distance 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 = baabccbc C = babcacca QEuclidean Distancedist() can be implemented using a table lookup.Hierarchical ClusteringWe can objectively s

20、tate that SAX is superior, since it correctly assigns each class to its own subtree. 數(shù)據(jù)類別事先知：decreasing trend, upward shift and normal classesClusteringHierarchical ClusteringCompute pairwise distance, merge similar clusters bottom-upCompared with Euclidean, IMPACTS, and SDAPartitional ClusteringK-m

21、eansOptimize the objective function by minimizing the sum of squared intra-cluster errorsCompared with Raw data比層次聚類具有更好的可伸縮性Partitional (K-means) ClusteringWorking with an approximation of the data gives better results than working with the original data. It has been shown that initializing the clu

22、sters centers on a low dimension approximation of the data can improve the quality, this is what clustering with SAX implicitly does.A comparison of the k-means clustering algorithm usingSAX and the raw data. The dataset was Space Shuttle telemetry,1,000 subsequences of length 512. Surprisingly, wor

23、king with thesymbolic approximation produces better results than working with theoriginal data動(dòng)態(tài)時(shí)間序列聚類Time Series Epenthesis: Clustering Time Series Streams Requires Ignoring Some Data動(dòng)態(tài)時(shí)間序列聚類所謂流數(shù)據(jù)，是指按照一定的時(shí)間順序，以較快的速度延續(xù)到達(dá)的數(shù)據(jù)序列，也稱為動(dòng)態(tài)時(shí)間序列。流數(shù)據(jù)聚類的難點(diǎn)在于：數(shù)據(jù)流隨著時(shí)間的推移近似地等效于一個(gè)無限的數(shù)據(jù)集合，因此對(duì)流數(shù)據(jù)的隨機(jī)訪問幾乎是不能夠?qū)崿F(xiàn)的，因此流數(shù)據(jù)聚

24、類通常都要求“一次性掃描數(shù)據(jù)。流數(shù)據(jù)聚類算法首先對(duì)每個(gè)新到達(dá)的數(shù)據(jù)進(jìn)展訪問處置，之后數(shù)據(jù)即被放入隨機(jī)訪問代價(jià)較高的存儲(chǔ)設(shè)備，或者直接被丟棄。流數(shù)據(jù)聚類算法通常會(huì)維護(hù)一個(gè)“概要數(shù)據(jù)構(gòu)造，用來保管數(shù)據(jù)的摘要信息，當(dāng)需求輸出聚類結(jié)果時(shí)，以概要數(shù)據(jù)構(gòu)造中保管的信息作為目的對(duì)象集合，生成所需求的結(jié)果。流數(shù)據(jù)實(shí)例商業(yè)領(lǐng)域中，大型倉儲(chǔ)超市的買賣數(shù)據(jù)。超市的數(shù)據(jù)中心每天收到各個(gè)分店大量的買賣記錄，包括顧客購買物品，消費(fèi)金額等屬性，按照時(shí)間順序陳列。電信行業(yè)中，挪動(dòng)公司可采集到用戶的通話記錄，包括主叫號(hào)碼，被叫號(hào)碼，通話時(shí)間，收費(fèi)金額等假設(shè)干屬性。大量的通話記錄以時(shí)間順序陳列，聚集到挪動(dòng)公司的數(shù)據(jù)中心，也可以被

25、籠統(tǒng)為是一種“流。醫(yī)療行業(yè)中，運(yùn)用生理信號(hào)采集儀器對(duì)患者進(jìn)展監(jiān)控，心跳，脈搏，血壓等一系列生理信號(hào)實(shí)時(shí)地傳送到分析模塊，從中推測(cè)出患者每一時(shí)段的安康情況。工業(yè)消費(fèi)中，一些大型設(shè)備的平安檢測(cè)儀器每時(shí)每刻將設(shè)備的各項(xiàng)運(yùn)轉(zhuǎn)參數(shù)采集出來，作為數(shù)據(jù)信號(hào)進(jìn)展分析處置。流數(shù)據(jù)特點(diǎn)首先，數(shù)據(jù)量非常龐大，這些數(shù)據(jù)隨著時(shí)間的增長數(shù)量急劇上升，如沃爾瑪超市的日買賣次數(shù)可達(dá)數(shù)十萬。其次，這些數(shù)據(jù)均按照時(shí)間順序延續(xù)到達(dá)。另外，數(shù)據(jù)流速很快，以廣東省挪動(dòng)公司的通話記錄為例，頂峰時(shí)間每小時(shí)可達(dá)數(shù)千條。流數(shù)據(jù)聚類問題模型假設(shè)流數(shù)據(jù)由一系列按照時(shí)間順序延續(xù)到達(dá)的數(shù)據(jù)點(diǎn) X1,.,Xi.構(gòu)成，其中，每個(gè)數(shù)據(jù)點(diǎn)擁有 d 個(gè)屬性，用

26、d 維向量的方式來表示：那么流數(shù)據(jù)聚類問題，就是將數(shù)據(jù)流中的某個(gè)特定的子對(duì)象集合X1,X2,.,XN劃分成 k 個(gè)簇區(qū)間(每個(gè)簇用其均值中心點(diǎn)來表示),使目的函數(shù)值:到達(dá)最小。其中Ci是Xi所在簇的中心點(diǎn)，D(Xi,Ci)表示兩個(gè)數(shù)據(jù)點(diǎn)之間的間隔。流數(shù)據(jù)聚類問題模型對(duì)該問題模型，有幾點(diǎn)需求闡明：1)目的集合中數(shù)據(jù)對(duì)象的個(gè)數(shù) N 通常在數(shù)量級(jí)上遠(yuǎn)遠(yuǎn)大于傳統(tǒng)算法中的數(shù)據(jù)集合，通常無法將全部數(shù)據(jù)讀入內(nèi)存進(jìn)展分析，因此難以利用傳統(tǒng)的聚類算法處理這類問題。2)在流數(shù)據(jù)聚類問題中，數(shù)據(jù)通常只能按照它們到達(dá)的順序訪問，以后，數(shù)據(jù)即被存放于外存或丟棄，內(nèi)存中只能保管已訪問數(shù)據(jù)的概要信息。也就是說，流數(shù)據(jù)算法為

27、了防止高昂的系統(tǒng)開銷應(yīng)該盡能夠少地反復(fù)訪問數(shù)據(jù)?，F(xiàn)實(shí)上，“一次掃描數(shù)據(jù)曾經(jīng)成為幾乎一切流數(shù)據(jù)算法都需求實(shí)現(xiàn)的目的。流數(shù)據(jù)聚類問題模型3)流數(shù)據(jù)算法的目的集合是數(shù)據(jù)流中截取的某一個(gè)時(shí)間段(時(shí)間窗)的對(duì)象集合。定義一個(gè)時(shí)間窗需求兩個(gè)重要的輸入?yún)?shù)：起始時(shí)辰 t 和時(shí)間窗口寬度 h，一個(gè)時(shí)間窗口可用 W(t, h)來表示。算法的目的集合即由落入窗口W(t, h)的數(shù)據(jù)對(duì)象組成。4)在流數(shù)據(jù)算法中，任何一個(gè)時(shí)辰的較小的誤差，都有能夠隨著時(shí)間的推移而急速擴(kuò)展，最終呵斥錯(cuò)誤或質(zhì)量較低的算法結(jié)果。因此，在每一個(gè)階段都要將誤差嚴(yán)厲控制在一個(gè)較小的區(qū)間之內(nèi)。5)同時(shí)，算法對(duì)時(shí)間效率的要求非常高，當(dāng)需求在某一個(gè)特

28、定時(shí)辰輸出聚類結(jié)果時(shí)，假設(shè)處置過程的時(shí)間開銷過大，那么有能夠會(huì)呵斥新到數(shù)據(jù)的脫漏或喪失，這種信息缺損隨著數(shù)據(jù)流的不斷進(jìn)展而加劇。早期的流數(shù)據(jù)聚類早期的流數(shù)據(jù)聚類努力將數(shù)據(jù)流的動(dòng)態(tài)特性轉(zhuǎn)化為傳統(tǒng)的靜態(tài)方式，從而可以運(yùn)用成熟的傳統(tǒng)方法處理問題。在這一階段，算法研討的重點(diǎn)是改良傳統(tǒng)算法的性能，使之可以順應(yīng)流數(shù)據(jù)的動(dòng)態(tài)特性。Small-Space 算法正是這類算法的典型代表。Small-Space 算法輸入：按時(shí)間順序到達(dá)的流數(shù)據(jù)序列輸出：k個(gè)聚類中心點(diǎn)算法過程：1) 首先對(duì)初始到達(dá)的 m 個(gè)數(shù)據(jù)點(diǎn)進(jìn)展聚類，得到 O(k)個(gè) 1-級(jí)聚類中心點(diǎn)。2) 反復(fù)上述步驟，當(dāng)處置 m2/ O(k)個(gè)原始數(shù)據(jù)點(diǎn)時(shí)

29、，將得到 m 個(gè)1-級(jí)中心點(diǎn)。3) 對(duì)這 m 個(gè) 1-級(jí)中心點(diǎn)進(jìn)展聚類得到 O(k)個(gè) 2-級(jí)中心點(diǎn)。4) 迭代執(zhí)行上述過程，每次迭代至多保管 m 個(gè) i-級(jí)中心點(diǎn)，否那么進(jìn)展聚類得到 O(k)個(gè)(i+1)-級(jí)中心點(diǎn)。5) 輸出聚類結(jié)果時(shí)，對(duì)當(dāng)前一切中心點(diǎn)進(jìn)展聚類，得到最終的 k個(gè)聚類中心。Small-Space 算法的問題算法需求累積數(shù)據(jù)點(diǎn)，當(dāng)數(shù)據(jù)量到達(dá)一定限制時(shí)進(jìn)展一致處置，而通常處置算法較為復(fù)雜，呵斥了數(shù)據(jù)流在處置節(jié)點(diǎn)上的延遲。另一方面，在累積數(shù)據(jù)點(diǎn)的過程中，算法處于空閑形狀，在一定程度上降低了算法的效率，添加了時(shí)間開銷。雙層流數(shù)據(jù)聚類J. Han 提出雙層構(gòu)造算法 CluStream12雙層聚類算法將處置任務(wù)分為兩個(gè)層面：在線層算法擔(dān)任對(duì)數(shù)據(jù)進(jìn)展粗糙但快速的處置，并擔(dān)任保管中間結(jié)果；離線層算法在中間結(jié)果的根底上進(jìn)展準(zhǔn)確而復(fù)雜的分析，此時(shí)目的集合已成為靜態(tài)集合，因此通常情況下不用思索數(shù)據(jù)流速的影響，并得到最終結(jié)果。CluStream根本思想在線層維護(hù)一系列的“微