Skip to content

Instantly share code, notes, and snippets.

@ungarson
Last active June 22, 2019 06:50
Show Gist options
  • Save ungarson/dbb2c71514e48f3e3d0ca8e91834a4ea to your computer and use it in GitHub Desktop.
Save ungarson/dbb2c71514e48f3e3d0ca8e91834a4ea to your computer and use it in GitHub Desktop.
k-nearest neighbors in js
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