Correlation-Based Clustering: Spectral Clustering Methods

Clustering consists in trying to identify groups of “similar behavior”1 - called clusters - from a dataset, according to some chosen characteristics. An example of such a characteristic in finance is the correlation coefficient between two time series of asset returns, whose usage to partition a universe of assets into groups of “close” and “distant” assets thanks to a hierarchical clustering method was originally2 proposed in Mantegna3. In this blog post, I will describe two correlation-based clustering methods belonging to the family of spectral clustering methods: the Blockbuster method introduced in Brownlees et al.4 and the SPONGE method introduced in Cucuringu et al.5. As examples of usage, I will discuss 1) how to automatically group U.S. stocks together without relying on external information like industry classification and 2) how to identify risk-on and risk-off assets within a U.S. centric universe of assets. Mathematical preliminaries Let $x_1$, …, $x_n$ be $n$ points6 in $\mathbb{R}^m, m \geq 1$ to be partitioned into $k \geq 2$ subsets. Spectral clustering Spectral clustering, like other approaches to clustering - geometric approaches such as $k$-means , density-based approaches such as DBSCAN… - initially relies on pairwise similarities $s(x_i, x_j)$ between points $i,j=1..n$ with $s$ some similarity function which is symmetric and non-negative1. Once the corresponding similarity matrix $S_{ij} = s(x_i, x_j)$, $i,j=1…n$, has been computed, a spectral clustering method then usually follows a three-step process: Compute an affinity matrix $A \in \mathbb{R}^{n \times n}$ from the similarity matrix $S$ The affinity matrix $A$ corresponds to the adjacency matrix of an underlying graph whose vertices represent the points $x_1$, …, $x_n$ and whose edges model the local7 neighborhood relationships between the data points1. Compute a matrix $L \in \mathbb{R}^{n \times n}$ derived from the affinity matrix $A$ Due to the relationship between spectral clustering and graph theory1, the matrix $L$ is typically called a Laplacian matrix. Compute a matrix $Y \in \mathbb{R}^{n \times k}$ derived from the eigenvectors corresponding to the $k$ smallest (or sometimes largest) eigenvalues of the matrix $L$ and cluster its $n$ rows $y_1$, …, $y_n$ using the $k$-means algorihm The result of that clustering represents the desired clustering of the original $n$ points $x_1$, …, $x_n$. It should be emphasized that there is nothing principled about using the $k$-means algorithm in this step1, c.f. for example Huang et al.8 in which spectral rotations are used instead of $k$-means, but one can argue that at least the Euclidean distance between the [rows of the matrix $Y$] is a meaningful quantity to look at1. The Ng-Jordan-Weiss spectral clustering method Different ways of computing the affinity matrix $A$, the Laplacian matrix $L$ or the matrix $Y$ lead to different spectral clustering methods9. One popular spectral clustering method is the Ng-Jordan-Weiss (NJW) method10, detailed in Figure 1 taken from Ng et al.10 where $\sigma^2$ is a scaling parameter that controls how rapidly the affinity $A_{ij}$ falls off with the distance between $s_i$ and $s_j$10. Figure 1. Ng-Jordan-Weiss spectral clustering method. Source: Ng et al. Rationale behind spectral clustering At first sight, [spectral clustering] seem to make little sense. Since we run $k$-means [on points $y_1$, …, $y_n$], why not just apply $k$-means directly to the [original points $x_1$, …, $x_n$]10? A visual justification of spectral clustering is provided in Figure 2 adpated from Ng et al.10, which displays data points in $\mathbb{R}^2$ forming two circles (e) and their associated spectral representation in $\mathbb{R}^2$ using the NJW spectral clustering method (h). Figure 2. Data points forming two circles, 2D plane and spectral plane. Source: Ng et al. On Figure 2, it is clearly visible that the transformed data points (h) form two well-separated convex clusters in the spectral plane, which is the ideal situation for the $k$-means algorithm. More generally11, it can be demonstrated that the change of representation from the original data points $x_1$, …, $x_n$ to the embedded data points $y_1$, …, $y_n$ enhances the cluster-properties in the data, so that clusters can be trivially detected [by the $k$-means clustering algorithm] in the new representation1. Correlation-based spectral clustering Let $x_1$, …, $x_n$ be $n$ variables whose pairwise correlations12 $\rho_{ij}$, $i,j=1…n$, have been assembled in a correlation matrix $C \in \mathbb{R}^{n \times n}$. Because correlation is a measure of dependency, a legitimate question is whether it is possible to use spectral clustering to partition these variables w.r.t. their correlations? Ideally, we would like to have highly correlated variables grouped together in the same clusters, with low or even negative correlations between the clusters themselves. Problem is, as noted in Mantegna3, the correlation coefficient of a pair of [variables] cannot be used as a distance [or as a similarity] between the two [variables] because it does not fulfill the three axioms that define a metric3, which a priori excludes its direct usage in a similarity matrix or in an affinity matrix. That being said, a13 metric14 can be defined using as distance a function of the correlation coefficient3 - like the distance $d_{ij} = \sqrt{ 2 \left( 1 - \rho_{ij} \right) }$ -, which allows to indirectly use any spectral clustering method15 with correlations. But what if we insist to work directly with correlations? In this case, a couple of specific spectral clustering methods have been developped, among which: The Blockbuster spectral clustering method of Brownlees et al.4 The SPONGE spectral clustering method of Cucuringu et al.5 The Blockbuster spectral clustering method Brownlees et al.4 introduces a network model16 under which large panels of time series are partitioned into latent groups such that correlation is higher within groups than between them4 and proposes an algorithm relying on the eigenvectors of the sample covariance matrix17 $\Sigma \in \mathbb{R}^{n \times n}$ to detect these groups. As can be seen in Figure 3 taken from Brownlees et al.4, this algorithm - called Blockbuster - is surprisingly very close to the NJW spectral clustering method. Figure 3. Blockbuster algorithm. Source: Brownlees et al. Brownlees et al.4 establishes that the Blockbuster algorithm consistently detects the [groups] when the number of observations $T$ and the dimension of the panel $n$ are sufficiently18 large4, as long as a couple of assumptions are satisfied, like: $T \geq n$, with the more fat-tailed and dependent the data are, the larger $T$ has to be4 The precision matrix $\Sigma^{-1}$ exists and contains only non-positive entries (or its fraction of positive entries is appropriately controlled19) An important feature of the Blockbuster algorithm is that it allows one to detect the [groups] without estimating the network structure of the data4. In other words, while the Blockbuster algorithm is a spectral clustering method, nowhere is an affinity matrix computed! The black magic at work here is that the underlying network model of Brownlees et al.4 additionally assumes that the (symmetric normalized) Laplacian matrix $L$ is a function of the precision matrix $\Sigma^{-1}$ through [L = \frac{\sigma^2}{\phi} \Sigma^{-1} - \frac{1}{\phi} I_n] , where: $\sigma^2$ is a network variance parameter that does not influence the detection of the groups $\phi$ is a network dependence parameter that does not influence the detection of the groups $I_n \in \mathbb{R}^{n \times n}$ is the identity matrix of order $n$ This formula clarifies the otherwise mysterious connection20 between the Blockbuster algorithm and the NJW method. The SPONGE spectral clustering method Cucuringu et al.5 extends the spectral clustering framework described in the previous section to the case of a signed affinity matrix $A$ whose underlying complete weighted graph represents the variables $x_1$, …, $x_n$ and their pairwise correlations. Figure 4 taken from Jin et al.21 illustrates the idea of Cucuringu et al.5, which is to minimize the number of violations in the constructed partition, with a violation, as in this figure, is when there are negative edges in a cluster and positive edges across clusters21. Figure 4. Illustration of the idea behind the SPONGE clustering algorithm - minimizing the number of violations in the constructed partition. Source: Jin et al. More formally, Cucuringu et al.5 proposes a three-step algorithm22 - called SPONGE (Signed Positive Over Negative Generalized Eigenproblem) - that aims to find a partition [of the underlying graph] into k clusters such that most edges within clusters are positive, and most edges across clusters are negative5: Decompose the adjacency matrix as $A = A^+ - A^-$, with $A^+ \in \mathbb{R}^{n \times n}$, with $A^+_{ij} = A_{ij}$ if $A_{ij} \geq 0$ and $A^+_{ij} = 0$ if A_{ij} < 0 $A^- \in \mathbb{R}^{n \times n}$, with $A^-_{ij} = A_{ij}$ if $A_{ij} \leq 0$ and $A^-_{ij} = 0$ if A_{ij} > 0 Compute the (unnormalized) positive and negative Laplacian matrices $L^+$ and $L^-$, with $L^+ \in \mathbb{R}^{n \times n}$, with $L^+ = D^+ - A^+$ and $D^+ \in \mathbb{R}^{n \times n}$ a diagonal matrix satisfying $D^+_{ii} = \sum_{j=1}^n A^+_{ij}$ $L^- \in \mathbb{R}^{n \times n}$, with $L^- = D^- - A^-$ and $D^- \in \mathbb{R}^{n \times n}$ a diagonal matrix satisfying $D^-_{ii} = \sum_{j=1}^n A^-_{ij}$ Compute the matrix $Y \in \mathbb{R}^{n \times k}$ made of the eigenvectors corresponding to the $k$ smallest eigenvalues of the matrix $\left( L^- + \tau^+ D^+ \right)^{-1/2} \left( L^+ + \tau^- D^- \right) \left( L^- + \tau^+ D^+ \right)^{-1/2}$, where \tau^+ > 0 and \tau^- > 0 are regularization parameters23, and cluster its $n$ rows using the $k$-means algorihm Cucuringu et al.5 establishes the consistency24 of the SPONGE algorithm in the case of $k = 2$ equally-sized clusters, provided $\tau^-$ is sufficiently small25 compared to $\tau^+$5 and the number of variables $n$ is sufficiently large26 for a clustering to be recoverable5. In subsequent work, Cucuringu et al.27 establish the consistency24 of a variant of the SPONGE algorithm - called symmetric28 SPONGE - in the case of $k \geq 2$ unequal-sized clusters when $n$ is large enough27. How to choose the number of clusters in correlation-based spectral clustering? Choosing the number $k$ of clusters is a general problem for all clustering algorithms, and a variety of more or less successful methods have been devised for this problem1. Correlation-based spectral clustering being 1) a clustering method 2) based on the spectrum of a matrix derived from 3) a correlation matrix, there are at least three families of methods which can be used to determine the “optimal” number of clusters: Generic methods Specific methods taylored to spectral clustering Specific methods taylored to correlation-based clustering or to correlation-based factor analysis However, even if it is mathematically satisfying to find such an optimal number, it is important to keep in mind that just because we find an [optimal] partition […] does not preclude the possibility of other good partitions29. Indeed, as Wang and Rohe29 puts it: We must disabuse ourselves of the notion of “the correct partition”. Instead, there are several “reasonable partitions” some of these clusterings might be consistent with one another (as might be imagined in a hierarchical clustering), others might not be consistent. Generic methods Any black box method to select an optimal number of clusters in a clustering algorithm - like the silhouette index30 or the gap statistic31 - can be used in correlation-based spectral clustering. On an opinionated note, though, the the elbow criterion should not be used, for reasons detailled in Schubert32. Specific methods taylored to spectral clustering In the context of spectral clustering, several specific methods for determining the optimal number of clusters have been proposed. The most well-known of these methods is the eigengap heuristic1, whose aim is to choose the number $k$ such that all eigenvalues $\lambda_1$,…,$\lambda_k$ [of the Laplacian matrix] are very small, but $\lambda_{k+1}$ is relatively large1. In practice, this method works well if the clusters in the data are very well pronounced1. Nevertheless, the more noisy or overlapping the clusters are, the less effective is this heuristic1, which is obviously a problem for financial applications33. Furthermore, just because there is a gap, it doesn’t mean that the rest of the eigenvectors are noise29. Another popular method is the method used in the self-tuning spectral clustering algorithm of Zelnik-Manor and Perona34, which selects the optimal number of clusters as the number allowing to “best” align the (rows of the) eigenvectors of the Laplacian matrix with the vectors of the canonical basis of $\mathbb{R}^{k}$. Specific methods taylored to correlation-based clustering or to correlation-based factor analysis Correlation-based clustering, whether spectral or not, revolves around a very special object - a correlation matrix -, whose properties can be used to find the optimal number of clusters. Random matrix theory-based methods From random matrix theory, the distribution of the eigenvalues of a large random correlation matrix follows a particular distribution - called the Marchenko-Pastur distribution - independent35 of the underlying observations. That distribution involves a threshold $\lambda_{+} \geq 0$ beyond which it is not expected to find any eigenvalue in a random correlation matrix. Laloux et al.36 uses this threshold to define a correlation matrix denoising procedure called the eigenvalues clipping method, c.f. a previous blog post. In the context at hand, Jin et al.21 proposes to determine the optimal number of clusters as the number of eigenvalues of the correlation matrix that exceed [this threshold], which are the eigenvalues associated with dominant factors or patterns in the [original data]21. To illustrate this method, Figure 5, taken from Laloux et al.36, depicts two different Marchenko-Pastur distributions fitted to a correlation matrix of37 406 stocks belonging to the S&P 500 index. Figure 5. Smoothed density of the eigenvalues of the correlation matrix of 406 assets belonging to the S&P 500 and two fitted Marchenko-Pastur distributions, 1991 – 1996. Source: Laloux et al. From this figure, the number of clusters corresponding to the method of Jin et al.21 when applied to the dotted Marchenko-Pastur distribution would be around 15. Non-linear shrinkage-based methods De Nard38 notes that non-linear shrinkage [of the sample covariance matrix] pushes the sample eigenvalues toward their closest and most numerous neighbors, thus toward (local) cluster38. As a consequence, it should be possible to use the information from non-linear shrinkage — the number of jumps in the shrunk eigenvalues — or directly the distribution of the sample eigenvalues — the number of sample eigenvalue clusters — to obtain38 the optimal number of clusters. This method is illustrated in Figure 6 taken from de Nard38, on which 2 clusters are visible. Figure 6. Distribution of the sample eigenvalues of a covariance matrix and optimal number of groups corresponding to the centroids of that distribution (0.8 and 2). Source: de Nard. From a practical perspective, de Nard38 suggests to use 1D KDE clustering in order to determine the number of sample eigenvalue clusters. Factor analysis-based methods Although the ultimate goal of cluster analysis and factor analysis is different, the underlying logic of both techniques is dimension reduction (i.e., summarizing information on multiple variables into just a few variables)39. Based on this similarity, de Nard38 discusses the eigenvalue ratio estimator40 of Ahn and Horenstein40 that consists in maximizing the ratio of two adjacent eigenvalues [of the sample correlation matrix41] to determine the number of factors (here clusters)38 in economic or financial data40. Unfortunately, the eigenvalue ratio estimator often cannot identify any cluster [in a large universe of U.S. stocks] and sets $k = 1$38, which corresponds to the situation described in Ahn and Horenstein40 where one factor [- here, the market factor -] has extremely strong explanatory power for response variables40. In such a situation, the growth ratio estimator40 of Ahn and Horenstein40 - this time maximizing the ratio of the logarithmic growth rate of two consecutive eigenvalues to determine the number of factors - should be used instead, because it empirically appears to be able to mitigate the effect of the dominant factor40. Yet another estimator of the number of common factors is the adjusted correlation thresholding estimator42 of Fan et al.42, which determines the number of common factors as the number of eigenvalues greater than 1 of the population correlation matrix […], taking into account the sampling variabilities and biases of top sample eigenvalues42. Implementation in Portfolio Optimizer Portfolio Optimizer implements correlation-based spectral clustering through the endpoint /assets/clustering/spectral/correlation-based. This endpoint supports three different methods: The Blockbuster spectral clustering method The SPONGE spectral clustering method The symmetric SPONGE spectral clustering method (default) As for the number of clusters to use, this endpoint supports: A manually-defined number of clusters An automatically-determined number of clusters, computed through a proprietary variation of Horn’s parallel analysis method43 (default) As a side note, Horn’s parallel analysis method seems to be little known in finance, but numerous studies [in psychology] have consistently shown that [it] is the most nearly accurate methodology for determining the number of factors to retain in an exploratory factor analysis44. Examples of usage Automated clustering of U.S. stocks De Nard38 and Jin et al.21 both study the automated clustering of a dynamic universe of U.S. stocks through correlation-based45 spectral clustering: De Nard38, in the context of covariance matrix shrinkage It uses the Blockbuster method, together with a 1D KDE clustering method to automatically determine the number of clusters. Jin et al.21, in the context of the construction of statistical arbitrage portfolios It uses the SPONGE and SPONGE symmetric methods, together with a Marchenko-Pastur distribution-based method46 to automatically determine the number of clusters. An important remark at this point. When clustering stocks, it is possible to rely on what de Nard38 calls external information38, for example industry classifications like: The Standard Industrial Classification The MSCI Global Industry Classification Standard Nevertheless, such an external information may fail to create (a valid number of) homogeneous groups38. In the words of de Nard38: For example, if we cluster the covariance matrix into groups of financial and nonfinancial firms, arguably, there will be some nonfinancial firm(s) that has (have) some stock characteristics more similar to the financial stocks as to the non-financial stocks and is (are) therefore misclassified. Especially in large dimension one would expect a few of such misclassifications in both directions. To overcome this misclassification problem and to really create homogeneous groups, [a data-driven procedure should be used instead]. Results of de Nard38 and Jin et al.21 are the following: Within a universe of 500 stocks over the period January 1998 to December 2017, de Nard38 finds that the number of clusters is limited to only 1 or 2 about 75% of the time. Within a universe of ~600 stocks over the period January 2000 to December 2022, Jin et al.21 finds that the number of clusters is relatively stable arou