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 is a noisy observation, and it learns the "classic" (i.e., non-sparse) fuzzy membership weight , the prototypes and the sparse noise components . 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 () present in the dataset. The authors explicitly acknowledge that overestimating allows outliers to contaminate the clusters, while underestimating 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 . Because the algorithm relies on ranking sample contributions to strictly isolate normal samples, an inaccurate estimate of 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 -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 ) 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 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 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 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.:
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 be a set of data points, and be the set of cluster representatives, corresponding to the clusters , respectively. We consider first the case where the data points form compact clusters and, as a consequence, the cluster representatives , , are points in (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:
where is the euclidean distance of the i-th data point from the j-th representative, is the membership matrix, where is the degree of belongingness of the i-th data point to the j-th cluster, and is the so-called fuzzifier parameter. Also, is the sparsity exponent (hence, is the quasinorm of vector ), 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:
To minimize with respect to under constraint (2), we construct the Lagrangian function:
where is the vector of Lagrange multipliers. Setting the partial derivative with respect to (for a specific data point and a specific cluster ) to zero yields the first-order stationarity condition:
where .
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 from eq. (5), due to the simultaneous presence of and .
Determining Sparse Memberships using the Bisection Method
Here we will discuss an optimization procedure for inferring the membership assignments for a data point from eq. (5). Focusing on a specific cluster we need to solve
To eliminate the negative exponent (), we multiply both sides of the equation by , yielding:
We introduce a substitution variable (implying ) and define the exponent scalar . This implies that
allowing us to rewrite as . Eq. (5) elegantly reduces to finding the roots of the generalized function:
To determine if valid non-negative memberships exist, we analyze the graph of . At , . Taking the first derivative with respect to and setting it to zero yields the location of the local extremum:
Because the second derivative is strictly positive for all , represents the unique global minimum of for . The existence of valid membership roots depends entirely on the value of . We consider two cases:
Sparse Pruning (): 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 . In this case, the optimal assignment is driven to exact zero: .
Active Condition (): The function dips below the x-axis, producing, in general, two positive real roots. When , the derivative is strictly negative, which translates to a negative second derivative of the GSFC objective (). In this region, the local objective segment is concave. Therefore, the stationary point (the smaller solution of ) is a local maximum.
Conversely, when , becomes strictly positive. This flips the second derivative of the initial objective to be strictly positive as well (), making the local objective strictly convex in that region. Therefore, , the larger solution of , is a local minimum of with respect to . Hence, the optimal lies in the interval .
General Newton-Raphson+Bisection Solver
Because lacks a closed-form expression for arbitrary values of the exponent , the active condition () requires a two-level numerical solver to determine for a specific data point : an outer bisection search for the Lagrange multiplier , and an inner Newton-Raphson (NR) solver to compute at every (outer) bisection step, corresponding to a specific value. The NR solver is utilized times, one for each , . For a specific , it is initialized to the right of the corresponding .
For a given candidate dual variable generated by the outer bisection search, the NR inner loop refines the root iteratively via:
Upon convergence, the active sparse membership is recovered via
Having applied the above procedure times for the specific point , the outer bisection loop evaluates the partition residual , updating the search bounds until , where is a small user-defined parameter.
One important detail is how the search interval for the bisection method is configured. A trivial lower bound can be configured by setting . Then is a sum of positive numbers and hence, . This triggers the Sparse Pruning condition for every single cluster, forcing for all . Hence the partition residual is .
To get an upper bound, we start from the general equation
If we substitute and use the minimal distance , the exponents disappear ( and ), leaving us with the exact theoretical upper bound:
Since will be equal to 1 for one cluster and positive for the rest, it will hold . 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 that collapse into exact closed-form algebraic solutions. Specifically, setting (as in [16]) yields two primary pathways:
Pathway 1 (, ): Reduces eq. (8) to a quadratic equation , yielding the direct root formula:
Otherwise, is set to 0.
Pathway 2 (, ): Reduces to a depressed cubic equation , solved analytically via Viète’s trigonometric roots:
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 (Invoked iteratively per data point within GSFC)
Input: Distance vector for a single sample , sparsity factor , parameters , bisection tolerance .
Output: Sparse membership vector and optimal Lagrange multiplier .
Set bounds and
Set ,
while do
for do
Compute and
Evaluate active condition:
if then
{Sparse Pruning}
else
Find root of {Via closed-form pathways or NR}
end if
end for
Evaluate partition residual:
if then
break {Convergence achieved}
else if then
{Sum too large decrease }
else
{Sum too small increase }
end if
end while
Set and return
End Subroutine
Validity of the Membership Bounds
A critical mathematical requirement for fuzzy clustering is that the resulting memberships strictly lie within the valid interval for the value outputted by algorithm 1. In the proposed framework, these bounds are strictly enforced through two distinct mechanisms:
Non-negativity (): The lower bound is guaranteed directly by the closed-form derivations in both evaluation pathways. In Pathway 1, the thresholding condition explicitly sets if . If this condition is met, the active formula evaluates to a squared real number. Similarly, in Pathway 2, the cubic discriminant check sets if , while Viète’s formula yields a real root that is subsequently squared. Thus, for any evaluated , it is mathematically guaranteed that .
For the general case with arbitrary exponents () non-negativity is preserved. Under the sparse pruning condition (), the membership is directly assigned to . When the active condition holds (), the critical point
is strictly positive since . As we have shown, in that case, the objective’s local minimum resides on the branch . As a result, the inverse power transformation is a positive real power of a strictly positive real number (as ). Thus, strictly in the active regime, guaranteeing that holds universally for any valid configuration.
Upper Bound (): 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 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 , the constraint is strictly satisfied.
Determination of the Optimal Number of Clusters
To automatically determine the optimal number of clusters 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 is underpopulated or isolated, we compute the effective cardinality (total accumulated membership):
Then is declared as degenerate and is eliminated if its effective cardinality falls below a user-defined threshold .
This pruning mechanism serves two key roles: it allows the algorithm to be safely over-initialized with a large candidate cluster count , and it also prevents division-by-zero singularities during prototype update steps (which scale inversely with ).
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 , if their Euclidean distance falls below a merge threshold :
the two clusters are collapsed into a single prototype using a cardinality-weighted average:
Once the prototypes are merged, columns and in the membership matrix are removed. The exact optimal memberships and distances for the unified prototype 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 is computed (where denotes the current optimization loop iteration), the objective function of eq. (1) decouples across the active clusters, allowing each representative to be updated independently by solving . In the present case of point representatives, the updating equation takes the following closed-form expression:
The GSFC framework is described analytically in Algorithm 2.
Algorithm 2 General Sparse Fuzzy Clustering (GSFC)
Input: Data , initial prototype count , hyperparameters , thresholds , small constant , max iterations .
Output: Optimized cluster prototypes and sparse membership matrix .
Initialize: Overestimated prototypes , iteration counter .
repeat
Distance Calculation: For all and , compute regularized distances .
Membership Update: For each point , determine and compute sparse vector calling Algorithm 1 .
Cluster Elimination: Compute effective cardinality for all . For any cluster with , remove prototype and update total count .
Cluster Update: For each active cluster , update parameters:
Cluster Merging: Identify pairs satisfying . Merge into .
until or
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 , we integrate a virtual noise sink governed by a constant distance threshold, . Specifically, a dummy cluster is appended at a fixed distance 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 , , , positioned at 1, 2, 8, 9 and initialized the GSFC algorithm (for and ) with 3 cluster representatives , , and . The merging threshold is set to . 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 and 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 . Likewise , are only assigned to due to sparsity.
In Step 1, as and shift inward to 1.2 and 1.8, they localize tightly around their nearest individual points ( versus and vice-versa). Because GSFC enforces a distance-dependent activation threshold (see the condition of eq. (12)) representative is "excluded" from the clusters connected to 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 and as redundant representations of the same dense data region. They fuse into a single cluster representative at 1.50, restoring a unified representation of and pruning the cluster count from 3 to the true .
GSFC for Elongated Clusters
Adapting GSFC for the case of elongated clusters requires redefining representatives as finite segments bounded by endpoints and along infinite carrier lines . 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 combines the squared perpendicular distance to the infinite carrier line (first term in eq. (17) below) with the distance of the projection of on , , from the finite segment, which is completely defined by its two end points and , i.e., (second term in (17) below).
where . If falls outside (that is, outside the interval on with endpoints and ), . Otherwise, .
Representative Update Rule
Representatives are updated by solving a weighted eigenvalue problem. Given the weighted mean
and covariance matrix
the orientation vector is the eigenvector corresponding to the smallest eigenvalue of . The intercept is updated as . New endpoints and are determined by projecting points with significant membership () onto .
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 (), where .
To handle redundant clusters, two line segments are merged if they are (i) collinear () and (ii) spatially contiguous, meaning their spans overlap or their nearest endpoints lie within a small distance 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 -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 ( ranging from 0 to 300 points) sampled from . The Gaussian means are located at coordinates , , and , 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 . 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 domain) and four clusters with distinct statistical profiles: a Gaussian cluster centered at (standard 0.75) with 300 points, a bounded uniform disc centered at (radius 2.0) with 300 points, a skewed log-normal cluster base-centered at (, ) with 300 points, and a heavy-tailed Laplace cluster centered at (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 () 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, , ; Pathway 2, , ) with clusters, whereas the sparsity multiplier is set to 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.
| Metric | Algorithm | Initial | Estimated | Score (Mean Std) |
| ARI | K-means | 3 | 3 | 0.8968 0.0249 |
| FCM | 3 | 3 | 0.8785 0.0063 | |
| GMM | 3 | 3 | 0.4084 0.0116 | |
| GSFC (Pathway 1) | 6 | 3 | 0.8975 0.0000 | |
| GSFC (Pathway 2) | 6 | 3 | 0.8975 0.0000 | |
| NMI | K-means | 3 | 3 | 0.8737 0.0245 |
| FCM | 3 | 3 | 0.8464 0.0064 | |
| GMM | 3 | 3 | 0.5066 0.0185 | |
| GSFC (Pathway 1) | 6 | 3 | 0.8759 0.0000 | |
| GSFC (Pathway 2) | 6 | 3 | 0.8759 0.0000 | |
| Silhouette | K-means | 3 | 3 | 0.2597 0.0336 |
| FCM | 3 | 3 | 0.2836 0.0005 | |
| GMM | 3 | 3 | 0.2587 0.0012 | |
| GSFC (Pathway 1) | 6 | 3 | 0.2849 0.0000 | |
| GSFC (Pathway 2) | 6 | 3 | 0.2849 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 .
In Fig. 3 we evaluated both optimization pathways for different values of . 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 .

Figure 3.
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 .
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 clusters (3 times the number of true ground truth value). Just like the previous results, the sparsity multiplier is set to 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 () 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 .
| Metric | Algorithm | Initial | Estimated | Score (Mean Std) |
| ARI | K-means | 2 | 2 | 0.6662 0.0105 |
| ARI | FCM | 2 | 2 | 0.6829 0.0000 |
| ARI | GMM | 2 | 2 | 0.0000 0.0000 |
| ARI | GSFC (Pathway 1) | 6 | 2 | 0.6883 0.0000 |
| ARI | GSFC (Pathway 2) | 6 | 2 | 0.4245 0.0000 |
| NMI | K-means | 2 | 2 | 0.5481 0.0134 |
| NMI | FCM | 2 | 2 | 0.5612 0.0000 |
| NMI | GMM | 2 | 2 | 0.0000 0.0000 |
| NMI | GSFC (Pathway 1) | 6 | 2 | 0.5733 0.0000 |
| NMI | GSFC (Pathway 2) | 6 | 2 | 0.3614 0.0000 |
| Silhouette | K-means | 2 | 2 | 0.3432 0.0009 |
| Silhouette | FCM | 2 | 2 | 0.3400 0.0000 |
| Silhouette | GMM | 2 | 2 | 0.0000 0.0000 |
| Silhouette | GSFC (Pathway 1) | 6 | 2 | 0.3433 0.0000 |
| Silhouette | GSFC (Pathway 2) | 6 | 2 | 0.3537 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 values will be closer to 0.5 than to 0.9. Because these values are strictly less than 1, the quadratic term () 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:
Pixels with a zero-class label are excluded.
Spectral signatures are normalized to zero mean and unit variance.
Finally, PCA projects the 200+ bands down to 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 spatial grid with a spatial resolution of 3.7 meters per pixel, yielding a total of 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 . In highly mixed datasets (like mineral mixtures or diffuse distributions), a larger 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 (requiring a cluster to claim roughly 2% of the image’s total membership weight to justify its existence) and the coalescence gap to .
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 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.

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 we actually sweeped 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 ; 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 for all considered values of , and Pathway 2 for all . If it slightly over-prunes estimating one less cluster.

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 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

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.

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.

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).

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.

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 (). While both [16] and the proposed GSFC pathway 1 () accurately infer the true cluster cardinality (), 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 () 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 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 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 (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.

Figure 12. Stress-testing GSFC pathway 2 in line detection: The point generating model of [28] is considered with different segment/cluster variance levels . For variances up to , the segment reconstruction is near perfect. For and , 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 the algorithm collapses significantly over-segmenting the line segments and producing too many clusters. Hence, our framework is substantially more robust to noise.
!Stress-testing the algorithm of [28] for line detection bbox=0.08,0.08,0.93,0.29
Figure 13. Stress-testing the algorithm of [28] for line detection: Different segment/cluster variance levels are considered for the same point generating model. The algorithm is substantially less robust than GSFC, producing oversegmentation for , which is severely worsened as 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 , 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 increases, progressively degrading the orientation estimates of the intersecting top segments as well. Ultimately, at , the algorithm collapses and entirely fails to identify one of the top intersecting segments.
!Stress-testing the algorithm of [16] for line detection bbox=0.08,0.37,0.93,0.58
Figure 14. Stress-testing the algorithm of [16] for line detection: Different segment/cluster variance levels 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 ), some points are incorrectly assigned to the wrong segment (resulting in incorrectly estimated and overly long line segments), with the issue worsening as 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, . Sensitivity analyses confirm that clustering performance remains high and superior to baseline benchmarks across a wide operational range, degrading only when 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 () generalizes robustly across varying spatial dimensions, Pathway 2 () 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 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 denote the total number of data points, the dimensionality of the feature space, and the initial (overestimated) number of cluster representatives. Because the active cluster count dynamically decreases via cardinality pruning and coalescence (), the initial allocation serves as a strict theoretical upper bound on the number of clusters evaluated at any iteration. The parameter , 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 across four primary computational stages:
Distance Computation: Evaluating the regularized Euclidean distances between all data points and candidate cluster representatives requires at most operations.
Sparse Membership Evaluation (Algorithm 1): For each sample , the dual variable is determined via an outer bisection search over the interval with stopping tolerance . We introduce to denote the worst-case number of bisection steps per sample, bounded by:
At each bisection step, evaluating the membership update formulas across all candidate clusters requires at most operations for the closed-form solutions (Pathways 1 and 2), or when utilizing the inner Newton-Raphson solver (where denotes the average number of Newton iterations). Consequently, updating the membership matrix requires at most operations under both analytic pathways.
Cluster Update: Updating the cluster representatives via weighted averages across all samples incurs a cost of at most .
Cardinality Pruning and Merging: Computing cluster cardinalities requires at most operations, while pairwise distance evaluations between active representatives scale as . Because , this step is asymptotically negligible.
Summing the individual contributions, the worst-case overall time complexity of GSFC over iterations is:
Because , , and are fixed hyperparameters, the overall worst-case complexity scales pseudo-linearly with the number of samples . In practice, the effective per-iteration cost progressively decreases as redundant clusters are pruned. ().
Line Segment Adaptation
When adapting GSFC for line segment detection in 2D edge images ():
Segment Distances: Computing the perpendicular and endpoint-bounded distances from edge points to candidate segments scales as .
Membership Evaluation: Unchanged from the compact formulation, requiring operations.
Weighted PCA Updates: Constructing the weighted covariance matrices requires operations, and solving the eigenvalue problem for each cluster requires .
Pruning and Merging: Collinear angular and proximity evaluations across candidate segment pairs scale as .
For planar image processing where , terms involving and reduce to small constant factors. Thus, the worst-case time complexity of the line segment extraction variant over iterations is:
References
- [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]Aeberhard, S., Forina, M., 1992. Wine. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C5PC7J.
- [3]Ballard, D.H., 1981. Generalizing the hough transform to detect arbitrary shapes. Pattern Recognition 13, 111–122.DOI
- [4]Bezdek, J.C., 1981. Pattern recognition with fuzzy objective function algorithms. Springer Science & Business Media.DOI
- [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]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]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]Dempster, A.Po., 1977. Maximum likelihood from incomplete data via the em algorithm. J. R. Stat. Soc., B 39, 1–22.DOI
- [9]Duda, R.O., Hart, P.E., 1973. Pattern Classification and Scene Analysis. Wiley, Hoboken, NJ, USA.
- [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]Galambos, C., et al., 1999. Progressive probabilistic hough transform for line detection, in: Proc. IEEE CVPR, Los Alamos, CA, USA.
- [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]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]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]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]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]Krishnapuram, R., Keller, J., 1993. A possibilistic approach to clustering. IEEE Transactions on Fuzzy Systems 1, 98–110.DOI
- [18]Krishnapuram, R., Keller, J.M., 1996. The possibilistic c-means algorithm: Insights and recommendations. IEEE Transactions on Fuzzy Systems 4, 385–393.
- [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]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]NASA AVIRIS Cuprite Hyperpectral Image, . https://aviris.jpl.nasa.gov/data/free_data.html. Accessed: 2026-06-06.
- [22]Pavia University Hyperspectral Image, . https://www.kaggle.com/datasets/syamkarlа/pavia-university-hsi. Accessed: 2026-06-06.
- [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]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]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]Salinas-A Hyperspectral Image, . https://www.kaggle.com/datasets/sreevallimanda/salinas-hyperspectral. Accessed: 2026-06-06.
- [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]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]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]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]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]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.
- [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
- [35]Zhang, X., et al., 2025. Outlier resistant fuzzy clustering via row sparse discriminative embedding projection. IEEE Signal Processing Letters 32, 3735–3739.DOI
- [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


