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 ( a 1 , a 2 , … , a m ) {\displaystyle (a_{1},a_{2},\dots ,a_{m})} where each observation a i {\displaystyle a_{i}} 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 R n {\displaystyle \mathbb {R} ^{n}} that is congruent to R q {\displaystyle \mathbb {R} ^{q}} . For example, a 0-flat is a point; a 1-flat is a line; a 2-flat is a plane; a n − 1 {\displaystyle n-1} -flat is a hyperplane. q-flat can be characterized by the solution set of a linear system of equations: F = { x ∣ x ∈ R n , W ′ x = γ } {\displaystyle F=\left\{x\mid x\in \mathbb {R} ^{n},W'x=\gamma \right\}} , where W ∈ R n × ( n − q ) {\displaystyle W\in \mathbb {R} ^{n\times (n-q)}} , γ ∈ R 1 × ( n − q ) {\displaystyle \gamma \in \mathbb {R} ^{1\times (n-q)}} . Denote a partition of { 1 , 2 , … , n } {\displaystyle \{1,2,\dots ,n\}} as S = ( S 1 , S 2 , … , S k ) {\displaystyle S=(S_{1},S_{2},\dots ,S_{k})} . The problem can be formulated as
where P F i ( a j ) {\displaystyle P_{F_{i}}(a_{j})} is the projection of a j {\displaystyle a_{j}} onto F i {\displaystyle F_{i}} . Note that ‖ a j − P F i ( a j ) ‖ = dist ( a j , F l ) {\displaystyle \|a_{j}-P_{F_{i}}(a_{j})\|=\operatorname {dist} (a_{j},F_{l})} is the distance from a j {\displaystyle a_{j}} to F l {\displaystyle F_{l}} .
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 F l ( 0 ) = { x ∈ R n ∣ ( W l ( 0 ) ) ′ x = γ l ( 0 ) } , l = 1 , … , k {\displaystyle F_{l}^{(0)}=\left\{x\in R^{n}\mid \left(W_{l}^{(0)}\right)'x=\gamma _{l}^{(0)}\right\},l=1,\dots ,k} , and proceeds by alternating between the following two steps:
… excerpt ends here. Continue reading the full article.
