# I want to formulate mathematically the k-nn, objective function and neighborhood

Summary : I need help to write the mathematical formulation of the objective function of knn and relate it to the neighborhood definition. The definition should encorporate the demonstration of the online evaluation objective and optionally the formulation of additional hashing algorithms (eg ScanNN).

Problem: Given distance of choice eg minkowski: $$d(\hat{x}, {x})$$ The neighborhood of $$k$$ samples for the new sample $$\hat{x}$$, can be defined as $$N_k(\hat{x}, \{x\})$$. I want to express the creation of this neighborhood set as a function of the distance. But I am not sure how one can "create a set" in mathematics language.

This is what I have so far :

What about the following for a list of points $$P = (p_1, \ldots, p_n)$$:
Let $$d_i = ||x-p_i||$$. Then the kNN neighbors of $$x$$ are $$\mbox{kNN}(x) = \{ p\in P \mbox{ with } ||p-x|| \leq rank_k(d_1,\ldots,d_n)\}$$ where $$rank_k$$ means the $$k$$-th element in the ordered list (nth_element in C++ STL lingo).
• $rank_k$ means the k-th element in the ordered list. It is not necessary, though, to actually order the entire list (an $O(n\log n)$ algorithm) to obtain the k-th element. It is possible to compute the k-th element in $O(n)$ runtime: such an efficient implementation is readily available in the C++ STL algorithm nth_element: geeksforgeeks.org/stdnth_element-in-cpp Jan 26, 2021 at 15:17