Optimal Variable Weighting (OVW)

Vladimir Makarenkov and Pierre Legendre
Département de Sciences Biologiques
Université de Montréal
C.P. 6128, succursale Centre-ville
Montréal, Québec H3C 3J7, Canada
This program performs optimal variable weighting for ultrametric and additive tree clustering, following the method proposed by De Soete (1986, 1988), as well as for K-means partitioning. It is described in Makarenkov & Legendre.
The program, which is available free of charge to academic users, provides some improvements and extra options, compared to De Soete's (1988) program OVWTRE, which only implemented fitting to the first two families of clustering methods mentioned above. Given a rectangular data matrix Y (n,m), containing measurements of n objects on m variables, the procedure computes variable weights w(m) such that the resulting matrix of inter-object dissimilarities D(n,n) obtained from Y optimally satisfies either the ultrametric or the additive inequality, or optimally corresponds to a K-means partition with fixed number of groups K. The weights w are constrained to be nonnegative and their sum is equal to one. We used Polak-Ribiere's Conjugate Gradient Method (Numerical Recipes, Press et al., 1986) to carry out the optimization process. Once the optimal variable weights are obtained in the case of the ultrametric or additive tree clustering, the resulting inter-object dissimilarities D can be subjected to any of the existing ultrametric or additive tree fitting procedures. See De Soete (1986) or Makarenkov and Leclerc (1999) for an overview of these methods. It is worth noting that sometimes only a local minimum can be obtained as a final result. Hence a good choice of initial weights is essential. According to our investigations an initial guess consisting of all equal weights (as implemented in De Soete's software OVWTRE) cannot guarantee reaching the global minimum. An interesting feature of program OVW, compared to OVWTRE, is that it allows users to restart the optimization procedure any number of times, using different random initial guesses for the weights. As a consequence, OVW usually obtains better results than OVWTRE in the case of ultrametric and additive clustering; optimization for K-means partitionning is not available in OVWTRE. Moreover, the optimization in OVW is carried out in the way allowing to avoid a degenerate trivial solution in the case of the additive clustering. Such a solution consists of giving a weight of 1 to any one variable and weights of 0 to all other variables. Another important feature not mentioned by De Soete (1986, 1988) is that the global minimum of a function to minimize can be reached with several different sets of optimal weights w. This may lead to different inter-object dissimilarities matrices D, from which different hierarchies or additive trees can be inferred. References:
De Soete, G. 1986. Optimal variable weighting for ultrametric and additive tree clustering. Quality&Quantity 20: 169-180. De Soete, G. 1988. OVWTRE: A program for optimal variable weighting for ultrametric and additive tree fitting. Journal of Classification 5: 101-104. Makarenkov, V. & Leclerc, B. 1999. An Algorithm for the fitting of a tree metric according to a weighted least-squares criterion. Journal of Classification 16(1): 3-26. Makarenkov, V., Legendre, P. 2001. Optimal Variable Weighting for Ultrametric and Additive Trees and K-means Partitioning: Methods and Software. Journal of Classification 18: 245-271. Milligan, G.W. 1989. A validation study of a variable weighting algorithm for cluster analysis. Journal of Classification 6: 53-71. Polak, E. 1971. Computational methods in optimization. New York, Academic Press: 2.3. Press, W. H., B. P. Flanery, S. A. Teukolsky & W. T. Vetterling. (1986), Numerical Recipes - The art of scientific computing. Cambridge Univ. Press, Cambridge. xx + 818 p.