Decorrelated Clustering with Data Selection Bias

1 Introduction

One common hypothesis in traditional machine learning is that the data is drawn from an unbiased distribution, in which there are weak correlations between features [Heckman, 1979; Huang et al., 2007]. However, in many real world applications, we cannot fully control the data gathering process and always suffer from the data selection bias issue, which will inevitably cause the correlations between features. Unexpected high feature correlation is undesirable, as it not only brings redundancy in features, but also causes the algorithm to unsatisfied results [Zhang et al., 2018]. Some literatures have studied the problem of removing the feature correlation effect in machine learning model [Bengio and Bergstra, 2009; Cogswell et al., 2016; Rodr´ıguez et al., 2017; Zhang et al., 2018]. They mainly focus on removing the feature correlation effect in neural networks by designing decorrelation components, which bring great benefits for representation learning.

∗Corresponding Author.

Despite the enormous success of decorrelation in neural networks, the effect of data selection bias is severely underestimated in unsupervised learning scenario. Typically, clustering also suffers from the data selection bias issue [Kriegel et al., 2009]. Data selection bias may cause spurious correlation between features. Assuming one meaningless feature is mistakenly identified to correlate with one important feature, because of the presence of spurious correlation, the effect of this meaningless feature will be unconsciously strengthened, rendering the inherent data distribution unrevealed. Thus clustering on these data will inevitably result in poor performance. As depicted in Figure 1, given an image dataset with many dogs on the grass and some cats in various backgrounds, it is easy to draw a conclusion that grass features are highly correlated with dog features and cat features have low correlation with background. Therefore, when performing clustering algorithm on such biased dataset, any object on the grass, even a cat, will be clustered to the dog cluster with large probability. This implies that clustering is very easily misled by the presence of spurious correlations between features. However, most of existing clustering algorithm [Hartigan and Wong, 1979; Bachem et al., 2018; Schmidt et al., 2018; Von Luxburg, 2007] do not take the data selection bias into consideration, and the feature correlation effect in clustering is largely ignored.

Although it is promising to marry feature decorrelation with clustering, there are two unsolved challenges. (1) How to remove the correlations between features in highdimensional scenarios? In real applications, the correlations between features might be very complex, especially in highdimensional settings. Moreover, we have little prior knowledge about which correlations are unexpected and would hurt clustering performance. In practical, one possible way is to remove correlations between each targeted feature with the remaining features one by one, but obviously this method suffers from huge model complexity. Therefore, we need to design efficient feature decorrelation method. (2) How to make the feature decorrelation benefit for clustering? Feature decorrelation and clustering are traditionally two independent tasks. Because they have different objectives, feature decorrelation does not necessarily lead to good clustering. Therefore, we need to discriminatively remove correlations for clustering. To achieve this goal, a task-oriented feature decorrelation framework is highly desirable. However, it is highly non-trivial to design a scalable feature decorrelation method for clustering problem, because feature decorrelation usually cannot be directly incorporated with clustering objective.

In this paper, we propose a novel Decorrelation regularized K-Means (DCKM) model for clustering on data with selection bias. Specifically, to decorrelate one targeted feature with the remaining features, a decorrelation regularizer is introduced to balance the remaining feature distributions through learning a global sample weight matrix. Meanwhile, the weight matrix is employed to reweight the k-mean loss. In this way, the weighted k-means and decorrelation regularizer are in a unified framework, causing that clustering results are not affected by unexpected correlated features. Moreover, we derive an effectively iterative updating rules to optimize the parameters of our model. Our contributions are summarized in the following three folds:

• We investigate an important but seldom studied problem, i.e., clustering on data with selection bias. The correlation caused by the data selection bias is ubiquitous in real applications, while the effect of the correlation in clustering is largely unexplored.
• We propose a novel Decorrelation regularized K-Means (DCKM) model which removes the unexpected correlations among features for clustering by a decorrelation regularizer. Moreover, we derive an effectively updating algorithm to optimize the parameters of DCKM.
• We conduct comprehensive experiments, where the significant performance gains demonstrate the superiority of our method in clustering on the biased data.

2 Preliminaries

Notations. In our paper, n refers to the sample size, and d is the dimensions of features. For a vector v ∈ Rd×1 , vi represents the i-th element of v and ||v||22 = ∑di=1 v2 i . For any matrix X ∈ Rn×d , we denote Xi. and X.j represent the i-th row and the j-th column in X, respectively. And ||X||2F = ∑ni=1 ∑dj=1 X2ij .

Problem Definition. Clustering on Data with Selection Bias . Given n samples with d-dimensional features, represented by X ∈ Rn×d , the task is to learn a robust clustering model, which will not be affected by the unexpected correlations between features, to partition the n samples into predefined K disjoint clusters {C1, · · · , CK}.

Definition 1. Remaining Features. If we treat the j-th feature of X (i.e., X.j) as targeted feature, X.-j = X\X.j are regarded as remaining features, which is from X by replacing its j-th column as 0.

Definition 2. Treated Group and Control Group. Given the targeted feature X.j , if the j-th feature of sample i: Xij = 11 , then the sample Xi. is a treated sample, and the treated group is a sample set TGj = {Xi.|Xij = 1}; otherwise, the sample set CGj = {Xi.|Xij = 0} is a control group.

It is well recognized that k-means is one of the most representative clustering algorithms. Thus, to validate the necessity of decorrelation when clustering, we focus on k-means algorithm and propose a novel decorrelation regularized kmeans method. Here, we first introduce some preliminaries in k-means clustering.

K-means and matrix factorization. The classical kmeans clustering is a centroid-based clustering method, which partitions the data space into a structure known as Voronoi diagram. Besides, the G-orthogonal non-negative matrix factorization (NMF) is equivalent to relaxed k-means clustering [Ding et al., 2005], which can be reformulated as:

where F ∈ Rd×K is the cluster centroid matrix, G ∈ Rn×K is the cluster assignment matrix, each row of which satisfies the 1-of-K coding scheme, i.e., if data point Xi. is assigned to k-th cluster, then Gik = 1; otherwise, Gik = 0.

3 Decorrelation Regularized K-means

3.1 Decorrelation Regularizer

Recalling the example in Figure 1, we assume the j-th feature represents whether the image has dog feature and the t-th feature indicates whether the image has grass feature. If the majority of dogs are on the grass, then the j-th and the t-th feature will be highly correlated. As a result, when perform clustering on such data, the t-th feature, i.e., the grass feature, will probably mislead the algorithm to cluster other kinds of images with grass and dogs into the same cluster. One alternative solution to alleviate the data selection bias is to add extra dog images with other backgrounds, so that the j-th feature will not correlate with the t-th feature, but it is difficult to obtain extra data in many real applications.

1 Please note that, without losing any generality, here we assume all the features are binary for the ease of discussion and understanding (categorical and continuous features can be converted to binary ones through binning and one-hot encoding).

Instead, we adjust data distribution by learning a sample weight for each sample so that all the features trend to be independent [Shen et al., 2018; Kuang et al., 2018; Kuang et al., 2020; Shen et al., 2020]. Specifically, we first focus on how to remove correlation between the j-th targeted feature X.j and the correspondingly remaining features X.-j .

Single feature decorrelation regularizer. If the targeted feature X.j correlates with the remaining features X.-j, the treated and control groups, TGj and CGj, will have different distributions on X.-j . Once we balance the distributions between TGj and CGj , we are able to reduce the correlation between the targeted feature and the correspondingly remaining features. As moments can uniquely determine a distribution [Shen et al., 2018], we use the first-order moment to measure the distributions. Specifically, for the remaining features in treated group TGj, the first-order moment is:

where 1n = [1, 1, · · · , 1] ∈ Rn×1 . Similarly, the first-order moment of the remaining feature in control group CGj is:

To balance the moments ¯X.-j and ˆX.-j, we introduce the sample weights wj ∈ Rn×1 to adjust the value of moments, which can be learned by:

where '⊙' refers to the Hadamard product. The first term XT.-j ·(wj ⊙X.j ) wj T ·X.j is the weighted moment of TGj and the second term XT.-j ·(wj ⊙(1n-X.j )) wj T ·(1n-X.j ) is the weighted moment of CGj. By optimizing Eq. (4), the two terms will be balanced. After remaining features balancing, the targeted feature selection bias will be corrected and the correlation between the tar-

geted feature and remaining features will tend to be removed.

Global feature decorrelation regularizer. Note that the above method is to remove the correlation between a single targeted feature X.j with the remaining features X.-j . However, we need to remove the correlations of all features with the correspondingly remaining features. This implies that we need to learn n × d sample weights, which is apparently infeasible in high-dimensional scenarios. However, because d sets of sample weights {wj }dj=1 are used to adjust the same set of n samples, the sample weights for different targeted feature can be shared. Thus we introduce a global balancing method as the decorrelation regularizer. Specially, we add all the single feature remaining feature balancing term together, in which each balancing term is formulated by setting each feature as targeted feature, and for all the remaining feature balancing term, they use the same set of sample weights w ∈ Rn×1 :

As we can see from Eq. (5), the global sample weights w simultaneously balance all the remaining feature terms, which yields the correlations between all features tend to be removed.

3.2 Decorrelation Regularized K-means

In the traditional k-means model Eq. (1), the cluster centroid F and the cluster assignment G are learned on the original feature X. But the unexpected highly correlated features may confuse the data distribution, which yields to unsatisfied clustering results. Because the sample weights w learned from the decorrelation regularizer are capable of globally decorrelating the features, we propose to use the weights to reweight the k-means loss and jointly optimize the weighted k-means loss and decorrelation regularizer:

The term w ⪰ 0 constrains each of sample weights to be non-negative. With norm ||w||22 ≤ γ2, we can reduce variance of the sample weights to achieve stability. The formula (∑ni=1 wi - 1)2 ≤ γ3 avoids all the sample weights to be 0. Although DCKM still performs on data X, the weight of each Xi. is no longer same. This weight adjusts the contribution of each data in the entire loss, so that the cluster centroid and the cluster assignment are learned on the decorrelated features which can better reveal real data distribution.

3.3 Optimization

The constrained matrix factorization objective Eq. (6) is not convex, and we separate the optimization of Eq. (6) into three subproblems and iteratively optimize them. Next we describe the optimization process in detail.

The function Eq. (6) is equal to minimize J (w, F,G):

To optimize Eq. (7), we iteratively update three parameters (i.e. F, G, w), which are described below:

F-subproblem : When updatingFwithwandGin Eq. (7) being fixed, we need to optimize the following objective function:

which is a form of weighted k-means. Taking derivative of J (F) with respect to F, we get

Setting Eq. (9) to 0, we can update F as:

G-subproblem : When updating G with F and w in Eq. (7) being fixed, we need to optimize the following objective function:

We can solve Eq. (11) by decoupling the data and assigning the cluster indicator for them one by one independently. In particular, we optimize Gi. for each sample i respectively:

We can see that wi will not influence the optimal Gi.. Given the fact that Gi. satisfies 1-of-K coding scheme, there are K candidates to be the solution of Eq. (12), each of which is the k-th column of matrix IK = [e1, e2, · · · , eK]. To be specific, we can perform an exhaustive search to find out the solution of Eq. (12) as,

where k is decided as follows,

w-subproblem : When updating w with F and G in Eq. (7) being fixed, we need to optimize the following objective function:

We let w = ω ⊙ ω to ensure non-negativity of w, where ω ∈ Rn×1 . Then Eq. (15) can be reformulated as:

The partial gradient of term J (ω) with respect to ω is:

where

Then we update ω using gradient descent, and finally update w(t) at the t-th iteration with:

We update F, G and w iteratively until the objective function Eq. (7) converges. As we can see from Eq. (17), the partial gradient of term J (ω) with respect to ω is not only related to decorrelation term but also influenced by the weight k-means loss, so the learned sample weight w will decorrelate the features as well as benefit for clustering.

ComplexityAnalysis The overall complexity of each iteration of DCKM is O(Knd + nd2 ), which is linear with respect to n.

4 Experiments

Dataset

• Office-Caltech dataset [Gong et al., 2012]. The officecaltech dataset is a collection of images from four domains (DSLR, Amazon, Webcam, Caltech), which on average have almost a thousand labeled images with 10 categories. It has been widely used in the area of transfer learning [Long et al., 2014], due to the biases created from different data collecting process. We use SURF [Bay et al., 2006] and Bag-of-Words as image features, where the dimension is 500.
• Office-Home dataset [Venkateswara et al., 2017]. It is an object recognition dataset which contains hundreds of object categories found typically in Office and Home settings. To extensively evaluate our method, we randomly sample 3 subsets from the dataset where each subset contains 10 classes (marked as OH1, OH2, OH3) and each class has hundreds of images. We also use SURF and Bag-of-Words as image features, where the dimension is 500.

Baselines Because our proposed model is based on kmeans, k-means is the most direct baseline. Moreover, unsupervised feature selection algorithms can delete useless features by an unsupervised way, so we also compare with several unsupervised feature selection algorithms: RUFS [Qian and Zhai, 2013], FSASL [Du and Shen, 2015], and REFS [Li et al., 2017]. All the unsupervised feature selection methods first select the useful features and then feed the selected features into the k-means algorithm. Furthermore, we implement three straight-forward two-step decorrelated methods to validate the necessary of jointly training.

• PCA+KM [Ding and He, 2004]: We first perform PCA to reduce the feature dimension while removing the feature correlations, and then perform k-means.
• Drop+KM: We first compute each feature's correlation with other features and then drop the highly correlated features. K-means performs on the remaining features.
• Dec+KM: We first perform decorrelation regularizer Eq. (5) only to learn the sample weights and then apply the weighted k-means.

Note that, because our model is based on k-means method, we mainly select k-means based methods as baselines to validate the effectiveness of the proposed decorrelation regularization. The decorrelation regularizer can also be easily extended to other clustering paradigms, such as the autoencoder-based clustering, which is the future work.

Parameter Setting andMetrics. For DCKM, we fix λ3 = 1 and select λ1 and λ2 from {10-2 , 10-1 , 1, 10, 102 , 103 }. For Drop+KM, we set the highly correlation features threshold as 0.7. For PCA+KM, following [Ding and He, 2004], we set the reduced dimension as K-1, where K is the number of clusters. Because all the unsupervised feature selection methods are relatively sensitive to the number of selected features, we "grid-search" the number of selected features from {50, 100, · · · , 450}. And for all the methods, the number of clusters, i.e., K, is decided by the classes of each subdatasets. Since all the clustering algorithms depend on the initializations, we repeat all the methods 20 times using random initialization and report the average performance. We employ two widely used clustering metrics: NMI and ARI [Fan et al., 2020].

Clustering Result Analysis Table 1 shows the clustering results, and we have following observations. (1) Our DCKM model achieves the best performance on almost all the datasets (from 8.2% to 48.5% improvements compared to the best baseline). Particularly, compared with k-means, DCKM significantly outperforms it with the 25.1% average improvement ratio on NMI. This well demonstrates the effectiveness of integrating the decorrelation regularizer with k-means. (2) Two-step decorrelated approaches (PCA+KM, Drop+KM, and Dec+KM) are not always better than kmeans, which indicates that removing correlations between features do not necessarily benefit for clustering. We should remove the unexpected correlations which hurt the clustering performance. (3) DCKM outperforms the two-step decorrelated approaches, especially the Dec+KM method, which clearly demonstrates the importance of jointly optimizing decorrelation regularizer and clustering. (4) DCKM also outperforms various unsupervised feature selection methods. The reason is that these unsupervised feature selection methods reduce the correlation by deleting some features and some meaningful features may be deleted, while our DCKM keeps all features and removes the correlations among them. Moreover, unsupervised feature selection methods are sensitive to the number of selected features [Li et al., 2017], but our method does not have such problem.

Sample Weight Analysis Here we analyze the effect of sample weights w in our model. We compute the amount of correlations in original unweighted dataset and the weighted dataset, in which the weights are the last iteration sample weights of DCKM. Following [Cogswell et al., 2016], the amount of correlations is measured by the Frobenius norm of the sample cross-corvairance matrix computed from the features of samples. Figure 2 shows the amount of correlations in unweighted dataset and weighted dataset, and we can observe that the feature correlations in all the weighted datasets are reduced, demonstrating that the weights learned by DCKM can reduce the correlations between the features. Since the major difference between DCKM and a standard k-means is the decorrelation regularizer, we can safely attribute the significant improvement to the effective decorrelation regularizer and its seamless joint with k-means.

Parameters Sensitivity In this subsection, we study the sensitiveness of parameters. Limited by space, we just report the results on four subdatasets of Office-Caltech with λ3 = 1 (sensitiveness under other values of λ3 is similar) on Figure 3. The experimental results show that DCKM is relatively stable to λ1 and λ2 with wide ranges, indicating the robustness of DCKM.

5 Conclusion

In this paper, we investigate a seldom studied but important problem: clustering on data with selection bias. The data selection bias will inevitably introduce correlations between the features, making the data distribution confuse for clustering.

We then propose a novel decorrelation regularized k-means model, which combines the feature balancing technique with k-means in a unified framework. Extensive experimental results well demonstrate the effectiveness of DCKM.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. U1936220, 61702296, 61772082, 61806020, U1936104), the National Key Research and Development Program of China (2018YFB1402600), the CCFTencent Open Research Fund, and the Fundamental Research Funds for the Central Universities. Kun Kuang's research was supported by the Fundamental Research Funds for the Central Universities; National Key Research and Development Program of China No. 2018AAA0101900. Shaohua Fan's research was supported by BUPT Excellent Ph.D. Students Foundation (No. CX2019127).