ls_fit_ultrametric(x, method = c("SUMT", "IP", "IR"), weights = 1,
control = list())"dist", or an ensemble of such objects."SUMT" (default), "IP", or
"IR", or a unique abbreviation thereof.x, and the lower diagonal part is used.
"cl_ultrametric" containing the
fitted ultrametric distances.x, the problem to be solved
is minimizing
$$L(u) = \sum_{i,j} w_{ij} (x_{ij} - u_{ij})^2$$
over all $u$ satisfying the ultrametric constraints (i.e., for all
$i, j, k$, $u_{ij} \le \max(u_{ik}, u_{jk})$). This problem
is known to be NP hard (Krivanek and Moravek, 1986). For an ensemble of dissimilarity objects, the criterion function is
$$L(u) = \sum_b w_b \sum_{i,j} w_{ij} (x_{ij}(b) - u_{ij})^2,$$
where $w_b$ is the weight given to element $x_b$ of the
ensemble and can be specified via control parameter weights
(default: all ones). This problem reduces to the above basic problem
with $x$ as the $w_b$-weighted mean of the $x_b$.
We provide three heuristics for solving the basic problem.
Method "SUMT" implements the SUMT (Sequential
Unconstrained Minimization Technique, Fiacco and McCormick, 1968)
approach of de Soete (1986) which in turn simplifies the suggestions
in Carroll and Pruzansky (1980). (See sumt for more
information on the SUMT approach.) We then use a final
single linkage hierarchical clustering step to ensure that the
returned object exactly satisfies the ultrametric constraints. The
starting value $u_0$ is obtained by x, i.e., the given dissimilarities are
incomplete, we follow a suggestion of de Soete (1984), imputing
the missing values by the weighted mean of the non-missing ones, and
setting the corresponding weights to zero.
Available control parameters are method, control,
eps, q, and verbose, which have the same roles as
for sumt, and the following.
[object Object],[object Object]
The default optimization using conjugate gradients should work
reasonably well for medium to large size problems. For 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.
If starting values for the SUMT are provided via
start, the number of starting values gives the number of runs
to be performed, and control option nruns is ignored.
Otherwise, nruns starting values are obtained by random shaking
of the dissimilarity to be fitted. In the case of multiple
SUMT runs, the (first) best solution found is returned.
Method "IP" implements the Iterative Projection approach of
Hubert and Arabie (1995). This iteratively projects the current
dissimilarities to the closed convex set given by the ultrametric
constraints (3-point conditions) for a single index triple $(i, j,
k)$, in fact replacing the two largest values among $d_{ij},
d_{ik}, d_{jk}$ by their mean. The following control parameters can
be provided via the control argument.
[object Object],[object Object],[object Object],[object Object],[object Object]
If permutations are provided via order, the number of these
gives the number of runs to be performed, and control option
nruns is ignored. Otherwise, nruns randomly generated
orders are tried. In the case of multiple runs, the (first) best
solution found is returned.
Non-identical weights and incomplete dissimilarities are currently not supported.
Method "IR" implements the Iterative Reduction approach
suggested by Roux (1988), see also Barthélémy and Guénoche (1991).
This is similar to the Iterative Projection method, but modifies the
dissimilarities between objects proportionally to the aggregated
change incurred from the ultrametric projections. Available control
parameters are identical to those of method "IP".
Non-identical weights and incomplete dissimilarities are currently not supported.
It should be noted that all methods are heuristics which can not be
guaranteed to find the global minimum. Standard practice would
recommend to use the best solution found in
L. Hubert and P. Arabie (1995). Iterative projection strategies for the least squares fitting of tree structures to proximity data. British Journal of Mathematical and Statistical Psychology, 48, 281--317. M. Krivanek and J. Moravek (1986). NP-hard problems in hierarchical tree clustering. Acta Informatica, 23, 311--323. M. Roux (1988). Techniques of approximation for building two tree structures. In C. Hayashi and E. Diday and M. Jambu and N. Ohsumi (Eds.), Recent Developments in Clustering and Data Analysis, pages 151--170. New York: Academic Press.
G. de Soete (1984). Ultrametric tree representations of incomplete dissimilarity data. Journal of Classification, 1, 235--242.
G. de Soete (1986). A least squares algorithm for fitting an ultrametric tree to a dissimilarity matrix. Pattern Recognition Letters, 2, 133--137.
cl_consensus for computing least squares (Euclidean)
consensus hierarchies by least squares fitting of average ultrametric
distances;
l1_fit_ultrametric.## 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 <- as.dist(1 - Phonemes)
u <- ls_fit_ultrametric(d, control = list(verbose = TRUE))
## Cophenetic correlation:
cor(d, u)
## Plot:
plot(u)
## ("Basically" the same as Figure 1 in de Soete (1986).)Run the code above in your browser using DataLab