stream (version 1.0-3)

DSC_DStream: D-Stream Data Stream Clustering Algorithm

Description

Implements the D-Stream data stream clustering algorithm.

Usage

DSC_DStream(gridsize, d=NA_integer_, lambda = 1e-3, 
   gaptime=1000L, Cm=3, Cl=.8, attraction=FALSE, epsilon=.3, Cm2=Cm, k=NULL)
get_attraction(x, dist=FALSE, relative=FALSE)

Arguments

gridsize

Size of grid cells. Vector of length d (dimensionality of the data). If only one value is specified then the same size is used for all dimensions.

d

dimensionality of the data. If unspecified then it is taken from the first clustered data point.

lambda

The lambda used in the fading function (Note: in the paper the authors use denote the decay factor as lambda, while here the decay factor will be computed from lambda using $2^-lambda$).

gaptime

sporadic grids are removed every gaptime number of points.

Cm

threshold used to detect dense grids (as a proportion of the average expected density).

Cl

threshold to detect transitional and sporadic grids (0 > Cl > 1).

attraction

compute and store information about the attraction between adjacent grids. If TRUE then attraction is used to create macro-clusters, otherwise macro-clusters are created by merging adjacent dense grids.

epsilon

overlap parameter for attraction as a proportion of gridsize.

Cm2

threshold on attraction to join two dense grid cells (as a proportion on the average expected attraction). In the original algorithm Cm2 is equal to Cm.

k

alternative to Cm2 (not in the original algorithm). Create k clusters based on attraction. In case of more than k unconnected components, closer groups of MCs are joined.

x

DSC_DStream object to get attraction values from.

dist

make attraction symmetric and transform into a distance.

relative

calculates relative attraction (normalized by the cluster weight).

Value

• An object of class DSC_DStream (subclass of DSC, DSC_R, DSC_Micro).

Details

D-Stream creates an equally spaced grid and estimates the density in each grid cell using the count of points falling in the cells. Grid cells are classified based on density into dense, transitional and sporadic cells. The density is faded after every new point by a factor of $2^{-lambda}$. Every gaptime number of points sporadic grid cells are removed. For reclustering D-Stream (2007 version) merges adjacent dense grids to form macro-clusters and then assigns adjacent transitional grids to macro-clusters. This behavior is implemented as attraction=FALSE. The 2009 version of the algorithm adds the concept of attraction between grids cells. If attraction=TRUE is used then the algorithm produces macro-clusters based on attraction between dense adjacent grids (uses Cm2 which in the original algorithm is equal to Cm).

For many functions (e.g., get_centers(), plot()), D-Stream adds a parameter grid_type with possible values of "dense", "transitional", "sparse", "all" and "used". This only returns the selected type of grid cells. "used" includes dense and adjacent transitional cells which are used in D-Stream for reclustering.

For plot D-Stream also provides extra parameters "grid" and "grid_type" to show micro-clusters as grid cells (density represented by gray values).

References

Yixin Chen and Li Tu. 2007. Density-based clustering for real-time stream data. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '07). ACM, New York, NY, USA, 133-142.

Li Tu and Yixin Chen. 2009. Stream data clustering based on grid density and attraction. ACM Trans. Knowl. Discov. Data 3, 3, Article 12 (July 2009), 27 pages.

See Also

DSC, DSC_Micro

Examples

dsd <- DSD_BarsAndGaussians(noise=.05)
plot(dsd)

# we set Cm=.8 to pick up the lower density clusters
dstream1 <- DSC_DStream(gridsize=1, Cm=3)
cluster(dstream1, dsd, 1000)
dstream1

# micro-clusters (these are "used" grid cells)
nclusters(dstream1)
head(get_centers(dstream1))

# plot (DStream provides additional grid visualization)
plot(dstream1, dsd)
plot(dstream1, dsd, grid=TRUE)

# look only at dense grids
nclusters(dstream1, grid_type="dense")
plot(dstream1, dsd, grid=TRUE, grid_type="dense")

# look at transitional and sparse cells
plot(dstream1, dsd, grid=TRUE, grid_type="transitional")
plot(dstream1, dsd, grid=TRUE, grid_type="sparse")

### Macro-clusters
# standard D-Stream uses reachability
nclusters(dstream1, type="macro")
get_centers(dstream1, type="macro")
plot(dstream1, dsd, type="both", grid=TRUE)
evaluate(dstream1, dsd, measure="crand", type="macro")


# use attraction for reclustering
dstream2 <- DSC_DStream(gridsize=1, attraction=TRUE, Cm=3)
cluster(dstream2, dsd, 1000)
dstream2

plot(dstream2, dsd, type="both", grid=TRUE)
evaluate(dstream2, dsd, measure="crand", type="macro")