The University of Windsor has moved to an “essential service only” model. Learn More.

MSc Thesis Proposal Announcement by Nachiket Bhide:"Efficient Clustering via Spectral Dimensionality Reduction and Optimal One-dimensional Thresholding"

Wednesday, June 10, 2020 - 10:00 to 11:30



The School of Computer Science is pleased to present…


MSc Thesis Proposal by:  Nachiket Bhide

 Date: Wednesday June 2020
Time:  10:00 AM to 11:30 AM


Graph-based clustering is one of the techniques used for clustering high dimensional data. High dimensional data can be clustered efficiently by
representing it as a graph and then partitioning the graph based on its spectral decomposition. Traditionally, the spectral clustering approach is based on performing dimensionality reduction of high dimensional graph data and then using k-Means for clustering in lower dimensions. However, this approach based on k-Means does not guarantee optimality. Moreover, the result of k-means is highly dependent on initial cluster centers and hence not repeatable. An optimal clustering approach based on spectral dimensionality reduction is proposed. The Fiedler vector is obtained from eigen decomposition of the graph Laplacian matrix. The one dimensional values of the Fiedler vector are then clustered optimally based on a dynamic programming in polynomial time. Clusters in one dimensional data are obtained by minimizing the sum of within-class variance or maximizing the sum of between-class variance. This one dimensional clustering of the Fiedler vector corresponds to the partitioning of graph data in higher dimensions. The advantage in optimality of clustering based on this approach is demonstrated over standard k-Means based spectral clustering algorithm.

Thesis Committee:

Internal Reader: Dr. Alioune Ngom
External Reader: Dr. Dilian Yang
Advisor: Dr. Luis Rueda

MSc Thesis Proposal Announcement  Vector Institute AI approved Seminar logo

5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716