Apriori算法----Node.js的实现

1.Apriori介绍

Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做$L_1$，然后利用$L_1$找频繁2项集的集合$L_2$，$L_2$找$L_3$，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。

其中，Apriori算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)< 最小支持度阈值，当有元素A添加到I中时，结果项集（A∩I）不可能比I出现次数更多。因此A∩I也不是频繁的。

2.连接步和剪枝步

在上述的关联规则挖掘过程的两个步骤中，第一步往往是总体性能的瓶颈。Apriori算法采用连接步和剪枝步两种方式来找出所有的频繁项集。

(1) 连接步

为找出$L_k$（所有的频繁k项集的集合），通过将$L_{k-1}$（所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。候选集合记作$C_k$。设$l_1$和$l_2$是$L_{k-1}$中的成员。记$l_i$[j]表示$l_i$中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-1）项集$l_i$，$l_i$[1]<$l_i$[2]<……….<$l_i$[k-1]。将$L_{k-1}$与自身连接，如果($l_1$[1]=$l_2$[1])&&( $l_1$[2]=$l_2$[2])&&………&& ($l_1$[k-2]=$l_2$[k-2])&&($l_1$[k-1]<$l_2$[k-1])，那认为$l_1$和$l_2$是可连接。连接$l_1$和$l_2$产生的结果是{$l_1$[1],$l_1$[2],……,$l_1$[k-1],$l_2$[k-1]}。

(2) 剪枝步

$C_K$是$L_K$的超集，也就是说，$C_K$的成员可能是也可能不是频繁的。通过扫描所有的事务（交易），确定$C_K$中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。为了压缩$C_K$,可以利用Apriori性质：任一频繁项集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从$C_K$中删除。

（Tip：为什么要压缩$C_K$呢？因为实际情况下事务记录往往是保存在外存储上，比如数据库或者其他格式的文件上，在每次计算候选计数时都需要将候选与所有事务进行比对，众所周知，访问外存的效率往往都比较低，因此Apriori加入了所谓的剪枝步，事先对候选集进行过滤，以减少访问外存的次数。）

3.Node.js的实现

// 因为k项集的项不确定它的类型，所以此处没有用字典排序...
const fs = require("fs");
const readline = require('readline');

const fReadName = './data.txt';

const fRead = fs.createReadStream(fReadName);

const rl = readline.createInterface({
    input: fRead
});

// 最小支持度
const min_sup = 2;

const dataArr = [];

rl.on('line', (line) => {
    let row = line.split(",");
    dataArr.push(row);
});

rl.on('close', () => {
    let Ck1 = freq1Gen(dataArr);
    while (Ck1.length !== 0) {
        Ck = Ck1;
        Ck1 = freqKGen(Ck);
    }
    console.log(Ck);
});


//1.计算候选集C1  
function freq1Gen(data) {
    let buffer = [];
    let isShow = false;
    for (let i = data.length - 1; i >= 0; i--) {
        for (let j = data[i].length - 1; j >= 0; j--) {
            isShow = false;
            for (let k = buffer.length - 1; k >= 0; k--) {
                if (buffer[k].name == data[i][j]) {
                    buffer[k].count++;
                    isShow = true;
                    break;
                }
            }
            if (isShow == false) {
                buffer.push({
                    name: data[i][j],
                    count: 1
                })
            }
        }
    }
    let ret = [];
    for (let i = buffer.length - 1; i >= 0; i--) {
        if (buffer[i].count >= min_sup) {
            ret.push([buffer[i].name]);
        }
    }
    return ret;
}

//2.计算候选集C(k+1)  
function freqKGen(data) {

    // 连接
    // 补充：如果k项集的项是数字或字符串，可先将其按字典次序排序。
    // 方便后面数组去重复的操作。
    let candi = [];
    for (let i = 0; i < data.length; i++) {
        for (let j = i + 1; j < data.length; j++) {
            candi.push(data[i].concat(data[j]).unique());
        }
    }
    candi = rr_unique(candi);
    let buffer = [];
    for (let i = candi.length - 1; i >= 0; i--) {
        buffer.push({
            arr: candi[i],
            count: 0
        });
    }
    //计算支持数  
    for (let i = buffer.length - 1; i >= 0; i--) {
        for (let j = dataArr.length - 1; j >= 0; j--) {
            if (isContain(dataArr[j], buffer[i].arr)) {
                buffer[i].count++;
            }
        }
    }
    //剪枝  
    let ret = [];
    for (let i = buffer.length - 1; i >= 0; i--) {
        if (buffer[i].count >= min_sup) {
            ret.push(buffer[i].arr);
        }
    }
    return ret;
}


//数组去重,hash table.  
Array.prototype.unique = function() {
    let n = {},
        r = []; //n为hash表，r为临时数组  
    for (let i = 0; i < this.length; i++) { //遍历当前数组  
        if (!n[this[i]]) { //如果hash表中没有当前项  
            n[this[i]] = true; //存入hash表  
            r.push(this[i]); //把当前数组的当前项push到临时数组里面  
        }
    }
    return r;
}

// 假设k项集里面的项为不确定元素，无法排序。此处只能一一比较。
// arr里面的数组去重复：如何arr里面存在两个相同的数组则找到它，然后删除一个。
function rr_unique(arr) {
    let toDel = []
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i].length == arr[j].length) {
                let flag = true;
                for (let k = 0; k < arr[j].length; k++) {
                    if (!arr[i].includes(arr[j][k])) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    toDel.push(i);
                    break;
                }
            }

        }
    }
    for (let i = toDel.length - 1; i >= 0; i--) {
        arr.splice(toDel[i], 1);
    }
    return arr;
}


//判断arr1是否包含arr2  
function isContain(arr1, arr2) {
    for (let i = arr2.length - 1; i >= 0; i--) {
        if (!arr1.includes(arr2[i])) {
            return false;
        }
    }
    return true;
}

参考链接：

https://www.cnblogs.com/catkins/p/5270485.html
http://blog.csdn.net/lx583274568/article/details/70739258