Adaptive Weighted Nonnegative Matrix Factorization for Robust Feature Representation

NMF decomposes a nonnegative matrix $X\in R^{M\times N}$ into the product of two low-dimensional nonnegative matrices: one is the base matrix $W\in R^{M\times L}$ and the other is the representation matrix $H\in R^{L\times N}$, where $L<<min\{M,N\}$. It can be formulated as:

As well known, it is difficult to be solved, even there may be no solution, so we turn to an optimization method for achieving the best approximation. There are many criteria to measure the similarity between $X$ and $WH$. In general, the square of the Frobenius norm and the Kullback-Leibler (KL) divergence are used. In this paper, the square of the Frobenius norm is adopted and the formula is expressed as:

Although the objective function is convex quadratic function on either $W$ or $H$, it isn’t convex for both of them. Thus, it will be alternatively minimized with regard to $W$ and $H$, in which the constructed auxiliary function will be important to derive the iterative update rule.

Then, we easily draw the following conclusion:

It can be observed that the original function should decrease if the auxiliary function reaches the minimum. Now, we drive the update rule for NMF. Consider $W$ first, where $W^{t}>0$ and $H>0$ are fixed. Let $\xi_{ijk}=W^{t}_{ik}H_{kj}/(W^{t}H)_{ij}$, certainly, $\xi_{ijk}\geq 0$ and $\sum_{k=1}^{L}\xi_{ijk}=1$. Therefore, the auxiliary function is as below:

The function is separable and its minimization is equivalent to the solutions of some univariate optimizaiton problems. Take the partial derivative of Eq. (7) and set it to zero so that the following update rule is got.

Similarly, the update of $H$ is obtained:

Different from the previous methods that use a similarity measure with slow growth for outliers, we introduce an optimizable weight $Q_{j}$ to emphasize the importance of each data point, in which an outlier will be paid less attention than a normal point.

We first consider the solution to $Q$ in an alternative optimization manner. Obviously, for fixed $W$ and $H$, $Q_{j}$ can be solved as $Q_{j}=1$ if $Z_{j}=min\{Z_{1},Z_{2},...,Z_{N}\}$, otherwise 0, where $Z_{j}=\sum_{i=1}^{M}(X-WH)_{ij}^{2}$. The derivation is very easy, which is similar to that of the membership degree in k-means [13]. It demonstrates the simple fact that only one $Q_{j}$ is 1, and the others are 0, i.e., the only one data point is involved in NMF. Such a phenomenon is certainly incompatible with the real problem. In fact, we generally think that the weights are in the range of $[0,1]$ instead of 0 or 1, which is more consistent fuzzy logic thinking process. To address this issue, we propose two methods as follows.

Obviously, the proposed techniques are irrelative to the measure between $X$ and $WH$, so it can easily be popularized to KL-divergence, $\alpha$-divergence, Orthogonal NMF, ConvexNMF, etc, which demonstrates its good compatibility. We omit the derivation processing since it is very similar to the proposed ones.

Experiments were performed on an HP Compaq PC with a 2.90-GHz Core i7-10700 CPU and 16 GB memory, and all the methods were implemented in MATLAB. We compared the performance of the two proposed methods with the traditional NMF (named EucNMF), ConvexNMF, NMFL2 and HuberRNMF on nine public datasets, including the Yale, ORL, GTFD, Winequality-red, Page-blocks, Balance, Thyroid, WDBC and Dimdata. The important details of these datasets are shown in Table 1. We add Gaussian noise to the data to interpret the robustness of the methods as below:

where $c$ control the noise level and $N(0,X_{ij})$ follows a Gaussian distribution with mean 0 and variance $X_{ij}$. It implies that noise relates to the scale of data, and a bigger value corresponds to a higher noise, which is reasonable in practical applications.

After obtaining a new feature representation, we use k-means to cluster them and then evaluate the clustering results. Clustering accuracy (ACC) [16], [17] and normalized mutual information (NMI) [18], [19] are used to evaluate the performance of these clustering results.

Given a set of the ground true class labels $y$ and the obtained cluster labels $y^{\prime}$, the clustering accuracy is defined as:

where:

and $map(\cdot)$ is a permutation mapping function that maps the obtained cluster labels to the real labels. The higher the ACC value is, the better the clustering performance.

NMI is used to calculate the agreement between the two data distributions and is defined as follows:

where $H(y)$ is the entropy of $y$. $MI(y,y^{\prime})$ quantifies the amount of information between two random variables (i.e., $y$ and $y^{\prime}$) and is defined as:

where $p(y_{i})$ and $p(y^{\prime}_{j})$ are the probabilities that a data point selected from the dataset belongs to the clusters $y_{i}$ and $y^{\prime}_{j}$, respectively; and $p(y_{i},y^{\prime}_{j})$ is the joint probability that an arbitrarily selected data point belongs to clusters $y_{i}$ and $y^{\prime}_{j}$ concurrently. NMI ranges from 0 to 1, and the larger NMI is, the better the clustering performance.

Because NMF does not have a sole solution, we randomly initialized 10 times to obtain an averaged ACC and NMI for a creditable comparsion. And we force reduced dimensionalty to equal to clustering number, which is a usual practice.

We first compare all the methods on all the datasets, in which the hyperparameters of HuberRNMF, FWRNMF and EWRNMF are optimally from $cutoff\in\left\{10^{i},i=-4,-3,...,3,4\right\}$, $p\in\left\{1.5,2,...,10.5,11\right\}$, and $\gamma\in\left\{10^{i},i=-4,-3,...,3,4\right\}$, respectively. The noise level is set to be $c=0.05$. In the following experiments, we always use such a noise level unless otherwise specified. The optimal hyperparameter statergy is also used in the following experiments unless otherwise stated. Clustering results are shown in Tables 2 and 3. We can see that either FWRNMF or EWRNMF always exhibits better performance than other methods, meanwhile NMF2L and HuberRNMF are generally better than the traditional NMF and ConvexNMF. It demonstrates the feasibility and effectivity of the proposed methods. In general, none of FWRNMF or EWRNMF has established total supremacy over each other.

We inspect the ability of FWRNMF and EWRNMF to improve the performance of the traditional NMF on the Yale and WDBC datasets for dimensionality reduction and k-means clustering. The hyperparameters of FWRNMF and EWRNMF are still selected optimally as above. As shown in Figures 1 and 2, regardless of the hyperparameter $p$ or $\gamma$, the proposed methods indeed provide better performance than the traditional NMF and can achieve a consistently superior clustering result on extensive hyperparameters.

We investigate the robustness of the proposed methods with regard to different noise levels on two datasets: GTFD and Balance, which add Gaussian noise to each dataset by Eq. (30) with the noise level $c$ ranging from 0.02 to 0.1. The results are shown in Figures 3 and 4. It can be seen that the effect of FWRNMF is particularly prominent in GTFD and EWRNMF performs well in Balance. Furthermore, regardless of which dataset, either of two proposed methods always obtains the best results, which shows a strong robustness.

We study the relationship between the evaluation standards and cluster number on the Yale and GTFD datasets, where cluster number ranges from 2 to 10 are selected. The experimental details are described as follows:
1) Randomly select k categories as a subset for the following experiment.
2) Randomly initialize $W$, $H$ and obtain new representations, then cluster them by k-means. Hyperparameters are selected according to the above instruction.
3) Repeat 1) and 2) 10 times to obtain an average result.

It can be seen in Figures 5 and 6 that either of our methods is better than the other methods. In detail, for the Yale dataset, EWRNMF is the best, for the GTFD dataset, FWRNMF is the best; however, none of the proposed methods is always the best.

We will directly visualize the results of the NMF methods for qualitative comparison. The Dimdata dataset is selected, in which we reduce the dimension number of the original data to two dimensions since it includes two clusters. The separability of new representation ($H$) can be directly observed in Figure 7. By the naked eye, it is easy to observe that the new representations obtained by FWRNMF and EWRNMF have good separability if considering a center-distance-based clustering method such as k-means. This explains why they obtain an extremely excellent result in Tables 2 and 3 regardless of accuracy or NMI.

From the theoretical analysis, we know that the objective function of the proposed methods are monotonically decreasing, but due to the nonconvexity of the objective function, it cannot be guaranteed to be strictly convergent, which is the commonplace in character for NMF methods [20]. Thus, we investigate the convergence speed of the NMF methods. Figure 8 shows the objective functions on the ORL dataset which are obtained by EucNMF, ConvexNMF, NMFL2, HuberRNMF, FWRNMF and EWRNMF. The convergence speed of the proposed FWRNMF is relatively slow, but EWRNMF shows an excellent performance. However, both methods basically show convergence when iterating 200 times. We also show the base images in Figure 9. As can be seen, ConvexNMF identifies more global faces; and the other methods present similar sparse base images that are difficult to distinguish from each other.