Weighted k-NN

The Weighted k-NN algorithm is an extension of the standard k-NN algorithm. Instead of treating all k neighbors equally, it assigns weights to neighbors based on their distance from the test instance.

The idea is:

• Closer neighbors have higher weight.
• Farther neighbors have lower weight.
• This helps in making more accurate predictions, especially when neighbors are unevenly distributed.

Weights are inversely proportional to the distance between the test instance and the training instance.

---

Algorithm 4.2: Weighted k-NN

Inputs: Training dataset T, Distance metric d, Weighting function w(i), Test instance t, Number of neighbors k

Output: Predicted class or category

Prediction Steps:

1. Compute distances: For each instance iii in dataset T, compute the distance between the test instance t and instance i using:
   • Euclidean Distance for continuous values:

1. Hamming Distance for binary (categorical) values.
2. Sort distances and choose the k nearest neighbors.
3. Apply weighted voting:
   • Compute inverse distance for each of the k neighbors.
   • Find the sum of all inverse distances.
   • Divide each inverse distance by the total sum to get the weight.
   • Add the weights class-wise.
   • Predict the class with the maximum total weight.

---

Weighted k-NN on Student Dataset

Given a test instance: (7.6, 60, 8)
We are to classify it using Weighted k-NN with k = 3

---

Step 1: Distance Calculation (using Euclidean)

Sl.No	CGPA	Assessment	Project	Result	Euclidean Distance
1	9.2	85	8	Pass	25.05115
2	8.0	80	7	Pass	20.02898
3	8.5	81	8	Pass	21.01928
4	6.0	45	5	Fail	15.38051
5	6.5	50	4	Fail	10.82636
6	8.2	72	7	Pass	12.05653
7	5.8	38	5	Fail	22.27644
8	8.9	91	9	Pass	31.04336

---

Step 2: Select 3 Nearest Neighbors

Instance	Euclidean Distance	Class
5	10.82636	Fail
6	12.05653	Pass
4	15.38051	Fail

---

Step 3: Compute Weights by Inverse Distance

Table: Inverse Distance

Instance	Euclidean Distance	Inverse Distance	Class
4	15.38051	0.06502	Fail
5	10.82636	0.09237	Fail
6	12.05653	0.08294	Pass

Sum of Inverses: 0.06502+0.09237+0.08294=0.24033

---

Step 4: Calculate Weights

Table: Final Weight Calculation

Instance	Inverse Distance	Weight = Inverse/Sum	Class
4	0.06502	0.270545	Fail
5	0.09237	0.384347	Fail
6	0.08294	0.345109	Pass

---

Step 5: Class Prediction

• Total weight for Fail = 0.270545 + 0.384347 = 0.654892
• Total weight for Pass = 0.345109

Since Fail has higher total weight →
Predicted class: ‘Fail’

---

The test instance (7.6, 60, 8) is classified as ‘Fail’ using the Weighted k-NN method.