0
$\begingroup$

Wiki gives this definition of KNN

In pattern recognition, the k-nearest neighbors algorithm (k-NN) is a non-parametric method used for classification and regression. In both cases, the input consists of the k closest training examples in the feature space. The output depends on whether k-NN is used for classification or regression:

  • In k-NN classification, the output is a class membership. An object is classified by a plurality vote of its neighbors, with the object
    being assigned to the class most common among its k nearest neighbors (k is a positive integer, typically small). If k = 1, then the object is simply assigned to the class of that single nearest neighbor.
  • In k-NN regression, the output is the property value for the object. This value is the average of the values of k nearest neighbors.

and this explanation about "The weighted nearest neighbour classifier"

The k-nearest neighbour classifier can be viewed as assigning the k nearest neighbours a weight 1/k and all others 0 weight. This can be generalised to weighted nearest neighbour classifiers. That is, where the ith nearest neighbour is assigned a weight ${\displaystyle > w_{ni}}$, with ${\displaystyle \sum _{i=1}^{n}w_{ni}=1}$. An analogous result on the strong consistency of weighted nearest neighbour classifiers also holds.

this $w_{ni}$ confuses me a lot.

taking the iris dataset as the example, there are 150 data points, if we choose k=50, are there top 50 neighbours, each of which has a 1/50 weight, and the other 100 data points 0 weight.

if it is, $w_i = 1/50$ where $i=1, 2, ..., 50$.

so, what does $w_{ni}$ mean?

Assume $𝑀_{𝑛1}$ represents the nearest neighbor, $𝑀_{𝑛2}$ represents the second nearest neighbor, what does "n" in $𝑀_{𝑛i}$=1/50 mean? Does $𝑀_{11}$mean the first example weights 1/50 to first class, say, Iris Setosa?

$\endgroup$
0
$\begingroup$

In weighted nearest neighbour, all of the points in the dataset have a contribution, which is quantified by $w_{ni}$ in your references. So, in this version, there is no top $k$. Every point in the dataset has a saying on the outcome. And, KNN can also be considered as a special case of weighted NN where $w_{ni}=1/k$ when $1\leq i\leq k$, and $0$ otherwise. In regression, these weights can be directly incorporated to the outcome, i.e. $$\hat{y}=\sum_{i=1}^nw_{ni}y_i$$ But in classification, you'll count votes together with weights, i.e. the cumulative vote for class $m$ is calculated as follows: $$c_m=\sum_{i=1}^nw_{ni}\underbrace{\mathbf{1}[y_i=m]}_{\text{indicator function}}=\sum_{y_i=m}w_{ni}$$ In the end, you'll compare the votes on classes. And, decide the class with the highest vote.

Taking your example, i.e. the iris dataset, and a KNN with $k=50$, we have $w_{ni}=1/50$ for $1\leq i \leq 50$, as you noted. So, the top $50$ nearest neighbors have equal vote on the outcome. Iris dataset has three classes, so you'll calculate $c_1,c_2,c_3$ and choose the one with the highest value.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer! Assume $w_{n1}$ represents the nearest neighbor, $w_{n2}$ represents the second nearest neighbor, what does "n" in $w_{ni}=1/50$ mean? What does $w_{11}$ mean the first example weights 1/50 to first class, say, Iris Setosa? $\endgroup$ – fu DL Aug 18 '19 at 3:22

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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