Fast Robust Non-Negative Matrix Factorization for Large-Scale Human Action Data Clustering

1 Introduction

Human action recognition is very useful in improving human life in various aspects, like smart home applications, rehabilitation, human-computer interaction, etc. To recognize human action is helpful to know one's intent, such that an intelligent system could make corresponding reactions. However, in the real world life, the data are not as clean as we want, and there might be many outliers and noise. For example, it is common that part of the human body is shielded behind an obstacle, which makes the human action difficult to recognize. Therefore, robust data mining techniques should be developed in order to achieve good performance.

Non-negative matrix factorization (NMF) and nonnegative matrix tri-factorization (NMTF) are models which aim to factorize a matrix into non-negative matrices with minimum reconstruction error. It has been widely researched and used in various kinds of applications, like document coclustering [Li and Ding, 2006], computer vision [Lee and Seung, 1999], social network analysis [Huang et al., 2013], bioinformatics [Wang et al., 2012; 2014b], knowledge transfer [Wang et al., 2011; 2015] and many others.

⇤To whom all correspondence should be addressed. This work was partially supported by US NSF-IIS 1117965, NSF-IIS 1302675, NSF-IIS 1344152, NSF-DBI 1356628, NIH R01 AG049371.

Different kinds of NMF and NMTF models are proposed these years. The standard NMF factorize a non-negative matrix into two non-negative matrices. [Ding et al., 2005] discussed the equivalence relationship between K-means, NMF and spectral clustering. Later, [Ding et al., 2010] proposed two NMF models: semi-NMF and convex NMF. In many situations, the data matrix may contain negative elements. In such situation, it is not suitable to enforce the non-negative constraints on NMF model factors. Different from standard NMF, semi-NMF relaxed the non-negative constraint on NMF models, allowed one factor to be mix-signed. In convex NMF, the author restricts that the centroid to be a linear combination of samples. Such model has better interpretability, however, the performance may not be as good as other NMF models [Li and Ding, 2006]. [Ding et al., 2006] proposed to add orthogonality constraints in the cluster indicator factor G. This property will enforce the solution of G to have a clear cluster structure, which is desirable for using NMF for clustering. It is pointed out in [Gu et al., 2011] that the orthogonal constraint can prevent trivial solution of NMF models. [Gu and Zhou, 2009] combines Laplacian graph based algorithms with NMF to enforce the smoothness on data manifolds. [Kong et al., 2011; Gao et al., 2015] proposed robust NMF models which are robust to outliers.

Most previous works can not achieve good clustering results when there exist outliers in the data. Presence of outliers is very common in real world applications. For example, in human action recognition, it is common that part of the human body is shielded behind an obstacle, which makes the human action difficult to recognize. Therefore, robust data mining techniques should be developed in order to achieve good performance.

In view of the above considerations, we propose three NMF and NMTF models which converge as fast as K-means, and are robust to outliers.

Notations: Given a matrix X 2 Rn⇥m, its i-th row and j-th column are denoted by Xi▷, X▷j, respectively. The `r↪p-norm of a matrix is defined as:

kXkr↪p = (Pni=1 (Pmj=1 ♣xij♣r ) pr ) 1p . According to this definition, we can get the following norms:

2 New Fast Algorithms for Robust NMF and NMTF Models

2.1 Motivations

NMF models often have the following form of objective functions, subjecting to different kinds of constraints.

where X 2 Rd⇥n + is a data matrix with d features and n samples. Such models have close relation to K-means clustering as pointed out in [Ding et al., 2005]. F 2 Rd⇥c + can be viewed as cluster centroids, and G 2 Rn⇥c + can be viewed as clustering indicator matrix.

Many previous NMF work [Ding et al., 2010; 2006; Lee and Seung, 2001; Kong et al., 2011] use a soft indicator matrix G, i.e., elements in G are continuous values. Algorithms for those models are based on matrix multiplicative updating rules. However, these algorithms converge very slowly, often need hundreds or even thousands of iterations before convergence. Considering the computational cost of large matrix multiplication, such algorithms usually take a long time to converge. In addition, an additional postprocessing step need to be performed to get the final clustering labels using the soft indicator matrix G.

On the other hand, outliers are very common in real world data problems. For example, in image recognition problems, there maybe different extent of noise due to different conditions of illuminations, viewpoints, wearings, etc. Also, human measurement and recording errors may also incur many outliers. Previous NMF models using Frobenius norm as loss measurement can not get good clustering results if there exist outliers/noise in the data. This is because the loss term will be dominated by outliers, thus the loss of other normal data points will be disregarded. We will show this using a synthetic data set in the experimental section. Therefore, developing robust models to handle data with outliers is important.

To address the above challenges, in this paper, we propose three new fast robust NMF and NMTF models.

2.2 New Fast Robust NMF and NMTFModels

To make the NMF/NMTF models robust to outliers, instead of using Frobenius norm, we propose to use the `2↪1-norm and

`1-norm as loss measurements. The new robust and fast NMF models aim to minimize the following objective functions:

where G 2 Ind or F 2 Ind indicates that G and F are indicator matrices, i.e. gij = 1 if xi belongs to class j, and gij = 0 otherwise. There is only one element can be nonzero in each row of binary indicator matrix. Note that in this way, the constraint GT G = I in orthogonal NMF [Ding et al., 2006] is automatically satisfied. In addition, clustering labels are directly obtained without the need for further postprocessing as in previous NMF works. While F ≥ 0 indicates that F is a non-negative matrix with all elements greater or equal to zero.

In the tri-factorization model (7), since both F and G are restricted to be binary indicators, S is introduced to absorb the magnitude in the original data matrix X. Since our methods are robust and fast NMF/NMTF models, we call the three models as RFNMF L1, RFNMF, and RFNMTF, respectively.

`2↪1-norm and `1-norm are often used for enforcing sparsity when applied to regularize parameter matrix [Nie et al., 2010; Wang et al., 2014a; 2013], and achieving robustness to outliers when applied to loss function [Kong et al., 2011].

Laplacian Noise Interpretation for RFNMF L1: We show the probabilistic motivation of our model from Laplacian noise distribution. Suppose xi is an observed data point contaminated by an additional noise σi:

where ↵i is the unobservable true data, in NMF clustering it is the clustering centroid, i.e. ↵i = FGTi▷ , Gi▷ 2 Ind. σi is the noise. Suppose the noise is drawn from Laplacian distribution with zero mean, then we have:

where b is the scale parameter of Laplacian distribution. Suppose we have an observed data set X = [x1↪ x2↪ ▷▷▷↪ xN], the maximum likelihood estimate (MLE) of ↵i should be:

Therefore, the MLE under Laplacian noise assumption is equivalent to the RFNMF L1 model. In the algorithm section, we will show that the solution of cluster centroids F is exactly finding the sample medians, which coincides with the MLE of the location parameter of Laplacian distribution.

Similar to the Laplacian noise interpretation of RFNMF L1, it is also not difficult to see that: the RFNMTF

model can also be interpreted from a Laplacian distributed noise, except ↵ is replaced by FSGi▷ instead of FGi▷; the RFNMF model can be interpreted from a Gaussian distributed noise. For space reason, we do not show the detail derivation.

The constraints in the objective functions involves combinatorial search over the solution space of F and G, which is very hard to optimize. Previous works always solve the relaxed version to make G have continuous values. In the following section, efficient algorithms are proposed for solving the objective functions with binary indicator constraints.

3 Optimization Algorithms

We first introduce a lemma which will be used in the following optimization algorithms.

Lemma 1. Considering the following objective function:

The optimal solution of z is the median value of ai.

This lemma can be easily obtained by setting the derivative of Eq. 11 to zero:X i sgn(z - ai) = 0 (12)

where sgn(x) = 1 if x > 0, sgn(x) = -1 if x < 0, and sgn(x) = 0 if x = 0. This condition can be satisfied if and only if z takes the median value of ai.

3.1 Efficient Algorithm for Problem (5)

Given an initial guess of F and G, we iteratively update the model parameters. When G is fixed, problem (5) becomes:

Since `1-norm can be decoupled through rows and columns, the above problem can be reduced to:

The above problem can be decoupled as: for 8i↪ k, solving:

According to Lemma 1, the optimal solution of FiK can be efficiently obtained by finding the median values of samples belong to the k-th cluster.

When F is fixed, G can be efficiently optimized by assigning label to the cluster with nearest centroid, i.e.:

3.2 Efficient Algorithm for Problem (6)

When G is fixed, using reweighted method, problem (6) can be reduced to:

where D 2 Rn⇥n is a diagonal matrix whose diagonal elements are:

Setting the derivative w.r.t. F to zero, we get:

When F is fixed, G can be obtained by assigning labels to the cluster with the nearest centroid:

3.3 Efficient Algorithm for Problem (7)

When F and G are fixed, problem Eq. (7) becomes:

This problem can be decoupled as: 8k↪ l, solving:

According to Lemma 1, S can be efficiently optimized by finding the median values.

When S and F are fixed, G can be obtained by:

When S and G are fixed, F can be obtained by:

Therefore, all the three models can be efficiently solved by iteratively update F and G.

Unlike previous works which need to initialize G using the clustering results of K-means, our algorithms works good with random initialization of G. In practice, we can repeat the algorithm many times using different random initializations, and then take the result with the minimum objective value.

Note that our algorithms use binary indicator matrix instead of soft indicator matrix. Therefore, the clustering labels can be obtained directly by assigning labels to the cluster with nearest centroid. Therefore, our algorithms avoid the intensive computation of matrix multiplication. More importantly, previous NMF/NMTF works converges slowly, often needs hundreds or even thousands iterations before convergence. Our algorithms converge very fast, usually in just tens of iterations, and take much less computational time.

3.4 Convergence Analysis

In this section, we prove the convergence of our algorithms. To begin with, following are some simple definitions that will be used.

where xi is the i-th data, f is the cluster centroid of the previous iteration, f 0 is the new cluster centroid, si(f) denotes the clustering assignment of the i-th data using the cluster centroid of previous step. Obviously, when f = f 0 = ft, E(ft) = J(ft↪ ft) is exactly the objective value of RFNMF L1 in Eq. (5) in the t-th iteration.

According to Lemma 1: the optimum solution of f 0 is the median value of samples, and we have J(f↪ f 0 )  J(f↪ f).

In addition, since by definition si(f 0 ) is the best cluster assignment using cluster centroid f 0 , we have:

Therefore, our algorithm for solving problem (5) monotonically decreases the objective value at each iteration until it reaches the optimum solution where f 0⇤ = f⇤. In addition, the KKT condition is satisfied. So the algorithm converges to a local minimum.

The convergence proof of the other two algorithms follows a similar procedure. For space reasons, we omit the detailed proof.

4 Experimental Results

4.1 Experiment Settings

In order to validate the effectiveness of the proposed NMF and NMTF methods, we compare our methods with some related methods as following:

1. Standard NMF (NMF) [Lee and Seung, 2001]: solves the objective function in Eq. (4).
2. Orthogonal NMTF (OrthNMF) [Ding et al., 2006]: factorizes a matrix into three non-negative components, and each column of the soft indicator matrices (F and G) are required to be orthogonal.
3. SemiNMF [Ding et al., 2010]: allows the basis matrix F in standard NMF to be mix-signed
4. Convex NMF (ConvNMF) [Ding et al., 2010]: restricts the basis matrix F into a linear combination of original data points.
5. Robust NMF (RNMF) [Kong et al., 2011]: replaces the loss measurement in standard NMF from Frobenius norm to `2↪1-norm, which makes the model robust to outliers. The difference between our methods and RNMF is that: our methods

use a hard indicator, which is more difficult to solve, but has clearer clustering interpretation since they reduce to directly assign cluster labels to samples at each updates of indicator matrix. This approach is better for clustering tasks. In addition, the algorithm is also much faster as we will show empirically in the experiment section. All the above models are solved using a multiplicative updating rules, which converges slowly and involves intensive matrix computations.

K-means serves as a baseline in the clustering performance comparison. The above comparison methods need to be initialized with the clustering results of K-means, since the objective functions are non-convex, and the final clustering results are sensitive to initializations. A little perturbation is needed for preventing these NMF models from sticking at the K-means solutions. As suggested in previous researches [Kong et al., 2011; Ding et al., 2006], the initialization of indicator matrix is set as G0 = Gk +0▷2, where Gk is the result of the K-means algorithm. The solution of these comparison methods is then get by iteratively update F and G using the multiplicative rule in Table 1 in [Li and Ding, 2006]. The iteration number is set as 500.

As for our methods, the initialization is set as the following: for RFNMF and RFNMF L1, rather than using the result of K-means, we just randomly initialize the cluster indicator matrix G in case of the model stuck at the solution of K-means. We can see in the experiments that our objective converges good on a local minimum even with random initialization. For RFNMTF, the initialization of G and F is using the clustering results of the data dimension and feature dimension, similar to the strategy used in traditional NMF methods.

4.2 Experiments on Synthetic Data

We compare our methods with standard NMF on a synthetic data set with outliers. As shown in Figure 1 (a), the data set contains two normal clusters (blue points and red points) drawn from two gaussian distributions with mean (-6, 0) and (6,0), respectively. Each cluster contains 100 data points. Three outliers (black points) were added far away from these two clusters. Figure 1 (b) shows the clustering results using standard NMF algorithm. Because standard NMF is not robust to outliers, the original blue/red points in one cluster are split into two clusters. Other comparison methods follow the same pattern as standard NMF, i.e. split the original cluster into two clusters. Figure 1 (c) shows the clustering results using the proposed three methods. Our methods are robust to outliers, therefore, the correct clustering structure is recovered.

Table 1 reports the average distance of data points from the corresponding cluster centroids. We can see that the distance of standard NMF algorithm for outliers is a little smaller than our methods, since it pays more attention to outliers. The distances of our methods for normal data and for all data are much more smaller than standard NMF.

4.3 Data Set Descriptions

In this section, we will present empirical results to evaluate the proposed NMF and NMTF approaches. Five real world data sets are used to evaluate the effectiveness of our method.

Digit data set is a public data set hosted in UCI Machine Learning Repository 1 . This data set consists of handwritten digits from 0 to 9, and each digit is a class.

HumanEva data set 2 contains 10000 samples from two subjects with 5000 samples per subject. There are five types of motions: boxing, walking, throw-catch, jogging and gesturing.

YouTube data set 3 contains 11 human activities: soccer juggling, swinging, tennis swinging, to name a few. Figure 3 show some sample images with bounding action labels in YouTube data set.

1 https://archive.ics.uci.edu/ml/datasets/Multiple+Features

2 http://vision.cs.brown.edu/humaneva/index.html

3 http://www.cs.ucf.edu/˜liujg/YouTube Action dataset.html

UCF data set 4 is an extension to the YouTube data sets. It contains 50 actions consisting of realistic videos in YouTube. This data set is very hard to recognize due to large variations in camera position, pose, illumination conditions, viewpoint, and cluttered background.

KTH data set 5 contains six type of human actions: walking, jogging, running, boxing, hand waving and hand clapping. These actions are performed by 25 subjects in four different scenarios: outdoor, outdoor with scale variations, outdoor with different clothes, and indoors. All samples are taken in homogeneous background, so that it is more close to natural environments. This setting add noise in the sample, thus, it is more difficult to recognize the actions.

4 http://crcv.ucf.edu/data/UCF50.php

5 http://www.nada.kth.se/cvap/actions/

4.4 Clustering Performance and Convergence Speed Comparison

We use accuracy, NMI (normalized mutual information), and Purity as measurements of the clustering performance. Since all the methods are sensitive to initializations, we repeat each algorithm 10 times, and the clustering results with the minimum objective value is recorded in Figure 2. We can see that: RFNMF L1 and RFNMF achieve the best performance on most data sets in terms of both accuracy, NMI and purity. The performance of OrthNMTF and RNMF is also pretty good on some data sets.

Figure 2 (d) shows the convergence of the proposed algorithms. For space limitation, only one of the five data sets are shown in the paper. We can see that all the three algorithms converge fast, usually in about 50 iterations.

Table 2 shows the comparison of computational time. The algorithms are run on a Dell desktop with double i7 Cores and 16GB memory. For RFNMF and RFNMF L1, we just use random initialization in the experiments. For all of the other methods, K-means result is used as initialization since it is suggested by previous research. The time consumption of K-means initialization is not considered for all of these methods. We can see that the RFNMF L1 algorithm converges very fast, which is often comparable or even faster than Kmeans. Thus, our algorithm is scalable to large data. The computational time of RFNMF and RFNMTF is also much less than other compared NMF and NMTF methods.

5 Conclusions

We proposed three new NMF and NMTF models which are robust to outliers to improve the human action clustering tasks. Efficient algorithms are derived, which converge as fast as the standard K-means algorithm, and thus are scalable to large-scale data sets. Experimental results on both synthetic and real world data sets show that our methods outperform other existing NMF and NMTF methods in most cases, and in the meanwhile, take much less computational time.