Representative subsets for big data learning using k-NN graphs
- 1 October 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 37-42
Abstract
In this paper we propose a deterministic method to obtain subsets from big data which are a good representative of the inherent structure in the data. We first convert the large scale dataset into a sparse undirected k-NN graph using a distributed network generation framework that we propose in this paper. After obtaining the k-NN graph we exploit the fast and unique representative subset (FURS) selection method [1], [2] to deterministically obtain a subset for this big data network. The FURS selection technique selects nodes from different dense regions in the graph retaining the natural community structure. We then locate the points in the original big data corresponding to the selected nodes and compare the obtained subset with subsets acquired from state-of-the-art subset selection techniques. We evaluate the quality of the selected subset on several synthetic and real-life datasets for different learning tasks including big data classification and big data clustering.Keywords
This publication has 14 references indexed in Scilit:
- Optimal reduced sets for sparse kernel spectral clustering2014
- Self-tuned kernel spectral clustering for large scale networks2013
- Relative Validity Criteria for Community Mining Algorithms2012
- Coupled Simulated AnnealingIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2009
- Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Kernel PCAIEEE Transactions on Pattern Analysis and Machine Intelligence, 2008
- Interruptible iteratorsACM SIGPLAN Notices, 2006
- On Nearest-Neighbor GraphsDiscrete & Computational Geometry, 1997
- Separators for sphere-packings and nearest neighbor graphsJournal of the ACM, 1997
- An alternative method of cross-validation for the smoothing of density estimatesBiometrika, 1984
- A Simplex Method for Function MinimizationThe Computer Journal, 1965