I am able to visualize how KNN works. Essentially take avg of the k nearest train neighbors for regression problem.
However every ML algorithm optimizes a cost/loss function for example: Linear regression minimize MSE and Logistic regression minimize logloss
Similarly what is the cost function of KNN? How is it optimized?
From scikit-learn documentation I see the below algorithm options for K nearest neighbors algorithm : {‘ball_tree’, ‘kd_tree’, ‘brute’}
How does these algorithm works?
Specification of a loss function is not sufficient to describe a machine learning algorithm, you also must describe the allowable shapes of the prediction surface.
By prediction surface, I mean the graph of the function
$$ x \mapsto \text{predicted_value}(x) $$
So, for example, for logistic regression the prediction surface is the graph of a function like:
$$ f(x) = \frac{1}{1 + e^{(\beta_0 + \beta_1 x + \cdots \beta_k x_k)}} $$
and for a decision tree the prediction surface is a piecewise constant function, where the region's on which the prediction function is constant are rectangles parallel to the coordinate axis.
For KNN the prediction surface is chosen to be constant on Voronoi cells, the polyhedral regions that are defined by the KNN condition. I.e., a region is all the points whose K-nearest neighbours are some K training data points. This decision is made outside the context of a loss function, it depends instead on the specification of a distance metric.
Within each Voronoi cell the choice of a loss function can guide how one should calculate the predicted value. For example, the mean squared error loss would compel us to choose the mean of all the K-nearest training data points, and the log-loss (in the case of classification) would compel us to choose the proportion of K-nearest data points labeled with the positive class.
This is the same situation as decision trees, where the choice of a loss function leads to a way to calculate a predicted value in the terminal nodes of the tree based on all the training data points that reside in that terminal node.
Sorry, the following is only correct if $k=1$.
In kNNs, as in many others ML models, indeed a loss function is minimised. Say we have data $(x_i, y_i)_{i=1}^I$, where $x_i$ are the vectors of independent variables and $y_i$ contains the class of $x_i$. The kNN constructs a function $f$, such that $\mathrm{Loss}(f(x_i),y_i,i=1,...,I)$ is minimised. In this case, any loss function can be taken that is always positive and that is zero if and only if $f(x_i)=y_i, i=1,...,I$.
Any can be taken means, the results would be equivalent for any of them. However, as opposed to linear or logistic regression, the function $f$ cannot be fully described by the $\mathrm{Loss}()$ function, since it also depends on the distance function that you choose to determine the neighbours.
The kNN algorithm does not have a loss function during training. In the sense that no parameters are minimized during training.
But that said you could write a formulation of kNN since like all stats algorithm it is explicitly or implicitly minimizing some objective, even if there are no parameters or hyperparameters, and even if the minimization is not done iteratively. The kNN is so simple that one does not typically think of it like this, but you can actually write down an explicit objective function:
$$ \hat{t} = \text{argmax}_\mathcal{C} \sum_{i: x_i \in N_k(\{x\}, \hat{x})} \delta(t_i, \mathcal{C}) $$
See Does KNN have a loss function? for more details.
