Abstract
Modern astronomical surveys generate billions of light-curves, necessitating automated anomaly detection to discover rare celestial phenomena. A primary challenge in analyzing these datasets is the "phasing problem," where periodic signals are unsynchronized, making traditional $O(n^2)$ alignment computationally prohibitive for large-scale catalogs. We present PCAD (Periodic Curve Anomaly Detection), which utilizes a novel Phased K-means (Pk-means) algorithm to achieve $O(n)$ scalability. By aligning time series to a small set of centroids using Fast Fourier Transforms, PCAD efficiently identifies both global and local anomalies in massive datasets. Our evaluation on the OGLE dataset demonstrates that PCAD identifies rare celestial objects with high precision and significant speed improvements over exhaustive methods.
Introduction: The Phasing Problem
In astronomy, light-curves—measurements of a star's brightness over time—are the primary tool for discovery. With modern surveys producing data for billions of stars, manual inspection is impossible. Automated anomaly detection is the only viable path to finding new, rare classes of celestial objects.
However, periodic time series present a unique challenge: the phasing problem. Because stars are observed at arbitrary starting points in their cycles, two identical stars may appear completely different to standard machine learning algorithms if their peaks and valleys are not aligned.
As shown in Figure 1, different classes like Cepheids and Eclipsing Binaries have distinct shapes, but their phase is random in raw observations. While pairwise alignment could solve this, the $O(n^2)$ complexity is a death sentence for "Big Data" catalogs.
Methodology: Phased K-means (Pk-means)
PCAD centers on a modified clustering algorithm called Phased K-means (Pk-means). Unlike standard k-means, which calculates the distance between a point and a static centroid, Pk-means searches for the optimal phase shift $\tau$ that maximizes the correlation between the time series and the centroid.
Figure 2 illustrates this mechanism: the algorithm utilizes Fast Fourier Transforms (FFT) to efficiently perform cross-correlation (middle plot), identifying the shift required to align the input curve (top) with the reference (bottom). This shifts the computational complexity from $O(n^2)$ to $O(n)$, making it viable for billions of objects. Furthermore, the authors provide a mathematical proof that Pk-means maintains the convergence properties of standard k-means despite this added alignment step.
Scalability via Sampling and Anomaly Scoring
To handle massive datasets, PCAD runs Pk-means on a small, representative sample to generate a set of "normal" centroids. Research shows that centroids from a small sample are remarkably effective at representing the general population. Once centroids are established, every object in the full dataset is assigned an anomaly score:
- Global Anomalies: Objects that do not resemble any of the centroids.
- Local Anomalies: Objects that are outliers even within their own assigned cluster.
Experimental Results
PCAD was evaluated on four distinct datasets, including real light-curve data from the Optical Gravitational Lensing Experiment (OGLE) and various synthetic benchmarks.
Key findings include:
- Performance: PCAD consistently outperformed naive solutions and state-of-the-art rotation-invariant methods like RI-DISCORD.
- High-Speed Approximation: PCAD serves as an excellent, high-speed approximation of PN-MEANS, the exhaustive $O(n^2)$ "gold standard" algorithm used in astrophysics.
- Real-World Validation: Astrophysicists verified that the top anomalies flagged by PCAD in the OGLE data were indeed "true" anomalies, including misclassified stars and objects with rare eccentric orbits or atmospheric variations.
Conclusion and Future Work
PCAD provides a scalable framework for discovering rare periodic phenomena in massive datasets. While highly effective, future work will focus on incorporating observational error to handle noise and moving toward density-based ranking (such as Local Outlier Factor) to better identify anomalies in clusters with varying densities. The ultimate goal is the deployment of PCAD on the Pan-STARRS survey, which contains billions of light-curves, providing the ultimate test of the algorithm's scalability.
Summary updated