Build a binary classifier with only positive and unlabeled data

Question

I have 2 datasets, one with positive instances of what I would like to detect, and one with unlabeled instances. What methods can I use ?

As an example, suppose we want to understand detect spam email based on a few structured email characteristics. We have one dataset of 10000 spam emails, and one dataset of 100000 emails for which we don't know whether they are spam or not.

How can we tackle this problem (without labeling manually any of the unlabeled data) ?

What can we do if we have additional information about the proportion of spam in the unlabeled data (i.e. what if we estimate that between 20-40% of the 100000 unlabeled emails are spam) ?

Answer 1

My suggestion would be to attempt to build some kind of clustering on your unlabeled data that somewhat approximates a labelled dataset. The rationale is more or less as follows:

• You have some feature vector for representing your documents
• Based on that feature vector, you can come up with a number of different clusterings, with either fuzzy, rough, or class-based clustering methods
• Knowing what a positive example looks like, you can quickly evaluate the overall similarity of a cluster to your positive cluster
• Knowing that there should really only be two clusters, you can adjust the hyperparameters on your clustering method so that the above two metrics are closer and closer to satisfaction
• With the two clusters, you have what is likely a close approximation of a labelled dataset, which you can then use as a silver-standard corpus of sorts to actually train your model

Hope that makes sense, if you're specifically looking for clustering algorithms, a few that I personally enjoy that might be good in this scenario are FLAME and tsne. Alternately, looking at the spectacular gensim library in python will get you a long way toward the clustering you're looking for.

Hope that helps and makes sense, leave a comment if you've got any questions.

Answer 2

Your problem belongs to the framework of PU learning (only positives, a lot of unlabelled).

It is also close to the more common frameworks of Semi supervised learning (few positives and negatives, a lot of unlabeled).

There are many survey papers that you can look up on the field.

A classical method in the field, that was also tested on spam as in your case, is co-training In co training you build two independent learners (e.g, one based on the mail content and one based on the sending scheme) and you use the results of one of the to train the other and vice versa.

Answer 3

Train 2 generative models, one for each dataset (spam only, spam plus ham), that will give you the probability that a datapoint is drawn from the same probability distribution of the training data. Assign emails as spam or ham based on which model gives you the highest probability of the document arising from the training data used to train it. Example generative models are RBM's, autoencoders (in that case, which model has the lowest reconstruction error). There are likely some bayesian generative models also that will assign a probability to a data point based on some training data.

The best option though would be to take time to curate a second dataset containing only ham. That will give you higher classification accuracy. Assuming a lower proportion of spam to ham emails, that should not be too hard. You can even use Mechanical Turk if you lack the time or resources (or interns \ graduates students or other cheap labor).