Robust capped norm dual hyper-graph regularized non-negative matrix tri-factorization

1.   Introduction

As the dimension of data in machine learning and data mining is too high to learn, matrix factorization algorithms are adopted to deconstruct the high-dimensional data into several low-dimensional data and explore the hidden structure of low dimensional data. The widely used matrix factorization approaches, include Principal Component Analysis (PCA) ^[1], Singular Value Decomposition (SVD) ^[2], Vector Quantization (VQ) ^[3] and Non-negative matrix factorization (NMF).

Different from PCA, SVD and VQ, the main motivations of NMF, are to decompose a high-dimensional data matrix into two low-rank non-negative matrices, whose product is approximate to the original data matrix. NMF is able to obtain a parts-based representation of data as the non-negative constraints allow only additive, not subtractive, combinations ^[4]. NMF algorithm and its extensions have been applied in several areas, e.g., medical research ^[5], community discovery ^[6], gene expression ^[7,8,9,10], text mining ^[11] and neural network ^{[12,13,14,15]}.

As an extension of NMF, Non-negative matrix tri-factorization (NMTF) aims to decompose a high-dimensional data matrix into three low-rank non-negative matrices ^[16,17]. With an extra decomposition matrix, NMTF can obtain higher degrees of freedom than NMF ^[18]. NMTF is helpful for co-clustering task as it can categorize feature space and sample space simultaneously. Nevertheless, Ding et al. ^[18] point out that unconstrained NMTF is equivalent to NMF while constrained NMTF brings new features to NMF and hereby propose orthogonal non-negative matrix tri-factorization (ONMTF). ONMTF can obtain a rigorous clustering presentation as non-negative and orthogonality constraints lead to a sparse solution. Abundant research show the superiority of spareness research ^{[14,19,20,21,22,23,24,25,26,27]}.

The standard NMF and NMTF algorithms rarely consider the hidden geometrical information in feature space and sample space. However, it is pointed out that the observed data lie on a nonlinear low dimensional manifold embedded in a high dimensional ambient space ^[28,29]. Several manifold learning algorithms have been proposed to exploit intrinsic geometrical information ^[30,31,32], such as ISOMAP ^[33] and Laplacian Eigenmap (LE) ^[34]. Inspired by recent progress in manifold learning, Cai et al. propose graph regularized NMF (GNMF) ^[35]. GNMF firstly constructs a nearest neighbor graph to encode the geometrical information of the data space and incorporates the graph regularization into its objective function. To explore the geometrical information in feature space, which is neglected in GNMF, Shang et al. further propose graph dual regularized NMF (DNMF) ^[17]. DNMF constructs dual graph to discover the manifold embedded in sample space and feature space simultaneously. Unfortunately, the high-order relations among samples are seldom considered in graph-based learning methods as the constructed graph only considers the pairwise relationship between two samples or two features. This problem has been solved by hyper-graph learning ^[36,37]. Contrast to graph, hyper-graph is constructed by edges connected with multiple samples. Therefore, hyper-graph can explore high-order relationship of data and features. Hyper-graph is popular in machine learning fields ^[38,39]. Feng et al. propose Hyper-graph Neural Networks (HNN)^[40]. Jiang et al. propose dynamic hyper-graph neural networks^[41]. HNN utilizes hyper-edge convolution operations to learn the hidden layer representation considering the high-order data structure ^[40,42]. Zeng et al. first combine hyper-graph learning and NMF algorithm and propose hyper-graph regularized NMF (HNMF) ^[43]. HNMF utilizes single hyper-graph regularization to obtain a better geometrical information in sample space.

Although standard NMF and NMTF algorithms utilize Forbenius norm to calculate residual error and perform well on untainted data, the performance can be dramatically decreased by noise and outliers as Forbenius norm calculates the squared residual error. To alleviate the impact of noise and outliers, several robust M-estimator based NMF algorithms are proposed ^[44]. Kong et al. propose a robust NMF using $l_{2, 1}$-norm to calculate the residual error of each sample point without squaring it ^[45]. Gao et al. design a robust capped NMF ^[46]. The main contribution of robust capped NMF is that it caps the residual of extreme outlier to further enhance the robustness. Li et al. propose a robust NMF using $l_{2, p}$-norm to further reduce the impact of noise and outliers ^[47]. Guan et al. develop Truncated Cauchy non-negative matrix factorization which utilizes Truncated Cauchy loss to truncate large errors and handle outliers ^[48]. Guan et al. also propose Manhattan non-negative matrix factorization (MahNMF) which uses Manhattan distance instead of Euclidean distance to model the heavy tailed Laplacian noise ^[49].

Motivated by the good robustness of $l_{2, p}$-norm and capped $l_{2, 1}$-norm and excellent performance of manifold learning based NMF algorithms, a robust capped norm dual hyper-graph regularized NMTF (RCHNMTF) is proposed. Specifically, RCHNMTF utilizes capped $l_{2, p}$-norm to enhance robustness. Second, RCHNMTF constructs dual hyper-graph to encode intrinsic geometrical information in sample manifold and feature manifold. Third, ONMTF framework is incorporated to RCHNMTF to improve clustering performance. The main contribution of the article is summarized as follows:

1) A novel method called RCHNMTF is proposed. RCHNMTF first utilizes capped $l_{2, p}$-norm to improve robustness. Dual hyper-graph regularization and ONMTF framework are also added to RCHNMTF to further improve clustering performance. 2) The optimization problem of RCHNMTF is reformulated and an alternative iteration algorithm is designed thereafter to simplify iteration steps. The computational complexity of RCHNMTF and its comparison methods are calculated thoroughly with three arithmetic operations and big $O$ notation. 3) Experiments on seven real-world datasets and four noised datasets verify the superior clustering performance and robustness of RCHNMTF, compared with eight state-of-the-art algorithms.

The rest of the paper is arranged as follows: In Section 2, NMF algorithm, $l_{q, p}$-norm, capped $l_{2, 1}$-norm NMF and hyper-graph regularization are introduced. In Section 3, the formulation of RCHNMTF is first described. The optimization problem of RCHNMTF is reformulated thereafter to simplify iteration steps. The computational complexity of RCHNMTF and its comparison algorithms are thoroughly analyzed. Section 4 demonstrates the clustering performance and robustness of RCHNMTF on seven real-world datasets and four contaminated datasets, compared with eight state-of-the-art algorithms. The paper is summarized in Section 5.

2.   Related works

2.1.   Non-negative matrix factorization

Given a data matrix $\mathit{\boldsymbol{X}} = [\mathit{\boldsymbol{x}}_{1}, \mathit{\boldsymbol{x}}_{2}, ..., \mathit{\boldsymbol{x}}_{n}]\in R^{m\times n}$, each column of $\mathit{\boldsymbol{X}}$ denotes a sample vector $\mathit{\boldsymbol{x}}_{n}$. NMF aims to decompose the data matrix $\mathit{\boldsymbol{X}}$ into two low-dimensional non-negative matrices $\mathit{\boldsymbol{U}} = [\mathit{\boldsymbol{u}}_{1}, \mathit{\boldsymbol{u}}_{2}, ..., \mathit{\boldsymbol{u}}_{k}]\in R^{m\times k}$ and $\mathit{\boldsymbol{V^T}} = [\mathit{\boldsymbol{v}}_{1}, \mathit{\boldsymbol{v}}_{2}, ..., \mathit{\boldsymbol{v}}_{k}]\in R^{k\times n}$, whose product $\mathit{\boldsymbol{UV}}^T$ is approximate to the original data matrix $\mathit{\boldsymbol{X}}$. The residual error between $\mathit{\boldsymbol{X}}$ and $\mathit{\boldsymbol{UV}}^T$ is calculated by Frobenius norm. The optimization problem of NMF is defined as ^[4]:

where $\left\|\cdot\right\|_F$ represents the Frobenius norm of the matrix. Optimization problem (2.1) can be solved by the following multiplicative update rules ^[4]:

2.2.   $L_{q, p}$-Norm

The $l_{q, p}$-norm of $\mathit{\boldsymbol{X}}$ is defined as follows ^[47]:

where $\left\Vert\cdot\right\Vert_{q, p}$ represents $l_{q, p}$-norm. Let $q = 2$, the $l_{2, p}$-norm of $\mathit{\boldsymbol{X}}$ is defined as follows:

where $\left\Vert\cdot\right\Vert_{2, p}$ represents $l_{2, p}$-norm. It should be noticed that $l_{2, p}$-norm $(0 < p < 1)$ is not a valid matrix norm as it does not admit the triangular inequality. However, for simplicity, we term it a matrix norm. Moreover, the $l_{2, p}$ matrix pseudo norm is not convex or Lipschitz continuous as the $l_p$-norm $(0 < p < 1)$ is neither convex nor Lipschitz continuous.

2.3.   Capped $L_{2, 1}$-norm NMF

To decrease the influence of extreme outliers, Gao et al. propose capped $l_{2, 1}$-norm based NMF, whose optimization problem is defined as follows ^[46]:

where $\theta > 0$ is a thresholding parameter to choose the extreme data outliers. In capped $l_{2, 1}$-norm based NMF, if the residual error of a data point $\left\Vert \mathit{\boldsymbol{x}}_i-\mathit{\boldsymbol{Uv}}_i \right\Vert > \theta$, then data point $x_i$ is determined as an extreme outlier and its residual is capped as $\theta$ to fix its effect on the whole model. For other data points $\left\Vert \mathit{\boldsymbol{x}}_i-\mathit{\boldsymbol{Uv}}_i \right\Vert < \theta$, the algorithm calculates the residual error using $l_{1}$-norm, which is also robust to regular data outliers. Moreover, $\theta$ is set according to the ratio of outliers. With an extra thresholding parameter $\theta$ to select extreme data outliers and cap their influence, capped $l_{2, 1}$-norm based NMF is more robust than $l_{2, 1}$-norm based NMF.

2.4.   Hyper-graph regularization

With the development of graph theory, hyper-graph regularization has been widely used. Unlike graph regularization only considers the pairwise relationships between two samples or two features, hyper graph regularization considers the relationships between multiple samples or multiple features. Specifically, an edge of graph connects two nodes while an edge of hyper graph connects multiple nodes. Therefore, using hyper-graph prevents the forced conversion of multivariate relationships into binary relationships and explores the high-order information in sample space and feature space ^[43].

Hyper-graph $G = (V, E, \mathit{\boldsymbol{W}})$ consists of vertex set $V$, hyper-edge set $E$ and diagonal hyper-edge weight matrix $\mathit{\boldsymbol{W}}$. The incidence matrix $\mathit{\boldsymbol{H}} \in R^{|V|\times|E|}$ is defined as follows:

$\mathit{\boldsymbol{W}}_i$ represents the weight of hyper-edge $e_{i}$. The calculation method of $\mathit{\boldsymbol{W}}_i$ depends on the specific situation. Denote $V_x$ and $V_y$ represent the sample points $\mathit{\boldsymbol{X}}_x$ and $\mathit{\boldsymbol{X}}_y$, respectively. In this paper, $\mathit{\boldsymbol{W}}_i$ is defined as:

where $\sigma^2$ is defined as:

where parameter $k$ represents the value of $k$-nearest neighbors for each vertex.

The degree of vertex $v$ is expressed as:

The degree of edge $e$ is defined as:

Given diagonal matrix $\mathit{\boldsymbol{D}}_v$ composed of $d(v)$ and diagonal matrix $\mathit{\boldsymbol{D}}_e$ composed of $f(e)$, the unnormalized hyper-graph Laplacian matrix $\mathit{\boldsymbol{L}}_{hyper}$ is defined as:

3.   The proposed model

In this section, a novel algorithm called RCHNMTF is proposed. After that, an efficient optimization algorithm is designed. The computational complexity analysis of RCHNMTF and comparison algorithms are discussed subsequently. Figure 1 shows the framework of RCHNMTF.

3.1.   Problem formulation

The optimization problem of NMTF with capped $l_{2, p}$-norm is formulated as follows:

where $\theta$ denotes a thresholding parameter.

In optimization problem (3.1), $\sum_{i = 1}^{n}\mathop{\min} \{ \left\Vert (\mathit{\boldsymbol{X-UBV^T}})_i \right\Vert_2^p, \theta \}$ indicates using capped $l_{2, p}$-norm to measure the residual error of each point. If the residual error $\left\Vert (\mathit{\boldsymbol{X-UBV^T}})_i \right\Vert_2^p$ of data point $\mathit{\boldsymbol{x}}_i$ is bigger than $\theta$, data point $\mathit{\boldsymbol{x}}_i$ is determined as extreme outliers and its residual error is capped. The influence of outlier sample point $\mathit{\boldsymbol{x}}_i$ to the whole model is decreased by capping its residual error. For other data points whose residual error $\left\Vert (\mathit{\boldsymbol{X-UBV^T}})_i \right\Vert_2^p < \theta$, the optimization problem will minimize $\sum_{i = 1}^{n} \left\Vert (\mathit{\boldsymbol{X-UBV^T}})_i \right\Vert_2^p$, which is also robust as it calculates the residual error of each sample point to the $p$-th power, compared with Forbenius norm in original NMF measures the residual error to the power of 2. Therefore, utilizing capped $l_{2, p}$ -norm, the proposed algorithm can decrease the influence of extreme outliers and have good robustness.

To adopt geometric information of data space and sample space, dual hyper-graph regularization is incorporated to optimization problem (3.1). Let $\mathit{\boldsymbol{L}}_{hyper}^{\mathit{\boldsymbol{U}}}$ and $\mathit{\boldsymbol{L}}_{hyper}^{\mathit{\boldsymbol{V}}}$ represent the unnormalized hyper-graph Laplacian matrix of matrix $\mathit{\boldsymbol{U}}$ and $\mathit{\boldsymbol{V}}$, respectively. With hyper-graph Laplacian matrix $\mathit{\boldsymbol{L}}_{hyper}^{\mathit{\boldsymbol{U}}}$ and $\mathit{\boldsymbol{L}}_{hyper}^{\mathit{\boldsymbol{V}}}$, we extend the optimization problem as:

where $Tr(\cdot)$ denotes the trace of a matrix and $\alpha$ denotes dual hyper-graph regularization parameter. The dual hyper-graph regularization is formulated as $\alpha Tr (\mathit{\boldsymbol{V}}^T\mathit{\boldsymbol{L}}^{\mathit{\boldsymbol{V}}}_{hyper} \mathit{\boldsymbol{V}}) + \alpha Tr(\mathit{\boldsymbol{U}}^T\mathit{\boldsymbol{L}}^{\mathit{\boldsymbol{U}}}_{hyper}\mathit{\boldsymbol{U}})$. Dual hyper-graph regularization utilizes two nearest neighbor hyper-graphs to exploit the geometric structure of the sample manifold and feature manifold.

Orthogonality constraints in NMTF is important as orthogonality constraints lead to a sparse and unique solution. To guarantee orthogonality of matrix $\mathit{\boldsymbol{U}}$ and $\mathit{\boldsymbol{V}}$, orthogonality penalty terms $\beta{\left \Vert\mathit{\boldsymbol{U}}^T\mathit{\boldsymbol{U}}-\mathit{\boldsymbol{I}}_K\right \Vert_F^2}$ and $\beta{\left \Vert\mathit{\boldsymbol{V}}^T\mathit{\boldsymbol{V}}-\mathit{\boldsymbol{I}}_K\right \Vert_F^2}$ are added to the optimization problem:

where $\beta \ge0$ denotes orthogonality parameter.

3.2.   Optimization of RCHNMTF

First, the following equation can be easily proved:

where $\mathit{\boldsymbol{H}}$ is the diagonal matrix whose $i$ -th diagonal element is calculated as:

It is apparent that optimization problem (3.3) is a non-convex optimization problem, so it is not easy to solve the optimization problem (3.3) directly. The optimization problem (3.3) is reformulated as follows:

where $\mathit{\boldsymbol{I}}_{k}$ is the $a \times a$ identity matrix and $\mathit{\boldsymbol{D}}$ is the diagonal matrix whose $i$-th diagonal element is calculated as:

3.3.   Update rules of RCHNMF

Considering $||\mathit{\boldsymbol{X}}||_F^2 = Tr(\mathit{\boldsymbol{XX}}^T)$, the optimization problem (3.6) is rewritten as follows:

Optimization problem (3.8) can be solved by multiplicative iteration method. Let $\mathit{\boldsymbol{\phi}} = [\phi_{jk}]\in R_{\ge0}^{m\times k}$, $\mathit{\boldsymbol{\omega}} = [\omega_{kk'}]\in R_{\ge 0}^{k \times k}$, $\mathit{\boldsymbol{\psi}} = [\psi_{ik}]\in R_{\ge 0}^{n \times k}$ be the Lagrange multipliers for $\mathit{\boldsymbol{U}}$, $\mathit{\boldsymbol{B}}$, $\mathit{\boldsymbol{V}}$ respectively, Lagrange function $\mathcal{L}$ is obtained as follows:

The partial derivatives of $\mathcal{L}$ with respect to $\mathit{\boldsymbol{U}}$, $\mathit{\boldsymbol{B}}$ and $\mathit{\boldsymbol{V}}$ are as follows:

Considering that $\mathit{\boldsymbol{L}}_{hyper}^{U}$ and $\mathit{\boldsymbol{L}}_{hyper}^{V}$ are not non-negative matrices, we refer to (2.12) and define non-negative matrices $\mathit{\boldsymbol{D}}_{hyper}^{\mathit{\boldsymbol{U}}}$, $\mathit{\boldsymbol{S}}_{hyper}^{\mathit{\boldsymbol{U}}}$, $\mathit{\boldsymbol{D}}_{hyper}^{\mathit{\boldsymbol{V}}}$, $\mathit{\boldsymbol{S}}_{hyper}^{\mathit{\boldsymbol{V}}}$ as follows:

Using the KKT condition $\mathit{\boldsymbol{\phi U}} = 0$, $\mathit{\boldsymbol{\omega B}} = 0$, and $\mathit{\boldsymbol{\beta V}} = 0$, we have:

According to the above equations, the multiplicative update rules of RCHNMTF are as follows:

3.4.   Computational complexity analysis

In this part, the computational complexity of the proposed RCHNMTF algorithm and comparison algorithms are calculated and presented. The computational complexity of NMF is also added for reference. To accurately present the computational complexity of RCHNMTF and comparison algorithms, big $O$ notation and three arithmetic operations, namely addition, multiplication and division, are adopted. Table 1 shows the detailed computational complexity information of each algorithm in each iteration. It can be seen that the extra factorization matrix, graph regularization, hyper-graph regularization and orthogonality constraints will all increase the computational complexity. However, these extra term will not dramatically affect the runtime of algorithms. It can be explained by two reasons. First, if measured by big $O$ notation, the computational complexity of all algorithms are $O(mnk)$. Second, considering $k < < \min{(m, n)}$, $mnk$ term counts much in computational complexity analysis and the coefficient of $mnk$ term in RCHNMTF is not high, which indicates the computational complexity of RCHNMTF is not high. Moreover, compared with other M-estimator based NMF algorithms, the computational complexity of capped $l_{q, p}$-norm are small (e.g., correntropy based NMF algorithms require exponential operation). If calculate the computational complexity of RCHNMTF algorithm from the beggining to the $n$-th iterations, then the computational complexity of RCHNMTF is $O(tmnk+mn^2+nm^2)$, due to the extra $O(mn^2+nm^2)$ from constructing dual hyper-graph in feature space and sample space.

4.   Experiments

In this section, RCHNMTF algorithm is compared with eight state-of-the-art algorithms on seven datasets (i.e., AR100^*, ORL^†, YALE^‡, PIE^§, MSRA25^¶, PENDIGITS^|| and COIL100^**) to verify the effectiveness and robustness of the proposed algorithm.

^*http://www2.ece.ohio-state.edu/aleix/ARdatabase.html

^†http://www.cl.cam.ac.uk/Research/DTG/attarchive:pub/data/att_faces.tar.Z

^‡http://cvc.cs.yale.edu/cvc/projects/yalefaces/yalefaces.html

^§https://www.ri.cmu.edu/publications/the-cmu-pose-illumination-and-expression-pie-database-of-human-faces

^¶http://www.escience.cn/people/fpnie/index.html

^||http://archive.ics.uci.edu/ml/datasets/pen-based+recognition+of+handwritten+digits

^**https://www.cs.columbia.edu/CAVE/software/softlib/coil-100.php

4.1.   Experiments setting

4.1.1.   Datasets

Seven real-world datasets are used in the experiment. The description of these datasets can be found in Table 2. Besides, to simulate the situation in reality where parts of sample points are affected by noise and outliers, four contaminated datasets are produced by adding noise to parts of the sample points of the original dataset while leaving the other data points unchanged. Specifically, the formulations are: 1) The last 5 images of each class in PIE dataset are noised by Gaussian noise with mean 0 and variance $V$ = 0.1, 0.2, 0.3, 0.4, 0.5; 2) The last 4 images of each class in YALE dataset are contaminated with Speckle noise with mean 0 and variance $V$ = 0.08, 0.16, 0.24, 0.32, 0.4; 3) The last 2 images of each class in ORL dataset are polluted by $a \times a$-blocks noise with $a = 6, 7, 8, 9, 10$; 4) The last 2 images of each class in ORL dataset are contaminated by Salt & Pepper noise with noise density $D$ = 10, 20, 30, 40, 50%. Figure 2 shows the example class of each polluted datasets.

4.1.2.   Comparison algorithms

The proposed RCHNMTF algorithm are compared with eight state-of-the-art algorithms to verify its clustering performance and robustness, which are listed as follows:

1). CNMTF ^[50]. A correntropy based NMTF combines dual graph regularization and orthogonal constraints.

2). CHNMF ^[7]. It incorporates correntropy and hyper-graph regularization into NMF.

3). DNMF ^[17]. It utilizes dual graph regularization to learn the geometrical information of the sample manifold and the feature manifold.

4). GNMF ^[35]. It constructs a single graph to consider the geometrical information of the sample manifold.

5). HNMF ^[43]. A hyper-graph regularized NMF constructs a hyper-graph to explore the geometrical information of the sample manifold.

6). RHNMF ^[8]. A robust NMF utilizes $l_{2, 1}$-norm and hyper-graph regularization.

7). CaNMF ^[46]. A robust NMF adopts capped norm to cap the residual error of extreme outliers.

8). DHSNMF ^[51]. A robust dual hyper-graph regularized supervised NMF. To compare DHSNMF with other unsupervised algorithms in a fair way, the label information parameter of DHSNMF is set to 0 specifically.

4.1.3.   Evaluation metrics

To evaluate the performance and robustness of RCHNMTF and comparison algorithms in a sound manner, three evaluation metrics, namely purity (PUR), normalized mutual information (NMI) and accuracy (ACC) are introduced.

Purity demonstrates how well each cluster contains sample from primarily one, which is defined as follows:

where $n_i^j$ denotes the sample in cluster $i$ that also belongs to original class $j$.

NMI calculates the shared information of two clusters and it expresses the degree of agreement between the two clusters. Given the ground truth cluster $C$ and the cluster $\overline{C}$ from clustering algorithm result, NMI of $C$ and $\overline{C}$ is calculated as follows:

where $MI(C, \overline{C})$ denotes the mutual information of the cluster $C$ and $\overline{C}$, $H(C)$ and $H(\overline{C})$ are the entropies of $C$ and $\overline{C}$, respectively.

Given ground truth label $l_i$ and the learned cluster label $r_i$, accuracy is defined as follows:

where $\delta(x, y) = 1$ if $x = y$ and $\delta(x, y) = 0$ otherwise. Mapping function $Map(\cdot)$ is solved by Hungarian algorithm ^[52]. For the mentioned evaluation metrics PUR, NMI and ACC, the higher they are, the better clustering performance the algorithm is.

4.1.4.   Experimental setup

In this part, experiments setup are reported in detail. The dimension $k$ of the $\mathit{\boldsymbol{B}}\in R^{k\times k}$ is adjusted to be the same as the number of real classes for all datasets. $K$-nearest neighbor method is applied to construct graph and hyper-graph in graph regularized and hyper-graph regularized algorithms. The nearest neighbor parameter $p$ in $k$-nearest neighbor method is set to $5$ empirically. HeatKernel method is adopted to assign weights for each edge of a graph. For hyper-graph, the weight of a hyper-edge is calculated by (2.8). Parameter $\theta$ is not fixed but set according to the outliers radio $s$. Outliers ratio $s$ denotes the ratio of outlier samples to the whole sample. Specifically, in the first five iterations, the outlier data with the largest $l_{2, p}$ loss at a ratio of $s$ are selected to determine $\theta$. To better reduce the influence of extreme sample points, $s$ is set to 0.05 and 0.1 for unpolluted real-world datasets and polluted real-world datasets, respectively. Additionally, dual hyper-graph regularization parameter $\alpha$ in RCHNMTF is tuned as 100 and orthogonality parameter $\beta$ is set to 0.01. Moreover, the parameter $p$ in the capped $l_{2, p}$-norm is set to $0.5$ to achieve good clustering performance and robustness. The parameters of the comparison algorithms are set according to the default given values. Matrices $\mathit{\boldsymbol{U}}, \mathit{\boldsymbol{B}}, \mathit{\boldsymbol{V}}$ are initialized randomly and we run each method on different datasets 20 times. After decomposition to obtain low-dimensional representation matrix $\mathit{\boldsymbol{V}}$, we apply $k$-means method to $\mathit{\boldsymbol{V}}$ to get clustering performance measured by PUR, NMI and ACC.

4.2.   Experiment results

To testify the clustering performance of RCHNMTF, RCHNMTF and eight comparison algorithms are first experimented on seven real-world datasets. Tables 3–5 demonstrate the clustering performance on seven real-world datasets measured by PUR, NMI and ACC. Figures 3–6 present the clustering performance on polluted datasets. Figure 7 shows the convergent results on seven datasets. To validate the robustness of RCHNMTF, RCHNMTF and the comparison algorithms are further experimented on four contaminated datasets. From the experiment results on seven real-world datasets and four polluted datasets, the following conclusions are obtained:

1) RCHNMTF outperforms other algorithms on most original datasets (e.g., AR100, PIE, ORL, MSRA25, PENDIGITS, COIL100). The reasons are as follows: ⅰ.) Capped $l_{2, p}$-norm can alleviate the impact caused by the noise and outliers inherent in the original datasets; ⅱ.) Dual hyper-graph regularization helps RCHNMTF to obtain intrinsic geometrical information of feature manifold and data manifold; ⅲ.) Orthogonal NMTF framework provides a decomposed results with more degree of freedom and enables RCHNMTF to learn a unique decomposition result.

2) The algorithms which utilize $l_{q, p}$-norm or capped $l_{q, p}$-norm (e.g., RHNMF, CaNMF, RCHNMTF) are more robust than other algorithms as the former calculates the residual error of each sample point. When parts of sample points are contaminated, $l_{q, p}$-norm and capped $l_{q, p}$-norm are able to distinguish the polluted sample points and reduces the influence of outlier sample points. Moreover, RCHNMTF is more robust to CaNMF and RHNMF because capped $l_{2, p}$-norm caps the residual error of extreme outlier points and uses $l_{2, 0.5}$-norm to calculate the residual error of other data, which can alleviate the impact of outlier points as much as possible. Therefore, RCHNMTF outperforms other algorithms when the dataset has extreme outliers.

3) The convergence curve in Figure 7 shows the convergence results of RCHNMTF.

4.3.   Parameter selection

Parameter selection are crucial to RCHNMTF algorithm. The main parameters in RCHNMTF are $p$ in capped $l_{2, p}$-norm, outlier ratio $s$, thresholding parameter $\theta$, hyper-graph graph regularization parameter $\alpha$ and orthogonality constrains parameter $\beta$. During the experiments, $\alpha$ and $\beta$ are fixed as 100 and 0.01 ^[8,50]. The value of $\theta$ is set according to the ratio of the outliers $s$. Specifically, in the first five iterations, we select outlier data with the largest $l_{2, p}$ loss at a ratio of $s$ and the value of $l_{2, p}$ loss is assigned to $\theta$. By this means, outlier data with the largest $l_{2, p}$ loss is capped and its impact to the whole model is reduced. In parameter selection, $s$ and $p$ are adjusted to find their optimal values. Figure 8 shows the clustering accuracy on different datasets with $s$ ranging in $\{0, 0.05, 0.1, 0.15, 0.2\}$. Table 6 demonstrates the clustering performance with $p$ ranging in $\{0.25, 0.5, 0.75\}$. The conclusions are as follows:

1) Compared with uncapped $l_{2, p}$-norm, a proper value of $s$ in capped $l_{2, p}$-norm can improve clustering performance on both original and noised datasets (e.g., $s = 0.05$ for original datasets and $s = 0.1$ for noised datasets), because the residual error of intrinsic noised points in original real-world datasets and the formulated outlier sample points in noised datasets are capped and thus the influence of noise and outliers are decreased. However, relatively large $s$ will reduce the clustering performance, as the unpolluted sample points are misidentified as outlier sample points.

2) RCHNMTF with $p = 0.5$ is better than the ones with $p = 0.75$ and $p = 0.25$. Given that $l_{2, p}$-norm calculates the residual error of each sample points to the $p$-th power, a relatively large $p$ will decrease the robustness of capped $l_{2, p}$-norm while a relatively small $p$ will blur the difference between normal sample points and outlier sample points.

4.4.   Ablation study

In this subsection, ablation study is made to demonstrate the superiority of dual hyper-graph regularization and orthogonality constraints. Table 7 records the ablation study of RCHNMTF for three cases: 1) without dual hyper-graph regularization; 2)without orthogonality constraints; 3) with dual hyper-graph regularization and orthogonality constraints. $\alpha$ and $\beta$ are accordingly set to: 1) 0 and 0.01; 2) 100 and 0; 3) 100 and 0.01. From Table 7, we can learn that both hyper-graph regularization and orthogonality constraints will improve the clustering performance of RCHNMTF.

5.   Conclusions and feature work

In this paper, the robustness of NMTF is improved by introducing capped $l_{2, p}$-norm to cap the extreme outlier points. Dual hyper-graph is constructed to encode the high-dimensional geometrical information of the sample space and feature space. ONMTF framework is incorporated to RCHNMTF to get unique clustering solution and improve clustering performance. To solve the formulated problem, the optimization problem is rewritten and an alternative algorithm is designed. The computational complexity of RCHNMTF and comparison algorithms are thoroughly analyzed. Abundant experiments verify that RCHNMTF performs well on real-world datasets and performs better on datasets with extreme outliers.

Although RCHNMTF is robust and has good clustering performance, it still has some limitations. Firstly, RCHNMTF has many parameters, which makes adjusting parameters troublesome. Secondly, though the first term in (3.3) can distinguish and cap outlier sample points, the orthogonal penalty term and hyper-graph regularization term regard outlier sample points as normal sample points and can not cap the influence of outliers. In the future, several investigations will be conducted to improve RCHNMTF:

1) Systematic mechanisms for simplifying parameter selections are needed.

2) The orthogonality penalty term and hyper-graph regularization term also need to be optimized for finding and capping outlier sample points.

3) Multi-view clustering is popular in machine learning field as multi-view clustering can analyze multi-view data ^{[53,54,55,56,57,58,59,60,61,62]}. It is worth the time to utilize RCHNMTF in multi-view clustering field.

Acknowledgements

The authors are grateful for the reviewers and editor for their beneficial suggestions.

conflict of interest

The authors declare that there is no conflict of interest.