Optimal Variable Weighting (OVW)
Vladimir Makarenkov and Pierre LegendreDépartement de Sciences Biologiques
Université de Montréal
C.P. 6128, succursale Centreville
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 Kmeans 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 interobject dissimilarities D(n,n) obtained from Y optimally satisfies either the ultrametric or the additive inequality, or optimally corresponds to a Kmeans partition with fixed number of groups K. The weights w are constrained to be nonnegative and their sum is equal to one. We used PolakRibiere'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 interobject 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 Kmeans 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 interobject dissimilarities matrices D, from which different hierarchies or additive trees can be inferred.

Macintosh version
 C source code for Macintosh, which can be compiled using a C++ compiler
 Compiled version of the program for Macintosh computers with a PowerPC processor
 User's guide containing a detailed description of the problem, in Word 6 format
 Sample files

32bit DOS version (The executable file is a Win32 "console" executable, not a DOS executable. Therefore it cannot run under plain DOS, nor in a DOS window under Windows 3.x, only in Windows 95/98 or Windows NT consoles)
 C source code for Win32, which can be compiled using a C++ compiler
 Compiled version of the program for Win32 compatible computers
 User's guide containing a detailed description of the problem, in Word 97 format
 Sample files

Unix version
 C source code for UNIX, which can be compiled using a C++ compiler
 User's guide containing a detailed description of the problem, in ASCII format
 Sample files
 No executable program is distributed, it is assumed that you will compile your own for your flavor of UNIX.
De Soete, G. 1986. Optimal variable weighting for ultrametric and additive tree clustering. Quality&Quantity 20: 169180. De Soete, G. 1988. OVWTRE: A program for optimal variable weighting for ultrametric and additive tree fitting. Journal of Classification 5: 101104. Makarenkov, V. & Leclerc, B. 1999. An Algorithm for the fitting of a tree metric according to a weighted leastsquares criterion. Journal of Classification 16(1): 326. Makarenkov, V., Legendre, P. 2001. Optimal Variable Weighting for Ultrametric and Additive Trees and Kmeans Partitioning: Methods and Software. Journal of Classification 18: 245271. Milligan, G.W. 1989. A validation study of a variable weighting algorithm for cluster analysis. Journal of Classification 6: 5371. 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.