The coMAD (co-median absolute deviation) is a measure for the joint median of two random variables. Previous experiments have shown that a coMAD-based PCA is more robust towards noise and outliers, yielding eigenvectors which represent linear correlation better than its covariance-based competitors. In this preliminary work we introduce CODEC - COrrelations in DEnse Clusters - a method for detecting linear correlations in dense clusters utilizing a coMAD-based PCA. The idea of CODEC is intriguingly simple: rst a density-based clustering is performed using the well established clustering method DBSCAN. Then on each of the clusters PCA is performed. Instead of using the covariance matrix we use the coMAD matrix as a basis for performing PCA.
As Data Analysis is becoming more and more important in recent years, a multitude of possible interesting properties of datasets have emerged. Clustering, which constitutes a huge eld of data analysis with diverse sub-categories, leverages these properties to nd sets of points which are similar to each other, but dissimilar to points of other sets or clusters. This similarity can be based on density, on the distance to centroids, or how well they t to a certain distribution. On the other hand, points which are correlated only in certain dimensions can also be interpreted as similiar, which is covered by subspace and correlation clustering algorithms. Surprisingly only few algorithms combine both concepts, and, to the best of our knowledge, none of them investigate found clusters further regarding possible correlations. Especially density-based clusters, which can be of any shape, can contain correlated data (rather than centroid-based clusters for example, which tend to have similar extensions in every dimension). Thus, we introduce CODEC, a new prototype algorithm which nds correlations in density-based clusters found by DBSCAN using an improved version of PCA to Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). account for dispersions. We have found that using the coMAD matrix instead of the covariance matrix, we nd less distorted main components of correlation clusters.
We provide an overview over related work in Section 2, including an introduction of the improved PCA using the coMAD (co-median absolute deviation) matrix. In Section 3 the algorithm is explained in detail and tested in Section 4. Section 5 concludes this short paper and gives ideas for future work. 2
There already exist several sophisticated methods which detect linear correlated
clusters, such as ORCLUS[
Since the coMAD is one of the core elements of our method, we will rst elaborate on the de nition of the coMAD. Suppose we are given a data matrix D of dimensionality d, where the rows represent a data record and their respective columns represent the features (A1; :::; Ad). If we consider the variance, its analogon in the median context would be the median absolute deviation from the median (MAD): mad(Ai) = med(jAi med(Ai)j)
Then the analogon to the covariance is the coMAD which is a generalization of the MAD: com(Ai; Aj ) := med((Ai med(Ai))(Aj med(Aj ))) Finally we use the de nition of the coMAD to construct the coMAD matrix known as:
0 mad(A1) . .
. com(Ad; A1) . . .
com(A1; Ad) 1
... CA mad(Ad)
Based on the coMAD matrix the PCA is performed which yields the corresponding eigenpairs.
Our algorithm then proceeds as follows: First, dense clusters are detected by applying DBSCAN on the data set. Then on each of the dense clusters PCA is applied, using the coMAD instead of the covariance matrix. As a result we obtain a set of eigenvectors for each cluster, which show the direction of linear CODEC - Detecting Linear Correlations in Dense Clusters correlations within the clusters. The intuition here is that instead of the direction of highest variance (which would be the classical result using the covariance matrix), the eigenvectors now point in the direction of the highest MAD, therefore the direction where most points are situated. This leads to the PCA being less contaminated by noise points that diverge from the main direction of linear correlation.
One may think that a dense cluster should already be almost without any noise. This however depends on the density of the clusters which is implicitly determined by the choice of the hyperparameters of DBSCAN, namely "-range and minpts for the minimum number of objects required to be located within an "-range. The larger the "-ranges and the lower minpts, the less dense are clusters. Further the so called 'border points' can, depending on the "-range, have similar e ects as outliers and therefore skew the principal components of a PCA. In Section 4 we show a case where PCA based on the covariance matrix yields skewed results compared to PCA using the coMAD matrix. 4
As a rst experiment of our preliminary work, we constructed a data set with four clusters exhibiting linear correlations, both locally and globally, as it can be seen in Figure 1 (top left). Furthermore, each of these clusters are not perfectly linearly correlated but studded with noise. From a high-level view one could state that the noise should not have any impact on the result of the PCA. However, if we apply a covariance-based PCA on each of the dense clusters, the resulting eigenvectors are signi cantly skewed, as it can be seen in Figure 1 (top right). Especially in the blue cluster the noise leads to a massive distortion of the expected direction. The e ects of using a coMAD-based approach become visible in Figure 1 (bottom), where despite the noise the detected eigenvectors remain robust. The algorithm and data generator used for the experiment were implemented in python and are publically available 1. 5
In summary we developed a method to nd correlations in density-based clusters accurately and robust to noise and jitter. We showed that using the coMAD matrix for PCA delivers more intuitive results than using the covariance matrix, especially for real-world data which is usually not correlated perfectly. We plan to examine further combinations of correlation clustering and densitybased clustering in future work. Investigating the trade-o between e ciency of the computation and improvement of the results using the coMAD matrix is a further subject of future work. 1 https://github.com/huenemoerder/CODEC