频繁子图挖掘算法gspan的实现
gspan-mining的Python项目详细描述
gspan
中文自述请转到README-Chinese。
gspan是一种挖掘频繁子图的算法。
这个程序用python实现gspan。github上的存储库是https://github.com/betterenvi/gSpan。这个实现借鉴了gboost的一些思想。
无向图
此程序支持无向图，并在数据集graphdata/graph.data上生成与gboost相同的结果。
有向图
到目前为止（日期：2016-10-29），gboost不支持有向图。这个程序实现了有向图的gspan。更具体地说，该程序可以挖掘至少有一个节点可以到达子图中其他节点的频繁有向子图。但是由于作者没有做足够的测试，所以不能保证正确性。在数据集graphdata/graph.data.directed.1和graph.data.simple.5上运行几次之后，就没有错误了。
如何安装
这个程序同时支持python 2和python 3。
方法1
使用pip安装此项目：
pip install gspan-mining
方法2
首先，克隆项目：
git clone https://github.com/betterenvi/gSpan.git
cd gSpan
您可以选择将此项目安装为第三方库，以便可以在任何路径下运行它。
python setup.py install
如何运行
命令是：
python -m gspan_mining [-s min_support][-n num_graph][-l min_num_vertices][-u max_num_vertices][-d True/False][-v True/False][-p True/False][-w True/False][-h] database_file_name
一些例子
- 从./graph data/graph.data读取图形数据，并在最小支持为5000的情况下挖掘无向子图
python -m gspan_mining -s 5000 ./graphdata/graph.data
- 从./graph data/graph.data读取图形数据，在最小支持为5000的情况下挖掘无向子图，并可视化这些频繁子图（需要matplotlib和networkx）
python -m gspan_mining -s 5000 -p True ./graphdata/graph.data
- 从./graph data/graph.data和mine-directed子图中读取图形数据，最小支持为5000
python -m gspan_mining -s 5000 -d True ./graphdata/graph.data
- 打印帮助信息
python -m gspan_mining -h
python -m gspan_mining -s 5000 ./graphdata/graph.data
python -m gspan_mining -s 5000 -p True ./graphdata/graph.data
python -m gspan_mining -s 5000 -d True ./graphdata/graph.data
python -m gspan_mining -h
作者还使用jupyter笔记本编写了example code。给出了挖掘结果和可视化结果。详情请参阅main.ipynb。
运行时间
环境
- 操作系统：Windows 10
- python版本：python 2.7.12
- 处理器：Intel（R）Core（TM）i7-4790 CPU@3.60GHz 3.60GHz
- 内存：8.00 GB
运行时间 在数据集./graphdata/graph.data上，运行时间如下所示：
| Min support | Number of frequent subgraphs | Time |
|---|---|---|
| 5000 | 26 | 51.48 s |
| 3000 | 52 | 69.07 s |
| 1000 | 455 | 3 m 49 s |
| 600 | 1235 | 7 m 29 s |
| 400 | 2710 | 12 m 53 s |
参考值
gspan：基于图的子结构模式挖掘，作者x.yan和j.han。 过程。2002年国际数据挖掘会议（ICDM'02）。
一个C++实现的GSPAN。
欢迎加入QQ群-->： 979659372
