betaFeedback

WorksComputer Science

A Generalized Sparse Fuzzy Clustering Framework with Automated Cluster Cardinality Estimation Ability

Abstract

Fuzzy clustering provides a robust framework for handling ambiguous and overlapping data boundaries, yet its traditional formulation generates entirely dense membership assignments that limit noise resilience and prevent estimating the true number of clusters, when it is unknown. To address these limitations, we introduce in this paper the Generalized Sparse Fuzzy Clustering (GSFC) framework, which incorporates a continuous sparsity penalty into the fuzzy objective function. Because closed-form solutions are precluded by the simultaneous presence of fuzzifier and sparsity exponents, we propose an efficient primal-dual bisection search coupled with specialized analytic pathways to rigorously enforce the partition constraint while organically driving trace memberships to exact zero. This mathematically enforced sparsity empowers the algorithm to autonomously estimate the true number of clusters by dynamically pruning redundant clusters, provided that it is initialized by a larger than the true number of clusters. Furthermore, we integrate a virtual noise sink to insulate outliers from the rest of the data points. The usage of the proposed framework is also extended to line segment detection. Extensive empirical evaluations across synthetic toy datasets, high-noise geometric stress tests, and real-world benchmarks (UCI wine dataset and hyperspectral images) demonstrate that GSFC effectively exceeds conventional fuzzy benchmarks while autonomously resolving cluster cardinality. Additionally, it significantly outperforms existing sparse possibilistic and probabilistic soft-clustering alternatives in line detection tasks.

Highlights

  • We propose the Generalized Sparse Fuzzy Clustering (GSFC) framework, introducing an additional term into the fuzzy objective, that promotes sparsity on the fuzzy membership values.

  • A novel primal-dual optimization algorithm combining bisection search with closed-form analytic pathways is developed to solve the resulting Cost Function Optimization (CFO) problem.

  • Due to the enforced sparsity on membership values redundant clusters are pruned, implying that the algorithm can reliably infer the true number of clusters from a safe over-initialization. Henceforth, prior knowledge of the exact number of clusters is not required.

  • Two specific algorithmic instances for the GSFC framework, which are suitable for the identification of compact and elongated clusters, respectively, are discussed extensively.

  • Comprehensive evaluations across synthetic data and multiple real-world datasets, for both the compact and the elongated cluster case, showcase that the introduced sparsity penalty results in superior performance over other relevant clustering approaches.

Introduction

The primary focus of this paper is the introduction of sparsity on membership assignments in Cost Function Optimization (CFO) clustering algorithms. CFO algorithms have two general categories: (a) the hard CFO algorithms where each data point belongs exclusively to a single cluster (this branch includes the probabilistic set up [8]) and (b) the soft CFO algorithms where the concept of membership of a point to a cluster is relaxed (this branch includes the fuzzy [4, 10] and possibilistic algorithms [17, 18]). It has been shown that imposing sparsity in possibilistic and probabilistic CFO algorithms greatly improve their performance [16, 28].

Fuzzy clustering distinguishes itself from rigid hard-partitioning methods by allowing data points to belong to multiple clusters simultaneously up to a degree of membership, a strategy that naturally accommodates data ambiguity and overlapping boundaries. However, this mathematical flexibility inherently produces entirely dense membership assignments, meaning every data point retains a non-zero connection to every cluster. This dense modeling risks artificially blurring boundaries between neighboring groups, heavily increasing sensitivity to noise and outliers (which persistently drag cluster representatives away from their true positions), and prevents the autonomous discovery of the dataset’s true clustering structure. Because points are forced to distribute their membership across all available clusters, there is no way to identify and prune redundant clusters. For instance, consider a line segment detection application featuring an image with 50 line segments. While a single pixel might belong to multiple intersecting line segments—necessitating soft assignments—physical reality dictates that it will intersect with only a small fraction of them, not all 50. The potential for such unrealistic representations highlights the need for a framework that can naturally drive irrelevant, trace memberships to exact zero. As will be experimentally showcased, enforcing sparsity in the data membership vectors not only improves clustering quality but also can identify and prune redundant clusters, effectively learning the number of true clusters in the dataset.

  • Corresponding author1

The primary focus of this paper is the introduction of sparsity on membership assignments in Cost Function Optimization (CFO) clustering algorithms. CFO algorithms have two general categories: (a) the hard CFO algorithms where each data point belongs exclusively to a …

Literature Review

While there have been numerous attempts at introducing sparsity into fuzzy clustering, most works focus on different sparsity models. For instance, Zhang et al [36], introduces sparsity into the general fuzzy clustering framework, focusing on image segmentation tasks. It assumes that each data point xi\mathbf{x}_i is a noisy observation, and it learns the "classic" (i.e., non-sparse) fuzzy membership weight ui,ju_{i,j}, the prototypes θj\boldsymbol{\theta}_j and the sparse noise components ei\mathbf{e}_i. Hence, the typical issues associated with fuzzy clustering discussed above remain. Furthermore, its noise suppression is limited by its strict reliance on a manually tuned deviation hyperparameter and the exact number of clusters needs to be specified a priori.

Similarly, Cheng et al [6], introduces a Sparsity Fuzzy C-Means framework with Principal Component Analysis (PCA) embeddings that performs dimensionality reduction and fuzzy membership learning simultaneously. To mitigate the impact of noise in high-dimensional spaces, the authors introduce a binary weighting factor to adaptively filter out outliers (hard thresholding). However, this approach presents significant practical limitations, as it strictly requires the user to pre-define the exact number of normal (i.e., non-outlier) data points (kk) present in the dataset. The authors explicitly acknowledge that overestimating kk allows outliers to contaminate the clusters, while underestimating kk permanently discards valid data points. Furthermore, the proposed method requires a fixed, predetermined number of clusters. Consequently, sparsity in this model acts merely as a rigid, quota-based outlier rejection tool.

A closely related strategy is adopted by Zhang et al. [35], who propose the so-called Row Sparse Discriminative Embedding Projection (RFCDE) framework. Like [6], RFCDE learns a low-dimensional subspace while utilizing an adaptive binary sample contribution vector to filter out outliers. Although RFCDE successfully induces row-sparse memberships via entropy regularization and mitigates prototype bias through joint projection learning, it inherits the exact same fundamental vulnerability regarding the hyperparameter kk. Because the algorithm relies on ranking sample contributions to strictly isolate kk normal samples, an inaccurate estimate of kk will inevitably exclude valid, informative data or absorb outliers into the clusters. Furthermore, it also requires the total number of clusters to be known in advance.

Another interesting direction, given in [14], builds directly upon the foundational Membership Affinity Lasso (MalFCM) framework [13], which attempts to preserve local data geometry by applying a Lasso penalty that forces neighboring points to share similar fuzzy assignments. To address the entirely dense memberships generated within the original MalFCM framework, the extended Sparse Membership Affinity Lasso (SMalFCM) introduces an explicit L0L_0-norm constraint to limit the maximum number of clusters a single sample can belong to. However, this approach enforces sparsity through a rigid method (a user-defined hyperparameter sˉ\bar{s}) that hard-truncates memberships, rather than achieving it organically through a continuous mathematical penalty term, as is the case with our proposed framework. Furthermore, both SMaIFCM and its predecessor rely entirely on pre-computed nearest-neighbor graphs to dictate membership affinity, making their performance highly fragile if this initial geometric prior is not accurate, a common occurrence in high-dimensional or noisy datasets. Finally, these approaches require the exact number of clusters to be strictly defined in advance and practically restrict the fuzzifier to a value of q=2q = 2 to maintain closed-form ADMM updates.

In [19] the focus is on large high-dimensional data applications, proposing the Robust Jointly Sparse Fast Fuzzy Clustering (RSFCAG) algorithm to address computational bottlenecks. To achieve linear time complexity, RSFCAG approximates the dataset using a small subset of anchor points—generated via a fast ternary-tree hierarchical approach—and performs fuzzy clustering within a low-dimensional space obtained through joint Locality Preserving Projection (LPP). The algorithm introduces sparsity strictly for denoising and graph construction. However, approximating the entire dataset with a sparse set of anchors inevitably results in information loss, which, as the authors note, can degrade clustering performance on datasets that require fine-grained topological mapping. Furthermore, the framework strictly requires the exact number of clusters to be pre-specified and relies on extensive hyperparameter tuning. Critically, while the projection matrices and anchor connections are sparse, the actual fuzzy membership updates do not enforce sparsity, resulting in dense assignments.

Reference [7] integrates conventional fuzzy methods with Sparse Subspace Clustering (SSC) to form a unified Fuzzy Sparse Subspace Clustering (FSSC) framework. By embedding the self-representation coefficients of SSC into the fuzzy objective function, FSSC leverages global data correlations to mitigate the effects of complex backgrounds and intensity inhomogeneity in infrared images. However, the construction of the self-representation matrix introduces severe computational bottlenecks, forcing the algorithm to rely on superpixel preprocessing to reduce the input size. Furthermore, the required ADMM optimization mathematically restricts the fuzzifier to q=2q = 2 and assumes a rigidly pre-specified cluster count.

Another interesting idea is considered in [5, 12, 24] where sparsity is investigated in terms of features. For each high-dimensional data point xi\mathbf{x}_i only a small number of its features should dictate the clustering placement, and hence the work focuses on optimizing the feature weighing mechanism. Consequently, these works do not resolve the fundamental ambiguity of dense fuzzy assignments, nor does it organically shape membership boundaries or prune redundant clusters (again, the true number of clusters is required).

To summarize, the key limitations of the aforementioned works are:

  • Limited sparsity inclusion: Sparsity is typically utilized to filter out noisy points or to select relevant features.

  • Strong A Priori Assumptions: All cited works require the exact number of clusters to be known a priori.

  • Optimization Limitations: Some works are also restricted to specific fuzzifier values.

Remark: It is important to emphasize that the proposed framework does not necessarily compete with or seek to invalidate these prior schemes; rather, they target fundamentally different issues of the clustering framework. Because the previous approaches operate orthogonally to the currently proposed framework, the latter could work in conjunction with, sparse feature selection or subspace learning algorithms to utilize multi-level sparse representations produced by the aforementioned methods.

In addition to fuzzy clustering, sparsity can improve the performance of both possibilistic [16, 31, 34] [33] and probabilistic [15, 1] clustering. For example, [16] develops highly effective algorithms for line segment identification based on probabilistic and possibilistic sparse clustering.

The main issue of [16] is that the possibilistic framework does not enforce the membership sum constraint, i.e.:

∑membership weight(x)=1∀ data point x\sum\text{membership weight}(\mathbf{x}) = 1 \quad\forall\ \text{data point }\mathbf{x}

Because memberships are entirely independent in the possibilistic rationale, the clusters do not mathematically compete for data points. Without this competition, multiple cluster representatives can easily collapse onto the same dense region of data, requiring highly sensitive hyperparameter tuning to keep nearby clusters separated. This issue is addressed by [28]. However, the proposed iterative algorithm relies on specific distribution models to define the spread of each cluster. This parametric assumption can be heavily limiting in applications where the data is not Gaussian-like or where distinct clusters exhibit vastly different spatial variances.

Our work aims to address the weaknesses of both [16] and [28] by combining the concept of sparsity with fuzzy clustering. By doing so, the resulting framework strictly enforces the competitive membership sum-to-one constraint, while it remains model-agnostic, allowing it to successfully address general, non-Gaussian data structures. The main contributions of this work are summarized as follows:

  • A Novel General Sparse Fuzzy Clustering (GSFC) Framework: We introduce a continuous sparsity penalty term into the traditional fuzzy objective. This mathematically enforced sparsity enables GSFC to autonomously discover the true number of clusters by organically pruning redundant clusters from an over-initialized state. The solution of the resulting CFO problem is carried out through the utilization of a novel bisection-driven optimization mechanism. To overcome the extreme sensitivity of dense fuzzy assignments to outliers, we integrate a "dummy" noise cluster into the GSFC optimization. This mechanism safely absorbs noisy data points, preventing them from affecting the positions of the cluster representatives.

  • Improvement over Dense Fuzzy Methods: Through comprehensive experiments on both synthetic toy datasets, real-world tabular data, and HyperSpectral Images (HSIs), we demonstrate that the enforced sparsity allows GSFC to match or exceed the performance of traditional Fuzzy C-Means (FCM), while providing the true cluster cardinality. Furthermore, our experimental results reveal exceptional stability across random initializations, as over-initializing the candidate cluster representatives pool, followed by a dynamically pruning procedure, ensures thorough coverage of the data space and prevents convergence traps caused by poorly placed initial cluster centers.

  • State-of-the-Art Line Segment Extraction: Apart from the use of the proposed framework for the case of compact clusters, we demonstrate the use of GSFC to the complex geometrical task of line segment identification. The model’s ability to drive trace memberships to exact zero allows it to significantly outperform alternative soft clustering algorithms in identifying intersecting physical segments.

The rest of this paper is organized as follows. The GSFC framework for point representatives is presented in section II, and an extension to the special case of elongated clusters is provided in section III. A wide range of experiments in both synthetic and real-world data is provided in section IV, and section V concludes.

General Sparse Fuzzy Clustering (GSFC)

Objective Function and Lagrangian

Let X={x1,…,xN}⊂Rd\mathcal{X} = \{\mathbf{x}_1, \ldots, \mathbf{x}_N\} \subset\mathbb{R}^d be a set of NN data points, and Θ={θ1,…,θm}\Theta= \{\boldsymbol{\theta}_1, \ldots, \boldsymbol{\theta}_m\} be the set of mm cluster representatives, corresponding to the clusters C1,…,CmC_1, \ldots, C_m, respectively. We consider first the case where the data points form compact clusters and, as a consequence, the cluster representatives θs\boldsymbol{\theta}_s, s=1,…,ms = 1, \ldots, m, are points in Rd\mathbb{R}^d (in Section III, it is shown how GSFC can be extended to handle the case of elongated clusters corresponding to line-segments). The objective/cost function of General Sparse Fuzzy Clustering (GSFC) is defined as:

JGSFC(U,Θ)=∑i=1N∑j=1muijqd(xi,θj)+s∑i=1N∑j=1muijp=∑i=1N∑j=1muijqd(xi,θj)+s∑i=1N∥ui∥pp,(1)J_{\mathrm{GSFC}}(\mathbf{U}, \Theta) = \sum_{i=1}^{N}\sum_{j=1}^{m}u_{ij}^{q}d(\mathbf{x}_i,\boldsymbol{\theta}_j) + s\sum_{i=1}^{N}\sum_{j=1}^{m}u_{ij}^{p} = \sum_{i=1}^{N}\sum_{j=1}^{m}u_{ij}^{q}d(\mathbf{x}_i,\boldsymbol{\theta}_j) + s\sum_{i=1}^{N}\lVert\mathbf{u}_i\rVert_p^p, \tag*{(1)}

where d(xi,θj)d(\mathbf{x}_i,\boldsymbol{\theta}_j) is the euclidean distance of the i-th data point from the j-th representative, U=[uij]∈RN×m\mathbf{U} = [u_{ij}] \in\mathbb{R}^{N\times m} is the membership matrix, where uiju_{ij} is the degree of belongingness of the i-th data point to the j-th cluster, and q(>1)q(> 1) is the so-called fuzzifier parameter. Also, 0<p<10 < p < 1 is the sparsity exponent (hence, ∥v∥p\lVert\mathbf{v}\rVert_p is the quasinorm of vector v\mathbf{v}), s>0s > 0 controls sparsity strength.

The first term in (1) is the traditional fuzzy objective and the second is the sparsity-imposing term. In the general fuzzy clustering framework, optimization of the cost function is subject to the following constraints:

∑j=1muij=1,∀i∈{1,…,N}(2)\sum_{j=1}^{m}u_{ij} = 1,\quad\forall i \in\{1,\ldots,N\} \tag*{(2)}
uij∈[0,1],∀i∈{1,…,N}, j∈{1,…,m},(3)u_{ij} \in[0,1],\quad\forall i \in\{1,\ldots,N\},\ j \in\{1,\ldots,m\}, \tag*{(3)}

To minimize JGSFCJ_{\mathrm{GSFC}} with respect to U\mathbf{U} under constraint (2), we construct the Lagrangian function:

L(U,Θ,λ)=∑i=1N∑j=1muijqd(xi,θj)+s∑i=1N∑j=1muijp−∑i=1Nλi(∑j=1muij−1)(4)\mathcal{L}(\mathbf{U},\Theta,\boldsymbol{\lambda}) = \sum_{i=1}^{N}\sum_{j=1}^{m}u_{ij}^{q}d(\mathbf{x}_i,\boldsymbol{\theta}_j) + s\sum_{i=1}^{N}\sum_{j=1}^{m}u_{ij}^{p} - \sum_{i=1}^{N}\lambda_i\left(\sum_{j=1}^{m}u_{ij}-1\right) \tag*{(4)}

where λ=[λ1,…,λN]T\boldsymbol{\lambda} = [\lambda_1,\ldots,\lambda_N]^{T} is the vector of Lagrange multipliers. Setting the partial derivative with respect to ursu_{rs} (for a specific data point xr\mathbf{x}_r and a specific cluster θs\boldsymbol{\theta}_s) to zero yields the first-order stationarity condition:

∂L∂urs=qdrsursq−1+s⋅pursp−1−λr=0(5)\frac{\partial\mathcal{L}}{\partial u_{rs}} = qd_{rs}u_{rs}^{q-1} + s\cdot pu_{rs}^{p-1} - \lambda_r = 0 \tag*{(5)}

where drs≡d(xr,θs)d_{rs} \equiv d(\mathbf{x}_r,\boldsymbol{\theta}_s).

Remark: Unlike the classic (i.e., without the sparsity loss term) fuzzy clustering frameworks e.g., FCM, in this framework we can not extract closed-form solution for ursu_{rs} from eq. (5), due to the simultaneous presence of ursq−1u_{rs}^{q-1} and ursp−1u_{rs}^{p-1}.

Determining Sparse Memberships ursu_{rs} using the Bisection Method

Here we will discuss an optimization procedure for inferring the membership assignments for a data point xr\mathbf{x}_r from eq. (5). Focusing on a specific cluster ss we need to solve

qdrsursq−1+spursp−1−λr=0.qd_{rs}u_{rs}^{q-1} + spu_{rs}^{p-1} - \lambda_r = 0.

To eliminate the negative exponent (p−1<0p - 1 < 0), we multiply both sides of the equation by urs1−pu_{rs}^{1-p}, yielding:

qdrsursq−p+sp−λrurs1−p=0(6)qd_{rs}u_{rs}^{q-p}+sp-\lambda_ru_{rs}^{1-p}=0 \tag*{(6)}

We introduce a substitution variable v=urs1−p1−pv=u_{rs}^{\frac{1-p}{1-p}} (implying urs=v11−pu_{rs}=v^{\frac{1}{1-p}}) and define the exponent scalar a=q−11−p>0a=\frac{q-1}{1-p}>0. This implies that

q−p=(a+1)(1−p),(7)q-p=(a+1)(1-p), \tag*{(7)}

allowing us to rewrite ursq−pu_{rs}^{q-p} as va+1v^{a+1}. Eq. (5) elegantly reduces to finding the roots of the generalized function:

f(v)≡qdrsva+1−λrv+sp=0(8)f(v)\equiv qd_{rs}v^{a+1}-\lambda_rv+sp=0 \tag*{(8)}

To determine if valid non-negative memberships exist, we analyze the graph of f(v)f(v). At v=0v=0, f(0)=sp>0f(0)=sp>0. Taking the first derivative with respect to vv and setting it to zero yields the location of the local extremum:

f′(v)=(a+1)qdrsva−λr=0⟹f'(v)=(a+1)qd_{rs}v^a-\lambda_r=0 \quad\Longrightarrow
vmin⁡=(λr(a+1)qdrs)1a(9)v_{\min}=\left(\frac{\lambda_r}{(a+1)qd_{rs}}\right)^{\frac{1}{a}} \tag*{(9)}

Because the second derivative f′′(v)=(a+1)aqdrsva−1f''(v)=(a+1)aqd_{rs}v^{a-1} is strictly positive for all v>0v>0, vmin⁡v_{\min} represents the unique global minimum of ff for v>0v>0. The existence of valid membership roots depends entirely on the value of f(vmin⁡)f(v_{\min}). We consider two cases:

Sparse Pruning (f(vmin⁡)>0f(v_{\min})>0): The minimum sits above the x-axis, meaning no positive real roots exist, which in turn means that the data point is too far from the cluster, relative to the dual variable λr\lambda_r. In this case, the optimal assignment is driven to exact zero: urs=0u_{rs}=0.

Active Condition (f(vmin⁡)≤0f(v_{\min})\leq0): The function dips below the x-axis, producing, in general, two positive real roots. When v<vmin⁡v<v_{\min}, the derivative f′(v)f'(v) is strictly negative, which translates to a negative second derivative of the GSFC objective (∂2L∂urs2<0\frac{\partial^2\mathcal{L}}{\partial u_{rs}^2}<0). In this region, the local objective segment is concave. Therefore, the stationary point v1v_1 (the smaller solution of ∂L∂urs=0\frac{\partial\mathcal{L}}{\partial u_{rs}}=0) is a local maximum.

Conversely, when v>vmin⁡v>v_{\min}, f′(v)f'(v) becomes strictly positive. This flips the second derivative of the initial objective to be strictly positive as well (∂2L∂urs2>0\frac{\partial^2\mathcal{L}}{\partial u_{rs}^2}>0), making the local objective strictly convex in that region. Therefore, v2v_2, the larger solution of ∂L∂urs=0\frac{\partial\mathcal{L}}{\partial u_{rs}}=0, is a local minimum of L\mathcal{L} with respect to ursu_{rs}. Hence, the optimal v∗v^* lies in the interval (vmin⁡,1)(v_{\min},1).

General Newton-Raphson+Bisection Solver

Because f(v)=0f(v)=0 lacks a closed-form expression for arbitrary values of the exponent aa, the active condition (f(vmin⁡)≤0f(v_{\min})\leq0) requires a two-level numerical solver to determine ur1,…,urmu_{r1},\ldots,u_{rm} for a specific data point xr\mathbf{x}_r: an outer bisection search for the Lagrange multiplier λr\lambda_r, and an inner Newton-Raphson (NR) solver to compute v∗v^* at every (outer) bisection step, corresponding to a specific λr\lambda_r value. The NR solver is utilized mm times, one for each ursu_{rs}, s=1,…,ms=1,\ldots,m. For a specific ss, it is initialized to the right of the corresponding vmin⁡v_{\min}.

For a given candidate dual variable λmid\lambda_{\mathrm{mid}} generated by the outer bisection search, the NR inner loop refines the root iteratively via:

\begin{aligned} v^{(t+1)}&=v^{(t)}-\frac{f(v^{(t)})}{f'(v^{(t)})}\\ &=v^{(t)}-\frac{qd_{rs}(v^{(t)})^{a+1}-\lambda_{\mathrm{mid}}v^{(t)}+sp}{(a+1)qd_{rs}(v^{(t)})^a-\lambda_{\mathrm{mid}} \end{aligned}} \tag*{(10)}\end{aligned}

Upon convergence, the active sparse membership is recovered via

urs=(v∗)11−p.u_{rs}=(v^*)^{\frac{1}{1-p}}.

Having applied the above procedure mm times for the specific point xr\mathbf{x}_r, the outer bisection loop evaluates the partition residual Φ(λmid)=∑s=1murs−1\Phi(\lambda_{\mathrm{mid}})=\sum_{s=1}^{m}u_{rs}-1, updating the search bounds until ∣Φ∣<ϵbis|\Phi|<\epsilon_{\mathrm{bis}}, where ϵbis\epsilon_{\mathrm{bis}} is a small user-defined parameter.

One important detail is how the search interval for the bisection method (λmin⁡,λmax⁡)(\lambda_{\min},\lambda_{\max}) is configured. A trivial lower bound can be configured by setting λmin⁡=0\lambda_{\min}=0. Then f(v)f(v) is a sum of positive numbers and hence, f(vmin⁡)>0f(v_{\min})>0. This triggers the Sparse Pruning condition for every single cluster, forcing urs=0u_{rs}=0 for all ss. Hence the partition residual is Φ(0)=0−1=−1\Phi(0)=0-1=-1.

To get an upper bound, we start from the general equation

qdrsursq−1+spursp−1=λr.q d_{rs} u_{rs}^{q-1}+s p u_{rs}^{p-1}=\lambda_r.

If we substitute urs=1u_{rs}=1 and use the minimal distance min⁡s(drs)\min_s(d_{rs}), the exponents disappear (1q−1=11^{q-1}=1 and 1p−1=11^{p-1}=1), leaving us with the exact theoretical upper bound:

λmax⁡=qmin⁡s(drs)+sp(11)\lambda_{\max}=q\min_s(d_{rs})+sp \tag*{(11)}

Since ursu_{rs} will be equal to 1 for one cluster and positive for the rest, it will hold Φ(λmax⁡)≥0\Phi(\lambda_{\max})\ge0. The above procedure is described in its detail in Algorithm 1.

Special Pathways Leading to Analytic Solutions for (5)

The computational overhead of running an inner NR solver inside the bisection loop can be bypassed for specific choices of values of the parameter pairs (p,q)(p,q) that collapse f(v)=0f(v)=0 into exact closed-form algebraic solutions. Specifically, setting p=0.5p=0.5 (as in [16]) yields two primary pathways:

  • Pathway 1 (q=1.5q=1.5, p=0.5⟹a=1p=0.5 \Longrightarrow a=1): Reduces eq. (8) to a quadratic equation 1.5drsv2−λrv+0.5s=01.5d_{rs}v^2-\lambda_r v+0.5s=0, yielding the direct root formula:

urs(λr)=(λr+λr2−3sdrs3drs)2for λr≥3sdrs(12)u_{rs}(\lambda_r)=\left(\frac{\lambda_r+\sqrt{\lambda_r^2-3sd_{rs}}}{3d_{rs}}\right)^2 \quad\text{for }\lambda_r\ge\sqrt{3sd_{rs}} \tag*{(12)}

Otherwise, ursu_{rs} is set to 0.

  • Pathway 2 (q=2.0q=2.0, p=0.5⟹a=2p=0.5 \Longrightarrow a=2): Reduces to a depressed cubic equation 2.0drsv3−λrv+0.5s=02.0d_{rs}v^3-\lambda_r v+0.5s=0, solved analytically via Viète’s trigonometric roots:

urs(λr)=2λr6drscos⁡(13arccos⁡(−s454drs3λr3))(13)u_{rs}(\lambda_r)=2\sqrt{\frac{\lambda_r}{6d_{rs}}}\cos\left(\frac{1}{3}\arccos\left(-\frac{s}{4}\sqrt{\frac{54d_{rs}^{3}}{\lambda_r^{3}}}\right)\right) \tag*{(13)}

In the sequel we will experimentally showcase that both of these pathways can produce very strong performance, across diverse datasets.

Algorithm 1 Subroutine: Sparse Membership Vector Evaluation for Sample xr\mathbf{x}_r (Invoked iteratively per data point within GSFC)

  1. Input: Distance vector dr=[dr1,…,drm]T\mathbf{d}_r = [d_{r1}, \ldots, d_{rm}]^{T} for a single sample xr\mathbf{x}_r, sparsity factor s>0s > 0, parameters (p,q)(p,q), bisection tolerance ϵbis>0\epsilon_{bis} > 0.

  2. Output: Sparse membership vector ur=[ur1,…,urm]T\mathbf{u}_r = [u_{r1}, \ldots, u_{rm}]^{T} and optimal Lagrange multiplier λr∗\lambda_r^*.

  3. Set bounds λmin⁡←0\lambda_{\min} \leftarrow0 and λmax⁡=qmin⁡s(drs)+sp\lambda_{\max} = q\min_s(d_{rs}) + sp

  4. Set λlow←λmin⁡\lambda_{\mathrm{low}} \leftarrow\lambda_{\min}, λhigh←λmax⁡\lambda_{\mathrm{high}} \leftarrow\lambda_{\max}

  5. while (λhigh−λlow)>ϵbis(\lambda_{\mathrm{high}}-\lambda_{\mathrm{low}}) > \epsilon_{bis} do

  6. λmid←λlow+λhigh2\lambda_{\mathrm{mid}} \leftarrow\frac{\lambda_{\mathrm{low}}+\lambda_{\mathrm{high}}}{2}

  7. for s=1…ms = 1 \ldots m do

  8. Compute a=q−11−pa = \frac{q-1}{1-p} and vmin⁡=(λmid(a+1)qdrs)1av_{\min} = \left(\frac{\lambda_{\mathrm{mid}}}{(a+1)qd_{rs}}\right)^{\frac{1}{a}}

  9. Evaluate active condition: f(vmin⁡)=qdrs(vmin⁡)a+1−λmidvmin⁡+spf(v_{\min}) = qd_{rs}(v_{\min})^{a+1} - \lambda_{\mathrm{mid}}v_{\min} + sp

  10. if f(vmin⁡)>0f(v_{\min}) > 0 then

  11. urs←0u_{rs} \leftarrow0 {Sparse Pruning}

  12. else

  13. Find root v∗≥vmin⁡v^* \ge v_{\min} of f(v)=0f(v) = 0 {Via closed-form pathways or NR}

  14. urs←(v∗)11−pu_{rs} \leftarrow(v^*)^{\frac{1}{1-p}}

  15. end if

  16. end for

  17. Evaluate partition residual: Φ←∑s=1murs−1\Phi\leftarrow\sum_{s=1}^{m}u_{rs} - 1

  18. if ∣Φ∣<ϵbis|\Phi| < \epsilon_{bis} then

  19. break {Convergence achieved}

  20. else if Φ>0\Phi> 0 then

  21. λhigh←λmid\lambda_{\mathrm{high}} \leftarrow\lambda_{\mathrm{mid}} {Sum too large ⟹\Longrightarrow decrease λr\lambda_r}

  22. else

  23. λlow←λmid\lambda_{\mathrm{low}} \leftarrow\lambda_{\mathrm{mid}} {Sum too small ⟹\Longrightarrow increase λr\lambda_r}

  24. end if

  25. end while

  26. Set λr∗←λmid\lambda_r^* \leftarrow\lambda_{\mathrm{mid}} and return ur=[ur1,…,urm]T\mathbf{u}_r = [u_{r1}, \ldots, u_{rm}]^{T}

  27. End Subroutine

Validity of the Membership Bounds

A critical mathematical requirement for fuzzy clustering is that the resulting ursu_{rs} memberships strictly lie within the valid interval [0,1][0,1] for the λr\lambda_r value outputted by algorithm 1. In the proposed framework, these bounds are strictly enforced through two distinct mechanisms:

Non-negativity (urs≥0u_{rs} \ge0): The lower bound is guaranteed directly by the closed-form derivations in both evaluation pathways. In Pathway 1, the thresholding condition explicitly sets urs=0u_{rs}=0 if λr<3sdrs\lambda_r < \sqrt{3sd_{rs}}. If this condition is met, the active formula evaluates to a squared real number. Similarly, in Pathway 2, the cubic discriminant check sets urs=0u_{rs}=0 if Δrs>0\Delta_{rs} > 0, while Viète’s formula yields a real root v∗v^* that is subsequently squared. Thus, for any evaluated λr\lambda_r, it is mathematically guaranteed that urs(λr)≥0u_{rs}(\lambda_r) \ge0.

For the general case with arbitrary exponents (q>1,0<p<1q > 1, 0 < p < 1) non-negativity is preserved. Under the sparse pruning condition (f(vmin⁡)>0f(v_{\min}) > 0), the membership is directly assigned to urs=0u_{rs}=0. When the active condition holds (f(vmin⁡)≤0f(v_{\min}) \le0), the critical point

vmin⁡=(λr(a+1)qdrs)1/av_{\min} = \left(\frac{\lambda_r}{(a+1)qd_{rs}}\right)^{1/a}

is strictly positive since λr,drs,q,a>0\lambda_r,d_{rs},q,a > 0. As we have shown, in that case, the objective’s local minimum v∗v^* resides on the branch (vmin⁡,1)(v_{\min},1). As a result, the inverse power transformation urs=(v∗)11−pu_{rs}=(v^*)^{\frac{1}{1-p}} is a positive real power of a strictly positive real number (as 1−p>01-p>0). Thus, urs>0u_{rs}>0 strictly in the active regime, guaranteeing that urs≥0u_{rs}\ge0 holds universally for any valid (p,q)(p,q) configuration.

Upper Bound (urs≤1u_{rs} \le1): The upper bound is not explicitly restricted by the individual membership formulas, but is rather implicitly guaranteed by the bisection search regardless of the optimization pathway. Because the algorithm terminates only when the fuzzy partition constraint ∑s=1murs(λr∗)=1\sum_{s=1}^{m} u_{rs}(\lambda_r^*) = 1 is satisfied, and because all individual memberships are guaranteed to be non-negative, the fundamental properties of addition dictate that no single membership can exceed 1. Therefore, at the optimal dual variable λr∗\lambda_r^*, the constraint urs∈[0,1]u_{rs} \in[0, 1] is strictly satisfied.

Determination of the Optimal Number of Clusters

To automatically determine the optimal number of clusters mm and safeguard against numerical instabilities, the iterative optimization loop incorporates two dynamic post-processing procedures: cardinality-based elimination and distance-based merging.

Cluster Elimination (Cardinality-Based Pruning)

Because of the sparsity imposition, some clusters may lose membership support, that is, almost all data points have very low membership values for these clusters, which, in turn, it translates to the the fact that these clusters are "almost empty". To identify whether a specific cluster CjC_j is underpopulated or isolated, we compute the effective cardinality NjN_j (total accumulated membership):

Nj=∑r=1Nurj(14)N_j = \sum_{r=1}^{N} u_{rj} \tag*{(14)}

Then CjC_j is declared as degenerate and is eliminated if its effective cardinality falls below a user-defined threshold ϵelim≥0\epsilon_{\mathrm{elim}} \ge0.

This pruning mechanism serves two key roles: it allows the algorithm to be safely over-initialized with a large candidate cluster count m(0)m^{(0)}, and it also prevents division-by-zero singularities during prototype update steps (which scale inversely with NjN_j).

Cluster Merging (Distance-Based Coalescence)

Over-initialization or overlapping clusters can cause multiple cluster representatives to converge onto the same area of a single physical cluster (erroneously splitting it to two or more clusters). To eliminate redundant representatives (and, at the same time, the clusters they are associated with), a pairwise distance check is conducted across all active clusters. For any pair of representatives (θj,θk)(\theta_j, \theta_k), if their Euclidean distance falls below a merge threshold ϵgap>0\epsilon_{\mathrm{gap}} > 0:

d(θj,θk)=∥θj−θk∥2<ϵgap(15)d(\theta_j, \theta_k) = \lVert\theta_j - \theta_k \rVert_2 < \epsilon_{\mathrm{gap}} \tag*{(15)}

the two clusters are collapsed into a single prototype θnew\theta_{\mathrm{new}} using a cardinality-weighted average:

θnew=Njθj+NkθkNj+Nk(16)\theta_{\mathrm{new}} = \frac{N_j\theta_j + N_k\theta_k}{N_j + N_k} \tag*{(16)}

Once the prototypes are merged, columns jj and kk in the membership matrix UU are removed. The exact optimal memberships and distances for the unified prototype θnew\theta_{\mathrm{new}} are naturally recomputed during the evaluation phase of the subsequent iteration. Note that directional or manifold prototype geometries (such as line segments) can incorporate angular alignment metrics into the merge criterion (an example, based on [16] is provided in the next section).

Cluster Representative Update

Once the optimal sparse membership matrix U(t)U^{(t)} is computed (where tt denotes the current optimization loop iteration), the objective function JGSFCJ_{\mathrm{GSFC}} of eq. (1) decouples across the active clusters, allowing each representative to be updated independently by solving θj(t+1)=arg min⁡θj∑r=1Nurjq(t)d(xr,θj)\theta_j^{(t+1)} = \underset{\theta_j}{\operatorname{arg\,min}} \sum_{r=1}^{N} u_{rj}^{q}(t)d(x_r,\theta_j). In the present case of point representatives, the updating equation takes the following closed-form expression:

θj(t+1)=∑r=1Nurjq(t)xr∑r=1Nurjq(t)\theta_j^{(t+1)} = \frac{\sum_{r=1}^{N} u_{rj}^{q}(t)x_r}{\sum_{r=1}^{N} u_{rj}^{q}(t)}

The GSFC framework is described analytically in Algorithm 2.

Algorithm 2 General Sparse Fuzzy Clustering (GSFC)

  1. Input: Data X={x1,…,xN}\mathcal{X} = \{\mathbf{x}_1, \ldots, \mathbf{x}_N\}, initial prototype count m(0)m^{(0)}, hyperparameters (q,p,s)(q,p,s), thresholds (ϵelim,ϵgap,ϵconv)(\epsilon_{\mathrm{elim}}, \epsilon_{\mathrm{gap}}, \epsilon_{\mathrm{conv}}), small constant ϵd=10−12\epsilon_d = 10^{-12}, max iterations tmax⁡t_{\max}.

  2. Output: Optimized cluster prototypes Θ={θ1,…,θm}\Theta= \{\boldsymbol{\theta}_1, \ldots, \boldsymbol{\theta}_m\} and sparse membership matrix U∈RN×mU \in\mathbb{R}^{N \times m}.

  3. Initialize: Overestimated prototypes Θ(0)={θ1,…,θm(0)}\Theta^{(0)} = \{\boldsymbol{\theta}_1, \ldots, \boldsymbol{\theta}_{m^{(0)}}\}, iteration counter t←0t \leftarrow0.

  4. repeat

  5. Distance Calculation: For all r∈{1,…,N}r \in\{1,\ldots,N\} and j∈{1,…,m}j \in\{1,\ldots,m\}, compute regularized distances drj=max⁡(d(xr,θj),ϵd)d_{rj} = \max\left(d(\mathbf{x}_r,\boldsymbol{\theta}_j),\epsilon_d\right).

  6. Membership Update: For each point xr\mathbf{x}_r, determine λr∗\lambda_r^* and compute sparse vector ur(t)=[ur1,…,urm]T\mathbf{u}_r(t) = [u_{r1},\ldots,u_{rm}]^{T} calling Algorithm 1 (xr,[dr1,…,drm],s,q,p)(\mathbf{x}_r,[d_{r1},\ldots,d_{rm}],s,q,p).

  7. Cluster Elimination: Compute effective cardinality Nj=∑r=1Nurj(t)N_j = \sum_{r=1}^{N}u_{rj}(t) for all jj. For any cluster with Nj<ϵelimN_j < \epsilon_{\mathrm{elim}}, remove prototype θj\boldsymbol{\theta}_j and update total count mm.

  8. Cluster Update: For each active cluster j∈{1,…,m}j \in\{1,\ldots,m\}, update parameters:

θj(t+1)=arg⁡min⁡θj∑r=1Nurjq(t) d(xr,θj)\boldsymbol{\theta}_j^{(t+1)} = \underset{\boldsymbol{\theta}_j}{\arg\min}\sum_{r=1}^{N}u_{rj}^{q}(t)\,d(\mathbf{x}_r,\boldsymbol{\theta}_j)
  1. Cluster Merging: Identify pairs satisfying d(θj,θk)≤ϵgapd(\boldsymbol{\theta}_j,\boldsymbol{\theta}_k) \leq\epsilon_{\mathrm{gap}}. Merge into θnew=Njθj+NkθkNj+Nk\boldsymbol{\theta}_{\mathrm{new}} = \frac{N_j\boldsymbol{\theta}_j+N_k\boldsymbol{\theta}_k}{N_j+N_k}.

  2. t←t+1t \leftarrow t+1

  3. until ∥Θ(t)−Θ(t−1)∥F≤ϵconv\lVert\Theta^{(t)}-\Theta^{(t-1)}\rVert_F \leq\epsilon_{\mathrm{conv}} or t≥tmax⁡t \geq t_{\max}

Handling Outliers via a Virtual Noise Sink

To prevent distant outliers from acting as heavy anchors that drag prototypes out of place under the strict partition constraint (∑j=1murj=1)(\sum_{j=1}^{m}u_{rj}=1), we integrate a virtual noise sink governed by a constant distance threshold, dnoised_{\mathrm{noise}}. Specifically, a dummy cluster is appended at a fixed distance dnoised_{\mathrm{noise}} from all prototypes. During membership evaluation, any data point exceeding this threshold from the active prototypes assigns its membership entirely to the dummy cluster. This forces its membership to the true structural segments to zero, completely excluding background outliers from prototype updates while explicitly flagging them as noise during final evaluation.

Visualizing Pruning Procedure

To better understand how the algorithm eliminates redundant prototypes we constructed a toy example with 4 1D points x1x_1, x2x_2, x3x_3, x4x_4 positioned at 1, 2, 8, 9 and initialized the GSFC algorithm (for q=1.5q=1.5 and p=0.5p=0.5) with 3 cluster representatives θ1=0.8\theta_1=0.8, θ2=2.2\theta_2=2.2, and θ3=8.5\theta_3=8.5. The merging threshold is set to ϵgap=1\epsilon_{\mathrm{gap}}=1. The operation of GSFC for 3 optimization iterations is depicted in Figure 1. The first optimization pathway was considered without a noise cluster.

Figure 1. Visualization of GSFC’s pruning process

Initially, both x1x_1 and x2x_2 are very close to prototypes 1 and 2 leading to genuine fuzzy sharing with memberships of approximately 0.52 and 0.48. Due to the sparsity penalty u1,3=u2,3=0u_{1,3}=u_{2,3}=0. Likewise x3x_3, x4x_4 are only assigned to θ3\theta_3 due to sparsity.

In Step 1, as θ1\theta_1 and θ2\theta_2 shift inward to 1.2 and 1.8, they localize tightly around their nearest individual points (d1,1=0.04d_{1,1}=0.04 versus d1,2=0.64d_{1,2}=0.64 and vice-versa). Because GSFC enforces a distance-dependent activation threshold (see the condition of eq. (12)) representative θ2\theta_2 is "excluded" from the clusters connected to x1x_1 and vice-versa (i.e. the membership becomes 0). Consequently, the memberships snap to compact assignments of 1.00 for each point’s local prototype, demonstrating how the algorithm eliminates background fuzziness when prototypes become locally dominant.

Finally, in Step 2, despite the sharp local partitioning in Step 1, the spatial proximity condition identifies θ1\theta_1 and θ2\theta_2 as redundant representations of the same dense data region. They fuse into a single cluster representative at 1.50, restoring a unified representation of {x1,x2}\{x_1,x_2\} and pruning the cluster count from 3 to the true m∗=2m^*=2.

GSFC for Elongated Clusters

Adapting GSFC for the case of elongated clusters requires redefining representatives as finite segments θj\theta_j bounded by endpoints aj\mathbf{a}_j and bj\mathbf{b}_j along infinite carrier lines Hj(wjTx+wj0=0)H_j(\mathbf{w}_j^{T}\mathbf{x}+w_{j0}=0). A notable example where the elongated cluster case is useful is in line segment detection in edge-pixel images that contain linear elements. In this case, the data points are the image edge pixels, and the aim is to group the pixels that form a certain line to the same cluster.

Here, we briefly review how clustering mechanisms can be utilized for this application, based on the rigorous study of [16]. The core sparsity and bisection mechanics remain unchanged, but pruning and merging rules are specialized for linear structures.

Segment-to-Point Distance Metric

The distance d(xi,θj)d(\mathbf{x}_i,\boldsymbol{\theta}_j) combines the squared perpendicular distance to the infinite carrier line Hj:wjTxi+wj0=0H_j : \mathbf{w}_j^{T}\mathbf{x}_i+w_{j0}=0 (first term in eq. (17) below) with the distance of the projection of xi\mathbf{x}_i on HjH_j, xij\mathbf{x}_i^j, from the finite segment, which is completely defined by its two end points aj\mathbf{a}_j and bj\mathbf{b}_j, i.e., θj=[aj,bj]\boldsymbol{\theta}_j=[\mathbf{a}_j,\mathbf{b}_j] (second term in (17) below).

d(xi,θj)=(wjTxi+wj0)2∥wj∥2+d(xij,θj)(17)d(\mathbf{x}_i,\boldsymbol{\theta}_j)=\frac{(\mathbf{w}_j^{T}\mathbf{x}_i+w_{j0})^2}{\lVert\mathbf{w}_j\rVert^2}+d(\mathbf{x}_i^j,\boldsymbol{\theta}_j) \tag*{(17)}

where xij=xi−wjTxi+wj0∥wj∥2wj\mathbf{x}_i^j=\mathbf{x}_i-\frac{\mathbf{w}_j^{T}\mathbf{x}_i+w_{j0}}{\lVert\mathbf{w}_j\rVert^2}\mathbf{w}_j. If xij\mathbf{x}_i^j falls outside θj\boldsymbol{\theta}_j (that is, outside the interval on HjH_j with endpoints aj\mathbf{a}_j and bj\mathbf{b}_j), d(xij,θj)=min⁡(d(xij,aj),d(xij,bj))d(\mathbf{x}_i^j,\boldsymbol{\theta}_j)=\min(d(\mathbf{x}_i^j,\mathbf{a}_j),d(\mathbf{x}_i^j,\mathbf{b}_j)). Otherwise, d(xij,θj)=0d(\mathbf{x}_i^j,\boldsymbol{\theta}_j)=0.

Representative Update Rule

Representatives are updated by solving a weighted eigenvalue problem. Given the weighted mean

ξj=∑uijxi∑uij,\boldsymbol{\xi}_j=\frac{\sum u_{ij}\mathbf{x}_i}{\sum u_{ij}},

and covariance matrix

Aj=∑uij(xi−ξj)(xi−ξj)T,\mathbf{A}_j=\sum u_{ij}(\mathbf{x}_i-\boldsymbol{\xi}_j)(\mathbf{x}_i-\boldsymbol{\xi}_j)^T,

the orientation vector wj\mathbf{w}_j is the eigenvector corresponding to the smallest eigenvalue of Aj\mathbf{A}_j. The intercept is updated as wj0=wjTξjw_{j0}=\mathbf{w}_j^T\boldsymbol{\xi}_j. New endpoints aj\mathbf{a}_j and bj\mathbf{b}_j are determined by projecting points with significant membership (uij>0.05u_{ij}>0.05) onto HjH_j.

Cluster Elimination and Merging

Standard continuous pruning is replaced by a discrete cardinality requirement: a segment is pruned if it fails to serve as the primary representative for at least two distinct points (∣Sj∣<2|S_j|<2), where Sj={xi∈X∣j=arg⁡max⁡kuik}S_j=\{\mathbf{x}_i\in\mathcal{X}\mid j=\arg\max_k u_{ik}\}.

To handle redundant clusters, two line segments are merged if they are (i) collinear (arccos⁡(∣wjTwk∣)≤ϵangle\arccos(\lvert\mathbf{w}_j^{T}\mathbf{w}_k\rvert) \leq\epsilon_{\mathrm{angle}}) and (ii) spatially contiguous, meaning their spans overlap or their nearest endpoints lie within a small distance gap ϵgap\epsilon_{\mathrm{gap}}.

Numerical Experiments

In this section, we conduct a comprehensive empirical evaluation of GSFC across a diverse benchmark suite, comprising two synthetic toy datasets, two real-world tabular benchmarks, three HSIs, and multiple line-segment detection scenarios. The primary objective of these experiments is twofold. First, we aim to validate that introducing sparsity into the fuzzy membership assignment process yields substantial performance improvements and noise robustness over conventional, non-sparse FCM. Second, we seek to demonstrate the superiority of the proposed framework over competing sparse clustering algorithms developed for the elongated cluster case.

Toy Examples

Before considering realistic applications, we will first investigate the value of sparsity in the GSFC framework through toy 11-dimensional experiments. More specifically, we conducted two experiments to investigate GSFC in differently shaped compact clusters:

  • Experiment A: We generated a synthetic dataset containing three clusters whose points stem from Gaussian distributions (consisting of 500, 300, and 150 points, respectively) alongside uniform background noise (NnpN_{\mathrm{np}} ranging from 0 to 300 points) sampled from [−12.0,12.0]2[-12.0, 12.0]^2. The Gaussian means are located at coordinates [−5.0,−5.0][-5.0, -5.0], [5.0,−5.0][5.0, -5.0], and [0.0,5.0][0.0, 5.0], with the standard deviations are equal to 2.5 (highly diffuse), 1.2 (moderate), and 0.4 (highly dense). This configuration explicitly tests an algorithm’s ability to adapt to non-uniform cluster densities while simultaneously resisting the effect background outliers. The number of clusters of the algorithm was initialized to 15 and the sparsity penalty multiplier prior to s=10s = 10. The elimination threshold was set to 15 and the distance threshold for merging to 5.

  • Experiment B: We generated a mixed-distribution dataset containing uniform background noise (sampled across a [−8.0,8.0]2[-8.0, 8.0]^2 domain) and four clusters with distinct statistical profiles: a Gaussian cluster centered at [−2.5,2.0][-2.5, 2.0] (standard 0.75) with 300 points, a bounded uniform disc centered at [−2.0,−2.5][-2.0, -2.5] (radius 2.0) with 300 points, a skewed log-normal cluster base-centered at [0.5,−4.5][0.5, -4.5] (μ=0.0\mu= 0.0, σ=0.65\sigma= 0.65) with 300 points, and a heavy-tailed Laplace cluster centered at [2.0,2.0][2.0, 2.0] (scale 1.3). To explicitly test the algorithms’ robustness against heavy-tailed data, the Laplace cluster is positioned so its double-exponential tail bleeds into the adjacent Gaussian cluster, and its total number of points (NLapN_{\mathrm{Lap}}) is systematically varied from 30 to 60. For this setup, the elimination threshold was increased to 20 and the sparsity penalty decreased to 5 to account for more closely positioned clusters.

These data do not have a specific geometry (e.g. line segments), and the basic GSFC algorithm with point representatives is employed. They serve merely as a preliminary testbed.

In this evaluation, we have used the Adjusted Rand Index (ARI) [25], a statistical measure used in machine learning and data science to evaluate and compare the similarity of two data clusterings. Since the data are synthetic, the clustering results for each case are compared against the ground-truth grouping of the data. All performance scores in this section constitute averages computed out of 10 runs with different initialization conditions each.

Remark: Throughout this section, FCM and other conventional algorithms like K-means or Gaussian Mixture Models (GMM) are implemented using skfuzzy [30] or sklearn [23]. This implies that the true number of clusters is provided as an argument, hence they have a pretty significant advantage over GSFC.

The resulting scores are reported in Figure 2, where the impact of sparsity in clustering performance is evident. Figure 2a reveals that FCM is highly sensitive to noise points. When there are no noise points it matches the performance of GSFC. However, as the number of such points increase its ARI score exhibits a steep decline. Furthermore, as shown 2b the heavy-tailed Laplacian data leads FCM to a very low ARI score compared to our method. Both GSFC pathways accurately filter-out noise points and compute the true number of clusters, while achieving ARI scores larger than 0.9 for all experimental configurations. Finally, as indicated by the shaded regions, GSFC displays strong robustness to initialization conditions as the number of noise/Laplacian points increases.

Figure 2. Robustness evaluation of GSFC Pathways 1 and 2 compared to the FCM baseline. (a) ARI scores across varying levels of uniform background noise. (b) ARI scores as the number of Laplacian data points increases. Solid lines denote the mean ARI across multiple initializations, while the shaded regions bound the minimum and maximum observed values.

UCI Wine Dataset

To evaluate the algorithm’s capability to autonomously recover cluster cardinality in higher-dimensional real-world data, we applied GSFC to the UCI Wine dataset [2]. Comprising 178 samples spanning 13 standardized chemical attributes, the dataset contains three (3) distinct clusters. We over-initialized two GSFC configurations (Pathway 1, q=1.5q = 1.5, p=0.5p = 0.5; Pathway 2, q=2.0q = 2.0, p=0.5p = 0.5) with m0=6m_0 = 6 clusters, whereas the sparsity multiplier is set to s=0.1s = 0.1 and the elimination gap to 2.0. To provide a more comprehensive assessment of the cluster quality, we additionally evaluated the Normalized Mutual Information (NMI) and the internal cluster cohesion via the Silhouette score.

We compared the performance of GSFC against baseline FCM, K-means, and GMMs, with the results being reported in Table 1. Interestingly, both pathways converge to the same exact ARI score, outperforming all benchmarks. At the same time they successfully learn the true number of clusters. This performance improvement occurs because the sparsity penalty truncates long-tail fuzzy assignments to absolute zero, preventing distant data points from skewing centroid calculations and allowing the remaining prototypes to lock perfectly onto the true density peaks. Furthermore, a crucial observation is the stability of GSFC under initialization conditions: across multiple independent initializations, both pathways consistently converge to identical metric scores, underscoring the algorithm’s robustness against suboptimal initial cluster placements.

MetricAlgorithmInitial m(0)m^{(0)}Estimated m∗m^{*}Score (Mean ±\pm Std)
ARIK-means330.8968 ±\pm 0.0249
FCM330.8785 ±\pm 0.0063
GMM330.4084 ±\pm 0.0116
GSFC (Pathway 1)630.8975 ±\pm 0.0000
GSFC (Pathway 2)630.8975 ±\pm 0.0000
NMIK-means330.8737 ±\pm 0.0245
FCM330.8464 ±\pm 0.0064
GMM330.5066 ±\pm 0.0185
GSFC (Pathway 1)630.8759 ±\pm 0.0000
GSFC (Pathway 2)630.8759 ±\pm 0.0000
SilhouetteK-means330.2597 ±\pm 0.0336
FCM330.2836 ±\pm 0.0005
GMM330.2587 ±\pm 0.0012
GSFC (Pathway 1)630.2849 ±\pm 0.0000
GSFC (Pathway 2)630.2849 ±\pm 0.0000

Table 1. Quantitative comparison on the UCI Wine dataset across 5 independent runs. Competitors are provided with the true number of clusters (3), whereas GSFC autonomously recovers it from an over-initialization of m(0)=6m^{(0)} = 6.

In Fig. 3 we evaluated both optimization pathways for different values of ss. As is evident, the ARI scores remain consistently over 0.75. In fact, for almost all configurations it is higher than 0.85, highlighting the robustness of GSFC to the parameter ss.

ARI scores for Pathway 1 and Pathway 2 at different sparsity penalty values

Figure 3.

Image not extracted

Figure 3 (PDF p. 14). Sensitivity Study in the UCI Wine Dataset: The average ARI scores of both pathways are reported for different values of the sparsity parameter ss.

Breast Cancer Wisconsin (Diagnostic) Dataset

We considered an additional real-world tabular dataset, the Breast Cancer Wisconsin (Diagnostic) Dataset [27]. It comprises of 30-dimensional features from 569 patients (i.e., 569 points), extracted from medical images. There are two official classes in the dataset, Malignant (cancerous) and Benign (non-cancerous/healthy tissue). We initialized both GSFC paradigms with m(0)=6m^{(0)} = 6 clusters (3 times the number of true ground truth value). Just like the previous results, the sparsity multiplier is set to s=0.1s = 0.1 and the elimination gap to 2.0.

The results against FCM, K-means, and GMM are reported in Table 2. As demonstrated, GSFC Pathway 1 successfully bypasses the limitations of traditional algorithms, achieving top performance by autonomously recovering the correct cluster count (m∗=2m^{*} = 2) from over-initialization while outperforming standard K-means and FCM in ARI (0.6883), NMI (0.5733), and Silhouette. In contrast, while Pathway 2 can successfully prune the cluster down to the correct number (2), its ARI and NMI are substantially smaller. Interestingly, Pathway 2 achieves the highest Silhouette score (0.3537) among all methods.

Quantitative comparison on the Breast Cancer Wisconsin (Diagnostic) (WDBC) dataset across 5 independent runs. Competitors are provided with the true number of clusters (2), whereas GSFC autonomously recovers or evaluates it from an over-initialization of m(0)=6m^{(0)} = 6.

MetricAlgorithmInitial m(0)m^{(0)}Estimated m∗m^{*}Score (Mean ±\pm Std)
ARIK-means220.6662 ±\pm 0.0105
ARIFCM220.6829 ±\pm 0.0000
ARIGMM220.0000 ±\pm 0.0000
ARIGSFC (Pathway 1)620.6883 ±\pm 0.0000
ARIGSFC (Pathway 2)620.4245 ±\pm 0.0000
NMIK-means220.5481 ±\pm 0.0134
NMIFCM220.5612 ±\pm 0.0000
NMIGMM220.0000 ±\pm 0.0000
NMIGSFC (Pathway 1)620.5733 ±\pm 0.0000
NMIGSFC (Pathway 2)620.3614 ±\pm 0.0000
SilhouetteK-means220.3432 ±\pm 0.0009
SilhouetteFCM220.3400 ±\pm 0.0000
SilhouetteGMM220.0000 ±\pm 0.0000
SilhouetteGSFC (Pathway 1)620.3433 ±\pm 0.0000
SilhouetteGSFC (Pathway 2)620.3537 ±\pm 0.0000

Table 2.

This paradox stems from the behavior of the quadratic penalty in high dimensions. In high-dimensional spaces, the distances between points are very large, meaning a point’s distance to different centroids will not be vastly different. This leads to highly fractional memberships; for instance, most uiju_{ij} values will be closer to 0.5 than to 0.9. Because these values are strictly less than 1, the quadratic term (q=2.0q = 2.0) shrinks them even more drastically (0.9² = 0.81 vs. 0.5² = 0.25). To improve the cost function, the centroids are essentially "forced" apart to achieve strong exclusive memberships close to 1.0. As these centroids are pushed toward the edges of the space, they create wide separation and thus achieve a great Silhouette score. However, the resulting decision boundary for the "middle" points is completely wrong, leading to poor performance in external metrics that use the actual labels, such as ARI and NMI.

Again, both methods are exceptionally robust to initialization conditions. Consider a dataset with two clusters A, B. If for instance a classical possibilistic algorithm initialized with 2 clusters is provided with a bad initialization with all centroids being placed inside cluster A and far away from point B, then there is a significant risk that it will get trapped to a local optimum. On the contrary, GSFC is initialized with multiple cluster representatives, meaning that each true cluster will probably have at least one or two potential representatives inside or near it. The dense point clouds of the cluster will drag these centroids inside the cluster and close to the true center, whereas the sparsity penalty will force the membership weights of points away from them (from other clusters) to small values. When they are close to each other they will get merged into one. In contrast, potential representatives initialized away from all clusters will be pruned. Hence, GSFC mitigates the initial noise due to the centroid initialization, displaying profound robustness across all datasets considered.

HyperSpectral Images (HSIs)

We will now evaluate GSFC on three publicly available HSIs. The Salinas-A scene [26], the Pavia university scene [22], and the AVIRIS Cuprite dataset [21]. All three datasets contain ground truth labels for the pixels and hence we can evaluate GSFC using metrics like the ARI score. The following pre-processing pipeline was performed for all three images:

  1. Pixels with a zero-class label are excluded.

  2. Spectral signatures are normalized to zero mean and unit variance.

  3. Finally, PCA projects the 200+ bands down to d=10d = 10 components, mitigating high-frequency noise while preserving spatial variance.

The Salinas-A hyperspectral scene, captures an agricultural area in Salinas Valley, California. The image comprises a 220×120220 \times120 spatial grid with a spatial resolution of 3.7 meters per pixel, yielding a total of N=26,400N = 26{,}400 sample pixels across 204 spectral bands. The ground truth defines seven distinct crop classes (grapes, broccoli, fallow 1, fallow 2, fallow 3, stubble, and celery), while unlabeled background pixels are masked out from the evaluation. To demonstrate autonomous structural recovery, GSFC is heavily over-initialized with 15 candidate prototypes. The sparsity parameter is set to s=0.01s = 0.01. In highly mixed datasets (like mineral mixtures or diffuse distributions), a larger ss may be required. However, agricultural hyperspectral scenes like Salinas-A consist of human-planted blocks where crop types change abruptly at field boundaries rather than blending smoothly. The cardinality pruning threshold is set to eelim=500.0e_{\mathrm{elim}} = 500.0 (requiring a cluster to claim roughly 2% of the image’s total membership weight to justify its existence) and the coalescence gap to egap=5.0e_{\mathrm{gap}} = 5.0.

For reference, we again considered the classic K-means algorithm, the FCM and the GMM (again the implementations require precise specification of the number of clusters). GSFC correctly infers the true number of clusters, and the ARI scores presented in Figure 4 illustrate that it outperforms all baselines. Interestingly, classic FCM is highly sensitive to initialization conditions. For some "lucky" runs it comes close to matching the ARI scores of GSFC but for some other "unlucky" runs it outputs very low-quality clusterings.

Figure 4. ARI scores for the Salinas-A HSI task.

While Salinas-A contains a rural scene, in order to have a broad dataset pool, we also considered the Pavia university image, which captures a complex urban campus environment in Pavia, northern Italy. The HSI comprises 610×340610 \times340 pixels across 103 usable spectral bands. Excluding the unlabeled background, the dataset contains 42,776 valid pixels distributed across 9 distinct ground-truth classes, representing diverse materials. As shown in Figure 5 the GSFC (with the same parameter configuration as the one used for the Salinas-A image) outperforms all baselines in terms of ARI by a significant margins, while also outputting the correct number of clusters. Its dense counterpart performs extremely poorly.

ARI scores for the Pavia university HSI task

Figure 5. ARI scores for the Pavia university HSI task.

Finally, the AVIRIS Cuprite HSI, captured by NASA’s Airborne Visible Infrared Imaging Spectrometer over the Cuprite Hills mining district in Nevada, serves as a benchmark for geological and mineralogical remote sensing. The scene is globally renowned for its exposed, diverse mineral types (such as alunite, buddingtonite, calcite, and kaolinite). Unlike the neatly managed agricultural blocks of Salinas-A, the Cuprite scene is characterized by complex, irregular mineral outcroppings interspersed with extensive background scatter, atmospheric noise, and pervasive mixed-pixel boundaries. These geological characteristics create a challenging environment where traditional clustering algorithms frequently fail due to their susceptibility to background interference.

While the Cuprite scene encompasses a broad range of potential mineral types across the entire landscape, any individual pixel physically comprises only a small subset of those elements. This localized reality provides an ideal physical justification for GSFC’s sparsity component: rather than forcing a pixel’s membership to leak across numerous irrelevant mineral classes (as standard dense fuzzy clustering tends to do), the sparsity penalty mathematically enforces that a pixel’s composition is active in only a few matching clusters.

The ARI scores are depicted in Figure 6. To evaluate the robustness/sensitivity to the choice of ss we actually sweeped ss from a very small value of 0.01 to 10 (the rest of the parameters are set to the same values as the previous HSI experiments). The evaluation on the Cuprite dataset demonstrates that both GSFC pathways consistently outperform classical baselines like K-means, GMM, and standard FCM across a wide range of sparsity configurations (despite also needing to learn the true number of clusters). Furthermore, the performance exhibits strong empirical robustness to the choice of ss; except for Pathway 2 under excessively large sparsity penalties where performance degrades, the resulting ARI scores remain superior to all competing benchmarks, confirming the stability and efficacy of the noise-aware sparse framework. Pathway 1 correctly infers m∗m^{*} for all considered values of ss, and Pathway 2 for all s≤2s \le2. If s>2s > 2 it slightly over-prunes estimating one less cluster.

ARI scores for the AVIRIS Cuprite HSI task

Figure 6. ARI scores for the AVIRIS Cuprite HSI task.

Line Segment Identification

Having established the effectiveness of sparsity in the fuzzy clustering pipeline, we now evaluate our framework against two alternative soft sparse clustering approaches for line detection: the possibilistic scheme SPCLS of [16] and the probabilistic framework PLSC of [28]. To ensure a fair and direct comparison, we adhere as closely as possible to their reference implementations and recommended hyperparameter selections. Rather than evaluating idealized, one-pixel-thin line segments, each segment is modeled as a 2D point cloud with slight spatial noise around the line, simulating imperfect resolution. To rigorously assess performance of GSFC across varied challenges, we examine 7 images with distinct geometrical properties, initializing each model with m(0)=12m^{(0)} = 12 candidate prototypes:

  • Case 1: Three-line Concurrent Intersection (Figure 7). Three distinct line segments intersect concurrently at the origin with varying angular separations. This setup evaluates whether the models can isolate intersecting linear manifolds without suffering from prototype merging or over-partitioning near the dense center.

  • Case 2: Eight-line Radial Starburst (Figure 8). This is a more challenging version of the previous experiment. Eight symmetric lines intersect at a single central hub, generating an exceptionally dense intersection with acute inter-line angles. This experiment will highlight the importance of sparsity.

  • Case 3: Overlapping Rectangles / Floppy Disk (Figure 9). This scenario features a closed rectangle inside another rectangle. Sparsity is important, in order to ensure that nearby inside and outside segments are not conflicted.

  • Case 4: Triangle with Horizontal Intersection (Figure 10). A closed triangular frame is intersected by a long horizontal segment, yielding four intersection points.

  • Case 5: Imbalanced H-Shaped Configuration with T-Junctions (Figure 11). Two vertical uprights (legs) connected by a central horizontal crossbar forming an H. This experiment is particularly interesting because the crossbar contains 2.5× higher point density than each leg, creating two sharp T-junctions with severe density imbalance. The detector must leverage sparsity to ensure points along the dense interior segment are not erroneously assigned to the legs, where they would act as anchors dragging the uprights into a twisted orientation

Four panels showing SPCLS, PLSC, GSFC Pathway 1, and GSFC Pathway 2 for three line segments intersecting at a single point

Figure 7. Case 1: 3 Line segments intersecting at a single point. While all methods can reconstruct the underlying geometry, the method of [28] introduces slight over-segmentation overestimating the true number of clusters. Both pathways and the algorithm of [16] estimate the correct number of clusters and produce the correct line segments.

Four panels showing SPCLS, PLSC, GSFC Pathway 1, and GSFC Pathway 2 for eight line segments intersecting at a single point

Figure 8. Case 2: 8 Line segments intersecting at a single point. The algorithm of [28] suffers from hub fracturing: hard Bayes partitioning creates spatial contention at the dense junction, leaving several components prematurely truncated as radial half-spokes, while [16] exhibits phantom secants: unconstrained possibilistic memberships accumulate mass transversely across adjacent rays, yielding spurious chords near the hub while dropping one true diameter. Finally, the proposed GSFC can accurately infer the true geomery for both optimization pathways.

Four panels showing SPCLS, PLSC, GSFC Pathway 1, and GSFC Pathway 2 for overlapping rectangles

Figure 9. Case 3: Overlapping Rectangles/Floppy Disk. All algorithms can learn the underlying segments’ position and orientation, with minor performance difference. The method of [28] results in slightly shorter outside vertical segments (small empty spaces).

Triangle with horizontal intersection, showing SPCLS, PLSC, GSFC Pathway 1, and GSFC Pathway 2

Figure 10. Case 4: Triangle with Horizonal Intersection Both proposed GSFC pathways accurately reconstruct the complex intersecting geometry of the four distinct line segments without fragmentation (although the left triangle side is slightly twisted for pathway 1). The method of [28] severely over-segments the structure resulting in 10 fragmented clusters. While the method of [16] identifies the correct number of clusters, the intersections act as heavy ’anchors’, physically twisting the estimated segments away from their ground-truth values.

Imbalanced H-shaped intersection, showing SPCLS, PLSC, GSFC Pathway 1, and GSFC Pathway 2

Figure 11. Case 5: Imbalanced H-shaped Intersection The horizontal crossbar contains 2.5× the data of the vertical legs. The method of [28] exhibits severe over-segmentation (m∗=9m^{*} = 9). While both [16] and the proposed GSFC pathway 1 (q=1.5q = 1.5) accurately infer the true cluster cardinality (m∗=3m^{*} = 3), their vertical legs display slight angular distortion induced by the denser crossbar points (albeit pathway 1 enables a slightly tighter reconstruction). In contrast, pathway 2 delivers near-perfect line segment extraction.

The results are provided in Figure 7-Figure 11, where thick black segments designate the final estimated cluster representatives.

Remark: While numerous specialized techniques exist for line segment detection (for example references [11, 9, 3]), establishing a state-of-the-art extraction pipeline is beyond the scope of this work. Rather, this application serves as a rigorous geometric testbed to demonstrate that the proposed sparse fuzzy framework structurally outperforms existing possibilistic and probabilistic sparse clustering paradigms.

In summary, visual evaluations across these geometric configurations confirm that the sparse GSFC framework provides a substantial structural advantage over alternative soft-clustering methods. By mathematically enforcing local competition through sparsity, our method successfully resolves complex intersections and bypasses the coincident cluster traps that plague [16]—a direct consequence of the lack of membership competition in possibilistic frameworks. Furthermore, GSFC prevents the severe over-segmentation seen in the [28] probabilistic baseline, whose rigid parametric distribution assumptions restrict its ability to organically adapt to irregular, dense, or non-Gaussian intersecting structures.

Stress-Testing

To evaluate the structural robustness of GSFC under severe spatial noise and understand its limitations, we generated synthetic point clouds comprising three line segments, two of which intersect. Unlike the complex geometric benchmarks evaluated previously (Cases 1-5), this simpler configuration was deliberately selected to isolate the direct impact of point-cloud dispersion (σ\sigma) from compound structural entanglements such as multi-way intersections or asymmetric crossbars. The point distribution strictly follows the generative model proposed in [28], where a 2D dispersion is centered around a line segment parameterized by its endpoints. Stress-testing is conducted by systematically varying the variance σ∈[0.05,0.30]\sigma\in[0.05, 0.30] of the points normal to the carrier lines. To rigorously evaluate autonomous cardinality resolution under noisy conditions, GSFC is initialized with an overcomplete set of m(0)=10m^{(0)} = 10 candidate prototypes. The results are depicted in Figure 12, where the robustness is highlighted. For all noise levels the algorithm maintains sharp, geometrically accurate boundaries at the dense intersection point, correctly identifying the two top segments. For larger values of σ\sigma (0.22 and 0.3) there is some slight over-segmentation, where the bottom segment is split into two prototypes, potentially requiring a looser merging threshold to account for the high point cloud noise.

Stress-testing GSFC pathway 2 in line detection at different segment and cluster variance levels

Figure 12. Stress-testing GSFC pathway 2 in line detection: The point generating model of [28] is considered with different segment/cluster variance levels σ\sigma. For variances up to σ=0.2\sigma= 0.2, the segment reconstruction is near perfect. For σ=0.22\sigma= 0.22 and σ=0.3\sigma= 0.3, there is a small issue in the bottom line segment, which is split in two clusters, but the top intersecting segments are consistently estimated correctly.

In contrast, in Figure 13 we repeated the same experiment for the algorithm proposed in [28]. As is evident, for σ>0.1\sigma> 0.1 the algorithm collapses significantly over-segmenting the line segments and producing too many clusters. Hence, our framework is substantially more robust to noise.

Figure 13. Stress-testing the algorithm of [28] for line detection: Different segment/cluster variance levels σ\sigma are considered for the same point generating model. The algorithm is substantially less robust than GSFC, producing oversegmentation for σ≥0.1\sigma\ge0.1, which is severely worsened as σ\sigma increases.

Finally, Figure 14 illustrates the stress-test evaluation of the algorithm proposed in [16]. Although the baseline correctly infers the true number of segments for σ<0.3\sigma< 0.3, points from the two upper intersecting segments are erroneously assigned to the bottommost cluster. This misclassification severely distorts the estimated orientation of the bottom segment away from its true angle. This phenomenon exacerbates as the variance σ\sigma increases, progressively degrading the orientation estimates of the intersecting top segments as well. Ultimately, at σ=0.3\sigma= 0.3, the algorithm collapses and entirely fails to identify one of the top intersecting segments.

Figure 14. Stress-testing the algorithm of [16] for line detection: Different segment/cluster variance levels σ\sigma are considered for the same point generating model. While the algorithm can consistently identify the true number of clusters (besides the experiment with the largest σ\sigma), some points are incorrectly assigned to the wrong segment (resulting in incorrectly estimated and overly long line segments), with the issue worsening as σ\sigma increases.

General Discussion

The empirical evaluation across two synthetic toy datasets, two tabular real-world dataset, six line-segment detection scenarios, and three real-world HSIs establishes several consistent behavioral characteristics of the proposed GSFC framework. The key takeaways are:

  • Autonomous cardinality recovery: Across all tested domains the proposed framework consistently and autonomously learns the true number of clusters. By dynamically pruning redundant prototypes, GSFC eliminates the need for prior knowledge of the cluster cardinality, overcoming a major fundamental limitation of baseline methods.

  • Sparsity enhances fuzzy fidelity: Enforcing a sparsity penalty on membership assignments generally yields noticeable performance improvements over standard non-sparsity aware fuzzy clustering.

  • Superiority over standard baselines: GSFC consistently outperforms traditional hard partitioning (K-means) and GMM, demonstrating stronger resilience to noise, scattered outliers, and structural ambiguity.

  • Advancements in elongated cluster case: The proposed line-detection variant of the framework outperforms existing soft-clustering alternatives in line segment detection. It successfully resolves intersecting geometries,

handles dense overlaps, and dynamically prunes redundant prototypes where traditional methods force false alignments.

  • Hyperparameter robustness: The algorithm exhibits empirical stability regarding the sparsity strength parameter, ss. Sensitivity analyses confirm that clustering performance remains high and superior to baseline benchmarks across a wide operational range, degrading only when ss is pushed to excessively aggressive extremes.

  • Robustness to Initialization Conditions: Interestingly, both GSFC optimization pathways exhibit extreme robustness to initialization. We hypothesize that initializing with an excess of cluster representatives floods the data space, ensuring every true cluster has representatives placed near or within it from the onset. As dense point clouds drag nearby estimated representatives toward the true cluster centers, coincident representatives are systematically merged, while any isolated representatives stranded away from all clusters are pruned, preventing the algorithm from getting trapped in suboptimal local minima. In contrast, traditional algorithms with a fixed number of clusters can fail when poorly initialized; for instance, if multiple centroids are inadvertently placed within a single cluster while another cluster receives none, the algorithm can get trapped in a suboptimal partition because it cannot reposition or prune the redundant representatives.

We must, however, acknowledge that no learning algorithm is perfect, and our proposed framework certainly exhibits limitations. First, our empirical analysis uncovered a clear boundary condition regarding the choice of the membership exponent: while Pathway 1 (q=1.5q = 1.5) generalizes robustly across varying spatial dimensions, Pathway 2 (q=2.0q = 2.0) suffers a noticeable performance degradation in higher-dimensional settings (the 30-dimensional WDBC benchmark). As analyzed, quadratic membership decay exacerbates the distance concentration phenomenon, causing artificial cluster representative dispersion away from true positions. Second, because GSFC operates directly on the input feature space in the manner of standard fuzzy and partitioning frameworks, its clustering fidelity remains susceptible to the curse of dimensionality when presented with raw, uncurated data matrices; incorporating automated feature selection or representation learning pipelines constitutes a natural direction to safeguard high-dimensional geometry. Finally, the framework introduces several hyperparameters governing sparsity strength, cluster pruning, and fuzzification. While parameter dependency is a universally acknowledged trait across both fuzzy and sparse clustering paradigms [16, 28, 36, 6, 35, 35], our sensitivity analyses confirm that GSFC remains remarkably stable across broad operational ranges of the sparsity parameter ss and shows negligible variance across random initialization conditions.

Conclusion and Future Work

This paper presents the GSFC framework, which effectively addresses the fundamental limitations of dense membership assignments in traditional fuzzy clustering paradigms. By introducing a continuous sparsity penalty—solved via a novel primal-dual optimization methodology—the proposed framework organically drives trace memberships to exactly zero. This empowers the algorithm to autonomously estimate the true number of clusters by dynamically pruning redundant clusters from an initially overestimated state, bypassing a critical limitation present in nearly all existing fuzzy clustering literature. Furthermore, the integration of a virtual "noise sink" mechanism effectively neutralizes the impact of background outliers. Extensive empirical evaluations demonstrated that GSFC achieves highly competitive performance against traditional benchmarks on both synthetic and real-world datasets. Most notably, when adapted for treating elongated clusters, the framework successfully outperformed baseline probabilistic and possibilistic alternatives in complex line segment detection scenarios.

Future research will explore integrating the proposed sparse membership formulation with complementary sparsity paradigms and recent architectural advancements in the clustering literature. Notably, while prior studies predominantly employ sparsity as an external mechanism (such as for sparse noise decomposition, or feature selection), they continue to compute traditional dense fuzzy memberships. A promising direction is to unify these methodologies with GSFC, combining feature or subspace level sparse learning with our sparse partition solver to achieve dual-level sparsity in high-dimensional domains. Furthermore, we envision coupling GSFC with Neural Network (NN)-driven soft clustering frameworks to enhance representation learning across complex manifolds [32, 29]. Finally, we aim to extend the GSFC framework to accommodate large-scale, streaming environments by developing an online optimization variant of our primal-dual bisection algorithm [20].

CRediT authorship contribution statement

George Stamatelis: Methodology, Software, Writting. Konstantinos Koutroumbas: Conceptualization, Writing, Supervision.

Computational Complexity Analysis

In this section, we analyze the computational complexity of the proposed GSFC framework for both point representatives and the line segment detection adaptation. Let NN denote the total number of data points, dd the dimensionality of the feature space, and m(0)m^{(0)} the initial (overestimated) number of cluster representatives. Because the active cluster count mm dynamically decreases via cardinality pruning and coalescence (m≤m(0)m \le m^{(0)}), the initial allocation m(0)m^{(0)} serves as a strict theoretical upper bound on the number of clusters evaluated at any iteration. The parameter tmax⁡t_{\max}, defined in Algorithm 2, denotes the maximum number of iterations allowed for convergence.

Point Representatives (Compact Clusters)

At any iteration of Algorithm 2, the workload across active clusters is strictly upper-bounded by m(0)m^{(0)} across four primary computational stages:

  1. Distance Computation: Evaluating the regularized Euclidean distances d(xr,θj)d(\mathbf{x}_r, \boldsymbol{\theta}_j) between all NN data points and candidate cluster representatives requires at most O(Nm(0)d)\mathcal{O}(Nm^{(0)}d) operations.

  1. Sparse Membership Evaluation (Algorithm 1): For each sample xr\mathbf{x}_r, the dual variable λr\lambda_r is determined via an outer bisection search over the interval [λmin⁡,λmax⁡][\lambda_{\min}, \lambda_{\max}] with stopping tolerance ϵbis\epsilon_{bis}. We introduce KbisK_{bis} to denote the worst-case number of bisection steps per sample, bounded by:

Kbis=⌈log⁡2(λmax⁡−λmin⁡ϵbis)⌉.(18)K_{bis} = \left\lceil\log_{2}\left(\frac{\lambda_{\max}-\lambda_{\min}}{\epsilon_{bis}}\right) \right\rceil. \tag*{(18)}

At each bisection step, evaluating the membership update formulas across all candidate clusters requires at most O(m(0))\mathcal{O}(m^{(0)}) operations for the closed-form solutions (Pathways 1 and 2), or O(m(0)KNR)\mathcal{O}(m^{(0)}K_{NR}) when utilizing the inner Newton-Raphson solver (where KNRK_{NR} denotes the average number of Newton iterations). Consequently, updating the membership matrix U\mathbf{U} requires at most O(Nm(0)Kbis)\mathcal{O}(Nm^{(0)}K_{bis}) operations under both analytic pathways.

  1. Cluster Update: Updating the cluster representatives via weighted averages across all NN samples incurs a cost of at most O(Nm(0)d)\mathcal{O}(Nm^{(0)}d).

  1. Cardinality Pruning and Merging: Computing cluster cardinalities requires at most O(Nm(0))\mathcal{O}(Nm^{(0)}) operations, while pairwise distance evaluations between active representatives scale as O((m(0))2d)\mathcal{O}((m^{(0)})^{2}d). Because m(0)≪Nm^{(0)} \ll N, this step is asymptotically negligible.

Summing the individual contributions, the worst-case overall time complexity of GSFC over tmax⁡t_{\max} iterations is:

O(tmax⁡Nm(0)(d+Kbis)).(19)\mathcal{O}\left(t_{\max}Nm^{(0)}(d+K_{bis})\right). \tag*{(19)}

Because tmax⁡t_{\max}, m(0)m^{(0)}, and KbisK_{bis} are fixed hyperparameters, the overall worst-case complexity scales pseudo-linearly with the number of samples NN. In practice, the effective per-iteration cost progressively decreases as redundant clusters are pruned. (m≪m(0)m \ll m^{(0)}).

Line Segment Adaptation

When adapting GSFC for line segment detection in 2D edge images (d=2d=2):

  1. Segment Distances: Computing the perpendicular and endpoint-bounded distances from NN edge points to mm candidate segments scales as O(Nmd)\mathcal{O}(Nmd).

  1. Membership Evaluation: Unchanged from the compact formulation, requiring O(NmKbis)\mathcal{O}(NmK_{bis}) operations.

  1. Weighted PCA Updates: Constructing the mm weighted covariance matrices Aj\mathbf{A}_j requires O(Nmd2)\mathcal{O}(Nm d^2) operations, and solving the d×dd \times d eigenvalue problem for each cluster requires O(md3)\mathcal{O}(m d^3).

  1. Pruning and Merging: Collinear angular and proximity evaluations across candidate segment pairs scale as O(m2d)\mathcal{O}(m^2 d).

For planar image processing where d=2d = 2, terms involving d2d^2 and d3d^3 reduce to small constant factors. Thus, the worst-case time complexity of the line segment extraction variant over tmax⁡t_{\max} iterations is:

O(tmax⁡Nm(1+Kbis))≡O(tmax⁡Nm).(20)\mathcal{O}\left(t_{\max}Nm(1+K_{\mathrm{bis}})\right) \equiv\mathcal{O}(t_{\max}Nm). \tag*{(20)}

References

  1. [1]Adler, A., et al., 2013. Probabilistic subspace clustering via sparse representations. IEEE Signal Processing Letters 20, 63–66. doi:10.1109/LSP.2012.2229705.DOI
  2. [2]Aeberhard, S., Forina, M., 1992. Wine. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C5PC7J.
  3. [3]Ballard, D.H., 1981. Generalizing the hough transform to detect arbitrary shapes. Pattern Recognition 13, 111–122.DOI
  4. [4]Bezdek, J.C., 1981. Pattern recognition with fuzzy objective function algorithms. Springer Science & Business Media.DOI
  5. [5]Chang, X., et al., 2017. Sparse regularization in fuzzy c-means for high-dimensional data clustering. IEEE Transactions on Cybernetics 47, 2616–2627. doi:10.1109/TCYB.2016.2627686.DOI
  6. [6]Chen, J., et al., 2023a. Sparsity fuzzy c-means clustering with principal component analysis embedding. IEEE Transactions on Fuzzy Systems 31, 2099–2111. doi:10.1109/TFUZZ.2022.3217343.DOI
  7. [7]Chen, Y., et al., 2023b. Fuzzy sparse subspace clustering for infrared image segmentation. IEEE Transactions on Image Processing 32, 2132–2146. doi:10.1109/TIP.2023.3263102.DOI
  8. [8]Dempster, A.Po., 1977. Maximum likelihood from incomplete data via the em algorithm. J. R. Stat. Soc., B 39, 1–22.DOI
  9. [9]Duda, R.O., Hart, P.E., 1973. Pattern Classification and Scene Analysis. Wiley, Hoboken, NJ, USA.
  10. [10]Dunn, J.C., 1973. A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters. Journal of Cybernetics 3, 32–57.DOI
  11. [11]Galambos, C., et al., 1999. Progressive probabilistic hough transform for line detection, in: Proc. IEEE CVPR, Los Alamos, CA, USA.
  12. [12]Gu, J., et al., 2017. Sparse learning based fuzzy c-means clustering. Knowledge-Based Systems 119, 113–125. doi:10.1016/j.knosys.2016.12.006.DOI
  13. [13]Guo, L., et al., 2020. Membership affinity lasso for fuzzy clustering. IEEE Transactions on Fuzzy Systems 28, 294–307. doi:10.1109/TFUZZ.2019.2905114.DOI
  14. [14]Huang, J., et al., 2024. Sparse membership affinity lasso for fuzzy clustering. IEEE Transactions on Fuzzy Systems 32, 1553–1563. doi:10.1109/TFUZZ.2023.3327668.DOI
  15. [15]Jung, Y.M., Whang, J.J., Yun, S., 2020. Sparse probabilistic k-means. Applied Mathematics and Computation 382, 125328. URL: https://www.sciencedirect.com/science/article/pii/S0096300320302940, doi:https://doi.org/10.1016/j.amc.2020.125328.
  16. [16]Koutroumbas, K.D., 2018. Introducing sparsity in possibilistic clustering: A unified framework and a line detection paradigm. IEEE Transactions on Fuzzy Systems 26, 2886–2898. doi:10.1109/TFUZZ.2018.2792467.DOI
  17. [17]Krishnapuram, R., Keller, J., 1993. A possibilistic approach to clustering. IEEE Transactions on Fuzzy Systems 1, 98–110.DOI
  18. [18]Krishnapuram, R., Keller, J.M., 1996. The possibilistic c-means algorithm: Insights and recommendations. IEEE Transactions on Fuzzy Systems 4, 385–393.
  19. [19]Liu, J., et al., 2025. Robust jointly sparse fast fuzzy clustering via ternary-tree-based anchor graph. IEEE Transactions on Fuzzy Systems 33, 2284–2294. doi:10.1109/TFUZZ.2025.3562834.
  20. [20]Mavidris, C.N., Baras, J.S., 2023. Online deterministic annealing for classification and clustering. IEEE Transactions on Neural Networks and Learning Systems 34, 7125–7134. doi:10.1109/TNNLS.2021.3138676.
  21. [21]NASA AVIRIS Cuprite Hyperpectral Image, . https://aviris.jpl.nasa.gov/data/free_data.html. Accessed: 2026-06-06.
  22. [22]Pavia University Hyperspectral Image, . https://www.kaggle.com/datasets/syamkarlа/pavia-university-hsi. Accessed: 2026-06-06.
  23. [23]Pedregosa, F., et al., 2011. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research 12, 2825–2830.arxiv.org/abs/1201.0490
  24. [24]Qiu, X., et al., 2015. A sparse fuzzy c-means algorithm based on sparse clustering framework. Neurocomputing 157, 290–295. doi:10.1016/j.neucom.2015.01.003.DOI
  25. [25]Rand, W.M., 1971. Objective criteria for the evaluation of clustering methods. Journal of the American Statistician Association 66, 846–850. doi:10.1080/01621459.1971.10482356.DOI
  26. [26]Salinas-A Hyperspectral Image, . https://www.kaggle.com/datasets/sreevallimanda/salinas-hyperspectral. Accessed: 2026-06-06.
  27. [27]Street, W.N., et al., 1993. Nuclear feature extraction for breast tumor diagnosis, in: Proceedings of SPIE 1905, Biomedical Image Processing and Biomedical Visualization, pp. 861–870. doi:10.1117/12.146898.
  28. [28]Stylianopoulos, K., Koutroumbas, K., 2021. A probabilistic clustering approach for detecting linear structures in two-dimensional spaces. Pattern Recognition and Image Analysis 31, 671–687. URL: https://doi.org/10.1134/S1054661821040222, doi:10.1134/S1054661821040222.
  29. [29]Vardakas, G., et al., 2026. Deep clustering using the soft silhouette score: Towards compact and well-separated clusters. Machine Learning 115, 81. doi:10.1007/s10994-026-07026-w.DOI
  30. [30]Warner, J., et al., 2024. Jdwarner/scikit-fuzzy: Scikit-fuzzy 0.5.0. URL: https://doi.org/10.5281/zenodo.13372212, doi:10.5281/zenodo.13372212.
  31. [31]Xenaki, S.D., et al., 2016. Sparsity-aware possibilistic clustering algorithms. IEEE Transactions on Fuzzy Systems 24, 1611–1626. doi:10.1109/TFUZZ.2016.2543752.DOI
  32. [32]Yang, B., et al., 2017. Towards k-means-friendly spaces: Simultaneous deep learning and clustering, in: Proc. ICML, Sydney, Australia. Yang, M.S., Benjamin, J.B., 2023. Sparse possibilistic c-means clustering with lasso. Pattern Recognition 138, 109348. URL: https://www.sciencedirect.com/science/article/pii/S0031320323000493, doi:https://doi.org/10.1016/j.patcog.2023.109348.
  33. [34]Zeng, S., et al., 2023. A sparse framework for robust possibilistic k-subspace clustering. IEEE Transactions on Fuzzy Systems 31, 1124–1138. doi:10.1109/TFUZZ.2022.3195298.DOI
  34. [35]Zhang, X., et al., 2025. Outlier resistant fuzzy clustering via row sparse discriminative embedding projection. IEEE Signal Processing Letters 32, 3735–3739.DOI
  35. [36]Zhang, Y., et al., 2019. Deviation-sparse fuzzy c-means with neighbor information constraint. IEEE Transactions on Fuzzy Systems 27, 185–199. doi:10.1109/TFUZZ.2018.2883033.DOI

Paper details

vlnc:W_w79vtttu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents