09 Clustering

Tip

🆕 Դասերն անցկացված են։ Սլայդերը, նշումներով PDF-երը և տեսանյութերը ներքևում են՝ երկու դասախոսություն ([32], [33]) և երկու գործնական ([34] Սևան, [35] նկարի սեղմում)։

🎲 Random

Շաբաթվա պատահական հղումը՝ Interactive RGB / HSV demo — վեց սահիչ, երեքը RGB, երեքը HSV, բոլորն էլ նույն գույնի վրա։ Շարժիր մեկը, նայիր ինչպես են մյուսներն իրենք իրենց շարժվում։

Առանց պիտակների խմբավորում — և հետո պարզվում է, որ ամբողջ հարցը նրանում է, թե որ տարածությունում ես չափում հեռավորությունը 🎨

📚 Նյութը

Երկու դասախոսություն․ առաջինը՝ կլաստերիզացիա, երկրորդը՝ գունային տարածությունները, որոնց վրա հենվում են նկարների գործնականները։ Սլայդերը ml/09_clustering/ պանակում։

📝 Թեմայի վերաբերյալ հարցաշար (Google Form): TBD

References:

  • scikit-learn example: Color Quantization using K-Means
  • 🎛️ Interactive RGB / HSV demo — David J. Eck, Introduction to Computer Graphics (HWS, v1.4). Linked above as the random link; try setting saturation to 0 and watching what happens to R, G and B.
  • Specification of sRGB (ICC) — the transfer-function constants used in the gamma frames.
  • Charles Poynton, Digital Video and HD — the standard reference for the luma (Y′) vs luminance (Y) distinction and the Rec. 601 / Rec. 709 weight sets.
  • Bishop, Pattern Recognition and Machine Learning (2006), section 9.1.1 (image segmentation / compression with k-means).
  • Sentinel-2 L2A cloud-optimized GeoTIFFs on AWS — the satellite data, free and without an account.
  • ESA WorldCover 10 m v200 — the land-cover map used as ground truth (CC-BY 4.0).

🏡 Տնային

Project — Image compression with k-means 🧀🧀🧀

An image is just a grid of pixels, and every pixel is a point in RGB space (3 numbers). If you run k-means on the pixels and repaint each one with its cluster’s centroid color, the result uses only k colors — a much smaller palette for a small drop in quality. This is color quantization, the practical we set up at the end of the lecture.

Setup. Use any image you like (a photo, a painting — img/saryan_mountains.jpg is provided). Deliver one reproducible notebook, seed 509, ending with a 3–5 sentence conclusion. Resize the image down first if it is large — k-means on millions of pixels is slow.

Tasks.

  1. Load the image, reshape it to (n_pixels, 3), and scale the values to [0, 1].
  2. Quantize with k-means for several k (e.g. 2, 4, 8, 16, 32) and show the results next to the original.
  3. Choose a k: plot inertia (the elbow) and the silhouette against k, and argue for one value.
  4. Show the palette — the k centroid colors.
  5. Measure the compression honestly. A quantized image stores a palette (k × 3 bytes) plus one index per pixel (ceil(log2 k) bits), versus 24 bits/pixel originally — compute that ratio and the reconstruction error (MSE between original and quantized pixels). Explain in one line why comparing re-saved .jpg file sizes is misleading.
  6. Where does it break? Find a k low enough that banding / posterization shows up in smooth gradients (sky, shadows).

Everything above quantizes the numbers stored in the file, with k-means, and takes k as given. The next four tasks each challenge one of those three assumptions.

  1. Quantize the light, not the numbers. A centroid is an average of pixels — and from the colour-spaces lecture you know that averaging gamma-encoded values does not average the light they carry. So every palette you built above is biased. Measure it: for each k, compare the mean light (linearized) of your quantized image against the original’s. Then redo the whole thing in linear light — linearize, cluster, average, re-encode — and compare both the light error and the reconstruction error. Which k suffers most, and why does the gap shrink as k grows? One of the two methods preserves the total light in every cluster exactly; say which and prove it in one line of algebra, not by running it.

  2. A palette you can actually buy. A centroid is an invented colour: it is an average, so in general no pixel in the image has that colour. Check that — for k = 8, report the distance from each centroid to the nearest colour that actually occurs. If the palette has to be physically realizable (paint, thread, ink, a fixed display palette), you need k-medoids, whose palette entries are real pixels. scikit-learn has no k-medoids, so write the alternating loop yourself (assign to nearest medoid, then replace each medoid with the member minimising total distance to the rest; restrict candidates to a random subsample so it finishes). Report what realizability costs you in reconstruction error.

  3. Nested palettes. Run k-means at k = 8 and again at k = 16. Is every 16-colour group contained in exactly one 8-colour group? Test it, do not assume. Then do the same with agglomerative (Ward) clustering on a subsample, cutting the same dendrogram at 8, 16 and 32. Report which method gives nested palettes and explain why that falls out of how each algorithm works. Then say where nesting is worth having — think about an image that must render progressively, or one palette that has to degrade gracefully onto a weaker device.

  4. Let the data choose the number of colours. Every task so far handed the algorithm a k. Run DBSCAN on a subsample of the pixels for several eps values, and HDBSCAN too. Report clusters found and the percentage marked as noise for each setting. You will hit a problem k-means never poses: noise points have no centroid, so what colour do you paint them? Decide, justify it, and show the result. Then answer the real question in two sentences: is “how many colours are in this image” a question density can answer, and if not, what is it about a photograph’s colour cloud that defeats it?

Bonus: MiniBatchKMeans to quantize the full-resolution image fast; quantize in Lab and score with ΔE instead of MSE (watch the scaling — L* runs 0–100 while a*/b* run about ±128, which is exactly the trap from the clustering lecture); fix the banding from task 6 with Floyd–Steinberg dithering and say what it trades away; pick k automatically from the elbow.

Լուծումը (ամբողջական walkthrough): 35_image_compression_solution.ipynb (download) · view on GitHub · 📺 [35] Clustering գործնական. նկարի գույների սեղմում K-means-ով | Մեքենայական ուսուցում

Project — Land cover of Lake Sevan from space 🧀🧀🧀

Same idea as above, different stakes. A satellite image is also a grid of pixels, but each one carries six numbers instead of three — blue, green, red, near-infrared and two short-wave infrared bands — and each covers 20 m of real ground. Cluster those pixels and the groups are not colors to discard: they are water, fields, bare rock, a town. So this time you have to name what came out, and at the end score yourself against a real land-cover map.

Setup. Everything is pre-cropped into data/sevan_s2_crop.npz: a 20 km square on the south shore of Lake Sevan near Martuni, cloud-free, 2 September 2024, plus ESA’s WorldCover labels for the same pixels. It loads with plain np.load — no geospatial libraries needed. One reproducible notebook, seed 509, ending with a 3–5 sentence conclusion.

The stored values are digital numbers; convert to surface reflectance with bands * reflectance_scale + reflectance_offset. Some values over water come out slightly negative, which is expected — the atmospheric correction is an estimate.

Tasks.

  1. Show the scene in true color (B04, B03, B02) and in false color with near-infrared in the red channel. Say in one line what the second one shows that the first cannot.
  2. Reshape to (n_pixels, 6), then choose k. Plot both the elbow and the silhouette — they will not agree. Pick a value and defend it in two sentences.
  3. Cluster, map the labels back to (H, W), and name every cluster from its mean spectrum. Water, vegetation and bare ground have distinct shapes; work out which is which from the numbers, not by guessing. Deliver the map with a named legend.
  4. Build a second feature set from NDVI and NDWI and cluster again. Show both maps. Which would you ship, and how could you tell without labels?
  5. Now load the WorldCover labels. Compute plain accuracy first, explain in one line why the number is meaningless, then report ARI and AMI.
  6. Print the contingency table (cluster × true class). Name one pair of real classes your clustering merged and explain why the spectra cannot separate them.
  7. Recompute ARI on land pixels only, with the water cluster dropped. Explain the drop in two sentences.

Bonus: agglomerative clustering with a dendrogram on a subsample; MiniBatchKMeans or HDBSCAN; add a texture feature (local standard deviation) and see whether built-up finally separates from bare ground; or edit CANDIDATES in py_src/fetch_sevan_scene.py and fetch your own Armenian scene.

Լուծումը (ամբողջական walkthrough): 34_land_cover_solution.ipynb (download) · view on GitHub · 📺 [34] Սևանի արբանյակային նկարը - Clustering գործնական | Մեքենայական ուսուցում

Project — Հայերեն բառերի իմաստային ծառը 🧀🧀🧀

The three projects above all ask the same question: which representation wins? Here the representation is fixed — one Armenian embedding model — and the question is what else decides your clusters. The answer turns out to be the metric, the linkage, and something nobody warns you about.

The clusters are also finally readable. You cannot look at a cluster of pixels and say whether it is right; you can look at մայր, հայր, քույր, եղբայր and know instantly. So the dendrogram is the deliverable, not a score.

Setup. data/armenian_words.npz holds 108 Armenian words and short phrases across 12 semantic families, already embedded with Metric-AI/armenian-text-embeddings-2-large — plus the phrase forms, four sets of polysemous sentences, and every word’s tokenization. It loads with np.load(..., allow_pickle=True); no model, no downloads. The word list itself is py_src/armenian_words.py. One reproducible notebook, seed 509.

Note for Windows: the console is cp1252 and cannot print Armenian. Start with sys.stdout.reconfigure(encoding="utf-8").

Tasks.

  1. Build the tree with Ward linkage and draw the dendrogram with Armenian labels. Which families came out clean? Find at least one word the model placed more sensibly than the ground truth does.
  2. Predict first. Before computing anything: which two words do you expect to be closest? Then find the ten closest pairs. Say why the second-closest pair should alarm you.
  3. Form a hypothesis and break it. The obvious explanation for that result is that the model reads spelling. Find the word in the dataset that refutes it — same first letter, yet 1.6× further away — and say what makes it different.
  4. Open the tokenizer. The .npz carries meta["tokens"]. Print them for every probe word and state the rule that actually predicts which pairs collide. Verify it against all six probe groups, including the three designed not to collide. Watch out for one token that appears everywhere and means nothing.
  5. Quantify it. Score ARI and AMI against the 12 families, then drop the colliding words and re-score. What fraction of the vocabulary causes what fraction of the damage?
  6. Does context repair it? Re-embed using the phrase forms (հավի ձու instead of ձու) and compare both the pair distances and the overall ARI. Is this a fix or a mitigation? Answer with the number.
  7. Euclidean or cosine? For L2-normalised vectors prove \(\|a-b\|^2 = 2 - 2\cos(a,b)\) on your own data. Then work out from that identity which linkages can possibly change when you switch metric, and confirm it across several k. Explain why single and complete cannot change but average can.
  8. Ward and cosine. Ask scipy for Ward with cosine two different ways: passing the vectors, and passing a precomputed distance matrix. It refuses one and not the other. Which answer would you have shipped?
  9. Compare linkages on the same data and metric. One of them collapses almost completely — name it, and explain the mechanism from the lecture.
  10. Polysemy. Արա is three different words (թագավոր / դիմելաձև / հրամայական), and սեր, մարտ, բաց are two each. Match each sense’s sentence to its own anchor. Three fail — find the pattern in which three, and report how narrowly each one lost.

Bonus: measure the space’s anisotropy (‖mean vector‖, and the range of pairwise cosines), then try centering on four different bases and see whether it repairs task 10 — be careful which sample you estimate the mean from, and say why the smallest one flatters itself; try armenian-text-embeddings-2-base and see whether the smaller model collides more; add your own Armenian words and try to break the tree further.

Լուծումը (ամբողջական walkthrough): xx_semantic_tree_solution.ipynb (download) · view on GitHub

Flag Counter