Fitting a graph to vector data
SI Daitch, JA Kelner, DA Spielman - Proceedings of the 26th annual …, 2009 - dl.acm.org
SI Daitch, JA Kelner, DA Spielman
Proceedings of the 26th annual international conference on machine learning, 2009•dl.acm.orgWe introduce a measure of how well a combinatorial graph fits a collection of vectors. The
optimal graphs under this measure may be computed by solving convex quadratic programs
and have many interesting properties. For vectors in d dimensional space, the graphs
always have average degree at most 2 (d+ 1), and for vectors in 2 dimensions they are
always planar. We compute these graphs for many standard data sets and show that they
can be used to obtain good solutions to classification, regression and clustering problems.
optimal graphs under this measure may be computed by solving convex quadratic programs
and have many interesting properties. For vectors in d dimensional space, the graphs
always have average degree at most 2 (d+ 1), and for vectors in 2 dimensions they are
always planar. We compute these graphs for many standard data sets and show that they
can be used to obtain good solutions to classification, regression and clustering problems.
We introduce a measure of how well a combinatorial graph fits a collection of vectors. The optimal graphs under this measure may be computed by solving convex quadratic programs and have many interesting properties. For vectors in d dimensional space, the graphs always have average degree at most 2(d + 1), and for vectors in 2 dimensions they are always planar. We compute these graphs for many standard data sets and show that they can be used to obtain good solutions to classification, regression and clustering problems.