# Monitor Transitions in Cluster Solutions. 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 ). ```r 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. ## Returns 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. ## 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. ## Examples ```r ### 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) ``` ## 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).

Transition function