Take the 2-minute tour ×
Quantitative Finance Stack Exchange is a question and answer site for finance professionals and academics. It's 100% free, no registration required.

I'm attempting to solve for $\hat{k}$ clusters, such that the rate distortion is minimized, as described here, however, the answers that I am getting from my algorithm are not following the "Jump" behavior (as is needed to appropriately choose $k$).

My current process:

Given a $N$ by $d$ matrix of asset returns:

  1. Calculate the correlation of the assets, resulting in a $d \times d$ correlation matrix.
  2. For $k \in [1, d]$ calculate the $1 \times d$ vectors of cluster labels, using the correlation matrix as the input
  3. For $k \in [1, d]$ calculate $k, 1 \times d$ vectors of cluster centroids, using the correlation matrix as the input
  4. Based on the cluster label (see code below), construct $\mathbf{A}$, a $d \times d$ matrix of cluster centroids based on the cluster label of each asset. So for instance, say $k=3$ and there are 4 assets total, and the results of the k-means cluster is:

    • asset 1 is in cluster 1
    • asset 2 is in cluster 1
    • asset 3 is in cluster 2
    • asset 4 is in cluster 3

      I would create a $4 \times 4$ matrix where $\textrm{row }1 = \textrm{centroid } 1$ (a 1, 4 row vector), $\textrm{row }2 = \textrm{centroid } 1$ $\textrm{row }3 = \textrm{centroid } 2$ (a 1, 4 row vector), $\textrm{row }4 = \textrm{centroid} 3$

  5. Then calculate the rate distortion function, $\epsilon$, for each $k$, where:

    $\epsilon_{k} \triangleq \frac{1}{p}\mathbf{A^\intercal}\mathbf{\Sigma^{-1}}\mathbf{A}$ where, $\mathbf{\Sigma} \triangleq$ The Covariance Matrix of the $N \times d$ asset returns NOTE: I'm not certain whether I take the covariance of the asset returns or the covariance of the covariance matrix (which didn't seem right to me).

  6. This leaves me with a $d \times d$ matrix that I then sum all the values, and follow the remainder of the procedure listed here. This procedure is derived from the paper, Finding the number of clusters in a data set: An information theoretic approach

My Python Code is as follows:

  import Pycluster

  def rate_distortion(X, cov_matrix, num_clusters):
      clusterid, error, nfound = Pycluster.kcluster(X, nclusters = num_clusters)
      cdata, cmask = Pycluster.clustercentroids(X, clusterid = clusterid)
      c_mat = pandas.DataFrame(numpy.empty(X.shape), columns = X.columns)
      for i, cluster in enumerate(clusterid):
        c_mat.ix[i, :] = cdata[cluster, :]

      diff_mat = numpy.subtract(X, c_mat)
      p = X.shape[1]
      Y = p/2.
      distortion = 1./p * numpy.sum(numpy.dot(numpy.dot(diff_mat.transpose(),  numpy.linalg.inv(cov_matrix)), diff_mat))
      return distortion**(-Y)

To execute a script that exactly illustrates to what I'm referring to, use data located here and the following script:

  import pandas, numpy, Pycluster

  prices = pandas.DataFrame.from_csv('asset_prices.csv')
  returns = prices.apply(numpy.log).diff()
  k = numpy.arange(1,12)
  d = []
  for i in k:
        d.append(rate_distortion(returns.corr(), returns.cov(), i)
  d = pandas.Series(d, index = k)

  In [22]: d
  1     8.845139e-33
  2     3.969062e-29
  3     9.387323e-28
  4     9.200729e-28
  5     4.675902e-18
  6     2.412458e-21
  7     3.582043e-18
  8     8.094695e-17
  9     1.424341e-16
  10    4.320064e-14
  11             inf
  dtype: float64
share|improve this question
any chance you could post your data? –  quasi May 7 '13 at 12:09
Just posted the data, as well as a small script to show you exactly what I'm seeing (as well as the output). Thanks for the suggestion @quasi –  benjaminmgross May 7 '13 at 13:53
So I'm a little confused. You're using $\Sigma$ as your underlying data, with each row a data point. So you have $d$ points in $\mathbb{R}^d$. But in your dispersion calculation, you're not using the covariance matrix of $\Sigma$, you're using $\Sigma$ itself. This seems to not be the algorithm. –  quasi May 7 '13 at 20:39
The naive application of the paper you cited seems to be: calculate $\Sigma$ as you did, then use the distortion measure to cluster the $d$-dimensional returns as a function of time. –  quasi May 7 '13 at 20:40
@quasi, thanks for the reply. A little clarification, $\mathbf{\Sigma}$ as I've defined it, is the covariance matrix as an input to the distortion calculation. The clustering algorithm is being run on the correlation matrix of asset returns. So you're saying, I should set $\mathbf{\Sigma}$ equal to the Covariance of the correlation matrix (which is the input to my clustering algorithm), instead of the covariance of asset returns (which I'm currently doing), correct? –  benjaminmgross May 7 '13 at 20:57
show 4 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.