gk: Gustafson-Kessel Clustering
In ppclust: Probabilistic and Possibilistic Cluster Analysis

View source: R/gk.R

gk	R Documentation

Gustafson-Kessel Clustering

Description

Partitions a numeric data set by using the Gustafson-Kessel (GK) clustering algorithm (Gustafson & Kessel, 1979). Unlike FCM using the Euclidean distance, GK uses cluster specific Mahalanobis distance.

Usage

gk(x, centers, memberships, m=2,  
   dmetric="sqeuclidean", pw = 2, alginitv="kmpp", 
   alginitu="imembrand", nstart=1, iter.max=1e03, con.val=1e-09, 
   fixcent=FALSE, fixmemb=FALSE, stand=FALSE, numseed)

Arguments

`x`	a numeric vector, data frame or matrix.
`centers`	an integer specifying the number of clusters or a numeric matrix containing the initial cluster centers.
`memberships`	a numeric matrix containing the initial membership degrees. If missing, it is internally generated.
`m`	a number greater than 1 to be used as the fuzziness exponent or fuzzifier. The default is 2.
`dmetric`	a string for the distance metric. The default is sqeuclidean for the squared Euclidean distances. See `get.dmetrics` for the alternative options.
`pw`	a number for the power of Minkowski distance calculation. The default is 2 if the `dmetric` is minkowski.
`alginitv`	a string for the initialization of cluster prototypes matrix. The default is kmpp for K-means++ initialization method (Arthur & Vassilvitskii, 2007). For the list of alternative options see `get.algorithms`.
`alginitu`	a string for the initialization of memberships degrees matrix. The default is imembrand for random sampling of initial membership degrees.
`nstart`	an integer for the number of starts for clustering. The default is 1.
`iter.max`	an integer for the maximum number of iterations allowed. The default is 1000.
`con.val`	a number for the convergence value between the iterations. The default is 1e-09.
`fixcent`	a logical flag to make the initial cluster centers not changed along the different starts of the algorithm. The default is `FALSE`. If it is `TRUE`, the initial centers are not changed in the successive starts of the algorithm when the `nstart` is greater than 1.
`fixmemb`	a logical flag to make the initial membership degrees not changed along the different starts of the algorithm. The default is `FALSE`. If it is `TRUE`, the initial memberships are not changed in the successive starts of the algorithm when the `nstart` is greater than 1.
`stand`	a logical flag to standardize data. Its default value is `FALSE`. If its value is `TRUE`, the data matrix `x` is standardized.
`numseed`	a seeding number to set the seed of R's random number generator.

Details

As an extension of basic FCM algorithm, Gustafson and Kessel (GK) clustering algorithm employs an adaptive distance norm in order to detect clusters with different geometrical shapes (Babuska, 2001; Correa et al, 2011).

The objective function of GK is:

J_{GK}(\mathbf{X}; \mathbf{V}, \mathbf{A}, \mathbf{U}) = \sum\limits_{i=1}^n \sum\limits_{j=1}^k u_{ij}^m d_{A_j}(\vec{x}_i, \vec{v}_j)

In the above equation d_{A_j}(\vec{x}_i, \vec{v}_j) is the Mahalanobis distance between the data object \vec{x}_j and cluster prototype \vec{v}_i.

d_{A_j}(\vec{x}_i, \vec{v}_j) = (\vec{x}_i - \vec{v}_j)^T \mathbf{A}_j (\vec{x}_i - \vec{v}_j)

As it is understood from the above equation, each cluster has its own norm-inducing matrix in GK, so that the norm matrix \mathbf{A} is a k-length tuples of the cluster-specific norm-inducing matrices:

\mathbf{A}=\{\mathbf{A}_1, \mathbf{A}_2, \dots, \mathbf{A}_k\}.

The objective function of GK cannot be directly minimized with respect to \mathbf{A}_j since it is linear in \mathbf{A}_j. For obtaining a feasible solution, \mathbf{A}_j must be constrained in some way. One of the usual ways of accomplishing this is to constrain the determinant of \mathbf{A}_j (Babuska, 2001):

\mid\mathbf{A}_j\mid=\rho_j \;,\; \rho_j > 0 \;,\; 1 \leq j \leq k

Allowing the matrix \mathbf{A}_j to vary with its determinant fixed corresponds to optimizing the shape of cluster while its volume remains constant. By using the Lagrange-multiplier method, the norm-inducing matrix for the cluster j is defined as follows (Babuska, 2001):

\mathbf{A}_j = [\rho_i \; det(\mathbf{F}_j)]^{-1/n}{\mathbf{F}_j}^{-1},

where:

n is the number of data objects,

\rho_j represents the volume of cluster j,

\mathbf{F}_j is the fuzzy covariance matrix for the cluster j, and is calculated as follows:

\mathbf{F}_j = \frac{\sum\limits_{i=1}^n u_{ij}^m \; d^2(\vec{x}_i, \vec{v}_j)}{\sum\limits_{i=1}^n u_{ij}^m}

m is the fuzzifier to specify the amount of fuzziness for the clustering; 1\leq m\leq \infty. It is usually chosen as 2.

GK must satisfy the following constraints:

\sum\limits_{j=1}^k u_{ij} = 1 \;\;;\; 1 \leq i \leq n

\sum\limits_{i=1}^n u_{ij} > 0 \;\;;\; 1 \leq j \leq k

The objective function of GK is minimized by using the following update equations:

u_{ij} =\Bigg[\sum\limits_{j=1}^k \Big(\frac{d_{A_j}(\vec{x}_i, \vec{v}_j)}{d_{A_l}(\vec{x}_i, \vec{v}_l)}\Big)^{1/(m-1)} \Bigg]^{-1} \;\;; 1 \leq i \leq n,\; 1 \leq l \leq k

\vec{v}_{j} =\frac{\sum\limits_{i=1}^n u_{ij}^m \vec{x}_i}{\sum\limits_{i=1}^n u_{ij}^m} \;\;; 1 \leq j \leq k

Value

an object of class ‘ppclust’, which is a list consists of the following items:

`x`	a numeric matrix containing the processed data set.
`v`	a numeric matrix containing the final cluster prototypes (centers of clusters).
`u`	a numeric matrix containing the fuzzy memberships degrees of the data objects.
`d`	a numeric matrix containing the distances of objects to the final cluster prototypes.
`k`	an integer for the number of clusters.
`m`	a number for the fuzzifier.
`cluster`	a numeric vector containing the cluster labels found by defuzzying the fuzzy membership degrees of the objects.
`csize`	a numeric vector containing the number of objects in the clusters.
`iter`	an integer vector for the number of iterations in each start of the algorithm.
`best.start`	an integer for the index of start that produced the minimum objective functional.
`func.val`	a numeric vector for the objective function values in each start of the algorithm.
`comp.time`	a numeric vector for the execution time in each start of the algorithm.
`stand`	a logical value, `TRUE` shows that data set `x` contains the standardized values of raw data.
`wss`	a number for the within-cluster sum of squares for each cluster.
`bwss`	a number for the between-cluster sum of squares.
`tss`	a number for the total within-cluster sum of squares.
`twss`	a number for the total sum of squares.
`algorithm`	a string for the name of partitioning algorithm. It is ‘FCM’ with this function.
`call`	a string for the matched function call generating this ‘ppclust’ object.

Author(s)

Zeynel Cebeci & Cagatay Cebeci

References

Arthur, D. & Vassilvitskii, S. (2007). K-means++: The advantages of careful seeding, in Proc. of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1027-1035. http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf

Gustafson, D. E. & Kessel, W. C. (1979). Fuzzy clustering with a fuzzy covariance matrix. In Proc. of IEEE Conf. on Decision and Control including the 17th Symposium on Adaptive Processes, San Diego. pp. 761-766. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1109/CDC.1978.268028")}

Babuska, R. (2001). Fuzzy and neural control. DISC Course Lecture Notes. Delft University of Technology. Delft, the Netherlands. https://tr.scribd.com/document/209211977/Fuzzy-and-Neural-Control.

Correa, C., Valero, C., Barreiro, P., Diago, M. P., & Tardáguila, J. (2011). A comparison of fuzzy clustering algorithms applied to feature extraction on vineyard. In Proc. of the 14th Conf. of the Spanish Assoc. for Artificial Intelligence. http://oa.upm.es/9246/

Examples

## Not run: 
# Load dataset iris 
data(iris)
x <- iris[,-5]

# Initialize the prototype matrix using K-means++
v <- inaparc::kmpp(x, k=3)$v

# Initialize the membership degrees matrix 
u <- inaparc::imembrand(nrow(x), k=3)$u

# Run FCM with the initial prototypes and memberships
gk.res <- gk(x, centers=v, memberships=u, m=2)

# Show the fuzzy membership degrees for the top 5 objects
head(gk.res$u, 5)

## End(Not run)

ppclust documentation built on May 29, 2024, 7:20 a.m.