Clustering of High-Dimensional Data with Intrinsic Low Rank

Introduction

This project addresses the challenge of clustering high-dimensional data points in a 1000-dimensional space, partitioning 300 data points into 7 clusters. The objective is to overcome the curse of dimensionality through advanced dimensionality reduction and clustering techniques.

Dataset Specifications:

• Data points: 300 samples
• Dimensionality: 1000-dimensional feature space
• Target clusters: 7 distinct groups

Task Requirements:

1. Apply clustering algorithms to the 300 data points in data_1000d.npy
2. Generate prediction results saved as pred_labels.npy (300 integers, range 0-6)
3. Submit to Canvas competition platform for evaluation

Methodological Flexibility:

• Multiple clustering approaches supported: Gaussian Mixture Models (GMM), K-means, Hierarchical Clustering, Spectral Clustering, DBSCAN
• Custom implementation required without reliance on existing clustering libraries
• Comparative analysis of different methods encouraged

---

Provided Files

Filename	Description
data_1000d.npy	Clustering dataset (300×1000 matrix)
validation_indices.npy	Validation set indices (60 data point indices)
validation_labels.npy	Ground truth labels for validation (60 labels)
evaluate_validation.py	Validation set evaluation script
data_2D_visualization.png	2D projection reference visualization

Dataset Partitioning:

• Validation set: 20% (60/300) available for local development and debugging
• Test set: 80% (240/300) reserved for final Canvas platform evaluation

Usage

Methodological Approach

This research implements a comprehensive two-stage framework for high-dimensional clustering:

Stage 1: Dimensionality Reduction Given the intrinsic low-rank structure of the high-dimensional data, we employ three distinct dimensionality reduction techniques:

1. Principal Component Analysis (PCA): Linear orthogonal transformation preserving maximum variance through eigenvalue decomposition of the covariance matrix. Projects data onto the top-$k$ eigenvectors corresponding to the largest eigenvalues, providing optimal $\ell_2$ reconstruction error minimization.

2. Truncated Singular Value Decomposition (SVD): Matrix factorization approach that computes the best rank-$k$ approximation in the Frobenius norm sense. Extracts the most significant singular vectors to capture the essential data structure.

3. AutoEncoder Architecture: Neural network-based nonlinear dimensionality reduction utilizing an encoder-decoder framework. The encoder $f_\theta: \mathbb{R}^{1000} \rightarrow \mathbb{R}^k$ learns compact latent representations, while the decoder $g_\phi: \mathbb{R}^k \rightarrow \mathbb{R}^{1000}$ reconstructs the original input through minimization of reconstruction loss $\mathcal{L}(\theta, \phi)$.

Stage 2: Clustering Algorithms Four primary clustering methodologies are implemented and evaluated:

1. K-means Clustering: Centroid-based partitioning algorithm that minimizes within-cluster sum of squared distances through iterative alternation between assignment and update steps. Formally solves $\min_{\mathbf{S}, \mathbf{C}} \sum_{k=1}^K \sum_{\mathbf{x}_i \in C_k} |\mathbf{x}_i - \boldsymbol{\mu}_k|_2^2$.

2. Gaussian Mixture Model (GMM): Probabilistic clustering approach assuming data generation from a mixture of Gaussian distributions. Implements Expectation-Maximization algorithm for parameter estimation $\Theta = {\pi_k, \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k}$ through likelihood maximization.

3. DBSCAN: Density-based spatial clustering identifying arbitrarily shaped clusters through density connectivity principles. Utilizes parameters $\epsilon$ (neighborhood radius) and MinPts (minimum points) to distinguish core points, border points, and noise.

4. Spectral Clustering: Graph-based clustering methodology leveraging eigendecomposition of the normalized graph Laplacian $\mathbf{L}{\text{sym}} = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{S} \mathbf{D}^{-1/2}$. Constructs similarity matrices using RBF kernels: $s{ij} = \exp(-|\mathbf{x}_i - \mathbf{x}_j|^2/2\sigma^2)$.

Key Findings:

• The dataset exhibits intrinsic two-dimensional structure with 77.46% variance explained by the first principal component
• AutoEncoder 2D representations achieve optimal performance for centroid-based methods (ARI: 0.6510, NMI: 0.7654)
• Spectral clustering with RBF kernels demonstrates superior performance on original high-dimensional data
• Dimensionality reduction significantly mitigates the curse of dimensionality while preserving discriminative cluster structure

Evaluations

Run all the experiments:

bash eval.sh

The evaluation results demonstrate the effectiveness of our proposed methodology:

============================================================
                 Validation Set Evaluation Results
============================================================
Validation data points: 60 / 300 (20%)

  ARI (Adjusted Rand Index):        0.6832
  NMI (Normalized Mutual Info):     0.7784

============================================================
Note: This represents validation set performance only.
Final evaluation is based on the test set (240 points).
============================================================

Submission Requirements

A compressed archive (.zip) containing:

• pred_labels.npy - Predicted cluster labels for all 300 data points
• your_code.py - Complete clustering algorithm implementation
• Algorithm description document (PDF) with methodological details

Evaluation Metrics:

• Adjusted Rand Index (ARI): Measures similarity between predicted and true cluster assignments, adjusted for chance
• Normalized Mutual Information (NMI): Quantifies mutual information between clusterings normalized by entropy
• Silhouette Coefficient: Assesses cluster cohesion and separation (where applicable)