Deciding how to improve
To improve on this, we basically have the following options:
Add more data: It may be that there is just not enough data for the learning algorithm and that we simply need to add more training data.
Play with the model complexity: It may be that the model is not complex enough or is already too complex. In this case, we could either decrease k so that it would take less nearest neighbors into account and thus would be better at predicting non-smooth data, or we could increase it to achieve the opposite.
Modify the feature space: It may be that we do not have the right set of features. We could, for example, change the scale of our current features or design even more new features. Or rather, we could remove some of our current features in case some features are aliasing others.
Change the model: It may be that kNN is generally not a good fit for our use case, such that it will never be capable of achieving good prediction performance no matter how complex we allow...
