How to construct training set for anomaly detection? I am using a K-Nearest-Neighbor calculation as part of an outlier detection method, and I'm trying to decide how to construct the training dataset on which to base my KNN calculation for subsequent observations. I have too many observations to efficiently include them all in my training set, so I need to decide how to select the subset of observations to include in the training set. What is the best way to make this selection? A random sample? Or should I somehow try to select a subset of the total observations that I believe are more "normal" than others. Would that be a better approach if I am using the KNN calculation as an outlier detection method, or could it bias my results?
 A: *

*It doesn't make that much of a difference if you are using $k$-NN or other algorithm for anomaly detection, how you construct the training set would be the same. The usual anomaly detection setup is to put the "typical" data in the training set and mix of "typical" data and anomalies (labelled) in test set. Based on the training set, the algorithm learns the distribution of the "typical" data, so that it can mark the data that is unlikely under this distribution as anomalies.

*So if you have a reasonable way of finding "normal" samples, use it for splitting the data. If you don't, and you marked some of the data as "normal" and "anomalies" based on some poor heuristic, this could influence your results and make the algorithm learn rather your heuristic than the actual anomalies.

*How you subsample the data would depend on how the data was gathered. For example, if your sample would already be biased, subsampling it randomly wouldn't do anything about the bias. If you have a random, representative sample, you can just subsample randomly. If your data is stratified, you need to consider the stratification when subsampling.

*The size of the data can indeed be a problem when using $k$-NN, did you consider using other anomaly detection algorithms that scale better?

