ON MACHINE-LEARNED CLASSIFICATION OF VARIABLE STARS WITH SPARSE AND NOISY TIME-SERIES DATA

2.1.1. A Fast Period Search Including Measurement Uncertainty

We model the photometric magnitudes of variable stars versus time t as a superposition of sines and cosines, starting from the most basic form

$$\begin{equation} y_i(t|f_i) = a_i \sin (2\pi f_i t) + b_i \cos (2\pi f_i t) + b_{i,\circ }, \end{equation} \tag{ 1 }$$

where a and b are normalization constants for the sinusoids of frequency f_i, and b_i,○ is the magnitude offset. For each variable star, we record at each epoch, t_k, a photometric magnitude, d_k, and its uncertainty, σ_k. To search for periodic variations in these data, we fit Equation (1) by minimizing the sum of squares

$$\begin{equation} \chi ^2 = \sum _k [d_k-y_i(t_k)]^2/\sigma _k^2, \end{equation} \tag{ 2 }$$

where σ_k is the measurement uncertainty in data point d_k. As discussed in Zechmeister & Kürster (2009), this least-squares fitting of sinusoids with a floating mean and over a range of test frequencies is closely similar to an evaluation of the well-known Lomb–Scargle (Lomb 1976; Barning 1963; Scargle 1982) periodogram. Allowing the mean to float leads to more robust period estimates in the cases where the periodic phase is not uniformly sampled; in these cases, the model light curve has a non-zero mean. (This is particularly important for searching for periods on timescales similar to the data span T_tot.) If we define

$$\begin{equation} \chi ^2_{\circ } = \sum _k [d_k-\mu ]^2/\sigma _k^2 \end{equation} \tag{ 3 }$$

with the weighted mean μ = ∑_k[d_k/σ²_k]/∑_k1/σ²_k, then our generalized Lomb–Scargle periodogram P_f is

$$\begin{equation} P_f(f) = {(N-1) \over 2} {\chi ^2_{\circ } - \chi ^2_m(f) \over \chi ^2_{\circ }}, \end{equation} \tag{ 4 }$$

where χ²_m(f) is χ² minimized with respect to a, b, and b_○. For the NULL hypothesis of no periodic variation and a white Gaussian noise spectrum, we expect P_f to be F-distributed with two numerator and N − 1 denominator degrees of freedom. A similar periodogram statistic and NULL distribution is derived in Gregory (2005) by marginalizing over an unknown scale error in the estimation of the uncertainties. In the limit of many data, the NULL distribution takes the well-known exponential form (e.g., Zechmeister & Kürster 2009). For all σ_i = 1, Equation (4) becomes the standard Lomb–Scargle periodogram. In addition to the benefits of allowing a floating mean, the generalized Lomb–Scargle periodogram (4) has two principal advantages over the standard formula: (1) uncertainties on the measurements are included and (2) scale errors in the determination of these uncertainties have no influence on the periodogram because P(f) is a ratio of two sums of squares (cf. Gregory 2005).

We undertake the search for periodicity in each source by evaluating Equation (4) on a linear test grid in frequency from a minimum value of 1/T_tot to a maximum value of 20 cycles per day, in steps of δf = 0.1/T_tot. This follows closely the prescription in Debosscher et al. (2007), with the important exception that we search for periods up to 20 cycles per day in all sources, whereas Debosscher et al. (2007) search up to a "pseudo" Nyquist frequency (f_N = 0.5〈1/ΔT〉, where ΔT is the difference in time between observations and 〈 · 〉 is an average) for most sources but allow the maximum frequency value to increase for certain source classes. To avoid favoring spurious high-frequency peaks in the periodogram, we subtract a mild penalty of log f/f_N above f_N from P_f(f) above f = f_N. Significance of the highest peak is evaluated from P_f(f). We apply an approximate correction for the number of search trials using the prescription of Horne & Baliunas (1986), although we note that numerical simulations suggest that these significance estimates underestimate the number of true trials and are uniformly high by 1σ–2σ.

Standard "fast" implementations of the Lomb–Scargle periodogram (e.g., Press et al. 2001), which scale with the number of frequency bins N_f as N_flog N_f, are not particularly fast for our purposes. This is because we wish to sample relatively few data (N ∼ 100) on a very dense, logarithmic frequency grid N_f ∼ 10⁶. It is more fruitful to pursue algorithms which scale more strongly with N than N_f. We find that standard implementations, which scale as N · N_f, are sped up by a factor of ∼10, substantially outperforming N_flog(N_f) implementations, by simply taking care to efficiently calculate the sines and cosines that are necessary to tabulate Equation (4). Instead of calculating all the sines and cosines at a given time point at each of the N_f frequency bins, we calculate sine and cosine only once at f = δf and then use trigonometric identities (i.e., successive rotations by an angle 2πδft_i) to determine the sines and cosines at higher frequencies.

2.1.2. Fitting Multiple Periods

Following Debosscher et al. (2007), we fit each light curve with a linear term plus a harmonic sum of sinusoids:

$$\begin{equation} y(t) = ct + \sum _{i=1}^3 \sum _{j=1}^4 y_i(t|jf_i), \end{equation} \tag{ 5 }$$

where each of the three test frequencies f_i is allowed to have four harmonics at frequencies f_i,j = jf_i. The three test frequencies f_i are found iteratively, by successfully finding and removing periodic signal producing a peak in P_f(f). Given a peak in P_f(f), we seek to whiten the data with respect to that frequency by fitting away a model containing that frequency as well as components with frequencies two, three, and four times that fundamental frequency. We then subtract this model from the data, update χ²_○, and recalculate P_f(f) to find an additional periodic component. The procedure is repeated three times, to extract three frequencies as well as the statistics pertaining to the harmonic amplitudes, phases, and significance of each component. In Figure 1 we show the result of applying this iterative fitting procedure to the light curve of an eclipsing variable star.

Zoom In Zoom Out Reset image size

In reporting the values from the fit of Equation (5), we ignore the constant offsets b_i,○. We translate the sinusoid coefficients into an amplitude and a phase

$$\begin{eqnarray} A_{i,j} &=& \sqrt{ a_{i,j}^2+b_{i,j}^2 } \end{eqnarray} \tag{ 6 }$$

$$\begin{eqnarray} {\rm PH}_{i,j} &=& \tan ^{-1}(b_{i,j},a_{i,j}). \end{eqnarray} \tag{ 7 }$$

Here, A_i,j (PH_i,j) is the amplitude (phase) of the jth harmonic of the ith frequency component. Following Debosscher et al. (2007), we correct the phases PH_i,j to relative phases with respect to the phase of the first component PH'_i,j = PH_i,j − PH₀₀. This is to preserve comparative utility in the phases for multiple sources by dropping a non-informative phase offset for each source. All phases are then remapped to the interval | − π, + π|.

A list and summary of all of the period features used in our analysis is found in Table 4 in Appendix A.

In seeking to classify variable-star light curves, it may not always be possible to characterize flux variation purely by detecting and characterizing periodicity. We find that simple summary statistics of the flux measurements (e.g., standard deviation, skewness, etc.)—determined without sorting the data in time or period phase—give a great deal of predictive power. For instance, skewness is very effective for separating eclipsing from non-eclipsing sources. We define (in Appendix A) 20 non-periodic features and explore in Section 4 their utility for source classification. A summary of all of the non-period features used in our analysis is found in Table 5 in Appendix A.

When only a small number of epochs (≲12) are sampled, we find that period detection becomes unreliable: we can only rely on crude summary statistics and contextual information to characterize these sources. In addition, some source classes yield non-period or multiply periodic light curves, whereby the non-periodic features are expected in these cases to carry useful additional information not already contained in the periodic features. As an example, we apply metrics used in the time-domain study of quasars (Butler & Bloom 2011) to aid in disentangling the light curves of some complexly varying, long-period variables (e.g., semiregular pulsating variables). These quasar metrics are derived from a simple model of time-correlated variations not captured by our other features.

Decision tree learning has been a popular method for classification and regression in statistics and machine learning for more than 20 years (Breiman et al. 1984 popularized this approach). Recently, the astronomical community has begun to use tree-based techniques, for several problems. For example, tree-based classifiers have been used by Suchkov et al. (2005) for Sloan Digital Sky Survey (SDSS) object classification, by Ball et al. (2006) and O'Keefe et al. (2009) for star–galaxy separation, by Bailey et al. (2007) to identify supernova candidates, and by several groups for supernova classification in the recent DES Supernova Photometric Classification Challenge (Kessler et al. 2010).

Tree-based learning algorithms use recursive binary partitioning to split the feature space, $\mathcal {X}$, into disjoint regions, R₁, R₂, ..., R_M. Within each region, the response is modeled as a constant. Every split is performed with respect to one feature, producing a partitioning of $\mathcal {X}$ into a set of disjoint rectangles (nodes in the tree). At each step, the algorithm selects both the feature and split point that produces the smallest impurity in the two resultant nodes. The splitting process is repeated, recursively, on all regions to build a tree with multiple levels.

In this section, we give an overview of three tree-based methods for classification: classification trees, RF, and boosting. We focus on the basic concepts and a few particular challenges in using these classifiers for variable-star classification. For further details about these methods, we refer the interested reader to Hastie et al. (2009).

3.1.1. Classification Trees

To build a classification tree, begin with a training set of (feature, class) pairs (X₁, Y₁), ..., (X_n, Y_n), where Y_i can take any value in {1, ..., C}. At node m of the tree, which represents a region R_m of the feature space $\mathcal {X}$, the probability that a source with features in R_m belongs to class c is estimated by

$$\begin{equation} \widehat{p}_{mc} = \frac{1}{N_m} \sum _{\mathbf {X}_i \in R_m} I(Y_i = c), \end{equation} \tag{ 8 }$$

which is the proportion of the N_m training set objects in node m whose science class is c, where I(Y_i = c) is the indicator function defined to be 1 if Y_i = c and 0 else. In the tree-building process, each subsequent split is chosen among all possible features and split points to minimize a measure of the resultant node impurity, such as the Gini index ($\sum _{c\ne c^{\prime }}^C\widehat{p}_{mc}\widehat{p}_{mc^{\prime }}$) or entropy ($-\sum _{c=1}^C \widehat{p}_{mc}\log _2\widehat{p}_{mc}$). The Gini index is the measure of choice for CART (Breiman et al. 1984), while entropy is used by the popular algorithm C4.5 (Quinlan 1996). This splitting process is repeated recursively until some pre-defined stopping criterion (such as minimum number of observations in a terminal node, or relative improvement in the objective function) is reached.

Once we have trained a classification tree on the examples (X₁, Y₁), ..., (X_n, Y_n), it is straightforward to ingest features from a new instance, X_new, and predict its science class. Specifically, we first identify which tree partition X_new resides in and then assign it a class based on that node's estimated probabilities from Equation (8). For example, if X_new ∈ R_m, then the classification-tree probability that the source is in class c is

$$\begin{equation} \widehat{p}_{c}(\mathbf {X}_{\rm new}) = \widehat{p}_{mc}, \end{equation} \tag{ 9 }$$

where $\widehat{p}_{mc}$ is defined in Equation (8). Using Equation (9), the predicted science class is $\widehat{p}(\mathbf {X}_{\rm new}) = \arg \,\max _c \widehat{p}_{c}(\mathbf {X}_{\rm new})$. Note that we are free to describe the classification output for each new source either as a vector of class probabilities or as its predicted science class.

There remains the question of how large of a tree should be grown. A very large tree will fit the training data well, but will not generalize well to new data. A very small tree will likely not be large enough to capture the complexity of the data-generating process. The appropriate size of a tree ultimately depends on the complexity of model necessary for the particular application at hand and hence should be determined by the data. The standard approach to this problem is to build a large tree, T, with M terminal nodes and then to prune this tree to find the subtree T* of T that minimizes a cross-validation estimate of its statistical risk (see Section 3.5).

3.1.2. Random Forest

3.1.3. Boosted Trees

An additional advantage to tree-based classifiers is that, because the trees are constructed by splitting one feature at a time, they allow us to estimate the importance of each feature in the model. A feature's importance can be deduced by, for instance, counting how often that feature is split or looking at the resultant decrease in node impurity for splits on that feature. Additionally, RF provides a measure of the predictive strength of each feature, referred to as the variable importance, which tells us roughly what the decrease in overall classification accuracy would be if a feature were replaced by a random permutation of its values. RF has a rapid procedure for estimating variable importance via its out-of-bag samples for each tree, those data that were not included in the bootstrapped sample.

Analyzing the feature importance is a critical step in building an accurate classification model. By determining which features are important for distinguishing certain classes, we gain valuable insight into the physical differences between particular science classes. Moreover, we can visualize which types of features are more predictive than others, which can inform the use of novel features or the elimination of useless features in a second-generation classifier.

A common approach for multi-class classification is to reduce the C-class problem into a set of C(C − 1)/2 pairwise comparisons. This is a viable approach because two-class problems are usually easier to solve since the class boundaries tend to be relatively simple. Moreover, some classification methods, such as SVMs (Vapnik 2000), are designed to work only on two-class problems. In pairwise classification, classifiers for all C(C − 1)/2 two-class problems are constructed. The challenge, then, is to map the output from the set of pairwise classifiers for each source (pairwise probabilities or class indicators) to a vector of C-class probabilities that accurately reflects the science class of that source. This problem is referred to as pairwise coupling.

The simplest method of pairwise coupling is voting (Knerr et al. 1990; Friedman 1996), where the class of each object is determined as the winner in a pairwise head-to-head vote. Pairwise voting is suboptimal because it ignores the pairwise class probabilities and tends to estimate inaccurate C-class probabilities. In situations where pairwise class probability estimates are available, voting is outperformed by other methods such as that of Hastie & Tibshirani (1998), which attempts to minimize the Kullback–Leibler distance between the observed pairwise probabilities and those induced by the C-class probabilities, and the approaches of Wu et al. (2004), which minimize a related discrepancy measure that reduces to solving a linear system of equations. In this paper, we explore the use of both tree-based classifiers and SVMs in pairwise classifiers. To obtain C-class probabilities, we employ the second pairwise coupling method introduced by Wu et al. (2004). We refer the interested reader to that paper for a more detailed description of the method and a review of similar techniques in the literature.

In variable-star classification, we have at our disposal a well-established hierarchical taxonomy of classes based on the physics and phenomenology of these stars and stellar systems. For instance, at the top level of our taxonomy, we can split the science classes into three main categories: pulsating, eruptive, and multi-star systems. From there, we can continue to divide the subclasses until we are left with exactly one of the original 25 science classes in each node (see Figure 2). For classification purposes, the meaning of the hierarchy is clear: mistakes at the highest levels of the hierarchy are more costly than mistakes made at deeper levels because the top levels of the hierarchy divide physical classes that are considerably different, whereas deeper levels divide subclasses that are quite similar.

Zoom In Zoom Out Reset image size

Incorporating a known class hierarchy, such as that of Figure 2, into a classification engine is a research field that has received much recent attention in the machine-learning literature (see Silla & Freitas 2011 for a survey of these methods). By considering the class hierarchy, these classifiers generally outperform their "flat classifier" counterparts because they impose higher penalties on the more egregious classification errors. In this paper, we consider two types of hierarchical classification approaches: hierarchical single-label classification (HSC; Cesa-Bianchi et al. 2006) and hierarchical multi-label classification (HMC; Blockeel et al. 2006, p. 18). We implement both HSC and HMC using RFs of decision trees. Below, we provide a synopsis of HSC and HMC. For more details about these methods, see Vens et al. (2008).

In HSC, a separate classifier is trained at each non-terminal node in the class hierarchy, whereby the probabilities of each classifier are combined using conditional probability rules to obtain each of the class probabilities. This has a similar flavor to the pairwise classifier approach of Section 3.3, but by adhering to the class hierarchy it needs only to build a small set of classifiers and can generate class probabilities in a straightforward, coherent manner. Moreover, different classifiers and/or sets of features can be used at each node in HSC, allowing for the use of more general classifiers at the top of the hierarchy and specialized domain-specific classifiers deeper in the hierarchy. A recent paper of Blomme et al. (2010) applied a method similar to HSC, using Gaussian mixture classifiers, to classify variable stars observed by the Kepler satellite. A second hierarchical classification approach is HMC, which builds a single classifier in which errors on the higher levels of the class hierarchy are penalized more heavily than errors deeper down the hierarchy. In the version of HMC that we use, the weight given to a classification error at depth d in the class hierarchy is w^d₀, where w₀ ∈ (0, 1) is a tuning parameter. This forces the algorithm to pay more attention to the top level, minimizing the instances of catastrophic error (defined in Section 4.3).

We have introduced a few methods that, given a sample of training data, estimate a classification model, $\widehat{p}$, to predict the science class of each new source. In this section, we introduce statistically rigorous methodology for assessing each classifier and choosing the best classifier among a set of alternatives. Since our ultimate goal is to accurately classify newly collected data, we will use the classifier that gives the best expected performance on new data. We achieve this by defining a classifier's statistical risk (i.e., prediction error) and computing an unbiased estimate of that risk via cross validation. We will ultimately use the model that obtains the smallest risk estimate.

Given a new source of class Y, having features X, we define a loss function, $L(Y,\widehat{p}(\mathbf {X}))$, describing the penalty incurred by the application of our classifier, $\widehat{p}$, on that source. The loss function encompasses our notion of how much the classifier $\widehat{p}$ has erred in predicting the source's class from its features X. The expected value of L, $E[L(Y,\widehat{p}(\mathbf {X}))]$, is the statistical risk, $R(\widehat{p})$, of the classifier. The expected value, E[ · ], averages over all possible realizations of (X, Y) to tell us how much loss we can expect to incur for the predicted classification of each new source (under the assumption that new data are drawn from the same distribution as the training data). A key aspect to this approach is that it guards against overfitting to the training data: if a model is overly complex, it will only add extra variability in classification without decreasing the bias of the classifier, leading to an increase in the risk (this is the bias-variance trade-off; see Wasserman 2006).

Conveniently, within this framework each scientist is free to tailor the loss function to meet their own scientific goals. For instance, an astronomer interested in finding Mira variables could define a loss function that incurs higher values for misclassified Miras. In this work, we use the vanilla 0–1 loss that is defined to be 0 if $Y = \widehat{p}(\mathbf {X})$ and 1 if misclassified (here, $\widehat{p}(\mathbf {X})$ is the estimated class of the source; alternatively, we could define a loss function over the set of estimated class probabilities, $\lbrace \widehat{p}_1(\mathbf {X}),...,\widehat{p}_C(\mathbf {X})\rbrace$). Under 0–1 loss, the statistical risk of a classifier is its expected overall misclassification rate, which we aim to minimize.

There remains the problem of how to estimate the statistical risk, $R(\widehat{p})$ of a classifier $\widehat{p}$. If labeled data were plentiful, we could randomly split the sources into training and validation sets, estimating $\widehat{p}$ with the training set and computing a risk estimate $\widehat{R}(\widehat{p})$ with the validation set. Since our data are relatively small in number, we use k-fold cross validation to estimate R. In this procedure, we first split the data into K (relatively) equal-sized parts. For each subset k = 1, ..., K, the classifier is fitted on all of the data not in k and a risk estimate, $\widehat{R}_{(-k)}(\widehat{p})$, is computed on the data in set k. The cross-validation risk estimate is defined as $\widehat{R}_{\rm CV}(\widehat{p})= \frac{1}{K} \sum _{k=1}^K\widehat{R}_{(-k)}(\widehat{p})$. As shown in Burman (1989), for K ≳ 4, $\widehat{R}_{\rm CV}(\widehat{p})$ is an approximately unbiased estimate of $R(\widehat{p})$. In this paper, we use K = 10 fold cross validation.

In addition to selecting between different classification models, cross-validation risk estimates can be used to choose the appropriate tuning parameter(s) for each classifier. For instance, we use cross validation to choose the optimal pruning depth for classification trees, to pick the optimal number and depth of trees to build, and number of candidate splitting features to use at each split for RFs, and to select the optimal size of the base learner, number of trees, and learning rate for boosted decision trees. The optimal set of tuning parameters for each method is found via a grid search. For each of the methods considered, we find that $\widehat{R}_{\rm CV}$ is stable in the neighborhood of the optimal tuning parameters, signifying that the classifiers are relatively robust to the specific choice of tuning parameters and that a grid search over those parameters is sufficient to obtain near-optimal results.

In this paper, we test our feature extraction and classification methods using a mixture of variable-star photometric data from the OGLE and Hipparcos surveys. Optical Gravitational Lensing Experiment (OGLE; Udalski et al. 1999) is a ground-based survey from Las Campanas Observatory covering fields in the Magellanic Clouds and Galactic bulge. Hipparcos Space Astrometry Mission (Perryman et al. 1997) was an ESA project designed to precisely measure the positions of more than one hundred thousand stars. The data selected for this paper are the OGLE and Hipparcos sources analyzed by Debosscher et al. (2007), totaling 90% of the variable stars studied in that paper. A summary of the properties, by survey, of the data used in our study, is in Table 1. The light-curve data and classifications used for each source can be obtained through our dotastro.org light-curve repository.⁷

This sample was designed by Debosscher et al. (2007) to provide a sizable set of stars within each science class, for a broad range of classes. Our sample contains stars from the 25 science classes analyzed in their paper. Via an extensive literature search, they obtained a set of confirmed stars of each variability class. In Table 2 we list, by science class, the proportion of stars in that data set that we have available for this paper. Since the idea of their study was to capture and quantify the typical variability of each science class, the light curves were pre-selected to be of good quality and to have an adequate temporal sampling for accurate characterization of each science class. For example, the multi-mode Cepheid and double-mode RR Lyrae stars, which have more complicated periodic variability, were sampled from OGLE because of its higher sampling rate.

In our sample, there are 25 objects that are labeled as two different science classes. Based on a literature search of these stars, we determine that 14 of them reasonably belong to just a single class (five S Doradus, two Herbig AE/BE, three Wolf–Rayet (W-R), two Delta Scuti, one Mira, and one Lambda Bootis). The other 11 doubly labeled stars, which are listed in Table 6, were of an ambiguous class or truly belonged to two different classes, and were removed from the sample. See Appendix B for a detailed analysis and references for the doubly labeled objects. Because the sample was originally constructed by Debosscher et al. (2007) to consist only of well-understood stars with confident class labeling, we are justified in excluding these sources.

Using the methodology in Section 2, we estimate features for each variable star in the data set using their light curve. The feature-extraction routines take 0.8 s per light curve, giving us a 53-dimensional representation of each variable star. The computations are performed in Python and C using a non-parallelized, single thread on a 2.67 GHz Intel Xeon X5550 CPU running on a v2.6.18 linux kernel machine. We estimate that the periodic-feature routines account for 75% of the computing time and scale linearly with the number of epochs in the light curve. Note that these metrics do not take into account the CPU time needed to read the XML data files from disk and load the data into memory.

Plots of one-dimensional density estimates, by science class, of a selected set of features are in Figure 3. These classwise feature distributions allow us to quickly and easily identify the differences, in feature space, between individual variable-star science classes. Density plots are very useful for this visualization because they provide a complete feature-by-feature characterization of each class, showing any multi-modality, outliers, and skewness in the feature distributions. For instance, it is immediately obvious that several of the eruptive-type variable-star classes have an apparent bi-modal or relatively flat frequency distributions, likely attributed to their episodic nature. Conversely, the RR Lyrae frequency distributions are all narrow and peaked, showing that indeed these stars are well characterized by the frequency of their flux oscillations. The feature density plots also inform us of which feature(s) are important in separating different sets of classes. For example, the RR Lyrae, FO and RR Lyrae, DM stars have overlapping distributions for each of the features in Figure 3 except the feature QSO, where their distributions are far apart, meaning that QSO will be a useful classification feature in separating stars of those two classes.

Zoom In Zoom Out Reset image size

In this section, we compare the different classification methods introduced in Section 3. To fit each classifier, except HMC–RF, we use the statistical environment R.⁸ To fit HMC–RF, we use the open-source decision tree and rule learning system Clus.⁹ Each of the classifiers was tuned via a grid search over the relevant tuning parameters to minimize the cross-validation misclassification rates. To evaluate each classifier, we consider two separate metrics: the overall misclassification error rate and the catastrophic error rate. We define catastrophic errors to be any classification mistake in the top level of the variable-star hierarchy in Figure 2 (i.e., pulsating, eruptive, multi-star). The performance measures for each classifier, averaged over 10 cross-validation trials, are listed in Table 3. In terms of overall misclassification rate, the best classifier is an RF with B = 1000 trees, achieving a 22.8% average misclassification rate. In terms of catastrophic error rate, the HSC–RF classifier with B = 1000 trees achieves the lowest value, 7.8%. The processing time required to fit the ensemble methods is greater than the time needed to fit single-tree models. However, this should not be viewed as a limiting factor: once any of these models is fit, predictions for new data can be produced very rapidly. For example, for an RF classifier of 1000 trees, class probability estimates can be generated for new data at the rate of 3700 instances per second.

4.3.1. Tree-based Classifiers

4.3.2. Pairwise Classifiers

4.3.3. Hierarchical Classifiers

RF achieves a 22.8% average misclassification rate, a 24% improvement over the 30% misclassification rate achieved by the best method of Debosscher et al. (2007; Bayesian model averaging of artificial neural networks). Furthermore, each of the classifiers proposed in this paper, except the single-tree models CART and C4.5, achieves an average misclassification rate smaller than 25.8% (see Table 3). There is no large discrepancy between the different ensemble methods—the difference between the best (RF) and worst (boosting) ensemble classifier is 2.2%, or an average of 34 more correct classifications—but in terms of both accuracy and speed, RF is the clear winner.

In comparing our results to the Debosscher et al. (2007) classification results, it is useful to know whether the gains in accuracy are due to the use of better classifiers, more accurate periodic-feature extraction, informative non-periodic features, or some combination of these. To this end, we classify these data using the following sets of features:

• 1.  
  the periodic features estimated by Debosscher et al. (2007);
• 2.  
  our estimates of the periodic features following Section 2;
• 3.  
  the non-periodic features proposed in Section 2; and
• 4.  
  the non-periodic features in addition to our periodic features.

Misclassification rates from the application of our classifiers to the above sets of features are plotted in Figure 4. As a general trend, using both our periodic and non-periodic features is better than using only our periodic features, which is in turn better than using Debosscher et al.'s periodic features, which achieves similar rates to using only the non-periodic features. Using an RF classifier, we find that the average cross-validated misclassification rates are 22.8% using all features, 23.8% using our periodic features, 26.7% using Debosscher et al. (2007) features, and 27.6% using only our non-periodic features. This is evidence that we obtain better classification results both because our classification model is better and because the extracted features we use are more informative.

Zoom In Zoom Out Reset image size

Understanding the source and nature of the mistakes that our classifier makes can alert to possible limitations in the classification methods and feature-extraction software and aid in the construction of a second-generation light-curve classifier. Let us focus on the classifier with the best overall performance: the RF, whose cross-validated misclassification rate was 22.8%. In Figure 5, we plot the confusion matrix of this classifier, which is a tabular representation of the classifier's predicted class versus the true class. A perfect classifier would place all of the data on the diagonal of the confusion matrix; any deviations from the diagonal inform us of the types of errors that the classifier makes.

Zoom In Zoom Out Reset image size

A few common errors are apparent in Figure 5. For instance, Lambda Bootis and Beta Cephei are frequently classified as Delta Scuti. Wolf-Rayet, Herbig AE/BE, and S Doradus stars are usually classified as Periodic Variable Super Giants, and T Tauri are often misclassified as Semiregular Pulsating Variables. None of these mistakes are particularly egregious: often the confused science classes are physically similar. Also, the misclassified examples often come from classes with few training examples (see below) or characteristically low-amplitude objects (see Section 4.8).

As the RF is a probabilistic classifier, for each source it supplies us with a probability estimate that the source belongs to each of the science classes. Until now, we have collapsed each vector of probabilities into an indicator of most probable class, but there is much information available to extract from the individual probabilities. For instance, in Figure 6 we plot, by class, the RF estimated probability that each source is of its true class. We immediately see a large disparity in performance between the classes: for a few classes, we estimate high probabilities of true class, while for others we generally estimate low probabilities. This discrepancy is related to the size of each class: within the science classes that are data-rich, we tend to get the correct class, while in classes with scarce data, we usually estimate the wrong class. This same effect is seen in Debosscher et al. (2007, their Table 5). This is a common problem in statistical classification for imbalanced class sizes: classifiers such as RF try to minimize the overall classification rate, thus focusing most of their efforts on the larger classes. In these methods, there is an implicit prior that the class frequencies equal their observed proportions. One can attempt to achieve better error rates within the smaller classes by imposing a flat prior, which is attained by weighting the training data inversely proportional to their class frequency. The price to pay for the increase in balanced error among the classes is a higher overall misclassification rate (see Breiman et al. 1984). The better solution is to obtain more training examples for the undersampled classes to achieve a better characterization of these sources.

Zoom In Zoom Out Reset image size

We have experimented with an RF classifier using inverse class-size weighting. The results of this experiment were as expected: our overall misclassification rate climbs to 28.0%, a 23% increase in error over the standard RF, but we perform better within the smaller classes. Notably, the number of correctly classified Lambda Bootis increases from 1 to 7, while the number of correctly classified Ellipsoidal variables jumps from 6 to 11, Beta Cephei from 5 to 23, and Gamma Doradus from 8 to 15. All four classes in which the original RF found no correct classifications each had at least two correct classifications with the weighted RF.

Although our classifier was constructed to minimize the number of overall misclassifications in the 25-class problem, we can also use it to obtain samples of objects from science classes of interest via probability thresholding. The RF classifier produces a set of classwise posterior probability estimates for each object. To construct samples of a particular science class, we define a threshold on the posterior probabilities, whereby any object with class probability estimate larger than the threshold is included in the sample. By decreasing the threshold, we trade-off purity of the sample for completeness, thereby mapping out the receiver operating characteristic (ROC) curve of the classifier.

In Figure 7, we plot the cross-validated ROC curve of the multi-class RF for four different science classes: (a) RR Lyrae, FM, (b) T Tauri, (c) Milky Way Structure, which includes all Mira, RR Lyrae, and Cepheid stars, and (d) Eclipsing Systems, which include all Beta Persei, Beta Lyrae, and W Ursae Major stars. Each ROC curve shows the trade-off between the efficiency and purity of the samples. At a 95% purity, the estimated efficiency for RR Lyrae, FM, is 94.7%, for Milky Way Structure stars 98.2%, and for Eclipsing Systems 99.1%. The T Tauri ROC curve is substantially worse than these other classes due to the small number of sources (note: inverse class-size weighting does not help in this problem because the ordering of the posterior class probabilities drives the ROC curve, not the magnitude of those probabilities). Surprisingly, the 25-class RF ROC curve dominates the ROC curve of a one-versus-all RF for three of the four science classes, with vastly superior results for small classes.

Zoom In Zoom Out Reset image size

In Section 3.2, we described how to estimate the importance of each feature in a tree-based classifier. In Figure 8, the importance of each feature from a pairwise RF classifier is plotted by class. The intensity of each pixel depicts the proportion of instances of each class that are correctly classified by using each particular feature in lieu of a feature containing random noise. The intensities have been scaled to have the same mean across classes to mitigate the effects of unequal class sizes and are plotted on a square-root scale to decrease the influence of dominant features. In independently comparing the performance of each feature to that of noise, the method does not account for correlations among features. Consequentially, sets of features that measure similar properties—e.g., median_absolute_deviation,std,and stetson_j are all measures of the spread in the fluxes—may each have high importance, even though their combined importance is not much greater than each of their individual importances.

Zoom In Zoom Out Reset image size

Figure 8 shows that a majority of the features used in this work have substantial importance in the RF classifier for discerning at least one science class. Close inspection of this figure illuminates the usefulness of certain features for distinguishing specific science classes. As expected, the amplitude and frequency of the first harmonic, along with the features related to the spread and skew of the flux measurements, have the highest level of importance. The flux amplitude is particularly important for classifying Mira stars, Cepheids, and RR Lyrae, which are distinguished by their large amplitudes. The frequency of the first harmonic has high importance for most pulsating stars, likely because these classes have similar amplitudes but different frequencies. The QSO-variability feature is important for identifying eruptive sources, such as Periodically Variable Super Giants and Chemically Peculiar stars, because these stars generally have small values of the QSO feature compared to other variable star classes.

In addition, there are several features that have very low importance for distinguishing any of the science classes. These features include the relative phase offsets for each of the harmonics, the amplitudes of the higher-order harmonics, and non-periodic features such as beyond1std, max_slope, and pair_slope_trend. We rerun the RF classifier excluding the 14 features with the smallest feature importance (the excluded features are nine relative phase offsets, beyond1std, max_slope, pair_slope_trend, and the 65th, and 80th middle flux percentiles. Results show a cross-validated error rate of 22.8% and a catastrophic error rate of 8.2% (averaged over 10 repetitions of the RF), which is consistent with the error rates of the RF trained on all 53 features, showing the insensitivity of the RF classifier to inclusion of features that carry little or no classification information.

High-amplitude variable stars constitute many of the central scientific impetuses of current and future surveys. In particular, finding and classifying pulsational variables with known period–luminosity relationships (Mira, Cepheids, and RR Lyrae) is a major thrust of the LSST (Walkowicz et al. 2009; LSST Science Collaborations et al. 2009). Moreover, light curves from low-amplitude sources generally have a lower S/N, making it more difficult to estimate their light-curve-derived features and hence more difficult to obtain accurate classifications. Indeed, several of the classes in which we frequently make errors are populated by low-amplitude sources.

Here we classify only those light curves with amplitudes greater than 0.1 mag, removing low-amplitude classes from the sample. This results in the removal of 383 sources, or 25% of the data. After excluding these sources, we are left with a handful of classes with less than seven sources. Due to the difficulty in training (and cross validating) a classifier for classes with such small amount of data, we ignore those classes, resulting in the exclusion of 19 more sources, bringing the total to 408 excluded sources, or 26% of the entire data set. We are left with 1134 sources in 16 science classes.

On this subset of data, our RF classifier achieves a cross-validated misclassification rate of 13.7%, a substantial improvement from the 22.8% misclassification rate from the best classifier on the entire data set. The catastrophic misclassification rate is only 3.5%, compared to 8.0% for the entire data set. In Figure 9, the confusion matrix for the classifier is plotted. The most prevalent error is misclassifying Pulsating Be and T Tauri stars as semiregular pulsating variables. On average eight of the nine Pulsating Be stars and four of the twelve T Tauri stars are misclassified as semiregular pulsating variables.

Zoom In Zoom Out Reset image size

Data for the sources that we classify in this section come from either the OGLE or Hipparcos surveys. Specifically, there are 523 sources from five science classes whose data are from OGLE, while the data from the remaining 858 sources are from Hipparcos. Our classifiers tend to perform much better for the OGLE data than for the Hipparcos sources: for the RF classifier we obtain a 11.3% error rate for OGLE data and 27.9% error rate for Hipparcos.

It is unclear whether the better performance for OGLE data is due to the relative ease at classifying the five science classes with OGLE data or because of differences in the survey specifications. The sampling rate of the OGLE survey is three times higher than that of Hipparcos. The average number of observations per OGLE source is 329, compared to 103 for Hipparcos, even though the average time baselines for the surveys are each near 1100 days. OGLE observations have on average twice the flux as Hipparcos observations, but the flux measurement errors of OGLE light curves tend to be higher, making their respective S/Ns similar (OGLE flux measurements have on average an S/N 1.25 times higher than Hipparcos S/Ns).

To test whether the observed gains in accuracy between OGLE and Hipparcos sources are due to differences in the surveys or differences in the science classes observed by each survey, we run the following experiment. For each OGLE light curve, we thin the flux measurements down to one-third of the original observations to mimic Hipparcos conditions and rerun the feature-extraction pipeline and classifier using the thinned light curves. Note that we do not add noise to the OGLE data because of the relative similarity in average S/N between the surveys; the dominant difference between data of the two surveys is the sampling rate. Results of the experiment are that the error rate for OGLE data increases to 13.0%, an increase of only 1.7% representing nine more misclassified OGLE sources. This value remains much lower than the Hipparcos error rate, showing that the better classifier performance for OGLE data is primarily driven by the ease of distinguishing those science classes.

A description of the 32 periodic features computed using the methodology in Section 2.1 is in Table 4. In addition to these 32 periodic features, we calculate 20 non-periodic features for every light curve (Section 2.2). These features are compiled in Table 5. These consist primarily of simple statistics that can be calculated in the limit of few data points and also when no period is known in order to characterize the flux variation distribution. Where possible, we give the name of the Python function that calculates the feature (e.g., skewness is from scipy.stats.skew()in the Python SciPy module).

We begin with basic moment calculations using the observed photometric magnitude mag vector for each source:

• 1.  
  skew: skewness of the magnitudes: scipy.stats.skew();
• 2.  
  small_kurtosis: small sample kurtosis of the magnitudes;¹⁰
• 3.  
  std: standard deviation of the magnitudes: Numpy std();
• 4.  
  beyond1std: the fraction (⩽1) of photometric magnitudes that lie above or below one std() from the weighted (by photometric errors) mean;
• 5.  
  stetson_j: Stetson (1996) variability index, a robust standard deviation;
• 6.  
  stetson_k: Stetson (1996) robust kurtosis measure.

We also calculate the following basic quantities using the magnitudes:

• 1.  
  max_slope: examining successive (time-sorted) magnitudes, the maximal first difference (value of delta magnitude over delta time);
• 2.  
  amplitude: difference between the maximum and minimum magnitudes;
• 3.  
  median_absolute_deviation: median(|mag − median(mag)|);
• 4.  
  median_buffer_range_percentage: fraction (⩽1) of photometric points within amplitude/10 of the median magnitude;
• 5.  
  pair_slope_trend: considering the last 30 (time-sorted) measurements of source magnitude, the fraction of increasing first differences minus the fraction of decreasing first differences.

We also characterize the sorted flux F = 10^−0.4 mag distribution using percentiles, following Eyer (2006). If F_5,95 is the difference between 95% and 5% flux values, we calculate the following:

• 1.  
  flux_percentile_ratio_mid20: ratio F_40,60/F_5,95;
• 2.  
  flux_percentile_ratio_mid35: ratio F_32.5,67.5/F_5,95;
• 3.  
  flux_percentile_ratio_mid50: ratio F_25,75/F_5,95;
• 4.  
  flux_percentile_ratio_mid65: ratio F_17.5,82.5/F_5,95;
• 5.  
  flux_percentile_ratio_mid80: ratio F_10,90/F_5,95;
• 6.  
  percent_amplitude:the largest absolute departure from the median flux, divided by the median flux;
• 7.  
  percent_difference_flux_percentile:ratio of F_5,95 over the median flux.

Finally, useful for stochastically varying sources, we calculate the quasar similarity metrics from Butler & Bloom (2011):

• 1.  
  QSO: quality of fit χ²_QSO/ν for a quasar-like source, assuming mag = 19;
• 2.  
  non_QSO: quality of fit for a non-quasar-like source (related to NULL value of QSO).

As discussed in Section 4.1, there are 25 sources with more than one class label. Five of these objects are labeled as both S Doradus and periodically variable super giants. We assign these to the S Doradus class because S Doradus is a subclass of periodically variable super giants. Two other sources, V* BF Ori and HD 97048, were verified to be Herbig AE/BE-type stars by Grinin et al. (2010) and Doering et al. (2007), respectively. RY Lep is listed incorrectly in Simbad as an Agol-type eclipsing system (its original 50 year old classification) and as RR Lyrae/Delta Scuti. Derekas et al. (2009) clearly establish this source as a high-amplitude δ-Scuti in a binary system. Likewise, HIP 99252 is a δ-Scuti star (Rodríguez et al. 2000) and not also an RR Lyrae. HIP 30326 (=V Mon) is a Mira variable and not also part of the RV Tauri class (Whitelock et al. 2008). HD 210111 (listed also as delta Scuti) is a λ Bootis star (Paunzen & Reegen 2008). HD 165763 is a W-R star that is not periodic to a high degree of confidence (Moffat et al. 2008). Likewise, WR40 is not periodic as it was once believed (Marchenko et al. 1994). We found no reference to the periodic nature of the W-R star HD 156385. The remaining 11 sources were of ambiguous class or truly deserved of two classes and were excluded from the training and testing sample. These stars are listed in Table 6 and briefly mentioned below.

• 1.  
  HD 136488 = HIP 75377. This is a W-R with a measured periodicity in Hipparcos data (Koen & Eyer 2002).
• 2.  
  HD 94910 = AG Car. This is a W-R thought to be a "hot, quiescent state LBV" (Clark et al. 2010).
• 3.  
  HD 50896 = EZ CMa = W-R 6. Listed as both a W-R and periodic variable super giant, this is a prototype W-R and has a known periodic variability possibly due to a binary companion (Flores et al. 2007).
• 4.  
  HD 37151. Slowly pulsating B stars (SPBs) occur in the same instability strip of the H-R diagram as chemically peculiar B stars (with variability associated with rotation and magnetic fields). The classification of this star is particularly ambiguous (see Briquet et al. 2007 and references therein).
• 5.  
  HD 35715. Is a cataloged Beta Cepheid but is also an ellipsoidal variable (Stankov & Handler 2005). Pulsation was not detected photometrically but in line profiles.
• 6.  
  HIP34042 (Z CMa A). Is a binary system consisting of a Herbig component (A) and an FU Orionis star (B) in a close orbit. Determining the photometric contributions of the two components separately is problematic because of strong variability and the small angular separation (Millan-Gabet & Monnier 2002).
• 7.  
  TV Lyn, UY Cam, V1719 Cyg (HD 200925), and V753 Cen. Ambiguous classification (within the literature) of RR Lyrae or Delta Scuti-type stars.
• 8.  
  IK Hya. Is a short-period Pop. II Cepheid, making it likely a BL Herculis-type star.

We trained an RF classifier on the features of only the single-labeled stars and then predicted the class probabilities of each label for the doubly labeled stars. This experiment shows that for 7 of the 11 sources, our classifier predicts one of the two classes that the star was originally labeled as. Note that recently, several methods have been developed to classify data with multiple labels (multi-label classification; see Tsoumakas & Katakis 2007), but for the purposes of this work we choose to only perform single-label classification, and remove these data from our sample to avoid biases from inaccurate training labels.