# optimalleaforder

Optimal leaf ordering for hierarchical clustering

## Description

returns an optimal leaf ordering for the hierarchical binary cluster tree,
`leafOrder`

= optimalleaforder(`tree`

,`D`

)`tree`

, using the distances, `D`

. An optimal
leaf ordering of a binary tree maximizes the sum of the similarities between
adjacent leaves by flipping tree branches without dividing the clusters.

returns the optimal leaf ordering using one or more name-value pair arguments.`leafOrder`

= optimalleaforder(`tree`

,`D`

,`Name,Value`

)

## Examples

### Plot Dendrogram with Optimal Leaf Order

Create a hierarchical binary cluster tree using `linkage`

. Then, compare the dendrogram plot with the default ordering to a dendrogram with an optimal leaf ordering.

Generate sample data.

rng(0,"twister") % For reproducibility X = rand(10,2);

Create a distance vector and a hierarchical binary clustering tree. Use the distances and clustering tree to determine an optimal leaf order.

```
D = pdist(X);
tree = linkage(D,"average");
leafOrder = optimalleaforder(tree,D);
```

Plot the dendrogram with the default ordering and the dendrogram with the optimal leaf ordering.

figure() subplot(2,1,1) dendrogram(tree) title("Default Leaf Order") subplot(2,1,2) dendrogram(tree,reorder=leafOrder) title("Optimal Leaf Order")

The order of the leaves in the bottom figure corresponds to the elements in `leafOrder`

. The optimal leaf order flips tree branches to maximize the sum of the similarities between adjacent leaves.

leafOrder

`leafOrder = `*1×10*
1 4 9 10 2 5 8 3 7 6

Create a scatter plot of the sample data and label the points.

```
figure()
plot(X(:,1),X(:,2),".")
text(X(:,1),X(:,2),num2str((1:size(X,1))'))
```

In the default leaf ordering, points 1 and 4 are located next to points 3 and 8. In the optimal leaf ordering, points 1 and 4 are located next to point 9, which reflects their relative positions in the scatter plot.

### Optimal Leaf Order Using Inverse Distance Similarity

Generate sample data.

rng('default') % For reproducibility X = rand(10,2);

Create a distance vector and a hierarchical binary clustering tree.

```
D = pdist(X);
tree = linkage(D,'average');
```

Use the inverse distance similarity transformation to determine an optimal leaf order.

leafOrder = optimalleaforder(tree,D,'Transformation','inverse')

`leafOrder = `*1×10*
1 4 9 10 2 5 8 3 7 6

## Input Arguments

`tree`

— Hierarchical binary cluster tree

matrix returned by `linkage`

Hierarchical binary cluster tree, specified as an (*M* – 1)-by-3 matrix that you generate using `linkage`

, where *M* is the number of leaves.

`D`

— Distances

matrix | vector

Distances for determining similarities between leaves, specified as a matrix or vector of distances. For example, you can generate distances using `pdist`

.

### Name-Value Arguments

Specify optional pairs of arguments as
`Name1=Value1,...,NameN=ValueN`

, where `Name`

is
the argument name and `Value`

is the corresponding value.
Name-value arguments must appear after other arguments, but the order of the
pairs does not matter.

*
Before R2021a, use commas to separate each name and value, and enclose*
`Name`

*in quotes.*

**Example: **`'Criteria','group','Transformation','inverse'`

specifies that the sum of similarities be maximized between every leaf and all other leaves in adjacent clusters, using an inverse similarity transformation.

`Criteria`

— Optimization criterion

`'adjacent'`

(default) | `'group'`

Optimization criterion for determining an optimal leaf ordering, specified as the comma-separated pair consisting of `'criteria'`

and one of these values:

`'adjacent'` | Maximize the sum of similarities between adjacent leaves. |

`'group'` | Maximize the sum of similarities between every leaf and all other leaves in the adjacent clusters at the same level of the dendrogram. |

**Example: **`'Criteria','group'`

`Transformation`

— Method for transforming distances to similarities

`'linear'`

(default) | `'inverse'`

| function handle

Method for transforming distances to similarities, specified as the comma-separated pair consisting of `'Transformation'`

and one of `'linear'`

, `'inverse'`

, or a function handle.

Let *d _{i,j}* and

*Sim*denote the distance and similarity between leaves

_{i,j}*i*and

*j*, respectively. The included similarity transformations are:

`'linear'` | Sim = max_{i,j}_{i,j} (d) – _{i,j }d_{i,j} |

`'inverse'` | Sim = 1/_{i,j}d_{i,j} |

To use a custom transformation function, specify a handle to a function that accepts a matrix of distances, `D`

, and returns a matrix of similarities, `S`

. The function should be monotonic decreasing in the range of distance values. `S`

must have the same size as `D`

, with `S(i,j)`

being the similarity computed based on `D(i,j)`

.

**Example: **`'Transformation',@myTransform`

## Output Arguments

`leafOrder`

— Optimal leaf order

vector

Optimal leaf order, returned as a length-*M* vector, where *M* is the number of leaves. `leafOrder`

is a permutation of the vector `1:M`

, giving an optimal leaf ordering based on the specified distances and similarity transformation.

## References

[1] Bar-Joseph, Z., Gifford, D.K., and Jaakkola, T.S. (2001). "Fast optimal leaf ordering for hierarchical clustering." *Bioinformatics* Vol. 17, Suppl 1:S22–9. PMID: 11472989.

## Version History

**Introduced in R2012b**

## See Also

`dendrogram`

| `linkage`

| `pdist`

## MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

You can also select a web site from the following list:

## How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

### Americas

- América Latina (Español)
- Canada (English)
- United States (English)

### Europe

- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)

- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)