Complex devices are connected daily and eagerly generate vast streams of multidimensional state measurements. These devices often operate in distinct modes based on external conditions (day/night, occupied/vacant, etc.), and to prevent complete or partial system outage, we would like to recognize as early as possible when these devices begin to operate outside the normal modes. Unfortunately, it is often impractical or impossible to predict failures using rules or supervised machine learning, because failure modes are too complex, devices are too new to adequately characterize in a specific environment, or environmental change puts the device into an unpredictable condition. We propose an unsupervised anomaly detection method that creates a negative sample from the positive, observed sample, and trains a classifier to distinguish between positive and negative samples. Using the Contraction Principle, we explain why such a classifier ought to establish suitable decision boundaries between normal and anomalous regions, and show how Integrated Gradients can attribute the anomaly to specific variables within the anomalous state vector. We have demonstrated that negative sampling with random forest or neural network classifiers yield significantly higher AUC scores than Isolation Forest, One Class SVM, and Deep SVDD, against (a) a synthetic dataset with dimensionality ranging between 2 and 128, with 1, 2, and 3 modes, and with and without noise dimensions; (b) four standard benchmark datasets; and (c) a multidimensional, multimodal dataset from real climate control devices. Finally, we describe how negative sampling with neural network classifiers have been successfully deployed at large scale to predict failures in real time in over 15,000 climate-control and power meter devices in 145 Google office buildings.