Face image clustering method and system based on localized simple multiple kernel k-means

[0001] This application is the national phase entry of International Application No. PCT/CN2022/112016, filed on Aug. 12, 2022, which is based upon and claims priority to Chinese Patent Application No. 202110940777.6, filed on Aug. 17, 2021, the entire contents of which are incorporated herein by reference.

[0002] The present application relates to the technical field of machine learning of face image processing, in particular to a face image clustering method and system based on a localized simple multiple kernel k-means.

[0003] With the widespread application of the face recognition and retrieval system, the face image data in the system has increased sharply, and the face clustering technology has become an important foundation for improving the retrieval efficiency of the system. In face clustering, the face image information in the database is usually clustered into different subclasses, so that the similarity between the subclasses is as small as possible, and the similarity in the subclasses is as large as possible. In this way, during retrieval, only the subclasses with high similarity to the target to be retrieved need to be identified one by one, thus retrieving records with the highest similarity to the target to be retrieved.

[0004] K-means clustering is the most widely used method, and kernel k-means clustering is widely studied because it can learn the nonlinear information of samples. Multiple kernel clustering provides an elegant framework for grouping samples into different categories by extracting complementary information from multiple sources. Through highly efficient and high-quality clustering, the efficiency of data analysis is greatly enhanced and labor costs are saved. By fully considering the relationships between samples, a local kernel alignment variable has been developed. Experiments have proven that this can improve clustering performance. By assuming that an optimal kernel is located in the neighborhood of a combined kernel, an optimal neighborhood multiple kernel clustering algorithm has been provided that improves clustering performance by improving the representability of learned optimal kernels. The algorithm maximally aligns multiple base partitions with consistent partitions, with considerable algorithm acceleration and satisfactory clustering performance. On this basis, an effective algorithm based on late-fusion for processing incomplete multi-view data has been provided.

[0005] As a representative of multi-view clustering, a new simple multiple kernel k-means (SimpleMKKM) has recently been provided. SimpleMKKM does not jointly minimize the kernel weight and the clustering partition matrix, but minimizes the kernel weight and maximizes the clustering partition matrix optimization framework, resulting in a troublesome minimum-maximum optimization. It can then be equivalently converted into a minimization problem, and a reduced gradient algorithm is designed to solve the resulting optimization. This algorithm has proven to be an efficient optimization with robustness to noise perspectives and has attracted a wide range of attention from many researchers.

[0006] Although the recently provided SimpleMKKM has the above-mentioned advantages, it has been observed that it tightly aligns the combined kernel matrix with the “ideal” similarity globally generated by the clustering partition matrix. This can force all sample pairs to align equally with the same ideal similarity indiscriminately. Therefore, it cannot effectively handle the relationships between samples, neglects local structures, and possibly results in unsatisfactory clustering performance.

[0007] The present application aims to address the defects of the prior art by providing a face image clustering method and system based on localized simple multiple kernel k-means.

[0008] In order to achieve the above objective, the present application adopts the following technical solutions:

[0009] Provided is a face image clustering method based on localized simple multiple kernel k-means, including the following steps:

• • [0010] S1, acquiring face images, and preprocessing the acquired face images to obtain an average kernel matrix for each view;
  • [0011] S2, calculating n (τ×n)-nearest neighbor matrices according to the obtained average kernel matrices;
  • [0012] S3, calculating a localized kernel matrix for each view according to the nearest neighbor matrices;
  • [0013] S4, constructing a localized simple multiple kernel k-means clustering objective function according to the calculated localized kernel matrix for each view;
  • [0014] S5, solving a minimum of the constructed objective function by adopting a reduced gradient descent method to obtain an optimal clustering partition matrix; and
  • [0015] S6, performing k-means clustering on the obtained clustering partition matrix to achieve clustering.

[0016] Further, calculating the localized kernel matrix for each view in S3 is expressed as:

[0017] ${\overline{K}}_p=\left(\sum _{i=1}^n{A}^{\left(i\right)}\right)\otimes K_p$

• • [0018] wherein K_p represents the localized kernel matrix of each view; A⁽ⁱ⁾ represents the n (τ×n)-nearest neighbor matrices; K_p represents the p-th given kernel matrix; n represents a number of samples; ⊗ represents the multiplication of elements.

[0019] Further, the simple multiple kernel k-means clustering objective function in S4 is expressed as:

[0020] $\underset{\gamma \in \Delta }{\min }\underset{H\in {ℝ}^{n\times k}}{\max }\mathrm{Tr}\left(K_{\gamma }{\mathrm{HH}}^T\right)$ $s.t.$ $H^{T}H=I_k.$

• • [0021] wherein γ represents a coefficient vector; H represents a partition matrix; H^T represents a permutation of a commutation matrix; K_γ represents a combined kernel matrix of K_p generated by γ; I_k represents a k-order identity matrix.

[0022] Further, the localized simple multiple kernel k-means clustering objective function in S4 is expressed as:

[0023] ${\min }_{\gamma \in \Delta }{\max }_{H\in {ℝ}^{n\times k}}\mathrm{Tr}\left(H^T{\sum }_{i=1}^n\left(A^{\left(i\right)}{K}_{\gamma }{A}^{\left(i\right)}\right)H\right)$ $s.t.$ $H^{T}H=I_k,$

• • [0024] wherein

[0025] $\Delta =\left\{\gamma \in {ℝ}^m❘{\sum }_{p=1}^m{\gamma }_p=1,{\gamma }_p\ge 0,\forall p\right\},$
R^m represents an m-dimensional real number vector space; γ_p represents the p-th component of γ.

[0026] Further, solving the minimum of the constructed objective function in S5 specifically includes: simplifying the localized simple multiple kernel k-means clustering objective function into a simple multiple kernel k-means clustering objective function:

[0027] ${\sum }_{i=1}^n\mathrm{Tr}\left(H^T\left(A^{\left(i\right)}{K}_{\gamma }{A}^{\left(i\right)}\right)H\right)={\sum }_{i=1}^n{\langle A^{\left(i\right)}\otimes K_{\gamma },A^{\left(i\right)}\otimes \left({\mathrm{HH}}^T\right)\rangle }_F={\sum }_{i=1}^n{\langle A^{\left(i\right)}\otimes K_{\gamma },{\mathrm{HH}}^T\rangle }_F={\langle \left({\sum }_{i=1}^n{A}^{\left(i\right)}\right)\otimes K_{\gamma },{\mathrm{HH}}^T\rangle }_F={\sum }_{p=1}^m{\gamma }_p^2{\langle \left({\sum }_{i=1}^n{A}^{\left(i\right)}\right)\otimes K_p,{\mathrm{HH}}^T\rangle }_F={\sum }_{p=1}^m{\gamma }_p^2{\langle {\tilde{K}}_p,{\mathrm{HH}}^T\rangle }_F=\mathrm{Tr}\left(H^T{\tilde{K}}_{\gamma }H\right),$

• • [0028] wherein ⊗ represents the multiplication of elements;

[0029] ${\tilde{K}}_p=\left({\sum }_{i=1}^n{A}^{\left(i\right)}\right)\otimes K_p$
represents a standardized kernel matrix;

• • [0030] when all elements of A⁽ⁱ⁾ are set to 1, the simple multiple kernel k-means clustering objective function is expressed as:

[0031] ${\min }_{\gamma \in \Delta }𝒥\left(\gamma \right)$ $\mathrm{wherein}$ $𝒥\left(\gamma \right)=\left\{\underset{H}{\max }\mathrm{Tr}\left(H^T{\tilde{K}}_{\gamma }H\right),s.t.H^{T}H=I_k.\right\},$
representing an optimum function.

[0032] Further, solving the minimum of the constructed objective function by adopting the reduced gradient descent method in S5 specifically includes:

• • [0033] calculating the objective function by the gradient descent method as:

[0034] ${\left[\nabla 𝒥\left(\gamma \right)\right]}_p=\frac{\partial 𝒥\left(\gamma \right)}{\partial {\gamma }_p}-\frac{\partial 𝒥\left(\gamma \right)}{\partial {\gamma }_u}\forall p\ne u$ ${\left[\nabla 𝒥\left(\gamma \right)\right]}_p={\sum }_{p=1,p\ne u}^m\left(\frac{\partial 𝒥\left(\gamma \right)}{\partial {\gamma }_u}-\frac{\partial 𝒥\left(\gamma \right)}{\partial {\gamma }_p}\right)$ $\mathrm{wherein}$ $\frac{\partial 𝒥\left(\gamma \right)}{\partial {\gamma }_p}=2{\gamma }_p\mathrm{Tr}\left(H^{*T}{\tilde{K}}_p{H}^{*}\right),$ $H^{*}=\left\{\arg {\max }_H\mathrm{Tr}\left(H^T{\tilde{K}}_{\gamma }H\right)s.t.H^{T}H=I_k\right\};$

• • [0035] u is set as a number indicating the largest component of vector γ, and a positive constraint of γ is expressed as:

[0036] $d_p=\{\begin{array}{cc}0& \mathrm{if}{\gamma }_p=0{\mathrm{and}\left[\nabla 𝒥\left(\gamma \right)\right]}_p>0\\ -{\left[\nabla 𝒥\left(\gamma \right)\right]}_p& \mathrm{if}{\gamma }_p>0\mathrm{and}p\ne u\\ -{\left[\nabla 𝒥\left(\gamma \right)\right]}_u& \mathrm{if}p=u\end{array}.$

• • [0037] wherein d_p represents a descending direction.

[0038] Correspondingly, further provided is a face image clustering system based on localized simple multiple kernel k-means, including:

• • [0039] an acquisition module, configured for acquiring face images and preprocessing the acquired face images to obtain an average kernel matrix for each view;
  • [0040] a first calculation module, configured for calculating n (τ×n)-nearest neighbor matrices according to the obtained average kernel matrices;
  • [0041] a second calculation module, configured for calculating a localized kernel matrix for each view according to the nearest neighbor matrices;
  • [0042] a construction module, configured for constructing a localized simple multiple kernel k-means clustering objective function according to the calculated localized kernel matrix for each view;
  • [0043] a solving module, configured for solving a minimum of the constructed objective function by adopting a reduced gradient descent method to obtain an optimal clustering partition matrix; and
  • [0044] a clustering module, configured for performing k-means clustering on the obtained clustering partition matrix to achieve clustering.

[0045] Further, calculating the localized kernel matrix for each view in the second calculation module is expressed as:

[0046] ${\overline{K}}_p=\left(\sum _{i=1}^n{A}^{\left(i\right)}\right)\otimes K_p$

• • [0047] wherein K_p represents the localized kernel matrix of each view; A⁽ⁱ⁾ represents the n (τ×n)-nearest neighbor matrices; K_p represents the p-th given kernel matrix; n represents a number of samples; ⊗ represents the multiplication of elements.

[0048] Further, the simple multiple kernel k-means clustering objective function in the construction module is expressed as:

[0049] $\underset{\gamma \in \Delta }{\min }\underset{H\in {ℝ}^{n\times k}}{\max }\mathrm{Tr}\left(K_{\gamma }{\mathrm{HH}}^T\right)$ $s.t.$ $H^{T}H=I_k.$

• • [0050] wherein γ represents a coefficient vector; H represents a partition matrix; H^T represents a permutation of a commutation matrix; K_γ represents a combined kernel matrix of K_p generated by γ; I_k represents a k-order identity matrix.

[0051] Further, the localized simple multiple kernel k-means clustering objective function in the construction module is expressed as:

[0052] ${\min }_{\gamma \in \Delta }{\max }_{H\in {ℝ}^{n\times k}}\mathrm{Tr}\left(H^T{\sum }_{i=1}^n\left(A^{\left(i\right)}{K}_{\gamma }{A}^{\left(i\right)}\right)H\right)$ $s.t.$ $H^{T}H=I_k,$ $\mathrm{wherein}$ $\Delta =\left\{\gamma \in {ℝ}^m❘{\sum }_{p=1}^m{\gamma }_p=1,{\gamma }_p\ge 0,\forall p\right\},$
R^m represents an m-dimensional real number vector space; γ_p represents the p-th component of γ.

[0053] Compared with the prior art, the present application provides a novel localized simple multiple kernel k-means clustering machine learning method, which includes modules of localized kernel alignment, objective function optimization to obtain an optimal combination coefficient γ, a corresponding partition matrix H, and the like. In the present application, through the optimization of the objective function, the optimized kernel combination can represent the information of a single view, and can better serve the view fusion, so that the purpose of improving the clustering effect is achieved. Moreover, the present application performs localization processing on each view to strengthen local information. Multiple kernel k-means with min-max learning (MKKM-MM) was the first attempt to improve MKKM through min-max learning, which indeed improves MKKM, but has a limited effect. The performance of the provided localized SimpleMKKM significantly surpasses that of MKKM-MM. This once again proves the advantages of the formula and the associated optimization strategy of the present application. The localized SimpleMKKM consistently and significantly outperforms SimpleMKKM.

[0061] The embodiments of the present application are illustrated below through specific examples, and other advantages and effects of the present application can be easily understood by those skilled in the art based on the contents disclosed herein. The present application can also be implemented or applied through other different specific embodiments. Various modifications or changes to the details in the description can be made based on different perspectives and applications without departing from the spirit of the present application. It should be noted that, unless conflicting, the embodiments and features of the embodiments below may be combined with each other.

[0062] The present application aims to address the defects of the prior art by providing a face image clustering method and system based on localized simple multiple kernel k-means.

[0063] The embodiment provides a face image clustering method based on localized simple multiple kernel k-means, as shown in FIG. 1, including the following steps:

• • [0064] S1, acquiring face images, and preprocessing the acquired face images to obtain an average kernel matrix for each view;
  • [0065] S2, calculating n (TX n)-nearest neighbor matrices according to the obtained average kernel matrices;
  • [0066] S3, calculating a localized kernel matrix for each view according to the nearest neighbor matrices;
  • [0067] S4, constructing a localized simple multiple kernel k-means clustering objective function according to the calculated localized kernel matrix for each view;
  • [0068] S5, solving a minimum of the constructed objective function by adopting a reduced gradient descent method to obtain an optimal clustering partition matrix; and
  • [0069] S6, performing k-means clustering on the obtained clustering partition matrix to achieve clustering.

[0070] The kernel k-means clustering process is as follows:

[0071] ${\left\{x_i\right\}}_{i=1}^n\subseteq X$
is set as a dataset consisting of n samples, and φ(·):x ∈ χ → represents a feature mapping that projects sample x into a reproducing kernel Hilbert space . The target of kernel k-means clustering is to minimize the sum of squared errors based on the partition matrix B ∈ {0,1}^n×k, as shown in the following formula:

[0072] $\underset{Z\in {\left\{0,1\right\}}^{n\times k}}{\min }\sum _{i=1,c=1}^{n,k}{B}_{ic}{\varphi \left(x_i\right)-{\mu }_c}_2^2$ $s.t.$ $\sum _{c=1}^k{B}_{ic}=1,$ $\mathrm{wherein}$ ${\mu }_c=\left(1/n_c\right){\sum }_{i=1}^n{B}_{ic}\varphi \left(x_i\right),$
and

[0073] $n_c={\sum }_{i=1}^n{B}_{\mathrm{ic}}$
represents the number of samples belonging to the c-th cluster (1≤c≤k). The above formula can be reformulated as:

[0074] $\underset{Z\in {\left\{0,1\right\}}^{n\times k}}{\min }\mathrm{Tr}\left(K\right)-\mathrm{Tr}\left(L^{\frac{1}{2}}{B}^{T}KB{L}^{\frac{1}{2}}\right)$ $s.t.$ $B{1}_k=1_n,$

• • [0075] wherein K is a kernel matrix with elements

[0076] $K_{\mathrm{ij}}={\varphi \left(x_i\right)}^T\varphi \left(x_j\right),L=\mathrm{diag}\left(\left[n_1^{-1},\dots ,n_k^{-1}\right]\right),$
and 1_s ∈ ^s represents a vector in which all elements are 1.

[0077] Since variable B in the above formula is discrete, optimization is difficult,

[0078] $H=B{L}^{\frac{1}{2}}$
is set, and the discrete constraint is converted into a real-value orthogonal constraint, i.e., H^TH=I_k. The target formula may be converted into:

[0079] $\underset{H^{T}H=I_k}{\min }\mathrm{Tr}\left(K\left(I_n-{\mathrm{HH}}^T\right)\right),$

• • [0080] the closed-form solution thereof is given by the eigenvectors corresponding to the k maximum eigenvalues of the kernel matrix K_p which can be obtained by eigendecomposition of K.

[0081] In S3, the localized kernel matrix for each view is calculated according to the nearest neighbor matrices.

[0082] The localized kernel matrix for each view is expressed as:

[0083] ${\overline{K}}_p=\left(\sum _{i=1}^n{A}^{\left(i\right)}\right)\otimes K_p$

• • [0084] wherein K_p represents the localized kernel matrix of each view; A⁽ⁱ⁾ represents the n (τ×n)-nearest neighbor matrices; K_p represents the p-th given kernel matrix; n represents a number of samples; ⊗ represents the multiplication of elements.

[0085] In S4, the localized simple multiple kernel k-means clustering objective function is constructed according to the calculated localized kernel matrix for each view.

[0086] The simple multiple kernel k-means clustering objective function is expressed as:

[0087] $\underset{\gamma \in \Delta }{\min }\underset{H\in {ℝ}^{n\times k}}{\max }\mathrm{Tr}\left(K_{\gamma }{\mathrm{HH}}^T\right)$ $s.t.$ $H^{T}H=I_k.$

• • [0088] wherein γ represents a coefficient vector; H represents a partition matrix; H^T represents a permutation of a commutation matrix; K_γ represents a combined kernel matrix of K_p generated by γ; I_k represents a k-order identity matrix.
  • [0089] S⁽ⁱ⁾ ∈{0, 1}^{n×round(r×n)} represents the (τ×n)-nearest neighbor indicator matrix of the i-th sample, and round(·) represents a rounding function. The embodiment defines the local alignment of the i-th sample, which is expressed as:

[0090] ${\langle S^{{\left(i\right)}^T}{K}_{\gamma }{S}^{\left(i\right)},S^{{\left(i\right)}^T}{H}^T{\mathrm{HS}}^{\left(i\right)}\rangle }_F$

• • [0091] wherein S^(i)TK_γS⁽ⁱ⁾ represents that the nearest neighbor element of the i-th sample is taken. This local alignment only requires more reliable samples to be kept together, which enables it to better use the variations between kernel matrices for clustering. Local alignment of each sample is achieved by connecting pairs.

[0092] The localized simple multiple kernel k-means clustering objective function is expressed as:

[0093] ${\min }_{\gamma \in \Delta }{\max }_{H\in {ℝ}^{n\times k}}\mathrm{Tr}\left(H^T{\sum }_{i=1}^n\left(A^{\left(i\right)}{K}_{\gamma }{A}^{\left(i\right)}\right)H\right)$ $s.t.$ $H^{T}H=I_k,$ $\mathrm{wherein}$ $\Delta =\left\{\gamma \in {ℝ}^m❘{\sum }_{p=1}^m{\gamma }_p=1,{\gamma }_p\ge 0,\forall p\right\},$
R^m represents . . . ; γp represents . . . ;

[0094] $K_{\gamma }={\sum }_{p=1}^m{\gamma }_p^2{K}_p,\mathrm{and}{A}^{\left(i\right)}=S^{\left(i\right)}{S}^{{\left(i\right)}^T}$
represents the nearest neighbor mask matrix.

[0095] In S5, the reduced gradient descent method is used to solve the minimum of the constructed objective function to obtain the optimal clustering partition matrix.

[0096] (1) The objective function of the simple multiple kernel k-means clustering SimpleMKKM is a special case of the localized simple multiple kernel k-means clustering objective function described above, then:

[0097] ${\sum }_{i=1}^n\mathrm{Tr}\left(H^T\left(A^{\left(i\right)}{K}_{\gamma }{A}^{\left(i\right)}\right)H\right)={\sum }_{i=1}^n{\langle A^{\left(i\right)}\otimes K_{\gamma },A^{\left(i\right)}\otimes \left({\mathrm{HH}}^T\right)\rangle }_F={\sum }_{i=1}^n{\langle A^{\left(i\right)}\otimes K_{\gamma },{\mathrm{HH}}^T\rangle }_F={\langle \left({\sum }_{i=1}^n{A}^{\left(i\right)}\right)\otimes K_{\gamma },{\mathrm{HH}}^T\rangle }_F={\sum }_{p=1}^m{\gamma }_p^2{\langle \left({\sum }_{i=1}^n{A}^{\left(i\right)}\right)\otimes K_p,{\mathrm{HH}}^T\rangle }_F={\sum }_{p=1}^m{\gamma }_p^2{\langle {\tilde{K}}_p,{\mathrm{HH}}^T\rangle }_F=\mathrm{Tr}\left(H^T{\tilde{K}}_{\gamma }H\right),$

• • [0098] wherein ⊗ represents the multiplication of elements;

[0099] ${\tilde{K}}_p=\left({\sum }_{i=1}^n{A}^{\left(i\right)}\right)\otimes K_p$
represents a standardized kernel matrix;

• • [0100] when

[0101] ${\tilde{K}}_{\gamma }={\sum }_{p=1}^m{\gamma }_p^2{\tilde{K}}_p,$
by applying such normalization to each basis kernel, it is clearly seen that global kernel alignment is a special case of the local kernel alignment criteria. As can be seen from the above, the aforementioned formula is simplified to SimpleMKKM when all elements of A⁽ⁱ⁾ are set to 1. In this case, each sample takes the remaining samples as its neighbors. This means that SimpleMKKM may be taken as a special case of the above formula, and therefore, the above formula can be written equally effectively as:

[0102] ${\min }_{\gamma \in \Delta }𝒥\left(\gamma \right)$ $\mathrm{wherein}$ $𝒥\left(\gamma \right)=\left\{\underset{H}{\max }\mathrm{Tr}\left(H^T{\tilde{K}}_{\gamma }H\right),s.t.H^{T}H=I_k.\right\},$
in this case, the min-max optimization is transformed into a min optimization, where its target (γ) is a kernel k-means optimum function.

[0103] (2) Through the above normalization, each K_p still remains positive semi-definite (PSD).

[0104] This is specified with each K_p being a positive semi-definite matrix.

[0105] Note that S⁽ⁱ⁾ ∈{0, 1}^{n×round(τ×n)} and A^{({dot over (i)})}=S⁽ⁱ⁾S^(i)T, A^{({dot over (i)})} is a positive semi-definite matrix. Moreover, the product on the elements between two positive semi-definite matrices is still a positive semi-definite matrix. Therefore, each {tilde over (K)}_p is a positive semi-definite matrix.

[0106] Every {tilde over (K)}_p remains positive semi-definite through the above normalization, which guarantees the differentiability of (γ). The differentiability of (γ) is demonstrated next below, showing how its gradient is calculated and optimized using a reduced gradient descent algorithm.

[0107] (3) (γ) is differentiable, and the global uniqueness of (γ) can be derived.

[0108] The objective function is calculated by the gradient descent method as:

[0109] ${\left[\mathrm{▽𝒥}\left(\gamma \right)\right]}_p=\frac{\partial 𝒥\left(\gamma \right)}{\partial {\gamma }_p}-\frac{\partial 𝒥\left(\gamma \right)}{\partial {\gamma }_u}\forall p\ne u$ ${\left[\mathrm{▽𝒥}\left(\gamma \right)\right]}_u={\sum }_{p=1,p\ne u}^m\left(\frac{\partial 𝒥\left(\gamma \right)}{\partial {\gamma }_u}-\frac{\partial 𝒥\left(\gamma \right)}{\partial {\gamma }_p}\right)$ $\mathrm{wherein}$ $\frac{\partial 𝒥\left(\gamma \right)}{\partial {\gamma }_p}=2{\gamma }_p\mathrm{Tr}\left(H^{*}\top {\tilde{K}}_p{H}^{*}\right),$ $H^{*}=\left\{\arg {\max }_H\mathrm{Tr}\left(H\top {\tilde{K}}_{\gamma }H\right)s.t.H\top H=I_k\right\};$

• • [0110] u is set as a number indicating the largest component of vector γ, which is believed to provide better numerical stability.

[0111] The embodiment considers a positive constraint of γ in a descending direction, which is expressed as:

[0112] $d_p=\{\begin{array}{cc}0& \mathrm{if}{\gamma }_p=0{\mathrm{and}\left[\mathrm{▽𝒥}\left(\gamma \right)\right]}_p>0\\ -{\left[\mathrm{▽𝒥}\left(\gamma \right)\right]}_p& \mathrm{if}{\gamma }_p>0\mathrm{and}p\ne u\\ -{\left[\mathrm{▽𝒥}\left(\gamma \right)\right]}_u& \mathrm{if}p=u.\end{array}$

• • [0113] wherein d_p represents the descending direction, and γ can be calculated by γ←+ad, where α is the optimal step length. It may be selected by a one-dimensional line search strategy, such as an Armijo criterion.

[0114] The embodiment discusses the computational complexity of the provided localized simple MKKM. In each iteration, the localized SimpleMKKM needs to solve a kernel k-means problem, calculate the descending direction, and search for the optimal step length. Therefore, its computational complexity at each iteration is O(n³+m*n³+m*n₀), where n₀ is the maximum operand required to find the optimal step length. As observed, the localized simple MKKM does not significantly increase the computational complexity of existing MKKM and SimpleMKKM algorithms.

[0115] The convergence of the localized SimpleMKKM is then briefly discussed. Note that with a given γ, it becomes a traditional kernel k-means, which has a global optimum. Under this condition, the gradient calculation in step (3) is precise, the algorithm of the embodiment performs reduced gradient descent on a domain, and the function converges to the minimum of (γ).

[0116] FIG. 2 shows a flowchart of an algorithm.

[0117] The embodiment provides a novel localized simple multiple kernel k-means clustering machine learning method, which includes modules of localized kernel alignment, objective function optimization to obtain an optimal combination coefficient γ, a corresponding partition matrix H, and the like. In the embodiment, through the optimization of the objective function, the optimized kernel combination can represent the information of a single view, and can better serve the view fusion, so that the purpose of improving the clustering effect is achieved. Moreover, the embodiment performs localization processing on each view to strengthen local information. MKKM-MM was the first attempt to improve MKKM through min-max learning, which indeed improves MKKM, but has a limited effect. The performance of the provided localized SimpleMKKM significantly surpasses that of MKKM-MM. This once again proves the advantages of the formula and the associated optimization strategy of the embodiment. The localized SimpleMKKM consistently and significantly outperforms SimpleMKKM.

[0118] Correspondingly, further provided is a face image clustering system based on localized simple multiple kernel k-means, including:

• • [0119] an acquisition module, configured for acquiring face images and preprocessing the acquired face images to obtain an average kernel matrix for each view;
  • [0120] a first calculation module, configured for calculating n (τ×n)-nearest neighbor matrices according to the obtained average kernel matrices;
  • [0121] a second calculation module, configured for calculating a localized kernel matrix for each view according to the nearest neighbor matrices;
  • [0122] a construction module, configured for constructing a localized simple multiple kernel k-means clustering objective function according to the calculated localized kernel matrix for each view;
  • [0123] a solving module, configured for solving a minimum of the constructed objective function by adopting a reduced gradient descent method to obtain an optimal clustering partition matrix; and
  • [0124] a clustering module, configured for performing k-means clustering on the obtained clustering partition matrix to achieve clustering.

[0125] Further, calculating the localized kernel matrix for each view in the second calculation module is expressed as:

[0126] ${\overline{K}}_p=\left(\sum _{i=1}^n{A}^{\left(i\right)}\right)\otimes K_p$

• • [0127] wherein K_p represents the localized kernel matrix of each view; A⁽ⁱ⁾ represents the n (τ×n)-nearest neighbor matrices; K_p represents the p-th given kernel matrix; n represents a number of samples; ⊗ represents the multiplication of elements.

[0128] Further, the simple multiple kernel k-means clustering objective function in the construction module is expressed as:

[0129] $\underset{\gamma \in \Delta }{\min }\underset{H\in {ℝ}^{n\times k}}{\max }\mathrm{Tr}\left(K_{\gamma }\mathrm{HH}\top \right)$ $s.t.H\top H=I_k.$

• • [0130] wherein γ represents a coefficient vector; H represents a partition matrix; H^T represents a permutation of a commutation matrix; K_γ represents a combined kernel matrix of K_p generated by γ; I_k represents a k-order identity matrix.

[0131] Further, the localized simple multiple kernel k-means clustering objective function in the construction module is expressed as:

[0132] ${\min }_{\gamma \in \Delta }{\max }_{H\in {ℝ}^{n\times k}}\mathrm{TR}\left(H\top {\sum }_{i=1}^n\left(A^{\left(i\right)}{K}_{\gamma }{A}^{\left(i\right)}\right)H\right)$ $s.t.H\top H=I_k,$ $\mathrm{wherein}$ $\Delta =\left\{\gamma \in {ℝ}^m❘{\sum }_{p=1}^m{\gamma }_p=1,{\gamma }_p\ge 0,\forall p\right\},$
R^m represents an m-dimensional real number vector space; γ_p represents the p-th component of γ.

[0133] The difference between the face image clustering method based on localized simple multiple kernel k-means provided in the embodiment and that provided in Embodiment I is as follows: The embodiment tested the clustering performance of the present method on 8 MKKM benchmark datasets, including MSRA, Still, Cal-7, PFold, Nonpl, Flo17, Flo102, and Reuters. See table 1 for relevant information on the datasets.

[0134]

TABLE 1
Datasets Used
	Dataset	Samples	Kernels	Clusters
	MSRA	210	6	7
	Still	467	3	6
	Cal-7	441	6	7
	PFD	694	12	27
	Nonpl	2732	69	3
	Flo17	1360	7	17
	Flo102	8189	4	102
	Reuters	18758	5	6

[0135] The embodiment adopted an average multiple kernel k-means (A-MKKM) clustering algorithm, multiple kernel k-means (MKKM) clustering, localized multiple kernel k-means (LMKKM) clustering, robust multiple kernel k-means clustering (MKKM-MM), multiple kernel k-means clustering with matrix-induced regularization (MKKM-MR), optimal neighborhood multiple kernel clustering (ONKC), multi-view clustering via late fusion alignment maximization (MVC-LFA), and multiple kernel clustering with local alignment maximization (LKAM). In all experiments, all benchmark kernels were first centered and regularized. For all datasets, the number of categories was assumed to be known and set as the number of clustering categories. In addition, in the embodiment, grid search was used for the parameters of RMKKM, MKKM-MR, ONKC, and MVC-LFA.

[0136] The embodiment used common cluster accuracy (ACC), normalized mutual information (NMI), and Rand index (RI) to show the clustering performance of each method. All methods were randomly initialized and repeated 50 times and showed the best results to reduce the randomness caused by k-means.

[0137]

TABLE 2
Clustering Effect of Different Algorithms on Eight Datasets
		MKKM	LMKKM	ONKC	MKKM-MIR	LKAM	LF-MVC	MKKM-MM	SIMPLEMKKM	PRO-
DATASETS	AVG-KKM	[4]	[2]	[13]	[12]	[9]	[23]	[1]	[33]	POSED
ACC
MSRA	83.3 ± 0.8	81.3 ± 3.1	81.9 ± 0.7	77.4 ± 1.6	87.9 ± 0.6	72.5 ± 0.5	84.2 ± 0.5	83.3 ± 0.8	86.5 ± 0.2	91.2 ± 0.3
STILL	31.3 ± 0.7	31.3 ± 0.6	31.1 ± 0.5	31.2 ± 1.3	31.5 ± 1.0	31.6 ± 0.2	31.7 ± 0.4	31.3 ± 0.7	31.3 ± 0.6	36.5 ± 0.7
CAL-7	59.2 ± 4.9	52.2 ± 4.3	53.9 ± 1.0	60.2 ± 1.6	68.3 ± 0.0	63.9 ± 3.1	65.2 ± 7.1	59.2 ± 4.9	68.3 ± 1.5	76.5 ± 1.8
PFD	29.0 ± 1.5	27.0 ± 1.1	22.4 ± 0.7	35.3 ± 1.3	34.3 ± 1.7	31.7 ± 2.1	32.6 ± 1.9	29.0 ± 1.5	34.7 ± 1.9	35.9 ± 1.3
NONPL	49.7 ± 0.2	49.3 ± 0.2	—	49.9 ± 0.0	50.3 ± 0.2	53.8 ± 0.0	46.7 ± 0.6	49.7 ± 0.2	52.0 ± 0.0	69.3 ± 0.2
FLO17	50.8 ± 1.5	44.9 ± 2.4	37.5 ± 1.6	42.9 ± 2.1	57.7 ± 1.2	39.6 ± 1.6	54.3 ± 1.8	50.8 ± 1.5	59.5 ± 1.3	61.3 ± 1.4
FLO102	27.1 ± 0.8	22.4 ± 0.5	—	39.2 ± 0.9	39.1 ± 1.3	40.0 ± 1.0	43.2 ± 1.3	27.1 ± 0.8	42.5 ± 0.8	44.0 ± 1.0
REUTERS	45.5 ± 1.5	45.4 ± 1.5	—	40.9 ± 2.1	39.7 ± 1.5	40.0 ± 2.2	45.4 ± 1.7	45.5 ± 1.5	45.5 ± 0.7	46.6 ± 0.6
NMI
MSRA	74.0 ± 1.0	73.2 ± 1.7	75.0 ± 1.4	62.4 ± 2.2	77.3 ± 1.1	62.7 ± 0.9	73.2 ± 0.3	74.0 ± 1.0	75.2 ± 0.5	82.6 ± 0.5
STILL	12.8 ± 0.8	13.0 ± 0.8	13.2 ± 0.5	12.7 ± 0.4	12.9 ± 0.3	13.6 ± 0.2	11.4 ± 0.3	12.8 ± 0.8	12.8 ± 1.0	14.2 ± 0.3
CAL-7	59.1 ± 2.9	51.6 ± 4.1	52.1 ± 1.3	53.7 ± 1.5	63.8 ± 0.0	59.2 ± 1.5	65.1 ± 2.6	59.1 ± 2.9	63.7 ± 0.3	74.6 ± 1.2
PFD	40.3 ± 1.3	38.0 ± 0.6	34.7 ± 0.6	44.0 ± 0.8	43.1 ± 1.0	42.5 ± 1.2	41.7 ± 1.1	40.3 ± 1.3	44.4 ± 1.1	45.2 ± 0.9
NONPL	17.2 ± 0.5	15.0 ± 0.5	—	14.4 ± 0.0	14.9 ± 0.0	0.2 ± 0.0	9.8 ± 0.2	17.2 ± 0.5	11.2 ± 0.0	22.6 ± 0.1
FLO17	49.7 ± 1.0	44.9 ± 1.5	38.8 ± 1.1	43.0 ± 1.4	57.2 ± 0.8	42.4 ± 0.8	54.1 ± 0.9	49.7 ± 1.0	57.8 ± 0.9	39.4 ± 0.7
FLO102	46.0 ± 0.5	42.7 ± 0.2	—	55.7 ± 0.4	55.9 ± 0.6	55.4 ± 0.4	57.8 ± 0.6	46.0 ± 0.5	58.6 ± 0.5	60.0 ± 0.4
REUTERS	27.4 ± 0.4	27.3 ± 0.4	—	21.0 ± 1.8	21.3 ± 1.3	21.5 ± 2.3	27.2 ± 0.2	27.4 ± 0.4	27.7 ± 0.2	28.3 ± 0.6
PURITY
MSRA	83.3 ± 0.8	81.5 ± 2.7	81.9 ± 0.7	77.4 ± 1.6	87.9 ± 0.6	72.5 ± 0.5	84.2 ± 0.5	83.3 ± 0.8	36.5 ± 0.2	91.2 ± 0.3
STILL	33.8 ± 0.8	33.8 ± 0.7	33.3 ± 0.5	33.9 ± 0.9	34.0 ± 0.8	35.7 ± 0.3	34.8 ± 0.4	33.8 ± 0.8	33.8 ± 0.7	38.2 ± 0.6
CAL-7	68.0 ± 3.2	63.8 ± 3.7	66.4 ± 0.6	67.1 ± 1.3	72.1 ± 0.0	70.7 ± 2.0	76.7 ± 3.2	68.0 ± 3.2	72.3 ± 0.2	82.3 ± 1.4
PFD	37.4 ± 1.7	33.7 ± 1.1	31.2 ± 1.0	41.9 ± 1.0	41.2 ± 1.4	39.6 ± 1.5	39.2 ± 1.4	37.4 ± 1.7	41.8 ± 1.5	42.5 ± 1.3
NONPL	72.5 ± 0.2	71.2 ± 0.2	—	60.4 ± 0.0	60.4 ± 0.0	60.4 ± 0.0	66.5 ± 0.2	72.3 ± 0.2	60.4 ± 0.0	71.6 ± 0.2
FLO17	51.9 ± 1.5	46.2 ± 2.0	39.2 ± 1.3	44.7 ± 2.0	39.2 ± 1.2	42.8 ± 1.2	55.6 ± 1.5	51.9 ± 1.5	60.9 ± 1.2	62.4 ± 1.3
FLO102	32.3 ± 0.6	27.8 ± 0.4	—	45.1 ± 0.9	45.2 ± 1.0	46.5 ± 0.6	49.7 ± 1.0	32.3 ± 0.6	48.6 ± 0.7	50.3 ± 0.8
REUTERS	53.0 ± 0.4	52.9 ± 0.5	—	51.8 ± 1.5	50.9 ± 1.4	51.9 ± 1.0	52.9 ± 0.3	53.0 ± 0.4	53.3 ± 0.0	53.4 ± 0.4
RAND INDEX
MSRA	68.1 ± 1.0	66.2 ± 3.1	68.0 ± 1.1	55.7 ± 2.6	74.4 ± 1.2	53.8 ± 0.7	68.4 ± 0.6	68.1 ± 1.0	71.2 ± 0.5	80.6 ± 0.5
STILL	8.0 ± 0.5	8.0 ± 0.5	8.0 ± 0.2	7.8 ± 0.3	8.1 ± 0.2	8.2 ± 0.1	7.1 ± 0.2	8.0 ± 0.5	7.9 ± 0.5	9.3 ± 0.3
CAL-7	46.0 ± 6.5	38.3 ± 4.9	41.2 ± 1.1	43.0 ± 2.1	54.9 ± 0.0	50.6 ± 3.1	55.8 ± 6.8	46.0 ± 6.5	55.6 ± 0.3	69.9 ± 1.8
PFD	14.4 ± 1.8	12.1 ± 0.7	7.8 ± 0.4	17.6 ± 1.3	17.4 ± 1.6	15.5 ± 1.5	15.8 ± 1.6	14.4 ± 1.8	17.6 ± 1.9	19.8 ± 1.0
NONPL	17.6 ± 0.3	13.8 ± 0.4	—	8.3 ± 0.0	8.5 ± 0.1	11.3 ± 0.0	10.7 ± 0.2	17.6 ± 0.3	8.0 ± 0.0	35.0 ± 0.1
FLO17	32.2 ± 1.3	27.2 ± 1.8	20.6 ± 1.1	24.3 ± 1.5	40.1 ± 0.9	22.6 ± 0.9	37.4 ± 1.3	32.2 ± 1.3	41.5 ± 1.5	43.4 ± 1.0
FLO102	15.5 ± 0.3	12.1 ± 0.4	—	24.5 ± 0.6	24.9 ± 1.1	26.0 ± 0.8	29.7 ± 1.1	15.5 ± 0.5	28.3 ± 0.8	29.9 ± 0.8
REUTERS	21.8 ± 1.4	21.8 ± 1.4	—	18.8 ± 2.4	18.9 ± 2.0	16.9 ± 2.7	21.4 ± 1.1	21.8 ± 1.4	22.1 ± 0.8	22.0 ± 0.3

[0138] Table 2 shows the clustering effects of the above methods and the comparison algorithms on all datasets. From this table, it can be observed that: 1. MKKM-MM was the first attempt to improve MKKM through min-max learning. As observed, it does improve MKKM, but the performance improvement over MKKM is limited across all datasets. Meanwhile, the performance of the provided localized simple MKKM significantly surpasses that of MKKM-MM. This once again proves the advantages of the method and the associated optimization strategy of the embodiment. 2. In addition to the localized SimpleMKKM of the method, SimpleMKKM also achieves comparable or better clustering performance than the above algorithms on all benchmark datasets. The superiority is attributed to its new formula and new optimization algorithm. 3. The provided localized SimpleMKKM consistently and significantly outperforms SimpleMKKM. For example, ACC exceeds SimpleMKKM algorithm by 4.7%, 5.2%, 8.3%, 1.2%, 17.3%, 17.3%, 1.8%, 1.5%, and 1.1% on 8 benchmark datasets. Improvements in other criteria are also similar. These results well prove the superiority of the provided localized simple MKKM benefiting from exploring and extracting local information of the kernel matrix.

[0139] FIG. 3 shows kernel coefficients learned by different algorithms. FIG. 4 shows the clustering performance of localized SimpleMKKM learning H over iterations on 6 benchmark datasets. FIG. 5 shows the variation in the objective function value of localized SimpleMKKM with the number of iterations. FIG. 6 shows the comparison of the running times (unit: logarithm of seconds) of different algorithms on all benchmark datasets, where histograms under each dataset are, from left to right, Avg-KKM, MKKM, LMKKM, ONKC, MKKM-MiR, LKAM, LF-MVC, MKKM-MM, SimpleMKKM, and LSMKKM. FIG. 7 shows the effect of the magnitude of the nearest neighbor ratio τ on clustering performance on 6 representative datasets.

[0140] The embodiment provides a novel localized simple multiple kernel k-means clustering machine learning method, which includes modules of localized kernel alignment, objective function optimization to obtain an optimal combination coefficient γ, a corresponding partition matrix H, and the like. In the embodiment, through the optimization of the objective function, the optimized kernel combination can represent the information of a single view, and can better serve the view fusion, so that the purpose of improving the clustering effect is achieved. Moreover, the embodiment performs localization processing on each view to strengthen local information. MKKM-MM was the first attempt to improve MKKM through min-max learning, which indeed improves MKKM, but has a limited effect. The performance of the provided localized SimpleMKKM significantly surpasses that of MKKM-MM. This once again proves the advantages of the formula and the associated optimization strategy of the embodiment. The localized SimpleMKKM consistently and significantly outperforms SimpleMKKM.

[0141] It should be noted that the above descriptions are only preferred embodiments of the present application and the principles of the employed technologies. It should be understood by those skilled in the art that the present application is not limited to the particular embodiments described herein, and those skilled in the art can make various obvious changes, rearrangements, and substitutions without departing from the protection scope of the present application. Therefore, although the present application has been described in more detail by the above embodiments, it is not limited to the above embodiments, and may further include other equivalent embodiments without departing from the concept of the present application, and the scope of the present application is determined by the scope of the appended claims