Sample selection algorithms to ensure that training & validation sets are representative Currently, I am encountering a question, which is how to selection representative samples (training set and test set, even validation set) from the whole data set? I would like build a classification model using a training set and adjust the parameters using a validation set, and at last do prediction to the external test set which is not used to build model (in practice, some unseen data without labels).
Usually, some common methods are cross-validation, hold-out, etc. Random split methods can deal with the problem. But, when further data points do not fall in the model domain, the prediction will be not reliable. So instead of randomly splitting into training and test sets, are there split methods based on the independent variables (X), other than the Kennard-Stone algorithm? Or are there any algorithms can do these things reasonably? (These algorithms should consider the sample distribution between training and test set.)
 A: If you want to go this route, you will need to consider the structure within your data in deciding which instances to use at some point (e.g. build a model). 
One way to do this would be clustering your data and then using some instances from every cluster (depending on its size). If the clustering method and the classification method are related (for example both kernel-based), you are probably implicitly causing information leaks in the sampling approach. Ofcourse, the clustering method you choose essentially imposes a lot of assumptions so whether or not this beats random is very much the question.
Personally, I prefer randomized approaches: few assumptions and they never failed me yet in practice.
A: It seems to me that you are thinking about making and using a single partition of your data for training and validating your model.  It is true that the ability of cross-validation to yield a good model can depend on the quality of the partition, and that a random partition can be poor.  I would still use random partitions as @MarcClaesen suggests, but try doing many of them and averaging over them.  With enough iterations, the process should work quite well, even if there is no guarantee any individual partition was perfectly representative.  
A: You did not specify your sample size and distribution of $Y$.  Depending on that, the size may be insufficient for reliably doing any splitting method other than 100 repeats of 10-fold cross-validation.  The bootstrap may be your best bet unless the total sample size is huge.  And what makes you choose a classification method or a prediction method?  No matter what you do, avoid at all costs the use of improper accuracy scoring rules such as the proportion 'classified' correctly.  This throws out much of the information in your sample.
A: I typically also use the randomized approaches. That being said, depending on your application/data structure and accessibility of cases it may be worth while to look at additional splits that give you an idea about the ability to extrapolate to cases outside the training domain. 
My reasoning behind this is that IMHO you can use your model for whatever data domain (theoretically independent of training domain - in practice it will often be closely related to the training domain) as long as you can demonstrate that the predictive ability is good enough for that domain. 
I'm chemometrician, so I'll formulate some chemistry-related example scenarios.


*

*Consider process analysis. You may receive both data from typical batches and untypical batches. In this scenario it would be important to measure the performance both for unknown typical and unknown untypical batches (separately). Maybe even the performance for untypical batches if the model is trained on typical batches only. 

*Consider a medical diagnostic problem, and data for a number of patients. Typically, you'd randomize patients. However, you may in addition look at the performance for test patients which are in addition extreme according to some other parameters (features). E.g. assume one of your features is blood glucose. It may be worth while to test unknown patients with unusual (high/low) blood glucose. 

*If you are into QSAR (quantitative structure activity relationship) models, consider testing the performance not only with unknown substances but for unknown substance classes.

*and so on
Note that you can also do this by clustering your data and then doing a leave-cluster-out validation. 
