C-MEANS CLUSTERING WITH THE L1 AND L-INFINITY NORMS

An extension of the hard and fuzzy c-means (HCM/FCM) clustering algorithms is described. Specifically, these models are extended to admit the case where the (dis)similarity measure on pairs of numerical vectors includes two members of the Minkowski or p-norm family, viz., the p = 1 and p = infinity (or "sup") norms. In the absence of theoretically necessary conditions to guide a numerical solution of the nonlinear constrained optimization problem associated with this case, it is shown that a basis exchange algorithm due to Bobrowski can be used to find approximate critical points of the new objective functions. This method broadens the applications horizon of the FCM family by enabling users to match "discontinuous" multidimensional numerical data structures with similarity measures that have nonhyperelliptical topologies. For example, data drawn from a mixture of uniform distributions have sharp or "boxy" edges; the (p = 1 and p = infinity) norms have open and closed sets that match these shapes. The technique is illustrated with a small artificial data set, and is compared with the results with the c-means clustering solution produced using the Euclidean norm.