How to predict outcome with only positive cases as training? For the sake of simplicity, let's say I'm working on the classic example of spam/not-spam emails.
I have a set of 20000 emails. Of these, I know that 2000 are spam but I don't have any example of not-spam emails. I'd like to predict whether the remaining 18000 are spam or not. Ideally, the outcome I'm looking for is a probability (or a p-value) that the email is spam.
What algorithm(s) can I use to make a sensible prediction in this situation?
At the moment, I'm thinking of a distance-based method that would tell me how similar my email is to a known spam email. What options do I have?
More generally, can I use a supervised learning method, or do I necessarily need to have negative cases in my training set to do that? Am I limited to unsupervised learning approaches? What about semi-supervised methods?
 A: I am assuming there aren't as many spam cases in your 18000 cases. To use a supervised learning approach to this, you need to have more than 1 category/class in your data. Since you know 2000 cases are spam, you can label the remaining 18000 cases as 'unknown category' and train any supervised learning model to predict if a case is in the spam or the unknown category. Then check your out of sample model accuracy to see how well the model performs to distinguish between the 2 categories. If it performs well, then my assumption of few spam cases in the 'unknown' category is warranted.
If it doesn't perform well, then you'll have to use an unsupervised learner(like kmeans, etc) to cluster and identify separate homogenous groups in your data. Then identify which clusters contain the most of the 2000 spam emails, and which ones do not, and label them as spam and non spam respectively. Next, you can proceed with modeling using a supervised learner like I described earlier.
A: This is called learning from positive and unlabeled data, or PU learning for short, and is an active niche of semi-supervised learning.
Briefly, it is important to use the unlabeled data in the learning process as it yields significantly improved models over so-called single-class classifiers that are trained exclusively on known positives. Unlabeled data can be incorporated in several ways, the predominant approaches being the following:


*

*somehow infer a set of likely negatives from the unlabeled data and then train a supervised model to distinguish known positives from these inferred negatives.

*treat the unlabeled set as negative and somehow account for the label noise that is known to be present.


I am active in this field, and rather than summarizing it here for you, I recommend reading two of my papers and the references therein to get an overview of the domain:


*

*A state-of-the-art technique to learn models from positive and unlabeled data (formal publication available here): http://arxiv.org/abs/1402.3144

*A technique to compute commonly used performance metrics without known negatives (under review, this is first of its kind): http://arxiv.org/abs/1504.06837
A: What the OP is talking about is a one-class classification task, which is a very challenging one. 
There are many papers on this task across different research fields. I also wrote one An Efficient Intrinsic Authorship Verification Scheme Based on Ensemble Learning. It is very easy to adapt it in order to classify spam/not spam, rather than authors. Give it a try and let me know if you need further details...
