ls-fit-ultrametric           package:clue           R Documentation

_L_e_a_s_t _S_q_u_a_r_e_s _F_i_t _o_f _U_l_t_r_a_m_e_t_r_i_c_s _t_o _D_i_s_s_i_m_i_l_a_r_i_t_i_e_s

_D_e_s_c_r_i_p_t_i_o_n:

     Find the ultrametric minimizing least squares distance (euclidean
     dissimilarity) to a given dissimilarity object.

_U_s_a_g_e:

     ls_fit_ultrametric(x, control = list())

_A_r_g_u_m_e_n_t_s:

       x: a dissimilarity object inheriting from class '"dist"'.

 control: a list of control parameters.  See *Details*.

_D_e_t_a_i_l_s:

     With L(u) = sum (x - u)^2, the problem to be solved is minimizing
     L over all u satisfying the ultrametric constraints (i.e., for all
     i, j, k, u_{ij} <= max(u_{ik}, u_{jk})).  This problem is known to
     be NP hard (Krivanek and Moravek, 1986).

     We follow de Soete (1986) to use a heuristic based on an SUMT
     (Sequential Unconstrained Minimization Technique) approach in turn
     simplifying the suggestions in Carroll and Pruzansky (1980).  One
     iteratively minimizes L(u) + rho_k P(u), where P(u) is a
     non-negative function penalizing violations of the ultrametric 
     constraints such that P(u) is zero iff u is an ultrametric.  The
     rho values are increased according to the rule rho_{k+1} = q rho_k
     for some constant q > 1, until convergence is obtained in the
     sense that the euclidean distance between successive solutions u_k
     and u_{k+1} is small enough.  We then use a final rounding step to
     ensure that the returned object exactly satisfies the ultrametric
     constraints.  The starting value u_0 is obtained by "random
     shaking" of the given dissimilarity object.

     The unconstrained minimizations are carried out using either
     'optim' or 'nlm', using the analytic gradients given in Carroll
     and Pruzansky (1980).  The following control parameters can be
     provided via the 'control' argument.

     '_m_e_t_h_o_d' a character string, or 'NULL'.  If not given, '"CG"' is
          used.  If equal to '"nlm"', minimization is carried out using
          'nlm'. Otherwise, 'optim' is used with 'method' as the given
          method.

     '_c_o_n_t_r_o_l' a list of control parameters to be passed to the
          minimization routine in case 'optim' is used.

     '_e_p_s' the absolute convergence tolerance. Defaults to
          'sqrt(.Machine$double.eps)'.

     '_q' a double greater than one controlling the growth of the rho_k
          as described above.  Defaults to 10.

     '_v_e_r_b_o_s_e' a logical indicating whether to provide some output on
          minimization progress.  Defaults to 'getOption("verbose")'.

     The default optimization using conjugate gradients should work
     reasonably well for medium to large size problems.  For "small"
     ones, using 'nlm' is usually faster.  Note that the number of
     ultrametric constraints is of the order n^3, where n is the number
     of objects in the dissimilarity object, suggesting to use the SUMT
     approach in favor of 'constrOptim'.

     It should be noted that the SUMT approach is a heuristic which can
     not be guaranteed to find the global minimum.  Standard practice
     would recommend to use the best solution found in "sufficiently
     many" replications of the base algorithm.

_V_a_l_u_e:

     An object of class '"cl_ultrametric"' containing the optimal
     ultrametric distances.

_R_e_f_e_r_e_n_c_e_s:

     J. D. Carroll and S. Pruzansky (1980). Discrete and hybrid scaling
     models. In E. D. Lantermann and H. Feger (eds.), _Similarity and
     Choice_. Bern (Switzerland): Huber.

     M. Krivanek and J. Moravek (1986). NP-hard problems in
     hierarchical tree clustering. _Acta Informatica_, *23*, 311-323.

     G. de Soete (1986). A least squares algorithm for fitting an
     ultrametric tree to a dissimilarity matrix. _Pattern Recognition
     Letters_, *2*, 133-137.

_S_e_e _A_l_s_o:

     'cl_median' for computing median hierarchies by least squares
     fitting average ultrametric distances.

_E_x_a_m_p_l_e_s:

     ## Least squares fit of an ultrametric to the Miller-Nicely consonant
     ## phoneme confusion data.
     data("Phonemes")
     ## Note that the Phonemes data set has the consonant misclassification
     ## probabilities, i.e., the similarities between the phonemes.
     d <- 1 - as.dist(Phonemes)
     u <- ls_fit_ultrametric(d, control = list(verbose = TRUE))
     ## Cophenetic correlation:
     cor(d, u)
     ## Dendrogram:
     plot(u)
     ## ("Basically" the same as Figure 1 in de Soete (1986).)

