數(shù)據(jù)流聚類算法D-Stream

1、Density-Based Clustering for Real-Time Stream Data基于密度的實(shí)時(shí)數(shù)據(jù)流聚類(D-Stream)翻譯 by muyefeiE-mail: muyefei注釋：版權(quán)歸作者所有，文檔僅用于交流學(xué)習(xí)，可以用大綱視圖查看文檔結(jié)構(gòu)摘要：現(xiàn)有的聚類算法比如CluStream是基于k-means算法的。這些算法不能夠發(fā)現(xiàn)任意形狀的簇以及不能處理離群點(diǎn)。而且，它需要預(yù)先知道k值和用戶指定的時(shí)間窗口。為了解決上述問題，本文提出了D-Stream算法，它是基于密度的算法。這個(gè)算法用一個(gè)在線部分將數(shù)據(jù)映射到一個(gè)網(wǎng)格，在離線部分計(jì)算網(wǎng)格的密度然后基于密度形成簇。算法采用

2、了密度衰減技術(shù)來捕獲數(shù)據(jù)流的動(dòng)態(tài)變化。為了探索衰減因子、數(shù)據(jù)密度以及簇結(jié)構(gòu)之間的關(guān)系，我們的算法能夠有效的并且有效率地實(shí)時(shí)調(diào)整簇。而且，我們用理論證明了移除那些屬于離群點(diǎn)的稀疏網(wǎng)格是合理的，從而提高了系統(tǒng)的時(shí)間和空間效率。該技術(shù)能聚類高速的數(shù)據(jù)流而不損失聚類質(zhì)量。實(shí)驗(yàn)結(jié)果表明我們的算法在聚類質(zhì)量和效率是有獨(dú)特的優(yōu)勢(shì)，并且能夠發(fā)現(xiàn)任意形狀的簇，以及能準(zhǔn)確地識(shí)別實(shí)時(shí)數(shù)據(jù)流的演化行為。關(guān)鍵詞流數(shù)據(jù)挖掘 基于密度的聚類 D-Stream 分散的網(wǎng)格1 介紹實(shí)時(shí)聚類高維數(shù)據(jù)流是困難的但很重要。因?yàn)樗诟鱾€(gè)領(lǐng)域應(yīng)用到。比如.聚類是一項(xiàng)關(guān)鍵的數(shù)據(jù)挖掘任務(wù)。挖掘數(shù)據(jù)流有幾項(xiàng)關(guān)鍵的挑戰(zhàn)：（1） 單遍掃描（2）

3、將數(shù)據(jù)流視為數(shù)據(jù)一個(gè)很長(zhǎng)的向量在很多應(yīng)用中捉襟見肘，用戶更加關(guān)注簇的演化行為。近來，出現(xiàn)了許多數(shù)據(jù)流聚類方法。比如STREAM、CluStream以及擴(kuò)展（在多數(shù)據(jù)流，分布式數(shù)據(jù)流，并行數(shù)據(jù)流上的擴(kuò)展）等。CluStream以及擴(kuò)展的算法有以下一些缺陷：1、 只能發(fā)現(xiàn)球形簇，不能發(fā)現(xiàn)任意形狀的簇。2、 不能夠識(shí)別噪聲和離群點(diǎn)。3、 基于k-means的算法需要多次掃描數(shù)據(jù)（其實(shí)CluStream利用兩階段方法和微簇解決了該問題）?；诿芏鹊木垲愃惴ń榻B。基于密度的方法可以發(fā)現(xiàn)任意形狀的簇，可以處理噪聲，對(duì)原始數(shù)據(jù)集只需一次掃描。而且，它不需要像k-means算法那樣預(yù)先設(shè)定k值。文本提出了D-

4、Stream,一種基于密度的數(shù)據(jù)流聚類框架。它不是簡(jiǎn)單用基于密度的算法替代k-means的數(shù)據(jù)流算法。它有兩項(xiàng)主要的技術(shù)挑戰(zhàn)：首先，我們不大愿意將數(shù)據(jù)流視為靜態(tài)數(shù)據(jù)很長(zhǎng)的一個(gè)序列，因?yàn)槲覀儗?duì)數(shù)據(jù)流演化的時(shí)間特征更加感興趣。為了捕獲簇的動(dòng)態(tài)變化，我們提出了一個(gè)新穎的方案，它可以將衰減因子與每個(gè)數(shù)據(jù)點(diǎn)的密度聯(lián)系起來。與CluStream算法要求用戶輸入聚類目標(biāo)的持續(xù)時(shí)間不同，衰減因子為系統(tǒng)提供一種新穎的機(jī)制，可以通過將最近的數(shù)據(jù)賦予更高的權(quán)重而不是完全丟棄歷史信息，從而動(dòng)態(tài)地、自動(dòng)地形成簇。另外，D-Stream不需要用戶輸入簇的數(shù)目k。因此，D-Stream特別適合于那些對(duì)應(yīng)用程序數(shù)據(jù)具有少量領(lǐng)

5、域知識(shí)的用戶。其次，由于數(shù)據(jù)流的數(shù)據(jù)是海量的，不大可能保留每個(gè)數(shù)據(jù)記錄的密度信息。因此我們提出將數(shù)據(jù)空間劃分成一個(gè)個(gè)離散的網(wǎng)格，然后將新來的數(shù)據(jù)映射到對(duì)應(yīng)的網(wǎng)格。這樣，我們不需要保留原始數(shù)據(jù)，僅僅需要操縱這些網(wǎng)格。然而，對(duì)于高維數(shù)據(jù)，這些網(wǎng)格的數(shù)目是海量的。因此如何處理高維數(shù)據(jù)來提高伸縮性是一個(gè)關(guān)鍵的問題。幸運(yùn)的是，實(shí)際上大部分網(wǎng)格是空的或者只包含少量的記錄，我們?cè)贒-Stream中開發(fā)了一種內(nèi)存有效的技術(shù)來管理這些松散的網(wǎng)格。與CluStream算法比起來，D-Stream在聚類質(zhì)量和效率方面更有優(yōu)勢(shì)，而且針對(duì)海量高維的流數(shù)據(jù)具有更好的伸縮性。本文的剩余部分是這樣組織的：部分2是D-Stre

6、am算法的概述；部分3提出了關(guān)于密度網(wǎng)格和衰減因子的一些概念和理論；部分4給出了算法的細(xì)節(jié)和理論分析；部分5是實(shí)驗(yàn)，在人工和真實(shí)數(shù)據(jù)集上與CluStream算法做了比較。部分6是論文總結(jié)。2 算法概述D-Stream算法對(duì)一個(gè)數(shù)據(jù)流，在每一個(gè)時(shí)刻，D-Stream算法的在線部分連續(xù)第讀入一個(gè)新的記錄，將多維的數(shù)據(jù)放置到對(duì)應(yīng)多維空間中的離散密度網(wǎng)格,然后更新密度網(wǎng)格的特征向量（5-8行）。關(guān)于密度網(wǎng)格和特征向量在部分3詳細(xì)介紹。離線部分在每隔gap（一個(gè)時(shí)間整數(shù)參數(shù)）時(shí)間動(dòng)態(tài)地調(diào)整簇。在第一個(gè)gap時(shí)間內(nèi)產(chǎn)生了初始簇（9-11行）。然后，算法周期性地移除松散的網(wǎng)格以及調(diào)整簇（12-15行）。3

7、密度網(wǎng)格由于不可能保留原始數(shù)據(jù)，D-Stream將多維數(shù)據(jù)空間分為許多密度網(wǎng)格然后由這些網(wǎng)格形成簇。如下圖所示：3.1 基礎(chǔ)定義文本中，假設(shè)輸入的數(shù)據(jù)有d維。并且在以下的數(shù)據(jù)空間中定義：在D-Stream中，我們將d維的空間S劃分成密度網(wǎng)格。假設(shè)對(duì)于每一維，它的空間是Si，i=1,.,d被分為pi個(gè)部分。這樣數(shù)據(jù)空間S被分成了個(gè)密度網(wǎng)格。每個(gè)密度網(wǎng)格g是由組成，我們將它表示為：一個(gè)數(shù)據(jù)記錄可以映射到下面一個(gè)密度網(wǎng)格g(x):對(duì)于每個(gè)記錄x,我們分給它一個(gè)密度系數(shù)，它隨著時(shí)間遞減。實(shí)際上，如果x在tc時(shí)刻到達(dá)，我們將它的時(shí)間戳定義成：T(x)=tc，這樣它在時(shí)刻t的密度系數(shù)D(x,t)就是：任何

8、網(wǎng)格的密度是經(jīng)常變動(dòng)的。然而，我們發(fā)現(xiàn)沒有必要在每一個(gè)時(shí)刻去更新所有數(shù)據(jù)記錄的密度值，而是，只有當(dāng)一個(gè)數(shù)據(jù)點(diǎn)映射到那個(gè)網(wǎng)格時(shí)，我們?nèi)ジ戮W(wǎng)格的密度。對(duì)于每個(gè)網(wǎng)格，當(dāng)一個(gè)新的數(shù)據(jù)記錄到達(dá)某個(gè)網(wǎng)格，且接收到需要記錄的最后的數(shù)據(jù)記錄時(shí)，我們才根據(jù)下面的結(jié)論去更新網(wǎng)格的密度。命題 3.1 假設(shè)一個(gè)網(wǎng)格g在時(shí)刻tn接收到一個(gè)新的數(shù)據(jù)記錄，假設(shè)g接收到最后的數(shù)據(jù)記錄是在時(shí)刻tl(tn>tl)，那么g的密度可以按下面的方式更新：證明略。命題3.1節(jié)省了大量的計(jì)算時(shí)間。原本在每個(gè)時(shí)間間隔更新所有網(wǎng)格需要計(jì)算時(shí)間。相反的是，利用命題3.1我們只用的運(yùn)行時(shí)間就可以更新一個(gè)網(wǎng)格。這種效率的增加是非常明顯的，因

9、為網(wǎng)格數(shù)目N的數(shù)目是巨大的。而且，命題3.1節(jié)省了內(nèi)存空間。我們發(fā)現(xiàn)在一個(gè)網(wǎng)格中，我們沒有必要去保存時(shí)間戳和密度值。相反的，對(duì)于每個(gè)網(wǎng)格，按一下定義的方式存儲(chǔ)一個(gè)特征向量。稍后解釋該向量中的每一項(xiàng)。命題 3.2 （特征向量） 一個(gè)網(wǎng)格g的特征向量是一個(gè)五元組：其中，tg是g更新的最后時(shí)間，tm是g作為松散（稀疏）網(wǎng)格從grid_list中移除的最后時(shí)間，D是網(wǎng)格最后更新后的密度，label是網(wǎng)格的類（簇）標(biāo)簽，status=SPORADIC,NORMAL是一個(gè)用來移除松散網(wǎng)格的標(biāo)簽，3.2 基于密度的網(wǎng)格簇我們現(xiàn)在需要決定如何基于密度信息得到簇。我們的方法是基于以下的觀察：命題3.2. 讓從時(shí)

10、刻0到時(shí)刻t到達(dá)的所有數(shù)據(jù)記錄成為一個(gè)集合。我們有：證明略。命題3.2表明系統(tǒng)中所有數(shù)據(jù)記錄密度的總和永遠(yuǎn)不會(huì)超過。由于存在個(gè)網(wǎng)格，因此每個(gè)網(wǎng)格的平均密度不會(huì)超過。有這個(gè)觀察得到以下的定義：在時(shí)刻t，對(duì)一個(gè)網(wǎng)格g，如果有我們稱它為稠密網(wǎng)格。其中，Cm>1是一個(gè)控制閾值的參數(shù)。比如，我們?cè)O(shè)定Cm=3。我們要求N>Cm，因?yàn)镈(g,t)不能超過。在時(shí)刻t，對(duì)一個(gè)網(wǎng)格g，如果有我們稱它為稀疏網(wǎng)格。其中，0<Cl<1。比如，我們?cè)O(shè)定Cl=0.8。在時(shí)刻t，對(duì)一個(gè)網(wǎng)格g，如果有我們稱它為過渡網(wǎng)格。在多維空間，為了形成簇，我們考慮連接各個(gè)鄰接的網(wǎng)格，我們按以下定義：定義 3.3 （

11、鄰接網(wǎng)格）考慮兩個(gè)稠密網(wǎng)格和，如果存在，使得：那么在第k維空間，g1和g2就是鄰接網(wǎng)格。表示為：g1g2。定義 3.4 （網(wǎng)格組）如果對(duì)于任何兩個(gè)網(wǎng)格G，存在一系列網(wǎng)格使得，那么密度網(wǎng)格的一個(gè)集合就是一個(gè)網(wǎng)格組。定義 3.5 （內(nèi)部網(wǎng)格和外部網(wǎng)格）考慮到一個(gè)網(wǎng)格組G以及一個(gè)網(wǎng)格，假如，如果g在每一個(gè)維度存在鄰接網(wǎng)格。那么g就是G中的一個(gè)內(nèi)部網(wǎng)格。否則g就是G中的一個(gè)外部網(wǎng)格?，F(xiàn)在我們準(zhǔn)備定義如何基于網(wǎng)格的密度形成簇。定義 3.6 （網(wǎng)格簇）如果G內(nèi)部每一個(gè)網(wǎng)格都是稠密網(wǎng)格而每個(gè)外部網(wǎng)格或者是一個(gè)稠密網(wǎng)格或者是一個(gè)過渡網(wǎng)格，那么G就是一個(gè)網(wǎng)格簇。直觀地，一個(gè)網(wǎng)格簇就是一個(gè)連接的網(wǎng)格組，它比它周圍

12、的網(wǎng)格密度要大。注意到我們總是嘗試在任何可能的時(shí)候合并簇，因此這樣會(huì)導(dǎo)致簇被松散的網(wǎng)格所包圍。4 D-Stream算法的組成我們將在圖1描述了算法D-Stream的主要部分。對(duì)于每一個(gè)新的數(shù)據(jù)記錄x，我們將它映射到一個(gè)網(wǎng)格g，然后利用（5）來更新g的密度（圖1 中5-8行）。然后，我們周期性的（每隔gap時(shí)間）形成簇以及移除稀疏網(wǎng)格。下面我們描述確定gap的策略，管理活動(dòng)網(wǎng)格的列表（list）以及產(chǎn)生簇。4.1 網(wǎng)格檢測(cè)以及時(shí)間間隔gap為了挖掘數(shù)據(jù)流的動(dòng)態(tài)特征，我們?cè)诓糠?開發(fā)的密度網(wǎng)格方案會(huì)逐漸地使得每個(gè)數(shù)據(jù)記錄和網(wǎng)格的密度變小。如果一個(gè)稠密網(wǎng)格長(zhǎng)期不接收一個(gè)新的數(shù)據(jù)，它可能會(huì)降級(jí)成為一個(gè)

13、過渡網(wǎng)格或者一個(gè)稀疏網(wǎng)格。另一方面，如果一個(gè)稀疏網(wǎng)格接受一些新的數(shù)據(jù)記錄，它可以升級(jí)成為一個(gè)過渡網(wǎng)格或者稠密網(wǎng)格。因此，經(jīng)過一個(gè)時(shí)間周期后，每個(gè)網(wǎng)格的密度應(yīng)該被重新檢查，簇也要調(diào)整。一個(gè)關(guān)鍵的決定是確定檢查網(wǎng)格的時(shí)間間隔的長(zhǎng)度。我們發(fā)現(xiàn)這個(gè)時(shí)間間隔gap不能太大也不能太小。如果gap太大，數(shù)據(jù)流的動(dòng)態(tài)變化不能夠被很好地識(shí)別出來。如果gap太小，會(huì)導(dǎo)致在離線部分頻繁地計(jì)算從而增加了負(fù)載。當(dāng)這種計(jì)算負(fù)載過重，離線部分的處理速度可能不能匹配數(shù)據(jù)流輸入的速度。我們提出以下的策略來確定gap值的合適大小。我們認(rèn)為使一個(gè)稠密網(wǎng)格降級(jí)成為稀疏網(wǎng)格所需的的最少時(shí)間與使一個(gè)稀疏網(wǎng)格成為一個(gè)稠密網(wǎng)格所需的時(shí)間差不

14、多。為了確保檢查除足夠頻繁地去監(jiān)測(cè)任何網(wǎng)格的密度變化，我們將gap設(shè)定為這些最小時(shí)間的中的最小值。命題 4.1 對(duì)任何稠密網(wǎng)格g，從稠密網(wǎng)格成為一個(gè)稀疏網(wǎng)格所需的最少時(shí)間是：證明略。命題 4.2 對(duì)任何稀疏網(wǎng)格g，從稀疏網(wǎng)格成為一個(gè)稠密網(wǎng)格所需的最少時(shí)間是：證明略?；谝陨蟽蓚€(gè)命題，我們選擇足夠小的gap，這樣可以識(shí)別一個(gè)網(wǎng)格從稠密變?yōu)橄∈璧娜魏巫兓?，或者從稀疏變?yōu)槌砻埽ǖ娜魏巫兓?。因此，在D-Stream中我們?cè)O(shè)定：4.2 檢測(cè)以及移除稀疏網(wǎng)格針對(duì)基于密度的方案一個(gè)嚴(yán)重挑戰(zhàn)是大量的網(wǎng)格，尤其是高維數(shù)據(jù)。比如，如果每一個(gè)維度被分為20個(gè)部分，那么將有20d（指數(shù)級(jí)）個(gè)可能的網(wǎng)格。一個(gè)關(guān)鍵的觀

15、察是空間中的大部分網(wǎng)格是空的或者只接收數(shù)據(jù)不是很頻繁。在我們的實(shí)現(xiàn)方法中，我們只為那些非空的網(wǎng)格分配內(nèi)存用來存儲(chǔ)特征向量，這可以形成一個(gè)非常小的網(wǎng)格子空間。不幸的是，實(shí)際上，由于在數(shù)據(jù)錯(cuò)誤中形成的離群點(diǎn)數(shù)據(jù)，導(dǎo)致在聚類過程中不斷地增加處理非空網(wǎng)格的時(shí)間，這個(gè)方法的效率不是足夠高。由于這些網(wǎng)格包含非常少的數(shù)據(jù)，我們稱它為稀疏網(wǎng)格。由于大量的數(shù)據(jù)流高速地到達(dá)而且運(yùn)行很長(zhǎng)時(shí)間，這樣使得稀疏網(wǎng)格不斷累積，它們的數(shù)目會(huì)變得非常巨大，最終導(dǎo)致系統(tǒng)運(yùn)行越來越慢。因此我們有必要周期性地檢測(cè)和移除這樣的稀疏網(wǎng)格。這在圖1中的D-Stream算法中的13行描述。那些的網(wǎng)格代表稀疏網(wǎng)格。然而，有兩種原因會(huì)導(dǎo)致一個(gè)網(wǎng)

16、格的密度會(huì)小于Dl。第一個(gè)原因是它接收到非常少的數(shù)據(jù)，第二個(gè)原因是那個(gè)網(wǎng)格雖然在過去時(shí)間接收到許多數(shù)據(jù)但是由于受衰減因子的影響它的密度不斷變小。只有前面那個(gè)原因?qū)е碌南∈杈W(wǎng)格才是真的，需要移除。有后者原因?qū)е碌南∈杈W(wǎng)格不應(yīng)該被移除，因?yàn)樗嗽S多數(shù)據(jù)，而且它經(jīng)常升級(jí)，可能會(huì)成為過渡網(wǎng)格或者稠密網(wǎng)格。通過大量的實(shí)驗(yàn)，我們發(fā)現(xiàn)由于后者原因從而導(dǎo)致錯(cuò)誤地移除這些網(wǎng)格會(huì)嚴(yán)重地惡化聚類的質(zhì)量。我們定義了一個(gè)密度閾值函數(shù)來區(qū)分這兩種不同類別的稀疏網(wǎng)格。定義 4.1 （密度閾值函數(shù)）假設(shè)一個(gè)網(wǎng)格g最后的更新時(shí)間是tg，那么在時(shí)刻t（t>tg），密度閾值函數(shù)是：命題 4.3 函數(shù)具有以下一些性質(zhì)：證明

17、略。我們從所有稀疏網(wǎng)格中用檢測(cè)出松散的網(wǎng)格。在圖1中13行的周期性檢測(cè)中，在時(shí)刻t，如果滿足以下條件，我們判斷那個(gè)稀疏網(wǎng)格是一個(gè)松散網(wǎng)格。注意tm和tg在是特征向量中存儲(chǔ)。在D-Stream中，我們維護(hù)一個(gè)grid_list，它包括那些考慮用來作聚類分析的網(wǎng)格。grid_list使用可以解決沖突的雙鏈表結(jié)構(gòu)的哈希表實(shí)現(xiàn)。哈希表運(yùn)行檢索、更新以及刪除。當(dāng)將每一個(gè)網(wǎng)格聯(lián)系到一個(gè)特征向量的入口，哈希表的關(guān)鍵詞就相當(dāng)于一個(gè)網(wǎng)格。我們使用下面的規(guī)則從grid_list刪除松散網(wǎng)格。(D1) 在圖1中的13行的周期性檢測(cè)中，所有滿足（S1）和（S2）條件的網(wǎng)格被標(biāo)識(shí)為SPORADIC，但是以后一直在等待（

18、不做任何操作）直到下一個(gè)被認(rèn)為可以刪除的周期性檢測(cè)。(D2) 在下一個(gè)周期性檢測(cè)中，如果一個(gè)被標(biāo)識(shí)為SPORADIC的網(wǎng)格，自從上一次檢測(cè)后再也沒有收到任何數(shù)據(jù)，我們將它從grid_list中刪除。否則，檢查g是否滿足（S1）和（S2）；如果是，我們保持g標(biāo)識(shí)為SPORADIC不變；如果否，我們將標(biāo)簽重置為NORMAL。我們應(yīng)當(dāng)注意到，一旦一個(gè)松散網(wǎng)格被刪除，它的密度實(shí)際上被重置為零，由于它的特征向量被刪除了。如果后來又有新的數(shù)據(jù)記錄映射到上述網(wǎng)格，我們可能需要增加上述的網(wǎng)格，但是它以前的記錄被拋棄了，它的密度將從新重零開始。這樣一個(gè)動(dòng)態(tài)機(jī)制可以維護(hù)內(nèi)存中適宜大小的網(wǎng)格，節(jié)省了聚類的計(jì)算時(shí)間，

19、以及阻止了對(duì)內(nèi)存中松散網(wǎng)格無盡的計(jì)算。盡管刪除松散的網(wǎng)格對(duì)D-Stream算法的效率性能非常關(guān)鍵，該方案是否正確，一個(gè)重要的問題是這種刪除是否會(huì)影響到聚類的結(jié)果。特別地，由于一個(gè)松散的網(wǎng)格可能在以后時(shí)間接收到數(shù)據(jù)從而成為過渡網(wǎng)格或者稠密網(wǎng)格，我們需要知道這種刪除是否有可能阻止這個(gè)網(wǎng)格被正確地標(biāo)識(shí)為過渡網(wǎng)格或者稠密網(wǎng)格。我們已經(jīng)設(shè)計(jì)了一個(gè)密度閾值函數(shù)和一些刪除規(guī)則，這樣的話過渡簇或者稠密簇不會(huì)被錯(cuò)誤地刪除，由于對(duì)松散網(wǎng)格的移除。考慮到一個(gè)網(wǎng)格g，它在時(shí)刻t的密度是D(g,t)，假設(shè)它在t（每次它的密度被重置為零）之前已經(jīng)被刪除若干次了，因?yàn)樗拿芏仍谠S多時(shí)刻比密度閾值函數(shù)值要小。假設(shè)這些密度值沒

20、有被清除而是被全部保留，那么網(wǎng)格g的密度是Da(g,t)，我們將Da(g,t)稱為網(wǎng)格g的完全密度函數(shù)?，F(xiàn)在我們提出了一些密度函數(shù)重要的理論性質(zhì)，這些性質(zhì)可以保證D-Stream系統(tǒng)的正確功能。我們將要闡明，如果一個(gè)網(wǎng)格在后來會(huì)成為一個(gè)過渡網(wǎng)格或者稠密網(wǎng)格，將它作為松散網(wǎng)格刪除將不會(huì)影響其以后的升級(jí)（就是說松散網(wǎng)格在以后可能升級(jí)為過渡網(wǎng)格或者稠密網(wǎng)格）。我們首先調(diào)查的問題是，如果一個(gè)網(wǎng)格g作為松散網(wǎng)格被刪除，如果它以前從沒有過從grid_list中刪除，那么g是否有可能成為非松散的呢？我們將用下面的結(jié)論回答這個(gè)問題。（答案是g不能是非松散的，一定是松散的）命題 4.4 假設(shè)網(wǎng)格g作為松散網(wǎng)格被

21、刪除的最后時(shí)刻是tm，以及g接收一個(gè)數(shù)據(jù)記錄的最后時(shí)間是tg。如果在現(xiàn)在時(shí)刻t，我們有，那么我們同樣有。證明略。命題4.4非常重要由于它表明了刪除一個(gè)松散的網(wǎng)格不會(huì)導(dǎo)致過渡網(wǎng)格或者稠密網(wǎng)格被錯(cuò)誤地刪除。它表明，如果網(wǎng)格g在t時(shí)刻由于它作為松散網(wǎng)格被刪除，那么即使在以前沒有發(fā)生過任何的刪除（操作），它仍然是一個(gè)松散網(wǎng)格，并不能成為一個(gè)過渡網(wǎng)格或者稠密網(wǎng)格，因?yàn)椤Ｃ} 4.5 一個(gè)網(wǎng)格g在時(shí)刻t的密度是D(g,t)，而且g在t+1和t+gap之間沒有收到任何數(shù)據(jù)，那么存在t0>0以及t1>0使得：證明略。命題4.5是一個(gè)關(guān)鍵的結(jié)論，它使得（S1），（S2），（D1），（D2）一起正確地

22、起作用。它表明，當(dāng)時(shí)間持續(xù)足夠長(zhǎng)，我們將永遠(yuǎn)不會(huì)因?yàn)閷?duì)過去數(shù)據(jù)的移除而刪除一個(gè)過渡網(wǎng)格或者稠密網(wǎng)格。如果如果一個(gè)網(wǎng)格是稀疏的（非稠密），那么當(dāng)它被刪除時(shí)，它肯定是稀疏的（非稠密），即使考慮到過去那些刪除的數(shù)據(jù)。我們知道表示網(wǎng)格的密度（假設(shè)在以前從來沒發(fā)生過刪除（操作）。結(jié)果表明，在一個(gè)初始化階段后，刪除松散的網(wǎng)格不會(huì)影響聚類的結(jié)果。4.3 聚類算法我們所描繪的算法初始化簇后，然后每隔gap時(shí)間調(diào)整簇。初始化聚類（initial_clustering）的過程在圖3描述。調(diào)整聚類（adjust_clustering）的過程在圖4描述。一旦網(wǎng)格的密度在給定的時(shí)刻被確定，聚類的過程與使用基于密度聚類的標(biāo)準(zhǔn)方法類似。我們應(yīng)當(dāng)注意，在計(jì)算過程中，不管在什么時(shí)候我們更新網(wǎng)格和發(fā)現(xiàn)鄰接網(wǎng)格，我們只需考慮那些在grid_list中維護(hù)的網(wǎng)格。因此，盡管高維數(shù)據(jù)可能存