  Clustering is a fundamental problem in machine learning where distance-based
approaches have dominated the field for many decades. This set of problems is
often tackled by partitioning the data into K clusters where the number of
clusters is chosen apriori. While significant progress has been made on these
lines over the years, it is well established that as the number of clusters or
dimensions increase, current approaches dwell in local minima resulting in
suboptimal solutions. In this work, we propose a new set of distance threshold
methods called Theta-based Algorithms (ThetA). Via experimental comparisons and
complexity analyses we show that our proposed approach outperforms existing
approaches in: a) clustering accuracy and b) time complexity. Additionally, we
show that for a large class of problems, learning the optimal threshold is
straightforward in comparison to learning K. Moreover, we show how ThetA can
infer the sparsity of datasets in higher dimensions.
