# Hierarchical clustering: is it possible to combine single-linkage clustering and average linkage clustering?

A "seismic section" shows amplitude for m discrete x values along its horizontal axis times n discrete time values along its vertical axis:

Peaks in amplitude (black) are centered on horizons; interfaces between different geological layers. The horizons are mostly continous but not necessarily horizontal nor flat lines. In the image above somebody has "tracked" the green and yellow horizons (using a crayon on a piece of paper?) that form the top and bottom of the "Ordovian" geological layer. These two lines are continous everywhere except for where they cross one of the vertical black lines: faults.

It is easy to implement a computer program that "draws" the colored lines by following the peaks, except for at the faults.

The problem here is that the peak "jump" in time and by how much differs from case to case.

One possible way to automate this is to assume that the shape of the signal around the peak is almost constant along a horizon. We can then reconstruct the amplitude around each peak sample by e.g. a Cosine series expansion with say 5 terms:

The result is a feature vector for each peak sample. In the case above the feature vector would be:

F1 = [94.2496  192.7706 -211.4520  -82.8782   11.2105]


The feature vectors can then be used as input to a classification/clustering algorithm that figures out which peak samples are on the same horizon.

The problem with the feature vector above is that it does not force the peak samples to be linked together; in fact it disregards their positions in space altogether. This would be fine if each horizon had a very different shape around the peak. Unfortunately this is often not the case.

So we want to include the x postion into the feature vector. However many clustering algorithms are not able to deal with this since they would require that all observations within a cluster have almost the same x position.

Perhaps hierarchical clustering may be a solution to this problem?

As I understand "single-linkage clustering" would only require that each peak had a peak within the same cluster that was its neighbour (adjacent x positions).

This is almost what we want. Ideally I would want single-linkage clustering on the x-position and average linkage clustering on the Cosine coefficients.

Is this possible?

For example, you could use the distance function $$d(a,b) := \alpha |x(a) - x(b)|^2 + (1-\alpha) \sqrt{\sum_{i=1}^{5} |c_i(a)-c_i(b)|^2}$$
Where $\alpha$ controls the balance between locality (which is deliberately squared, to punish larger differences more) and a similar shape using euclidean distance on attributes $c_1$ to $c_5$.
• DBSCAN and OPTICS do range queries. So if you have precomputed these neighbors, that should work fine for them and make them essentially O(n). The most expensive part in both is the neighborhood query, which adds n or log n (with a spatial index structure) to this. But precomputed neighbor lists with only the relevant neighbors is ideal for DBSCAN and OPTICS. – Has QUIT--Anony-Mousse Jun 17 '12 at 9:10