K-subspace clusteringΒΆ

K-subspace clustering [HYL+03] is a generalization of K-means [see here] and K-plane clustering. In K-means, we cluster points around centroids, in K-plane, we cluster points around hyperplanes, and in K-subspace clustering, we cluster points around subspaces. This algorithm requires the number of subspaces \(K\) and their dimensions \(\{ D_1, \dots, D_K \}\) to be known in advance. We present the version for linear subspaces with \(\mu_k = 0\). Fitting the dataset \(Y\) into \(K\)-subspaces can be reduced to means identifying an orthogonal basis \(Q_k \in \RR^{M \times D_k}\) for each subspace. If the data points fit perfectly, then for every \(s\) in \(\{ 1, \dots , S\}\) there exists a \(k\) in \(\{1, \dots, K\}\) such that \(y_s = Q_k \alpha_s\) (i.e. \(y_s\) belongs to \(k\)-th subspace with basis \(Q_k\)). If the data point belongs to an intersection of two or more subspaces, then we can arbitrarily assign the data point to one of the subspaces.

Lastly, data points may not be lying perfectly in the subspace. The orthoprojector for each subspace is given by \(Q_k Q_k^T\). Thus, the projection of a point \(y_s\) on a subspace \(\UUU_k\) is \(Q_k Q_k^T y_s\) and the error is \((I - Q_k Q_k^T) y_s\). The (squared) distance from the subspace is then \(\|(I - Q_k Q_k^T) y_s\|_2^2\). The point can be assigned to the subspace closest to it.

Given that a set of points \(Y_k\) are assigned to the subspace \(\UUU_k\), the orthonormal basis \(Q_k\) can be estimated for \(\UUU_k\) by performing principal component analysis here.

This gives us a straightforward iterative method for fitting the subspaces.

  • Start with initial subspace bases \(Q_1^{(0)}, \dots, Q_K^{(0)}\).
  • Assign points to subspaces by using minimum distance criteria.
  • Estimate the bases for each subspace.
  • Repeat steps 2 and 3 till the clustering keeps changing.

Initial subspaces can be chosen randomly.