Last active
June 22, 2019 06:50
-
-
Save ungarson/dbb2c71514e48f3e3d0ca8e91834a4ea to your computer and use it in GitHub Desktop.
k-nearest neighbors in js
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function findMetrics(values) { | |
return Math.hypot(...values); | |
} | |
export function updateWithMetrics(usersVotes) { | |
if (obj(usersVotes).doesntExist()) return null; | |
for (let i = 0, len = usersVotes.length; i < len; i++) { | |
const currentUser = usersVotes[i]; | |
if (currentUser['metrics']) continue; | |
else usersVotes[i]['metrics'] = findMetrics(currentUser['votes']); | |
} | |
} | |
export function kNearestNeighbors(usersVotes, target, amount) { | |
if (obj(target).doesntExist() || obj(usersVotes).doesntExist()) return null; | |
if (someKeys('votes', 'name', 'id').dontExistIn(target)) return null; | |
let biggestDistanceInStack = Infinity; | |
let smallestDistanceInStack = 0; | |
let stackOfNeighbors = []; | |
for (let i = 0, len = usersVotes.length; i < len; i++) { | |
const currentUser = usersVotes[i]; | |
if (currentUser['id'] === target['id']) continue; | |
const distanceBetweenTargetAndCurrentUser = Math.abs(target['metrics'] - currentUser['metrics']); | |
if (typeof(stackOfNeighbors[0]) === "undefined") { | |
stackOfNeighbors.push(currentUser); | |
smallestDistanceInStack = distanceBetweenTargetAndCurrentUser; | |
continue; | |
} | |
if (typeof(stackOfNeighbors[amount - 1]) === "undefined") { | |
stackOfNeighbors.push(currentUser); | |
if (distanceBetweenTargetAndCurrentUser < biggestDistanceInStack | |
&& distanceBetweenTargetAndCurrentUser > smallestDistanceInStack) { | |
biggestDistanceInStack = distanceBetweenTargetAndCurrentUser; | |
} else if (distanceBetweenTargetAndCurrentUser < smallestDistanceInStack) { | |
if (biggestDistanceInStack === Infinity) biggestDistanceInStack = distanceBetweenTargetAndCurrentUser; | |
smallestDistanceInStack = distanceBetweenTargetAndCurrentUser; | |
} | |
continue; | |
} | |
stackOfNeighbors.sort((a,b) => { | |
return Math.abs(target['metrics'] - a['metrics']) - Math.abs(target['metrics'] - b['metrics']); | |
}) | |
if (distanceBetweenTargetAndCurrentUser < biggestDistanceInStack | |
&& distanceBetweenTargetAndCurrentUser > smallestDistanceInStack) { | |
biggestDistanceInStack = distanceBetweenTargetAndCurrentUser; | |
stackOfNeighbors.pop(); | |
stackOfNeighbors.push(currentUser); | |
} else if (distanceBetweenTargetAndCurrentUser < smallestDistanceInStack) { | |
if (biggestDistanceInStack === Infinity) biggestDistanceInStack = distanceBetweenTargetAndCurrentUser; | |
smallestDistanceInStack = distanceBetweenTargetAndCurrentUser; | |
stackOfNeighbors.shift(); | |
stackOfNeighbors.push(currentUser); | |
} else if (distanceBetweenTargetAndCurrentUser < biggestDistanceInStack) { | |
stackOfNeighbors.pop(); | |
stackOfNeighbors.push(currentUser); | |
biggestDistanceInStack = distanceBetweenTargetAndCurrentUser; | |
} | |
} | |
return stackOfNeighbors; | |
} | |
function someKeys(...objKeys) { | |
return { | |
dontExistIn(obj) { | |
for (let i = 0, len = objKeys.length; i < len; i++) { | |
if (!obj[objKeys[i]]) return true; | |
} | |
} | |
} | |
} | |
function obj(objName) { | |
return { | |
doesntExist() { | |
return typeof objName !== "object"; | |
} | |
} | |
} | |
// Example of usage | |
// const usersVotes = [ | |
// { | |
// votes: [0, 0, 5, 5, 3], | |
// name: 'Michael', | |
// id: 0 | |
// }, | |
// { | |
// votes: [1, 1, 1, 1, 1], | |
// name: 'Ulf', | |
// id: 1 | |
// }, | |
// { | |
// votes: [5, 5, 5, 5, 5], | |
// name: 'Juliette', | |
// id: 2 | |
// }, | |
// { | |
// votes: [2, 3, 1, 5, 2], | |
// name: 'Aurelie', | |
// id: 3 | |
// }, | |
// { | |
// votes: [4, 4, 0, 4, 5], | |
// name: 'Aleksandr', | |
// id: 4 | |
// }, | |
// { | |
// votes: [1, 2, 3, 4, 5], | |
// name: 'Un Garson', | |
// id: 5 | |
// }, | |
// { | |
// votes: [5, 4, 3, 0, 0], | |
// name: 'Justin', | |
// id: 6 | |
// }, | |
// { | |
// votes: [1, 1, 2, 4, 5], | |
// name: 'Jean-Noel', | |
// id: 7 | |
// }, | |
// { | |
// votes: [1, 0, 3, 4, 0], | |
// name: 'Ekaterina', | |
// id: 8 | |
// }, | |
// { | |
// votes: [1, 0, 0, 4, 0], | |
// name: 'Evgeniy', | |
// id: 9 | |
// }, | |
// { | |
// votes: [1, 0, 3, 4, 0], | |
// name: 'Igor', | |
// id: 10 | |
// } | |
// ] | |
// updateWithMetrics(usersVotes); | |
// console.log(kNearestNeighbors(usersVotes, usersVotes[5], 3)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment