# Multiview Clustering via Robust Neighboring Constraint Nonnegative Matrix Factorization

Authors: Feiqiong Chen; Guopeng Li; Shuaihui Wang; Zhisong Pan
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

Many real-world datasets are described by multiple views, which can provide complementary information to each other. Synthesizing multiview features for data representation can lead to more comprehensive data description for clustering task. However, it is often difficult to preserve the locally real structure in each view and reconcile the noises and outliers among views. In this paper, instead of seeking for the common representation among views, a novel robust neighboring constraint nonnegative matrix factorization (rNNMF) is proposed to learn the neighbor structure representation in each view, andL2,1-norm-based loss function is designed to improve its robustness against noises and outliers. Then, a final comprehensive representation of data was integrated with those representations of multiviews. Finally, a neighboring similarity graph was learned and the graph cut method was used to partition data into its underlying clusters. Experimental results on several real-world datasets have shown that our model achieves more accurate performance in multiview clustering compared to existing state-of-the-art methods.


---

## Body

## 1. Introduction

Clustering is a fundamental topic in machine learning and data mining tasks. Datasets often are comprised of different views, and the views often provide compatible and complementary information in real world. Thus, multiview clustering (MVC) aims to integrate those different views and uncover the consistent latent information to achieve perfect clustering performance [1]. Over the past decades, it has attracted great attention [2, 3] and has been widely used in various real applications [4].Essentially, given the multiview inputs, the critical work in MVC is to fuse information of different views and learn the common agreement for clustering. For efficiently integrating views, many subspace clustering-based methods [5, 6] and nonnegative matrix factorization- (NMF-) [7, 8] based methods have been developed. In particular, NMF is shown to be equivalent to relaxed k-means and symmetric NMF is closely related to spectral clustering [9]. However, NMF cannot preserve the geometrical structure of the data space, which is essential for the algorithms to find the true cluster structures. Many manifold learning methods, which are motivated by the so-called locally invariant idea that the nearby points are likely to have similar embedding, have been proposed, such as locally linear embedding (LLE) [10] and locality preserving projection (LPP) [11]. In particular, Cai et al. [12] proposed graph-regularized nonnegative matrix factorization (GNMF) to find a compact representation which can uncover the hidden semantics and simultaneously respect the intrinsic geometric structure. It is well accepted that the clustering performance can be significantly enhanced when the local invariance is considered. These are single-view clustering methods.On the other hand, many NMF-based MVC methods [13] have attracted attention, in which various constraints have been applied to the coefficient matrix to cluster the data points. Multi-NMF [14] formulated a joint multiview NMF learning process with the constraint that encourages representation of each view toward a common consensus. Many extensions of multi-NMF methods were proposed for image clustering and other tasks [15]. In [16], two weight matrices are introduced to alleviate the issue of dataset imbalance in real applications. Ou et al. [17] explored the local geometric structure for each view under the patch alignment framework and adopted correntropy-induced metric to measure the reconstruction error of each view to improve the robustness. A deep matrix factorization model [18] aimed to seek a common representation by introducing graph regularization to guide shared representation learning in the final layer of each view. However, existing approaches are all used to exploit common information shared by multiple views but neglect the diversity among views. The diversity means that each view of the data contains some distinct information that other views do not have.In this paper, we propose a novel MVC method, with a novel algorithm, called robust neighboring constraint NMF (rNNMF), which uses the locally neighboring structure of each view to capture the diversity features. In rNNMF, a neighboring graph is constructed and updated for each view in factorization process to obtain the underlying diversity features. Finally, these diversity features will be combined to create an integrated feature for datasets, and then, a global graph is further generated from this integrated feature and Ncut is used to partition data into its underlying groups.In summary, the novelty and contribution of our research are as follows:(1)
A neighboring constraint NMF method is proposed to learn the diversity representation of data in each view. The proposed model only keeps the nearest relationship between a point and its nearest neighbor to maintain geometrical structure in feature learning in each view.(2)
L2,1-norm loss function is used in rNNMF to improve the robustness of feature in each view and reduce the effect of noisy features.The rest of this paper will be organized as follows. Section2 will introduce some related work about NMF-based MVC algorithms. Our proposed robust NMF-based MVC model will be introduced in Sections 3, the experimental results will be introduced in Section 4, and conclusions and discussions will be introduced in Section 5.


## 2. Related Work

Both subspace clustering and NMF-based methods are important in MVC. For example, a robust graph can be learned with correlation consensus agreement in [5] to improve the clustering performance. A multigraph regularized low-rank representation- (LRR-) based method is proposed to achieve the data correlation consensus among all views [6]. A structured LRR was proposed by factorizing into the latent low-dimensional data-cluster representations, which characterize the data clustering structure for each view [1]. Meanwhile, NMF-based methods [19] were also proved to be useful, which enforce the constraint that the elements of the factor matrices must be nonnegative. It shows that when the Frobenius norm is used as a divergence, NMF is equivalent to a relaxed form of K-means clustering method. However, NMF fails to discover the intrinsic geometry of the data, which is essential to the real applications. To preserve the locally geometrical structure of the data space, Cai et al. imposed graph regularization on NMF (GNMF). In [20], Shang et al. proposed graph dual regularization NMF (DNMF) which simultaneously considered the geometric structures of data manifold and feature manifold. Two subspace clustering algorithms were proposed in [21]. It established connection with spectral normalized cut [22] and ratio cut clustering. It also extended the nonlinear orthogonal NMF and introduced a graph regularization to obtain a factorization that respects a local geometric structure after the nonlinear mapping.In MVC, NMF-based methods also have received increasing attention. Let inputX=X1,…,Xv,…,XV and Xv be the v-th view, then it is a dv×n matrix, where dv denotes the feature dimensionality in row and n is the number of data in column. Hv is the representation of the v-th view, it is a p×n matrix, where v denotes the feature dimensionality and Zv is the corresponding basis matrix. For NMF-based methods, the overall framework is as follows:(1)minZH=Xv−ZvHvF2+fHv,Hs,s.t.Zv≥0,Hv≥0,where ⋅F2 is the Frobenius norm, and both Zv and Hv should be nonnegative. By default, the input data for each view should also be nonnegative for the NMF-based methods, i.e., Xv≥0. fHv,Hs is the regularization term to learn the agreement among different views. For example, MulNMF designed a constraint that encourages representation of each view toward a common consensus H∗. DiNMF [23] introduced a constraint term trHvHsT to guarantee the diversity among points in different views. In order to deal with mixed-sign data, based on the semi-NMF model, a deep semi-NMF method couples the output representation in the final layer of factorization and enforces views that share the same representation after layer by layer factorization.Although good performance can be achieved in those methods by finding a common agreement among views, the consensus information cannot be explored effectively and do not make full use of information of multiple views [18]. For full use of diversity information of views, combination of views’ representations is a natural method. Our work focuses on this kind of combination styles. However, original information contained among views can usually lead to poor performance in clustering. Therefore, it is necessary to design a new method which can not only get maximum preservation diversity feature of each view but also obtain the aggregated representation with good clustering performance.


## 3. Structural Constraint Semi-NMF

### 3.1. Robust Neighboring Constraint Regularization

GivenHv is the low-dimensional representation of Xv, we introduce a special matrix Rv to indicate the constraint of the v-th view; it is defined as(2)Rvi,j=−1,i=j,1,i∈Nvj,0,otherwise,where Nvj is the set of the nearest neighbors of point j in the v-th view. If point i is one of the nearest neighbors of j,Rvi,j will be set as 1. We hope the difference between the points j and i is as small as possible, which can be represented by Hv:,j−Hv:,i, where Hv:,j indicates the j-th column of Hv. So, we introduce constraint HvRv to describe this diversity of the point with its neighbors. The smaller the value of HvRv, the more similar they are. We introduce the L2,1 norm to penalize HvRv for seeking a representation in each view:(3)HvRv2,1.


### 3.2. Objective Function and Optimization Algorithm

In MVC, to learn the neighbor information in each view, based on ORNMF [19] which is a robust representation approach, the proposed rNNMF can be expressed as(4)minWvHv=∑v=1VXv−WvHv2,1+αHvRv2,1,s.t.Hv≥0,Wv≥0,where the L2,1-norm is applied to the loss function and defined as X−WH2,1=∑i=1nXi−WHi. With the error for each point not being squared, the impact of large errors is reduced significantly. The first term in equation (4) indicates the v-th data fidelity term, and the second term is the nearest neighboring constraint term. Hv is the v-th representation from the v-th view. α is the positive parameter to specify the relative importance of the factorization term and regularization term in the model.Like the most NMF-based methods, the objective function in (4) is not convex, so we present an iterative algorithm to achieve the local minima of (4).ComputingHv, to update Hv with Wv fixed, we need to solve the object function as follows:(5)minHv≥0JHv=∑v=1VXv−WvHv2,1+αHvR2,1,as Hv≥0 and JHv being NP-hard, a Lagrange multiplier matrix Θ=Θij is introduced. Then, the Lagrangian function LHv is(6)LHv=∑v=1VtrXvD1vXvT−2trD1vXvTWvHv+trD1vHvTWvTWvHv+αtrHvRvD2vRvTHvT+trΘHvT,where D1v and D2v are diagonal matrices, which are n×n matrices, and the elements defined as(7)D1vii=1Xiv−WvHiv,D2vii=1HvRvi.The partial derivative of Lagrangian functionLHv with respect to Hv is computed as follows:(8)∂LHv∂Hv=−2WvTXvD1vT+2WvTWvHvD1vT+2αHvRvD2vRvT+Θ.BecauseRv is mixed-sign data, we should decompose it into two nonnegative parts M+ and M−, representing the positive part and the negative part, respectively,(9)M+=M+M2,M−=M−M2.LetRav=Rv+DvRv−T, Rbv=Rv−DvRv+T, Rcv=Rv+DvRv+T, and Rdv=Rv−DvRv−T. The updating rule of Hv is formulated as follows:(10)Hv⟵Hv⋅WvTXvD1vT+αHvRav+RbvWvTWvHvD1vT+αHvRcv+Rdv.ComputingWv, to update Wv with Hv fixed, the following object function should be solved:(11)minWv≥0JWv=Xv−WvHv2,1.This is similar as that in [19, 24]. So we have the updating rule as(12)Wv⟵Wv⋅XvD1vHvTWvHvD1vHvT,where ⋅ indicates the Hadamard product. For each view, the updating rule of Hv and Wv satisfies the theorem in [24], which guarantees the correctness of the rule. The correctness analysis and convergence proof of (10) and (12) are shown based on the method [19] in the following section.


### 3.3. Correctness and Convergence

Theorem 1.
If the updating rule ofHv converges, then the final solution satisfies the KKT optimality condition.Proof.
At convergence,Hv∞=Hvt+1=Hvt=Hv, where t denotes the t-th iteration, and the following formula holds:(13)WvTXvD1vT−WvTWvHvD1vT+αHvRvD2vRvT−+αHvRvD2vT+ijHijv2=0.We now prove the convergence of the updating rule (10) using the auxiliary function approach in [19]. The definition of the auxiliary function is as follows.Definition 1.
G
H
,
H
′ is an auxiliary function for JH if GH,H′≥JHandGH,H=JH hold for any H and a constant matrix H′.
The auxiliary function is useful because of the following Lemma1.Lemma 1.
J is nonincreasing under the updating rule Ht+1=argminHGH,Ht, if G is an auxiliary function of J.Proof.
Following the definition ofGH,H′, we have(14)JHt+1≤GHt+1,Ht≤GHt,Ht=JHt.The key point is to find an appropriate auxiliary function for (6). Because the learning process is independent in each view, in generally. Let JH represents JHv to indicate each view’s process, and let B=D1XTW,A=WTW,andC=RD2RT. We rewrite (6) as follows:(15)JH=trXTD1X−2BH+D1HTAH+αtrHCHT.Since the update rules are elementwise, we should prove eachH is nonincreasing under the update (10) by defining the auxiliary function regarding Hik as follows.Lemma 2.
The function(16)GH,H′=∑ikXikTD1Xik−2∑ikBikHik′1+logHikHik′+∑ikAH′D1TikHik2Hik′+α∑ikCH′ikHik2Hik′,is an auxiliary function of JH in problem (6).Proof.
SinceGH,H=JH is obvious, we need to prove GH,H′≥JH. To this end, we compare (16) with (15). For the inequality z≥1+logz, which holds when z>0, we have the following inequalities:(17)trHTB=∑ikBikHik≥∑ikBikHik′1+logHikHik′.With the lemma and proposition in [19], we have the following inequalities:(18)trD1HTAH≤∑ikAH′D1TikHik2Hik′,trHCHT≤∑ikCH′ikHik2Hik′.Collecting all bounds,GH,H′≥JH holds, and Lemma 2 is proven.Theorem 2.
Problem (6) is nonincreasing under the iterative updating rule (10).Proof.
G
H
,
H
′ is a convex function. To find its minima, following the KKT condition, we let(19)∂GH,H′∂Hik=2−Bik+Hik′Hik′+Bik−HikHik′+A+H′ikHik′Hik−A−H′ikHik′Hik′+2αC+H′ikHik′Hik−C+H′ikHikHik′=0.This can derive the updating rule (10) under the objective function JH in (6). This updating rule of Wv also can be derived by this method.


### 3.4. MVC with rNNMF

#### 3.4.1. Representation Combining

After decomposed by the matrix factorizations model, the final representation can be obtained by combining different views’ representation. The final outputH which is a V∗p×n matrix can be obtained from Hv of multiview as(20)H⟵H1;…;Hv;…;HV.


#### 3.4.2. Clustering with Similarity Graph

Because the neighboring structure is kept during the factorization, the graph-based clustering method will be chosen to cluster data in our study. The similarity graphG is built from the final representation H by the k-NN algorithm. Then, normalized cut (Ncut) [22] is used to obtain the final clustering results. It can achieve better performance considering the graph structure of the data. Details of our method are described in Algorithm 1.Algorithm 1:rNNMF‐based MVC model.
Input: input Xv, parameter α, parameter k
Initialize:
for each view do
Wv,Hv⟵NNDSVDXv
end
designRv via (2) with Xv
while not converged do
for all view do
Wv update via (12)
Hv update via (10)
Rv update via (2) with Hv
end
end
combining: H⟵H1;⋯;Hv;⋯;HV
Similarity graph: G is built with H and k
clustering: Ncut G
Output: clustering results


### 3.5. Complexity Analysis

Suppose that the dimensions in all the input views are the same, denoted byd. The dimension of Hv is denoted by p. And V is the total number of views. The overall cost of Hv in each view is On3+pnd. Updating Rv costs Opn2−pn, and the cost of Wv is Opn2+pnd. Furthermore, each of Rav, Rbv, Rcv, and Rdv is On3. Note t is the number of iterations. The overall complexity is OVt2pnd+n3+2pn2−pn+4Vn3. Nevertheless, R (containing 2n non-zero elements) is a sparse matrix. The complexity will be reduced obviously.


## 3.1. Robust Neighboring Constraint Regularization

GivenHv is the low-dimensional representation of Xv, we introduce a special matrix Rv to indicate the constraint of the v-th view; it is defined as(2)Rvi,j=−1,i=j,1,i∈Nvj,0,otherwise,where Nvj is the set of the nearest neighbors of point j in the v-th view. If point i is one of the nearest neighbors of j,Rvi,j will be set as 1. We hope the difference between the points j and i is as small as possible, which can be represented by Hv:,j−Hv:,i, where Hv:,j indicates the j-th column of Hv. So, we introduce constraint HvRv to describe this diversity of the point with its neighbors. The smaller the value of HvRv, the more similar they are. We introduce the L2,1 norm to penalize HvRv for seeking a representation in each view:(3)HvRv2,1.


## 3.2. Objective Function and Optimization Algorithm

In MVC, to learn the neighbor information in each view, based on ORNMF [19] which is a robust representation approach, the proposed rNNMF can be expressed as(4)minWvHv=∑v=1VXv−WvHv2,1+αHvRv2,1,s.t.Hv≥0,Wv≥0,where the L2,1-norm is applied to the loss function and defined as X−WH2,1=∑i=1nXi−WHi. With the error for each point not being squared, the impact of large errors is reduced significantly. The first term in equation (4) indicates the v-th data fidelity term, and the second term is the nearest neighboring constraint term. Hv is the v-th representation from the v-th view. α is the positive parameter to specify the relative importance of the factorization term and regularization term in the model.Like the most NMF-based methods, the objective function in (4) is not convex, so we present an iterative algorithm to achieve the local minima of (4).ComputingHv, to update Hv with Wv fixed, we need to solve the object function as follows:(5)minHv≥0JHv=∑v=1VXv−WvHv2,1+αHvR2,1,as Hv≥0 and JHv being NP-hard, a Lagrange multiplier matrix Θ=Θij is introduced. Then, the Lagrangian function LHv is(6)LHv=∑v=1VtrXvD1vXvT−2trD1vXvTWvHv+trD1vHvTWvTWvHv+αtrHvRvD2vRvTHvT+trΘHvT,where D1v and D2v are diagonal matrices, which are n×n matrices, and the elements defined as(7)D1vii=1Xiv−WvHiv,D2vii=1HvRvi.The partial derivative of Lagrangian functionLHv with respect to Hv is computed as follows:(8)∂LHv∂Hv=−2WvTXvD1vT+2WvTWvHvD1vT+2αHvRvD2vRvT+Θ.BecauseRv is mixed-sign data, we should decompose it into two nonnegative parts M+ and M−, representing the positive part and the negative part, respectively,(9)M+=M+M2,M−=M−M2.LetRav=Rv+DvRv−T, Rbv=Rv−DvRv+T, Rcv=Rv+DvRv+T, and Rdv=Rv−DvRv−T. The updating rule of Hv is formulated as follows:(10)Hv⟵Hv⋅WvTXvD1vT+αHvRav+RbvWvTWvHvD1vT+αHvRcv+Rdv.ComputingWv, to update Wv with Hv fixed, the following object function should be solved:(11)minWv≥0JWv=Xv−WvHv2,1.This is similar as that in [19, 24]. So we have the updating rule as(12)Wv⟵Wv⋅XvD1vHvTWvHvD1vHvT,where ⋅ indicates the Hadamard product. For each view, the updating rule of Hv and Wv satisfies the theorem in [24], which guarantees the correctness of the rule. The correctness analysis and convergence proof of (10) and (12) are shown based on the method [19] in the following section.


## 3.3. Correctness and Convergence

Theorem 1.
If the updating rule ofHv converges, then the final solution satisfies the KKT optimality condition.Proof.
At convergence,Hv∞=Hvt+1=Hvt=Hv, where t denotes the t-th iteration, and the following formula holds:(13)WvTXvD1vT−WvTWvHvD1vT+αHvRvD2vRvT−+αHvRvD2vT+ijHijv2=0.We now prove the convergence of the updating rule (10) using the auxiliary function approach in [19]. The definition of the auxiliary function is as follows.Definition 1.
G
H
,
H
′ is an auxiliary function for JH if GH,H′≥JHandGH,H=JH hold for any H and a constant matrix H′.
The auxiliary function is useful because of the following Lemma1.Lemma 1.
J is nonincreasing under the updating rule Ht+1=argminHGH,Ht, if G is an auxiliary function of J.Proof.
Following the definition ofGH,H′, we have(14)JHt+1≤GHt+1,Ht≤GHt,Ht=JHt.The key point is to find an appropriate auxiliary function for (6). Because the learning process is independent in each view, in generally. Let JH represents JHv to indicate each view’s process, and let B=D1XTW,A=WTW,andC=RD2RT. We rewrite (6) as follows:(15)JH=trXTD1X−2BH+D1HTAH+αtrHCHT.Since the update rules are elementwise, we should prove eachH is nonincreasing under the update (10) by defining the auxiliary function regarding Hik as follows.Lemma 2.
The function(16)GH,H′=∑ikXikTD1Xik−2∑ikBikHik′1+logHikHik′+∑ikAH′D1TikHik2Hik′+α∑ikCH′ikHik2Hik′,is an auxiliary function of JH in problem (6).Proof.
SinceGH,H=JH is obvious, we need to prove GH,H′≥JH. To this end, we compare (16) with (15). For the inequality z≥1+logz, which holds when z>0, we have the following inequalities:(17)trHTB=∑ikBikHik≥∑ikBikHik′1+logHikHik′.With the lemma and proposition in [19], we have the following inequalities:(18)trD1HTAH≤∑ikAH′D1TikHik2Hik′,trHCHT≤∑ikCH′ikHik2Hik′.Collecting all bounds,GH,H′≥JH holds, and Lemma 2 is proven.Theorem 2.
Problem (6) is nonincreasing under the iterative updating rule (10).Proof.
G
H
,
H
′ is a convex function. To find its minima, following the KKT condition, we let(19)∂GH,H′∂Hik=2−Bik+Hik′Hik′+Bik−HikHik′+A+H′ikHik′Hik−A−H′ikHik′Hik′+2αC+H′ikHik′Hik−C+H′ikHikHik′=0.This can derive the updating rule (10) under the objective function JH in (6). This updating rule of Wv also can be derived by this method.


## 3.4. MVC with rNNMF

### 3.4.1. Representation Combining

After decomposed by the matrix factorizations model, the final representation can be obtained by combining different views’ representation. The final outputH which is a V∗p×n matrix can be obtained from Hv of multiview as(20)H⟵H1;…;Hv;…;HV.


### 3.4.2. Clustering with Similarity Graph

Because the neighboring structure is kept during the factorization, the graph-based clustering method will be chosen to cluster data in our study. The similarity graphG is built from the final representation H by the k-NN algorithm. Then, normalized cut (Ncut) [22] is used to obtain the final clustering results. It can achieve better performance considering the graph structure of the data. Details of our method are described in Algorithm 1.Algorithm 1:rNNMF‐based MVC model.
Input: input Xv, parameter α, parameter k
Initialize:
for each view do
Wv,Hv⟵NNDSVDXv
end
designRv via (2) with Xv
while not converged do
for all view do
Wv update via (12)
Hv update via (10)
Rv update via (2) with Hv
end
end
combining: H⟵H1;⋯;Hv;⋯;HV
Similarity graph: G is built with H and k
clustering: Ncut G
Output: clustering results


## 3.4.1. Representation Combining

After decomposed by the matrix factorizations model, the final representation can be obtained by combining different views’ representation. The final outputH which is a V∗p×n matrix can be obtained from Hv of multiview as(20)H⟵H1;…;Hv;…;HV.


## 3.4.2. Clustering with Similarity Graph

Because the neighboring structure is kept during the factorization, the graph-based clustering method will be chosen to cluster data in our study. The similarity graphG is built from the final representation H by the k-NN algorithm. Then, normalized cut (Ncut) [22] is used to obtain the final clustering results. It can achieve better performance considering the graph structure of the data. Details of our method are described in Algorithm 1.Algorithm 1:rNNMF‐based MVC model.
Input: input Xv, parameter α, parameter k
Initialize:
for each view do
Wv,Hv⟵NNDSVDXv
end
designRv via (2) with Xv
while not converged do
for all view do
Wv update via (12)
Hv update via (10)
Rv update via (2) with Hv
end
end
combining: H⟵H1;⋯;Hv;⋯;HV
Similarity graph: G is built with H and k
clustering: Ncut G
Output: clustering results


## 3.5. Complexity Analysis

Suppose that the dimensions in all the input views are the same, denoted byd. The dimension of Hv is denoted by p. And V is the total number of views. The overall cost of Hv in each view is On3+pnd. Updating Rv costs Opn2−pn, and the cost of Wv is Opn2+pnd. Furthermore, each of Rav, Rbv, Rcv, and Rdv is On3. Note t is the number of iterations. The overall complexity is OVt2pnd+n3+2pn2−pn+4Vn3. Nevertheless, R (containing 2n non-zero elements) is a sparse matrix. The complexity will be reduced obviously.


## 4. Experiment

### 4.1. Experimental Setting

#### 4.1.1. Datasets

Four datasets are used in the experiment.UCI Digit (https://archive.ics.uci.edu/ml/datasets/Multiple+Features) is a dataset of handwritten digits of 0 to 9 from UCI machine learning repository. It consists of 2000 points. Similarly to the work in [21], we use 76 Fourier coefficients and 216 profile correlations.3Sources (http://mlg.ucd.ie/datasets/3sources.html) is collected from three well-known online news sources and each is treated as one view. We select the 169 stories which are reported in all three sources.ORL (http://cs.tju.edu.cn/faculty/zhangchangqing/code/ORL_mtv.rar) contains 400 different images of 40 subjects with three views: intensity, LBP, and Gabor. All images are resized into 48 × 48. LBP is a 59-dimension histogram over 9 × 10 pixel patches generated from cropped images. The scale parameter λ in Gabor wavelets is fixed as 4 at four orientations θ = {0°, 45°, 90°, 135°} with a cropped image of size 25°×°30 pixels.Washington (http://www.cs.umd.edu/projects/linqs/projects/lbc/) belongs to WebKB, which collected webpages from four universities. The webpages are distributed over five classes: student, project, course, staff, and faculty, and they are described by two views: the content view and the citation view. Each webpage is described by 1703 words in the content view and the number of citation links between other pages in the citation view. We summarize them in Table 1.Table 1
Information of datasets in the experiments.
Features
UCI
3Sources
ORL
Washington
1
Fourier
Bbc
Intensity
Content
2
Profile
Guardian
LBP
Cites
3
—
Reuters
Gabor
—
Of data
2000
169
400
230
Of classes
10
6
40
5The algorithms that we employ to compare are as follows: (1) BestSV performs the best performance in each view [25]; NMF-based methods: (2) MulNMF and (3) D-SNMF; subspace clustering based methods: (4) c-LRSSC [26], (5) p-LRSSC [26], (6) RMSC [27], (7) ECMSC [28], and (8) MVGL [29].The codes of all the baseline methods are provided by their authors. We adjust the parameters of all comparison methods according to the corresponding literature to obtain their best performance. For RMSC, its parameter is searched from 0.005 to 100 as the authors’ suggestion. For all the NMF-based methods, we set the dimensionality of the new space to be the same as or bigger than the number of clusters and the initial step follows the authors’ suggestion. K-means will be applied to the new representation for clustering. This process is repeated 10 times, and the average clustering performance is recorded as the final result.For rNNMF, the dimensionality ofHv is 60 for UCI and ORL, and it is 20 for 3Sources and Washington. It is initialized by NNDSVD and repeated five times for average results. The hot kernel, in which the parameter σ is 2, is used to determine the distance between points to select the neighboring points as same as in [30] (https://github.com/louloupiano/PCPSNMF).For evaluation, we use three evaluation metrics: accuracy (ACC), normalized mutual information (NMI), and adjusted Rand index (AR) [31]. For all the metrics, a high value denotes good performance.


### 4.2. Clustering Performance

Table2 summarizes the clustering performance. The best values are in bold. As the table shows, rNNMF achieves the highest performance. In UCI, with settings σ=0.1 and k=5, it outperforms the second best method by roughly 6.78%, 9.07%, and 12.49% in the three metrics. In 3Sources, it also obtains the best with settings σ=0.05 and k=5. In ORL, when σ=0.05 and k=5, it also outperforms the best in ACC and AR, while becomes worse slightly in NMI than ECMSC. In Washington, with σ=0.001 and k=7, it also outperforms the second best method by roughly 2.43%, 0.77%, and 12.87%. In all, rNNMF achieves more accurate performance than others obviously.Table 2
Clustering results ((mean) %) on different datasets.
BestSV
MulNMF
D-SNMF
c-LRSSC
p-LRSSC
RMSC
ECMSC
MVGL
rNNMF
UCI
ACC
65.40
86.78
74.91
83.54
83.43
78.48
80.95
82.10
93.56
NMI
61.34
78.20
80.86
85.14
85.12
71.70
83.61
83.39
88.13
AR
50.19
74.11
71.26
81.79
81.09
64.23
76.63
76.70
86.60
3Sources
ACC
53.49
65.68
42.90
70.36
67.10
60.12
66.86
75.74
76.21
NMI
45.23
60.00
29.48
60.02
58.71
51.47
61.46
60.49
62.76
AR
33.47
50.76
19.51
57.09
53.12
39.33
54.20
53.93
63.93
ORL
ACC
71.56
77.50
74.22
74.31
70.60
72.55
81.50
72.75
84.80
NMI
88.09
86.58
86.41
89.24
85.52
87.24
92.71
85.14
92.57
AR
64.48
64.46
63.96
68.17
60.47
65.41
76.49
47.01
80.27
Washington
ACC
59.00
57.39
41.74
45.78
47.15
58.30
57.39
64.35
66.78
NMI
22.45
23.52
10.62
32.72
32.58
28.80
30.71
33.00
33.77
AR
27.86
32.21
8.96
24.84
25.44
33.47
33.00
31.57
44.34We present Figure1 to show more details on clustering results with the similarity matrix yielded from two high-performance MVC methods in UCI and ORL. For UCI, we can see that diagonal blocks of rNNMF are whiter than MulNMF, and the surrounding nondiagonal black blocks are blacker than MulNMF. For ORL, the similar conclusions also hold, which is clearer in the similarity matrix of rNNMF.Figure 1
Visual comparison of the similarity matrices produced on UCI and ORL by 2 high ACC performance methods. (a) rNNMF on UCI. (b) MulNMF on UCI. (c) rNNMF on ORL. (d) ECMSC on ORL.
(a)
(b)
(c)
(d)Hence, with the representation combining process, rNNMF can fuse multiple views efficiently. And neighboring constraint plays an important role in discovering the underlying structure of points. It is observed that a comprehensive graph structure is important to discover the cluster structure.


### 4.3. Influence of the Parameters

σ plays an important role for representation learning process in rNNMF. We test σ within the setting [0, 0.0001, 0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1] for all datasets. Among them, σ=0 means there is no neighboring constraint in our model. The ACC and NMI results are shown in Figure 2.Figure 2
ACC and NMI with parameterσ on four datasets. (a) UCI. (b) 3Sources. (c) ORL. (d) Washington.
(a)
(b)
(c)
(d)It shows that ACC performance and NMI performance improve with increasingσ in UCI, and they will reach their best performance when σ=0.1. Then, the performance drops obviously. This tendency can also be observed in 3Sources. The only difference is that the best ACC and NMI can be obtained when σ=0.05. However, in ORL dataset, performances improve slightly with increasing σ, and they drop obviously after reaching the best value. ACC and NMI in Washington will drop with increasing σ. This shows that too large σ can destroy the similarity structure in each view, which can lead to worse performance in final clustering process. And the suitable σ can strengthen the cluster structure in learning process. Furthermore, when σ=0, ACC and NMI performances in our model are better than those in some methods, such as D-SNMF and RMSC, demonstrating that combining multiviews and building graph is useful in MVC.Parameterk is important to create the final similarity graph. Figure 3 shows the ACC and NMI results with different k values. As we can see, the final results are sensitive with k in integrated representation. In UCI, 3Sources, and ORL, obviously, the best performance can be obtained when k=5, and then, the tendency of performance will drop as k increases. In Washington, ACC and NMI reach their best when k=7. This shows that the influence of k mainly focuses on similarity graph building from integrated representation, and it is important to build the graph from representation.Figure 3
ACC and NMI with parameterk on four datasets. (a) UCI. (b) 3Sources. (c) ORL. (d) Washington.
(a)
(b)
(c)
(d)


### 4.4. Convergence Analysis

Figure4 shows the convergence property of rNNMF by computing the objective error in each iteration. It is clear that the objective value decreases steadily in all datasets. All of NMI finally keeps the rough stability around the convergence point. So the maximum number of iterations is set to 100 for all the experiments.Figure 4
Objective error values on four datasets. (a) UCI. (b) 3Sources. (c) ORL. (d) Washington.
(a)
(b)
(c)
(d)


## 4.1. Experimental Setting

### 4.1.1. Datasets

Four datasets are used in the experiment.UCI Digit (https://archive.ics.uci.edu/ml/datasets/Multiple+Features) is a dataset of handwritten digits of 0 to 9 from UCI machine learning repository. It consists of 2000 points. Similarly to the work in [21], we use 76 Fourier coefficients and 216 profile correlations.3Sources (http://mlg.ucd.ie/datasets/3sources.html) is collected from three well-known online news sources and each is treated as one view. We select the 169 stories which are reported in all three sources.ORL (http://cs.tju.edu.cn/faculty/zhangchangqing/code/ORL_mtv.rar) contains 400 different images of 40 subjects with three views: intensity, LBP, and Gabor. All images are resized into 48 × 48. LBP is a 59-dimension histogram over 9 × 10 pixel patches generated from cropped images. The scale parameter λ in Gabor wavelets is fixed as 4 at four orientations θ = {0°, 45°, 90°, 135°} with a cropped image of size 25°×°30 pixels.Washington (http://www.cs.umd.edu/projects/linqs/projects/lbc/) belongs to WebKB, which collected webpages from four universities. The webpages are distributed over five classes: student, project, course, staff, and faculty, and they are described by two views: the content view and the citation view. Each webpage is described by 1703 words in the content view and the number of citation links between other pages in the citation view. We summarize them in Table 1.Table 1
Information of datasets in the experiments.
Features
UCI
3Sources
ORL
Washington
1
Fourier
Bbc
Intensity
Content
2
Profile
Guardian
LBP
Cites
3
—
Reuters
Gabor
—
Of data
2000
169
400
230
Of classes
10
6
40
5The algorithms that we employ to compare are as follows: (1) BestSV performs the best performance in each view [25]; NMF-based methods: (2) MulNMF and (3) D-SNMF; subspace clustering based methods: (4) c-LRSSC [26], (5) p-LRSSC [26], (6) RMSC [27], (7) ECMSC [28], and (8) MVGL [29].The codes of all the baseline methods are provided by their authors. We adjust the parameters of all comparison methods according to the corresponding literature to obtain their best performance. For RMSC, its parameter is searched from 0.005 to 100 as the authors’ suggestion. For all the NMF-based methods, we set the dimensionality of the new space to be the same as or bigger than the number of clusters and the initial step follows the authors’ suggestion. K-means will be applied to the new representation for clustering. This process is repeated 10 times, and the average clustering performance is recorded as the final result.For rNNMF, the dimensionality ofHv is 60 for UCI and ORL, and it is 20 for 3Sources and Washington. It is initialized by NNDSVD and repeated five times for average results. The hot kernel, in which the parameter σ is 2, is used to determine the distance between points to select the neighboring points as same as in [30] (https://github.com/louloupiano/PCPSNMF).For evaluation, we use three evaluation metrics: accuracy (ACC), normalized mutual information (NMI), and adjusted Rand index (AR) [31]. For all the metrics, a high value denotes good performance.


## 4.1.1. Datasets

Four datasets are used in the experiment.UCI Digit (https://archive.ics.uci.edu/ml/datasets/Multiple+Features) is a dataset of handwritten digits of 0 to 9 from UCI machine learning repository. It consists of 2000 points. Similarly to the work in [21], we use 76 Fourier coefficients and 216 profile correlations.3Sources (http://mlg.ucd.ie/datasets/3sources.html) is collected from three well-known online news sources and each is treated as one view. We select the 169 stories which are reported in all three sources.ORL (http://cs.tju.edu.cn/faculty/zhangchangqing/code/ORL_mtv.rar) contains 400 different images of 40 subjects with three views: intensity, LBP, and Gabor. All images are resized into 48 × 48. LBP is a 59-dimension histogram over 9 × 10 pixel patches generated from cropped images. The scale parameter λ in Gabor wavelets is fixed as 4 at four orientations θ = {0°, 45°, 90°, 135°} with a cropped image of size 25°×°30 pixels.Washington (http://www.cs.umd.edu/projects/linqs/projects/lbc/) belongs to WebKB, which collected webpages from four universities. The webpages are distributed over five classes: student, project, course, staff, and faculty, and they are described by two views: the content view and the citation view. Each webpage is described by 1703 words in the content view and the number of citation links between other pages in the citation view. We summarize them in Table 1.Table 1
Information of datasets in the experiments.
Features
UCI
3Sources
ORL
Washington
1
Fourier
Bbc
Intensity
Content
2
Profile
Guardian
LBP
Cites
3
—
Reuters
Gabor
—
Of data
2000
169
400
230
Of classes
10
6
40
5The algorithms that we employ to compare are as follows: (1) BestSV performs the best performance in each view [25]; NMF-based methods: (2) MulNMF and (3) D-SNMF; subspace clustering based methods: (4) c-LRSSC [26], (5) p-LRSSC [26], (6) RMSC [27], (7) ECMSC [28], and (8) MVGL [29].The codes of all the baseline methods are provided by their authors. We adjust the parameters of all comparison methods according to the corresponding literature to obtain their best performance. For RMSC, its parameter is searched from 0.005 to 100 as the authors’ suggestion. For all the NMF-based methods, we set the dimensionality of the new space to be the same as or bigger than the number of clusters and the initial step follows the authors’ suggestion. K-means will be applied to the new representation for clustering. This process is repeated 10 times, and the average clustering performance is recorded as the final result.For rNNMF, the dimensionality ofHv is 60 for UCI and ORL, and it is 20 for 3Sources and Washington. It is initialized by NNDSVD and repeated five times for average results. The hot kernel, in which the parameter σ is 2, is used to determine the distance between points to select the neighboring points as same as in [30] (https://github.com/louloupiano/PCPSNMF).For evaluation, we use three evaluation metrics: accuracy (ACC), normalized mutual information (NMI), and adjusted Rand index (AR) [31]. For all the metrics, a high value denotes good performance.


## 4.2. Clustering Performance

Table2 summarizes the clustering performance. The best values are in bold. As the table shows, rNNMF achieves the highest performance. In UCI, with settings σ=0.1 and k=5, it outperforms the second best method by roughly 6.78%, 9.07%, and 12.49% in the three metrics. In 3Sources, it also obtains the best with settings σ=0.05 and k=5. In ORL, when σ=0.05 and k=5, it also outperforms the best in ACC and AR, while becomes worse slightly in NMI than ECMSC. In Washington, with σ=0.001 and k=7, it also outperforms the second best method by roughly 2.43%, 0.77%, and 12.87%. In all, rNNMF achieves more accurate performance than others obviously.Table 2
Clustering results ((mean) %) on different datasets.
BestSV
MulNMF
D-SNMF
c-LRSSC
p-LRSSC
RMSC
ECMSC
MVGL
rNNMF
UCI
ACC
65.40
86.78
74.91
83.54
83.43
78.48
80.95
82.10
93.56
NMI
61.34
78.20
80.86
85.14
85.12
71.70
83.61
83.39
88.13
AR
50.19
74.11
71.26
81.79
81.09
64.23
76.63
76.70
86.60
3Sources
ACC
53.49
65.68
42.90
70.36
67.10
60.12
66.86
75.74
76.21
NMI
45.23
60.00
29.48
60.02
58.71
51.47
61.46
60.49
62.76
AR
33.47
50.76
19.51
57.09
53.12
39.33
54.20
53.93
63.93
ORL
ACC
71.56
77.50
74.22
74.31
70.60
72.55
81.50
72.75
84.80
NMI
88.09
86.58
86.41
89.24
85.52
87.24
92.71
85.14
92.57
AR
64.48
64.46
63.96
68.17
60.47
65.41
76.49
47.01
80.27
Washington
ACC
59.00
57.39
41.74
45.78
47.15
58.30
57.39
64.35
66.78
NMI
22.45
23.52
10.62
32.72
32.58
28.80
30.71
33.00
33.77
AR
27.86
32.21
8.96
24.84
25.44
33.47
33.00
31.57
44.34We present Figure1 to show more details on clustering results with the similarity matrix yielded from two high-performance MVC methods in UCI and ORL. For UCI, we can see that diagonal blocks of rNNMF are whiter than MulNMF, and the surrounding nondiagonal black blocks are blacker than MulNMF. For ORL, the similar conclusions also hold, which is clearer in the similarity matrix of rNNMF.Figure 1
Visual comparison of the similarity matrices produced on UCI and ORL by 2 high ACC performance methods. (a) rNNMF on UCI. (b) MulNMF on UCI. (c) rNNMF on ORL. (d) ECMSC on ORL.
(a)
(b)
(c)
(d)Hence, with the representation combining process, rNNMF can fuse multiple views efficiently. And neighboring constraint plays an important role in discovering the underlying structure of points. It is observed that a comprehensive graph structure is important to discover the cluster structure.


## 4.3. Influence of the Parameters

σ plays an important role for representation learning process in rNNMF. We test σ within the setting [0, 0.0001, 0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1] for all datasets. Among them, σ=0 means there is no neighboring constraint in our model. The ACC and NMI results are shown in Figure 2.Figure 2
ACC and NMI with parameterσ on four datasets. (a) UCI. (b) 3Sources. (c) ORL. (d) Washington.
(a)
(b)
(c)
(d)It shows that ACC performance and NMI performance improve with increasingσ in UCI, and they will reach their best performance when σ=0.1. Then, the performance drops obviously. This tendency can also be observed in 3Sources. The only difference is that the best ACC and NMI can be obtained when σ=0.05. However, in ORL dataset, performances improve slightly with increasing σ, and they drop obviously after reaching the best value. ACC and NMI in Washington will drop with increasing σ. This shows that too large σ can destroy the similarity structure in each view, which can lead to worse performance in final clustering process. And the suitable σ can strengthen the cluster structure in learning process. Furthermore, when σ=0, ACC and NMI performances in our model are better than those in some methods, such as D-SNMF and RMSC, demonstrating that combining multiviews and building graph is useful in MVC.Parameterk is important to create the final similarity graph. Figure 3 shows the ACC and NMI results with different k values. As we can see, the final results are sensitive with k in integrated representation. In UCI, 3Sources, and ORL, obviously, the best performance can be obtained when k=5, and then, the tendency of performance will drop as k increases. In Washington, ACC and NMI reach their best when k=7. This shows that the influence of k mainly focuses on similarity graph building from integrated representation, and it is important to build the graph from representation.Figure 3
ACC and NMI with parameterk on four datasets. (a) UCI. (b) 3Sources. (c) ORL. (d) Washington.
(a)
(b)
(c)
(d)


## 4.4. Convergence Analysis

Figure4 shows the convergence property of rNNMF by computing the objective error in each iteration. It is clear that the objective value decreases steadily in all datasets. All of NMI finally keeps the rough stability around the convergence point. So the maximum number of iterations is set to 100 for all the experiments.Figure 4
Objective error values on four datasets. (a) UCI. (b) 3Sources. (c) ORL. (d) Washington.
(a)
(b)
(c)
(d)


## 5. Conclusion

In this paper, we proposed a novel NMF-based MVC model, named “rNNMF.” In this model, the neighbor structure representation can be learned in each view, andL2,1-norm-based loss function is designed to improve its robustness against noises and outliers. Then, a final representation of data was integrated with those representations of all views, and a graph was learned from this representation. Finally, the graph cut method was used to partition data into its underlying clusters. Unlike existing methods, rNNMF can well encode the local structure from each view feature space and achieve the structure agreement via combining fusion. Experiments show that the rNNMF-based model yields higher performance. One of the important further works is to find a better graph structure to obtain more clear representation. In addition, the weight for each view is also worth studying to deal with varying levels of quality. The future work can also be done to extend rNNMF model and optimization strategy to handle dynamic data and achieve online multiview clustering.



---

*Source: 6084382-2019-11-23.xml*