The bi-partial approach in clustering and ordering: the model and the algorithms
| STATISTICA & APPLICAZIONI - 2011 - Special issue. Partial orders in applied sciences
The paper outlines an approach, applicable to both the problem of clustering and to (‘‘optimum’’)
ordering, which starts from a formulation of the objective function and the constraints, equivalent to
a binary mathematical programming problem. This formulation, for both ordering and clustering,
represents a number of very positive features, like possibility of dealing with incomplete and inconsistent
data, while posing essential numerical difficulties. For clustering, it implies a globally optimal
solution in that both cluster content and cluster number are obtained. We reformulate this problem
by parameterising it and show that, under certain additional assumptions, an effective algorithm
can be deduced for both clustering and ordering, which suboptimises the objective function.
In the case of clustering, the algorithm is an analogue of the classical hierarchical merger procedures,
while in the case of ordering it relies on iterations, in which just one object is moved. Some
essential properties are given, along with a simple illustration. In spite of the analogy, the properties
of the approach and the respective algorithms are different for the two cases considered, i.e.
clustering and ordering.
Keywords: Clustering, Ordering, Mathematical Programming, Parameterisation, Suboptimisation Algorithms, Objective Functions.