"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