Custom Similarity Measures for MNIST and ADULT

Course project for IFT 3700 – Introduction to Data Science (Université de Montréal), completed in a team of two.

• Full report (in French): report.pdf
• Assignment instructions (original in French, English translation): instructions_en.md

---

1. Summary

Context

The assignment asks us to design two original similarity measures, one for each dataset, and to check whether they improve the performance of standard clustering, dimensionality-reduction and classification algorithms compared with off-the-shelf distances.

Dataset	Data	Task	Baseline
MNIST	28×28 grayscale images of handwritten digits (10 classes)	Digit recognition / clustering	Euclidean distance
ADULT (UCI)	Census records with 6 continuous and 8 categorical features	Predict income >50K vs <=50K (2 classes)	None (Euclidean only works on continuous features)

What was built

• MNIST similarity: compares the row and column pixel-sum profiles of two digits after aligning them, so that small translations do not matter.
• ADULT similarity: replaces each categorical value by the proportion of >50K records having that value (computed on the training set only), min-max normalizes the continuous features, then applies the Manhattan distance.

Each measure is plugged into five algorithms and evaluated on both datasets:

Family	Algorithm	Implementation
Clustering	k-medoids	sklearn_extra.cluster.KMedoids
Clustering	Binary partition (hierarchical, average-distance variant)	sklearn.cluster.AgglomerativeClustering (linkage='average')
Dimensionality reduction	PCoA (MDS)	sklearn.manifold.MDS on a precomputed distance matrix
Dimensionality reduction	Isomap	sklearn.manifold.Isomap
Classification	k-nearest neighbours	sklearn.neighbors.KNeighborsClassifier

Clustering and classification are each run on the raw data and on the PCoA / Isomap embeddings. Metrics: Adjusted Rand Index, V-measure, silhouette (clustering) and accuracy (classification).

---

2. Topics covered

Similarity and distance design

• Building a domain-specific dissimilarity instead of relying on Euclidean distance on raw features.
• Making a measure robust to nuisance variation (small image translations) via projection and alignment.
• Handling mixed-type tabular data: target-based (similarity) encoding of categorical variables, following Cerda et al. (2018), and train-only min-max normalization to avoid leakage.

Machine-learning algorithms with custom metrics

• Hierarchical (agglomerative) clustering and k-medoids, which, unlike k-means, work with any dissimilarity.
• Classical embedding methods that start from a distance matrix: PCoA/MDS and Isomap (geodesic distances on a neighbourhood graph).
• k-nearest-neighbours classification with a user-defined metric.

Evaluation

• External clustering metrics (Adjusted Rand Index, V-measure), an internal one (silhouette) and classification accuracy.
• Comparing a proposed measure against a baseline and against its own ablation (with vs. without the alignment step).
• Reading 2-D embeddings critically (cluster overlap, outliers, uniform "blobs").

Engineering and analysis

• Modular Python design: abstract base classes for transformers, clusterers and classifiers (model/model.py), so any similarity can be swapped in.
• Working with scikit-learn callable metrics and precomputed distance matrices; subsampling to keep O(n²) pairwise computations tractable.
• Computational complexity analysis of both measures, and an honest discussion of strengths and weaknesses.

---

3. Project structure

.
├── run.py                  # Runs every dataset × transformation × algorithm and saves metrics (JSON)
├── run_analysis.py         # Produces the 2-D Isomap / PCoA scatter plots (PNG)
├── lib.py                  # Logging helpers, progress bar, MNIST ASCII printer
├── data/
│   ├── data.py             # `Data` container (train/test inputs and labels)
│   ├── loader.py           # Reads the raw MNIST (idx) and ADULT (csv) files
│   ├── processor.py        # Subsampling + ADULT encoding/normalization
├── similarities/
│   ├── for_mnist.py        # MNIST similarity (profile alignment)
│   └── for_adult.py        # ADULT similarity (Manhattan on encoded data)
├── model/
│   ├── model.py            # Abstract base classes
│   ├── binary_part.py      # Hierarchical clustering
│   ├── kmedoide.py         # k-medoids
│   ├── knn.py              # k-nearest neighbours
│   ├── isomap.py           # Isomap transformer
│   └── pcoa.py             # PCoA/MDS transformer
├── evaluation/
│   ├── cluster_eval.py     # ARI, V-measure, silhouette
│   └── classif_eval.py     # Accuracy
├── out/                    # Generated results (create it, see §4)

---

4. How to run

4.1 Requirements

Python 3.9+ is recommended.

python -m venv .venv
source .venv/bin/activate          # Windows: .venv\Scripts\activate
pip install -r requirements.txt

scikit-learn is pinned below 1.4 because AgglomerativeClustering(affinity=...) was removed in that release. On Python 3.12+, setuptools must be installed (it is listed in requirements.txt) for scikit-learn-extra to import.

4.2 Run

mkdir -p out                # results and plots are written here

python run.py               # all algorithms on both datasets -> out/eval_<timestamp>.json
python run_analysis.py      # 2-D scatter plots           -> out/plt_<dataset>_<transform>_<timestamp>.png

run.py prints each metric as it goes and saves everything in a single JSON file, keyed as <DATASET>_<algorithm>_<transformation> (e.g. MNIST_K-Medoids_Isomap). Because the similarities are Python callables evaluated on every pair of points, a full run can take a long time; reduce n_train / n_test in run.py for a quick test.

4.3 Configuration and variants

• Sample sizes (run.py): MNIST 1,500 train / 250 test (≈2.5 % of the data); ADULT 3,256 train / 1,628 test (≈10 %). run_analysis.py plots 500 MNIST and 3,256 ADULT test points.

• Hyperparameters (run.py): 10 clusters for MNIST and 2 for ADULT; KNN with k=4 (MNIST) and k=7 (ADULT); Isomap with 4 (MNIST) and 9 (ADULT) neighbours. After PCoA/Isomap, downstream algorithms use the Euclidean distance in the embedded space.

• Logging: change LOG_LEVEL in lib.py.

• Euclidean baseline for MNIST: in similarities/for_mnist.py, the line mnist_similarity = 'euclidean' is currently overridden by the function defined below it. To run the baseline, move that line after the function definition (or comment the function out):

  def mnist_similarity(x_1, x_2):
      ...
  
  mnist_similarity = 'euclidean'   # overrides the custom measure
  

• MNIST measure without alignment (the "without translation step" column below): comment out the two np.roll(...) calls in mnist_similarity so the raw profiles are compared directly.

---

5. Main results

The report is written in French and plot titles are too (Transformation X sur Y = “X transformation on Y”). Only the key points are reproduced here.

5.1 The two similarity measures

MNIST: aligned row/column profiles

1. Reshape the image to 28×28 and sum the pixel values along columns and along rows. This gives two 28-value profiles, the top view and the side view of the digit. The profiles tell us where the ink is concentrated (a 6 is heavier in its lower half) and how thin the digit is (a 1 is much narrower than a 0).

   

2. To be robust to translation, the profiles are aligned. Each profile is divided by 1.3 × its maximum and rounded to 0/1, which keeps only the strongly inked region and gives a clean “first edge” of the digit. (Aligning on the maximum fails for slanted digits, whose maxima fall on opposite sides.)

   

3. The first index equal to 1 in each profile is found, and the original profiles of the first image are shifted so that these edges coincide with those of the second image (avant = before, après = after).

   

4. The dissimilarity is the sum of the absolute differences between the aligned top-view profiles plus the same for the side-view profiles (e.g. 43,248 for the “3” and the “1” above).

Complexity: both this measure and the Euclidean distance are O(d) per pair, but this one has a much larger constant (≈3,300 elementary operations vs. 784 for a 28×28 image), so it is slower.

ADULT: similarity-encoded features + Manhattan distance

1. For each of the 8 categorical features, replace every value by the proportion of training records with that value whose label is >50K (target/similarity encoding, inspired by Cerda et al., 2018).
2. Min-max normalize the 6 continuous features using the training minimum and maximum (test values can therefore fall slightly outside [0, 1]).
3. Compare points with the Manhattan distance on the resulting 14 numeric features.

No test label is used: all encoding statistics come from the training set. Complexity: O(n) per feature, O(nd) overall for the preprocessing.

5.2 MNIST: comparison with the Euclidean distance

Higher is better for all metrics. Bold = best of the three measures in that row. ARI = Adjusted Rand Index, V = V-measure, Sil = silhouette score. Clustering is evaluated on the test subset.

Algorithm	Metric	Ours, no alignment	Ours	Euclidean
Binary partition	ARI	0.0914	0.1044	0.0296
	V	0.2712	0.2724	0.2204
	Sil	0.1302	0.1551	0.0402
Binary partition + PCoA	ARI	-0.0048	0.0049	-0.0028
	V	0.0763	0.0812	0.0900
	Sil	-0.1766	-0.1003	-0.0574
Binary partition + Isomap	ARI	0.2160	0.2301	0.2185
	V	0.3759	0.4130	0.4493
	Sil	0.0994	0.1334	0.0329
K-medoids	ARI	0.1926	0.1976	0.1048
	V	0.3437	0.3725	0.2800
	Sil	0.0576	0.0343	-0.0016
K-medoids + PCoA	ARI	-0.0085	-0.0097	0.0003
	V	0.0678	0.0627	0.0767
	Sil	-0.0731	-0.0883	-0.0448
K-medoids + Isomap	ARI	0.2387	0.2119	0.3151
	V	0.4127	0.3819	0.4872
	Sil	0.0345	0.0379	0.0240
KNN	Accuracy	0.7410	0.7211	0.8486
KNN + PCoA	Accuracy	0.0797	0.1076	0.0956
KNN + Isomap	Accuracy	0.1633	0.0956	0.0598

Takeaways

• Our measure clearly beats the Euclidean distance for hierarchical clustering and k-medoids on the raw data (e.g. binary-partition silhouette 0.155 vs. 0.040; k-medoids ARI 0.198 vs. 0.105).
• Euclidean remains better for KNN (0.849 vs. 0.721), for most PCoA variants and for k-medoids + Isomap.
• The alignment step improves most results, with a few exceptions (k-medoids silhouette, k-medoids + PCoA, and k-medoids + Isomap ARI/V-measure).
• Isomap with our measure splits the points into two groups with classes overlapping inside each group; with Euclidean the points are more scattered and noisier. PCoA shows no structure with either measure, and every algorithm performs worse after PCoA than on the raw data.
• Expected weaknesses: digits without a concentrated zone look alike in the profiles, slanted digits have very different top views, thin digits are over-attracted to class “1”, and the alignment can fail.

Isomap / PCoA embeddings of MNIST test points (2-D)

	Isomap	PCoA
Our similarity
Euclidean

5.3 ADULT

There is no baseline here, since the Euclidean distance cannot handle the categorical features.

Algorithm	ARI	V-measure	Silhouette	Accuracy
Binary partition	0.0324	0.0307	0.4359
Binary partition + PCoA	-0.0011	0.0005	0.0012
Binary partition + Isomap	0.0783	0.0557	0.3226
K-medoids	0.1716	0.1741	0.4036
K-medoids + PCoA	-0.0008	0.0002	0.0000
K-medoids + Isomap	0.1736	0.1765	0.4044
KNN				0.8220
KNN + PCoA				0.7041
KNN + Isomap				0.7993

Takeaways

• KNN works well: the encoding injects information about the label into the features, so proximity under this measure is already very informative for classification.
• Clustering recovers the true partition poorly (low ARI / V-measure) but produces compact, well-separated groups (silhouette ≈ 0.40–0.44). The measure is tailored to classification rather than to general similarity.
• Isomap reveals two distinct clouds, but outliers sit inside the opposite cloud rather than around it. PCoA yields a uniform blob with both classes mixed.
• Weaknesses: every feature has the same weight and useless features are not discounted, which may explain the PCoA result and the misplaced outliers. Strengths: the idea is versatile and can be reused on other datasets or with other distances.

Isomap	PCoA

5.4 Limitations and caveats

These are worth keeping in mind when reading the numbers above:

• Subsampled data and a single run: results come from the subsets listed in §4.4, without repetitions or confidence intervals. Differences of a few hundredths should not be over-interpreted.
• PCoA implementation: it is done with scikit-learn's MDS(metric=False, dissimilarity='precomputed'), i.e. non-metric MDS, rather than classical (metric) PCoA via eigendecomposition. This may contribute to the weak PCoA results.
• KNN on embeddings: the train and test sets are embedded separately (fit_transform is called on each), so they do not share the same coordinate system. The very low MNIST accuracies for KNN + PCoA / Isomap (≈6–16 %, close to chance for 10 classes) should be read with this in mind.
• ADULT class imbalance: roughly three quarters of ADULT records are <=50K, so a trivial majority-class predictor already scores about 0.76. The KNN accuracy of 0.822 should be compared with that figure.
• Supervised encoding: the ADULT measure is label-aware (computed from training labels), which helps classification but makes it less of a neutral “similarity”, as discussed in the report.

---

References

1. Olah, C. (2014). Visualizing MNIST: An Exploration of Dimensionality Reduction. colah's blog. http://colah.github.io/posts/2014-10-Visualizing-MNIST/
2. Cerda, P., Varoquaux, G. & Kégl, B. (2018). Similarity encoding for learning with dirty categorical variables. Machine Learning 107, 1477–1494. https://doi.org/10.1007/s10994-018-5724-2