On a two-stage clustering procedure and the choice of objective function

Abstract

The paper introduces a class of simple hybrid clustering algorithms, based on the idea of obtaining, ¯rst, a high number of "subassemblies" or "cells", through application of a k-means-type procedure, and, second, aggregating these "sub- assemblies" into shapes with a hierarchical merger procedure. For n objects, characterized by vectors of values xi; i = 1; ; n, we look in the ¯rst stage for p1 cluster "cells", with n >> p1 >> 1, possibly p1 » O(n1=2). Then, distances between the thus formed clusters, A¤ q1 ; q1 = 1; ; p1, are calculated according to one of the prede¯ned formulas. On the basis of these distances the second stage algorithm is executed of the hierarchical merger kind. The ¯nal number of output clusters Aq2 , i.e. p2; p1 >> p2 ¸ 1, is determined with the use of the global ob- jective function for the clustering, developed by the author. The generic method is primarily meant to recover the clusters of cumbersome, curvilinear, shapes, which it does e®ectively and e±ciently. The class of algorithms is generated by (a) choice of a particular k-means-type algorithm for the first stage; (b) choice of a particular distance measure d(A¤ q1 ;Aq1 ); (c) choice of the hierarchical merger algorithm, coupled with the concrete form of the objective function. The overall algorithms thus obtained diler signicantly by their e±ciency, numerical complexity and electiveness, as well as the nature of output clusters.