A New View of Classification in Astronomy with the Archetype Technique:
  An Astronomical Case of the NP-complete Set Cover Problem
  We introduce a new generic Archetype technique for source classification and
identification, based on the NP-complete set cover problem (SCP) in computer
science and operations research (OR). We have developed a new heuristic SCP
solver, by combining the greedy algorithm and the Lagrangian Relaxation (LR)
approximation method. We test the performance of our code on the test cases
from Beasley's OR Library and show that our SCP solver can efficiently yield
solutions that are on average 99% optimal in terms of the cost. We discuss how
to adopt SCP for classification purposes and put forward a new Archetype
technique. We use an optical spectroscopic dataset of extragalactic sources
from the Sloan Digital Sky Survey (SDSS) as an example to illustrate the steps
of the technique. We show how the technique naturally selects a basis set of
physically-motivated archetypal systems to represent all the extragalactic
sources in the sample. We discuss several key aspects in the technique and in
any general classification scheme, including distance metric, dimensionality,
and measurement uncertainties. We briefly discuss the relationships between the
Archetype technique and other machine-learning techniques, such as the
$k$-means clustering method. Finally, our code is publicly available and the
technique is generic and easy to use and expand. We expect that it can help
maximize the potential for astrophysical sciences of the low-S/N spectroscopic
data from future dark-energy surveys, and can find applications in many fields
of astronomy, including the formation and evolution of a variety of
astrophysical systems, such as galaxies, stars and planets.
