python 3中的prefixspan、bide和feat
prefixspan的Python项目详细描述
在importpython第173期的上特别报道。非常感谢您的支持！
著名的频繁序列模式挖掘算法的最短而有效的实现explore.ieee.org/abstract/document/1319986" rel="nofollow">等待（在closed.py中），以及频繁的生成器顺序模式挖掘算法feat（在generator.py中），作为一个统一的整体算法框架。
bide通常比prefixspan在大型数据集上要快得多，因为只返回共享所有模式的等效信息的封闭模式的一小部分。
feat通常比prefixspan快，但在大型数据集上比bide慢。
对于更简单的代码，一些通用函数已被移到新库中，成为新库的一部分。
参考
研究论文
PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth. Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, Meichun Hsu. Proceedings of the 17th International Conference on Data Engineering, 2001.
BIDE: Efficient Mining of Frequent Closed Sequences. Jianyong Wang, Jiawei Han. Proceedings of the 20th International Conference on Data Engineering, 2004.
Efficient mining of frequent sequence generators. Chuancong Gao, Jianyong Wang, Yukai He, Lizhu Zhou. Proceedings of the 17th International Conference on World Wide Web, 2008.
替代实施
我创建这个项目时，使用了prefixspan的原始的最少15行实现，用于教育目的。然而，随着这个项目发展成为一个完整的功能库，它的代码大小也不可避免地增长。我已经修改并重新发布了最初的实现，将其作为github的一个gisthub gist参考。
您也可以尝试我的scalaprefixspan版本。
功能
输出传统的单项目顺序模式，允许项目之间存在间隙。
支持挖掘top-k模式，并对效率进行了相应的优化。
您可以限制挖掘模式的长度。请注意，正确设置最大图案长度可以显著加快算法的速度。
可以应用自定义键函数、自定义筛选函数和自定义回调函数。
安装
这个包在pypi上提供。只需使用pip3 install-u prefixspan即可安装它。
cli用法
您只需在终端上使用算法即可。
Usage:
prefixspan-cli (frequent | top-k) <threshold> [options] [<file>]
prefixspan-cli --help
Options:
--text Treat each item as text instead of integer.
--closed Return only closed patterns.
--generator Return only generator patterns.
--key=<key> Custom key function. [default: ]
Must be a Python function in form of "lambda patt, matches: ...", returning an integer value.
--bound=<bound> The upper-bound function of the respective key function. When unspecified, the same key function is used. [default: ]
Must be no less than the key function, i.e. bound(patt, matches) ≥ key(patt, matches).
Must be anti-monotone, i.e. for patt1 ⊑ patt2, bound(patt1, matches1) ≥ bound(patt2, matches2).
--filter=<filter> Custom filter function. [default: ]
Must be a Python function in form of "lambda patt, matches: ...", returning a boolean value.
--minlen=<minlen> Minimum length of patterns. [default: 1]
--maxlen=<maxlen> Maximum length of patterns. [default: 1000]
- 序列从标准输入读取。每个序列都是由空格分隔的整数，如以下示例：
cat test.dat 0 1 2 3 4 1 1 1 3 4 2 1 2 2 0 1 1 1 2 2
- 处理文本数据时，请使用
--text选项。每个序列都是由空格分隔的单词，假设停止词已被删除，如以下示例：
cat test.txt a b c d e b b b d e c b c c a b b b c c
- 模式及其各自频率打印到标准输出。
prefixspan-cli frequent 2 test.dat 0 : 2 1 : 4 1 2 : 3 1 2 2 : 2 1 3 : 2 1 3 4 : 2 1 4 : 2 1 1 : 2 1 1 1 : 2 2 : 3 2 2 : 2 3 : 2 3 4 : 2 4 : 2
prefixspan-cli frequent 2 --text test.txt a : 2 b : 4 b c : 3 b c c : 2 b d : 2 b d e : 2 b e : 2 b b : 2 b b b : 2 c : 3 c c : 2 d : 2 d e : 2 e : 2
API使用
或者，您可以通过API使用算法。
fromprefixspanimportPrefixSpandb=[[0,1,2,3,4],[1,1,1,3,4],[2,1,2,2,0],[1,1,1,2,2],]ps=PrefixSpan(db)
有关每个参数的详细信息，请参阅prefixspan/api.py中的prefixspan类
PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth. Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, Meichun Hsu. Proceedings of the 17th International Conference on Data Engineering, 2001.0
闭合模式和生成器模式
由于数字较小，闭合图案更加紧凑。
- 如果没有相同频率的超级模式，则模式关闭。
PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth. Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, Meichun Hsu. Proceedings of the 17th International Conference on Data Engineering, 2001.1
由于数量较少，长度较短，发电机的外形更加紧凑。
如果没有相同频率的子模式，则模式是生成器。
由于高度紧凑，生成器模式可作为分类等功能使用。
PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth. Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, Meichun Hsu. Proceedings of the 17th International Conference on Data Engineering, 2001.2
有闭合模式和生成器模式。
PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth. Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, Meichun Hsu. Proceedings of the 17th International Conference on Data Engineering, 2001.3
自定义键功能
对于frequent和top-k算法，都可以应用自定义键函数key=lambda patt，matches:…，其中patt是当前模式，matches是当前匹配序列列表（id，position）元组。
默认情况下，
len（matches）用于表示当前模式的频率。或者，可以使用任何键功能。例如，
sum（len（db[i]）for i in matches）可用于根据匹配项的数目来找到满意的模式。为了提高效率，还应为修剪指定一个反单调上界函数。
- 如果未指定，则键函数也是上界函数，并且必须是反单调的。
PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth. Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, Meichun Hsu. Proceedings of the 17th International Conference on Data Engineering, 2001.4
自定义筛选函数
对于frequent和top-k算法，都可以应用一个自定义过滤函数filter=lambda patt，matches:…，其中patt是当前模式，而matches是当前匹配序列的列表（id，position）元组。
默认情况下，
筛选器不应用，并且返回所有模式。或者，可以使用任何函数。例如，
匹配[0][0]>；0可用于排除覆盖第一个序列的模式。
PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth. Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, Meichun Hsu. Proceedings of the 17th International Conference on Data Engineering, 2001.5
自定义回调函数
对于frequent和top-k算法，可以使用自定义回调函数callback=lambda patt，matches:…而不是返回模式的正常结果及其各自的频率。
当指定回调函数时，将返回
none。对于大型数据集，在挖掘频繁模式时，可以使用回调函数立即处理每个模式，避免大量模式占用大量内存。
以下示例查找覆盖每个序列的最长频繁模式。
PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth. Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, Meichun Hsu. Proceedings of the 17th International Conference on Data Engineering, 2001.6
Tip
我强烈建议使用pypy而不是cpython来运行脚本以获得最佳性能。以我自己的经验，平均速度快了近10倍。首先，您可以在为pypy创建的虚拟环境中安装此软件包。
欢迎加入QQ群-->： 979659372
