Type:	Package
Title:	Circular, Periodic, or Framed Data Clustering: Fast, Optimal, and Reproducible
Version:	0.0.4
Date:	2021-07-27
Author:	Tathagata Debnath [aut], Joe Song [aut, cre]
Maintainer:	Joe Song <joemsong@cs.nmsu.edu>
Description:	Fast, optimal, and reproducible clustering algorithms for circular, periodic, or framed data. The algorithms introduced here are based on a core algorithm for optimal framed clustering the authors have developed (Debnath & Song 2021) <doi:10.1109/TCBB.2021.3077573>. The runtime of these algorithms is O(K N log^2 N), where K is the number of clusters and N is the number of circular data points. On a desktop computer using a single processor core, millions of data points can be grouped into a few clusters within seconds. One can apply the algorithms to characterize events along circular DNA molecules, circular RNA molecules, and circular genomes of bacteria, chloroplast, and mitochondria. One can also cluster climate data along any given longitude or latitude. Periodic data clustering can be formulated as circular clustering. The algorithms offer a general high-performance solution to circular, periodic, or framed data clustering.
VignetteBuilder:	knitr
License:	LGPL (≥ 3)
Encoding:	UTF-8
RoxygenNote:	7.1.1
LinkingTo:	Rcpp
Imports:	Ckmeans.1d.dp, graphics, plotrix, Rcpp, Rdpack, stats, reshape2
Suggests:	ape, ggplot2, knitr, rmarkdown, testthat
NeedsCompilation:	yes
RdMacros:	Rdpack
Packaged:	2021-07-28 07:01:31 UTC; joesong
Repository:	CRAN
Date/Publication:	2021-07-28 07:40:05 UTC

Circular Data Clustering

Description

Perform clustering on circular data to minimize the within-cluster sum of squared distances.

Usage

CirClust(O, K, Circumference, method = c("FOCC", "HEUC", "BOCC"))

Arguments

Details

By circular data, we broadly refer to data points on any non-self-intersecting loop. In clustering N circular points into K clusters, the "FOCC" algorithm is reproducible with runtime O(K N \log^2 N) (Debnath and Song 2021); The "HEUC" algorithm, not always reproducible, calls the kmeans function repeatedly; The "BOCC" algorithm with runtime O(KN^2), reproducible but slow, is done via repeatedly calling the Ckmeans.1d.dp function.

Value

An object of class "CirClust" which has a plot method. It is a list with the following components:

References

Debnath T, Song M (2021). “Fast optimal circular clustering and applications on round genomes.” IEEE/ACM Transactions on Computational Biology and Bioinformatics. doi: 10.1109/TCBB.2021.3077573.

Examples

O <- c(1,2, 10,11,12,13,14,15, 27,28,29,30,31,32, 40,41)

K <- 3

Circumference <- 42

# Perform circular clustering:
output <- CirClust(O, K, Circumference)

# Visualize the circular clusters:
opar <- par(mar=c(1,1,2,1))
plot(output)
par(opar)

Framed Data Clustering

Description

Find a frame of given size, among all possible such frames on the input data, to minimize the minimum within-cluster sum of square distances.

Usage

FramedClust(
  X,
  K,
  frame.size,
  first.frame = 1,
  last.frame = length(X) - frame.size + 1,
  method = c("linear.polylog", "kmeans", "Ckmeans.1d.dp")
)

Arguments

Details

The method option "linear.polylog" (default) performs fast optimal framed clustering. The runtime is O(K N \log^2 N) (Debnath and Song 2021).

The "kmeans" option repeatedly calling the heuristic k-means algorithm in all frames without any guarantee of cluster optimality.

The method option "Ckmeans.1d.dp" performs optimal framed clustering by repeatedly finding the best clustering within each frame using the "Ckmeans.1d.dp" method. At a runtime of O(K N^2), the algorithm is slow but optimal. It is included to provide a baseline.

Value

An object of class "FramedClust" which has a plot method. It is a list with the following components:

References

Debnath T, Song M (2021). “Fast optimal circular clustering and applications on round genomes.” IEEE/ACM Transactions on Computational Biology and Bioinformatics. doi: 10.1109/TCBB.2021.3077573.

Examples

N <- 100
X <- rnorm(N)
K <- 5
frame.size <- 60

result <- FramedClust(X, K, frame.size)
plot(result, main="Example 1. Framed clustering on all frames")

frame.size <- 40
first.frame <- 30
last.frame <- 50
method <- "linear.polylog"

result <- FramedClust(X, K, frame.size, first.frame,
                      last.frame, method)
plot(result, main="Example 2. Framed clustering on a subset of frames")

Plot Method for Circular Data Clustering

Description

The plot method for circular data clustering result object of class CirClust. It visualizes circular clusters on the input data.

Usage

## S3 method for class 'CirClust'
plot(
  x,
  xlab = "",
  ylab = "",
  main = NULL,
  sub = "",
  col.clusters = c("blue", "red3", "green3", "orange", "purple", "brown"),
  axes = FALSE,
  xlim = c(-1.75, 1.75),
  ylim = c(-1.75, 1.75),
  fill = "floralwhite",
  border = "gray36",
  border.lty = "dotted",
  ...
)

Arguments

Value

A copy of the input object of class CirClust.

Examples

opar <- par(mar=c(1,1,2,1))
# Example 1. Circular data clustering
n <- 100
Circumference <- 7
O <- runif(n, 0, Circumference)
result <- CirClust(O, K=3, Circumference=Circumference)
plot(result, fill="mintcream", main="Example 1. Circular clustering")


# Example 2. Circular data clustering
n <- 40
m <- 5
O <- c(rnorm(n,mean=5,sd=m), rnorm(n,mean=15,sd=m), rnorm(n,mean=26,sd=m))
K <- 3
Circumference <- 28

result <- CirClust(O, K, Circumference, method = "FOCC")

color <- c("royalblue", "green3", "firebrick") # c("#0000CD","#808080", "#DC143C")

par(mar=c(1,1,2,1))

plot(result, col.clusters = color, fill="floralwhite",
     main="Example 2. Circular clustering")


# Example 3. Periodic data clustering
n <- 100
period <- 5.2
O <- rnorm(n)
result <- CirClust(O, K=5, Circumference=period)
plot(result, fill="navy", border="gray", border.lty="dotted",
     main="Example 3. Periodic clustering")

par(opar)

Plot Method for Framed Data Clustering

Description

The plot method for framed data clustering result object. It visualizes clusters on the input data that are within a best frame.

Usage

## S3 method for class 'FramedClust'
plot(
  x,
  xlab = NULL,
  ylab = NULL,
  main = NULL,
  sub = NULL,
  col.clusters = c("blue", "red3", "green3", "orange", "purple", "brown"),
  ...
)

Arguments

Value

An object of class "FramedClust", identical to the input x

Examples

N <- 100
X <- rchisq(N, 5)
K <- 3
frame.size <- 40

result <- FramedClust(X, K, frame.size)

plot(result)