Solving the problem of clustering using gradient descent

Hey. In this article, we will discuss the method of data clustering using the gradient descent method . To be honest, this method is more academic than practical. I needed to implement this method for demonstration purposes for a machine learning course to show how identical tasks can be solved in various ways. Although of course, if you plan to cluster data using a differentiated metric, for which it is computationally more difficult to find a centroid , rather than counting a gradient on some data set, then this method may be useful. So, if you're wondering how to solve the k-means clustering problem with a generalized metric using the gradient descent method, I ask for cat. Code in R.

Data

First, let's discuss the set of data on which we will test the algorithms. For testing uses a lot of data from the sensors of smartphones : only 563 fields in 7352 observations; from the bottom 2 fields are allocated for the user ID and type of action. The set is created to classify user actions depending on sensor readings, a total of 6 actions (WALKING, WALKING_UPSTAIRS, WALKING_DOWNSTAIRS, SITTING, STANDING, LAYING). A more detailed description of the set can be found at the above link.

As you understand it, to visualize such a multitude without reducing the dimensionality is a bit problematic. To reduce the dimension, the principal component method was used; for this, you can use the standard means of the R language, or implement this method in the same language from my repository . Let's take a look at what the original set looks like, projected onto the first and third main components.


')


Different colors indicate different actions, then we will use this two-dimensional set to test and visualize the results of clustering.

K-means algorithm cost function

We introduce the following notation:

• - many centroids corresponding clusters
• - the original set of data that must be clustered
• - k-th cluster, a subset of the original set

Now consider the cost function of the classic k-means algorithm :

those. the algorithm minimizes the total square deviation of cluster elements from the centroid. In other words, the sum of squares of the Euclidean distance of cluster elements from the corresponding centroid is minimized:
where f is in this case the Euclidean distance.

As it is known, there is an effective learning algorithm based on the expectation-maximization algorithm for solving this problem. Let's take a look at the result of this algorithm, using the built-in function in R:

Gradient descent

The gradient descent algorithm itself is pretty simple, the point is to move in small steps towards the opposite direction of the gradient, for example, the back propagation error algorithm , or the contrastive divergence algorithm for learning the limited Boltzmann machine , works. First of all, it is necessary to calculate the gradient of the objective function, or the partial derivatives of the objective function from the model parameters.

since we left the section on classic k-means, then f can in principle be any measure of distance, not necessarily the Euclidean metric

But there is a problem, we do not know at this stage what the partition of the set X into clusters is. Let's try to reformulate the objective function in such a way that we write it in the form of one formula that would be easy to differentiate: the sum of the minimum distances from each element of the set to one of the three centroids. This formula is as follows:



Now let's find the derivative of the new objective function:



Well, it remains to find out what the derivative of the minimum is equal to, but everything turns out to be simple: if the a- th centroid is really the one to which the distance is minimal from the current element of the set, then the derivative of the expression is equal to the derivative of the square of the distance along the vector element, otherwise case is zero:

Method implementation

As you understand, all the steps from the previous paragraph can be performed without squaring the distance. This was done in the implementation of this method. The method receives as parameters the distance function and the function of calculating the partial derivative of the distance function between two vectors by the component of the second vector, for example, “half the square Euclidean distance” (convenient to use because the derivative is very simple), as well as the function of the gradient descent :







Let's take a look at the result of clustering and make sure that it is almost identical.



And this is how the dynamics of the value function from iteration of both algorithms look like:

Conclusion

Let's first say a few words about what happened in our test. We got a decent split of the two-dimensional set into three clusters, we visually see that the clusters do not overlap much and we can completely build models for recognizing actions for each cluster, thus we get some hybrid model (one cluster contains basically one action, the other two, and the third three).

Take a look at the complexity of the algorithms for clustering using the Euclidean distance, consider only one iteration (analyzing the number of iterations is not a trivial task at all). Let k be the number of clusters, n is the dimension of the data, m is the amount of data (k <= m). In the extreme case, k = m.

• EM version:
• GD version:

In general, mathematically, both algorithms are on the same level, but we know that one is slightly higher.

You can find all the code here .