The goal of extra trees is to partition space in order to subcluster data

Split step a node

Given a subset S, try to partition it.

If stop split(S) : do nothing Else

Select K attributes in the non-constant candidates attributes

Try K split [s₁, ..., s_K] given the pick_random_split(S, a_i)

Return the split s_i that maximize Score(s_i, S)

Pick_random_split (S, a)

Find the extremum attribute values a_min and a_max

Pick a_c ∈ [a_min, a_max]

Return the split [a < a_c]

Stop Split

Given a subset S

if :

• The number of elements of S (|S|) is inf to n_min then TRUE
• All attribute are constant in S, then TRUE (all same X in the cluster, so no need to split)
• All output are constant in s, then TRUE (all same y in the local cluster)
• ELSE : FALSE