Thesis (PDF)

October 22, 2015
DRAFT

An Experimental Study into Spectral and
Geometric Approaches to Data Clustering
Prashant Sridhar
October 2015

School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15289
Thesis Committee:
Dr. Gary Miller, Chair
Dr. Alex Smola
Submitted in partial fulfillment of the requirements
for the degree of Masters in Computer Science.

c 2015 Prashant Sridhar
Copyright

October 22, 2015
DRAFT

Keywords: Geometry, Nonparametric, Clustering

October 22, 2015
DRAFT

For my parents

October 22, 2015
DRAFT

iv

October 22, 2015
DRAFT

Abstract

October 22, 2015
DRAFT

vi

October 22, 2015
DRAFT

Acknowledgments
My advisor is cool.

October 22, 2015
DRAFT

viii

October 22, 2015
DRAFT

Contents
1

Introduction

1

2

Roadmap

5

3

Traditional Non-parametric clustering

7

4

Density based distance metrics and clustering
4.1 Approximation of density based distance metrics
4.2 Gabriel graphs and approximate Gabriel graphs .
4.3 Weakly Gabriel graph and fast linear spanner . .
4.4 Results and Discussion . . . . . . . . . . . . . .

5

Geometric non-parametric clustering

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

9
. 9
. 11
. 17
. 21
25

Bibliography

27

ix