What are good criteria for performance evaluation of algorithms in a regression problem? I'm classifying different algorithms on the wine quality dataset. The quality ranges from between 0 - 10 based on 11 other attributes. Here is the data. 
I'm treating this as a regression problem. 
When I run the Decision tree algorithm (w/ a 10 fold cross validation) and confidence factor of 0.5 on the dataset I get the following output:
Correctly Classified Instances        3808               58.6117 %
Incorrectly Classified Instances      2689               41.3883 %
Kappa statistic                          0.3808
Mean absolute error                      0.0787
Root mean squared error                  0.2562
Relative absolute error                 64.3868 %
Root relative squared error            103.6923 %
Total Number of Instances             6497  

When I run the same thing with confidence factor of 0.125 I get the following output
Correctly Classified Instances        3790               58.3346 %
Incorrectly Classified Instances      2707               41.6654 %
Kappa statistic                          0.3722
Mean absolute error                      0.0817
Root mean squared error                  0.253 
Relative absolute error                 66.8975 %
Root relative squared error            102.4069 %
Total Number of Instances             6497   

Questions


*

*What should I be using to evaluate the performance of the algorithm? RMSE? or Correctly classified instances?

*What if I was comparing output of different algorithms? e.g. Decision Tree vs. KNN..etc.

*What if the problem for classification and not regression?

 A: First of all, there may be some confusion wrt terminology here. Decision trees are classification routines, despite being commonly known as CART models (or classification and regression trees) and, as such, they aren't truly regression models (I'm sure someone will take issue with this statement. No problem), particularly since they are non-parametric and distribution-free techniques. 
That said, the kinds of performance metrics possible can differ between regression models and decision trees but the fundamental issues being addressed do not change. Ever since the late, great Leo Breiman in the 90s (author of the original book about CART), the statistical industry has enshrined optimizing predictive accuracy (PA, alternatively, minimizing the mean squared error) as the gold standard metric for performance evaluation and model validation. 
That PA has evolved to this status is understandable: it’s easily calibrated and for the most part is a consistent statistic for internal model validation. However, all too often it is the sole criterion for model value, without thought given to wider business impact, and despite its being prone to p-hacking, gaming, and analyst fraud.
The 2008 Netflix Prize provides an object lesson in these challenges. Netflix offered a reward to any statistician or team able to improve upon the MSE of their recommender system The eventual winners used a complex ensemble of 107 different models. As Netflix learned however, the real problem was that, from a fully loaded cost perspective, the actual improvement over their incumbent model was a 0.005% reduction in the real 5 point rating scale. Moreover the IT costs in maintaining this ensemble of 107 models more than nullified any gains from the error reduction. Netflix abandoned the pursuit of MSE and no more Netflix Prizes have been awarded. 
Regardless, other competitions – e.g., Kaggle, Crowdanalytix – have enshrined PA. However, to be fair, the era of crowd-sourcing problems as data-mining contests was brand new when NetFlix launched it. The organizers and sponsors of such events are now learning to be more careful in how they pose the problem and data-mining contests are evolving towards more practical and more usable solutions. This year or next, we may see contests where using a designated AWS sand-box (or equivalent) will be part of the scoring. "The official provisioned contest virtual-server will be 8-CPUs rated at XXXX MHz and with 128-GB of RAM. Solutions that run more than 4 hours will be penalized 10% per hour (pro-rated) for excess run-time. Solutions that run more than 10 hours, or that fail due to exceeding available resources, will be disqualified." But this hasn't happened yet.
My real point is that PA is not the only metric for model validation. Should the analyst be willing to sacrifice some PA by factoring in other considerations? Which combination of possible metrics will satisfy constraints wrt PA and derive the strongest strategic insights and confidence in the predictions in the face of truly out-of-sample information and the uncertainty inherent in all future projections? 
Integration With Business Financials
Among applied analysts, having domain expertise and a general sense of how their business makes money can result in much greater alignment between purely statistical considerations such as PA and strategic objectives. These insights, as Netflix shows, are not always obvious. Recent articles in the strategic mgmt literature point to PA as a red herring that can be misleading, particularly with respect to strategic planning under uncertainty.
Descriptive vs Predictive Models
Descriptive models find a reduced set of predictors that provide independent information from one to the next, are intuitively interpretable to lay people for the greatest strategic insights. Pricing models are an example where independence is desirable since the goal is to understand how price alone impacts the outcome. Predictive models, one the other hand, usually optimize PA and are sometimes described as “black boxes” that are opaque or even counter-intuitive to lay understanding.
Model Validation
PA is not unidimensional and the distinctions between internal versus external or truly out-of-sample validation can be lost or blurred:


*

*Historic: PA from a randomly drawn holdout or k-fold cv sample(s) from the same data

*Forecast: assumes the data is in the form of a time series. Validation is between predicted and actual values based on “today’s” observations projected into the future

*Prospective: external validation on truly out-of-sample data, can be an “in-market” experiment achieved by making predictions regarding the future then waiting a period of time to evaluate the model relative to actual events. Software such as Unica can also provide this evidence
Model Stability
Parameter estimates can be notoriously unstable out-of-sample. Given a fixed set of model predictors, how stable are they across fixed, k-fold cv data sets? Also, how stable are the predictors across k-fold cv data based on the variable selection method? Do differing methods provide similar results?
Additional Metrics
Model complexity is usually expressed terms of the number of parameters in a model and relies on measures such as the AIC, BIC or Hannan-Quinn. Other metrics are possible. For instance, metrics exist to assess qualitative aspects of model performance that may not improve PA but can be related to descriptive power. These include Mandelbrot’s D for fractal dimensionality, Hurst’s H exponent for “wild” randomness, entropy, interestingness, conformal confidence, diversity, novelty, etc.
A: Since you used cross-validation, MSE is the error you want to look at because it's the error from your testing set, and approximation of the true testing error. 
If you use other algorithms with cross-validation, MSE is still appropriate. 
You would only want to use an adjustment to MSE--like AIC, BIC, adj. R^2--if you only ran your models on the training set without any sort of validation.
For classification use the error rate, which is the average of $I(y_i \neq \hat{y_i})$. 
Source: "An Introduction to Statistical Learning" by Gareth James
