Uncertainty, Topology, and Graphs

Introduction

Clustering: k-means and FCM

k-means splits data into crisp clusters; fuzzy c-means expresses the boundary by degrees.

k-meansone objective1982

Each point goes to its nearest prototype, and each prototype moves to the mean of its points; the sum of squared distances never increases.
Lloyd · IEEE Trans. Inf. Theory, 1982
FCMone objective1981

Every point belongs to every cluster by a degree; the degrees soften with m.
Bezdek · Plenum, 1981

In short A prototype summarizes each group; crisp or fuzzy membership is the starting point of the three parts.

Part 1

Rough clustering finds uncertain regions between clusters by distances.

RCMrule-based2004

Each point belongs to every relatively close cluster, within β of the nearest: upper approximations.
Lingras & West · J. Intell. Inf. Syst., 2004 · Peters · Pattern Recognit., 2006
GRCMrule-based2017

One threshold with a ratio α and a difference β; α = 1 or β = 0 gives the classic rules.
Ubukata, Notsu, Honda · IJCSNS, 2017
ExRCMrule-based2026

Raises the distances to a power p, which shapes the clusters: round, polygonal or star-shaped; p = 1 gives GRCM.
Okimoto, Ubukata, Honda · IUKM, LNCS 16919, 2026

In short One family of thresholds for distance-based rough clustering; an exponent shapes the clusters.

Part 2

Rough set theory finds uncertainty by neighborhoods.

Rough membershipdefinition1994

The share of a point's neighbors that lie in a cluster.
Pawlak · Int. J. Comput. Inf. Sci., 1982 · Pawlak & Skowron · Wiley, 1994
RSCM · RMCMrule-based2018

Regions from neighborhoods (RSCM), or rough membership as weights (RMCM).
Ubukata et al. · JACIII, 2018 (RSCM) · JACIII, 2018 (RMCM)
RMCM2one objective2021

Rough membership inside the k-means objective; every update minimizes it.
Ubukata, Notsu, Honda · Information Sciences, 2021
Recommendationapplication2021

A user between groups draws on both, by rough membership, in collaborative filtering.
Kim, Ubukata, Notsu, Honda · ISIS, 2021

In short From distances to neighborhoods, and from rules to one objective; overlapping clusters can also link prototypes into a graph.

Part 3

Prototypes are kept in order on a map.

SOM · Batch SOMrule-based1982

Prototypes on a lattice; each input pulls its winner and the winner's neighbors.
Kohonen · Biol. Cybern., 1982
SOM-OLPone objective2026

Each point gets a continuous latent position; one objective, three closed-form updates, O(nC) per iteration.
Ubukata, Notsu, Honda · IJCNN, 2026 · arXiv · code
Heskes's energyone objective1999

SOM learning as one energy; its winners couple the nodes, at O(nC²) per iteration.
Heskes · Kohonen Maps, 1999

In short From winner nodes to latent positions, with one objective at O(nC) per iteration.