# Localized Simple Multiple Kernel K-Means Clustering with Matrix-Induced Regularization

Authors: Jiaji Qiu; Huiying Xu; Xinzhong Zhu; Michael Adjeisah
Journal: Computational Intelligence and Neuroscience
 (2023)

---

## Abstract

Multikernel clustering achieves clustering of linearly inseparable data by applying a kernel method to samples in multiple views. A localized SimpleMKKM (LI-SimpleMKKM) algorithm has recently been proposed to perform min-max optimization in multikernel clustering where each instance is only required to be aligned with a certain proportion of the relatively close samples. The method has improved the reliability of clustering by focusing on the more closely paired samples and dropping the more distant ones. Although LI-SimpleMKKM achieves remarkable success in a wide range of applications, the method keeps the sum of the kernel weights unchanged. Thus, it restricts kernel weights and does not consider the correlation between the kernel matrices, especially between paired instances. To overcome such limitations, we propose adding a matrix-induced regularization to localized SimpleMKKM (LI-SimpleMKKM-MR). Our approach addresses the kernel weight restrictions with the regularization term and enhances the complementarity between base kernels. Thus, it does not limit kernel weights and fully considers the correlation between paired instances. Extensive experiments on several publicly available multikernel datasets show that our method performs better than its counterparts.


---

## Body

## 1. Introduction

Clustering is a widely used machine learning algorithm [1–4]. Multikernel clustering is one of the clustering methods which is based on multiview clustering and performs clustering by implicitly mapping sample points of different views to high dimensions. Many studies have been carried out in recent years [5–9]. For example, early work [10] shows that kernel matrices could encode different views or sources of the data, and MKKM [11] extends the kernel combination by adapting the weights of kernel matrices. Gönen and Margolin [12] improve the performance of MKKM by focusing on sample-specific weights on the correlations between neighbors to obtain a better clustering, called localized MKKM. Du et al. [13] engaged the l2,1 norm to reduce the uncertainty of algorithm results due to unexpected factors such as outliers. To enhance the complementary nature of base kernels and reduce redundancy, Liu et al. [14] employed a regularization term containing a matrix that measures the correlation between base kernels to facilitate alignment. Other works [15–19]are different from the original MKKM method [11] that prefused multiple view kernels. These methods first obtain the clustering results of each kernel matrix, then fuse each clustering result in a later stage to obtain a unified result.More recently, a newly proposed optimization strategy, simple multiple kernel k-means (SimpleMKKM) [20] has emerged as a representative of multikernel clustering (MKC). Different from the normal MKKM algorithm, SimpleMKKM assumes minimization of kernel weights and maximization of cluster partition, which leads to min-max optimization that is somewhat difficult to unravel. It converts the optimization to a minimization problem and cleverly solves it with a specially designed gradient descent method rather than a coordinate descent method. However, it is established that the strict alignment of the combined kernel matrix can force the combination globally. Therefore, Liu et al. proposed [21] localized SimpleMKKM, which reduces the negative impact of distant samples on clustering by restricting the kernel alignment to the k-nearest neighbors of the sample rather than the global alignment. In this way, LI-SimpleMKKM can sufficiently account for the variation between samples, improving clustering performance.Although localized SimpleMKKM shows excellent performance on MKC problems, we find that the correlation between the given kernels is not sufficiently considered providing an opportunity for improvement based on the listed problem statement.(i)
The original method [21] makes the data stable by setting a larger weight ηu in the gradient descent step and maintaining the summation and nonnegativity of the weights through the association with other weights. However, this idea only enhances the correlation between different view weights and ηu and does not consider the relationship between view kernel matrices, especially between pairs.(ii)
The original method is possible to select multikernel kernels with high correlation for clustering simultaneously. Repeated selection of similar information sources makes the algorithm redundant and has low diversity, leading to the low ratio of different kernel matrices’ effectiveness, ultimately affecting the accuracy of the clustering results.Motivated by these, we propose a localized SimpleMKKM with matrix-induced regularization (LI-SimpleMKKM-MR) to improve upon the LI-SMKKM algorithm by adding an entry containing a matrix to measure the correlation between each two basis kernel matrices. LI-SimpleMKKM-MR algorithm can reduce the probability and simultaneously select high-correlation kernels, thereby enhancing the diversity of synthetic kernels and enhancing the complementarity of low-correlation kernels. Moreover, it adopts the advantage of localized SimpleMKKM, which has a better optimization effect that can be achieved by clustering the neighbor index matrix formed by the sample and the nearestk neighbors, and uses the optimization strategy minη−maxH instead of minη−minH.Compared with the original multiple kernel clustering, the proposed method optimizes kernel matrix weights by using gradient descent rather than coordinate descent, combined with localized sample alignment and kernel matrix induced regularization. This reduces the negative effects of forced alignment of long-distance samples and high redundancy and low complementarity of multiple kernel matrices.We experimented with the algorithm on 6 benchmark datasets and compared it with the other nine baseline algorithms that solve similar problems through four indicators: clustering accuracy (ACC), normalized mutual information (NMI), purity, and rand index. We find that LI-SimpleMKKM-MR outperforms other methods. This is the first work to fully consider and solve the correlation problem between the base kernels to the best of our knowledge.The contributions of this method are summarized as follows:(1)
Proposed algorithm LI-SimpleMKKM-MR can productively deal with the alignment problem between kernel matrices using a regularization term, in order to reduce the redundancy, enhance the complementarity, and correlation between kernel matrices.(2)
The novelty is that our proposed method can be transformed into SimpleMKKM or LI-SimpleMKKM by adjusting the hyperparameters, making LI-SimpleMKKM-MR an extension of the previous two methods.(3)
We conducted extensive experiments on 6 public multiple kernel datasets using 4 metrics. The results show that our method achieves state-of-the-art performance compared to 9 existing baseline algorithms. The experiments essentially validate our understanding of the previous problems and the effectiveness of the proposed solution.


## 2. Related Works

### 2.1. Multiple Kernel K-Means

Letxii=1n∈χ be a set of n samples, and ϕp⋅:x∈χ⇒Hp means mapping the features of the sample x of the pth view into a high-dimensional Hilbert space Hp1≤p≤m. According to this theory, each sample can be represented by ϕηx=η1ϕ1⊤x,…,ηmϕm⊤x, where η=η1,⋯ηm⊤ means the weights of m prespecified base kernels Kp⋅,⋅p=1m. The kernel weights will be changed according to the algorithm optimizing in the kernel learning step. According to the definition of ϕηx and the definition of kernel function, the kernel function can be defined as follows:(1)Kηxi,xj=ϕη⊤xiϕηxj=∑p=1mηp2Kpxi,xj.We can use training samplesxii=1n by (1) to calculate a kernel matrix Kη. Based on the calculation of Kη, the objective function of MKKM with Kη can be expressed as follows:(2)minH,ηTrKηIn−HH⊤s.t.H⊤H=Ik,η⊤1m=1,ηp≥0,∀p.Here,H∈Rn×k means one soft label matrix, which is used to solve NP-hard problems caused by the direct use of hard allocation, which is also called the partition matrix. Moreover, Ik means an identity matrix which is k×k in size.Optimization of (2) can be divided into 2 steps: optimizing H or η and fixing the other one.(i)
OptimizingH with η is fixed, the problem of optimizing H in (2) can be represented as follows:(3)maxHTrH⊤KηHs.t.H∈Rn×k,H⊤H=Ik.The optimization ofH of (3) can be easily solved by taking the first k eigenvalues of the matrix Kη.(ii)
Optimizingη with H is fixed, with the soft label matrix H is fixed, the problem of optimizing η in (2) can be represented as follows: (4)minη∑p=1mηp2TrKpIn−HH⊤s.t.H⊤H=Ik,η⊤1m=1,ηp≥0,∀p.According to the constraints, it can be easily solved by the Lagrange multiplier method [10].


### 2.2. MKKM with Matrix-Induced Regularization

As (2) shows that ηp only depends on Kp and H. However, the interactions between different kernel matrices are not considered. Liu et al. [14] defined a criterion MKp,Kq to measure the correlation between Kp and Kq. A larger MKp,Kq means high correlation between Kp and Kq, and a smaller one implies that their correlation is low. By introducing the criterion term in (2), we can obtain the following objective function:(5)MinH,ηTrKηIn−HH⊤+λ2η⊤Mηs.t.H∈Rn×k,H⊤H=Ik,η⊤1m=1,ηp≥0,∀p,where λ is a hyperparameter to balance clustering loss and regularization term.


### 2.3. Localized SimpleMKKM

Unlike the existingminη−minH paradigm, SimpleMKKM adopts minη−maxH optimization [20]. However, it is extended to make full use of the information between local sample neighbors and minη−maxH optimization to enhance the clustering effect with a fusion algorithm called localized SimpleMKKM. The objective value of LI-SimpleMKKM can be represented as follows:(6)minηmaxHTrH⊤∑i=1nBiKηBiHs.t.H∈Rn×k,H⊤H=Ik,∑p=1mηp=1,ηp≥0,∀p,where ∑p=1mηp2Kp and Bi=NiNi⊤ with Ni∈0,1n×roundτ×n are the ith sample’s neighborhood mask matrices; that is, only the samples closest to the target sample will be aligned. This new method is hard to solve with a simple two-step alternating optimization convergence method. To solve this problem, LI-SimpleMKKM first optimizes H by a method similar to MKKM and then converts the problem into a problem of finding the minimum with respect to η. With proving the differentiability of the minimized formula, the gradient descent method can be used to optimize η [21].


## 2.1. Multiple Kernel K-Means

Letxii=1n∈χ be a set of n samples, and ϕp⋅:x∈χ⇒Hp means mapping the features of the sample x of the pth view into a high-dimensional Hilbert space Hp1≤p≤m. According to this theory, each sample can be represented by ϕηx=η1ϕ1⊤x,…,ηmϕm⊤x, where η=η1,⋯ηm⊤ means the weights of m prespecified base kernels Kp⋅,⋅p=1m. The kernel weights will be changed according to the algorithm optimizing in the kernel learning step. According to the definition of ϕηx and the definition of kernel function, the kernel function can be defined as follows:(1)Kηxi,xj=ϕη⊤xiϕηxj=∑p=1mηp2Kpxi,xj.We can use training samplesxii=1n by (1) to calculate a kernel matrix Kη. Based on the calculation of Kη, the objective function of MKKM with Kη can be expressed as follows:(2)minH,ηTrKηIn−HH⊤s.t.H⊤H=Ik,η⊤1m=1,ηp≥0,∀p.Here,H∈Rn×k means one soft label matrix, which is used to solve NP-hard problems caused by the direct use of hard allocation, which is also called the partition matrix. Moreover, Ik means an identity matrix which is k×k in size.Optimization of (2) can be divided into 2 steps: optimizing H or η and fixing the other one.(i)
OptimizingH with η is fixed, the problem of optimizing H in (2) can be represented as follows:(3)maxHTrH⊤KηHs.t.H∈Rn×k,H⊤H=Ik.The optimization ofH of (3) can be easily solved by taking the first k eigenvalues of the matrix Kη.(ii)
Optimizingη with H is fixed, with the soft label matrix H is fixed, the problem of optimizing η in (2) can be represented as follows: (4)minη∑p=1mηp2TrKpIn−HH⊤s.t.H⊤H=Ik,η⊤1m=1,ηp≥0,∀p.According to the constraints, it can be easily solved by the Lagrange multiplier method [10].


## 2.2. MKKM with Matrix-Induced Regularization

As (2) shows that ηp only depends on Kp and H. However, the interactions between different kernel matrices are not considered. Liu et al. [14] defined a criterion MKp,Kq to measure the correlation between Kp and Kq. A larger MKp,Kq means high correlation between Kp and Kq, and a smaller one implies that their correlation is low. By introducing the criterion term in (2), we can obtain the following objective function:(5)MinH,ηTrKηIn−HH⊤+λ2η⊤Mηs.t.H∈Rn×k,H⊤H=Ik,η⊤1m=1,ηp≥0,∀p,where λ is a hyperparameter to balance clustering loss and regularization term.


## 2.3. Localized SimpleMKKM

Unlike the existingminη−minH paradigm, SimpleMKKM adopts minη−maxH optimization [20]. However, it is extended to make full use of the information between local sample neighbors and minη−maxH optimization to enhance the clustering effect with a fusion algorithm called localized SimpleMKKM. The objective value of LI-SimpleMKKM can be represented as follows:(6)minηmaxHTrH⊤∑i=1nBiKηBiHs.t.H∈Rn×k,H⊤H=Ik,∑p=1mηp=1,ηp≥0,∀p,where ∑p=1mηp2Kp and Bi=NiNi⊤ with Ni∈0,1n×roundτ×n are the ith sample’s neighborhood mask matrices; that is, only the samples closest to the target sample will be aligned. This new method is hard to solve with a simple two-step alternating optimization convergence method. To solve this problem, LI-SimpleMKKM first optimizes H by a method similar to MKKM and then converts the problem into a problem of finding the minimum with respect to η. With proving the differentiability of the minimized formula, the gradient descent method can be used to optimize η [21].


## 3. Localized Simple Multiple Kernel K-Means with Matrix-Induced Regularization

According to Liu et al. [21], the relative value of ηp is only dependent on Kp, H, and Ku, where u is the largest component of η. Only the weights of different kernels are linked, indicating that the LI-SimpleMKKM algorithm is not fully considered the interaction of the kernels when optimizing the kernel weights. This motivates us to derive a regularization term which can measure the correlation between the base kernels to improve this shortcoming.


### 3.1. Formulation

Although the performance of clustering can be improved to some extent by aligning samples with closer samples, there is still room for further improvement of that algorithm.To address this issue, we define a criterionMKp,Kq to measure the correlation between Kp and Kq. A larger MKp,Kq means high correlation between Kp and Kq, and a smaller one implies that their correlation is low. We propose to add a matrix-induced regularization ηTMη based on LI-SimpleMKKM to improve the shortcomings, enhancing the kernel alignment between multiple kernels and reducing the redundancy of kernels with higher correlation. By fusing the regular term with (6), we can get the objective function as follows:(7)minη∈∆maxH∈Rn×kTrH⊤∑i=1nBiKηBiH+λ2η⊤Mη,s.t.H∈Rn×k,H⊤H=Ik,∑p=1mηp=1,ηp≥0,∀p,where λ is a trade-off parameter to balance the loss of clustering problem and the regularization term on kernel weights. The regularization term has many types, such as KL divergence and Hilbert–Schmidt independent criterion.In our proposed algorithm, we setMpq=TrKpKq for each element in M to measure the correlation between Kp and Kq. Choosing this method makes the calculation not too complicated and adopts the Hilbert–Schmidt independent criterion in disguise, which can reflect the correlation between different base kernels to a certain extent.The incorporation ofηTMη use of the basic kernel better, thus improving clustering performance. Moreover, we can clearly see that if we set λ=0, equation (7) is a special case of LI-SimpleMKKM.Li et al. [22] use η⊤Miη instead of η⊤Mη as a regular term, where Mi means a matrix with Mpqi=TrKpiKqi, Kηi=Ni⊤KηNi. Although this method shows excellent performance, we find that the induced regularization of matrices should be global rather than local because the kernel alignment should be for the global kernel matrix. It can also be found from the experimental results in Table 1 that the global kernel-induced regularization has a better effect.Table 1
Comparation of localizedM and global M in ACC.
DatasetsLocalizedMGlobalMFlower1751.8 ± 1.061.3 ± 1.5Flower10237.4 ± 0.844.0 ± 1.0ProteinFold36.4 ± 1.539.0 ± 1.4Digital83.4 ± 1.294.9 ± 3.0Cal-25views36.6 ± 0.737.3 ± 1.1Cal-7classes47.8 ± 1.049.8 ± 0.8


### 3.2. Alternate Optimization

We design a two-step alternating optimization to solve the formula in (7).(i)
OptimizingH by η is fixed: fixed η, the optimization value with respect to H in (7) is represented as follows:(8)maxH∈Rn×kTrH⊤∑i=1nBiKηBiHs.t.H⊤H=Ik.Treating the summationBiKηBi as a whole, (8) can be solved by solving for the eigenvalues of the matrix.(ii)
Optimizingη by H is fixed: fixed H, the optimization value with respect to η in (7) can be represented as follows:(9)Jη=maxηTrH⊤∑i=1nBiKηBiH.+λ2ηTMηs.t.H⊤H=.We first prove the differentiability of (9), then calculate the gradient, and optimize η by the gradient descent method. The first part of the objective function in (9) is as follows:(10)TrH⊤∑i=1nBiKηBiH.With the hyperparameterτ defined, we can regard BiKηBi as a whole, which is global kernel alignment and PSD [21]. For convenience, we let BiKηBi=Tηi.Thus, the function in (9) can be represented as follows:(11)minη∈∆Jη,with(12)Jη=maxHTrH⊤TηiH+λ2η⊤Mηs.t.H∈Rn×k,H⊤H=Ik.Theorem 1.
Jη in (12) is differentiable. ∂Jη/∂ηp=2ηpTrH∗⊤TpiH∗+λ∑q=1mηqMpq,
whereH∗=argmaxHTrH⊤TηiHs.t.H⊤H=Ik.Proof.
For any givenη∈∆, the maximum of optimization problem TrH⊤KηHs.t.H⊤H=Ik is unique [21], with H∗˜∈H∗˜H∗˜=H∗U,UU⊤=U⊤U=Ik the corresponding maximizer. According to theorem in [23], the former part of Jη is differentiable. By defining other elements in η except for p as s and the latter part of the Jη as J2η, the differential of J2η=λ/2η⊤Mη can be expressed as follows:(13)J2η=λ2ηpηsMppMpsMpsMssηpηs=λ2ηp2Mpp+2ηpηsMps+ηs2Mss,∂J2η∂ηp=ληpMpp+ληsMps,where p means one of the components of η and s means all of the other components so that ∂J2η/∂ηp=λ∑q=1mηqMpq, and the whole Jη in (12) is differentiable.
We can solve this problem by designing a gradient descent method. After obtaining the gradient ofJη under the premise of satisfying the equality constraints ∑p=1mηp=1 and nonnegativity constraints ηp≥0 of η, we update η by gradient descent [23]. To implement this method, we let ηu become a nonzero unit in η and ∇Jη indicates the reduced gradient of Jη. The pth 1≤p≤m element of ∇Jη is presented as follows:(14)∇Jηp=∂Jη∂ηp−∂Jη∂ηu∀p≠u,and(15)∇Jηu=−∑p=1,p≠um∇Jηp.
To improve numerical stability, we chooseu as the largest unit in the vector η. The nonnegativity constraint of η also needs to be considered during gradient descent.
To minimizeJη, we define −∇Jη as a descent direction. However, if there is an index p corresponding to ηp=0, with ∇Jηp≥0, the situation of ηp<0 may occur when the gradient is updated, violating the nonnegativity constraint. Under these circumstances, the descent direction for that unit p is set as zero. This makes η when the gradient is updated as follows:(16)dp=0,ifηp=0and∇Jηp≥0,−∇Jηp,ifηp≥0andp≠u,−∇Jηu,forp=u.
The gradient update adopts the formulaη←η+γd, where γ is the step size. We determine the step size γ by a one-dimensional linear search method, rather than setting it directly, and in order to ensure global convergence, this method has appropriate stopping criteria, for example, Armijo’s rule [21].The specific calculation steps of the algorithm in equation (13) are detailed in Algorithm 1.Algorithm 1: LI-SimpleMKKM-MR.
Input: Kpp=1m, k, λ, τ, ϵ, and t(1)
Initializationη0=1/m and t = 1.(2)
CalculateBii=1n by Bi=NiNi⊤ for pth samples 1≤p≤m according to the average kernel.(3)
Tpi=∑i=1nBi(4)
repeat(5)
UpdateH by solving the first k eigenvalues with Tηi.(6)
Compute∂Jη/∂ηp1≤p≤m and the direction of descent of the gradient dt in (16).(7)
Updateηt+1←ηt+γdt.(8)
t←t+1.(9)
Untilmaxηt+1−ηt≤ϵTheorem 2.
The proposed algorithm is converged.Proof.
Note that for thekth iteration, TrH⊤TηiH will be bigger than k + 1th iteration. In each iteration, the gradient of ηp is smaller than 0 by equation (14) because u is the component of η, and in order to get the maximum of TrH⊤TηiH, TrηuH⊤TuiH should be larger than other parts, so the differential of it is bigger than others. The component u has the gradient which is the opposite number of other component gradients’ sum by the equation (15). According to the equation (16), the component of p will be bigger, while the coefficient of u will be smaller, and we can let ∆ as the difference of the kth iteration and k + 1th’s, with ∆=Trγd1H⊤T1iH+Trγd2H⊤T2iH+…+TrγdmH⊤TmiH, ∑p=1,p≠umdp with H⊤TuiH as the largest part of each H⊤TiH, γ is bigger than 0, it can be easy to get the conclusion ∆ is smaller than 0, because the non-negativity of ηand kernel matrix, the former term has the lower bound 0 and convex, so the former term’s convergence is been proofed.As for the latter termλ/2η⊤Mη with the similar thought, it is also decreasing monotonically because M is a PSD matrix, η is not negative, and λ is bigger than 0; the second derivative of J2η can be easy to be calculated bigger than 0 (since each element of M is bigger than 0), so the latter term has the lower bound 0 and convex. At the same time, the whole equation (13) is monotonically decreasing and lower-bounded.


### 3.3. Computational Complexity Analysis

We theoretically analyze the time complexity of the algorithm LI-SimpleMKKM-MR. We assume thatn and m denote the number of samples and the number of base kernels. LI-SimpleMKKM-MR based on Algorithm 1 first computes a neighborhood mask matrix with computational complexity On2log2n and then computes the regularization term with computational complexity Om3. Therefore, the time complexity of LI-SimpleMKKM-MR is n3+n2log2n+m3 per iteration.Let us compare the complexity of LI-SimpleMKKM-MR and LI-SimpleMKKM. Since in most cases, the number of base kernels is much fewer than the number of samplesm≪n, compared with LI-SimpleMKKM n3, the time complexity of the proposed method does not increase significantly.


## 3.1. Formulation

Although the performance of clustering can be improved to some extent by aligning samples with closer samples, there is still room for further improvement of that algorithm.To address this issue, we define a criterionMKp,Kq to measure the correlation between Kp and Kq. A larger MKp,Kq means high correlation between Kp and Kq, and a smaller one implies that their correlation is low. We propose to add a matrix-induced regularization ηTMη based on LI-SimpleMKKM to improve the shortcomings, enhancing the kernel alignment between multiple kernels and reducing the redundancy of kernels with higher correlation. By fusing the regular term with (6), we can get the objective function as follows:(7)minη∈∆maxH∈Rn×kTrH⊤∑i=1nBiKηBiH+λ2η⊤Mη,s.t.H∈Rn×k,H⊤H=Ik,∑p=1mηp=1,ηp≥0,∀p,where λ is a trade-off parameter to balance the loss of clustering problem and the regularization term on kernel weights. The regularization term has many types, such as KL divergence and Hilbert–Schmidt independent criterion.In our proposed algorithm, we setMpq=TrKpKq for each element in M to measure the correlation between Kp and Kq. Choosing this method makes the calculation not too complicated and adopts the Hilbert–Schmidt independent criterion in disguise, which can reflect the correlation between different base kernels to a certain extent.The incorporation ofηTMη use of the basic kernel better, thus improving clustering performance. Moreover, we can clearly see that if we set λ=0, equation (7) is a special case of LI-SimpleMKKM.Li et al. [22] use η⊤Miη instead of η⊤Mη as a regular term, where Mi means a matrix with Mpqi=TrKpiKqi, Kηi=Ni⊤KηNi. Although this method shows excellent performance, we find that the induced regularization of matrices should be global rather than local because the kernel alignment should be for the global kernel matrix. It can also be found from the experimental results in Table 1 that the global kernel-induced regularization has a better effect.Table 1
Comparation of localizedM and global M in ACC.
DatasetsLocalizedMGlobalMFlower1751.8 ± 1.061.3 ± 1.5Flower10237.4 ± 0.844.0 ± 1.0ProteinFold36.4 ± 1.539.0 ± 1.4Digital83.4 ± 1.294.9 ± 3.0Cal-25views36.6 ± 0.737.3 ± 1.1Cal-7classes47.8 ± 1.049.8 ± 0.8


## 3.2. Alternate Optimization

We design a two-step alternating optimization to solve the formula in (7).(i)
OptimizingH by η is fixed: fixed η, the optimization value with respect to H in (7) is represented as follows:(8)maxH∈Rn×kTrH⊤∑i=1nBiKηBiHs.t.H⊤H=Ik.Treating the summationBiKηBi as a whole, (8) can be solved by solving for the eigenvalues of the matrix.(ii)
Optimizingη by H is fixed: fixed H, the optimization value with respect to η in (7) can be represented as follows:(9)Jη=maxηTrH⊤∑i=1nBiKηBiH.+λ2ηTMηs.t.H⊤H=.We first prove the differentiability of (9), then calculate the gradient, and optimize η by the gradient descent method. The first part of the objective function in (9) is as follows:(10)TrH⊤∑i=1nBiKηBiH.With the hyperparameterτ defined, we can regard BiKηBi as a whole, which is global kernel alignment and PSD [21]. For convenience, we let BiKηBi=Tηi.Thus, the function in (9) can be represented as follows:(11)minη∈∆Jη,with(12)Jη=maxHTrH⊤TηiH+λ2η⊤Mηs.t.H∈Rn×k,H⊤H=Ik.Theorem 1.
Jη in (12) is differentiable. ∂Jη/∂ηp=2ηpTrH∗⊤TpiH∗+λ∑q=1mηqMpq,
whereH∗=argmaxHTrH⊤TηiHs.t.H⊤H=Ik.Proof.
For any givenη∈∆, the maximum of optimization problem TrH⊤KηHs.t.H⊤H=Ik is unique [21], with H∗˜∈H∗˜H∗˜=H∗U,UU⊤=U⊤U=Ik the corresponding maximizer. According to theorem in [23], the former part of Jη is differentiable. By defining other elements in η except for p as s and the latter part of the Jη as J2η, the differential of J2η=λ/2η⊤Mη can be expressed as follows:(13)J2η=λ2ηpηsMppMpsMpsMssηpηs=λ2ηp2Mpp+2ηpηsMps+ηs2Mss,∂J2η∂ηp=ληpMpp+ληsMps,where p means one of the components of η and s means all of the other components so that ∂J2η/∂ηp=λ∑q=1mηqMpq, and the whole Jη in (12) is differentiable.
We can solve this problem by designing a gradient descent method. After obtaining the gradient ofJη under the premise of satisfying the equality constraints ∑p=1mηp=1 and nonnegativity constraints ηp≥0 of η, we update η by gradient descent [23]. To implement this method, we let ηu become a nonzero unit in η and ∇Jη indicates the reduced gradient of Jη. The pth 1≤p≤m element of ∇Jη is presented as follows:(14)∇Jηp=∂Jη∂ηp−∂Jη∂ηu∀p≠u,and(15)∇Jηu=−∑p=1,p≠um∇Jηp.
To improve numerical stability, we chooseu as the largest unit in the vector η. The nonnegativity constraint of η also needs to be considered during gradient descent.
To minimizeJη, we define −∇Jη as a descent direction. However, if there is an index p corresponding to ηp=0, with ∇Jηp≥0, the situation of ηp<0 may occur when the gradient is updated, violating the nonnegativity constraint. Under these circumstances, the descent direction for that unit p is set as zero. This makes η when the gradient is updated as follows:(16)dp=0,ifηp=0and∇Jηp≥0,−∇Jηp,ifηp≥0andp≠u,−∇Jηu,forp=u.
The gradient update adopts the formulaη←η+γd, where γ is the step size. We determine the step size γ by a one-dimensional linear search method, rather than setting it directly, and in order to ensure global convergence, this method has appropriate stopping criteria, for example, Armijo’s rule [21].The specific calculation steps of the algorithm in equation (13) are detailed in Algorithm 1.Algorithm 1: LI-SimpleMKKM-MR.
Input: Kpp=1m, k, λ, τ, ϵ, and t(1)
Initializationη0=1/m and t = 1.(2)
CalculateBii=1n by Bi=NiNi⊤ for pth samples 1≤p≤m according to the average kernel.(3)
Tpi=∑i=1nBi(4)
repeat(5)
UpdateH by solving the first k eigenvalues with Tηi.(6)
Compute∂Jη/∂ηp1≤p≤m and the direction of descent of the gradient dt in (16).(7)
Updateηt+1←ηt+γdt.(8)
t←t+1.(9)
Untilmaxηt+1−ηt≤ϵTheorem 2.
The proposed algorithm is converged.Proof.
Note that for thekth iteration, TrH⊤TηiH will be bigger than k + 1th iteration. In each iteration, the gradient of ηp is smaller than 0 by equation (14) because u is the component of η, and in order to get the maximum of TrH⊤TηiH, TrηuH⊤TuiH should be larger than other parts, so the differential of it is bigger than others. The component u has the gradient which is the opposite number of other component gradients’ sum by the equation (15). According to the equation (16), the component of p will be bigger, while the coefficient of u will be smaller, and we can let ∆ as the difference of the kth iteration and k + 1th’s, with ∆=Trγd1H⊤T1iH+Trγd2H⊤T2iH+…+TrγdmH⊤TmiH, ∑p=1,p≠umdp with H⊤TuiH as the largest part of each H⊤TiH, γ is bigger than 0, it can be easy to get the conclusion ∆ is smaller than 0, because the non-negativity of ηand kernel matrix, the former term has the lower bound 0 and convex, so the former term’s convergence is been proofed.As for the latter termλ/2η⊤Mη with the similar thought, it is also decreasing monotonically because M is a PSD matrix, η is not negative, and λ is bigger than 0; the second derivative of J2η can be easy to be calculated bigger than 0 (since each element of M is bigger than 0), so the latter term has the lower bound 0 and convex. At the same time, the whole equation (13) is monotonically decreasing and lower-bounded.


## 3.3. Computational Complexity Analysis

We theoretically analyze the time complexity of the algorithm LI-SimpleMKKM-MR. We assume thatn and m denote the number of samples and the number of base kernels. LI-SimpleMKKM-MR based on Algorithm 1 first computes a neighborhood mask matrix with computational complexity On2log2n and then computes the regularization term with computational complexity Om3. Therefore, the time complexity of LI-SimpleMKKM-MR is n3+n2log2n+m3 per iteration.Let us compare the complexity of LI-SimpleMKKM-MR and LI-SimpleMKKM. Since in most cases, the number of base kernels is much fewer than the number of samplesm≪n, compared with LI-SimpleMKKM n3, the time complexity of the proposed method does not increase significantly.


## 4. Experiments

### 4.1. Datasets

In this section, we evaluate the clustering performance of our algorithm on a set of standard MKKM benchmark datasets, including Oxford Flower17(FLO17), Flower102(FLO102) (https://www.robots.ox.ac.uk/~+vgg/data/flowers/), Protein Fold Prediction(proteinFold) (https://mkl.ucsd.edu/dataset/protein-fold-prediction/), Digital (https://ss.sysu.edu.cn/~+py/), Caltech101-25views(Cal-25views), and Caltech101-7classes(Cal-7classes) (https://files.is.tue.mpg.de/pgehler/projects/iccv09/). Caltech101-25views refers to the number of kernels randomly selected by 25, and Caltech101-7classes refers to the number of classes randomly selected by 7. The details of these can be found in Table 2. We can compare the performance of the different MKKM algorithms using these datasets.Table 2
Specification of our 6 benchmark datasets.
Datasets#Samples#Kernels#ClassesFlower171360717Flower10281894102ProteinFold6941227Digital2000310Cal-25views153025102Cal-7classes147467


### 4.2. Compared Algorithms

In addition to the localized SimpleMKKM with matrix-induced regularization, we tested nine other comparative algorithms from the other MKKM algorithms, including, average kernel k-means (Avg-KKM), multiple kernel k-means (MKKM) [10], localized multiple kernel k-mean (LMKKM) [12], optimal neighborhood kernel clustering (ONKC) [24], multiple kernel k-mean with matrix-induced regularization (MKKM-MR) [14], multiple kernel clustering with local alignment maximization (LKAM) [22], multiview clustering via late fusion alignment maximization (LF-MVC) [25], simple multiple kernel k-means (SimpleMKKM) [20], and localized SimpleMKKM (LI-SimpleMKKM) [21].The implementations of the comparison algorithms are publicly available in the corresponding papers, and we directly apply them to our experiments without tuning. Among the previous algorithms, ONKC, MKKM-MR, LKAM, LF-MVC, and LI-SimpleMKKM need to adjust hyperparameters. Based on the published papers and actual experimental results, we show the best clustering results of the previous methods by tuning the hyperparameters on each dataset.


### 4.3. Experimental Settings

In all experiments, to reduce the difference between different views, all the base kernels are first centered and then scaled so that for alli and p, we have Kpxi,xi=1. For our proposed algorithm, its trade-off parameters λ and τ are chosen from 2−15,2−13,…,210 and 0.05,0.1,…,0.95×n by grid search, where n is the number of samples.For all the datasets, we set the number of clustersk according to the actual number of categories in the dataset. We engage 4 indicators: clustering accuracy (ACC), normalized mutual information (NMI), purity, and rand index to measure the effect of clustering. To reduce the harmful effects of randomness, we initialized and executed all algorithms fifty times (50×) to obtain the mean and variance of the experimental indicators.


### 4.4. Experimental Results

Table3 reports the ACC, NMI, purity, and rand index of the previously mentioned algorithms on all 6 datasets. The following observations were made based on the results:Table 3
ACC, NMI, purity, and Rand index data of localized-SimpleMKKM-matrix-induced regularization with nine comparison methods on six benchmark datasets.
DatasetAVG-KKMMKKM [10]LMKKM [12]ONKC [24]MKKM-MR [14]LKAM [22]LF-MVC [25]SimpleMKKM [20]LI-SimpleMKKM [21]ProposedACC (%)FLO1751.3 ± 1.443.6 ± 1.742.7 ± 1.743.4 ± 2.057.7 ± 1.248.9 ± 0.956.7 ± 1.559.4 ± 1.559.1 ± 1.161.3 ± 1.5FLO10227.1 ± 0.822.4 ± 0.8—39.5 ± 0.740.2 ± 0.941.4 ± 0.838.4 ± 1.242.5 ± 0.844.0 ± 1.044.1 ± 1.0PFold29.1 ± 1.427.1 ± 1.022.4 ± 0.735.4 ± 1.534.3 ± 1.634.2 ± 1.633.3 ± 2.034.4 ± 1.935.9 ± 1.539.0 ± 1.4DIGIT88.8 ± 0.147.2 ± 0.647.2 ± 0.789.5 ± 0.187.4 ± 0.195.0 ± 0.389.2 ± 0.190.3 ± 0.194.6 ± 0.194.9 ± 3.0Cal-2534.2 ± 1.032.8 ± 0.122.6 ± 0.734.3 ± 1.234.0 ± 1.237.2 ± 1.134.6 ± 1.136.2 ± 1.236.7 ± 0.937.3 ± 1.1Cal-733.7 ± 0.133.3 ± 0.234.4 ± 0.146.0 ± 4.043.5 ± 3.949.4 ± 1.042.3 ± 2.739.4 ± 1.546.4 ± 0.949.8 ± 0.8NMI (%)FLO1749.9 ± 0.944.3 ± 1.343.8 ± 1.142.9 ± 1.356.1 ± 0.748.1 ± 0.654.6 ± 1.057.6 ± 0.157.7 ± 0.558.9 ± 1.0FLO10246.0 ± 0.542.7 ± 0.2—56.1 ± 0.456.7 ± 0.556.9 ± 0.354.9 ± 0.458.6 ± 0.560.0 ± 0.460.1 ± 0.4PFold40.3 ± 1.238.1 ± 0.634.8 ± 0.644.1 ± 0.843.2 ± 1.143.7 ± 1.042.3 ± 1.244.2 ± 1.245.2 ± 1.348.0 ± 0.9DIGIT80.7 ± 0.248.7 ± 0.748.3 ± 0.281.7 ± 0.179.5 ± 0.189.4 ± 0.181.2 ± 0.283.3 ± 0.190.0 ± 0.190.3 ± 1.6Cal-2559.7 ± 0.558.6 ± 0.551.9 ± 0.359.6 ± 0.859.3 ± 0.562.0 ± 0.659.5 ± 0.760.7 ± 0.561.4 ± 0.461.5 ± 0.5Cal-734.9 ± 0.330.0 ± 0.330.7 ± 0.140.0 ± 1.043.1 ± 0.843.3 ± 0.240.0 ± 0.340.5 ± 0.439.2 ± 1.344.9 ± 0.1Purity (%)FLO1752.3 ± 1.245.1 ± 1.444.6 ± 1.545.1 ± 1.859.2 ± 1.150.1 ± 0.657.5 ± 1.660.5 ± 1.359.7 ± 0.362.7 ± 1.6FLO10232.3 ± 0.627.8 ± 0.4—45.6 ± 0.746.3 ± 0.848.0 ± 0.644.6 ± 0.848.6 ± 0.750.3 ± 0.750.5 ± 0.7PFold37.3 ± 1.633.7 ± 0.931.1 ± 1.042.0 ± 1.241.2 ± 1.441.6 ± 1.340.6 ± 1.641.4 ± 1.642.5 ± 1.646.2 ± 1.5DIGIT88.8 ± 0.150.1 ± 0.750.2 ± 0.389.5 ± 0.187.4 ± 0.195.0 ± 0.389.2 ± 0.190.3 ± 0.194.6 ± 0.194.9 ± 2.0Cal-2536.2 ± 1.034.9 ± 0.124.4 ± 0.636.6 ± 1.136.1 ± 1.039.4 ± 1.136.8 ± 1.038.2 ± 1.139.1 ± 0.839.3 ± 1.1Cal-779.0 ± 0.276.7 ± 0.274.9 ± 0.181.2 ± 0.982.9 ± 0.483.2 ± 0.281.6 ± 0.383.3 ± 0.380.8 ± 0.783.4 ± 0.1Rand Index (%)FLO1732.2 ± 1.326.3 ± 1.320.6 ± 1.135.2 ± 1.539.9 ± 1.331.6 ± 0.844.1 ± 0.441.5 ± 1.140.9 ± 0.842.6 ± 1.4FLO10215.5 ± 0.512.1 ± 0.5—24.9 ± 0.525.5 ± 0.627.2 ± 0.625.5 ± 1.028.5 ± 0.829.9 ± 0.830.0 ± 0.8PFold14.4 ± 1.812.1 ± 0.77.8 ± 0.418.0 ± 1.117.2 ± 1.520.1 ± 1.116.5 ± 2.017.6 ± 1.919.8 ± 1.220.8 ± 1.5DIGIT77.4 ± 0.231.4 ± 0.631.3 ± 0.281.7 ± 0.381.3 ± 0.190.8 ± 2.378.0 ± 0.180.6 ± 0.288.2 ± 0.188.3 ± 2.9Cal-2518.5 ± 0.917.3 ± 0.18.3 ± 0.618.6 ± 1.218.4 ± 0.821.5 ± 1.018.9 ± 0.920.4 ± 0.120.1 ± 0.721.1 ± 0.8Cal-726.5 ± 0.323.5 ± 0.320.3 ± 0.130.9 ± 1.731.5 ± 2.236.6 ± 0.529.3 ± 0.830.3 ± 0.732.2 ± 1.337.1 ± 0.3Bold indicates better results in comparison with other algorithms.The proposed localized SimpleMKKM with matrix-induced regularization significantly outperforms localized SimpleMKKM. For example, it outperforms the LI-SimpleMKKM algorithm by 1.8%, 0.1%, 3.1%, 0.3%, 0.6%, and 3.4% in terms of ACC on Flower17, Flower102, ProteinFold, DIGIT, Caltech-25 views, and Caltech-7 classes datasets. These results validate the effectiveness of enhancing the correlation between matrices.Also, our proposed LI-SimpleMKKM-MR significantly outperforms the MKKM-MR algorithms by 3.6%, 3.8%, 4.7%, 7.5%, 3.3%, and 6.3% in terms of ACC on Flower17, Flower102, ProteinFold, DIGIT, Caltech-25 views, and Caltech-7 classes datasets. This result proves that utilizing the data’s local structure andminη−maxH optimization improves the clustering effect very well.The proposed algorithm adopts the advanced formulation and uses matrix-induced regularization to improve the correlation between kernel matrices, reducing redundancy and increasing the diversity of selected kernel matrices, making it superior to its counterpart.Together, these factors make LI-SimpleMKKM-MR significantly improved over other algorithms on the same dataset. In addition, due to time complexity and memory constraints, the effect of LMKKM on some datasets has not been shown.


### 4.5. Parameter Sensitivity of LI-SimpleMKKM-MR

We designed comparative experiments to study the influence of the setting of two hyperparameters, localized alignment, and matrix-induced regularization, on the clustering effect. According to equation (7), LI-SimpleMKKM-MR tunes the clustering performance by setting two hyperparameters λ and τ, referring to the regularization balance factor and the nearest neighbor ratio.We experimentally show the difference in clustering performance inλ and τ in all benchmark datasets.Figure1 shows the ACC and NMI of our algorithm by varying one of τ or λ with the other one fixed. Based on these figures, we can conclude that (1) as the value of τ increases, the ACC and NMI of each dataset increase to their highest value and, correspondingly, decrease when τ decreases and (2) by keeping the τ unchanged, the ACC and NMI will exceed SimpleMKKM and be steady when λ is small.Figure 1
Sensitivity of the proposed method LI-SimpleMKKM-MR with a variation ofλ and τ compared with SimpleMKKM.Hence, we conclude that our proposed algorithm presents a new state-of-the-art performance for clustering compared to other algorithms that only preserve the global kernel, such as LI-MKKM. Thus, it focuses on preserving the local structure of the data as specific results are displayed in Table1.On top ofminη−maxH optimization, the clustering performance improves when the parameters are appropriately set by combining matrix-induced regularization and local alignment.


### 4.6. Convergence of LI-SimpleMKKM-MR

In addition to theoretical verification, we experimentally verify the convergence of the algorithm. We present simulations of our proposed algorithm using different datasets in Figure2. According to the results, the object value of the proposed algorithm oscillates first, then decreases monotonically, and finally converges in several iterations. Moreover, we know from experiments that most datasets can converge in fewer than 10 iterations. This result is comparable to the state-of-the-art methods.Figure 2
Proposed algorithm convergence illustration on flower17, flower102, ProteinFold, digit, Caltech-25, and Caltech-7 datasets.


### 4.7. Performance of LI-SIMPLEMKKM-MR by Learned H

We calculate the 4 clustering metrics at each iteration to show the variety of clustering performance variations of the learnedH in different datasets and plot them in Figure 3. As observed, the clustering performance increased firstly with iterations and remained stable after oscillation.Figure 3
Clustering performance ofH iteratively in LI-SimpleMKKM-MR learning on flower17, flower102, ProteinFold, digit, Caltech-25, and Caltech-7 datasets.


### 4.8. Running Time of LI-SimpleMKKM-MR

We report the running time comparison of all the baseline algorithms and LI-SimpleMKKM-MR on different datasets in Figure4. With the analysis of the time complexity in Section 3.3 and the experiment result from Figure 4, even though there are additional computational steps, we found that LI-SimpleMKKM-MR does not significantly increase in computation time.Figure 4
Running time comparison of different algorithms on all benchmark datasets (base 2 logarithm in seconds). The experimental environment is a desktop with Ubuntu 20.0 OS, Intel Core-i7-9700K cpu @ 3.60 GHz, 94.2 G RAM.


## 4.1. Datasets

In this section, we evaluate the clustering performance of our algorithm on a set of standard MKKM benchmark datasets, including Oxford Flower17(FLO17), Flower102(FLO102) (https://www.robots.ox.ac.uk/~+vgg/data/flowers/), Protein Fold Prediction(proteinFold) (https://mkl.ucsd.edu/dataset/protein-fold-prediction/), Digital (https://ss.sysu.edu.cn/~+py/), Caltech101-25views(Cal-25views), and Caltech101-7classes(Cal-7classes) (https://files.is.tue.mpg.de/pgehler/projects/iccv09/). Caltech101-25views refers to the number of kernels randomly selected by 25, and Caltech101-7classes refers to the number of classes randomly selected by 7. The details of these can be found in Table 2. We can compare the performance of the different MKKM algorithms using these datasets.Table 2
Specification of our 6 benchmark datasets.
Datasets#Samples#Kernels#ClassesFlower171360717Flower10281894102ProteinFold6941227Digital2000310Cal-25views153025102Cal-7classes147467


## 4.2. Compared Algorithms

In addition to the localized SimpleMKKM with matrix-induced regularization, we tested nine other comparative algorithms from the other MKKM algorithms, including, average kernel k-means (Avg-KKM), multiple kernel k-means (MKKM) [10], localized multiple kernel k-mean (LMKKM) [12], optimal neighborhood kernel clustering (ONKC) [24], multiple kernel k-mean with matrix-induced regularization (MKKM-MR) [14], multiple kernel clustering with local alignment maximization (LKAM) [22], multiview clustering via late fusion alignment maximization (LF-MVC) [25], simple multiple kernel k-means (SimpleMKKM) [20], and localized SimpleMKKM (LI-SimpleMKKM) [21].The implementations of the comparison algorithms are publicly available in the corresponding papers, and we directly apply them to our experiments without tuning. Among the previous algorithms, ONKC, MKKM-MR, LKAM, LF-MVC, and LI-SimpleMKKM need to adjust hyperparameters. Based on the published papers and actual experimental results, we show the best clustering results of the previous methods by tuning the hyperparameters on each dataset.


## 4.3. Experimental Settings

In all experiments, to reduce the difference between different views, all the base kernels are first centered and then scaled so that for alli and p, we have Kpxi,xi=1. For our proposed algorithm, its trade-off parameters λ and τ are chosen from 2−15,2−13,…,210 and 0.05,0.1,…,0.95×n by grid search, where n is the number of samples.For all the datasets, we set the number of clustersk according to the actual number of categories in the dataset. We engage 4 indicators: clustering accuracy (ACC), normalized mutual information (NMI), purity, and rand index to measure the effect of clustering. To reduce the harmful effects of randomness, we initialized and executed all algorithms fifty times (50×) to obtain the mean and variance of the experimental indicators.


## 4.4. Experimental Results

Table3 reports the ACC, NMI, purity, and rand index of the previously mentioned algorithms on all 6 datasets. The following observations were made based on the results:Table 3
ACC, NMI, purity, and Rand index data of localized-SimpleMKKM-matrix-induced regularization with nine comparison methods on six benchmark datasets.
DatasetAVG-KKMMKKM [10]LMKKM [12]ONKC [24]MKKM-MR [14]LKAM [22]LF-MVC [25]SimpleMKKM [20]LI-SimpleMKKM [21]ProposedACC (%)FLO1751.3 ± 1.443.6 ± 1.742.7 ± 1.743.4 ± 2.057.7 ± 1.248.9 ± 0.956.7 ± 1.559.4 ± 1.559.1 ± 1.161.3 ± 1.5FLO10227.1 ± 0.822.4 ± 0.8—39.5 ± 0.740.2 ± 0.941.4 ± 0.838.4 ± 1.242.5 ± 0.844.0 ± 1.044.1 ± 1.0PFold29.1 ± 1.427.1 ± 1.022.4 ± 0.735.4 ± 1.534.3 ± 1.634.2 ± 1.633.3 ± 2.034.4 ± 1.935.9 ± 1.539.0 ± 1.4DIGIT88.8 ± 0.147.2 ± 0.647.2 ± 0.789.5 ± 0.187.4 ± 0.195.0 ± 0.389.2 ± 0.190.3 ± 0.194.6 ± 0.194.9 ± 3.0Cal-2534.2 ± 1.032.8 ± 0.122.6 ± 0.734.3 ± 1.234.0 ± 1.237.2 ± 1.134.6 ± 1.136.2 ± 1.236.7 ± 0.937.3 ± 1.1Cal-733.7 ± 0.133.3 ± 0.234.4 ± 0.146.0 ± 4.043.5 ± 3.949.4 ± 1.042.3 ± 2.739.4 ± 1.546.4 ± 0.949.8 ± 0.8NMI (%)FLO1749.9 ± 0.944.3 ± 1.343.8 ± 1.142.9 ± 1.356.1 ± 0.748.1 ± 0.654.6 ± 1.057.6 ± 0.157.7 ± 0.558.9 ± 1.0FLO10246.0 ± 0.542.7 ± 0.2—56.1 ± 0.456.7 ± 0.556.9 ± 0.354.9 ± 0.458.6 ± 0.560.0 ± 0.460.1 ± 0.4PFold40.3 ± 1.238.1 ± 0.634.8 ± 0.644.1 ± 0.843.2 ± 1.143.7 ± 1.042.3 ± 1.244.2 ± 1.245.2 ± 1.348.0 ± 0.9DIGIT80.7 ± 0.248.7 ± 0.748.3 ± 0.281.7 ± 0.179.5 ± 0.189.4 ± 0.181.2 ± 0.283.3 ± 0.190.0 ± 0.190.3 ± 1.6Cal-2559.7 ± 0.558.6 ± 0.551.9 ± 0.359.6 ± 0.859.3 ± 0.562.0 ± 0.659.5 ± 0.760.7 ± 0.561.4 ± 0.461.5 ± 0.5Cal-734.9 ± 0.330.0 ± 0.330.7 ± 0.140.0 ± 1.043.1 ± 0.843.3 ± 0.240.0 ± 0.340.5 ± 0.439.2 ± 1.344.9 ± 0.1Purity (%)FLO1752.3 ± 1.245.1 ± 1.444.6 ± 1.545.1 ± 1.859.2 ± 1.150.1 ± 0.657.5 ± 1.660.5 ± 1.359.7 ± 0.362.7 ± 1.6FLO10232.3 ± 0.627.8 ± 0.4—45.6 ± 0.746.3 ± 0.848.0 ± 0.644.6 ± 0.848.6 ± 0.750.3 ± 0.750.5 ± 0.7PFold37.3 ± 1.633.7 ± 0.931.1 ± 1.042.0 ± 1.241.2 ± 1.441.6 ± 1.340.6 ± 1.641.4 ± 1.642.5 ± 1.646.2 ± 1.5DIGIT88.8 ± 0.150.1 ± 0.750.2 ± 0.389.5 ± 0.187.4 ± 0.195.0 ± 0.389.2 ± 0.190.3 ± 0.194.6 ± 0.194.9 ± 2.0Cal-2536.2 ± 1.034.9 ± 0.124.4 ± 0.636.6 ± 1.136.1 ± 1.039.4 ± 1.136.8 ± 1.038.2 ± 1.139.1 ± 0.839.3 ± 1.1Cal-779.0 ± 0.276.7 ± 0.274.9 ± 0.181.2 ± 0.982.9 ± 0.483.2 ± 0.281.6 ± 0.383.3 ± 0.380.8 ± 0.783.4 ± 0.1Rand Index (%)FLO1732.2 ± 1.326.3 ± 1.320.6 ± 1.135.2 ± 1.539.9 ± 1.331.6 ± 0.844.1 ± 0.441.5 ± 1.140.9 ± 0.842.6 ± 1.4FLO10215.5 ± 0.512.1 ± 0.5—24.9 ± 0.525.5 ± 0.627.2 ± 0.625.5 ± 1.028.5 ± 0.829.9 ± 0.830.0 ± 0.8PFold14.4 ± 1.812.1 ± 0.77.8 ± 0.418.0 ± 1.117.2 ± 1.520.1 ± 1.116.5 ± 2.017.6 ± 1.919.8 ± 1.220.8 ± 1.5DIGIT77.4 ± 0.231.4 ± 0.631.3 ± 0.281.7 ± 0.381.3 ± 0.190.8 ± 2.378.0 ± 0.180.6 ± 0.288.2 ± 0.188.3 ± 2.9Cal-2518.5 ± 0.917.3 ± 0.18.3 ± 0.618.6 ± 1.218.4 ± 0.821.5 ± 1.018.9 ± 0.920.4 ± 0.120.1 ± 0.721.1 ± 0.8Cal-726.5 ± 0.323.5 ± 0.320.3 ± 0.130.9 ± 1.731.5 ± 2.236.6 ± 0.529.3 ± 0.830.3 ± 0.732.2 ± 1.337.1 ± 0.3Bold indicates better results in comparison with other algorithms.The proposed localized SimpleMKKM with matrix-induced regularization significantly outperforms localized SimpleMKKM. For example, it outperforms the LI-SimpleMKKM algorithm by 1.8%, 0.1%, 3.1%, 0.3%, 0.6%, and 3.4% in terms of ACC on Flower17, Flower102, ProteinFold, DIGIT, Caltech-25 views, and Caltech-7 classes datasets. These results validate the effectiveness of enhancing the correlation between matrices.Also, our proposed LI-SimpleMKKM-MR significantly outperforms the MKKM-MR algorithms by 3.6%, 3.8%, 4.7%, 7.5%, 3.3%, and 6.3% in terms of ACC on Flower17, Flower102, ProteinFold, DIGIT, Caltech-25 views, and Caltech-7 classes datasets. This result proves that utilizing the data’s local structure andminη−maxH optimization improves the clustering effect very well.The proposed algorithm adopts the advanced formulation and uses matrix-induced regularization to improve the correlation between kernel matrices, reducing redundancy and increasing the diversity of selected kernel matrices, making it superior to its counterpart.Together, these factors make LI-SimpleMKKM-MR significantly improved over other algorithms on the same dataset. In addition, due to time complexity and memory constraints, the effect of LMKKM on some datasets has not been shown.


## 4.5. Parameter Sensitivity of LI-SimpleMKKM-MR

We designed comparative experiments to study the influence of the setting of two hyperparameters, localized alignment, and matrix-induced regularization, on the clustering effect. According to equation (7), LI-SimpleMKKM-MR tunes the clustering performance by setting two hyperparameters λ and τ, referring to the regularization balance factor and the nearest neighbor ratio.We experimentally show the difference in clustering performance inλ and τ in all benchmark datasets.Figure1 shows the ACC and NMI of our algorithm by varying one of τ or λ with the other one fixed. Based on these figures, we can conclude that (1) as the value of τ increases, the ACC and NMI of each dataset increase to their highest value and, correspondingly, decrease when τ decreases and (2) by keeping the τ unchanged, the ACC and NMI will exceed SimpleMKKM and be steady when λ is small.Figure 1
Sensitivity of the proposed method LI-SimpleMKKM-MR with a variation ofλ and τ compared with SimpleMKKM.Hence, we conclude that our proposed algorithm presents a new state-of-the-art performance for clustering compared to other algorithms that only preserve the global kernel, such as LI-MKKM. Thus, it focuses on preserving the local structure of the data as specific results are displayed in Table1.On top ofminη−maxH optimization, the clustering performance improves when the parameters are appropriately set by combining matrix-induced regularization and local alignment.


## 4.6. Convergence of LI-SimpleMKKM-MR

In addition to theoretical verification, we experimentally verify the convergence of the algorithm. We present simulations of our proposed algorithm using different datasets in Figure2. According to the results, the object value of the proposed algorithm oscillates first, then decreases monotonically, and finally converges in several iterations. Moreover, we know from experiments that most datasets can converge in fewer than 10 iterations. This result is comparable to the state-of-the-art methods.Figure 2
Proposed algorithm convergence illustration on flower17, flower102, ProteinFold, digit, Caltech-25, and Caltech-7 datasets.


## 4.7. Performance of LI-SIMPLEMKKM-MR by Learned H

We calculate the 4 clustering metrics at each iteration to show the variety of clustering performance variations of the learnedH in different datasets and plot them in Figure 3. As observed, the clustering performance increased firstly with iterations and remained stable after oscillation.Figure 3
Clustering performance ofH iteratively in LI-SimpleMKKM-MR learning on flower17, flower102, ProteinFold, digit, Caltech-25, and Caltech-7 datasets.


## 4.8. Running Time of LI-SimpleMKKM-MR

We report the running time comparison of all the baseline algorithms and LI-SimpleMKKM-MR on different datasets in Figure4. With the analysis of the time complexity in Section 3.3 and the experiment result from Figure 4, even though there are additional computational steps, we found that LI-SimpleMKKM-MR does not significantly increase in computation time.Figure 4
Running time comparison of different algorithms on all benchmark datasets (base 2 logarithm in seconds). The experimental environment is a desktop with Ubuntu 20.0 OS, Intel Core-i7-9700K cpu @ 3.60 GHz, 94.2 G RAM.


## 5. Conclusion

Although LI-SimpleMKKM can address the task of multiple kernel k-means in aminη−maxH optimization and realize the local alignment, it does not sufficiently account for the correlation between the basis kernels. This work proposes an LI-SimpleMKKM-MR algorithm that combines the sample localized alignment and matrix-induced regularization to solve this problem. Theoretically and experimentally, our method has demonstrated the best performance in clustering optimization and outperforms existing algorithms. In further research, we will apply this algorithm to incomplete MKKM problems.



---

*Source: 6654304-2023-03-17.xml*