Reordering matrix elements to reflect column and row clustering in naiive python

Question

Hello,

I'm looking for a way to perform clustering separately on matrix rows and than on its columns, reorder the data in the matrix to reflect the clustering and putting it all together. The clustering problem is easily solvable, so is the dendrogram creation (for example in this blog or in "Programming collective intelligence"). However, how to reorder the data remains unclear for me.

Eventually, I'm looking for a way of creating graphs similar to the one below using naive Python (with any "standard" library such as numpy, matplotlib etc, but without using R or other external tools).

Clarifications

I was asked what I meant by reordering. When you cluster data in a matrix first by matrix rows, then by its columns, each matrix cell can be identified by the position in the two dendrograms. If you reorder the rows and the columns of the original matrix such that the elements that are close each to another in the dendrograms become close each to another in the matrix, and then generate heatmap, the clustering of the data may become evident to the viewer (as in the figure above)

Answer 1

I'm not sure completely understand, but it appears you are trying to re-index each axis of the array based on sorts of the dendrogram indicies. I guess that assumes there is some comparative logic in each branch delineation. If this is the case then would this work(?):

>>> x_idxs = [(0,1,0,0),(0,1,1,1),(0,1,1),(0,0,1),(1,1,1,1),(0,0,0,0)]
>>> y_idxs = [(1,1),(0,1),(1,0),(0,0)]
>>> a = np.random.random((len(x_idxs),len(y_idxs)))
>>> x_idxs2, xi = zip(*sorted(zip(x_idxs,range(len(x_idxs)))))
>>> y_idxs2, yi = zip(*sorted(zip(y_idxs,range(len(y_idxs)))))
>>> a2 = a[xi,:][:,yi]

x_idxs and y_idxs are the dendrogram indicies. a is the unsorted matrix. xi and yi are your new row/column array indicies. a2 is the sorted matrix while x_idxs2 and y_idxs2 are the new, sorted dendrogram indicies. This assumes that when the dendrogram was created that a 0 branch column/row is always comparatively larger/smaller than a 1 branch.

If your y_idxs and x_idxs are not lists but are numpy arrays, then you could use np.argsort in a similar manner.

Answer 2

See my recent answer, copied in part below, to this related question.

import scipy
import pylab
import scipy.cluster.hierarchy as sch

# Generate features and distance matrix.
x = scipy.rand(40)
D = scipy.zeros([40,40])
for i in range(40):
    for j in range(40):
        D[i,j] = abs(x[i] - x[j])

# Compute and plot dendrogram.
fig = pylab.figure()
axdendro = fig.add_axes([0.09,0.1,0.2,0.8])
Y = sch.linkage(D, method='centroid')
Z = sch.dendrogram(Y, orientation='right')
axdendro.set_xticks([])
axdendro.set_yticks([])

# Plot distance matrix.
axmatrix = fig.add_axes([0.3,0.1,0.6,0.8])
index = Z['leaves']
D = D[index,:]
D = D[:,index]
im = axmatrix.matshow(D, aspect='auto', origin='lower')
axmatrix.set_xticks([])
axmatrix.set_yticks([])

# Plot colorbar.
axcolor = fig.add_axes([0.91,0.1,0.02,0.8])
pylab.colorbar(im, cax=axcolor)

# Display and save figure.
fig.show()
fig.savefig('dendrogram.png')