Apriori算法实现关联规则的数据挖掘
See FP-growth(https://github.com/LetMeFly666/FP-growth) For More
目标只有一个，就是对于一个给定的置信度，用尽可能少的时间求出Source/retail.dat的所有关联规则
也就是说，此算法将会尽可能多地采用空间换时间、多线程等方法，在8G内存、i5处理器的电脑上计算出结果。
这个数据共有88162行(消费记录)，总共有16470种产品。
每条消费记录存入一个vector中，vector<uint16_t> items[88162]
每个vector中记录都有哪些商品。
Data:
1 2 5
3 4 5
4
Storage:
vector<uint16_t> itmes[3] = {
{1, 2, 5},
{3, 4, 5},
{4}
};
有多少数据大约就会使用多少空间(不是很清楚vector具体是怎么动态扩容的)
经过统计共有908576个数据，需要约1e6*2Byte≈2M的内存空间
每件商品存入一个vector中，vector<int> itmes(2^16=65536<88162，不可用uint16_t，这里先不考虑数据压缩)
每个vector记录这个商品出现在哪些消费记录中。
Data:
1 2 5
3 4 5
4
Storage:
vector<int> itmes[5] = {
{0},
{0},
{1},
{1, 2},
{0, 1}
};
类似方法一，共需要约1e6*4Byte≈4M的内存空间
类似方法二，每件商品用一个bitset来存储。bitset<908576> items[16470]
bitset的第i位代表这件商品是否出现在第i条消费记录中。
Data:
1 2 5
3 4 5
4
Storage:
bitset<3> items[5] = {
0b001,
0b001,
0b010,
0b110,
0b011
};
共有16470种商品，共有908576条记录，因此共需要空间16470*908576bit=1870530840Byte=1783.87722015380859375M=1.742067597806453704833984375G≈1.75G的内存空间。
每条消费记录建立一个Trie树，树上插入这个消费记录的每个商品。每条消费记录建立一个setunordered_setunordered_set<uint16_t> items[88162]，这样查询一个商品是否在某个记录中就比较快。
不便展示
空间复杂度O(∑商品数)，只是常数比较大
Ln是所有的 商品个数为n的、支持度≥给定支持度的商品集 的集合
对于一个确定的n，要判同时包含某n件商品的消费记录的条数，以此来确定是否能够满足给定支持度。
Ln是由Ln-1得到的。假设n=3，ab、ac∈Ln-1，由Ln-1得到Ln的时候，由ab和ac就可以组成abc(长度为3)。
如果bc∉Ln-1，那么就直接排除abc。（其中bc是abc的一个长度为n-1的子集。这么剪枝要找到所有abc中长度为2的子集，复杂度为O(n)）
统计abc的出现次数
找C中前缀全部相同的项（abc + abd -> abcd）
算法已经实现，暂未优化。主要就是L1->L2比较慢。假如使用数据Source\retail.dat且令最小支持度为2%，那么L1就有20个元素。
一共88162条记录，88162(2019/2)=16,750,780，set.count再加个log(N)，应该是执行了最少1e8的运算。
| 支持度 | 耗时 | 结果 |
|---|---|---|
| 5% | 0.333s | 20 + 22 + 12 + 1 = 55 |
| 1% | 35.729s | 70 + 58 + 25 + 6 = 159 |
| 0.8% | 75.483s | 101 + 98 + 38 + 6 = 243 |
| 0.5% | 360.879s | 221 + 237 + 102 + 19 + 1 = 580 |
| 描述 | 方案一 | 方案二 |
|---|---|---|
| 方案四中，每条消费记录用set还是unordered_set来存 | set ❌ | unordered_set ✔ |