Positive Unlabeled Leaning for Time Series Classification

1 Introduction

Time series data are commonly found in many application domains including multimedia, medicine, aerospace, finance, manufacturing and entertainment (Olszewski 2001; Rath and Manmatha 2003; Xi, Keogh et al. 2006). A key task is to classify the time series data into predefined categories. For example, a typical application in manufacturing would be to classify the machines into normal or faulty statuses based on time series sensor readings.

Classification methods that simply apply traditional supervised learning techniques on the time series data rely on having large amounts of labeled examples for learning accurate classifiers. In practice, collecting and labeling large sets of training data could be very expensive and sometimes even impossible. As such, alternative learning techniques have been proposed to build classifiers from a small amount of labeled training data and a large set of unlabeled data which are typically available for learning. These methods include semi-supervised learning (Li and Zhou 2005; Chapelle, Scholkopf et al. 2006; Zhu 2008) and PU learning (Li and Liu 2003; Li, Liu et al. 2007; Li, Yu et al. 2009). While both approaches exploit the unlabelled data (U) to enhance the performance of their classifiers, they differ in the training data requirement as PU learning only requires positive data (P). As a result, PU learning is applicable in a wide range of application domains, e.g. text classification, biomedical informatics, pattern recognition, and recommendation system, as negative data are often unavailable in the real-world applications. However, due to the various challenges of time series classification such as high feature correlation (Wei and Keogh 2006), the application of PU learning to classify time series data has been relatively less explored than other data classification tasks.

Recently, Wei and Keogh (Wei and Keogh 2006) proposed a PU learning approach that iteratively expands the initial positive examples using those unlabelled data that are most similar to them, with the remaining unlabelled data being extracted as negative data. Unfortunately, without a good stopping criterion, the method often stops too early with an expansion of a small number of positives. The corresponding negatives being extracted are therefore not pure, resulting in classifiers with limited accuracy. To improve the algorithm, a more recent method (Ratanamahatana and Wanichsan 2008) attempted to propose a good stopping criterion by using the historical distances between candidate examples from U to the initial positive examples. Although more positive examples can be extracted, the method is unable to extract accurate positives and hence negatives from U. The resulting classifier therefore fails to identify the ground truthÕs boundary between positive and negative data. The experimental results reported showed that the classification results had high precision but low recall.

In this paper, we propose an effective technique called LCLC (Learning from Common Local Clusters) to tackle the challenge of constructing a robust classifier for time series classification using only limited labeled positive data. The proposed method first partitions the unlabeled set U into small unlabeled local clusters (ULC). It treats each cluster as an observed variable in which all the data belonging to the cluster share the same principal component and have the same class value. Our method will learn the local clustersÕ common principal features in order to choose independent and relevant features for classification. Next, LCLC automatically extracts the hidden positive clusters and negative clusters from U. Our cluster-based approach is much more reliable than existing PU learning methods that extract negative and positive instances point by point. We also propose a novel cluster chain approach which is critical for contributing to accurate cluster extraction.

The rest of the paper is organized as follows. First, we provide an overview on the related works of PU learning in Section 2. We then present our proposed LCLC algorithm and its experimental results in Sections 3 and 4 respectively. Extensive experiments on time series data across diverse fields show that classifiers built using LCLC can accurately identify the ground truthsÕ positive and negative boundaries, thereby significantly outperforming the existing state-of-theart PU learning methods for time series classification. Finally, Section 5 concludes the paper.

2 Related Work

As mentioned, traditional supervised learning methods rely on having sufficient positive and negative training examples available for learning. In practice, the negative examples can often be limited or unavailable. This has motivated the development of the model of learning from positive and unlabeled examples, or PU learning, where P denotes a set of positive examples, and U a set of unlabeled examples (which contains both hidden positive and hidden negative instances). The PU learning problem is therefore to build a classifier using P and U in the absence of negative examples to classify the data in a future test data T.

PU learning has been investigated by numerous researchers in the past decade or so. A study of PAC learning for the PU setting under the statistical query model was first given in (Denis 1998). An extension of positive naive Bayes learning for probabilistic problems could be found in (Borja, Pedro et al. 2007). (Liu, Lee et al. 2002) reported the sample complexity result and showed how the problem may be solved. Subsequently, a number of practical algorithms (Liu, Lee et al. 2002; Li and Liu 2003) were proposed. They generally follow a two-step strategy: (i) identifying a set of reliable negative documents RN from the unlabeled set U, and then (ii) building a classifier with the positive set P, the reliable negative set RN and the new unlabelled set UÕ (UÕ=U-RN), using EM, or running SVM iteratively. Please refer to (Liu 2007) for the details of more recently developed PU learning algorithms.

To our best knowledge, thus far only two PU learning approaches (Wei and Keogh 2006; Ratanamahatana and Wanichsan 2008) have been proposed for classifying time series data. However, as we have discussed in the previous section, the current methods are unable to accurately extract the reliable positive and negative examples from U, resulting in inaccurate classifiers. Given that time series data are commonly found in many application domains, we are thus motivated to explore devising better PU learning techniques for time series data classification.

3 The Proposed Technique

In this section, we present our proposed LCLC algorithm. Our method is designed to address two specific issues in PU learning for time series classification: how to select independent and relevant features from the time series data, and how to accurately extract reliable positive and negatives from the given unlabelled data. We design our algorithm to build robust classifiers with a small number of positives, even in the extreme scenario of having only one seed positive example.

3.1 Local Clustering and Feature Selection

Clearly, the single seed positive example set is too small to represent the positive feature space. We need to include additional high-confidence positive examples from U to construct an initial positive set P. In this paper, we adopt WeiÕs method (Wei and Keogh 2006) for this task. Given the seed positive s, we add the next most confident positive instances from U until the stopping criterion is reached, namely, there is a drop of the minimal nearest neighbor distance. WeiÕs method uses this early stopping criterion because if a negative example were to be mistakenly added into P, there is a high chance that we will keep adding more negative examples as the negative space is much denser than the positive space (Wei and Keogh 2006). While this method tends to provide an early stop instead of proceeding to find the actual boundary between the positives and negatives, we observe that it is useful for constructing a positive set P with very high precision. In other words, we can obtain a ÒpureÓ positive set P that is reasonably bigger than the original one seed positive example set to work with.

Next, we partition the remaining unlabeled data U (U = U - (P - {s})) into small local clusters ULCi (i=1, 2, É, K) using K-means clustering method (Kanungo, Mount et al. 2002). Each local cluster ULCi is treated as an observed variable of the time series data, and we assume that all the instances belonging to a local cluster share the same principal component and have the same class label. We use these local clusters for two purposes: 1) Instead of extracting individual likely positive and negative examples as in previous PU learning methods, we extract the likely positives and negatives based on the clusters (See Subsection 3.2). 2) Given that time series data have high feature correlation, we can exploit the clusters for feature selection, choosing a subset of common principal features from the raw feature set that better captures the underlying characteristics of the time series data set.

We find that this novel cluster-based approach of feature selection together with the robust cluster-based extraction of likely positives and negatives from the unlabelled test set help to build more accurate classifiers. Recall that the similarity between two time series data records can be effectively measured by comparing their principal components of the corresponding features (Yoon, Yang et al. 2005; Hyunjin and Cyrus 2006). A well-selected subset of the common principal features can capture the underlying characteristics of the time series data set to enable accurate extraction of the remaining hidden positives/negatives from U, subsequently identifying the boundary between positive and negative data. In this work, we use the Clever-Cluster method (Yoon, Yang et al. 2005) for selecting a common feature subset from the positive set P (a ÒpureÓ positive local cluster generated using WeiÕs method) and a partitioned coherent unlabelled cluster ULCi as follows.

Let Xi be the correlation matrix of the ith local cluster ULCi (i=1, 2, É, K) and XK+1 be the correlation matrix of positive cluster P. We first compute the principal components (PCs) matrix Li for all correlation matrixes (X1, X2 , É, XK+1) by applying Singular Value Decomposition (SVD):

Suppose we have n raw features in our time series data. Although there are n PCs for each cluster, for feature selection, only the first p (p <n) PCs are taken into consideration. Each cluster can thus be represented as a p n ⋅ matrix in which the p rows are its first p principal components and columns represent the feature indexes. In our implementation, p is chosen at 80%*n as recommended in (Yoon, Yang et al. 2005). Let the integration matrix H of these clusters be

The descriptive common principal components (DCPCs) that agree most closely with all the local clusters are then defined by the eigenvectors of H, i.e.

where the rows of V are the eigenvectors of the integration matrix H and the first p of them define the DCPCs for our K+1 clusters. is a diagonal matrix whose diagonal elements are the eigenvalues of H. They describe the total discrepancy between DCPCs and PCs. Just like the PC matrix of a local unlabelled cluster and positive cluster, the p rows of this DCPC matrix are the first principal components, while the columns still represent the n raw feature indexes, and the (i,j)th element is a DCPC loading of the jth variable to the ith DCPC. The correspondence to the original raw features is still retained in the columns of the DCPCs matrix with each raw feature now represented as a column vector of its DCPC loadings. Algorithm 1 below provides the detailed steps for selecting such a subset of common principal features. π

Algorithm 1. Local clustering and feature selection

Input: one initial seed positive s, unlabelled dataset U, number of clusters K

1. Use WeiÕs method to get an initial positive set P;
2. Partition the remaining unlabeled data U - (P - {s}) into K unlabeled local clusters using Kmeans clustering;
3. Compute principal components for positive cluster P, and each unlabelled cluster ULCi into a principal matrix Li for (i=1, .. , K+1);
4. 1 1 K T i i i H L L 0 _ _ ⎠
5. Compute the descriptive common principal components (DCPCs) on matrix H;
6. Compute raw feature vector of its DCPC loadings;
7. Perform K-means clustering algorithm to cluster the raw feature vectors (DCPC loadings) into K feature groups
8. Select K features (v1, v2, É,vK) from the raw feature set

Note that we have used K-means clustering algorithm again to cluster the raw feature vectors (DCPC loadings) into K feature groups in which the related raw features are grouped together. Since K-means could reach local minima, we repeat the K-means clustering 10 times and choose the one with the minimum sum of Euclidean distances between each clusterÕs centroid and its component feature vectors within the cluster as the best clustering result. Finally, the K highest mutual information features (Cai, He et al. 2005) are selected from these clusters as our final feature set. Specifically, for each cluster, we choose the one feature closest to the centroid of that cluster. The intuition behind such selection is based on the observation that features with similar patterns of loading values will be highly correlated and have high mutual information (Yoon, Yang et al. 2005).

3.2 Building the Final Classifier

There have been many algorithms proposed for time series classification; most of them are traditional supervised learning based techniques. Keogh et al (Keogh and Kasetty 2003) performed a comprehensive empirical evaluation on the current state-of-the-arts. Interestingly, the simple technique K-NN (specifically, 1-NN, i.e. classification based on the top one nearest neighbor) with Euclidean distance was shown to be the best technique. These supervised learning methods, including 1-NN, require both positive and negative training sets for learning. In the PU learning setting, there is therefore the need to extract a reliable negative set RN from the unlabeled set U as we only have positive set P.

Extracting Reliable Negative set RN

It is important to extract a RN according to the following two criteria: (1) The RN should cover as many diverse negative instances as possible; and (2) the negative data extracted from the unlabeled set U should be reasonably reliable or pure, i.e., with no or very few positive instances (i.e. false negatives). The presence of false negatives in RN will hurt the performance of the subsequent steps of extracting the likely positives and the likely negatives. The final step to build 1-NN classifier is also very sensitive to noise.

Algorithm 2. Extracting Reliable Negative Examples

Input: positive data P, K unlabeled local clusters ULCi

1. RN = ⇓, AMBI= ⇓;
2. For i=1 to K
3. Compute the distance between local cluster ULCi to P;
4. Sort d(ULCi , P) (i=1, 2, É, K) in a decreasing order;
5. dMedian= the median distance of d(ULCi , P) (i=1, 2,É, K);
6. For i=1 to K
7. If (d(ULCi , P)> dMedian)
8. RN= RN⇒ULCi;

9. Else

1. AMBI = AMBI ⇒ULCi;

Algorithm 2 above shows the steps to extract the reliable negative set RN. In step 1, both RN (which is used to store the reliable negative data) and AMBI (which is used to store the ambiguous data), are initialized as empty set. In steps 2 and 3, we compute the distance of each ULCi (i=1, 2, É, K) from our positive data P using the features selected (see previous Section 3.1). The distance between ULCi and P are defined as follows:

(4) Note that d(ULCi , P) is the minimum distance between all instances in ULCi and all the instances in P. Let ULCi = (a1, a2, É , aK) and P=(b1, b2, É , bK). The dist(xULC , xP) is computed using Euclidean distance between each pair of corresponding elements based on the K common selected features: ( , ) min( ( , )), , i UCL P UCL i P d UCL P dist x x x UCL x P _ # ∨ # ∨

Steps 4 and 5 then sort all the distances d(ULCi , P) in decreasing order and compute the median distance dMedian. Finally, in steps 6 to 10, we extract those local clusters which are farthest away from P and store them into RN. The size of RN is set to contain a half of the local clusters, while the other half is considered as ambiguous clusters AMBI to be processed further in the next phase.

Identifying Likely Positive Clusters LP and Likely Negative Clusters LN

Since we now have a positive data P and reliable negative data RN, we should be able to build a classifier using any supervised learning method. However, the number of initial positive training examples in cluster P is often insufficient, and the reliable negative clusters in RN extracted in the previous step is still far away from the boundary between the actual positive and negative data. To build a robust classifier, an important next step in our LCLC algorithm is to further extract the likely positive clusters LP and the likely negative clusters LN from instances in the ambiguous clusters AMBI which are near the positive and negative boundary.

We propose a novel idea to build cluster chains. Each cluster chain starts from the positive P, goes through one or more AMBI clusters, and finally stops at one reliable negative cluster in RN. Figure 1 illustrates the scenario where we have 5 five reliable negative clusters which are far away from the positive cluster, and 5 AMBI clusters which are located between the positive cluster and negative clusters.

We show two possible cluster chains: the chain on the lefthand side consists of 4 clusters (including two AMBI clusters) while the chain on the right-hand side consists of 5 clusters (including three AMBI clusters). For each cluster chain, we find the breaking link (decision boundary) with maximal distance between the clusters and separate the cluster chain into two sub-chains. All the AMBI clusters within a sub-chain including P will be regarded as likely positive clusters and stored into LP, while all the AMBI clusters within a sub-chain including RN will be regarded as likely negative clusters and stored into LN.

We use different measures to evaluate the distances between different types of clusters. The distance between a AMBI cluster CAMBI and the positive cluster P or a negative cluster CRN (CRN ∨RN) is defined as the minimum distance from the centroid of the AMBI cluster to every instance of cluster P or CRN, i.e.

d(CAMBI, CRN) = min(dist(centroidAMBI, xn)), n RN x C # ∨ (7) where centroidAMBI is the centroid of the AMBI cluster. On the other hand, the distance between two AMBI clusters CAMBI,A and CAMBI,B is computed based on the distance between their two centroids centroidAMBI,A and centroidAMBI,B:

d(CAMBI,A, CAMBI,B) = dist(centroidAMBI,A, centroidAMBI,B) (8) Note that we have used centroids instead of directly using the examples/points to compute the distance between two AMBI clusters. This is because compared with the relatively more reliable positive cluster P and negative clusters in RN, the AMBI clusters are likely to contain noisy examples which could result in inaccurate distance measure if we used individual examples. We therefore use centroids to minimize the effect of possible noisy examples.

Algorithm 3. Identifying likely positive clusters LP and likely negative clusters LN

Input: ambiguous clusters AMBI, positive cluster P, reliable negative clusters set in RN

1. LP =⇓; LN =⇓;
2. i = 0;
3. While (AMBI!= ⇓)
4. Find the nearest AMBI cluster CAMBI,A to P and add CAMBI,A to cluster-chaini ;
5. While CAMBI,A ∠ RN
6. Find the nearest cluster CAMBI,B (from AMBI ⇒ RN) to CAMBI,A and add CAMBI,B to cluster-chaini;
7. CAMBI,A= CAMBI,B;
8. i= i + 1;
9. Loop for all the cluster-chaini
10. breaking linki (Cm, Cm+1)= the link with maximal distance between the clusters in cluster-chaini
11. Separate the cluster chain cluster-chaini into two sub-chains;
12. Move all the ambiguous clusters from the clusterchaini with P into likely positive clusters LP;
13. Move all the ambiguous clusters from the clusterchaini without P (or stops with a negative cluster in RN) into likely negative clusters LN;

Algorithm 3 above shows the steps to identify the likely positive clusters LP and negative clusters LN. After initializing LP and LN in step 1 as empty sets, we build the cluster chains from steps 2 to 8. Then, for each cluster-chain, we break it into two sub-chains by separating the link with maximal distance. In particular, steps 9 to 13 allocate the ambiguous clusters into positive clusters LP if they are located in the sub-chains that include P, and negative clusters LN if they are located in the sub-chains that include a negative cluster in RN. The breaking links serve as the decision boundaries for separating the positive and negative ambiguous clusters. This process (from steps 9 to 13) is repeated until we have separated all the cluster chains and all the ambiguous clusters will be put into either LP or LN.

We are now ready to build the classifier for time series classification: we use P together with LP as a positive training set, and RN together with LN as a negative training set to build our final 1-NN classifier.

4 Empirical Evaluation

In this section, we compare our proposed LCLC algorithm with two existing state-of-the-art semi-supervised methods for time series classification that we have mentioned earlier, namely, WeiÕs method (Wei and Keogh 2006), and RatanamahatanaÕs method (denoted as RatanaÕs method) (Ratanamahatana and Wanichsan 2008). We use the F-measure to evaluate the performance of the three PU learning techniques. The F-measure is the harmonic mean of precision (p) and recall (r), and it is defined as F=2*p*r/(p+r). In other words, the F-measure reflects an average effect of both precision and recall. F-measure is large only when both precision and recall are good. This is suitable for our purpose to accurately classify the positives and negatives. Having either too small a precision or too small a recall is unacceptable and would be reflected by a low F-measure.

To facilitate comparison, similar to the experiments reported in (Wei and Keogh 2006), we have performed our empirical evaluation on the five diverse time series datasets across different fields from (Wei 2007) and the UCR Time Series Data Mining archive (Keogh 2008). The details of the datasets are shown in Table 1.

In our empirical evaluation, we randomly select just one seed instance from the positive class for the learning phase, and treat it as our only initial positive seed data; the rest of training data are treated as unlabeled data (ignoring their labels) for training. Given the random nature of choosing the initial positive examples and K-means clustering, we repeat our experiments 30 times and report the average values of the 30 results.

Table 2 shows the classification results of the three techniques. LCLC produces the best results consistently across all the data sets, achieving F-measures of 86.7%, 72.7%, 72.4%, 85.4% and 70.1%, which are 2.7%, 9.0%, 29.1%, 22.8% and 39.2% higher than the second best results (all from RatanaÕs method).

LCLC works much better than the existing methods because it focuses on effectively extracting the positive data P, reliable negative data RN, as well as the likely positive (negative) data LP (LN) from U, so that the resulting classifier is near the optimal positive and negative boundary. On the other hand, both WeiÕs method and RatanaÕs method suffer from the early stopping strategy. As a result, their identified positives are so few that their corresponding negatives still contain a large number of hidden positives that eventually result in bad classifiers.

Recall that the cluster-based feature selection and the cluster-chain approach are two key steps for our LCLC algorithm. To determine their individual effects on our classification performance, we also test the LCLC algorithm without these key steps. The results are shown in Table 3. Without feature selection, LCLC performed poorly on all the datasets: on most of the data the classification performance dropped by 10% in F-measure (except the Yoga dataset which resulted in only a 4.6% drop). To see the effect without cluster chaining, we perform the following procedure: we use P and RN as the positive and negative to train a 1-NN classifier, and use it to extract the ambiguous clusters (AMBI) to construct LP and LN. If an AMBI cluster is closer to P, we will add it into LP; otherwise, it will be added into LN. Similarly, we train the final 1-NN classifier with P+LP as positives and RN+LN as negatives. The results shown in Table 3 show that the corresponding drop in F-measure ranges from 8.6% to 40.4%, depending on the data sets. These results verify that these two innovative LCLC steps played crucial roles for classifying the time series data.

Finally, we evaluate the effect of K, the one parameter of our method which is used as the number of local clusters. In this paper, we have set K = Size(U)/ULC_size, where ULC_size is a predefined number that decides the size of the unlabelled clusters. We repeat our experiments with different values of ULC_size from 10 to 100. Figure 2 shows the sensitivity of LCLC with different values of K. We can see that the parameter ULC_size does not affect the F-measure for all the datasets when ULC_size ranges from 20 to 60.

5 Conclusions

Time series classification is an important data mining task for many real-world applications. Given that it is often tedious and costly to hand-label large amounts of training data, we must consider a setting in which not only the negative training examples are absent, but the number of positive examples available for learning can also be rather limited. There are relatively few existing semi-supervised learning methods for such scenarios. In this work, we have proposed a novel PU technique LCLC that can effectively extract positive and negative data from the unlabelled set U for training robust time series classifiers.

There are three key approaches that underlie LCLCÕs improved classification performance over existing methods. First, LCLC adopts a cluster-based method that is much more robust than current PU learning methods which are typically instance-based and hence more easily prone to noise in the time series data. Secondly, we have adopted a feature selection strategy that can take the characteristics of both positive and unlabelled clusters into consideration and thus enable LCLC to evaluate the similarities between the clusters/examples much more accurately. Finally, we have devised a novel cluster chaining approach to extract the boundary positive and negative clusters. All these approaches were important in facilitating LCLC in building robust classifiers for accurate time series classification, as demonstrated by the superior experimental results over existing methods.

We noticed that the AMBI clusters may contain some noise and uncertainty instances. In our future work, we intend to introduce a probabilistic representation for each ambiguous instance to increase the effectiveness of extracting LP and LN from these AMBI clusters.

Acknowledgement: We thank Eamonn and Wei gracefully share the datasets for our experimental evaluation.