ClusterLens Algorithms: PCA, KMeans, FAISS, HDBSCAN, And Graphs

After embedding, every image is represented by one vector:

image_0001.jpg -> [ 0.12, -0.44,  0.08, ...]
image_0002.jpg -> [ 0.10, -0.41,  0.11, ...]
image_0003.jpg -> [-0.72,  0.03,  0.55, ...]

Stacked together, these vectors form a matrix:

N = number of images
D = embedding dimension
matrix shape = N x D

For example:

20,000 images x 512 dimensions = 10,240,000 float values

At float32, the raw matrix costs about:

10,240,000 values * 4 bytes = about 40 MB

That is only the matrix. A desktop app also has image paths, thumbnails, UI objects, caches, indexes, and model runtime memory. The algorithm design has to account for this.

The matrix also needs a strict row contract:

The clustering backend usually returns row numbers, not file paths. If the row-to-path mapping changes after clustering, the UI can show the wrong images. That bug is easy to create when scan results, cache hits, and UI filtering are mixed too early.

A safer contract is:

1. scan files
2. freeze ordered image list
3. build embeddings in that order
4. cluster matrix rows
5. map labels back to frozen image list
6. apply UI filters after labels are stable

This is not algorithmically glamorous, but it is what keeps the product correct.

Not every grouping task asks the same question.

Semantic clustering:
  "Put conceptually similar images together."

Visual clustering:
  "Put visually similar images together."

Duplicate review:
  "Find images that are identical or near-identical."

These modes can use related machinery, but they should not be treated as the same product feature.

The most common mistake is to use a duplicate detector as a semantic clustering system. A perceptual hash can catch visually close images. It does not understand that a sketch of a dog and a photo of a dog are semantically related.

The opposite mistake is also common. Semantic embeddings can say two images are related, but they should not be used alone for destructive duplicate deletion. Similar meaning is not identical content.

KMeans assumes the data can be represented as k compact groups around k centers.

It asks:

Can these points be divided into k groups so each point is close to its group's center?

The objective is:

minimize sum(distance(point, assigned_center)^2)

The usual algorithm is Lloyd’s algorithm:

choose k initial centers
repeat:
  assign each point to the nearest center
  update each center to the mean of assigned points
until convergence or iteration limit

Worked example:

Then the centers move:

C1 = mean(A, B)
C2 = mean(C, D)

KMeans is a good product default when the user wants a fixed number of groups:

"Make 12 review groups."
"Split this folder into 30 buckets."
"Give me manageable chunks to inspect."

It is also easy to explain:

This cluster is centered around these representative images.
Images are ordered by closeness to the center.

But KMeans has clear failure modes.

That is why KMeans needs post-processing. It should not be the entire product.

MiniBatchKMeans is KMeans optimized for responsiveness.

Full KMeans uses every point in each iteration:

iteration 1: all 20,000 vectors
iteration 2: all 20,000 vectors
iteration 3: all 20,000 vectors

MiniBatchKMeans uses samples:

iteration 1: 512 vectors
iteration 2: 512 vectors
iteration 3: 512 vectors

Each batch nudges the centers:

new_center = old_center + learning_rate * (batch_mean - old_center)

The result is approximate, but often good enough for preview.

flowchart LR
  A[Prepared matrix] --> B[Sample batch]
  B --> C[Assign batch to centers]
  C --> D[Update centers]
  D --> B
  D --> E[Final labels]

Product wording should be honest:

Good wording:
  Fast approximate grouping for large folders.

Bad wording:
  More advanced clustering.

The tradeoff is speed versus stability. If the same folder produces slightly different grouping under MiniBatchKMeans, that is expected. The UI should avoid making approximate preview results look more authoritative than they are.

HDBSCAN is density-based clustering.

KMeans asks:

Can I split all points into k compact groups?

HDBSCAN asks:

Where are the stable dense regions, and which points are noise?

That is a better fit when the folder has unknown structure:

many vacation photos
some screenshots
some receipts
some one-off memes
some accidental duplicates
some unrelated downloaded images

HDBSCAN can mark points as noise:

cluster 0: 120 images
cluster 1: 88 images
cluster 2: 31 images
cluster -1: 247 outliers/noise images

The internal idea has several steps.

First, estimate local density. A point in a crowded region has nearby neighbors. A point in sparse space does not.

dense:
  o o o o
  o o o o

sparse:
          .       .            .

Second, use core distance. The core distance of a point is roughly the distance to its min_samples-th nearest neighbor.

small core distance -> dense area
large core distance -> sparse area

Third, build mutual reachability distance. This prevents sparse bridges from incorrectly joining dense groups.

mutual_reachability(a, b) =
  max(core_distance(a), core_distance(b), distance(a, b))

Fourth, build a hierarchy of clusters across density levels. HDBSCAN does not choose one fixed distance threshold immediately. It sees which groups persist as the density threshold changes.

Fifth, choose stable clusters from that hierarchy.

That is why HDBSCAN can find clusters without a predefined k.

Key parameters:

Useful explanation:

HDBSCAN is not better KMeans.
It answers a different question.

Outliers are not an afterthought. They are part of the product semantics.

Different backends produce outliers differently:

KMeans needs explicit outlier extraction if the product wants an outlier lane. One simple policy is centroid distance:

for each point:
  score = similarity(point, assigned_centroid)
  if score < threshold:
    move to outliers

The threshold should be visible or at least described, because outlier policy changes user trust. A photo moved to outliers is not “bad”; it is just not close enough to any chosen group under the current settings.

Good UI wording:

Outliers: images not confidently assigned to a cluster.

Bad UI wording:

Bad images.

Raw cluster members often arrive in row order. Row order is not meaningful to the user.

A better policy is to rank members by similarity to the cluster centroid:

centroid = mean(member_vectors)
centroid = normalize(centroid)

for each member:
  score = dot(member_vector, centroid)

sort by score descending

Then the first images in the UI are representative.

Before rerank:
  random scan order

After rerank:
  most central images first
  edge cases later

This one step can make clusters feel much more coherent because users judge a group by the first thumbnails they see.

CUDA can help when the workload is massively parallel:

embedding inference
large matrix multiplication
nearest-neighbor search
distance calculations
batched image preprocessing

But CUDA wording must be precise. If the shipped app uses a Torch CUDA build for model inference and FAISS CPU for vector acceleration, say that. Do not imply custom CUDA clustering kernels unless they actually exist, ship, and are benchmarked.

Accurate wording:

GPU builds can accelerate embedding inference through Torch CUDA.
FAISS CPU can accelerate vector operations without requiring CUDA.
Custom CUDA clustering kernels are a future optimization unless shipped and measured.

Conceptually, a CUDA distance kernel could work like this:

grid:
  one block handles a tile of images and centroids

threads:
  each thread computes partial dot products over dimensions

shared memory:
  cache centroid tiles

reduction:
  sum partial dot products

output:
  nearest centroid for each image

But writing that kernel is only worth it if profiling proves distance computation dominates runtime.

Reasons not to write a custom kernel too early:

data transfer can erase the gain
PyTorch/FAISS already provide optimized kernels
packaging CUDA increases release complexity
debugging numerical differences is expensive
CPU path still needs to exist

The pragmatic rule:

1. Make the CPU implementation correct.
2. Cache embeddings and avoid repeated work.
3. Use vectorized NumPy/scikit paths.
4. Add FAISS where vector search dominates.
5. Use Torch CUDA for model inference in GPU builds.
6. Write custom CUDA only after profiling proves it is necessary.

A simple implementation shape:

scan image paths
freeze ordered paths

for each path:
  load cached embedding if valid
  otherwise compute embedding
  store embedding with model signature and file fingerprint

matrix = stack embeddings in frozen order
matrix = float32(matrix)

if similarity mode uses cosine:
  matrix = l2_normalize(matrix)

if semantic mode and PCA is safe:
  matrix = PCA(matrix)
  matrix = l2_normalize(matrix)

labels = run_backend(matrix, options)

clusters = group row indexes by label
clusters = apply_outlier_policy(matrix, clusters)
clusters = merge_or_keep_tiny_clusters(matrix, clusters)
clusters = rerank_members_by_centroid(matrix, clusters)

explanations = compute_cluster_explanations(matrix, clusters)
return clusters, explanations, metrics

The metrics should include:

backend
input dimension
prepared dimension
PCA components if used
normalization
outlier count
cluster quality score
runtime
model signature

This makes clustering inspectable instead of magical.

Used:

L2 normalization
semantic PCA projection when safe
KMeans
MiniBatchKMeans
optional FAISS CPU backend
optional HDBSCAN backend
similarity graph clustering
outlier policy
tiny-cluster policy
centroid/member reranking
cluster explanations
perceptual hash index for duplicate-oriented lanes

Removed or avoided:

treating one clustering algorithm as universal
forcing HDBSCAN into fixed-k workflows
hiding PCA and backend choices
using perceptual hashes as semantic labels
presenting approximate preview results as final truth
automatic duplicate deletion from clustering alone

Deferred:

custom CUDA clustering kernels
automatic parameter tuning that overrides user intent
guaranteed perfect clusters
GPU FAISS claims unless the shipped build actually includes them
destructive cleanup based only on embedding similarity

The main lesson is that clustering is a system, not a single function call. A good implementation makes representation, backend, post-processing, and review policy explicit. That is what turns vector labels into a tool people can safely use.