# Adaptive Fuzzy C-Means with Graph Embedding

Qiang Chen, Weizhong Yu, Feiping Nie, and Xuelong Li Feiping Nie is the
corresponding author.Qiang Chen is with the School of Computer Science, and
School of Artificial Intelligence, Optics and Electronics (iOPEN),
Northwestern Polytechnical University, Xi’an 710072, Shaanxi, P. R. China.
(e-mail: chenq@mail.nwpu.edu.cn).Feiping Nie is with the School of Artificial
Intelligence, OPtics and ElectroNics (iOPEN), School of Computer Science,
Northwestern Polytechnical University, Xi’an 710072, P.R. China, and also with
the Key Laboratory of Intelligent Interaction and Applications (Northwestern
Polytechnical University), Ministry of Industry and Information Technology,
Xi’an 710072, P.R. China (email: feipingnie@gmail.com).Weizhong Yu is with the
School of Artificial Intelligence, OPtics and ElectroNics (iOPEN),
Northwestern Polytechnical University, Xi’an 710072, P.R. China, and also with
the Key Laboratory of Intelligent Interaction and Applications (Northwestern
Polytechnical University), Ministry of Industry and Information Technology,
Xi’an 710072, P.R. China (email: yuwz05@mail.xjtu.edu.cn).Xuelong Li is with
the Institute of Artificial Intelligence (TeleAI), China Telecom Corp Ltd, 31
Jinrong Street, Beijing 100033, P. R. China (email: li@nwpu.edu.cn).

###### Abstract

Fuzzy clustering algorithms can be roughly categorized into two main groups:
Fuzzy C-Means (FCM) based methods and mixture model based methods. However,
for almost all existing FCM based methods, how to automatically selecting
proper membership degree hyper-parameter values remains a challenging and
unsolved problem. Mixture model based methods, while circumventing the
difficulty of manually adjusting membership degree hyper-parameters inherent
in FCM based methods, often have a preference for specific distributions, such
as the Gaussian distribution. In this paper, we propose a novel FCM based
clustering model that is capable of automatically learning an appropriate
membership degree hyper-parameter value and handling data with non-Gaussian
clusters. Moreover, by removing the graph embedding regularization, the
proposed FCM model can degenerate into the simplified generalized Gaussian
mixture model. Therefore, the proposed FCM model can be also seen as the
generalized Gaussian mixture model with graph embedding. Extensive experiments
are conducted on both synthetic and real-world datasets to demonstrate the
effectiveness of the proposed model.

###### Index Terms:

Fuzzy clustering, spectral clustering, fuzzy C-means, Gaussian mixture model,
graph embedding.

##  I Introduction

Fuzzy clustering algorithms have been extensively utilized to uncover
potential latent structures within data. Typically, fuzzy clustering
algorithms can be roughly divided into two main categories: FCM based methods
and mixture model based methods.

FCM stands as one of the most classic fuzzy clustering models, forming the
cornerstone for numerous existing fuzzy clustering algorithms. The fundamental
concept behind FCM is to regulate the fuzziness of membership degrees through
hyper-parameters such as weighting exponent [1, 2], entropy regularization
[3], or quadratic term [4] hyper-parameters. Although various FCM variants
have been developed [5, 6], the challenge still persists in finding a reliable
method for automatically selecting the optimal values of these membership
degree hyper-parameters. In almost all existing FCM based clustering
algorithms, the membership degree hyper-parameters are adjusted through
historical experience or experimental methods. Unfortunately, these approaches
are often inefficient and may lead to poor clustering results.

Another drawback of FCM is that it can only achieve good performance on data
with spherical clusters, whereas real-world cluster shapes are often complex
and non-spherical, such as ellipsoidal and non-Gaussian. To improve the
performance of FCM on data with ellipsoidal clusters, Mahalanobis distance was
introduced into FCM [7, 8]. For non-Gaussian clusters, some kernel-based FCM
algorithms have been developed [9, 10, 11]. These algorithms can project data
from the low-dimensional space to a high-dimensional space, facilitating
linear classification of non-Gaussian clusters. However, kernel-based methods
are susceptible to noises, and selecting a proper kernel is also a challenging
problem.

Recently, graph embedding has become a frequently used technique in machine
learning fields because it can help algorithms handle non-Gaussian data [12,
13, 14, 15]. Spectral clustering is a classic graph based clustering
algorithm. It involves constructing graphs to represent samples using an
affinity matrix, followed by the application of the K-means algorithm to these
graph representations of the data [16, 17, 18]. Compared to kernel embedding
methods, graph embedding methods can better capture the local structure of
data and may yield more satisfactory results. Inspired by spectral clustering,
lots of graph based clustering algorithms were developed. In order to obtain
the optimal graph similarity matrix, Nie et al. proposed a novel model that
can automatically learn proper weights of the similarity matrix [19]. To
generate a graph with clusters, Han et al. proposed a spectral clustering
model that incorporates orthogonal and nonnegative constraints [20]. Moreover,
their approach enables the direct acquisition of final cluster labels,
eliminating the necessity for post-processing. Pei et al. revisited the
unified framework of K-means and ratio-cut spectral clustering, and proposed
an efficient clustering algorithm based on the framework [21]. Recently, a
novel clustering algorithm utilizing bipartite graphs was also developed [22],
which posses an excellent clustering performance but comparatively low
computational complexity.

Owing to the excellent performance of graph based methods on non-Gaussian
data, various graph based fuzzy clustering algorithms have recently been
developed as well. Locality preservation [23] is a proficient graph based
dimensional reduction method, and Zhou et al. introduced this method into FCM
to enhance clustering performance [24]. To better handel data with balanced
clusters, Liu et al. proposed a balance regularization to suppress unbalanced
classes. Recently anchor graph is getting a lot of attention, and some anchor
graph based clustering methods have been developed [25, 26]. Wang et al.
proposed to constraint the spareness of membership degree matrix utilizing
$L_{0}$-norm [27], which may suppress the influence of outliers on graph
weights learning and improve clustering performance. Besides, Zhao et al.
proposed a novel FCM model featured on shrunk pattern based manifold learning
[28], which can be also seen as a graph based method with the same graph
weights.

Mixture model based methods can be viewed as the other branch of fuzzy
clustering. A mixture model can be seen as a linear combination of multiple
probability distributions and is usually optimized by the EM algorithm [29].
The Gaussian mixture model is one of the most popular model based methods
[30]. However, the Gaussian mixture model assumes that data is drawn from the
Euclidean space. In reality, naturally occurring data may reside on or close
to an underlying sub-manifold. For considering the sub-manifold structure,
Laplacian regularized Gaussian mixture model and locally consistent Gaussian
mixture model were developed [31, 32]. Generally, heavy-tailed distributions
are more robust than the Gaussian distribution, such as the generalized
Gaussian distribution [33] and the Student’s $t$-distribution [34]. Therefore,
some heavy-tailed distributions based mixture models were proposed to improve
clustering performance on polluted datasets [35, 36].

By summarizing the above analysis we realize that, for almost all FCM based
clustering methods, the problem of automatically learning membership degree
hyper-parameters is still challenging and not well-resolved. Additionally,
most mixture model based methods only focus on data with specific
distributions, i.e., Gaussian distribution, and lack the ability of handling
non-Gaussain data. The main contributions of this paper are summarized as
follows:

  * •

The proposed FCM model introduces a membership hyper-parameter adaptive
learning mechanism that can automatically learn a proper value for the
membership degree hyper-parameter.

  * •

By introducing the graph embedding regularization term, the proposed FCM model
can handle data with non-Gaussian clusters, which also proves the
transferability of the membership hyper-parameter adaptive learning mechanism.

  * •

By removing the graph embedding regularization, the proposed FCM model can
degenerate into a simplified generalized Gaussian mixture model. Therefore,
the proposed FCM model can be also viewed as a mixture model with graph
embedding.

  * •

An efficient alternating optimization strategy with closed solutions is
provided to optimize the proposed FCM model.

Notations:  Throughout the paper, let $\mathbb{R}$, $\mathbb{R}^{+}$,
$\mathbb{R}^{n}$ and $\mathbb{R}^{n\times m}$ denote the sets of real numbers,
positive real numbers, length-$n$ vectors and size $n\times m$ matrices,
respectively. Suppose data matrix
$X=[x_{1},x_{2},...,x_{n}]\in\mathbb{R}^{d\times n}$ consists of $n$ samples
with $c$ clusters, and each sample $x_{i}$ has $d$ features. For matrix $A$,
the element in the $i$-th row and the $j$-th column of $A$ is denoted by
$a_{ij}$, and trace of $A$ is denoted by $Tr(A)$. The adjacency matrix of an
undirected weighted graph is defined as $W$ and the degree matrix is defined
as $D$. Then the Laplacian matrix is defined as $L=D-W$, and the normalized
one is defined as $\hat{L}=D^{-1/2}LD^{-1/2}$. The $L_{2}$-norm of vector $v$
is denoted by $||v||_{2}$. An identity matrix with $n$ diagonal elements is
denoted by $I_{n}$.

##  II Related Works

In this section, we introduce some important related works, including FCM,
spectral clustering and the generalized Gaussian mixture model.

###  II-A FCM

FCM is an extremely significant fuzzy clustering model as it forms the basis
for plenty of fuzzy clustering algorithms. According to the methods of
controlling fuzziness, FCM can be roughly divided into three types: weighting
exponent based, entropy regularization based, and quadratic term based. The
objective function of FCM with entropy regularization is shown below.

$\begin{gathered}\min_{U,V}\sum_{i=1}^{n}\sum_{j=1}^{c}u_{ij}||x_{i}-v_{j}||_{2}^{2}+\frac{1}{\gamma}u_{ij}\log
u_{ij},\\\ {\rm s.t.}\ \ \sum_{j=1}^{c}u_{ij}=1,\ \ 0<u_{ij}<1\end{gathered}$
(1)

where $U\in\mathbb{R}^{n\times c}$ denotes the membership degree matrix,
$V=\\{v_{1},v_{2},...,v_{c}\\}$ denotes the set of cluster centers,
$\gamma\in\mathbb{R}^{+}$ denotes the entropy regularization hyper-parameter,
and $n$ and $c$ denote the numbers of samples and clusters, respectively.

###### Remark 1

In almost all existing FCM with entropy regularization algorithms, the entropy
regularization hyper-parameter $\gamma$ can not be automatically updated.
Typically, the value of $\gamma$ is adjusted by historical experience or
experimental results.

###  II-B Spectral Clustering

Spectral clustering is a popular clustering algorithm for its effectiveness on
handling non-Gaussian clusters. The fundamental concept behind spectral
clustering is the similarity graph that encapsulates pairwise similarities
among data points, with higher similarity weights indicating closer proximity.
By strategically eliminating weaker edges, the algorithm extracts c
independent sub-graphs, ultimately yielding c clusters. However, the
optimization of spectral clustering is NP-hard, and it usually resorts to
optimizing the following relaxed problems.

$\begin{gathered}\min_{F}Tr(F^{T}LF),\ \ {\rm s.t.}\ \
F^{T}F=I_{c}\end{gathered}$ (2)

where $F\in\mathbb{R}^{n\times c}$ is the indicator matrix with $c$ clusters
and $L\in\mathbb{R}^{n\times n}$ is the Laplacian matrix. The objective
function in Eq. (2) can be optimized by computing the corresponding
eigenvectors of the $c$ minimum eigenvalues. Subsequently, performing K-means
on $F$ allows us to obtain $c$ clusters. According to the property of
Laplacian matrix, the objective function in Eq. (2) can be reformulated as

$\begin{gathered}\min_{F}\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}w_{ij}||f_{i}-f_{j}||_{2}^{2}\
\ {\rm s.t.}\ \ F^{T}F=I_{c}\end{gathered}$ (3)

where $w_{ij}$ is the element of the adjacency matrix $W$ representing the
similarity between sample $x_{i}$ and sample $x_{j}$, and
$f_{i}\in\mathbb{R}^{1\times c}$ is the $i$-th row of the $F$. Therefore, the
objective function in Eq. (3) can also be seen as a manifold learning
algorithm, which projects sample $x_{i}$ form the original manifold as $f_{i}$
into the new manifold while preserving the similarities among samples. If the
Laplacian matrix $L$ is replaced with the normalized Laplacian matrix
$\hat{L}$, the objective function of R-cut spectral clustering in Eq. (2) is
transformed into that of N-cut spectral clustering.

###  II-C Generalized Gaussian Mixture Model

The Kotz-type distribution is a member of the elliptically contoured
distribution family, and the generalized Gaussian distribution is a special
case of the Kotz-type distribution [37, 38, 39]. Let $x\in\mathbb{R}^{d}$ be a
$d$-dimensional random vector, and the probability density function of the
generalized Gaussian distribution is defined as follows.

$\begin{gathered}g(x|\theta)\\!=\\!\frac{{\beta\Gamma(\frac{d}{2}){m^{\frac{d}{{2\beta}}}}}}{{{\pi^{\frac{d}{2}}}\Gamma(\frac{d}{{2\beta}})}}|\Sigma{|^{-\frac{1}{2}}}\times\quad\qquad\qquad\\\
\qquad\qquad\exp\\!\left\\{\\!-m{{\left[{{{(x\\!-\\!v)}^{T}}{\Sigma^{-1}}(x\\!-\\!v)}\right]}^{\beta}}\\!\right\\}\\\
\end{gathered}$ (4)

where $\theta=\\{v,\Sigma,\beta,m\\}$ denotes the set of parameters,
$v\in\mathbb{R}^{d}$ denotes the mean, $\Sigma\in\mathbb{R}^{d\times d}$
denotes the positive definite covariance matrix, $\beta\in\mathbb{R}^{+}$
denotes the shape parameter, and $m\in\mathbb{R}^{+}$ denotes the scale
parameter.

The generalized Gaussian mixture model can be seen as a linear combination of
multiple generalized Gaussian components, and the probability distribution
function can be written as

$\begin{gathered}f(x|\Theta)=\mathop{\sum}\limits_{j=1}^{c}{\alpha_{j}}g(x|{\theta_{j}}),\
\ {\rm s.t.}\sum_{j=1}^{c}\alpha_{j}=1\end{gathered}$ (5)

where $\Theta=\\{\alpha,V,\Sigma,\beta,m\\}$ denotes the set of all parameters
in the MGGD mixture model,
${\theta_{j}}=\left\\{{{v_{j}},{\Sigma_{j}},\beta,m}\right\\}$ denotes the
parameter set of the $j$-th component,
$\alpha=\\{{\alpha_{1}},{\alpha_{2}},..,{\alpha_{c}}\\}$ denotes the set of
mixing coefficients, and $c$ denotes the number of components.

For estimating the parameters of a probability distribution, the maximum
likelihood estimation method is frequently used, and the log-likelihood
function is constructed as follows.

$\begin{gathered}L(\Theta|X)\\!\\!=\\!\\!\mathop{\sum}\limits_{i=1}^{n}\\!\log
f({x_{i}}|\Theta)\\!=\\!\\!\mathop{\sum}\limits_{i=1}^{n}\\!\log\\!\mathop{\sum}\limits_{j=1}^{c}\\!{\alpha_{j}}g({x_{i}}|{\theta_{j}}),\\\
{\rm s.t.}\sum_{j=1}^{c}\alpha_{j}=1\end{gathered}$ (6)

However, optimizing the above objective function presents challenges due to
the presence of sum in the logarithm. The Expectation-Maximization (EM)
algorithm [40], a probability-based optimization method, is a frequently used
method to addresses this difficulty. Instead of directly optimizing the
original objective function, EM introduces a latent variable. The optimization
process then shifts towards maximizing the Q function, a derived auxiliary
function.

##  III The Proposed Method

###  III-A Formulation

In this subsection, we initially introduce how the equivalent connection
between FCM and the generalized Gaussian mixture model is constructed. Then,
based on this, we show how the problem of automatically learning membership
degree hyper-parameters in FCM is solved. Furthermore, we introduce how the
graph is embedded into FCM to help deal with non-Gaussian clusters, and
finally present the objective function of the proposed model.

Equivalence and hyper-parameter learning: Since the log-likelihood function of
the generalized Gaussian mixture model involves a sum inside the logarithm,
optimizing this objective function requires using the EM algorithm. Notably,
the EM algorithm, being grounded in probability theory, diverges significantly
from the optimization strategy employed in FCM. In order to build the
connection between FCM and the generalized Gaussian mixture model, the
equivalent objective function of the generalized Gaussian mixture model is
constructed as follows.

###### Proposition 1

The update equations of the maximum log-likelihood function in Eq. (6) for the
generalized Gaussian mixture model, which is optimized through the EM
algorithm, are equivalent to the update equations of the following objective
function.

$\begin{gathered}\mathop{\min}\limits_{U,\alpha,V,\Sigma,\beta,m}\mathop{\sum}\limits_{i=1}^{n}\mathop{\sum}\limits_{j=1}^{c}{u_{ij}}\bigg{\\{}m{{{{\left[{{{(x_{i}-{v_{j}})}^{T}}{\Sigma_{j}^{-1}}(x_{i}-{v_{j}})}\right]}}}^{\beta}}\
\ \\\
\quad+\frac{1}{2}\log|{\Sigma_{j}}|-\log{\alpha_{j}}-\log\frac{{\beta\Gamma(\frac{d}{2}){m^{\frac{d}{{2\beta}}}}}}{{{\pi^{\frac{d}{2}}}\Gamma(\frac{d}{{2\beta}})}}+\log{u_{ij}}\bigg{\\}},\\\
\ \ {\rm s.t.}\ \ \mathop{\sum}\limits_{j=1}^{c}{\alpha_{j}}=1,\ \
0<{\alpha_{j}}<1,\\\ \ \ \ \ \ \ \ \
\mathop{\sum}\limits_{j=1}^{c}{u_{ij}}=1,\ \ 0<{u_{ij}}<1\end{gathered}$ (7)

where $u_{ij}$ is the membership degree denoting the probability of sample
$x_{i}$ being assigned to the $j$-th cluster,
$\alpha=\\{{\alpha_{1}},{\alpha_{2}},..,{\alpha_{c}}\\}$,
$V=\\{{v_{1}},{v_{2}},..,{v_{c}}\\}$ and
$\Sigma=\\{{\Sigma_{1}},{\Sigma_{2}},..,{\Sigma_{c}}\\}$ denote the sets of
mixing coefficients, means and scale matrices, and $\beta$ and $m$ denote the
shape parameter and the scale parameter in the generalized Gaussian mixture
model. To concentrate on the main idea, the proof for Proposition 1 is moved
to the Appendix.

If we consider only the membership degree matrix $U$ and the set of means $V$
as variables in Eq. (7), treating other variables as constants, i.e.,
$\Sigma_{j}=I_{d}$, $\alpha_{j}=1/c$, $\beta=1$ and $m\in\mathbb{R}^{+}$, we
obtain the objective function of the simplified generalized Gaussian mixture
model as follows.

$\begin{gathered}\min_{U,V}\sum_{i=1}^{n}\sum_{j=1}^{c}u_{ij}m||x_{i}-v_{j}||_{2}^{2}+u_{ij}\log
u_{ij},\\\ {\rm s.t.}\ \ \sum_{j=1}^{c}u_{ij}=1,\ \ 0<u_{ij}<1\end{gathered}$
(8)

Then let us look back at the objective function of FCM in Eq. (1). Since the
membership degree hyper-parameter $\gamma$ in FCM is a positive constant, the
objective function of FCM in Eq. (1) can be transformed by multiplying
$\gamma$ as follows.

$\begin{gathered}\min_{U,V}\sum_{i=1}^{n}\sum_{j=1}^{c}u_{ij}\gamma||x_{i}-v_{j}||_{2}^{2}+u_{ij}\log
u_{ij},\\\ {\rm s.t.}\ \ \sum_{j=1}^{c}u_{ij}=1,\ \ 0<u_{ij}<1\end{gathered}$
(9)

By comparing the objective function of the simplified generalized Gaussian
mixture model in Eq. (8) with that of FCM in Eq. (9), we can observe that the
membership degree hyper-parameter $\gamma$ in FCM serves the same purpose as
the scale parameter $m$ in the generalized Gaussian mixture model. However,
the scale parameter $m$ in the generalized Gaussian model can be learned
automatically. Therefore, it is possible to learn the membership degree hyper-
parameter $\gamma$ in FCM in the same manner.

In Eq. (7), if we replace $m$ with $\gamma$, consider $U$, $V$ and $\gamma$ as
variables, and set $\Sigma_{j}=I_{d}$, $\alpha_{j}=1/c$ and $\beta=1$, we
obtain an FCM objective function that can automatically learn the membership
degree hyper-parameter $\gamma$ as follows.

$\begin{gathered}\mathop{\min}\limits_{U,V,\gamma}\\!\sum\limits_{i=1}^{n}\\!\sum\limits_{j=1}^{c}\\!u_{ij}\gamma||x_{i}-{v_{j}}||_{2}^{2}+u_{ij}\log{u_{ij}}-n\log{\gamma^{\frac{d}{2}}},\\\
{\rm{}}{\rm s.t.}\ {\rm{}}\mathop{\sum}\limits_{j=1}^{c}{u_{ij}}=1,\
{\rm{}}0<{u_{ij}}<1\end{gathered}$ (10)

where $d$ is the number of features for sample $x_{i}$. Note that, the FCM
objective function in Eq. (10) can be also seen as a simplified generalized
Gaussian mixture model, because they have the same update equations.

(a)

(b)

Figure 1: Illustration on graph based manifold learning. For data residing in
a complex manifold, as depicted in (a), Euclidean distance may not accurately
capture the true relationships between samples. However, by projecting the
data according to the similarity graph into a simpler manifold, as illustrated
in (b), the newly learned manifold facilitates easier clustering compared to
the original manifold.

Graph embedding and the proposed model: A drawback of FCM is that it may not
perform well with non-spherical clusters because it relies directly on
Euclidean distance. However, real-world data are often non-spherical and non-
Gaussian. A frequently used method for handling non-Gaussian data is graph
based manifold learning. It constructs a similarity graph of the data and then
projects them according to these similarities from the original manifold into
a new manifold where the data can be more effectively clustered. An
illustration of graph based manifold learning is shown in Fig. 1.

A key point for graph based manifold learning is graph construction.
Membership degree $u_{ij}$ in FCM denotes the probability of the $i$-th sample
belonging to the $j$-th cluster, but it can also be used to reveal the latent
relationships between samples. Therefore, it is possible to construct a new
similarity graph, based on the membership degrees, to help complete the
original similarity graph. If the update equation of cluster center $v_{j}$
can be represented as
$v_{j}={\sum_{i=1}^{n}u_{ij}x_{i}}/{\sum_{i=1}^{n}u_{ij}}$, we have the
following equation.

$\begin{gathered}\sum_{i=1}^{n}\sum_{j=1}^{c}u_{ij}||x_{i}-v_{j}||_{2}^{2}\mathop{=}Tr\left[X(I_{n}-UBU^{T})X^{T}\right]\end{gathered}$
(11)

where $X=[x_{1},x_{2},...,x_{n}]\in\mathbb{R}^{d\times n}$ is the data matrix,
$U\in\mathbb{R}^{n\times c}$ is the membership degree matrix, and
$B\in\mathbb{R}^{c\times c}$ is a diagonal matrix with the $k$-th diagonal
element being $b_{kk}=1/\sum_{i=1}^{n}u_{ik}$. To concentrate on the main
idea, the proof for Eq. (11) is moved to the Appendix.

According to the graph theory proposed by Liu et al. [41], we know that the
matrix $I_{n}-UBU^{T}$ in Eq. (11) can be a Laplacian matrix on the anchor
graph, and the corresponding adjacency matrix is
$\\{\hat{W}|\hat{w}_{ij}=\sum_{k=1}^{c}u_{ik}u_{jk}/b_{kk}\\}$. Then we can
conclude that

$\begin{gathered}Tr\left[X(I_{n}-UBU^{T})X^{T}\right]=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\hat{w}_{ij}||x_{i}-x_{j}||_{2}^{2}\end{gathered}$
(12)

where $\hat{w}_{ij}$ reflects the relationship between $x_{i}$ and $x_{j}$.
Therefore, if we consider data matrix $X$ as a variable and denote it by
$\tilde{X}$, it is possible to project the data into a new manifold by
optimizing the following objective function.

$\begin{gathered}\min_{\tilde{X}}Tr\left[\tilde{X}(I_{n}-UBU^{T})\tilde{X}^{T}\right]\end{gathered}$
(13)

where $\tilde{X}\in\mathbb{R}^{\tilde{d}\times n}$ denotes the newly learned
data matrix, and $\tilde{d}$ denotes the dimension of the newly learned sample
$\tilde{x}_{i}$. Utilizing the objective function in Eq. (13) can make the
projected data more compact within the same cluster, but sometimes the learned
Laplacian matrix $I_{n}-UBU^{T}$ may be inaccurate and lead to incorrect
projection. Therefore, we attempt to introduce the normalized Laplacian matrix
$\hat{L}$ (see the definition in Notations) into the objective function in Eq.
(13) to help obtain a better manifold. The specific formulation is given as
follows.

$\begin{gathered}\min_{\tilde{X}}=Tr\left[\tilde{X}(I_{n}-UBU^{T})\tilde{X}^{T}\right]+\lambda
Tr(\tilde{X}\hat{L}\tilde{X}^{T})\end{gathered}$ (14)

where $\lambda\in\mathbb{R}^{+}$ is used to balance the influence of the
second term. Then, the objective function of the proposed AFCM (Adaptive Fuzzy
C-Means with graph embedding) model is shown as follows.

$\begin{gathered}\mathop{\min}\limits_{U,V,\gamma,\tilde{X}}\\!\sum\limits_{i=1}^{n}\\!\sum\limits_{j=1}^{c}\\!u_{ij}\gamma||\tilde{x}_{i}-{v_{j}}||_{2}^{2}+\lambda
Tr(\tilde{X}\hat{L}\tilde{X}^{T})\\\ \qquad\quad\ \
+u_{ij}\log{u_{ij}}-n\log{\gamma^{\frac{\tilde{d}}{2}}},\\\ {\rm{}}{\rm s.t.}\
{\rm{}}\tilde{X}\tilde{X}^{T}=I_{\tilde{d}}\,,\mathop{\sum}\limits_{j=1}^{c}{u_{ij}}=1,\
{\rm{}}0<{u_{ij}}<1\end{gathered}$ (15)

where $\tilde{d}$ is the dimension of the projected sample $\tilde{x_{i}}$,
and in this paper we directly set $\tilde{x_{i}}=c$, and the orthogonal
constraint $\tilde{X}\tilde{X}^{T}=I_{\tilde{d}}$ is introduced to avoid
trivial solutions. Note that the model in Eq. (10) can be viewed as a
degenerate form of the proposed model in Eq. (15).

###  III-B Optimization

There are four variables to be updated for the proposed objective function in
Eq. (15).

When we update $U$ while keeping other variables fixed, the objective function
in Eq. (15) can be reformulated as

$\begin{gathered}\min_{U}\sum_{i=1}^{n}{\sum_{j=1}^{c}{u_{ij}\gamma||(\tilde{x}_{i}-v_{j})||_{2}^{2}+u_{ij}\log\left(u_{ij}\right)}}\\\
{\rm s.t.}\mathrm{ }\sum_{j=1}^{c}{u_{ij}}=1,\mathrm{ }0<u_{ij}<1\\\
\end{gathered}$ (16)

An usual way to solve problem in Eq. (16) is using the Lagrange multiplier
method [42]. The Lagrange function is given as

$\begin{gathered}L\left(U,\eta\right)=\sum_{i=1}^{n}\sum_{j=1}^{c}u_{ij}\gamma||(\tilde{x}_{i}-v_{j})||_{2}^{2}\qquad\
\ \\\
\qquad+u_{ij}\log\left(u_{ij}\right)+\sum_{i=1}^{n}{\eta_{i}(\sum_{j=1}^{c}{u_{ij}}-1)}\end{gathered}$
(17)

By setting the derivative of the Lagrange function to zero with respective to
$u_{ij}$, and combining it with the constraint $\sum_{j=1}^{c}u_{ij}=1$, we
obtain the update solution of $u_{ij}$ as follows.

$u_{ij}=\frac{\exp\left\\{-\gamma||(\tilde{x}_{i}-v_{j})||_{2}^{2}\right\\}}{\sum_{j=1}^{c}{\exp\left\\{-\gamma||(\tilde{x}_{i}-v_{j})||_{2}^{2}\right\\}}}$
(18)

When we update $V$ while keeping other variables fixed, the objective function
in Eq. (15) can be reformulated as

$\min_{V}\sum_{i=1}^{n}{\sum_{j=1}^{c}{u_{ij}||(\tilde{x}_{i}-v_{j})||_{2}^{2}}}$
(19)

By setting the derivative of the objective function in Eq. (19) to zero with
respect to $v_{j}$ we obtain the update equation of $v_{j}$ as follows.

$v_{j}=\frac{\sum_{i=1}^{n}{u_{ij}\tilde{x}_{i}}}{\sum_{i=1}^{n}{u_{ij}}}$
(20)

When we update $\gamma$ while keeping other variables fixed, the objective
function in Eq. (15) can be reformulated as

$\min_{\gamma}\sum_{i=1}^{n}{\sum_{j=1}^{c}{u_{ij}\gamma||(\tilde{x}_{i}-v_{j})||_{2}^{2}-n\log\gamma^{\frac{\tilde{d}}{2}}}}$
(21)

By setting the derivative of the objective function in Eq. (21) to zero with
respect to $\gamma$ we obtain the update equation of $\gamma$ as follows.

$\gamma=\,\,\frac{\frac{1}{2}\tilde{d}n}{\sum_{i=1}^{n}{\sum_{j=1}^{c}{u_{ij}||(\tilde{x}_{i}-v_{j})||_{2}^{2}}}}$
(22)

When we update $\tilde{X}$ while keeping other variables fixed, the objective
function in Eq. (15) can be reformulated as

$\displaystyle\min_{\tilde{X}}\sum_{i=1}^{n}{\sum_{j=1}^{c}{u_{ij}\gamma||\tilde{x}_{i}-v_{j}||_{2}^{2}}}+\lambda
Tr(\tilde{X}\hat{L}\tilde{X}^{T})$ (23) $\displaystyle\Leftrightarrow$
$\displaystyle\min_{\tilde{X}}\gamma
Tr\left[\tilde{X}(I_{n}-UBU^{T})\tilde{X}^{T}\right]+\lambda
Tr(\tilde{X}\hat{L}\tilde{X}^{T})$ $\displaystyle\Leftrightarrow$
$\displaystyle\min_{\tilde{X}}Tr\left\\{\tilde{X}\left[\gamma(I_{n}-UBU^{T})+\lambda\hat{L}\right]\tilde{X}^{T}\right\\}$
$\displaystyle\qquad\qquad\quad\mathrm{s.t.}\ \
\tilde{X}\tilde{X}^{T}=I_{\tilde{d}}\mathrm{ }$

The proof for Eq. (23) is similar to that for Eq. (11), which has been
provided in the Appendix. According to the Rayleigh quotient [43], the problem
in Eq. (23) can be solved by selecting the $c$ minumum eigenvectors of matrix
$\gamma(I_{n}-UBU^{T})+\lambda\hat{L}$.

Up to this point, the optimization process has been completed. Algorithm 1
presents the pseudo code for optimizing the AFCM model defined in Eq. (15).
Algorithm 2 presents the pseudo code for optimizing the degenerate AFCM model
defined in Eq. (10).

Algorithm 1 Algorithm for AFCM in Eq. (15)

1: Input: Data matrix $X$, cluster number $c$, parameter $\lambda$, and
normalized Laplacian matrix $\hat{L}$.

2: Initialization: Membership degree matrix $U$, cluster center $V$, adaptive
hyper-parameter $\gamma$ and projected dimension $\tilde{d}=c$.

3: while not converge do

4: $\tilde{X}$  $\leftarrow$  ${\rm eigenvector}$
[$\gamma(I_{n}-UDU^{T})+\lambda\hat{L}$, $c$ smallest vectors];

5: Update $v_{j}$ by Eq. (20);

6: Update $\gamma$ by Eq. (22);

7: Update $u_{ij}$ by Eq. (18);

8: end while

9: Output: membership degree matrix $U$.

Algorithm 2 Algorithm for degenerated AFCM in Eq. (10)

1: Input: Data matrix $X$ and cluster number $c$.

2: Initialization: Membership degree matrix $U$, projected data matrix
$\tilde{X}=X$ and projected dimension $\tilde{d}=d$.

3: while not converge do

4: Update $v_{j}$ by Eq. (20);

5: Update $\gamma$ by Eq. (22);

6: Update $u_{ij}$ by Eq. (18);

7: end while

8: Output: membership degree matrix $U$.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 2: Clustering results on toy datasets. (a) and (b) depict the
clustering outcomes of FCM. (c) and (d) show the clustering results of
degenerate AFCM. (e)-(h) present the clustering results of AFCM, which
projects data from the original manifold into a newly learned manifold and
perform clustering in this new manifold rather than the original manifold.

###  III-C Construction of the Affinity Matrix

For graph embedded methods, it is important to construct a proper affinity
matrix. In this paper, we use the Gaussian kernel to construct the affinity
matrix as follows.

$\begin{gathered}w_{ij}=\begin{cases}\exp(-\frac{\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\|_{2}^{2}}{2\sigma^{2}})&\text{if
}{x}_{j}\in\mathcal{N}({x}_{i})\\\
0,&\text{otherwise}\end{cases}\end{gathered}$ (24)

where $\sigma$ is a predefined scalar, $\mathcal{N}({x}_{i})$ denotes the set
of the $k$ nearest neighbour of $x_{i}$. In this paper, we set the value of
$\sigma=2$.

###  III-D Computational Complexity Analysis

Let $n$ represent the number of samples, $c$ represent the number of clusters,
$d$ and $\tilde{d}$ represent the original dimension and the projected
dimension, and $t$ represent the number of iterative steps. For Algorithm 1,
in each iterative step, the computational complexity of updating $U$ is
$\mathcal{O}(nc\tilde{d})$, which is the same as that of updating $V$ and
$\gamma$. Then the computational complexity of updating $\tilde{X}$ focuses on
performing eigenvalue decomposition, which is $\mathcal{O}(n^{3})$. Therefore,
the overall computational complexity of the proposed AFCM method in Algorithm
1 is $\mathcal{O}(tn^{3}+3tnc\tilde{d})$, which can be simplified to
$\mathcal{O}(tn^{3})$. For Algorithm 2, since $\tilde{X}$ is not updated, the
algorithm operates in the original dimension $d$, resulting in a total
computational complexity of $\mathcal{O}(tncd)$.

TABLE I: Description of data sets. Data set | Samples | Dimensions | Clusters
---|---|---|---
Iris | 150 | 4 | 3
Breast | 699 | 10 | 2
Vehicle | 846 | 18 | 4
UPPS | 1854 | 256 | 10
Jaffe50 | 213 | 1024 | 10
warpPIE10P | 210 | 2420 | 10
Olivetti | 900 | 2500 | 10
ORL64x64 | 400 | 4096 | 40
Pose07 | 1629 | 4096 | 68
Pose29 | 1632 | 4096 | 68

##  IV Experiment

###  IV-A Description of Datasets

In this subsection, we provide a description of the experimental datasets. Ten
real-world datasets are used in experiments, including
Iris111https://archive.ics.uci.edu, Breast11footnotemark: 1,
Vehicle11footnotemark: 1,
USPS222http://www.cad.zju.edu.cn/home/dengcai/Data/MLData.html,
Jaffe50333https://www.kaggle.com/,
warpPIE10P444https://jundongl.github.io/scikit-feature/datasets.html,
Olivetti11footnotemark: 1, ORL64x6422footnotemark: 2,
Pose07555https://www.ri.cmu.edu/publications/the-cmu-pose-illumination-and-
expression-pie-database/, and Pose2955footnotemark: 5. The details of these
real-world datasets are given in Table I.

TABLE II: Clustering results for AFCM on ten real-world data sets (average ACC, NMI and ARI $\pm$ standard deviations$\times$1E+2). The bold characters are the optimal results. Dataset | Metric | FCM | FCM-ER | SC | RSFKM | CDKM | FKPS | FCAG | AFCM
---|---|---|---|---|---|---|---|---|---
Iris | ACC | 88.73($\pm$0.20) | 89.33($\pm$0.00) | 94.67($\pm$0.00) | 88.67($\pm$0.00) | 88.67($\pm$2.58) | 92.00($\pm$0.00) | 95.47($\pm$2.40) | 96.13($\pm$1.60)
NMI | 73.01($\pm$0.37) | 73.64($\pm$0.00) | 85.88($\pm$0.00) | 75.48($\pm$0.63) | 73.64($\pm$0.00) | 79.82($\pm$0.00) | 86.32($\pm$3.36) | 87.49($\pm$2.89)
ARI | 71.64($\pm$0.41) | 72.78($\pm$0.00) | 78.29($\pm$0.02) | 75.60($\pm$0.00) | 71.63($\pm$0.00) | 78.74($\pm$0.00) | 87.48($\pm$5.78) | 89.07($\pm$3.93)
Breast | ACC | 94.99($\pm$0.00) | 96.28($\pm$0.00) | 96.04($\pm$0.00) | 95.28($\pm$0.00) | 95.28($\pm$0.00) | 96.28($\pm$0.00) | 95.99($\pm$0.00) | 96.57($\pm$0.00)
NMI | 69.15($\pm$0.00) | 75.60($\pm$0.00) | 74.36($\pm$4.55) | 70.53($\pm$0.00) | 70.49($\pm$0.00) | 75.76($\pm$0.00) | 74.17($\pm$0.00) | 78.00($\pm$0.00)
ARI | 80.74($\pm$0.28) | 85.54($\pm$0.15) | 84.63($\pm$0.00) | 81.79($\pm$0.00) | 81.79($\pm$0.00) | 85.60($\pm$0.00) | 84.46($\pm$0.00) | 86.64($\pm$0.00)
Vehicle | ACC | 37.12($\pm$0.13) | 36.90($\pm$0.51) | 41.80($\pm$0.57) | 38.09($\pm$1.69) | 36.87($\pm$0.52) | 38.75($\pm$0.76) | 42.08($\pm$3.56) | 46.74($\pm$2.83)
NMI | 10.53($\pm$1.58) | 10.60($\pm$1.70) | 16.15($\pm$2.42) | 10.59($\pm$0.75) | 10.59($\pm$1.71) | 11.79($\pm$2.76) | 14.63($\pm$4.44) | 19.81($\pm$1.82)
ARI | 7.86($\pm$0.83) | 8.36($\pm$0.21) | 11.15($\pm$0.01) | 9.11($\pm$0.37) | 7.88($\pm$0.87) | 8.55($\pm$0.00) | 11.17($\pm$2.27) | 15.75($\pm$2.25)
USPS | ACC | 65.78($\pm$1.56) | 64.53($\pm$1.42) | 69.32($\pm$2.48) | 66.04($\pm$3.59) | 66.59($\pm$2.67) | 66.42($\pm$2.28) | 74.02($\pm$2.48) | 72.07($\pm$4.32)
NMI | 62.91($\pm$0.91) | 62.72($\pm$0.04) | 73.61($\pm$1.52) | 64.00($\pm$1.33) | 62.67($\pm$1.28) | 63.80($\pm$1.60) | 71.17($\pm$1.08) | 77.59($\pm$1.58)
ARI | 54.11($\pm$1.38) | 53.53($\pm$1.32) | 62.83($\pm$2.99) | 55.04($\pm$3.13) | 53.94($\pm$1.79) | 55.27($\pm$2.00) | 62.85($\pm$1.15) | 65.67($\pm$4.21)
Jaffe50 | ACC | 92.77($\pm$0.00) | 84.55($\pm$3.30) | 86.43($\pm$2.96) | 86.90($\pm$3.60) | 77.65($\pm$6.64) | 42.18($\pm$2.46) | 89.95($\pm$3.57) | 94.93($\pm$3.86)
NMI | 92.27($\pm$0.00) | 89.75($\pm$2.70) | 90.38($\pm$1.34) | 89.47($\pm$2.76) | 85.76($\pm$3.28) | 48.00($\pm$2.77) | 92.33($\pm$2.14) | 95.20($\pm$2.15)
ARI | 85.88($\pm$0.00) | 79.78($\pm$5.15) | 82.09($\pm$0.00) | 79.67($\pm$2.50) | 72.09($\pm$6.00) | 49.09($\pm$2.87) | 84.96($\pm$4.589) | 91.23($\pm$4.26)
warpPIE10P | ACC | 28.24($\pm$1.76) | 62.00($\pm$5.52) | 48.48($\pm$1.62) | 27.95($\pm$1.15) | 28.52($\pm$1.29) | 29.33($\pm$1.78) | 44.00($\pm$3.42) | 50.57($\pm$0.29)
NMI | 30.06($\pm$2.13) | 29.91($\pm$3.49) | 61.05($\pm$2.81) | 30.07($\pm$1.67) | 31.01($\pm$1.63) | 31.65($\pm$2.75) | 52.06($\pm$3.05) | 63.79($\pm$0.86)
ARI | 9.53($\pm$1.98) | 9.16($\pm$1.27) | 35.80($\pm$3.77) | 9.27($\pm$1.27) | 9.85($\pm$1.46) | 10.67($\pm$1.45) | 26.81($\pm$3.45) | 39.11($\pm$1.02)
Olivetti | ACC | 53.88($\pm$3.24) | 49.76($\pm$3.18) | 68.56($\pm$0.00) | 51.03($\pm$3.47) | 47.10($\pm$3.20) | 51.90($\pm$5.01) | 59.11($\pm$2.55) | 70.41($\pm$2.89)
NMI | 52.10($\pm$2.38) | 50.98($\pm$3.66) | 71.88($\pm$0.37) | 51.89($\pm$1.94) | 50.93($\pm$2.84) | 53.75($\pm$3.78) | 60.71($\pm$4.49) | 74.98($\pm$1.68)
ARI | 36.92($\pm$2.61) | 33.45($\pm$2.89) | 50.66($\pm$1.06) | 34.82($\pm$2.09) | 33.32($\pm$2.72) | 36.19($\pm$3.60) | 43.56($\pm$5.48) | 59.92($\pm$2.23)
ORL64x64 | ACC | 59.40($\pm$1.39) | 57.98($\pm$1.65) | 58.55($\pm$2.36) | 58.68($\pm$2.44) | 58.10($\pm$2.79) | 58.58($\pm$2.22) | 62.38($\pm$1.35) | 62.90($\pm$2.65)
NMI | 77.63($\pm$0.99) | 77.46($\pm$0.79) | 77.69($\pm$1.94) | 77.67($\pm$0.88) | 76.82($\pm$1.38) | 77.74($\pm$1.02) | 81.75($\pm$0.88) | 80.68($\pm$0.46)
ARI | 46.00($\pm$1.25) | 45.29($\pm$2.05) | 41.64($\pm$5.30) | 45.956($\pm$2.20) | 44.09($\pm$2.82) | 46.10($\pm$1.97) | 53.94($\pm$2.14) | 50.94($\pm$1.58)
Pose07 | ACC | 15.95($\pm$0.44) | 15.49($\pm$0.27) | 28.86($\pm$0.83) | 15.02($\pm$0.34) | 16.24($\pm$0.67) | 15.43($\pm$0.48) | 23.20($\pm$0.77) | 32.42($\pm$1.07)
NMI | 42.86($\pm$0.36) | 42.28($\pm$0.22) | 53.54($\pm$1.24) | 42.04($\pm$0.45) | 42.23($\pm$0.64) | 42.10($\pm$0.48) | 54.34($\pm$0.43) | 60.54($\pm$0.62)
ARI | 8.80($\pm$0.31) | 5.84($\pm$0.22) | 11.26($\pm$1.24) | 5.25($\pm$0.21) | 5.84($\pm$0.44) | 5.49($\pm$0.37) | 12.52($\pm$0.54) | 18.58($\pm$1.31)
Pose29 | ACC | 17.12($\pm$0.29) | 15.40($\pm$0.37) | 26.65($\pm$0.42) | 15.92($\pm$0.55) | 17.46($\pm$0.53) | 15.70($\pm$0.43) | 25.03($\pm$0.65) | 32.61($\pm$1.85)
NMI | 44.01($\pm$0.47) | 42.72($\pm$0.63) | 43.49($\pm$2.01) | 43.59($\pm$0.31) | 42.25($\pm$0.64) | 41.35($\pm$0.47) | 55.69($\pm$0.30) | 59.15($\pm$1.11)
ARI | 6.89($\pm$0.25) | 6.05($\pm$0.32) | 4.69($\pm$1.10) | 6.21($\pm$0.33) | 6.36($\pm$0.44) | 5.72($\pm$0.38) | 13.98($\pm$0.38) | 17.51($\pm$1.46)

###  IV-B Experimental Settings

In this experiment, seven state-of-the-art clustering algorithms are selected
as the comparative algorithms to compared with the proposed AFCM algorithm.
These comparative algorithms include Fuzzy C-Means (FCM) [1], Fuzzy C-Means
with Entropy Regularization (FCM-ER) [3], Spectral Clustering (SC) [18],
Robust Sparse Fuzzy K-Means (RSFKM) [5], Coordinate Descent K-Means (CDKM)
[44], Fuzzy K-Means with Pattern Shrinking (FKPS) [28] and Fast Clustering
model with Anchor Guidance (FCAG)[22].

To ensure a consistent standardization of the data, each dataset is subjected
to normalization using the min-max normalization method. For fair comparison
with the competitors, based on their given parameter lists, we use the grid-
search method to select the best parameter values for each comparative
algorithm. There are two parameters in the proposed AFCM algorithm including
the number of the nearest neighbors $k$ in the normalized Laplacian matrix and
the regularization parameter $\lambda$, and their parameter lists are given as
$[3,4,5,6,8,10,12]$ and [1e-1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6], respectively.
Similar to the competitors, we also use the grid-search method to select
parameters for AFCM. Accuracy (ACC), Normalized Mutual Information (NMI), and
Adjusted Rand Index (ARI) are three commonly utilized metrics for assessing
the performance of clustering algorithms [45], and they are employed in our
paper as well.

###  IV-C Visualization Experiments on Toy Datasets

We conduct visualization experiments on two synthetic toy datasets to
demonstrate the capability of the proposed model on handling data with non-
Gaussian clusters. The first one consists of two spiral-shaped clusters, with
each cluster containing 500 samples. The second one consists of three ring-
shaped clusters, with each cluster containing 300 samples.

First, we perform FCM on the toy datasets and the clustering results are shown
in Fig. 2a and Fig. 2b. Obviously, FCM cannot handle this type of data. Then,
we show the clustering results of the degenerate AFCM in Fig. 2c and Fig. 2d.
Since the degenerate AFCM performs clustering directly in the original
manifold, it consequently fails as well. Finally, we present the clustering
results of the proposed AFCM that performs clustering in the learned manifold.
In Fig. 2e and Fig. 2g, we show the clustering results of AFCM in the original
manifold. In Fig. 2f and Fig. 2h, we show the clustering results of AFCM in
the learned manifold. By observing the clustering results, it is clear that
the proposed AFCM successfully projected the data from a non-Gaussian manifold
into a Gaussian manifold, and then successfully clustered the data.

###  IV-D Evaluation on Real-World Datasets

In order to further verify the effectiveness of the proposed AFCM method, we
compare it with seven state-of-the-art clustering methods on ten real-world
datasets. To ensure a fair comparison, we execute each algorithm ten times and
present the average results along with standard deviations. The clustering
outcomes are evaluated using three frequently used metrics: ACC, NMI, and ARI.
The clustering results are shown in Table II.

According to the clustering results in Table II, the proposed AFCM obtains the
optimal results on most datasets, except for the USPS and ORL64x64 datasets.
The comparative algorithm FCAG exhibits better performance than the proposed
AFCM on the USPS in terms of ACC, but AFCM outperforms FCAG in terms of NMI
and ARI on the same dataset. A similar situation also occurs with the ORL64x64
dataset. Therefore, while the performance of AFCM is comparable to FCAG on the
USPS and ORL64x64 datasets, it obtains the best clustering results on the
other eight datasets, validating the effectiveness of the proposed AFCM
method. Moreover, it is observed that the graph based method AFCM, SC, and
FCAG usually perform better than other non-graph based methods. This
observation indicates that graph embedding is an excellent method to help
improve clustering performance.

###  IV-E Ablation Experiments

In this subsection, we want to verify two facts through the ablation
experiment. The first one is that the parameter-free degenerate AFCM algorithm
can be an excellent alternative to K-Means. The second one is that
simultaneously performing clustering and manifold learning may obtain better
results than performing them separately.

TABLE III: Clustering results for the ablation experiments on eight real-world data sets (average ACC, NMI and ARI $\pm$ standard deviations$\times$1E+2). The bold characters are the optimal results. Ablation-1 and Ablation-2 adopt the two-stage strategy, whereas AFCM takes the one-stage strategy. Metric | Method | Iris | Breast | Vehicle | USPS | warpPIE10P | Olivetti | ORL64x64 | Pose07
---|---|---|---|---|---|---|---|---|---
ACC | Ablation-1 | 94.67($\pm$0.00) | 95.85($\pm$0.00) | 41.76($\pm$0.46) | 69.31($\pm$3.34) | 47.52($\pm$2.65) | 67.69($\pm$0.16) | 59.45($\pm$1.83) | 27.26($\pm$1.38)
Ablation-2 | 94.67($\pm$0.00) | 95.85($\pm$0.00) | 44.65($\pm$2.51) | 71.65($\pm$3.89) | 50.29($\pm$0.32) | 68.54($\pm$2.10) | 61.63($\pm$1.93) | 31.33($\pm$1.05)
AFCM | 96.13($\pm$1.60) | 96.57($\pm$0.00) | 46.74($\pm$2.83) | 72.07($\pm$4.32) | 50.57($\pm$0.29) | 70.41($\pm$2.89) | 62.90($\pm$2.65) | 32.42($\pm$1.07)
NMI | Ablation-1 | 85.88($\pm$0.00) | 73.45($\pm$0.00) | 16.08($\pm$0.00) | 75.04($\pm$2.46) | 58.90($\pm$3.17) | 70.69($\pm$1.59) | 76.98($\pm$1.62) | 52.64($\pm$1.84)
Ablation-2 | 85.88($\pm$0.00) | 73.45($\pm$0.00) | 18.01($\pm$1.21) | 76.39($\pm$2.43) | 62.52($\pm$1.27) | 71.72($\pm$2.82) | 80.72($\pm$0.78) | 59.93($\pm$0.76)
AFCM | 87.49($\pm$2.89) | 78.00($\pm$0.00) | 19.81($\pm$1.82) | 77.59($\pm$1.58) | 63.79($\pm$0.86) | 74.98($\pm$1.68) | 80.68($\pm$0.46) | 60.54($\pm$0.62)
ARI | Ablation-1 | 85.15($\pm$0.00) | 83.94($\pm$0.00) | 10.86($\pm$0.00) | 61.85($\pm$5.43) | 32.04($\pm$3.28) | 48.86($\pm$1.45) | 40.89($\pm$3.19) | 10.84($\pm$1.40)
Ablation-2 | 85.15($\pm$0.00) | 83.94($\pm$0.00) | 14.34($\pm$2.01) | 64.00($\pm$5.42) | 37.59($\pm$1.40) | 56.75($\pm$3.82) | 50.41($\pm$1.65) | 16.76($\pm$1.59)
AFCM | 89.07($\pm$3.93) | 86.64($\pm$0.00) | 15.75($\pm$2.25) | 66.57($\pm$4.21) | 39.11($\pm$1.02) | 59.92($\pm$2.23) | 50.94($\pm$1.58) | 18.58($\pm$1.31)

(a) Iris

(b) Breast

(c) Vehicle

(d) USPS

(e) warpPIE10P

(f) Olivetti

(g) ORL64x64

(h) Pose07

Figure 3: Convergence and ACC curves for AFCM on eight real-world datasets.

To verify this, we construct two comparative algorithms named as Ablation-1
and Ablation-2. Ablation-1 is a two-stage method, which first computes the $c$
minimum eigenvectors of the normalized Laplacian matrix $\hat{L}$ and then
performs K-Means on these eigenvectors. Ablation-2 is also a two-stage method,
which first computes the $c$ minimum eigenvectors of the normalized Laplacian
matrix $\hat{L}$ and then performs the degenerate AFCM on the eigenvectors. We
run each algorithm ten times, recording the average clustering results, which
are presented in Table III.

According to the results in Table III, it is observed that the performance of
Ablation-2 is better than that of Ablation-1, which means that the performance
of the degenerate AFCM is better than K-means. The degenerate AFCM has the
similar computational complexity with K-Means but exhibit a better performance
than K-Means. Therefore it is an excellent alternative to K-means.
Furthermore, the performance of the one-stage method AFCM is better than
Ablation-1 and Ablation-2 that adopts two-stage approaches, which means
perform clustering and manifold learning together is better than performing
them separately.

###  IV-F Convergence Experiments

In order to validate the convergence of the proposed AFCM algorithm, we
present the curves of the objective function values and the ACC values in
Figure 3. The experiment was conducted using eight real-world datasets, with
the maximum number of iterations set to 80.

From the results depicted in Figure 3, it is evident that the curves of the
objective function values for all eight datasets exhibit a monotonically
decreasing trend. This observation confirms the efficacy of the optimization
strategy employed in the AFCM model. Additionally, the ACC curves in Figure 3
show a general trend of increasing with the iterative steps, albeit not
strictly monotonic. There are instances where the ACC values may decrease
temporarily; however, upon convergence, the ACC values significantly surpass
those at the initial iterative step. This pattern validates the rationality
and effectiveness of the proposed AFCM model design.

Overall, the experimental results presented in Figure 3 demonstrate the
successful convergence and effectiveness of the AFCM algorithm across diverse
real-world datasets.

##  V Conclusions

In this paper, we propose a novel Adaptive Fuzzy C-Means with graph embedding
model (AFCM) that can automatically learn the membership degree hyper-
parameter and handle data with non-Gaussian clusters. By establishing the
equivalent connections between FCM with entropy regularization and the
generalized Gaussian mixture model, we reveal that the entropy regularization
hyper-parameter in FCM can be interpreted as the scale parameter in the
generalized Gaussian mixture model. Therefore, the entropy regularization
hyper-parameter can be learned in a similar way to the scale parameter in the
mixture model. Furthermore, by introducing the graph embedding regularization,
the proposed AFCM model is capable of handling data with non-Gaussian
clusters. Note that, the proposed method perform clustering and manifold
learning simultaneously, which is better than performing them separately, and
we validate this by experiments. Moreover, the proposed AFCM can degenerate
into a parameter-free FCM. This simplified AFCM variant maintains a
computational complexity of $\mathcal{O}(ncd)$, comparable to K-Means, yet
outperforms K-Means in performance. However, while the proposed AFCM achieves
good performance, it still relies on the original FCM to conduct clustering in
the newly learned manifold. In the future, we aim to integrate more advanced
techniques into AFCM to enhance its clustering performance in the new
manifold.

## Proof for proposition 1

In this section, we presents a rigorous mathematical proof of Proposition 1.
To facilitate the readers, we rewritten the equivalent objective function of
the generalized Gaussian mixture model as follows.

$\begin{gathered}\mathop{\min}\limits_{U,\alpha,V,\Sigma,\beta,m}\mathop{\sum}\limits_{i=1}^{n}\mathop{\sum}\limits_{j=1}^{c}{u_{ij}}\bigg{\\{}m{{{{\left[{{{(x_{i}-{v_{j}})}^{T}}{\Sigma_{j}^{-1}}(x_{i}-{v_{j}})}\right]}}}^{\beta}}\\\
\quad+\frac{1}{2}\log|{\Sigma_{j}}|-\log{\alpha_{j}}-\log\frac{{\beta\Gamma(\frac{d}{2}){m^{\frac{d}{{2\beta}}}}}}{{{\pi^{\frac{d}{2}}}\Gamma(\frac{d}{{2\beta}})}}+\log{u_{ij}}\bigg{\\}},\\\
\ \ {\rm s.t.}\ \ \mathop{\sum}\limits_{j=1}^{c}{\alpha_{j}}=1,\ \
0<{\alpha_{j}}<1,\\\ \ \ \ \ \ \ \ \ \
\mathop{\sum}\limits_{j=1}^{c}{u_{ij}}=1,\ \ 0<{u_{ij}}<1\end{gathered}$ (25)

where $u_{ij}$ is the membership degree denoting the probability of sample
$x_{i}$ being assigned to the $j$-th cluster,
$\alpha=\\{{\alpha_{1}},{\alpha_{2}},..,{\alpha_{c}}\\}$,
$V=\\{{v_{1}},{v_{2}},..,{v_{c}}\\}$ and
$\Sigma=\\{{\Sigma_{1}},{\Sigma_{2}},..,{\Sigma_{c}}\\}$, denote the sets of
mixing coefficients, means and scale matrices, and $\beta$ and $m$ denotes the
shape parameter and the scale parameter in the generalized Gaussian mixture
model.

We will demonstrate that the update equations for the equivalent objective
function outlined in Eq. (25) coincide with those derived for the log-
likelihood function of the generalized Gaussian mixture model.

###  -A The maximum log-likelihood function

Let $x\in\mathbb{R}^{d}$ be a $d$-dimensional random vector, and the
probability density function of the generalized Gaussian distribution is given
as below.

$\begin{gathered}g(x|\theta)\\!=\\!\frac{{\beta\Gamma(\frac{d}{2}){m^{\frac{d}{{2\beta}}}}}}{{{\pi^{\frac{d}{2}}}\Gamma(\frac{d}{{2\beta}})}}|\Sigma{|^{-\frac{1}{2}}}\exp\\!\left\\{\\!-m{{\left[{{{(x\\!-\\!v)}^{T}}{\Sigma^{-1}}(x\\!-\\!v)}\right]}^{\beta}}\\!\right\\}\\\
\end{gathered}$ (26)

where $\theta=\\{v,\Sigma,\beta,m\\}$ denotes the set of parameters,
$v\in\mathbb{R}^{d}$ denotes the mean, $\Sigma\in\mathbb{R}^{d\times d}$
denotes the positive definite covariance matrix, $\beta\in\mathbb{R}^{+}$
denotes the shape parameter, and $m$ denotes the scale parameter.

Based on the probability density function the generalized Gaussian
distribution depicted in Eq. (26), the probability density function of the
generalized Gaussian mixture model can be defined as

$\begin{gathered}f(x|\Theta)=\mathop{\sum}\limits_{j=1}^{c}{\alpha_{j}}g(x|{\theta_{j}}),\
\ {\rm s.t.}\sum_{j=1}^{c}\alpha_{j}=1\end{gathered}$ (27)

where $\Theta=\\{\alpha,V,\Sigma,\beta,m\\}$ denotes the set of all parameters
in the generalized Gaussain mixture model,
${\theta_{j}}=\left\\{{{v_{j}},{\Sigma_{j}},\beta,m}\right\\}$ denotes the
parameter set of the $j$-th component,
$\alpha=\\{{\alpha_{1}},{\alpha_{2}},..,{\alpha_{c}}\\}$ denotes the set of
mixing coefficients, and $c$ denotes the number of components.

Then the expression of the log-likelihood function for the generalized
Gaussian mixture model is presented as follows.

$\begin{gathered}L(\Theta|X)\\!\\!=\\!\\!\mathop{\sum}\limits_{i=1}^{n}\\!\log
f({x_{i}}|\Theta)\\!=\\!\\!\mathop{\sum}\limits_{i=1}^{n}\\!\log\\!\mathop{\sum}\limits_{j=1}^{c}\\!{\alpha_{j}}g({x_{i}}|{\theta_{j}}),\\\
{\rm s.t.\ \ }\sum_{j=1}^{c}\alpha_{j}=1\end{gathered}$ (28)

###  -B EM for problem in (28)

Owing to the combination of logarithm and sum within the problem depicted in
Eq. (28), direct optimization becomes challenging, necessitating the
utilization of the EM algorithm. There are two main steps in the EM, including
E-step and M-step.

In E-step: According to the log-likelihood function in Eq. (28) one has

$\displaystyle
p(j|{x_{i}},{\Theta^{t-1}})\\!=\\!\frac{{\alpha_{j}^{t-1}g({x_{i}}|\theta_{j}^{t-1})}}{{\mathop{\sum}\limits_{j=1}^{c}\alpha_{j}^{t-1}g({x_{i}}|\theta_{j}^{t-1})}}$
(29)
$\displaystyle\\!=\\!\frac{{{\alpha_{j}^{t-1}}|{\Sigma_{j}^{t-1}}\\!{|^{-\frac{1}{2}}}\\!\exp\left\\{\\!{-m^{t-1}(d_{ij})^{t-1}}\\!\right\\}}}{{\mathop{\sum}\limits_{j=1}^{c}\\!\\!{{\alpha_{j}^{t-1}}|{\Sigma_{j}^{t-1}}\\!{|^{-\frac{1}{2}}}\\!\exp\left\\{\\!{-m^{t-1}(d_{ij})^{t-1}}\\!\right\\}}}}$

where
$(d_{ij})^{t-1}={{{{{{\left[{{{(x_{i}\\!-\\!{v_{j}^{t-1}})}^{T}}{(\Sigma_{j}^{t-1})^{-1}}(x_{i}\\!-\\!{v_{j}^{t-1}})}\right]}}}}}^{\beta^{t-1}}}$;
symbols $\Theta^{t-1}$ and $\theta^{t-1}_{j}$ denote the parameter sets
estimated in last iteration, and $p(j|{x_{i}},{\Theta^{t-1}})$ can be
considered as the posterior probability of the $i$-th sample being generated
by the $j$-th mixture component.

In M-step: Fix $p(j|{x_{i}},{\Theta^{t-1}})$ and optimize the following
problem.

$\displaystyle\mathop{\max}\limits_{\Theta}Q(\Theta,\\!{\Theta^{t\\!-\\!1}}\\!)\\!=\\!\mathop{\max}\limits_{\Theta}\\!\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{c}{p(j\left|{{x_{i}},{\Theta^{t\\!-\\!1}})}\\!\right.\log{\alpha_{j}}g({x_{i}}\left|{{\theta_{j}})}\right.}$
(30) $\displaystyle=$
$\displaystyle\mathop{\max}\limits_{\Theta}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{c}p(j\left|{{x_{i}},{\Theta^{t-1}})}\right.\log\bigg{\\{}\alpha_{j}{\frac{{\beta\Gamma(\frac{d}{2}){m^{\frac{d}{{2\beta}}}}}}{{{\pi^{\frac{d}{2}}}\Gamma(\frac{d}{{2\beta}})}}}\times$
$\displaystyle\qquad\ \
|\Sigma_{j}|^{\frac{-1}{2}}\exp\left[-m\left((x_{i}-v_{j})^{T}\Sigma_{j}^{-1}(x_{i}-v_{j})\right)^{\beta}\right]\bigg{\\}}$
$\displaystyle\Leftrightarrow$
$\displaystyle\mathop{\min}\limits_{\Theta}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{c}p(j\left|{{x_{i}},{\Theta^{t-1}})}\right.\bigg{\\{}m{{\left[{{{{(x_{i}-{v_{j}})}^{T}}{\Sigma_{j}^{-1}}(x_{i}-{v_{j}})}}\right]}^{\beta}}$
$\displaystyle\qquad\ \
+\frac{1}{2}\log|{\Sigma_{j}}|-\log{\alpha_{j}}-\log{\frac{{\beta\Gamma(\frac{d}{2}){m^{\frac{d}{{2\beta}}}}}}{{{\pi^{\frac{d}{2}}}\Gamma(\frac{d}{{2\beta}})}}}\bigg{\\}}$
$\displaystyle\qquad\qquad\quad\ {\rm s.t.}\ \
\mathop{\sum}\limits_{j=1}^{c}{\alpha_{j}}=1,\ \ 0<{\alpha_{j}}<1,\ \ $

where $\Theta=\\{\alpha,V,\Sigma,\beta,m\\}$.

Through iterative execution of the E-step and M-step until converging, one can
obtain a suitable local minimum for the log-likelihood function presented in
Eq. (28).

###  -C Proof for equivalence

The proof for the equivalence between the objective function in Eq. (25) and
the log-likelihood function in Eq. (28) is mainly divided into two parts. In
the first part, we prove that $u_{ij}$ in Eq. (25) have the same update
equation with $p(j|{x_{i}},{\Theta^{t-1}})$ in Eq. (29), where $u_{ij}$
denotes the membership degree and $p(j|{x_{i}},{\Theta^{t-1}})$ is the
posterior probability derived from the E-step. In the second part, we prove
that the equivalent objective function in Eq. (25) with $U$ being fixed has
the same form with the Q function in Eq. (30).

In the first part: When we update $U$ with the other variables being fixed,
the objective function in Eq. (25) can be reformulated as follows.

$\begin{gathered}\mathop{\min}\limits_{U}\mathop{\sum}\limits_{i=1}^{n}\mathop{\sum}\limits_{j=1}^{c}{u_{ij}}\bigg{\\{}m{{{{\left[{{{(x_{i}-{v_{j}})}^{T}}{\Sigma_{j}^{-1}}(x_{i}-{v_{j}})}\right]}}}^{\beta}}\\\
\quad\ \
+\frac{1}{2}\log|{\Sigma_{j}}|-\log{\alpha_{j}}+\log{u_{ij}}\bigg{\\}},\\\ \ \
\ \ \ {\rm s.t.}\ \ \mathop{\sum}\limits_{j=1}^{c}{u_{ij}}=1,\ \
0<{u_{ij}}<1\end{gathered}$ (31)

We remove the inequality constraints and take the Lagrange multiplier method
to optimize the objective function in Eq. (31). The corresponding Lagrange
function is constructed as

$\begin{gathered}L(U,\gamma)=\mathop{\sum}\limits_{i=1}^{n}\mathop{\sum}\limits_{j=1}^{c}{u_{ij}}\bigg{\\{}m{{{{\left[{{{(x_{i}-{v_{j}})}^{T}}{\Sigma_{j}^{-1}}(x_{i}-{v_{j}})}\right]}}}^{\beta}}\\\
+\frac{1}{2}\log|{\Sigma_{j}}|-\log{\alpha_{j}}+\log{u_{ij}}\bigg{\\}}+\mathop{\sum}\limits_{i=1}^{n}\eta_{i}(\mathop{\sum}\limits_{j=1}^{c}{u_{ij}}-1)\end{gathered}$
(32)

where $\eta=\\{\eta_{1},\eta_{2},...,\eta_{n}\\}$ is the set of Lagrange
multipliers. By setting the derivative of the Lagrange function in Eq. (32) to
zero with respect to $u_{ij}$ we have

$\displaystyle\frac{\partial L(U,\eta)}{\partial
u_{ij}}=m{\left[{{{(x_{i}-{v_{j}})}^{T}}\Sigma_{j}^{-1}(x_{i}-{v_{j}})}\right]^{\beta}}$
(33)
$\displaystyle+\frac{1}{2}\log|{\Sigma_{j}}|-\log{\alpha_{j}}+\log{u_{ij}}+1+{\eta_{i}}=0$

Then according to Eq. (33) we can obtain

$u_{ij}\\!=\\!\frac{{{\alpha_{j}}|{\Sigma_{j}}{|^{-\frac{1}{2}}}\exp\left\\{-m{{\left[{{{({x_{i}}\\!-\\!{v_{j}})}^{T}}\Sigma_{j}^{-1}({x_{i}}\\!-\\!{v_{j}})}\right]}^{\beta}}\right\\}}}{{\exp(1+{\eta_{i}})}}$
(34)

By combining Eq. (34) with the constraint $\sum_{j=1}^{c}u_{ij}=1$, we can
obtain

$\begin{gathered}\exp(1+\eta_{i})\\!=\\!\\!\mathop{\sum}\limits_{j=1}^{c}\\!{\alpha_{j}}|{\Sigma_{j}}|^{\frac{{-1}}{2}}\times\quad\qquad\qquad\qquad\\\
\quad\qquad\qquad\exp\left\\{-m{{\left[{{{(x_{i}-{v_{j}})}^{T}}\Sigma_{j}^{-1}\\!(x_{i}-{v_{j}})}\right]}^{\beta}}\right\\}\end{gathered}$
(35)

Substitute $\exp\\{1+\eta_{i}\\}$ in Eq. (35) back into Eq. (34) and then we
can obtain

$u_{ij}\\!\\!=\\!\\!\frac{{{\alpha_{j}}|{\Sigma_{j}}{|^{\frac{{-1}}{2}}}\\!\exp\left\\{\\!-m{{\left[{{{(x_{i}\\!-\\!{v_{j}})}^{T}}\Sigma_{j}^{-1}(x_{i}\\!-\\!{v_{j}})}\right]}^{\beta}}\right\\}}}{{\mathop{\sum}\limits_{j=1}^{c}\\!\\!{\alpha_{j}}|{\Sigma_{j}}{|^{\frac{{-1}}{2}}}\\!\exp\left\\{\\!-m{{\left[{{{(x_{i}\\!-\\!{v_{j}})}^{T}}\Sigma_{j}^{-1}(x_{i}\\!-\\!{v_{j}})}\right]}^{\beta}}\right\\}}}$
(36)

The solution of in Eq. (36) satisfies the inequality constraint $0<u_{ij}<1$,
and hence it is a suitable update equation for $u_{ij}$. By comparing the
update equation of $u_{ij}$ in Eq. (36) and the update equation of
$p(j|{x_{i}},{\Theta^{t-1}})$ in Eq. (29), we can find they have the same
form. Therefore, $u_{ij}$ can be seen as an equivalence of
$p(j|{x_{i}},{\Theta^{t-1}})$.

In the second part: When we fix $U$ to update the other variables, the
objective function in Eq. (25) can be reformulated as follows.

$\begin{gathered}\mathop{\min}\limits_{\alpha,V,\Sigma,\beta,m}\mathop{\sum}\limits_{i=1}^{n}\mathop{\sum}\limits_{j=1}^{c}{u_{ij}}\bigg{\\{}m{{{{\left[{{{(x_{i}-{v_{j}})}^{T}}{\Sigma_{j}^{-1}}(x_{i}-{v_{j}})}\right]}}}^{\beta}}\\\
\qquad\quad+\frac{1}{2}\log|{\Sigma_{j}}|-\log{\alpha_{j}}-\log\frac{{\beta\Gamma(\frac{d}{2}){m^{\frac{d}{{2\beta}}}}}}{{{\pi^{\frac{d}{2}}}\Gamma(\frac{d}{{2\beta}})}}\bigg{\\}},\\\
{\rm s.t.}\ \ \mathop{\sum}\limits_{j=1}^{c}{\alpha_{j}}=1,\ \
0<{\alpha_{j}}<1\end{gathered}$ (37)

By comparing the objective function in Eq. (37) and the Q function in Eq.
(30), it is observed that they have the same form and hence their variables
share the same update equations as well.

Up to this point, the proof for the equivalence between the objective function
in Eq. (25) and the log-likelihood function in Eq. (28) has been completed.

## proof for Eq. (11)

To facilitate the readers, we first rewrite Eq. (11) as below.

$\begin{gathered}\sum_{i=1}^{n}\sum_{j=1}^{c}u_{ij}||x_{i}-v_{j}||_{2}^{2}\mathop{=}Tr\left[X(I_{n}-UBU^{T})X^{T}\right]\end{gathered}$
(38)

where $X=[x_{1},x_{2},...,x_{n}]\in\mathbb{R}^{d\times n}$ denotes the data
matrix, $u_{ij}$ denotes the membership degree satisfying
$\sum_{j=1}^{c}u_{ij}=1$, and $B\in\mathbb{R}^{c\times c}$ is a diagonal
matrix with the $k$-th diagonal element $b_{kk}=1/\sum_{i=1}^{n}u_{ik}$, and
$v\in\mathbb{R}^{d}$ denotes the $j$-th cluster center. Moreover, the update
equation for $v_{j}$ is supposed to be

$v_{j}=\frac{\sum_{i=1}^{n}u_{ij}x_{i}}{\sum_{i=1}^{n}u_{ij}}=\sum_{i=1}^{n}{\left(\frac{u_{ij}}{\sum_{l=1}^{n}{u_{lj}}}\right)x_{i}}$
(39)

We define

$\begin{gathered}p_{ij}=\frac{u_{ij}}{\left(\sum_{l=1}^{n}{u_{lj}}\right)},\ \
P_{j}=\left(\begin{matrix}p_{1j}&&0\\\ &\ddots&\\\ 0&&p_{nj}\\\
\end{matrix}\right)\in\mathbb{R}^{n\times n}\end{gathered}$ (40)

where $P_{j}$ is a diagonal matrix with the $k$-th diagonal element being
$p_{kj}$. Then we have

$v_{j}=\sum_{i=1}^{n}p_{ij}x_{i}$ (41)

Let us now direct the attention to the left-hand side of Eq. (38).

$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{c}u_{ij}||x_{i}-v_{j}||_{2}^{2}$ (42)
$\displaystyle=$ $\displaystyle
Tr\left[\sum_{i=1}^{n}{\sum_{j=1}^{c}{u_{ij}(x_{i}-v_{j})(x_{i}-v_{j})^{T}}}\right]$
$\displaystyle=$ $\displaystyle
Tr\left[\sum_{j=1}^{c}{\left(\sum_{l=1}^{n}{u_{lj}}\right)\sum_{i=1}^{n}{\frac{u_{ij}}{\left(\sum_{l=1}^{n}{u_{lj}}\right)}(x_{i}-v_{j})(x_{i}-v_{j})^{T}}}\right]$
$\displaystyle=$ $\displaystyle
Tr\left[\sum_{j=1}^{c}{\left(\sum_{l=1}^{n}{u_{lj}}\right)\sum_{i=1}^{n}{p_{ij}(x_{i}-v_{j})(x_{i}-v_{j})^{T}}}\right]$

According to the definition of $p_{ij}$ and $P_{j}$ in Eq. (40) and the
definition of $v_{j}$ in Eq. (41), we can further conclude

$\displaystyle\sum_{i=1}^{n}{p_{ij}(x_{i}-v_{j})(x_{i}-v_{j})^{T}}$ (43)
$\displaystyle=$ $\displaystyle\left[X\left(I_{n}-P_{j}{\bf 1}{\bf
1}^{T}\right)\right]P_{j}\left[X\left(I_{n}-P_{j}{\bf 1}{\bf
1}^{T}\right)\right]^{T}$ $\displaystyle=$ $\displaystyle
X\left(I_{n}-P_{j}{\bf 1}{\bf 1}^{T}\right)P_{j}\left(I_{n}-{\bf 1}{\bf
1}^{T}P_{j}\right)X^{T}$ $\displaystyle=$ $\displaystyle
X\left(P_{j}-P_{j}{\bf 1}{\bf 1}^{T}P_{j}\right)\left(I_{n}-{\bf 1}{\bf
1}^{T}P_{j}\right)X^{T}$ $\displaystyle=$ $\displaystyle
X\left(P_{j}-P_{j}{\bf 1}{\bf 1}^{T}P_{j}-P_{j}{\bf 1}{\bf
1}^{T}P_{j}+P_{j}{\bf 1}{\bf 1}^{T}P_{j}{\bf 1}{\bf 1}^{T}P_{j}\right)X^{T}$
$\displaystyle=$ $\displaystyle X\left(P_{j}-P_{j}{\bf 1}{\bf
1}^{T}P_{j}\right)X^{T}$

where ${\bf 1}\in\mathbb{R}^{n\times 1}$ is a vector with all elements being
equal to $1$. Substitute Eq. (43) back into Eq. (42) and then we have

$\displaystyle
Tr\left[\sum_{j=1}^{c}{\left(\sum_{l=1}^{n}{u_{lj}}\right)\sum_{i=1}^{n}{p_{ij}(x_{i}-v_{j})(x_{i}-v_{j})^{T}}}\right]$
(44) $\displaystyle=$ $\displaystyle
Tr\left[\sum_{j=1}^{c}{\left(\sum_{l=1}^{n}{u_{lj}}\right)X(P_{j}-P_{j}11^{T}P_{j})X^{T}}\right]$
$\displaystyle=$ $\displaystyle
Tr\left\\{X\left[\sum_{j=1}^{c}{\left(\sum_{l=1}^{n}{u_{lj}}\right)P_{j}-\sum_{j=1}^{c}{\left(\sum_{l=1}^{n}{u_{lj}}\right)}P_{j}11^{T}P_{j}}\right]X^{T}\right\\}$
$\displaystyle=$ $\displaystyle
Tr\left[X\left(I_{n}-UBU^{T}\right)X^{T}\right]$

where $B\in\mathbb{R}^{c\times c}$ is a diagonal matrix with the definition
given as below.

$B=\left(\begin{matrix}\frac{1}{\sum_{l=1}^{n}{u_{l1}}}&&0\\\ &\ddots&\\\
0&&\frac{1}{\sum_{l=1}^{n}{u_{lc}}}\\\ \end{matrix}\right)$ (45)

Up to this point, the proof for Eq. (11) has been completed.

## References

  * [1] J. C. Bezdek, _Pattern recognition with fuzzy objective function algorithms_. Springer Science & Business Media, 2013.
  * [2] J. Xue, F. Nie, R. Wang, and X. Li, “Iteratively reweighted algorithm for fuzzy $c$-means,” _IEEE Transactions on Fuzzy Systems_ , vol. 30, no. 10, pp. 4310–4321, 2022.
  * [3] R.-P. Li and M. Mukaidono, “A maximum-entropy approach to fuzzy clustering,” in _Proceedings of 1995 IEEE International Conference on Fuzzy Systems._ , vol. 4. IEEE, 1995, pp. 2227–2232.
  * [4] S. Miyamoto and K. Umayahara, “Fuzzy clustering by quadratic regularization,” in _Proceedings of 1998 IEEE International Conference on Fuzzy Systems Proceedings._ , vol. 2. IEEE, 1998, pp. 1394–1399.
  * [5] J. Xu, J. Han, K. Xiong, and F. Nie, “Robust and sparse fuzzy k-means clustering,” in _Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16_ , 2016, pp. 2224–2230.
  * [6] E. H. Ruspini, J. C. Bezdek, and J. M. Keller, “Fuzzy clustering: A historical perspective,” _IEEE Computational Intelligence Magazine_ , vol. 14, no. 1, pp. 45–55, 2019.
  * [7] X. Zhao, Y. Li, and Q. Zhao, “Mahalanobis distance based on fuzzy clustering algorithm for image segmentation,” _Digital Signal Processing_ , vol. 43, pp. 8–16, 2015.
  * [8] Q. Chen, W. Yu, X. Zhao, F. Nie, and X. Li, “Rooted mahalanobis distance based gustafson-kessel fuzzy c-means,” _Information Sciences_ , vol. 644, p. 118878, 2023.
  * [9] L. Chen, C. P. Chen, and M. Lu, “A multiple-kernel fuzzy c-means algorithm for image segmentation,” _IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)_ , vol. 41, no. 5, pp. 1263–1274, 2011.
  * [10] H. Lu, S. Liu, H. Wei, and J. Tu, “Multi-kernel fuzzy clustering based on auto-encoder for fmri functional network,” _Expert Systems with Applications_ , vol. 159, p. 113513, 2020.
  * [11] S. Zeng, X. Wang, X. Duan, S. Zeng, Z. Xiao, and D. Feng, “Kernelized mahalanobis distance for fuzzy clustering,” _IEEE Transactions on Fuzzy Systems_ , vol. 29, no. 10, pp. 3103–3117, 2020.
  * [12] W. Xia, Q. Gao, Q. Wang, X. Gao, C. Ding, and D. Tao, “Tensorized bipartite graph learning for multi-view clustering,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 45, no. 4, pp. 5187–5202, 2022\.
  * [13] W. Xia, T. Wang, Q. Gao, M. Yang, and X. Gao, “Graph embedding contrastive multi-modal representation learning for clustering,” _IEEE Transactions on Image Processing_ , vol. 32, pp. 1170–1183, 2023.
  * [14] H. Yang, Q. Gao, W. Xia, M. Yang, and X. Gao, “Multiview spectral clustering with bipartite graph,” _IEEE Transactions on Image Processing_ , vol. 31, pp. 3591–3605, 2022.
  * [15] H. Zhao, X. Yang, Z. Wang, E. Yang, and C. Deng, “Graph debiased contrastive learning with joint representation clustering.” in _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21_ , 2021, pp. 3434–3440.
  * [16] J. MacQueen _et al._ , “Some methods for classification and analysis of multivariate observations,” in _Proceedings of the fifth Berkeley symposium on mathematical statistics and probability_ , vol. 1, no. 14, 1967, pp. 281–297.
  * [17] A. Ng, M. Jordan, and Y. Weiss, “On spectral clustering: Analysis and an algorithm,” _Advances in neural information processing systems_ , vol. 14, 2001.
  * [18] U. Von Luxburg, “A tutorial on spectral clustering,” _Statistics and computing_ , vol. 17, pp. 395–416, 2007.
  * [19] F. Nie, X. Wang, and H. Huang, “Clustering and projected clustering with adaptive neighbors,” in _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2014, pp. 977–986.
  * [20] J. Han, K. Xiong, and F. Nie, “Orthogonal and nonnegative graph reconstruction for large scale clustering,” in _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17_ , 2017, pp. 1809–1815.
  * [21] S. Pei, F. Nie, R. Wang, and X. Li, “Efficient clustering based on a unified view of $k$-means and ratio-cut,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 14 855–14 866, 2020.
  * [22] F. Nie, J. Xue, W. Yu, and X. Li, “Fast clustering with anchor guidance,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2023.
  * [23] X. He and P. Niyogi, “Locality preserving projections,” _Advances in neural information processing systems_ , vol. 16, 2003.
  * [24] J. Zhou, W. Pedrycz, X. Yue, C. Gao, Z. Lai, and J. Wan, “Projected fuzzy c-means clustering with locality preservation,” _Pattern Recognition_ , vol. 113, p. 107748, 2021.
  * [25] J. Wang, S. Guo, F. Nie, and X. Li, “Local-global fuzzy clustering with anchor graph,” _IEEE Transactions on Fuzzy Systems_ , vol. 32, no. 1, pp. 188–202, 2024.
  * [26] F. Nie, C. Liu, R. Wang, Z. Wang, and X. Li, “Fast fuzzy clustering based on anchor graph,” _IEEE Transactions on Fuzzy Systems_ , vol. 30, no. 7, pp. 2375–2387, 2022.
  * [27] J. Wang, Z. Yang, X. Liu, B. Li, J. Yi, and F. Nie, “Projected fuzzy c-means with probabilistic neighbors,” _Information Sciences_ , vol. 607, pp. 553–571, 2022.
  * [28] X. Zhao, F. Nie, R. Wang, and X. Li, “Robust fuzzy k-means clustering with shrunk patterns learning,” _IEEE Transactions on Knowledge and Data Engineering_ , 2021.
  * [29] G. J. McLachlan, S. X. Lee, and S. I. Rathnayake, “Finite mixture models,” _Annual review of statistics and its application_ , vol. 6, pp. 355–378, 2019\.
  * [30] D. A. Reynolds _et al._ , “Gaussian mixture models.” _Encyclopedia of biometrics_ , vol. 741, no. 659-663, 2009.
  * [31] J. Liu, D. Cai, and X. He, “Gaussian mixture model with local consistency,” in _Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence AAAI-10_ , 2010.
  * [32] X. He, D. Cai, Y. Shao, H. Bao, and J. Han, “Laplacian regularized gaussian mixture model for data clustering,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 23, no. 9, pp. 1406–1418, 2011.
  * [33] F. Pascal, L. Bombrun, J.-Y. Tourneret, and Y. Berthoumieu, “Parameter estimation for multivariate generalized gaussian distributions,” _IEEE Transactions on Signal Processing_ , vol. 61, no. 23, pp. 5960–5971, 2013.
  * [34] M. Ahsanullah, B. G. Kibria, and M. Shakil, _Normal and student’s t distributions and their applications_. Springer, 2014, vol. 4.
  * [35] J. Zhang and F. Liang, “Robust clustering using exponential power mixtures,” _Biometrics_ , vol. 66, no. 4, pp. 1078–1086, 2010.
  * [36] U. J. Dang, R. P. Browne, and P. D. McNicholas, “Mixtures of multivariate power exponential distributions,” _Biometrics_ , vol. 71, no. 4, pp. 1081–1089, 2015.
  * [37] S. Kotz, “Multivariate distributions at a cross road,” in _A Modern Course on Statistical Distributions in Scientific Work_. Springer, 1975, pp. 247–270.
  * [38] K.-T. Fang, S. Kotz, and K. W. Ng, _Symmetric multivariate and related distributions_. Chapman and Hall/CRC, 2018\.
  * [39] S. Nadarajah, “The kotz-type distribution with applications,” _Statistics: A Journal of Theoretical and Applied Statistics_ , vol. 37, no. 4, pp. 341–358, 2003.
  * [40] J. A. Bilmes _et al._ , “A gentle tutorial of the em algorithm and its application to parameter estimation for gaussian mixture and hidden markov models,” _International computer science institute_ , vol. 4, no. 510, p. 126, 1998.
  * [41] W. Liu, J. He, and S.-F. Chang, “Large graph construction for scalable semi-supervised learning,” in _Proceedings of the 27th international conference on machine learning (ICML-10)_ , 2010, pp. 679–686.
  * [42] S. P. Boyd and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [43] R. A. Horn and C. R. Johnson, _Matrix analysis_. Cambridge university press, 2012.
  * [44] F. Nie, J. Xue, D. Wu, R. Wang, H. Li, and X. Li, “Coordinate descent method for $k$-means,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 44, no. 5, pp. 2371–2385, 2022.
  * [45] A. Fahad, N. Alshatri, Z. Tari, A. Alamri, I. Khalil, A. Y. Zomaya, S. Foufou, and A. Bouras, “A survey of clustering algorithms for big data: Taxonomy and empirical analysis,” _IEEE Transactions on Emerging Topics in Computing_ , vol. 2, no. 3, pp. 267–279, 2014.