This file contains 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
"use strict"; | |
let exports = {} | |
Object.defineProperty(exports, "__esModule", { value: true }); | |
class CPT { | |
constructor() { | |
this.alphabet = new Set(); | |
this.root = new PredictionTree(); | |
this.II = {}; | |
this.LT = {}; | |
this.data = []; | |
// | |
} | |
/** | |
This functions populates the Prediction Tree, | |
Inverted Index and LookUp Table for the algorithm. | |
Input: The list of list training data | |
Output : Boolean True | |
*/ | |
train(data) { | |
let existingDataLength = this.data.length; | |
this.data = this.data.concat(data); | |
let cursornode = this.root; | |
data.forEach((row, idx) => { | |
idx = idx + existingDataLength; | |
row.forEach(element => { | |
if (!cursornode.hasChild(element)) { | |
cursornode.addChild(element); | |
} | |
cursornode = cursornode.getChild(element); | |
this.II[element] = this.II[element] || new Set(); | |
this.II[element].add(idx); | |
this.alphabet.add(element); | |
}); | |
this.LT[idx] = cursornode; | |
cursornode = this.root; | |
}); | |
return true; | |
} | |
/** | |
* | |
* This function is the main workhorse and calculates the score to be populated against an item. Items are predicted | |
using this score. | |
Output: Returns a counttable dictionary which stores the score against items. This counttable is specific for a | |
particular row or a sequence and therefore re-calculated at each prediction. | |
* | |
* @param counttable | |
* @param key | |
* @param numberOfSimilarSequences | |
* @param numberItemsCounttable | |
*/ | |
score(counttable, key, numberOfSimilarSequences, numberItemsCounttable) { | |
let weightLevel = 1 / numberOfSimilarSequences; | |
let weightDistance = 1 / numberItemsCounttable; | |
let score = 1 + weightLevel + weightDistance * 0.001; | |
let entry = (isNaN(counttable.get(key))) | |
? score | |
: score * counttable.get(key); | |
counttable.set(key, entry); | |
return counttable; | |
} | |
/** | |
* | |
* @param target Test dataset in the form of list of list | |
* @param k The number of last elements that will be used to find similar sequences | |
* @param n The number of predictions required | |
* | |
* @returns max n predictions for each sequence | |
*/ | |
predict(target, k = target.length, n = 1) { | |
let predictions = []; | |
for (let eachTarget of target) { | |
eachTarget = eachTarget.slice(-k); | |
let eachTargetSet = new Set(eachTarget); | |
let intersection = new Set([...Array(this.data.length).keys()]); | |
for (let element of eachTarget) { | |
if (!this.II[element]) | |
continue; | |
intersection = intersect(intersection, this.II[element]); | |
} | |
let similarSequences = []; | |
for (let element of intersection) { | |
let currNode = this.LT[element]; | |
let tmp = []; | |
while (currNode.item !== null) { | |
tmp.push(currNode.item); | |
currNode = currNode.parent; | |
} | |
similarSequences.push(tmp); | |
} | |
similarSequences = similarSequences.map(s => s.reverse()); | |
let countTable = new Map(); | |
for (let sequence of similarSequences) { | |
let index; | |
try { | |
index = sequence.length - 1 - sequence.slice(0) | |
.reverse() | |
.findIndex(v => v === eachTarget[eachTarget.length - 1]); | |
} | |
catch (e) { | |
index = null; | |
} | |
if (index >= 0) { | |
let count = 1; | |
for (let element of sequence.slice(index + 1)) { | |
if (eachTargetSet.has(element)) | |
continue; | |
countTable = this.score(countTable, element, similarSequences.length, count); | |
count++; | |
} | |
} | |
} | |
let pred = getNLargest(countTable, n); | |
predictions.push(pred); | |
} | |
return predictions; | |
} | |
} | |
exports.default = CPT; | |
/** | |
* A small utility to obtain top n keys of a Dictionary based on their values. | |
* | |
* @param dict | |
* @param n | |
*/ | |
function getNLargest(dict, n) { | |
return [...dict.entries()] | |
.sort(([key1, val1], [key2, val2]) => (val2 > val1) ? 1 : -1) | |
.slice(0, n) | |
.map(entry => entry[0]); | |
} | |
function intersect(a, b) { | |
return new Set([...a].filter(x => b.has(x))); | |
} | |
class PredictionTree { | |
constructor(itemValue = null) { | |
this.children = []; | |
this.parent = null; | |
this.item = itemValue; | |
} | |
addChild(child) { | |
let newChild = new PredictionTree(child); | |
newChild.parent = this; | |
this.children.push(newChild); | |
} | |
getChild(target) { | |
return this.children.find(child => child.item === target); | |
} | |
getChildren() { | |
return this.children; | |
} | |
hasChild(target) { | |
return !!this.getChild(target); | |
} | |
removeChild(childValue) { | |
this.children = this.children | |
.filter(child => child.item !== childValue); | |
} | |
} | |
exports.PredictionTree = PredictionTree; | |
//# sourceMappingURL=index.js.map |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment