This repository, spectral-clustering-shifted-power-sparse, hosts all the materials and code for the mandatory spectral clustering homework in the course Computational Linear Algebra for Large Scale Problems (A.A. 2024–2025). It features a from-scratch Shifted Inverse Power Method with Deflation for eigenvalue computations using SciPy sparse matrices.
- Technical Report (
HW_SpectralClustering.pdf
): Explains the methods, results, and comparisons with other clustering approaches. - Instructions (
instruction.txt
): Shows how to run the code and reproduce the results. - Source Code: Contains Python scripts for each step of the homework.
-
k-NN Similarity Graph & Adjacency Matrix
knn_similarity_graph.py
builds a k-nearest-neighbor graph from the data and forms the weighted adjacency matrix. -
Degree Matrix & Laplacian
laplacian_matrix.py
constructs the degree matrix and Laplacian for spectral clustering. -
Connectivity
connected_components.py
checks how many connected components exist. -
Finding Clusters
iterative_power_methods.py
computes small eigenvalues of the Laplacian using a shifted inverse power method plus deflation. -
Eigenvectors & Embedding
eigen_pairs.py
extracts the corresponding eigenvectors to embed the data. -
k-Means on Embedding
Groups the embedded points into clusters. -
Visualization
Plots clusters in distinct colors. -
Compare Methods
Evaluates spectral clustering against other clustering techniques.
- NumPy / SciPy for numerical operations and sparse matrix support.
- Custom Iterative Power Methods for eigenvalue approximation.
- Install Requirements: Check
requirements.txt
. - Run Scripts: See
instruction.txt
for steps. But just install the requirements and run the main notebook and that's it. - Experiment: Adjust parameters like
k
in k-NN or the number of eigenvalues or use different datasets.
Use or adapt this code for academic or personal research. For questions or suggestions, open an issue or reach out directly.