k-Plane Clustering

Abstract

A finite new algorithm is proposed for clustering m given points in n-dimensional real space into k clusters by generating k planes that constitute a local solution to the nonconvex problem of minimizing the sum of squares of the 2-norm distances between each point and a nearest plan/ The key to the algorithm lies in a formulation that generates a plane in n-dimensional space that minimizes the sum of the squares of the 2-norm distances to each of the m1 given points in the space. The plane is generated by an eigenvector corresponding to a smallest eigenvalue of an nxn simple matrix derived fro the m1 points. The algorithm was tested on the publicly available Wisconsin Breast Prognosis Cancer database to generate well separated patients survival curves. In contrast, the k-mean algorithm did non generate such well-separated survival curves.