Transition {clusTransition}

Monitor Transitions in Cluster Solutions.

Description

Model and trace the evolution of clusters evolving over time in cumulative datasets. A typical call to Transition() function involves three essential pieces: the data input (listdata, listclus, overlap), choice of window swSize, and the threshold parameters. The function either receive a list of datasets arriving at time points t_1, t_2, t_3, ..., t_n respectively, list of clustering solutions extracted from cumulative datasets at successive time points, or list of objects of class OverLap (see Details).

Usage

Transition(
  listdata,
  swSize = 1,
  Overlap = NULL,
  listclus = NULL,
  typeind = 1,
  Survival_thrHold = 0.7,
  Split_thrHold = 0.3,
  location_thrHold = 0.3,
  density_thrHold = 0.3,
  k = NULL
)

Arguments

listdata

List of numeric matrices containing datasets d_1, d_2, ..., d_n, or a list of objects that can be coerced to such matrices, for instance, data frames. Each element of the list contain dataset d_i evolving at corresponding time point t_i. The number of clusters in each accumulative data matrix is specified by the argument k.

swSize

Integer value (1, length(listdata)) indicating size of the sliding window. As time goes by, each window consist only objects that fall in the interval [t-swSize+1, t], while older objects are discarded. The default value of swSize = 1 indicate landmark window model, where objects over the entire history are included i.e. [1, t]. Size of sliding window can only be provided if listdata arguments is choosen. If there are total n time stamps and a window of size swSize is selected then entire history would be devided into n-swSize+2 window panes.

Overlap

A list of objects as produced by the Overlap() method. The object contains a matrix of similarity indices between clusters, and the summaries of clusters extracted at first and second clustering.

listclus

listclus is a list of nested lists containing clustering solutions \xi_1, \xi_2, ..., \xi_n at time points {t1, t2,···, tn} respectively, and having the same length as the number of time points. The i^th element of listclus is a nested list that contain set of clusters as matrices at corresponding time point t_i i.e. \xi_i = {X1, X2,···, Xki}. For more details, see Examples.

typeind

Type indicator. typeind = 1 indicates that the raw data is provided in listdata argument, typeind = 2 indicates that the OverLap objects are provided, whereas typeind = 3 indicates that list of clusters are provided using listclus argument.

Survival_thrHold

A numeric value (0,1) indicating minimum threshold value for survival of clusters.

Split_thrHold

A numeric value (0,1) indicating minimum threshold value for split of clusters.

location_thrHold

A numeric value (0,1) indicating minimum threshold value for shift in location of survived clusters.

density_thrHold

A numeric value (0,1) indicating minimum threshold value for changes in density of Survived clusters.

k

Numeric Vector of length vector("numeric", length = n-swSize+2). In the case of landmark window, its length is n, whereas in case of sliding window model its length is n-swSize+2, where n is the number of time points and swSize is the size of the sliding window. This argument should only be provided if listdata argument is chosen.

Details

The Transition() function apply 'MONIC' algorithm presented by Spiliopoulou et.al (2006) to trace changes in cluster solutions of dynamic data sets. The changes includes two types of transition i.e. External transition and Internal transition. External Transition consist of 'Survive', 'Split', 'Merge', 'Disappeared' and 'newly emerged' candidates, while Internal transition consist of changes in location and cohesion of the survived clusters. The listdata argument allow user to import dynamic datasets as a list of matrices or data frames, where each element of the list is a matrix containing data set at a single time point. Each dataset are clustered by 'kmeans' algorithm using default settings of cclust() function from flexclust package. The number of clusters at each time stamp can be import by k argument of the function, which is a vector of integers encompassing number of partitions in corresponding datasets of listdata argument. Once the datasets are clustered, the 'Overlap' matrices in clustering at consecutive time stamps are calculated. The Overlap matrix is calculated by using algorithm presented by Ntoutsi, I., et.al (2012). These 'Overlap' matrices are used to trace the transitions occurred in cluster solutions. Alternatively, the user can directly import list of 'Overlap' matrices between consecutive clustering. The Overlap matrix can be calculated using Overlap(obj, e1, e2) method of the package, where 'obj' is the object of class OverLap and e1, e2 are any clustering at time stamp i and j respectively. As a third option user can provide list of clusters at each data point utilizing listclus argument. Each element of the listclus is a nested list, which holds clusters at a single time stamp.

Value

Returns A list of class Monic.

Survive

Number of clusters survived.

Merged

Number of clusters merged.

Split

Number of clusters split.

Died

Number of clusters disappeared.

new.Emerged

Number of newly emerged clusters, which are not upshot of any external transition.

SurvivalCanx

A vector of integers indicating candidates from the first clustering survived to the latter time stamp

SurvivalCany

A vector of integers indicating candidates of second clustering, that clinch the survival candidates from first clustering.

SplitCanx

A vector of integers indicating candidate(s) that split into various daughter clusters from first clustering.

SplitCany

List of integer vector(s) designating candidates appeared, as a result of splits from first clustering.

MergeCanx

List of integer vector(s) designating Candidates that spliced together to form new clusters. Each element of the list gives candidates that merge together to form one.

MergeCany

Vector of integers designating candidates that emerged, as a result of merger of different candidates from first clustering.

EmergCan

Vector of integers contain Newly emerged candidates, which are not result of any external transition.

SurvivalRatio

The Ratio of survived clusters at second clustering to the total number of clusters at first clustering.

AbsorptionRatio

Ratio of number of merged clusters to total number of clusters at first clustering.

passforwardRatio

Sum of SurvivalRatio and AbsorptionRatio. This gives the ratio of clusters that is also present at second clustering either in the form of survival or absorption.

Overlap

A numeric matrix containing overlap of the two clustering. The rows of matrix indicate first clustering, while columns indicate second clustering.

Centersx

A matrix of cluster centers from first clustering.

Centersx

A matrix of cluster centers from second clustering.

rx

A numeric vector containing radius of each cluster from first clustering.

ry

A numeric vector containing radius of each cluster from second clustering.

avgDisx

A numeric vector containing average distance of points in a cluster from its center in first clustering.

avgDisy

A numeric vector containing average distance of points in a cluster from its center in second clustering.

ShiftLocCan

A vector of integers comprises of Survived candidates with shift in location.

NoShiftLocCan

A vector of integers comprises of Survived candidates with no shift in location.

MoreCompactCan

A Vector of integers comprises of Survived candidates, which becomes more compact.

MoreDiffuseCan

A Vector of integers comprises of Survived candidates, which becomes more diffuse.

NoChangeCompactCan

A Vector of integers comprises of Survived candidates, with no changes in compactness.

Location.diff

A numeric vector containing Distance between the centers of survived clusters.

Compactness.diff

A numeric vector containing Difference between compactness of survived clusters.

Cluster_Tracex

A vector containing result of each cluster from first clustering.

Cluster_Tracey

A Vector representing result of each cluster from second clustering.

clusterMem

A vector of integers (from 1 to k) indicating the point to which cluster it is allocated from second clusterig.

References

Spiliopoulou, M., Ntoutsi, I., Theodoridis, Y., Schult, R. MONIC: modeling and monitoring cluster transitions. In: Eliassi-Rad, T., Ungar, L. H., Craven, M., Gunopulos, D. (eds.) ACM SIGKDD 2006, pp. 706-711. ACM, Philadelphia (2006).

Examples

### Example 1: typeind = 1 (listdata Argument)

d1 <- Data2D[[1]][c("X1", "X2")]
d2 <- Data2D[[2]][c("X1", "X2")]
d3 <- Data2D[[3]][c("X1", "X2")]

listdata <- list(d1, d2, d3)

p <- Transition(listdata = listdata, swSize = 1, typeind = 1, Survival_thrHold = 0.8,
                Split_thrHold = 0.3, density_thrHold = 0.3, location_thrHold = 0.3, k = c(3,3,2))

### Example 2: typeind = 3 (listclus Argument)

D1 <- d1
D2 <- merge(d1, d2, all.x = TRUE, all.y = TRUE)
D3 <- merge(D2, d3, all.x = TRUE, all.y = TRUE)

set.seed(10)
f1 <- kmeans(D1, 3)
C1 <- list()
for(i in 1:3)C1[[i]] <- D1[f1$cluster == i, ]
f2 <- kmeans(D2, 3)
C2 <- list()
for(i in 1:3)C2[[i]] <- D2[f2$cluster == i, ]
f3 <- kmeans(D3, 2)
C3 <- list()
for(i in 1:2)C3[[i]] <- D3[f3$cluster == i, ]

listclus <- list(C1, C2, C3)

p <- Transition(listclus = listclus, typeind = 3, Survival_thrHold = 0.8,
                Split_thrHold = 0.3, density_thrHold = 0.3, location_thrHold = 0.3)

### Example 3: typeind = 3 (Overlap Argument)

obj <- new("OverLap")
Overlap1 <- Overlap(obj, e1 = C1, e2 = C2)
Overlap2 <- Overlap(obj, e1 = C2, e2 = C3)

Overlap <- list(Overlap1, Overlap2)
p <- Transition(Overlap = Overlap, typeind = 2, Survival_thrHold = 0.8,
                Split_thrHold = 0.3, density_thrHold = 0.3, location_thrHold = 0.3)