Using KNN (with contributing weights) to calculate ranking

Question

Sorry about the noob question, we tried looking through the answers but couldn't make sense of it. We are very basic with our math/stat knowledge, so please bear with us if this makes less relevant sense.

We have a data set - For example sake - scores (out of 100) in N Subjects for 800 students.

We have to find most suitable candidates (in descending order) for several Customized Courses.

Each Custom Course is a collection of 2 to N Subjects. For example:

Custom Course A could be Maths, Eng, Phys, History

Custom Course B could be Eng, Geography, Computers. Stats

Custom Course C could be History, Geography, Civil. Stats

Now, in our limited understanding and researching a solution so far - we have come down to using a simple KNN routine where we use it to find the eucledian distance between an imaginary value (with 100 for all dimensions) and actual score values. That ways we get a list of most suitable candidates in descending order - on the basis of increasing Eucledian distances.

Eg:

Custom Course A: We try and find nearest neighbors to (100,100,100,100) for Math, Eng, Physics, History with actual scores of 800 students : (35, 44, 32, 86), (19,74,63,82) and so on..

This seems to work fine for us, although we're not sure if we're using this right.

Now, the actual problem is that all subject scores for a Custom Course do not contribute equally. They are weighted. Each subject score has a weightage (1 to 5, 1 being least important and 5 being most important).

We began looking at Weighted KNN algorithms but haven't been able to figure out how to implement this. Any help would be greatly appreciated. The whole KNN approach itself might be totally wrong for us, in which case do say.

Thanks

Answer 1

I reproduced my answer in a Jupyter Notebook - Go and check it out!

First Impressions

Hello, This over a year old but I hope this might still be useful.

If I understand correctly, you want an algorithm to rank your 800 student in terms of their suitability for a specific course, based upon their achievements in the subjects that comprise the course.

Now, normally this is tricky because there are multiple measures: how do you compare someone who gets 79 in history and 41 in maths with someone who gets 65 in history and 62 in maths? Summing the points and comparing (ie. student b has 127pts vs 120pts for student a) gives implicit equal weighting to both measures and this is problem that comes up in multi-objective/pareto optimisation. I can write more detail about this if you're interested, but you've already decided on weights! Great - that makes this task very simple.

The suitability of a student for a given course with defined weights can be found easily: multiply each subject score of the student by the corresponding weight (which should be 0 is the subject is not considered) and sum the results. Once this has been done for all students, you can sort them according to this suitability, and viola, you are done.

Code

I will use python.

import numpy as np    # Use numpy for mathematical operations

students = load(file) 

I assume here that students is an array with 800 rows and N+1 columns. Each row represents a student and the first column is the student id, and the remain N columns are the student's grades. eg with 8 subjects, students looks like this:

[[ 0 38 26 13 60 95 58 72 44]
 [ 1 32 63 62 66  1 16 43 91]
 [ 2 97 60  4  9 53 21  9 96]
 [ 3 56 56 51 34 69 37 96 77]
 [ 4 50 76 56 55 40 32 29 11]
 [ 5 35 30 75 81 97 23 38 19]
 [ 6 57 45 96 35  4 72 11 36]
 [ 7 69 46 95 24 73 56 95  5]
 [ 8 45 91 59 24  7 30 82 84]
 .
 .
 .
 [ 799 24 88 75 96 82 60  7 27]]

Back to the code:

def rank(students, course_weights):
    ids = students[:,0]    # Get a vector of student ids
    grades = students[:, 1:]    # Get just the grades by themselves in a matrix
    scores = grades@course_weights    # matrix multiplication as of python 3.5
    I = scores.argsort()[::-1]    # sort by suitability in descending order
    return ids[I]

course_A_weights = [0,1,0,4,3,2,0,5]

most_suitable_for_A = rank(students, course_A_weights)

most_suitable_for_A is a list of student ids in descending order of the most suitable for the custom course A, as defined by the weights.

Alternatively

What you want to do is, given a student's grades and several optional custom courses, you want to find the most suitable custom course for the student. In which case, we can define a function that takes a student's grades and a matrix of course weights:

def most_suitable(student, courses):
    # Evaluate suitability of student for each course
    scores = courses@student[1:]
    I = scores.argsort()[::-1]
    return I

student = [1112, 789, 56, 64, 38, 41, 15, 25, 32]
courses = np.array([[5,3,4,0,2,1,0,0],
                        [0,1,0,4,3,2,0,5]])

best_courses = most_suitable(student, courses)

What you might use KNN for

The above isn't KNN. What KNN is used for is predicting the classification of observations. If you received the transcript for a new student and wanted to predict which custom course they might choose, you might be able to use KNN to do that.

Final Words

In my opinion, what would be interesting is if you look at clustering the students. There are some simple and effective clustering algorithms: agglomerative such as single and complete linkage, and centroid based, such as k-means. You could feed these algorithms your student data and see if there are any patterns, such as students who do well at mathematics also doing well at history. Then you could tailor your custom course to the clusters that you find in the data for instance doing a maths-history combo custom course if you find it's a common dual specialism.