Biology Reference
In-Depth Information
1, which
took less than 2 minutes to run, LST found a better solution than
hsearch
for more than half of the 20 problems. This was the case for all
l
max
tested.
Running LST with Trials
We now look at the 1000-leaf trees. Already with Trials
=
RBFS took less than 2 hours. In this
case, LST was superior to
hsearch
on at least 17 of the input problems.
Please notice that default parameters were used for
hsearch
, and that we
did not study to which extent tweaking the parameters would change the
results.
=
50
+
4.3. RBFS Heuristic
In Sec. 3.2, we have presented the general idea of the RBFS heuristic. In
this section, we show how this idea can be applied to WLS tree building.
To formulate RBFS, we need an index to score a given subtree and a way
to substitute a well-scoring subtree by a leaf. The two components are
described next.
4.3.1. Subtree index
Consider a subtree
S
in the following tree
T
:
S
A
X
R
B
The index we present here measures the contribution of a subtree
S
to
the total error made in
T
. It is composed of the sum of two parts. The
first part measures the fitting of distances inside the subtree
S
:
(
)
2
Td
-
Â
AB
AB
,
E
=
1
2
s
AB S
,
Œ
AB
where
A
and
B
are different leaves in the subtree
S
,
T
AB
is the
distance between
A
and
B
in
S
, and
d
AB
and
σ
2
AB
are the source data.
