Similarity-Based Approach for Positive and Unlabeled Learning

1 Introduction

Traditional supervised learning methods require that both the positive and negative examples are available for training. However, in many real-world applications [Fung et al., 2006], it is not easy to obtain the negative examples. For example, in Web page classification, the users may mark their favorite Web pages, but they are unwilling to mark the boring pages that they show no preference. Therefore, the positive and unlabelled learning (PU learning) is studied to deal with the situation where only the positive examples and the unlabelled examples are available in the training phase [Liu et al., 2002].

∗Bo Liu is the corresponding author.

In the PU learning, since the negative examples are unavailable, most of the existing works [Liu et al., 2002; Yu et al., 2004; Li and Liu, 2003; Liu et al., 2003; Li et al., 2009] focus on identifying some reliable negative examples from the unlabelled examples, so that the supervised learning methods can be applied to build the classifier. However, there may exist a number of unlabelled examples which can not be explicitly identified as positive or reliable negative (we call them ambiguous examples here). Compared to the examples which can be clearly classified to be positive or negative, the ambiguous examples are more likely to lie near the decision boundary and play a critical role in building the classifier. Therefore, it is essential to appropriately deal with the ambiguous examples in order to learn an accurate classifier.

Considering the existing PU learning works, different strategies have been proposed to deal with the ambiguous examples. Since the labels of ambiguous examples are difficult to be determined, one group of works [Liu et al., 2002; Yu et al., 2004; Li and Liu, 2003; Liu et al., 2003] excludes the ambiguous examples from the learning phase, and the classifier is trained by using only the positive and some negative examples. For example, Spy-EM (Spy Expectation Maximization) [Liu et al., 2002] uses a spy technique to identify some reliable negative examples from the unlabelled examples, and then EM is run to build the classifier by using the positive examples and the extracted negative examples. However, the classification ability of these methods may be limited, since the ambiguous examples, which can contribute to the classifier construction, are excluded from the learning process.

Another group of works includes the ambiguous examples in learning the classifier by straightforwardly assigning them to the positive class or the negative class. For example, in LELC [Li et al., 2009], the ambiguous examples are clustered into micro-clusters. For each micro-cluster, the distances from its examples to the positive prototypes and the identified negative prototypes are calculated. Based on a voting strategy, the micro-cluster (including all its examples) is assigned to the class which the micro-cluster is closer to. By considering the ambiguous examples, LELC performs better than other PU learning methods [Li et al., 2009]. However, in LELC, there may exist some micro-clusters, in which some examples are biased towards the positive class, while the others are closer to the negative class. In such case, if we simply enforce the whole micro-cluster of examples to any of the two classes, misclassification may be incurred.

In this paper, we propose a novel approach, called similarity-based PU learning (SPUL), by utilizing the ambiguous examples as an effective way to improve the PU learning classification accuracy. Instead of eliminating the ambiguous examples from the learning phase or enforcing the ambiguous examples directly to one class, our proposed approach explicitly deals with the ambiguous examples by considering their similarity towards both of the positive class and the negative class. Specifically, our proposed approach works in three steps. In the first step, we extract reliable negative examples from the unlabelled data and build the representative positive and negative prototypes. In the second step, we cluster the remaining unlabelled examples into micro-clusters and assign each example with two similarity weights, which indicate the similarity of an ambiguous example towards the positive class and the negative class, respectively. To do this, the local similarity-based and global similarity-based mechanisms are proposed to generate the similarity weights. In the third step, we extend the standard support vector machine (SVM) to incorporate the ambiguous examples with their similarity weights into a learning phase, such that the ambiguous examples can contribute differently on the classifier construction based on their similarity weights. Extensive experiments have been conducted to investigate the performance of SPUL and the statistical results show that SPUL outperforms state-of-the-art PU learning methods.

2 RelatedWork

2.1 Positive and Unlabelled Learning

In recent years, the PU learning has found various applications in text mining due to the fact that collecting a large set of negative documents is always expensive and challenging [Li et al., 2007; Liu et al., 2002; Yu et al., 2004; Lee and Liu, 2003; Li and Liu, 2003; Liu et al., 2003; Zhou et al., 2010; Scholkopf et al., 2001]. We briefly review the existing works on PU learning in the following.

The first group of works [Liu et al., 2002; Yu et al., 2004; Li and Liu, 2003; Liu et al., 2003] adopts an iterative framework to extract the negative examples from the unlabelled examples, and train the classifier alternatively. For example, Spy-EM (Spy Expectation Maximization) [Liu et al., 2002] uses a Spy technique to extract the negative examples, and EM algorithm is used to train the classifier iteratively. RocSVM (Rocchio-Support Vector Machine) [Li and Liu, 2003] extracts the reliable negative examples by using the information retrieval technique Rocchio [Rocchio, 1971]. In this category, except for positive examples and the extracted examples, the rest ambiguous examples are excluded from the training process. Therefore, the performance may be limited.

The second group of work does not include the iterative framework. For example, one-class classification method [Scholkopf et al., 2001] is proposed to build an one-class classifier by using only the positive examples. Since the unlabelled data information is not considered, the one-class classifier is always inferior to the binary classification-based methods [Li and Liu, 2003]. Another example is LELC [Li et al.,

2009]. LELC clusters the ambiguous examples into microclusters, and then assigns a whole micro-cluster of examples to the class which the micro-cluster is closer to. However, there may be some micro-clusters in which some examples are biased to the positive class and the other examples are closer to the negative class. In such case, enforcing the microcluster to any of the two classes may lead to misclassification.

In this paper, we propose a similarity-based PU learning method. Compared to the works in the first group, our proposed method explicitly incorporates the ambiguous examples to improve the classification accuracy of PU learning. Furthermore, rather than enforcing the ambiguous examples to either class, as some of the second group's works do, we incorporate the ambiguous examples in the training by measuring their similarity to the positive class and the negative class, such that the classification boundary can be refined based on the similarity information.

2.2 Support Vector Machine

SVM [Vapnik, 1998] has been proven to be a powerful classification tool. We briefly review SVM as follows.

Let S = {(x1, y1), (x2, y2), . . . , (x|S|, y|S|)} be a training set, where xi ∈ Rd and yi ∈ {+1, -1}. SVM aims at seeking an optimal separating hyperplane w · φ(x) + b = 0, where φ(x) is the image of example x in the feature space. The optimal separating hyperplane can be obtained by solving the following optimization function:

where ξi are variables to relax the margin constraints, and C is a parameter to balance the classification errors. By introducing the Lagrange function [Vapnik, 1998], the decision classifier can be obtained. For a test example x, if w · φ(x) + b > 0, it is classified into the positive class; otherwise, it is negative.

In the following, we will extend SVM to incorporate the examples with similarity weights into a learning phase, such that the ambiguous examples can contribute differently to the classifier construction.

3 Preliminary

Let S be a training set of a PU learning problem. Assume that PS and US store the positive examples and the unlabelled examples, respectively. Hence, we have S = PS ∪ US.

For the ambiguous examples, since we do not know which class it should belong to, we represent an ambiguous example x using a similarity-based data model:

where m+(x) and m-(x) are similarity weights which represent the similarity of x towards the positive class and the negative class, respectively. We have 0 ≤ m+(x) ≤ 1 and 0 ≤ m-(x) ≤ 1. {x, (1, 0)} means that x is positive, while {x, (0, 1)} indicates that x is identified to be negative. For {x, (m+(x), m-(x))}, where 0 < m+(x) < 1 and

0 < m-(x) < 1, it implies that the similarity of x towards the positive class and the negative class is both considered.

By using the similarity-based data model, we can generate similarity weights for the ambiguous examples based on the positive and extracted negative examples. These ambiguous examples and their similarity weights are thereafter incorporated into an SVM-based learning model.

4 Similarity-Based PU Learning Approach

In this section, we will introduce the proposed approach in details. The PU learning aims at constructing a classifier by using the positive examples and the unlabelled examples. It has been found various applications in text mining area. Based on the similarity-based data model introduced in Section 3, our proposed SPUL approach works in the following three steps.

1. In the first step, we extract the reliable negative examples and build the representative positive and negative prototypes.
2. In the second step, we cluster the remaining unlabelled data (ambiguous examples) into micro-clusters and assign similarity weights to the ambiguous examples. The local similarity-based and global similarity-based mechanisms are proposed to generate the similarity weights.
3. In the third step, we extend the standard SVM to incorporate the ambiguous examples and their similarity weights into the learning phase to build a more accurate classifier.

In the following, we present the detailed information of the above three steps.

4.1 Step 1: Negative Example Extraction

In the first step, we extract the reliable negative examples and put them in subset NS. Together with the positive examples, those negative examples are used to set up the representative positive prototypes and negative prototypes.

First of all, we extract the reliable negative examples from the unlabelled data. As LELC, we integrate the Spy technique [Liu et al., 2002] and the Rocchio technique [Li and Liu, 2003] to extract the most reliable negative examples. Let subsets S1 and S2 contain the corresponding reliable negative examples extracted by the Spy technique and the Rocchio technique. Examples are classified as reliable negative only if both techniques agree that they are negative. That is, NS = S1 ∩ S2, where subset NS contains the reliable negative examples. After the reliable negative examples are determined, we get rid of them from the unlabelled data subset, i.e., US = US - NS.

Furthermore, the representative positive prototypes and the representative negative prototypes are then set up by clustering the reliable negative examples into microclusters. Specifically, K-mean clustering is used to cluster the examples in NS into m micro-clusters, denoted as NS1, NS2, . . . , NSm where m = t ∗ |NS|/(|US| + |NS|) and t is set to be 30 in the experiments, as recommended in [Buckley et al., 1994; Li et al., 2009]. Then, the kth representative positive prototype, denoted as pk , and the kth representative negative prototype, denoted as nk, are built as follows:

where ‖ x ‖ represents the norm of example x; parameters α and β are set to be 16 and 4, respectively, as recommended in [Buckley et al., 1994; Li et al., 2009].

After Step 1, we obtain the reliable negative examples in NS, m representative positive prototypes pk and m representative negative prototypes nk.

4.2 Step 2: Similarity Weight Generation

In this step, we aim at creating two similarity weights m+(x) and m-(x) for the examples in subset US, such that the ambiguous examples can be incorporated into the training phase by considering their similarity to the positive class and the negative class. Specifically, we first cluster the examples in subset US into r micro-clusters, i.e., US1, US2, . . . , USr, where r is set as r = t ∗ |US|/(|US| + |NS|) and again we set t to be 30 in the experiments. Then, the similarity weights m+(xi) and m-(xi) are generated for each example in subsets USi (i = 1, . . . , r). To generate the similarity weights, we put forward the local similarity-based and global similarity-based schemes in the following.

Local Similarity Weight Generation Scheme

In this scheme, we generate the similarity weights by capturing the local data information. For each micro-cluster USj (j = 1, 2, . . . , r), we assume that there are ljp examples similar to the closest positive prototype pk , and ljn examples similar to the closest negative prototype nk. That is, for the ljp examples, we have

where Sim(., .) is calculated as Sim(x, pk ) = x·pk ‖x‖·‖pk ‖ . Similarly, for the ljn examples, we have

Based on the above functions, the similarity weights for ambiguous data in USj are calculated as

Figure 1 presents an example of assigning the similarity weights to ambiguous data. Based on Equations (7) and (8), the examples in micro-clusters 1, 2, 3 and 4 are assigned with weights (1, 0), (0, 1), ( 58 , 38 ) and ( 13 , 23 ), respectively. Distinguished from LELC, which directly assigns a whole microcluster of examples to one class, SPUL allows the ambiguous examples having different weights associated with the positive class and the negative class, such that the similarity of ambiguous examples towards the two classes can be considered. The advantage of the local generation scheme is that it is simple to implement. However, it can not distinguish the difference of examples in the same micro-cluster. The examples from the same micro-cluster have exactly the same weights towards the two classes. In fact, the similarity weights of examples from the same micro-cluster can be different, since they are located physically different.

Global Similarity Weight Generation Scheme

To consider the location of ambiguous examples, we further propose a global generation scheme to assign weights to ambiguous examples.

For the ambiguous example xi in subset US, we first calculate its similarity to each of the representative positive and negative prototypes. That is,

For xi ∈ US, the corresponding weights towards the positive class and the negative class are computed as follows:

The global generation scheme treats each ambiguous example in subset US differently and the weights are calculated based on the locations of examples towards the representative positive and negative prototypes, respectively. As shown in the experiments, the global generation scheme outperforms the local generation scheme.

4.3 Step 3: SVM-Based Classifier Construction

After performing the above two steps, each ambiguous example is assigned two similarity weights: m+(xi) and m-(xi). In the following, we will give a novel formulation of SVM by incorporating the data in positive set PS, negative set NS, ambiguous example set US and the similarity weights into an SVM-based learning model.

Primal Formulation

Since the similarity weights m+(xi) and m-(xi) indicate the different degrees of similarity for an ambiguous example towards the positive class and the negative class, respectively, the optimization function can be formulated as follows:

where C1, C2, C3 and C4 are penalty factors controlling the tradeoff between the hyperplane margin and the errors. ξi, ξj , ξk and ξg are the error terms. m+(xj)ξj and m-(xk)ξk can be considered as errors with different weights. Note that, a smaller value of m+(xi) can reduce the effect of parameter ξi, so that the corresponding example xi becomes less significant towards the positive class.

Dual Problem

Assume that αi, αj, αk and αg are Lagrange multipliers. To simplify the presentation, we redefine some notations in the following:

Based on the above definitions, we let S+ = PS ∪ US, S-= US ∪NS and S∗ = S+ ∪ S-. The Wolfe dual of (13) can be obtained as follows:

where K(xi, xj) is the inner product of φ(xi) and φ(xj).

After solving the problem in (14), w can be obtained in the following:

By using Karush-Kuhn-Tucker conditions (KKT) [Vapnik, 1998], b can be obtained. For a test example, if f(x) = w · φ(x) + b > 0 holds true, it belongs to the positive class. Otherwise, it is negative.

5 Experiment

All the experiments are performed on a laptop with a 2.8 GHz processor and 3GB DRAM.

5.1 Baselines andMetrics

We implement two variants of our proposed method, i.e., local similarity-based PU learning (Local SPUL) and global similarity-based PU learning (Global SPUL). For comparison, another three methods are used as baselines. The first one is Spy-EM [Liu et al., 2002], which uses Spy technique to extract negative examples and utilizes EM to construct the classifier. The second one is Roc-SVM [Li and Liu, 2003], which employs Rocchio method to extract the negative examples and builds an SVM classifier. Both methods exclude the ambiguous examples from the training. The third one is LELC [Li et al., 2009], which clusters the ambiguous examples into micro-clusters and assigns each micro-cluster to either the positive class or the negative class. The third baseline is used to demonstrate the capability of our method in coping with the ambiguous examples.

The performance of text classification is typically evaluated based on F-measure [Liu et al., 2002]. F-measure trades off the precision p and the recall r: F = 2pr r+p . Only when both are large will F-measure exhibit a large value. A desirable algorithm should have a F-measure value closer to one.

5.2 Datasets and Settings

To evaluate the properties of our approaches, we conduct experiments on three real-world datasets:

• Reuters-21578 1 : This dataset contains 21578 documents. Since it is highly skewed, we follow the same operations in [Fung et al., 2006] to select the top 10 largest categories, i.e., "acq", "corn", "crude", "earn", "grain", "interest", "money", "ship", "trade" and "wheat". In all, we have 9981 documents for the experiments.
• 20 Newsgroups 2 : There are 20 sub-categories and each sub-category has 1000 messages. For a fair comparison, we have removed all the UseNet headers, which contain the information of subject lines.
• WebKB 3 : It has 8282 Web pages and 7 categories. The dataset is slightly skewed. The number of Web pages in different categories ranges from 3764 to 137.

For each of the above datasets, we conduct the following operations to obtain sub-datasets for PU learning. We choose a category (a) from a dataset (A), and randomly select g percentage of examples from this category (a) to form a positive example set. The remaining examples in category (a) and the examples from other categories are used to form an unlabelled dataset.

By considering each category as the positive class, we obtain 10 sub-datasets from Reuters-21578, 7 sub-datasets from WebKB and 20 sub-datasets from 20 Newsgroups. In addition, since the sizes of some categories are small, e.g., "corn" category in Reuters-21578 only containing 238 examples, we first set g = 15%, and then investigate the performance of each method when g increases.

1 http://www.daviddlewis.com/resources/testcollections/

2 http://people.csail.mit.edu/jrennie/20Newsgroups/

3 www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-20/www/data

In the experiments, the linear kernel function K(xi, xj) = xi · xj is used, since it generally performs well for text classification [Sebastiani, 2002]. In our Local SPUL and Global SPUL methods, we let C1, C2, C3 and C4 range from 2-5 to 25 . Moreover, t is set to be 30, as recommended in [Li et al., 2009]. For the parameters contained in Spy-EM [Liu et al., 2002], Roc-SVM [Li and Liu, 2003] and LELC [Li et al., 2009], we adopt the settings in their own works.

5.3 Experimental Results

For each generated sub-dataset, we randomly select sixty percent of data to form a training set, and the remaining data forms a testing set. 10-fold cross validation is conducted on the test set. To avoid sampling bias, we repeat the above process for 10 times, and calculate the average F-measure values for each sub-dataset. Since there are thirty two sub-datasets, due to limited space, we only show the average F-measure values on nine sub-datasets, as reported in Table 1. In Table 1, the listed sub-datasets are denoted as "A-a" format, where "A" denotes the original dataset's name, and "a" represents the category which is used as the positive class. Note that, the reported results are all consistent on the other sub-datasets.

As shown in Table 1, both of Global SPUL and Local SPUL outperform the other baselines on the nine subdatasets. This is because our SPUL methods assigns similarity weights to the ambiguous examples, so that the similarity of ambiguous examples to the positive and negative classes can be evaluated and contribute to the classifier construction. In terms of our two variants Global SPUL and Local SPUL, Global SPUL generally performs better than Local SPUL on all the sub-datasets, since the former one generates similarity weights based on the locations of ambiguous samples towards the positive and negative prototypes, but the later one just considers the votes of a micro-cluster towards the positive and negative prototypes.

We further discover that, Spy-EM and Roc-SVM always obtain lower accuracy, since they discard the ambiguous samples from training. Consequently, they are inferior to the other methods. This is consistent with the findings in [Li et al., 2009]. Furthermore, LELC method performs better than Spy-EM and ROC-SVM, but worse than our methods. This is because, though LELC takes the ambiguous samples into learning the classifier, it simply enforces the micro-cluster into either class, and misclassification may be incurred if some of its examples are more biased towards the positive class and the other examples are closer to the negative class.

In the above, we report the detailed results on the nine subdatasets. In the following, the average F-measure values of the sub-datasets from the same dataset are also reported, as shown in Table 2. Here, we can have similar findings to the nine sub-datasets.

Moreover, Figure 2 illustrates the performance of each method on the Reuter-interest sub-dataset when the percentage g of positive examples increases. As shown in Figure 2, when g increases, the F-measure value of each method increases. At the same time, it is observed that our Local SPUL and Global SPUL methods consistently outperform the other baselines.

6 Conclusions and Future Work

This paper proposes a similarity-based PU learning (SPUL) method to handle the ambiguous examples by associating them with two weights which imply the similarity of the ambiguous examples towards the positive class and the negative class, respectively. The local similarity-based and global similarity-based methods are presented to generate the similarity weights for ambiguous examples. We then extend the standard SVM to incorporate the ambiguous examples and their similarity weights into an SVM-based learning phase. Extensive experiments have shown the good performance of our method.

In the future, we plan to exploit an online process to learn the SPUL classifier in the streaming data environment.

Acknowledgments

This work is supported by QCIS Center and Advanced Analytics Institute of UTS, Australian Research Council (DP1096218, DP0988016, LP100200774 and LP0989721), Natural Science Foundation of China (61070033), Natural Science Foundation of Guangdong province (9251009001000005), Science and Technology Planning Project of Guangdong Province (2010B050400011,2010B080701070,2008B080701005), Eleventh Five-year Plan Program of the Philosophy and Social Science of Guangdong Province (08O-01), Opening Project of the State Key Laboratory of Information Security (04-01), China Post-Doctoral First-Class Fund (L1100010) and South China University of Technology Youth Fund (x2zdE5090780).