Skip to contents

G-means Clustering

Source: R/gmeans.R
gmeans.Rd

Perform G-means clustering on a data matrix.

Usage

gmeans(x, k_init = 1L, k_max = 10L, level = 1e-04, ...)

Arguments

x

(matrix())
Numeric matrix of data, or a data frame with all numeric columns. Logical input is coerced to a 0/1 matrix. Missing and infinite values are not allowed and the matrix must have at least one row and one column.

k_init

(integer(1))
Initial amount of centers. Default is 1L.

k_max

(integer(1))
Maximum amount of centers. Must be greater than or equal to k_init. Default is 10L.

level

(numeric(1))
Significance level for the Anderson-Darling test. Default is 0.0001. A larger level such as 0.01 can work better for clusters with fewer than about 50 points. See ad.test() for more information.

...

(any)
Additional arguments passed to stats::kmeans(), except centers, which is set by k_init. nstart has no effect since the initial centers are always given as a matrix.

Value

An object of class c("gmeans", "kmeans") with the components of a stats::kmeans() object plus k_init, k_max, and level, the settings used to fit the model. See gmeans_tidiers for summarizing the result as data frames.

Details

The G-means clustering algorithm is an extension of the traditional k-means algorithm that automatically determines the number of clusters by iteratively testing the Gaussianity of data within clusters. The process begins with a specified initial number of clusters (k_init) and iteratively increases the number of clusters until it reaches the specified maximum (k_max) or the data within clusters is determined to be Gaussian at the specified significance level (level).

The algorithm is outlined as follows:

  1. Let \(C\) be the initial set of centers (usually \(C \leftarrow \{\bar{x}\}\)).

  2. Perform k-means clustering on the dataset \(X\) using the current set of centers \(C\), i.e., \(C \leftarrow \text{kmeans}(C, X)\).

  3. For each center \(c_j\), identify the set of data points \(\{x_i \mid \text{class}(x_i) = j\}\) that are assigned to \(c_j\).

  4. Use the Anderson-Darling test to check if the set of data points \(\{x_i \mid \text{class}(x_i) = j\}\) follows a Gaussian distribution at the confidence level \(\alpha\).

  5. If the data points appear Gaussian, keep \(c_j\). Otherwise, replace \(c_j\) with two new centers, found by k-means on the cluster started from \(c_j \pm s \sqrt{2 \lambda / \pi}\), where \(s\) is the main principal component of the cluster and \(\lambda\) its eigenvalue.

  6. Repeat from step 2 until no more centers are added.

References

Hamerly, Greg, Elkan, Charles (2003). “Learning the k in k-means.” In Thrun S, Saul L, Schölkopf B (eds.), Advances in Neural Information Processing Systems, volume 16. https://proceedings.neurips.cc/paper_files/paper/2003/file/234833147b97bb6aed53a8f4f1c7a7d8-Paper.pdf.

Examples

set.seed(123)
x <- rbind(
  matrix(rnorm(100, sd = 0.3), ncol = 2),
  matrix(rnorm(100, mean = 1, sd = 0.3), ncol = 2)
)
colnames(x) <- c("x", "y")
cl <- gmeans(x)