-
Notifications
You must be signed in to change notification settings - Fork 0
/
FPgrowth.js
384 lines (332 loc) · 13 KB
/
FPgrowth.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
var fs = require("fs");
var _ = require("lodash");
var TreeModel = require("tree-model");
var AllFPs = [];
var minSup = 0; // minimum support
module.exports = {
demoSmall: function demo(){
TreeModel.prototype.initialize = function(base = null){
this["header"] = []; // added header attribute for FPgrowth algorithm
this["root"] = this.parse({item: "root"}); // root of the tree
this["base"] = base; // what the tree was produced using
}
// testingDB and testingHeader are taken from the data mining textbook pg 258
testingDB = [
["I2", "I1", "I5"],
["I2", "I4"],
["I2", "I3"],
["I2", "I1", "I4"],
["I1", "I3"],
["I2", "I3"],
["I1", "I3"],
["I2", "I1", "I3", "I5"],
["I2", "I1", "I3"]
];
testingHeader = [
{item:"I2", support: 7},
{item:"I1", support: 6},
{item:"I3", support: 6},
{item:"I4", support: 2},
{item:"I5", support: 2},
];
minSup = 2;
var FPTree = new TreeModel(); // initialize FPTree
FPTree.initialize();
FPTree.header = testingHeader;
FPTree.header.forEach(element => { // add empty array to each header item
element['list'] = [];
});
console.log();
console.log("database: ");
testingDB.forEach(element =>{
console.log(JSON.stringify(element));
});
console.log();
console.log("one item sets: ");
FPTree.header.forEach(element =>{
console.log(JSON.stringify(element.item + " | " + element.support));
});
// Build FPTree
// insert all of the transactions into the fp tree
testingDB.forEach(track => {
FPTreeInsert(FPTree, track);
});
console.log("");
printTree(FPTree.root);
console.log("");
console.time("FPgrowth Execution time");
// generate frequent items
FPGrowthPlus(FPTree);
console.timeEnd("FPgrowth Execution time");
return AllFPs;
},
demoLarge: function spoftifyDBDemo(){
TreeModel.prototype.initialize = function(base = null){
this["header"] = []; // added header attribute for FPgrowth algorithm
this["root"] = this.parse({item: "root"}); // root of the tree
this["base"] = base; // what the tree was produced using
}
minSup = 5;
// Read ordered and pruned db into memory
var orderedTracks = JSON.parse(fs.readFileSync("./JSON/FPgrowthDB.json", 'utf8'));
// read header for FP tree
var headerFile = JSON.parse(fs.readFileSync("./JSON/FPgrowthHeader.json", 'utf8'));
var FPTree = new TreeModel(); // initialize FPTree
FPTree.initialize();
FPTree.header = headerFile;
FPTree.header.forEach(element => { // add empty array to each header item
element['list'] = [];
});
// Build FPTree
// insert all of the transactions into the fp tree
orderedTracks.forEach(track => {
FPTreeInsert(FPTree, track);
});
console.log("");
console.time("FPgrowth");
// generate frequent items
FPGrowthPlus(FPTree);
console.timeEnd("FPgrowth");
return AllFPs;
}
}
// ---------------- constructing initial FPTree from database ----------------
// Inserts items from a list into the tree and adds new nodes to the lists in
// the header. Recursively calls FPTreeInsert until the list is empty.
// Prams:
// tree: Tree that contains the header that will have new nodes added
// to its lists.
// node: Node that will have its children checked.
// row: transaction.
// returns: No return value
function FPTreeInsert(tree, track, node = tree.root){
var found = false;
var newNode = {};
if (node.hasChildren()) { // if node has children
// check if item matches any of node's children
for(var i = 0, len = node.children.length; i < len; i++) {
if (node.children[i].model.item == track[0]){ // if the child matches the item
found = true;
node.children[i].model.support++;
newNode = node.children[i];
}
};
}
if (!found){ // node not found so insert it
newNode = node.addChild(tree.parse({
item: track[0],
support: 1
}));
for(let i = 0, len = tree.header.length; i < len; i++){
if (tree.header[i].item == track[0]){
tree.header[i].list.push(newNode);
}
}
}
track.shift(); // remove item that was inserted
if (track.length !== 0){
FPTreeInsert(tree, track, newNode);
}
}
// ------------------------- FPGrowth* --------------------------------
function FPGrowthPlus(tree){
if (singlePath(tree.root)){
// generate all combinations of the path and union them with tree.base
// gets the path, removes root and removes unwanted tree information
var path = tree.header[tree.header.length - 1].list[0].getPath().slice(1).map(function(element){
return {item: element.model.item, support: element.model.support};
});
var combinations = [];
// pushes all combinations of item, support objects into combinations
for(let combination of allCombinations(path)){
if(combination.length !== 0){ // dont add empty arrays
combinations.push(combination);
}
}
// turn {item, support} combinations into {items:[item, item], support} patterns
combinations.forEach(combo => {
var supMin = combo[0].support;
var itemCombo = [];
combo.forEach(item => {
itemCombo.push(item.item);
// get the lowest support of the combination
supMin = supMin > item.support ? item.support : supMin;
});
// union tree.base with pattern
itemCombo = tree.base != null ? tree.base.concat(itemCombo) : itemCombo;
AllFPs.push({pattern: itemCombo, support: supMin});
});
} else {
// for each item in the header starting with lowest support
for (let i = tree.header.length - 1; i >= 0; i--){
var newPattern = tree.base != null ? tree.base.concat([tree.header[i].item]) : [tree.header[i].item];
// initialize tree for the new pattern
var newTree = new TreeModel();
newTree.initialize(newPattern);
AllFPs.push({pattern: newPattern, support: tree.header[i].support});
// construct header from tree paths
tree.header[i].list.forEach(listNode => {
var leafSup = listNode.model.support;
// get the path
let path = listNode.getPath().slice(1, -1);
// for each node on the path
for(let j = 0, len = path.length; j < len; j++){
let found = false;
let index = 0;
// check if it is in the header
while(!found && index < newTree.header.length){
if (newTree.header[index].item == path[j].model.item){
newTree.header[index].support += leafSup;
found = true;
}
index++;
}
if (!found){
newTree.header.push({item: path[j].model.item, support: leafSup, list: []});
}
}
});
newTree.header = newTree.header.filter(function(value){
return value.support >= minSup;
});
// sort header collection in ascending order
newTree.header.sort(function(a, b){
if (a.support < b.support){
return 1;
} else if (a.support > b.support){
return -1;
} else {
return 0;
}
});
// construct conditional base and create fp tree
tree.header[i].list.forEach(leaf => {
var conPattern = [];
var leafSupport = leaf.model.support;
var prefixPath = leaf.getPath().slice(1, -1);
// for each item in the new header
newTree.header.forEach(element => {
// check starting with highest support
// if a node.item matches the header header item
// add it to the pattern and break out of the loop
let found = false;
let index = 0;
while(!found && index < prefixPath.length){
if(prefixPath[index].model.item == element.item){
conPattern.push(prefixPath[index].model.item);
found = true;
}
index++;
}
});
// dont add a pattern with no items
if (conPattern.length > 0){
FPGrowthPlusInsert(newTree, {items: conPattern, support: leafSupport});
}
});
if (newTree.root.hasChildren()){
FPGrowthPlus(newTree);
}
}
}
}
// Inserts items from a list into the tree and adds new nodes to the lists in
// the header. Recursively calls FPGrowthPlusInsert until the list is empty.
// Prams:
// tree: Tree that contains the header that will have new nodes added
// to its lists.
// node: Node that will have its children checked.
// row: transaction.
// returns: No return value
function FPGrowthPlusInsert(tree, track, node = tree.root){
var found = false;
var newNode = {};
if (node.hasChildren()) { // if node has children
// check if item matches any of node's children
for(var i = 0, len = node.children.length; i < len; i++) {
if (node.children[i].model.item == track.items[0]){ // if the child matches the item
found = true;
node.children[i].model.support += track.support;
newNode = node.children[i];
}
};
}
if (!found){ // node not found so insert it
newNode = node.addChild(tree.parse({
item: track.items[0],
support: track.support
}));
for(let i = 0, len = tree.header.length; i < len; i++){
if (tree.header[i].item == track.items[0]){
tree.header[i].list.push(newNode);
}
}
}
track.items.shift(); // remove item that was inserted
if (track.items.length !== 0){
FPGrowthPlusInsert(tree, track, newNode);
}
}
// Checks if a tree is a single path
// prams:
// root: root of the tree to evaluate
// returns: true if the tree is a single path false otherwise.
function singlePath(root){
if(root.hasChildren()){
if (root.children.length == 1){
return singlePath(root.children[0]);
} else {
return false;
}
}
return true;
}
// Given an array of items this generator will create all possible combinations
// reference: https://stackoverflow.com/questions/42773836/how-to-find-all-subsets-of-a-set-in-javascript
// prams:
// array: array to generate power set from
function* allCombinations(array, offset = 0){
while(offset < array.length){
let first = array[offset++];
for(let combination of allCombinations(array, offset)){
combination.push(first);
yield combination;
}
}
yield [];
}
// --------------------- DEBUG --------------------
// Debugging function checks the support of all the nodes in the list vs the values in the header table
function FPtreeTest(tree){
var fail = false;
tree.header.forEach(element => {
var supportTotal = 0;
element.list.forEach(node => {
supportTotal += node.model.support;
});
if(supportTotal !== element.support){
fail = true;
console.log(element.item + " FAIL");
console.log("Header support: " + element.support);
console.log("Total support: " + supportTotal);
console.log("");
}
});
if(!fail){
console.log("Tree PASSES")
}
}
function printTree(node, level = 0){
var branch = "";
for(i = 0; i < level; i++){
branch += " ";
}
process.stdout.write(branch);
console.log("node: " + node.model.item + " Support: " + node.model.support);
if(node.hasChildren()){
var inc = level + 1;
for(var i = 0; i < node.children.length; i++){
printTree(node.children[i], inc);
}
}
}