--- title: "DSD_MG: A flexible Framework to Construct Non-Stationary Data Stream for Evaluation" author: "Michael Hahsler" output: rmarkdown::html_vignette: toc: true vignette: > %\VignetteIndexEntry{DSD_MG: A flexible Framework to Construct Non-Stationary Data Stream for Evaluation} %\VignetteEngine{knitr::rmarkdown} %\VignetteEncoding{UTF-8} --- ```{r setup, include=FALSE} knitr::opts_chunk$set(collapse = TRUE, comment = "#>", fig.width = 7, fig.height = 5) library(stream) set.seed(1000) ``` Testing stream clustering algorithms on non-stationary data requires streams where the ground truth is known and the way the data changes can be controlled: clusters that move, grow, shrink, appear, disappear, split or merge. `DSD_MG()`, the Data Stream Moving Cluster Generator provides a flexible framework for building such streams from individual components. Instead of one fixed model, a `DSD_MG` stream is assembled from a list of **Moving Generator Cluster** objects (`MGC`s). Each `MGC` is a small, independent component that describes a single cluster: * *where* it is (its center), * *how big* it is and what *shape* it has (the shape parameters), * *how many points* it produces (its density), and, for moving components, how these properties change over time. `DSD_MG()` combines the components into one stream. Because every component has its own behavior, mixing different components creates complex evolving streams from simple building blocks. This guide introduces the components, shows how to combine them, and shows how to change a stream after it has been created. See the help pages `?DSD_MG` and `?MGC` for the complete documentation. ## Building blocks The following components are available. All components for a stream must have the stream's dimensionality. | Component | Behavior | |:----------|:---------| | `MGC_Static()` | A stationary cluster with fixed properties (size, position, etc.). | | `MGC_Linear()` | A cluster whose center, density, and shape parameters are linearly interpolated between **keyframes**. | | `MGC_Function()` | A cluster where density, center, and shape parameters are **functions of time**. | | `MGC_Random()` | A cluster that follows a **random walk**. | | `MGC_Noise()` | Uniform random noise in a given area often used to create individual random outliers. | The shape of a cluster is given by the `shape` argument, which is a function that draws a single point from the cluster. Two shapes are provided: `Shape_Gaussian` (the default, where `parameter` is the standard deviation, one per dimension) and `Shape_Block` (a uniform block, where `parameter` gives the side lengths). If a single value is given, it is recycled for all dimensions. New shapes can be defined as functions with the arguments `center` and `parameter` that return a single point (see the end of this guide). ## How the generator works Generation is driven by a *generator time* that advances as points are drawn. Each component has a `density`. To produce a point, `DSD_MG()` chooses a component with a probability proportional to the current densities of all components, and then draws a point from the chosen component's shape at its current center. The density therefore controls both the relative chance of choosing a component and, through the total density, how fast generator time advances: with a total density of 100, approximately 100 points advance the generator by one time unit. Components that change over time thus change what the stream looks like, and components can be added or removed at any time. Each point is returned with a `.class` column containing the label of the component that produced it. Components can share a label to form one ground-truth cluster, and noise has the label `NA`. ## Combine static clusters and noise Start with a Gaussian cluster, a uniform rectangular cluster, and uniform background noise. `parameter` gives standard deviations for `Shape_Gaussian` and side lengths for `Shape_Block`. By default each component gets its own label; we set them explicitly here and use `NA` for the noise. ```{r static-stream} stream <- DSD_MG(dimension = 2, MGC_Static(density = 45, center = c(1, 0), parameter = 0.1), MGC_Static(density = 45, center = c(2, 0), parameter = c(0.4, 0.6), shape = Shape_Block), MGC_Noise(density = 10, range = rbind(c(0, 3), c(-1, 1))), labels = c(1, 2, NA) ) stream get_points(stream, n = 5) plot(stream, n = 500, xlim = c(0, 3), ylim = c(-1, 1)) ``` The total density is 100, so approximately 100 points advance the generator by one time unit, and the Gaussian component produces about 45% of the points. Noise has label `NA` in the `.class` column. Supplying the same label to several components makes them form one ground-truth cluster. This makes it easy to build clusters with non-convex shapes. Here three blocks form an L-shaped cluster (label 1) next to a second cluster (label 2): ```{r l-shape} stream <- DSD_MG(dimension = 2, MGC_Static(density = 10, center = c(.5, .2), parameter = c(.4, .2), shape = Shape_Block), MGC_Static(density = 10, center = c(.6, .5), parameter = c(.2, .4), shape = Shape_Block), MGC_Static(density = 5, center = c(.39, .53), parameter = c(.16, .35), shape = Shape_Block), MGC_Noise(density = 1, range = rbind(c(0, 1), c(0, 1))), labels = c(1, 1, 2, NA) ) plot(stream, n = 500, xlim = c(0, 1), ylim = c(0, 1)) ``` ## Define movement with keyframes `MGC_Linear()` interpolates the center, density, and shape parameters between keyframes. This lets you describe movement, growth, and appearance of a cluster with a few points in time. The next example starts with one cluster. At time 50, a second component appears at the same location, then moves in another direction. This simulates a cluster that splits. ```{r splitting-stream} c1 <- MGC_Linear(dimension = 2, keyframelist = list( keyframe(time = 1, density = 20, center = c(0, 0), parameter = 5), keyframe(time = 50, density = 20, center = c(50, 50), parameter = 5), keyframe(time = 100, density = 20, center = c(50, 100), parameter = 5) )) c2 <- MGC_Linear(dimension = 2, keyframelist = list( keyframe(time = 50, density = 20, center = c(50, 50), parameter = 5), keyframe(time = 100, density = 20, center = c(100, 50), parameter = 5) )) stream <- DSD_MG(dimension = 2, c1, c2) get_keyframes(c1) ``` A linear component produces no points before its first keyframe. After its last keyframe it keeps its final attributes. A keyframe with `reset = TRUE` can make the trajectory repeat, as in `DSD_Benchmark(1)`. Generator time is different from the count of requested points. The second component starts after about 980 points: 49 time units at density 20. Once it appears, the total density becomes 40. Plot three short sections around this change and near the end of the movement: ```{r splitting-snapshots, fig.width=9, fig.height=3.5} old_par <- par(mfrow = c(1, 3)) plot(stream, n = 200, xlim = c(-15, 115), ylim = c(-15, 115), main = "One cluster") invisible(get_points(stream, n = 780)) plot(stream, n = 200, xlim = c(-15, 115), ylim = c(-15, 115), main = "Second cluster appears") invisible(get_points(stream, n = 1400)) plot(stream, n = 200, xlim = c(-15, 115), ylim = c(-15, 115), main = "Separate paths") par(old_par) ``` Keyframes can also be added to an existing component with `add_keyframe()`, and removed with `remove_keyframe()`. Each keyframe can use a different density or shape parameter, so a cluster can also grow, shrink, fade in, or fade out. ```{r add-keyframe} c3 <- MGC_Linear(dimension = 2, shape = Shape_Block) add_keyframe(c3, time = 1, density = 25, parameter = c(10, 10), center = c(0, 0)) add_keyframe(c3, time = 100, density = 25, parameter = c(30, 30), center = c(100, 100)) get_keyframes(c3) ``` ## Specify movement as a function of time `MGC_Function()` accepts functions of generator time for density, center, and shape parameters. This allows arbitrary trajectories without defining keyframes. For example, a block-shaped cluster can move along the diagonal while it grows: ```{r function-growing} growing <- MGC_Function( density = function(t) 100, parameter = function(t) 1 * t, center = function(t) c(t, t), shape = Shape_Block ) ``` Here a Gaussian cluster travels around a circle while a static cluster remains at the center. ```{r functional-stream} orbit <- MGC_Function( density = function(t) 20, center = function(t) c(0.5 + 0.35 * cos(t / 10), 0.5 + 0.35 * sin(t / 10)), parameter = function(t) 0.03 ) stream <- DSD_MG(dimension = 2, orbit, MGC_Static(density = 5, center = c(0.5, 0.5), parameter = 0.03)) ``` The GIF below shows the functional generator in batches of 50 points using `animate_data()`, making the orbiting cluster's movement visible. It loops automatically at ten frames per second and is embedded directly in the HTML. Knitr creates the GIF using the `gifski` R package. Install `gifski` before rendering to include the animation. The animation chunk is skipped when `gifski` is unavailable or the output is not HTML. ```{r generator-animation, eval=knitr::is_html_output() && requireNamespace("gifski", quietly=TRUE) && requireNamespace("animation", quietly=TRUE), fig.show='animate', animation.hook='gifski', interval=0.1, aniopts='loop', dev='png', fig.width=6.4, fig.height=4.8, dpi=100, fig.retina=1, fig.alt='A moving Gaussian cluster orbiting a static cluster'} set.seed(1000) reset_stream(stream) animate_data(stream, n = 1500, horizon = 50, wait = 0, xlim = c(0, 1), ylim = c(0, 1)) ``` For interactive exploration, the following example uses the `animation` package and is not run during vignette builds. ```{r animation, eval=FALSE} reset_stream(stream) animate_data(stream, n = 1500, horizon = 100, xlim = c(0, 1), ylim = c(0, 1)) animation::ani.replay() ``` ## Clusters that move randomly `MGC_Random()` creates a cluster that follows a random walk. `center` is its starting position and `randomness` is the maximum amount it moves in one time step. Mixing random and static components gives streams where some clusters drift unpredictably while others stay in place. ```{r random-stream} stream <- DSD_MG(dimension = 2, MGC_Random(density = 100, center = c(1, 0), parameter = 0.1, randomness = 0.2), MGC_Random(density = 100, center = c(2, 0), parameter = 0.4, shape = Shape_Block, randomness = 0.2) ) stream ``` ## Add and remove components Generators can be modified after construction, so a stream can be changed while it is running. `get_clusters()` returns the component list; `add_cluster()` adds a component and `remove_cluster()` takes an index in that list. ```{r modify-stream} stream <- DSD_MG(dimension = 2, MGC_Linear(dimension = 2, keyframelist = list( keyframe(time = 1, density = 20, center = c(0, 0), parameter = 5), keyframe(time = 100, density = 20, center = c(100, 100), parameter = 5))), MGC_Static(density = 20, center = c(50, 50), parameter = 5)) noise <- MGC_Noise(density = 2, range = rbind(c(-15, 115), c(-15, 115))) add_cluster(stream, noise, label = NA) length(get_clusters(stream)) plot(stream, n = 500, xlim = c(-15, 115), ylim = c(-15, 115)) remove_cluster(stream, i = 3) length(get_clusters(stream)) ``` Use `add_keyframe()` and `remove_keyframe()` to edit a linear component's trajectory. Stream and component objects contain mutable state: updating a component can also affect a stream that contains it. ## Define your own shape A shape is a function with the arguments `center` and `parameter` that returns a single point. As an example, here is a ring shape in two dimensions, where `parameter` is the radius and the points are spread uniformly around the center with a little noise. ```{r custom-shape} Shape_Ring <- function(center, parameter) { angle <- runif(1, 0, 2 * pi) center + rnorm(1, mean = parameter[1], sd = 0.02) * c(cos(angle), sin(angle)) } stream <- DSD_MG(dimension = 2, MGC_Static(density = 50, center = c(0.5, 0.5), parameter = 0.3, shape = Shape_Ring), MGC_Static(density = 25, center = c(0.5, 0.5), parameter = 0.05) ) plot(stream, n = 500, xlim = c(0, 1), ylim = c(0, 1)) ``` ## Use the stream A `DSD_MG` stream is a regular `DSD` object. It can be used like any other stream to cluster and evaluate, for example with `update()` and `evaluate_stream()`. Because the generator knows which component produced each point, the true labels are available for external evaluation, even when the clusters move. See [Evaluating Non-stationary Clusters](evaluation_non-stationary.html) for how to evaluate clustering on moving data and [Clustering data streams with DBSTREAM](DBSTREAM.html) for a clustering algorithm that is able to follow such streams.