In data mining and machine learning, k q-flats algorithm[1][2] is an iterative method which aims to partition m observations into k clusters where each cluster is close to a q-flat, where q is a given integer.
q-flat can be characterized by the solution set of a linear system of equations:
In specific, the algorithm starts with an initial set of q-flats
, and proceeds by alternating between the following two steps: Stop whenever the assignments no longer change.
The key part of this algorithm is how to update the cluster, i.e. given m points, how to find a q-flat that minimizes the sum of squares of distances of each point to the q-flat.
The problem can be solved using Lagrangian multiplier method and the solution is as given in the cluster update step.
In addition, the algorithm will terminate at a point that the overall objective cannot be decreased either by a different assignment or by defining new cluster planes for these clusters (such point is called "locally optimal" in the references).
This convergence result is a consequence of the fact that problem (P2) can be solved exactly.
The same convergence result holds for k-means algorithm because the cluster update problem can be solved exactly.
k q-flats algorithm for the case that data lie in a few low-dimensional spaces.
k-means algorithm is desirable for the case the clusters are of the ambient dimension.
For example, the dimension of a 1024-by-1024 image is about 106, which is far too high for most signal processing algorithms.
One way to get rid of the high dimensionality is to find a set of basis functions, such that the high-dimensional signal can be represented by only a few basis functions.
where The idea of k q-flats algorithm is similar to sparse dictionary learning in nature.
If we restrict the q-flat to q-dimensional subspace, then the k q-flats algorithm is simply finding the closed q-dimensional subspace to a given signal.
Sparse dictionary learning is also doing the same thing, except for an additional constraints on the sparsity of the representation.
Mathematically, it is possible to show that k q-flats algorithm is of the form of sparse dictionary learning with an additional block structure on R. Let
denote concatenation of basis of K flats, it is easy to show that the k q-flat algorithm is the same as the following.
The block structure of R refers the fact that each signal is labeled to only one flat.
Comparing the two formulations, k q-flat is the same as sparse dictionary modeling when
and with an additional block structure on R. Users may refer to Szlam's paper[3] for more discussion about the relationship between the two concept.
Classification is a procedure that classifies an input signal into different classes.
Classification algorithms usually require a supervised learning stage.
In the classification stage, a new observation is classified into a class by using the characteristics that were already trained.
However, the classification performance can be further improved if we impose some structure on the flats.
One possible choice is to require different flats from different class be sufficiently far apart.
Some researchers[4] use this idea and develop a discriminative k q-flat algorithm.
On the contrary, if data lies in a very high dimension space but near a common center, then k-means algorithm is a better way than k q-flat algorithm to represent the data.
In k-metrics, error is measured by the following Mahalanobis metric.
If A is the identity matrix, then the Mahalanobis metric is exactly the same as the error measure used in k-means.