POCS-based Clustering Algorithm Explained

Each data has different importance

Cluster analysis (or clustering) is a data analysis technique that explores and groups a set of vectors (or data points) in such a way that vectors in the same cluster are more similar to one another than to those in other clusters. Clustering algorithms are widely used in numerous applications, e.g., data analysis, pattern recognition, and image processing.

This article reviews a new clustering algorithm based on the method of Projection onto Convex Sets (POCS), called POCS-based clustering algorithm. The original paper was introduced in .

Convex Sets

A convex set is defined as a set of data points in which a line segment connecting any two points x1 and x2 in the set is completely subsumed in this set. Following that definition of a convex set, empty set ∅, singleton set, line segment, hyperplane, and Euclidian ball are considered to be convex sets. A data point is also considered to be a convex set as it is a singleton set (a set with exactly one element). That directs to a new path that the concept of POCS can be applied to clustering data points.

Projection onto Convex Sets (POCS)

Let me briefly review the concept of POCS (without equations). The method of POCS can be roughly divided into 2 forms: Alternating and Parallel.

Alternating POCS

Starting from an arbitrary point in the data space, the alternating projections from this point onto two (or more) intersecting convex sets will converge to a point within the intersection of the sets. A graphical illustration is shown below.

When the convex sets do not intersect, the alternating projections will converge to greedy limit cycles which are dependent on the orders of the projections.

Parallel POCS

Different from the alternating form, the parallel form of POCS performs projections simultaneously from the data point onto all the convex sets and each projection has a weight of importance. For two non-empty intersection convex sets, similarly to the alternating version, the parallel projections converge to a point in the intersection of the sets.

In the case of non-intersecting convex sets, the projections will converge to a minimization solution. The main idea of the POCS-based clustering algorithm came up from this property.

For more details of POCS, you can visit the

. The descriptions of these datasets are summarized in the table below.

In the paper, the author compared the performance of the POCS-based clustering algorithm against other conventional clustering methods including the K-Means and Fuzzy C-Means algorithms. The evaluations in terms of execution time and clustering error are summarized in the following tables.

The visual clustering results are also illustrated in the following figure.

For more details, you can drop by the original paper  (preprint) or .

I am so glad to welcome you to my Facebook page for sharing things regarding Machine Learning:

Thanks for spending time!

on Medium, where people are continuing the conversation by highlighting and responding to this story.