時(shí)間序列挖掘聚類

1、時(shí)間序列挖掘聚類目目 錄錄 聚類的概念聚類的概念 聚類算法的評價(jià)標(biāo)準(zhǔn)聚類算法的評價(jià)標(biāo)準(zhǔn) 時(shí)間序列聚類概述時(shí)間序列聚類概述 k-mediods時(shí)間序列聚類時(shí)間序列聚類 基于基于 LB_Hust 距離的時(shí)間序列聚類距離的時(shí)間序列聚類 基于基于SAX表示的聚類表示的聚類聚類的概念聚類的概念 聚類（聚類（Clustering）是數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)重要分支。）是數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)重要分支。所謂聚類，是指將物理或抽象對象的集合分組成為由類似所謂聚類，是指將物理或抽象對象的集合分組成為由類似的對象組成的多個(gè)類的過程的對象組成的多個(gè)類的過程 。 聚類是依據(jù)事物的某些屬性將其聚集成類，使類間相似性聚類是依據(jù)

2、事物的某些屬性將其聚集成類，使類間相似性盡量小，類內(nèi)相似性盡量大。盡量小，類內(nèi)相似性盡量大。 ，的深圳舉辦的新一代信息技術(shù)產(chǎn)業(yè)發(fā)展高峰論壇上，的深圳舉辦的新一代信息技術(shù)產(chǎn)業(yè)發(fā)展高峰論壇上，中國工程院院士李德毅在發(fā)言中指出，盡管目前對于中國工程院院士李德毅在發(fā)言中指出，盡管目前對于大數(shù)據(jù)的認(rèn)知存在挑戰(zhàn)，但聚類將會成為大數(shù)據(jù)認(rèn)知大數(shù)據(jù)的認(rèn)知存在挑戰(zhàn)，但聚類將會成為大數(shù)據(jù)認(rèn)知的突破口。通過大數(shù)據(jù)聚類即時(shí)發(fā)現(xiàn)價(jià)值，要充分認(rèn)的突破口。通過大數(shù)據(jù)聚類即時(shí)發(fā)現(xiàn)價(jià)值，要充分認(rèn)識大數(shù)據(jù)中的不確定性和價(jià)值的隱蔽性。識大數(shù)據(jù)中的不確定性和價(jià)值的隱蔽性。 聚類算法的評價(jià)標(biāo)準(zhǔn)聚類算法的評價(jià)標(biāo)準(zhǔn) 1) 可伸縮性：可伸縮性

3、考察聚類算法對于目標(biāo)對象集可伸縮性：可伸縮性考察聚類算法對于目標(biāo)對象集合的規(guī)模以及目標(biāo)集合潛在的模式數(shù)量的適應(yīng)性。合的規(guī)模以及目標(biāo)集合潛在的模式數(shù)量的適應(yīng)性。 2) 處理不同類型屬性的能力：除了通常處理的數(shù)值型數(shù)據(jù)，處理不同類型屬性的能力：除了通常處理的數(shù)值型數(shù)據(jù)，應(yīng)用當(dāng)中可能要求聚類其它類型的數(shù)據(jù)，如：二元類型，分應(yīng)用當(dāng)中可能要求聚類其它類型的數(shù)據(jù)，如：二元類型，分類類/標(biāo)稱類型，序數(shù)型，時(shí)間序列、圖數(shù)據(jù)或者不同數(shù)據(jù)類標(biāo)稱類型，序數(shù)型，時(shí)間序列、圖數(shù)據(jù)或者不同數(shù)據(jù)類型的混合。型的混合。 3) 發(fā)現(xiàn)任意形狀的聚類：許多聚類算法基于歐幾里德距發(fā)現(xiàn)任意形狀的聚類：許多聚類算法基于歐幾里德距離或者曼

4、哈頓距離度量來決定聚類?；谶@種距離度量離或者曼哈頓距離度量來決定聚類?；谶@種距離度量的算法趨向于發(fā)現(xiàn)具有相近尺度和密度的球狀簇。但是的算法趨向于發(fā)現(xiàn)具有相近尺度和密度的球狀簇。但是一個(gè)簇可能是任意形狀的，提出能發(fā)現(xiàn)任意形狀簇的算一個(gè)簇可能是任意形狀的，提出能發(fā)現(xiàn)任意形狀簇的算法是很重要的。法是很重要的。 4)交互可視化：高維數(shù)據(jù)和復(fù)雜對象常常使可視化變交互可視化：高維數(shù)據(jù)和復(fù)雜對象常常使可視化變得困難，而交互性則使算法與人結(jié)合有利于提高聚類得困難，而交互性則使算法與人結(jié)合有利于提高聚類的質(zhì)量。的質(zhì)量。聚類算法的評價(jià)標(biāo)準(zhǔn)聚類算法的評價(jià)標(biāo)準(zhǔn) 5) 最小化用于決定輸入?yún)?shù)的領(lǐng)域知識和數(shù)據(jù)記錄敏感

5、性：最小化用于決定輸入?yún)?shù)的領(lǐng)域知識和數(shù)據(jù)記錄敏感性：一方面要求降低算法對輸入?yún)?shù)的敏感程度，另一方面要求一方面要求降低算法對輸入?yún)?shù)的敏感程度，另一方面要求輸入記錄順序?qū)λ惴ǖ慕Y(jié)果影響小。要求用戶輸入?yún)?shù)不僅輸入記錄順序?qū)λ惴ǖ慕Y(jié)果影響小。要求用戶輸入?yún)?shù)不僅會加重用戶的負(fù)擔(dān)，也使得聚類的質(zhì)量難以控制。會加重用戶的負(fù)擔(dān)，也使得聚類的質(zhì)量難以控制。 6) 處理噪聲數(shù)據(jù)的能力：絕大多數(shù)現(xiàn)實(shí)世界中的數(shù)據(jù)庫都處理噪聲數(shù)據(jù)的能力：絕大多數(shù)現(xiàn)實(shí)世界中的數(shù)據(jù)庫都包含了孤立點(diǎn)，空缺，未知或者錯(cuò)誤的數(shù)據(jù)。一些聚類算法包含了孤立點(diǎn)，空缺，未知或者錯(cuò)誤的數(shù)據(jù)。一些聚類算法對于這樣的數(shù)據(jù)敏感，導(dǎo)致聚類質(zhì)量對于這樣的

6、數(shù)據(jù)敏感，導(dǎo)致聚類質(zhì)量不高。不高。 7) 高維性：許多聚類算法只擅長處理低維數(shù)據(jù)。在高維高維性：許多聚類算法只擅長處理低維數(shù)據(jù)。在高維空間中聚類數(shù)據(jù)對象是一個(gè)挑戰(zhàn)，特別是空間中聚類數(shù)據(jù)對象是一個(gè)挑戰(zhàn)，特別是在數(shù)據(jù)有可能非在數(shù)據(jù)有可能非常稀疏和偏斜時(shí)。常稀疏和偏斜時(shí)。 8) 可解釋性和可用性：知識發(fā)現(xiàn)過程中，聚類結(jié)果總是可解釋性和可用性：知識發(fā)現(xiàn)過程中，聚類結(jié)果總是需要表現(xiàn)為一定的知識，這就要求聚類結(jié)果可解釋，易理需要表現(xiàn)為一定的知識，這就要求聚類結(jié)果可解釋，易理解。解。時(shí)間序列聚類概述時(shí)間序列聚類概述 時(shí)間序列聚類是時(shí)間序列數(shù)據(jù)挖掘的一個(gè)非?；A(chǔ)且時(shí)間序列聚類是時(shí)間序列數(shù)據(jù)挖掘的一個(gè)非常基礎(chǔ)且

7、非常活躍的研究方向，被廣泛應(yīng)用于包括模式識別、非常活躍的研究方向，被廣泛應(yīng)用于包括模式識別、數(shù)據(jù)分析、圖像處理、市場分析等各個(gè)領(lǐng)域：零售數(shù)數(shù)據(jù)分析、圖像處理、市場分析等各個(gè)領(lǐng)域：零售數(shù)據(jù)的季節(jié)模式聚類、國家能源消耗聚類分析、心電圖據(jù)的季節(jié)模式聚類、國家能源消耗聚類分析、心電圖ECGECG信號聚類分析、股票序列的模式發(fā)現(xiàn)以及個(gè)人收入數(shù)據(jù)信號聚類分析、股票序列的模式發(fā)現(xiàn)以及個(gè)人收入數(shù)據(jù)的聚類等等的聚類等等(Valk and Pinheiro, 2012, Rodrigues et (Valk and Pinheiro, 2012, Rodrigues et al., 2008, Costa San

8、tos et al., 2006, Berkhin, al., 2008, Costa Santos et al., 2006, Berkhin, 2006, Warren Liao2006, Warren Liao，2005, Bagnall and Janacek, 2005, Bagnall and Janacek, 2005)2005)。國內(nèi)外許多研究者提出了很多時(shí)間序列聚類方法，。國內(nèi)外許多研究者提出了很多時(shí)間序列聚類方法，這些方法大致可以分為三種：基于原始序列、基于特征數(shù)這些方法大致可以分為三種：基于原始序列、基于特征數(shù)據(jù)和基于模型參數(shù)據(jù)和基于模型參數(shù)(Warren Liao, 2

9、005)(Warren Liao, 2005)。基于原始序列數(shù)據(jù)的時(shí)間序列聚類基于原始序列數(shù)據(jù)的時(shí)間序列聚類 直接運(yùn)行在原始時(shí)間序列上的聚類稱為基于原始數(shù)據(jù)的聚直接運(yùn)行在原始時(shí)間序列上的聚類稱為基于原始數(shù)據(jù)的聚類類(Zhang et al., 2011, Rodrigues et al., 2008, (Zhang et al., 2011, Rodrigues et al., 2008, Warren Liao, 2005)Warren Liao, 2005)。 但在實(shí)踐中，由于時(shí)間序列的高維特點(diǎn)，會導(dǎo)致大部分的但在實(shí)踐中，由于時(shí)間序列的高維特點(diǎn)，會導(dǎo)致大部分的聚類方法失效，具體表現(xiàn)為：聚類

10、方法失效，具體表現(xiàn)為： (1)(1)時(shí)間序列被看成高維空間中的一個(gè)點(diǎn)，所以數(shù)據(jù)分布會呈現(xiàn)稀疏時(shí)間序列被看成高維空間中的一個(gè)點(diǎn)，所以數(shù)據(jù)分布會呈現(xiàn)稀疏性，從而導(dǎo)致歐氏距離不能正確測度對象間的相似程度性，從而導(dǎo)致歐氏距離不能正確測度對象間的相似程度(Wang et (Wang et al., 2005, Domeniconi et al., 2004)al., 2005, Domeniconi et al., 2004)； (2)(2)多數(shù)算法的性能受參數(shù)設(shè)置的影響，在缺乏背景知識時(shí)，用多數(shù)算法的性能受參數(shù)設(shè)置的影響，在缺乏背景知識時(shí)，用戶可以根據(jù)反饋的算法結(jié)果精調(diào)參數(shù)，但高維數(shù)據(jù)造成聚類結(jié)戶可以

11、根據(jù)反饋的算法結(jié)果精調(diào)參數(shù)，但高維數(shù)據(jù)造成聚類結(jié)果無法可視化，使得用戶很難判斷聚類結(jié)果的質(zhì)量，所以很難果無法可視化，使得用戶很難判斷聚類結(jié)果的質(zhì)量，所以很難合理設(shè)置參數(shù)（合理設(shè)置參數(shù)（Jain, 2010, Chen, 2007, Lin et al., 2004Jain, 2010, Chen, 2007, Lin et al., 2004，Ding and He, 2004)Ding and He, 2004)?；谔卣鲾?shù)據(jù)的時(shí)間序列聚類基于特征數(shù)據(jù)的時(shí)間序列聚類 基于特征的表示方法是把原始時(shí)間序列轉(zhuǎn)換到一個(gè)低維基于特征的表示方法是把原始時(shí)間序列轉(zhuǎn)換到一個(gè)低維的特征空間，然后用傳統(tǒng)的聚類方

12、法對特征向量進(jìn)行聚的特征空間，然后用傳統(tǒng)的聚類方法對特征向量進(jìn)行聚類類(Yang et al., 2009, Xiaozhe et al., 2007,Keogh et (Yang et al., 2009, Xiaozhe et al., 2007,Keogh et al., 2007, Chen, 2007, Zhang et al., 2006, Wang et al., 2007, Chen, 2007, Zhang et al., 2006, Wang et al., 2006al., 2006，Costa Santos et al., 2006Costa Santos et al.

13、, 2006，Wang et Wang et al., 2005al., 2005，Bagnall and Janacek, 2005Bagnall and Janacek, 2005，Domeniconi et al., 2004)Domeniconi et al., 2004)。 由于基于特征的聚類方法中提取的特征來自序列本身，且具由于基于特征的聚類方法中提取的特征來自序列本身，且具有特定的含義，所以該聚類方法不僅實(shí)現(xiàn)對序列的降維，又有特定的含義，所以該聚類方法不僅實(shí)現(xiàn)對序列的降維，又使得聚類結(jié)果具有可解釋性。這里，常用的傳統(tǒng)的聚類算法使得聚類結(jié)果具有可解釋性。這里，常用的傳統(tǒng)的聚類算法有

14、如下幾種：劃分聚類、層次聚類和密度聚類等等有如下幾種：劃分聚類、層次聚類和密度聚類等等(Jain, (Jain, 20102010，Chawla and Gionis, 2013, Rodrigues et al., Chawla and Gionis, 2013, Rodrigues et al., 20082008，Labini, 2008, Schikuta, 1996, Kriegel et al., Labini, 2008, Schikuta, 1996, Kriegel et al., 2011)2011)。基于模型的時(shí)間序列聚類基于模型的時(shí)間序列聚類 基于模型的聚類的基本思想是

15、把原始時(shí)間序列轉(zhuǎn)換成?；谀Ｐ偷木垲惖幕舅枷胧前言紩r(shí)間序列轉(zhuǎn)換成模型的幾個(gè)參數(shù)，比如型的幾個(gè)參數(shù)，比如ARAR模型或模型或HMMHMM模型等，然后用模型參模型等，然后用模型參數(shù)進(jìn)行聚類數(shù)進(jìn)行聚類(Jie and Qiang, 2005(Jie and Qiang, 2005，Camastra and Verri, Camastra and Verri, 2005, Xiong and Yeung, 2004, Panuccio et al., 2005, Xiong and Yeung, 2004, Panuccio et al., 2002)2002)。這種方法的不足之處在于需要對數(shù)據(jù)的

16、分布。這種方法的不足之處在于需要對數(shù)據(jù)的分布進(jìn)行預(yù)先假設(shè)，此外，對參數(shù)的聚類結(jié)果無法進(jìn)行解進(jìn)行預(yù)先假設(shè)，此外，對參數(shù)的聚類結(jié)果無法進(jìn)行解釋，使得聚類缺乏可理解性。釋，使得聚類缺乏可理解性。小小 結(jié)結(jié) 現(xiàn)有時(shí)間序列聚類方法大致可分成：基于現(xiàn)有時(shí)間序列聚類方法大致可分成：基于原始序列、基于特征值和基于模型參數(shù)三原始序列、基于特征值和基于模型參數(shù)三種。種。 基于原始序列的聚類方法由于基于原始序列的聚類方法由于“維災(zāi)難維災(zāi)難”很難產(chǎn)生較好的聚類效果，而基于模型參很難產(chǎn)生較好的聚類效果，而基于模型參數(shù)的方法由于需要對數(shù)據(jù)做預(yù)先假設(shè)也使數(shù)的方法由于需要對數(shù)據(jù)做預(yù)先假設(shè)也使得應(yīng)用受到限制，基于特征值的聚類方

17、法得應(yīng)用受到限制，基于特征值的聚類方法是最有前景的時(shí)間序列聚類算法。是最有前景的時(shí)間序列聚類算法。靜態(tài)時(shí)間序列聚類靜態(tài)時(shí)間序列聚類 k-medoids時(shí)間序列聚類時(shí)間序列聚類 基于基于 LB_Hust 距離的時(shí)間序列數(shù)據(jù)聚類距離的時(shí)間序列數(shù)據(jù)聚類 基于基于SAX表示的聚類表示的聚類k-mediods時(shí)間序列聚類時(shí)間序列聚類1、k-中心點(diǎn)聚類基本原理：中心點(diǎn)聚類基本原理：k-均值的缺點(diǎn)：對離群點(diǎn)敏感均值的缺點(diǎn)：對離群點(diǎn)敏感k-中心點(diǎn)：挑選實(shí)際對象來代表簇，每個(gè)中心點(diǎn)：挑選實(shí)際對象來代表簇，每個(gè)簇使用一個(gè)代表對象。簇使用一個(gè)代表對象。實(shí)現(xiàn)：圍繞中心點(diǎn)劃分（實(shí)現(xiàn)：圍繞中心點(diǎn)劃分（Partitioni

18、ng Around Medoids, PAM)算法算法算法算法:k-中心點(diǎn)。中心點(diǎn)。PAM輸入：輸入： k：結(jié)果簇的個(gè)數(shù)：結(jié)果簇的個(gè)數(shù) D：包含：包含n個(gè)對象的數(shù)據(jù)集合個(gè)對象的數(shù)據(jù)集合輸出：輸出： k個(gè)簇的集合個(gè)簇的集合k-mediods時(shí)間序列聚類時(shí)間序列聚類方法：方法： （1）從）從D中隨機(jī)選擇中隨機(jī)選擇k個(gè)對象作為初始的代表對象或種子個(gè)對象作為初始的代表對象或種子 （2）repeat （3）將每個(gè)剩余的對象分配到最近的代表對象所代表的簇）將每個(gè)剩余的對象分配到最近的代表對象所代表的簇 （4）隨機(jī)地選擇一個(gè)非代表對象）隨機(jī)地選擇一個(gè)非代表對象Orandom （5）計(jì)算用）計(jì)算用Orando

19、m代替代表對象代替代表對象Oj的總代價(jià)的總代價(jià)S（代價(jià)函數(shù)就是計(jì)（代價(jià)函數(shù)就是計(jì)算絕對誤差值的差）算絕對誤差值的差） （6）if S U.* Q-U; Q L.* L-Q.2); LB_Hust 距離距離-對對LB_Keogh距離的改進(jìn)距離的改進(jìn) 針對針對 LB_KeoghLB_Keogh距離計(jì)算的非對稱性距離計(jì)算的非對稱性 其中，其中，Lxi和和 Uxi分別對應(yīng)時(shí)間序列分別對應(yīng)時(shí)間序列 X 的第的第 i 個(gè)元素在個(gè)元素在 2w 時(shí)間域內(nèi)的最小值和最大值。時(shí)間域內(nèi)的最小值和最大值。Lyi和和 Uyi同理。距離產(chǎn)生方同理。距離產(chǎn)生方式如圖式如圖 3-5 所示。所示。 定理：對于長度為定理：對于長

20、度為 n 的任何兩個(gè)時(shí)間序列的任何兩個(gè)時(shí)間序列 X 和和 Y，限定彎曲路徑窗口為限定彎曲路徑窗口為w，即對于，即對于 xi和和 yj點(diǎn)的比較，限點(diǎn)的比較，限定為定為 j-w i j+w，存在如下不等式：，存在如下不等式： LB_ Hust(X,Y) Keogh(X,Y) 。 性質(zhì)性質(zhì)1：LB_Hust 距離是對稱的。即距離是對稱的。即 LB_Hust (X,Y) =LB_Hust (Y,X)。這可以減少距離計(jì)算的次數(shù)。這可以減少距離計(jì)算的次數(shù)。 性質(zhì)性質(zhì)2：在：在 LB_Hust 距離計(jì)算方式下，時(shí)間復(fù)雜度由距離計(jì)算方式下，時(shí)間復(fù)雜度由傳統(tǒng)的傳統(tǒng)的 DTW 距離計(jì)算的距離計(jì)算的 O(nm)縮減

21、到縮減到 O(n)?；诨?LB_Hust 距離的時(shí)間序列聚類距離的時(shí)間序列聚類 算法流程：算法流程： 1) 初始狀態(tài)下所有有時(shí)間序列數(shù)據(jù)自成一簇，每條時(shí)間序列初始狀態(tài)下所有有時(shí)間序列數(shù)據(jù)自成一簇，每條時(shí)間序列數(shù)據(jù)為各自的簇中心，循環(huán)數(shù)據(jù)為各自的簇中心，循環(huán) 2）到）到 4）。）。 2) 根據(jù)時(shí)間序列數(shù)據(jù)上下界曲線形成方法求取當(dāng)前簇中心的上下根據(jù)時(shí)間序列數(shù)據(jù)上下界曲線形成方法求取當(dāng)前簇中心的上下界序列界序列 Us和和 Ls。 3) 計(jì)算兩兩簇之間的距離，記錄具有最小距離的兩個(gè)簇，將計(jì)算兩兩簇之間的距離，記錄具有最小距離的兩個(gè)簇，將兩個(gè)簇歸并，根據(jù)歸并算法更新聚類中心。兩個(gè)簇歸并，根據(jù)歸并算法

22、更新聚類中心。 4) 若當(dāng)前聚類簇?cái)?shù)達(dá)到若當(dāng)前聚類簇?cái)?shù)達(dá)到 K，則終止，否則轉(zhuǎn)到，則終止，否則轉(zhuǎn)到 2)。 分析上述算法，存在的兩個(gè)關(guān)鍵的函數(shù)是計(jì)算兩個(gè)序列的分析上述算法，存在的兩個(gè)關(guān)鍵的函數(shù)是計(jì)算兩個(gè)序列的 LB_Hust 距離和求取新的簇中心兩個(gè)函數(shù)。距離和求取新的簇中心兩個(gè)函數(shù)?；诨?LB_Hust 距離矩陣的層次聚類距離矩陣的層次聚類 基于距離矩陣的層次聚類算法是以犧牲空間換取時(shí)間的算法，存基于距離矩陣的層次聚類算法是以犧牲空間換取時(shí)間的算法，存放放 n 條記錄兩兩之間的距離，在距離函數(shù)計(jì)算具有對稱性的情況條記錄兩兩之間的距離，在距離函數(shù)計(jì)算具有對稱性的情況下，實(shí)際的矩陣只需存放上

23、三角或下三角下，實(shí)際的矩陣只需存放上三角或下三角 n*(n+1)/2 個(gè)數(shù)據(jù)。個(gè)數(shù)據(jù)。這也是應(yīng)用這也是應(yīng)用 LB_Hust 距離計(jì)算函數(shù)的一個(gè)重要原因。距離計(jì)算函數(shù)的一個(gè)重要原因。 輸入：時(shí)間序列數(shù)據(jù)庫：輸入：時(shí)間序列數(shù)據(jù)庫：TSDB； 允許的彎曲路徑時(shí)間窗：允許的彎曲路徑時(shí)間窗：w； 最大的簇?cái)?shù)：最大的簇?cái)?shù)：K； 輸出：輸出：K 個(gè)簇：個(gè)簇：C1， C2、，、， CK；基于基于 LB_Hust 距離矩陣的層次聚類距離矩陣的層次聚類算法流程：算法流程： 1) 初始狀態(tài)下所有時(shí)間序列數(shù)據(jù)自成一簇，每條時(shí)間序列數(shù)據(jù)為各初始狀態(tài)下所有時(shí)間序列數(shù)據(jù)自成一簇，每條時(shí)間序列數(shù)據(jù)為各自的簇中心，初始化距離矩

24、陣，計(jì)算任意兩條時(shí)間序列數(shù)據(jù)間的距自的簇中心，初始化距離矩陣，計(jì)算任意兩條時(shí)間序列數(shù)據(jù)間的距離，循環(huán)離，循環(huán) 2）到）到 5）。）。 2) 找到距離矩陣中的最小距離對應(yīng)的兩個(gè)簇，合并，形成新的簇找到距離矩陣中的最小距離對應(yīng)的兩個(gè)簇，合并，形成新的簇中心。中心。3) 根據(jù)時(shí)間序列數(shù)據(jù)上下界曲線形成方法求取當(dāng)前簇中心的上下根據(jù)時(shí)間序列數(shù)據(jù)上下界曲線形成方法求取當(dāng)前簇中心的上下界索引序列界索引序列 Us、Ls。4) 重新計(jì)算當(dāng)前簇中心和其余簇的距離，更新距離矩陣。重新計(jì)算當(dāng)前簇中心和其余簇的距離，更新距離矩陣。 5) 若當(dāng)前聚類簇?cái)?shù)達(dá)到若當(dāng)前聚類簇?cái)?shù)達(dá)到 K，則終止，否則轉(zhuǎn)到，則終止，否則轉(zhuǎn)到 2)

25、。 對于上述采用距離矩陣的層次聚類，相比前面算法，每一層合對于上述采用距離矩陣的層次聚類，相比前面算法，每一層合并時(shí)，距離計(jì)算次數(shù)為并時(shí)，距離計(jì)算次數(shù)為c(n,2)次，其中次，其中 n 表示當(dāng)前層中的簇?cái)?shù)，時(shí)表示當(dāng)前層中的簇?cái)?shù)，時(shí)間復(fù)雜度為間復(fù)雜度為 o(n2)，采用距離矩陣方法則每次僅需計(jì)算，采用距離矩陣方法則每次僅需計(jì)算 n 次距離。次距離。應(yīng)用應(yīng)用-股票數(shù)據(jù)聚類股票數(shù)據(jù)聚類 股票數(shù)據(jù)作為典型的時(shí)間序列數(shù)據(jù)，被眾多時(shí)間序列挖掘股票數(shù)據(jù)作為典型的時(shí)間序列數(shù)據(jù)，被眾多時(shí)間序列挖掘方法作為實(shí)驗(yàn)性數(shù)據(jù)。典型的股票行情原始數(shù)據(jù)包括股票方法作為實(shí)驗(yàn)性數(shù)據(jù)。典型的股票行情原始數(shù)據(jù)包括股票的開盤價(jià)、最高價(jià)

26、、最低價(jià)、收盤價(jià)、成交量、成交金額的開盤價(jià)、最高價(jià)、最低價(jià)、收盤價(jià)、成交量、成交金額等，所有屬性的值對應(yīng)著一個(gè)特定時(shí)刻，在固定時(shí)間段內(nèi)等，所有屬性的值對應(yīng)著一個(gè)特定時(shí)刻，在固定時(shí)間段內(nèi)形成了典型的時(shí)間序列數(shù)據(jù)。形成了典型的時(shí)間序列數(shù)據(jù)。 對于多支股票的聚類是從控股公司間的經(jīng)營狀況、經(jīng)營手對于多支股票的聚類是從控股公司間的經(jīng)營狀況、經(jīng)營手段及外界影響因素的相似程度進(jìn)行聚類。通過對多支股票段及外界影響因素的相似程度進(jìn)行聚類。通過對多支股票的聚類，可以發(fā)現(xiàn)股票運(yùn)動(dòng)規(guī)律相似的企業(yè)，對中長期股的聚類，可以發(fā)現(xiàn)股票運(yùn)動(dòng)規(guī)律相似的企業(yè)，對中長期股票投資者選股提供一些參考。票投資者選股提供一些參考。股票數(shù)據(jù)聚

27、類：數(shù)據(jù)準(zhǔn)備股票數(shù)據(jù)聚類：數(shù)據(jù)準(zhǔn)備 采用搜狐財(cái)經(jīng)網(wǎng)采用搜狐財(cái)經(jīng)網(wǎng)( :/q.stock.sohu /)( :/q.stock.sohu /)的股票歷史行情的股票歷史行情數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，從中選擇數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，從中選擇 29 29 支股票作為實(shí)驗(yàn)數(shù)據(jù)：支股票作為實(shí)驗(yàn)數(shù)據(jù)：寶鋼股份、包鋼股份、上海電力、招商輪船、中國石油寶鋼股份、包鋼股份、上海電力、招商輪船、中國石油 、中國銀行、中海油服、武鋼股份、東湖高新、萬東醫(yī)療、中國銀行、中海油服、武鋼股份、東湖高新、萬東醫(yī)療、林海股份、中視傳媒等。在數(shù)據(jù)庫中，存儲股票的名稱采林海股份、中視傳媒等。在數(shù)據(jù)庫中，存儲股票的名稱采用字母代號表示，將用字母代

28、號表示，將 29 29 支股票對應(yīng)到支股票對應(yīng)到 AA3 AA3 的的 29 29 個(gè)字個(gè)字母串。母串。 抽取從抽取從 2010 2010年年3 3月份到月份到20102010年五月份的股票歷史行年五月份的股票歷史行情數(shù)據(jù)，將其中的每日收盤價(jià)作為實(shí)驗(yàn)數(shù)據(jù)。在提情數(shù)據(jù)，將其中的每日收盤價(jià)作為實(shí)驗(yàn)數(shù)據(jù)。在提取的數(shù)據(jù)中發(fā)現(xiàn)，股票數(shù)據(jù)存在如下兩個(gè)特點(diǎn)：一、取的數(shù)據(jù)中發(fā)現(xiàn)，股票數(shù)據(jù)存在如下兩個(gè)特點(diǎn)：一、由于股市的休市，股票數(shù)據(jù)存在空值；二、股票之由于股市的休市，股票數(shù)據(jù)存在空值；二、股票之間的收盤價(jià)存在很大差異。間的收盤價(jià)存在很大差異。股票數(shù)據(jù)聚類：數(shù)據(jù)準(zhǔn)備股票數(shù)據(jù)聚類：數(shù)據(jù)準(zhǔn)備 股票數(shù)據(jù)普遍存在空值，

29、主要是基于兩種情況：一、正常股票數(shù)據(jù)普遍存在空值，主要是基于兩種情況：一、正常的股市休市。二、個(gè)別控股公司由于內(nèi)部整合或者公司內(nèi)的股市休市。二、個(gè)別控股公司由于內(nèi)部整合或者公司內(nèi)部事件出現(xiàn)停開。部事件出現(xiàn)停開。 每支股票數(shù)據(jù)在休市時(shí)都是空值，因此可采用直接刪除每支股票數(shù)據(jù)在休市時(shí)都是空值，因此可采用直接刪除的方法不會影響到時(shí)間序列的時(shí)間對等性。的方法不會影響到時(shí)間序列的時(shí)間對等性。 針對公司內(nèi)部事件引起的空值采取填補(bǔ)處理。填補(bǔ)數(shù)據(jù)針對公司內(nèi)部事件引起的空值采取填補(bǔ)處理。填補(bǔ)數(shù)據(jù)根據(jù)線性化函數(shù)取得，對每個(gè)空值，以空值上下非空數(shù)根據(jù)線性化函數(shù)取得，對每個(gè)空值，以空值上下非空數(shù)據(jù)為端點(diǎn)得到一次線性化

30、函數(shù)，通過線性化函數(shù)可以取據(jù)為端點(diǎn)得到一次線性化函數(shù)，通過線性化函數(shù)可以取得空值對應(yīng)時(shí)間點(diǎn)的股價(jià)。得空值對應(yīng)時(shí)間點(diǎn)的股價(jià)。股票數(shù)據(jù)聚類：數(shù)據(jù)準(zhǔn)備股票數(shù)據(jù)聚類：數(shù)據(jù)準(zhǔn)備 采用線性化函數(shù)進(jìn)行填補(bǔ)處理是基于兩點(diǎn)考慮：采用線性化函數(shù)進(jìn)行填補(bǔ)處理是基于兩點(diǎn)考慮： 首先，基于對首先，基于對 LB_Hust LB_Hust 距離計(jì)算的過程，對于時(shí)間距離計(jì)算的過程，對于時(shí)間序列曲線，趨勢的變動(dòng)和時(shí)間序列的連續(xù)能夠增強(qiáng)相序列曲線，趨勢的變動(dòng)和時(shí)間序列的連續(xù)能夠增強(qiáng)相似性比較效果，所以，對空值數(shù)據(jù)進(jìn)行線性的平滑處似性比較效果，所以，對空值數(shù)據(jù)進(jìn)行線性的平滑處理可以更好地應(yīng)用理可以更好地應(yīng)用 LB_Hust LB_

31、Hust 距離計(jì)算方法。距離計(jì)算方法。 其次，從實(shí)際意義來看，在空值出現(xiàn)前的階段和空值結(jié)束其次，從實(shí)際意義來看，在空值出現(xiàn)前的階段和空值結(jié)束后，兩者股價(jià)一般不同，可見在股價(jià)為空值的階段，實(shí)際后，兩者股價(jià)一般不同，可見在股價(jià)為空值的階段，實(shí)際上隱藏著一些影響股價(jià)變動(dòng)的因素發(fā)生著作用，通過線性上隱藏著一些影響股價(jià)變動(dòng)的因素發(fā)生著作用，通過線性化函數(shù)，將期間出現(xiàn)的變化過程連續(xù)的表達(dá)出來，函數(shù)中化函數(shù)，將期間出現(xiàn)的變化過程連續(xù)的表達(dá)出來，函數(shù)中的斜率保持了股價(jià)在空值出現(xiàn)階段的趨勢變動(dòng)變化規(guī)律，的斜率保持了股價(jià)在空值出現(xiàn)階段的趨勢變動(dòng)變化規(guī)律，通過這種填補(bǔ)方法使得股價(jià)波動(dòng)曲線更連續(xù)和平滑通過這種填補(bǔ)方法

32、使得股價(jià)波動(dòng)曲線更連續(xù)和平滑股票數(shù)據(jù)聚類：數(shù)據(jù)的歸一化股票數(shù)據(jù)聚類：數(shù)據(jù)的歸一化 除了空值問題，股票數(shù)據(jù)另一典型的特點(diǎn)就是不同除了空值問題，股票數(shù)據(jù)另一典型的特點(diǎn)就是不同公司的股價(jià)在數(shù)值上差異很大。公司的股價(jià)在數(shù)值上差異很大。股票數(shù)據(jù)聚類：數(shù)據(jù)的歸一化股票數(shù)據(jù)聚類：數(shù)據(jù)的歸一化 針對股票數(shù)據(jù)間的股價(jià)差距大的問題，采用歸一針對股票數(shù)據(jù)間的股價(jià)差距大的問題，采用歸一化處理，歸一化處理主要解決比較數(shù)據(jù)間量綱不化處理，歸一化處理主要解決比較數(shù)據(jù)間量綱不統(tǒng)一的問題，在對股票進(jìn)行聚類分析中，股票的統(tǒng)一的問題，在對股票進(jìn)行聚類分析中，股票的相似性集中于股價(jià)變化趨勢的相似性，而非股價(jià)相似性集中于股價(jià)變化趨勢的

33、相似性，而非股價(jià)之間的相似性，所以采用以下公式之間的相似性，所以采用以下公式 對數(shù)據(jù)進(jìn)行歸對數(shù)據(jù)進(jìn)行歸一化處理。一化處理。minmaxminiixxxxx股票數(shù)據(jù)聚類：聚類結(jié)果股票數(shù)據(jù)聚類：聚類結(jié)果 運(yùn)行層次聚類算法時(shí)初始設(shè)定聚類簇?cái)?shù)為運(yùn)行層次聚類算法時(shí)初始設(shè)定聚類簇?cái)?shù)為4個(gè)，同個(gè)，同時(shí)設(shè)定時(shí)間彎折窗口時(shí)設(shè)定時(shí)間彎折窗口w為為3。股票數(shù)據(jù)聚類：聚類結(jié)果股票數(shù)據(jù)聚類：聚類結(jié)果 運(yùn)行層次聚類算法時(shí)初始設(shè)定聚類簇?cái)?shù)為運(yùn)行層次聚類算法時(shí)初始設(shè)定聚類簇?cái)?shù)為4個(gè)，同個(gè)，同時(shí)設(shè)定時(shí)間彎折窗口時(shí)設(shè)定時(shí)間彎折窗口w為為3。股票數(shù)據(jù)聚類：聚類結(jié)果股票數(shù)據(jù)聚類：聚類結(jié)果 運(yùn)行層次聚類算法時(shí)初始設(shè)定聚類簇?cái)?shù)為運(yùn)行層次

34、聚類算法時(shí)初始設(shè)定聚類簇?cái)?shù)為4個(gè)，同個(gè)，同時(shí)設(shè)定時(shí)間彎折窗口時(shí)設(shè)定時(shí)間彎折窗口w為為3。股票數(shù)據(jù)聚類：聚類結(jié)果股票數(shù)據(jù)聚類：聚類結(jié)果 運(yùn)行層次聚類算法時(shí)初始設(shè)定聚類簇?cái)?shù)為運(yùn)行層次聚類算法時(shí)初始設(shè)定聚類簇?cái)?shù)為4個(gè)，同個(gè)，同時(shí)設(shè)定時(shí)間彎折窗口時(shí)設(shè)定時(shí)間彎折窗口w為為3?；诨赟AX表示的聚類表示的聚類 Hierarchical Clustering Compute pairwise distance, merge similar clusters bottom-up Compared with Euclidean, IMPACTS, and SDA 基于基于SAX表示的距離表示的距離PAA di

35、stance 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 QniiicqCQD12,Euclidean DistancewiiiwncqCQDR12),(wiiiwncqdistCQMINDIST12) ,(),(dist() can be implemented using a table lookup.Hierarc

36、hical ClusteringWe can objectively state that SAX is superior, since it correctly assigns each class to its own subtree. 數(shù)據(jù)類別事先已知：數(shù)據(jù)類別事先已知：decreasing trend, upward shift and normal classesClustering Hierarchical Clustering Compute pairwise distance, merge similar clusters bottom-up Compared with Euc

37、lidean, IMPACTS, and SDA Partitional Clustering K-means Optimize the objective function by minimizing the sum of squared intra-cluster errors Compared with Raw data 比層次聚類具有更好的可伸縮性比層次聚類具有更好的可伸縮性Partitional (K-means) ClusteringWorking with an approximation of the data gives better results than working

38、 with the original data. It has been shown that initializing the clusters 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 S

39、huttle telemetry,1,000 subsequences of length 512. Surprisingly, working with thesymbolic approximation produces better results than working with theoriginal data動(dòng)態(tài)時(shí)間序列聚類動(dòng)態(tài)時(shí)間序列聚類 Time Series Epenthesis: Clustering Time Series Streams Requires Ignoring Some Data動(dòng)態(tài)時(shí)間序列聚類動(dòng)態(tài)時(shí)間序列聚類 所謂流數(shù)據(jù)，是指按照一定的時(shí)間順序，以較快的

40、速度連續(xù)到所謂流數(shù)據(jù)，是指按照一定的時(shí)間順序，以較快的速度連續(xù)到達(dá)的數(shù)據(jù)序列，也稱為動(dòng)態(tài)時(shí)間序列。達(dá)的數(shù)據(jù)序列，也稱為動(dòng)態(tài)時(shí)間序列。 流數(shù)據(jù)聚類的難點(diǎn)在于：數(shù)據(jù)流隨著時(shí)間的推移近似地流數(shù)據(jù)聚類的難點(diǎn)在于：數(shù)據(jù)流隨著時(shí)間的推移近似地等效于一個(gè)無限的數(shù)據(jù)集合，因此對流數(shù)據(jù)的隨機(jī)訪問等效于一個(gè)無限的數(shù)據(jù)集合，因此對流數(shù)據(jù)的隨機(jī)訪問幾乎是不可能實(shí)現(xiàn)的，因此流數(shù)據(jù)聚類通常都要求幾乎是不可能實(shí)現(xiàn)的，因此流數(shù)據(jù)聚類通常都要求“一一次性掃描數(shù)據(jù)次性掃描數(shù)據(jù)”。流數(shù)據(jù)聚類算法首先對每個(gè)新到達(dá)的。流數(shù)據(jù)聚類算法首先對每個(gè)新到達(dá)的數(shù)據(jù)進(jìn)行訪問處理，之后數(shù)據(jù)即被放入隨機(jī)訪問代價(jià)較數(shù)據(jù)進(jìn)行訪問處理，之后數(shù)據(jù)即被放入隨機(jī)

41、訪問代價(jià)較高的存儲設(shè)備，或者直接被丟棄。高的存儲設(shè)備，或者直接被丟棄。 流數(shù)據(jù)聚類算法通常會維護(hù)一個(gè)流數(shù)據(jù)聚類算法通常會維護(hù)一個(gè)“概要數(shù)據(jù)結(jié)構(gòu)概要數(shù)據(jù)結(jié)構(gòu)”，用來保，用來保存數(shù)據(jù)的摘要信息，當(dāng)需要輸出聚類結(jié)果時(shí)，以概要數(shù)據(jù)結(jié)存數(shù)據(jù)的摘要信息，當(dāng)需要輸出聚類結(jié)果時(shí)，以概要數(shù)據(jù)結(jié)構(gòu)中保存的信息作為目標(biāo)對象集合，生成所需要的結(jié)果。構(gòu)中保存的信息作為目標(biāo)對象集合，生成所需要的結(jié)果。流數(shù)據(jù)實(shí)例流數(shù)據(jù)實(shí)例 商業(yè)領(lǐng)域中，大型倉儲超市的交易數(shù)據(jù)。超市的數(shù)據(jù)中商業(yè)領(lǐng)域中，大型倉儲超市的交易數(shù)據(jù)。超市的數(shù)據(jù)中心每天收到各個(gè)分店大量的交易記錄，包括顧客購買物心每天收到各個(gè)分店大量的交易記錄，包括顧客購買物品，消費(fèi)金

42、額等屬性，按照時(shí)間順序排列。品，消費(fèi)金額等屬性，按照時(shí)間順序排列。 電信行業(yè)中，移動(dòng)公司可采集到用戶的通話記錄，包括主叫電信行業(yè)中，移動(dòng)公司可采集到用戶的通話記錄，包括主叫號碼，被叫號碼，通話時(shí)間，收費(fèi)金額等若干屬性。大量的號碼，被叫號碼，通話時(shí)間，收費(fèi)金額等若干屬性。大量的通話記錄以時(shí)間順序排列，匯集到移動(dòng)公司的數(shù)據(jù)中心，也通話記錄以時(shí)間順序排列，匯集到移動(dòng)公司的數(shù)據(jù)中心，也可以被抽象為是一種可以被抽象為是一種“流流”。 醫(yī)療行業(yè)中，使用生理信號采集儀器對患者進(jìn)行監(jiān)控，心跳醫(yī)療行業(yè)中，使用生理信號采集儀器對患者進(jìn)行監(jiān)控，心跳，脈搏，血壓等一系列生理信號實(shí)時(shí)地傳送到分析模塊，從，脈搏，血壓等一

43、系列生理信號實(shí)時(shí)地傳送到分析模塊，從中推測出患者每一時(shí)段的健康狀況。中推測出患者每一時(shí)段的健康狀況。 工業(yè)生產(chǎn)中，一些大型設(shè)備的安全檢測儀器每時(shí)每刻將設(shè)備的工業(yè)生產(chǎn)中，一些大型設(shè)備的安全檢測儀器每時(shí)每刻將設(shè)備的各項(xiàng)運(yùn)轉(zhuǎn)參數(shù)采集出來，作為數(shù)據(jù)信號進(jìn)行分析處理。各項(xiàng)運(yùn)轉(zhuǎn)參數(shù)采集出來，作為數(shù)據(jù)信號進(jìn)行分析處理。流數(shù)據(jù)特點(diǎn)流數(shù)據(jù)特點(diǎn) 首先，數(shù)據(jù)量十分龐大，這些首先，數(shù)據(jù)量十分龐大，這些數(shù)據(jù)隨著時(shí)間的增長數(shù)量急劇數(shù)據(jù)隨著時(shí)間的增長數(shù)量急劇上升，如沃爾瑪超市的日交易上升，如沃爾瑪超市的日交易次數(shù)可達(dá)數(shù)十萬。次數(shù)可達(dá)數(shù)十萬。 其次，這些數(shù)據(jù)均按照時(shí)間順序其次，這些數(shù)據(jù)均按照時(shí)間順序連續(xù)到達(dá)。連續(xù)到達(dá)。 另外

44、，數(shù)據(jù)流速很快，以廣另外，數(shù)據(jù)流速很快，以廣東省移動(dòng)公司的通話記錄為東省移動(dòng)公司的通話記錄為例，高峰時(shí)間每小時(shí)可達(dá)數(shù)例，高峰時(shí)間每小時(shí)可達(dá)數(shù)千條。千條。流數(shù)據(jù)聚類問題模型流數(shù)據(jù)聚類問題模型 假設(shè)流數(shù)據(jù)由一系列按照時(shí)間順序連續(xù)到達(dá)的數(shù)據(jù)點(diǎn)假設(shè)流數(shù)據(jù)由一系列按照時(shí)間順序連續(xù)到達(dá)的數(shù)據(jù)點(diǎn) X X1 1,.,X,.,Xi i.構(gòu)成，其中，每個(gè)數(shù)據(jù)點(diǎn)擁有構(gòu)成，其中，每個(gè)數(shù)據(jù)點(diǎn)擁有 d d 個(gè)屬個(gè)屬性，用性，用d d 維向量的形式來表示：維向量的形式來表示： 那么流數(shù)據(jù)聚類問題，就是將數(shù)據(jù)流中的某個(gè)特定的那么流數(shù)據(jù)聚類問題，就是將數(shù)據(jù)流中的某個(gè)特定的子對象集合子對象集合XX1 1,X,X2 2,.,X,.

45、,XN N 劃分成劃分成 k k 個(gè)簇區(qū)間個(gè)簇區(qū)間( (每個(gè)每個(gè)簇用其均值中心點(diǎn)來表示簇用其均值中心點(diǎn)來表示),),使目標(biāo)函數(shù)值使目標(biāo)函數(shù)值: : 達(dá)到最小。其中達(dá)到最小。其中C Ci i是是X Xi i所在簇的中心點(diǎn)，所在簇的中心點(diǎn)，D(XD(Xi i,C,Ci i) )表表示兩個(gè)數(shù)據(jù)點(diǎn)之間的距離。示兩個(gè)數(shù)據(jù)點(diǎn)之間的距離。12X(,.,)diiiixxx21(,)NiiiDXC流數(shù)據(jù)聚類問題模型流數(shù)據(jù)聚類問題模型 對該問題模型，有幾點(diǎn)需要說明：對該問題模型，有幾點(diǎn)需要說明： 1)1)目標(biāo)集合中數(shù)據(jù)對象的個(gè)數(shù)目標(biāo)集合中數(shù)據(jù)對象的個(gè)數(shù) N N 通常在數(shù)量級上遠(yuǎn)通常在數(shù)量級上遠(yuǎn)遠(yuǎn)大于傳統(tǒng)算法中的數(shù)

46、據(jù)集合，通常無法將全部數(shù)據(jù)遠(yuǎn)大于傳統(tǒng)算法中的數(shù)據(jù)集合，通常無法將全部數(shù)據(jù)讀入內(nèi)存進(jìn)行分析，因此難以利用傳統(tǒng)的聚類算法解讀入內(nèi)存進(jìn)行分析，因此難以利用傳統(tǒng)的聚類算法解決這類問題。決這類問題。 2)2)在流數(shù)據(jù)聚類問題中，數(shù)據(jù)通常只能按照它們到達(dá)在流數(shù)據(jù)聚類問題中，數(shù)據(jù)通常只能按照它們到達(dá)的順序訪問，此后，數(shù)據(jù)即被存放于外存或丟棄，內(nèi)的順序訪問，此后，數(shù)據(jù)即被存放于外存或丟棄，內(nèi)存中只能保存已訪問數(shù)據(jù)的概要信息。也就是說，流存中只能保存已訪問數(shù)據(jù)的概要信息。也就是說，流數(shù)據(jù)算法為了避免高昂的系統(tǒng)開銷應(yīng)該盡可能少地重?cái)?shù)據(jù)算法為了避免高昂的系統(tǒng)開銷應(yīng)該盡可能少地重復(fù)訪問數(shù)據(jù)。事實(shí)上，復(fù)訪問數(shù)據(jù)。事實(shí)上

47、，“一次掃描數(shù)據(jù)一次掃描數(shù)據(jù)”已經(jīng)成為幾已經(jīng)成為幾乎所有流數(shù)據(jù)算法都需要實(shí)現(xiàn)的目標(biāo)。乎所有流數(shù)據(jù)算法都需要實(shí)現(xiàn)的目標(biāo)。流數(shù)據(jù)聚類問題模型流數(shù)據(jù)聚類問題模型 3)3)流數(shù)據(jù)算法的目標(biāo)集合是數(shù)據(jù)流中截取的某一個(gè)時(shí)流數(shù)據(jù)算法的目標(biāo)集合是數(shù)據(jù)流中截取的某一個(gè)時(shí)間段間段( (時(shí)間窗時(shí)間窗) )的對象集合。定義一個(gè)時(shí)間窗需要兩個(gè)的對象集合。定義一個(gè)時(shí)間窗需要兩個(gè)重要的輸入?yún)?shù)：起始時(shí)刻重要的輸入?yún)?shù)：起始時(shí)刻 t t 和時(shí)間窗口寬度和時(shí)間窗口寬度 h h，一個(gè)時(shí)間窗口可用一個(gè)時(shí)間窗口可用 W(t, h)W(t, h)來表示。算法的目標(biāo)集來表示。算法的目標(biāo)集合即由落入窗口合即由落入窗口W(t, h)W(t,

48、 h)的數(shù)據(jù)對象組成。的數(shù)據(jù)對象組成。 4)4)在流數(shù)據(jù)算法中，任何一個(gè)時(shí)刻的較小的誤差，都在流數(shù)據(jù)算法中，任何一個(gè)時(shí)刻的較小的誤差，都有可能隨著時(shí)間的推移而急速擴(kuò)大，最終造成錯(cuò)誤或有可能隨著時(shí)間的推移而急速擴(kuò)大，最終造成錯(cuò)誤或質(zhì)量較低的算法結(jié)果。因此，在每一個(gè)階段都要將誤質(zhì)量較低的算法結(jié)果。因此，在每一個(gè)階段都要將誤差嚴(yán)格控制在一個(gè)較小的區(qū)間之內(nèi)。差嚴(yán)格控制在一個(gè)較小的區(qū)間之內(nèi)。 5)5)同時(shí)，算法對時(shí)間效率的要求非常高，當(dāng)需要在某同時(shí)，算法對時(shí)間效率的要求非常高，當(dāng)需要在某一個(gè)特定時(shí)刻輸出聚類結(jié)果時(shí)，如果處理過程的時(shí)間一個(gè)特定時(shí)刻輸出聚類結(jié)果時(shí)，如果處理過程的時(shí)間開銷過大，則有可能會造成新

49、到數(shù)據(jù)的遺漏或丟失，開銷過大，則有可能會造成新到數(shù)據(jù)的遺漏或丟失，這種信息缺損隨著數(shù)據(jù)流的不斷進(jìn)行而加劇。這種信息缺損隨著數(shù)據(jù)流的不斷進(jìn)行而加劇。早期的流數(shù)據(jù)聚類早期的流數(shù)據(jù)聚類 早期的流數(shù)據(jù)聚類努力將數(shù)據(jù)流的動(dòng)態(tài)特性轉(zhuǎn)化為傳早期的流數(shù)據(jù)聚類努力將數(shù)據(jù)流的動(dòng)態(tài)特性轉(zhuǎn)化為傳統(tǒng)的靜態(tài)模式，從而能夠應(yīng)用成熟的傳統(tǒng)方法解決問統(tǒng)的靜態(tài)模式，從而能夠應(yīng)用成熟的傳統(tǒng)方法解決問題。在這一階段，算法研究的重點(diǎn)是改進(jìn)傳統(tǒng)算法的題。在這一階段，算法研究的重點(diǎn)是改進(jìn)傳統(tǒng)算法的性能，使之能夠適應(yīng)流數(shù)據(jù)的動(dòng)態(tài)特性。性能，使之能夠適應(yīng)流數(shù)據(jù)的動(dòng)態(tài)特性。 Small-Space Small-Space 算法正是這類算法的典型

50、代表。算法正是這類算法的典型代表。Small-Space 算法算法 輸入：按時(shí)間順序到達(dá)的流數(shù)據(jù)序列輸入：按時(shí)間順序到達(dá)的流數(shù)據(jù)序列 輸出：輸出：k個(gè)聚類中心點(diǎn)個(gè)聚類中心點(diǎn) 算法過程：算法過程： 1) 首先對初始到達(dá)的首先對初始到達(dá)的 m 個(gè)數(shù)據(jù)點(diǎn)進(jìn)行聚類，得到個(gè)數(shù)據(jù)點(diǎn)進(jìn)行聚類，得到 O(k)個(gè)個(gè) 1-級聚類中心點(diǎn)。級聚類中心點(diǎn)。 2) 重復(fù)上述步驟，當(dāng)處理重復(fù)上述步驟，當(dāng)處理 m2/ O(k)個(gè)原始數(shù)據(jù)點(diǎn)時(shí)，將個(gè)原始數(shù)據(jù)點(diǎn)時(shí)，將得到得到 m 個(gè)個(gè)1-級中心點(diǎn)。級中心點(diǎn)。 3) 對這對這 m 個(gè)個(gè) 1-級中心點(diǎn)進(jìn)行聚類得到級中心點(diǎn)進(jìn)行聚類得到 O(k)個(gè)個(gè) 2-級中級中心點(diǎn)。心點(diǎn)。 4) 迭代

51、執(zhí)行上述過程，每次迭代至多保留迭代執(zhí)行上述過程，每次迭代至多保留 m 個(gè)個(gè) i-級中級中心點(diǎn)，否則進(jìn)行聚類得到心點(diǎn)，否則進(jìn)行聚類得到 O(k)個(gè)個(gè)(i+1)-級中心點(diǎn)。級中心點(diǎn)。 5) 輸出聚類結(jié)果時(shí)，對當(dāng)前所有中心點(diǎn)進(jìn)行聚類，得到最輸出聚類結(jié)果時(shí)，對當(dāng)前所有中心點(diǎn)進(jìn)行聚類，得到最終的終的 k個(gè)聚類中心。個(gè)聚類中心。Small-Space 算法的問題算法的問題 算法需要累積數(shù)據(jù)點(diǎn)，當(dāng)數(shù)據(jù)量達(dá)到一定限度時(shí)進(jìn)行統(tǒng)一算法需要累積數(shù)據(jù)點(diǎn)，當(dāng)數(shù)據(jù)量達(dá)到一定限度時(shí)進(jìn)行統(tǒng)一處理，而通常處理算法較為復(fù)雜，造成了數(shù)據(jù)流在處理節(jié)處理，而通常處理算法較為復(fù)雜，造成了數(shù)據(jù)流在處理節(jié)點(diǎn)上的延遲。點(diǎn)上的延遲。 另一方面，

52、在累積數(shù)據(jù)點(diǎn)的過程中，算法處于空閑狀另一方面，在累積數(shù)據(jù)點(diǎn)的過程中，算法處于空閑狀態(tài)，在一定程度上降低了算法的效率，增加了時(shí)間開態(tài)，在一定程度上降低了算法的效率，增加了時(shí)間開銷。銷。雙層流數(shù)據(jù)聚類雙層流數(shù)據(jù)聚類 J. Han 提出雙層結(jié)構(gòu)算法提出雙層結(jié)構(gòu)算法 CluStream12 雙層聚類算法將處理工作分為兩個(gè)層面：在線層算法負(fù)責(zé)雙層聚類算法將處理工作分為兩個(gè)層面：在線層算法負(fù)責(zé)對數(shù)據(jù)進(jìn)行粗糙但快速的處理，并負(fù)責(zé)保存中間結(jié)果；離對數(shù)據(jù)進(jìn)行粗糙但快速的處理，并負(fù)責(zé)保存中間結(jié)果；離線層算法在中間結(jié)果的基礎(chǔ)上進(jìn)行精確而復(fù)雜的分析，此線層算法在中間結(jié)果的基礎(chǔ)上進(jìn)行精確而復(fù)雜的分析，此時(shí)目標(biāo)集合已成為靜態(tài)集合，因此通常情況下不必考慮數(shù)時(shí)目標(biāo)集合已成為靜態(tài)集合，因此通常情況下不必考慮數(shù)據(jù)流速的影響，并得到最終結(jié)果。據(jù)流速的影響，并得到最終結(jié)果。CluStream基本思想基本思想 在線層維護(hù)一系列的在線層維護(hù)一系列的“微簇微簇”(Micro-Cluster)作為保存數(shù)據(jù)作為保存數(shù)據(jù)概要信息的數(shù)據(jù)結(jié)構(gòu)。每個(gè)微簇用五元組概要信息的數(shù)據(jù)結(jié)構(gòu)。每個(gè)微簇用五元組(