文档介绍：Density-Based Clustering for Real-Time Stream Data
基于密度的实时数据流聚^(D-Stream)
Yixin Chen
Department of Computer Science ampty hash table :
while data stream is active do
read record h =(① j ,工日):
determine the density grid g that contains x:
if(g not in griddist) insert g to :
update the characteristic vector of g;
if tc == gap then
call initiaLclusteri:
end if
if tc mod gap —— 0 then
detect and remove sporadic grids from griddist'.
call adjust_clustering(griddist);
end if
tc — tc — 1;
end while
end-procedure
Figure 1: The overall process of D-Stream.
对一个数据流，在每一个时刻，D-Stream算法的在线部分连续第读入一个新的记录，将多维的数据放置到对应多维空间中的离散密度网格，然后更新密度网格的特征向量（5-8 行）。关于密度网格和特征向量在部分3详细介绍。离线部分在每隔gap （一个时间整数参数）
时间动态地调整簇。在第一个gap时间内产生了初始簇（9-11行）。然后，算法周期性地移除松散的网格以及调整簇(12-15行)。
3密度网格
由于不可能保留原始数据，D-Stream将多维数据空间分为许多密度网格然后由这些网格形成簇。如下图所示：
Deadly Gild < hist«ilug results
■ ■
Ooliiie OfTLiiip pi o<€5^iug
Figure 2: I Bust ration of the use of density grid.

文本中，假设输入的数据有d维。并且在以下的数据空间中定义：
5 = Si X. 5a X.…x Sd- (1)
在D-Stream中，我们将d维的空间S划分成密度网格。假设对于每一维，它的空间是 Si，i=1,...,d被分为pi个部分。
s = u s’* U ‘ , • LJSlp” (2)
这样数据空间S被分成了二匚=."个密度网格。每个密度网格g是由
' 七： --组成，我们将它表示为：
g =(力’如，…,勿). (3)
一个数据记录■ = ■■ ■"- ■ 可以映射到下面一个密度网格g(x):
9(壬)=(jir J2-… 确)^vliere e Sij{ ■
对于每个记录x,我们分给它一个密度系数，它随着时间递减。实际上，如果x在tc时刻到达，我们将它的时间戳定义成：T(x)=tc，这样它在时刻t的密度系数D(x,t)就是：
D()=泌-丁⑴=(4)
任何网格的密度是经常变动的。然而，我们发现没有必要在每一个时刻去更新所有数据
记录的密度值，而是，只有当一个数据点映射到那个网格时，我们去更新网格的密度。对于每个网格，当一个新的数据记录到达某个网格，且接收到需要记录的最后的数据记录时，我们才根据下面的结论去更新网格的密度。
，假设g接收到最后的数据记录是在时刻tl(tn>tl)，那么g的密度可以按下面的方式更新：
比)=人坛_垃"(9的)+ 1 (5)
证明略。
JL
。原本在每个时间间隔更新所有网格需要计算时
间。相反的是，-的运行时间就可以更新一个网格。这种效率的
增加是非常明显的，因为网格数目N的数目是巨大的。
而且，。我们发现在一个网格中，我们没有必要去保存时间戳和密度值。相反的，对于每个网格，按一下定义的方式存储一个特征向量。稍后解释该向量中的每一项。
(特征向量)一个网格g的特征向量是一个五元组：
其中，tg是g更新的最后时间，tm是g作为松散(稀疏)网格
从grid_list中移除的最后时间，D是网格最后更新后的密度，label是网格的类(簇)标签， status={SPORADIC,NORMAL}是一个用来移除松散网格的标签，

我们现