k q-flats

In data mining and machine learning, k q-flats algorithm 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.

It is a generalization of the k-means algorithm. In k-means algorithm, clusters are formed in the way that each cluster is close to one point, which is a 0-flat. k q-flats algorithm gives better clustering result than k-means algorithm for some data set.

Description

Problem formulation

Given a set A of m observations [math]\displaystyle{ (a_1, a_2, \dots, a_m) }[/math] where each observation [math]\displaystyle{ a_i }[/math] is an n-dimensional real vector, k q-flats algorithm aims to partition m observation points by generating k q-flats that minimize the sum of the squares of distances of each observation to a nearest q-flat.

A q-flat is a subset of [math]\displaystyle{ \Reals^n }[/math] that is congruent to [math]\displaystyle{ \Reals^q }[/math]. For example, a 0-flat is a point; a 1-flat is a line; a 2-flat is a plane; a [math]\displaystyle{ n-1 }[/math]-flat is a hyperplane. q-flat can be characterized by the solution set of a linear system of equations: [math]\displaystyle{ F = \left\{ x \mid x\in \Reals^n, W'x = \gamma \right\} }[/math], where [math]\displaystyle{ W \in \Reals^{n\times (n-q)} }[/math], [math]\displaystyle{ \gamma \in \Reals^{1\times (n-q)} }[/math].

Denote a partition of [math]\displaystyle{ \{1,2,\dots, n\} }[/math] as [math]\displaystyle{ S = (S_1,S_2,\dots,S_k) }[/math]. The problem can be formulated as

[math]\displaystyle{ \min_{F_l,l=1,\dots,k \text{ are q-flats}} \min_S \sum_{l=1}^k \sum_{a_j \in S_i} \|a_j - P_{F_i}(a_j) \|^2, }[/math]

(P1)

where [math]\displaystyle{ P_{F_i}(a_j) }[/math] is the projection of [math]\displaystyle{ a_j }[/math] onto [math]\displaystyle{ F_i }[/math]. Note that [math]\displaystyle{ \|a_j - P_{F_i}(a_j) \| = \operatorname{dist}(a_j,F_l) }[/math] is the distance from [math]\displaystyle{ a_j }[/math] to [math]\displaystyle{ F_l }[/math].

Algorithm

The algorithm is similar to the k-means algorithm (i.e. Lloyd's algorithm) in that it alternates between cluster assignment and cluster update. In specific, the algorithm starts with an initial set of q-flats [math]\displaystyle{ F_l^{(0)} = \left\{x\in R^n \mid \left(W_l^{(0)}\right)' x = \gamma_l^{(0)} \right\}, l=1,\dots, k }[/math], and proceeds by alternating between the following two steps:

Cluster Assignment

(given q-flats, assign each point to closest q-flat): the i-th cluster is updated as [math]\displaystyle{ S_i^{(t)} = \left\{a_j \mid \left\|(W_i^{(t)})'a_j - \gamma_i^{(t)} \right\|_F = \min_{l=1,\dots,k} \left\|(W_l^{(t)})'a_j -\gamma_l^{(t)} \right\|_F \right \}. }[/math]

Cluster Update

(given cluster assignment, update the q-flats): For [math]\displaystyle{ l = 1,\dots, k }[/math], let [math]\displaystyle{ A(l)\in R^{m(l)\times n} }[/math] with rows corresponding to all [math]\displaystyle{ a_i }[/math] assigned to cluster l. Set [math]\displaystyle{ W_l^{(t+1)} }[/math] to be the matrix whose columns are the orthonormal eigenvectors corresponding to the [math]\displaystyle{ (n-q) }[/math] least eigenvalues of [math]\displaystyle{ A(l)' \left(I - \tfrac{ee'}{m}\right) A(l) }[/math] and [math]\displaystyle{ \gamma_l^{(t+1)} = \frac{e' A(l) W_l^{(t+1)}}{m} }[/math].

Stop whenever the assignments no longer change.

The cluster assignment step uses the following fact: given a q-flat [math]\displaystyle{ F_l = \{x \mid W'x=\gamma \} }[/math] and a vector a, where [math]\displaystyle{ W' W = I }[/math], the distance from a to the q-flat [math]\displaystyle{ F_l }[/math] is [math]\displaystyle{ \operatorname{dist}(a,F_l) = \min_{x:W' x = \gamma} \left\|x-a \right\|_F^2 = \left\|W(W'W)^{-1}(W' x - \gamma) \right\|_F^2 = \left\|W' x-\gamma \right\|_F^2. }[/math]

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. Mathematically, this problem is: given [math]\displaystyle{ A\in R^{m\times n}, }[/math] solve the quadratic optimization problem

[math]\displaystyle{ \min_{W\in R^{n\times (n-q)},\gamma \in R^{1\times (n-q)}} \left\|AW - e\gamma \right\|_F^2, }[/math] subject to [math]\displaystyle{ W' W = I, }[/math]

(P2)

where [math]\displaystyle{ A \in \R^{m \times n} }[/math] is given, and [math]\displaystyle{ e = (1, \dots, 1)' \in \R^{m \times 1} }[/math].

The problem can be solved using Lagrangian multiplier method and the solution is as given in the cluster update step.

It can be shown that the algorithm will terminate in a finite number of iterations (no more than the total number of possible assignments, which is bounded by [math]\displaystyle{ k^m }[/math]). 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.

Relation to other machine learning methods

k-means algorithm

k q-flats algorithm is a generalization of k-means algorithm. In fact, k-means algorithm is k 0-flats algorithm since a point is a 0-flat. Despite their connection, they should be used in different scenarios. 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, if all observations lie in two lines, k q-flats algorithm with [math]\displaystyle{ q = 1 }[/math] may be used; if the observations are two Gaussian clouds, k-means algorithm may be used.

Sparse Dictionary Learning

Natural signals lie in a high-dimensional space. For example, the dimension of a 1024-by-1024 image is about 10⁶, 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. In other words, the coefficients of the signal representation lies in a low-dimensional space, which is easier to apply signal processing algorithms. In the literature, wavelet transform is usually used in image processing, and fourier transform is usually used in audio processing. The set of basis functions is usually called a dictionary.

However, it is not clear what is the best dictionary to use once given a signal data set. One popular approach is to find a dictionary when given a data set using the idea of Sparse Dictionary Learning. It aims to find a dictionary, such that the signal can be sparsely represented by the dictionary. The optimization problem can be written as follows.

[math]\displaystyle{ \min_{B,R} \|X - BR\|_{F}^{2} }[/math] subject to [math]\displaystyle{ \|R_i\|_0 \leq q }[/math]

where

• X is a d-by-N matrix. Each columns of X represent a signal, and there are total N signals.
• B is a d-by-l matrix. Each columns of B represent a basis function, and there are total l basis functions in the dictionary.
• R is a l-by-N matrix. [math]\displaystyle{ R_i }[/math] (i-th columns of R) represent the coefficients when we use the dictionary B to represent the i-th columns of X.
• [math]\displaystyle{ \|v\|_0 }[/math] denotes the zero-norm of the vector v.
• [math]\displaystyle{ \|V\|_{F} }[/math] denotes the Frobenius norm of matrix V.

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 [math]\displaystyle{ B_k }[/math] be a [math]\displaystyle{ d \times q }[/math] matrix, where columns of [math]\displaystyle{ B_k }[/math] are basis of the k-th flat. Then the projection of the signal x to the k-th flat is [math]\displaystyle{ B_k r_k }[/math], where [math]\displaystyle{ r_k }[/math] is a q-dimensional coefficient. Let [math]\displaystyle{ B = [B_1, \cdots, B_K] }[/math] denote concatenation of basis of K flats, it is easy to show that the k q-flat algorithm is the same as the following.

[math]\displaystyle{ \min_{B,R} \|X - BR\|_{F}^{2} }[/math] subject to [math]\displaystyle{ \|R_i\|_0 \leq q }[/math] and R has a block structure.

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 [math]\displaystyle{ l = K \times q }[/math] and with an additional block structure on R. Users may refer to Szlam's paper for more discussion about the relationship between the two concept.

Applications and variations

Classification

Classification is a procedure that classifies an input signal into different classes. One example is to classify an email into spam or non-spam classes. Classification algorithms usually require a supervised learning stage. In the supervised learning stage, training data for each class is used for the algorithm to learn the characteristics of the class. In the classification stage, a new observation is classified into a class by using the characteristics that were already trained.

k q-flat algorithm can be used for classification. Suppose there are total of m classes. For each class, k flats are trained a priori via training data set. When a new data comes, find the flat that is closest to the new data. Then the new data is associate to class of the closest flat.

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 use this idea and develop a discriminative k q-flat algorithm.

K-metrics

In k q-flats algorithm, [math]\displaystyle{ \|x - P_{F} (x)\|^2 }[/math] is used to measure the representation error. [math]\displaystyle{ P_{F} (x) }[/math] denotes the projection of x to the flat F. If data lies in a q-dimension flat, then a single q-flat can represent the data very well. 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. It is because k-means algorithm use [math]\displaystyle{ \|x - x_c\|^2 }[/math] to measure the error, where [math]\displaystyle{ x_c }[/math] denotes the center. K-metrics is a generalization that use both the idea of flat and mean. In k-metrics, error is measured by the following Mahalanobis metric.

[math]\displaystyle{ \left\|x - y\right\|_{A}^2 = (x-y)^\mathsf{T} A (x-y) }[/math]

where A is a positive semi-definite matrix.

If A is the identity matrix, then the Mahalanobis metric is exactly the same as the error measure used in k-means. If A is not the identity matrix, then [math]\displaystyle{ \|x-y\|_A^2 }[/math] will favor certain directions as the k q-flat error measure.