Currently I am just go through from the min to the max, and determine $k$ by the performance. I am wondering if there's optimization approaches for selecting $k$? I am aware of there's question in this site asking for a practical method for selecting $k$, but I would like to know if there's any optimization strategy works for k-NN? My objective is make it more time efficient.

When I combine k-NN with another approach (with one parameter: ki) for a specific application, I found the objective function seems not smooth with respect to the two parameters: $ki$ and $item Neighborhood size$ ($k$). (See the pic)

How about the following method: I assume there are local maxima values of $k$.

In a case where I have the possible values of k between [1, 1000].

  1. I make a step size $s=$ 20, and then there will be 50 first-round $k$ values = {1, 20, 40,...,1000}. I evaluate them and get the results.
  2. for each first-round $k$ values, I produce 50 second-round $k$ values by adding $s/2==10$. Then I will have second-round $k$ values={$10,30,50,...,900$}. Then I evaluate them and get the results.
  3. I think in this way I can get a rough outline of the relation between performance and parameter $k$, and then next I can determine a most wanted range of $k$, then I can use a much smaller step size $s_2$ to continue the aforementioned process.

Does this method fall into the category of Monte Carlo methods? enter image description here


1 Answer 1


You can use either cross validation(k-fold cross-validation) or brute force using methods such as grid search

See this paper:http://www.cs.cmu.edu/~rahuls/pub/icml2000-rahuls.pdf

and this one on grid search for details: http://www.jmlr.org/papers/volume13/bergstra12a/bergstra12a.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.