一种基于局部重构树的改进频繁子图挖掘算法

An Improved Frequent Sub-graph Mining Algorithm Based on Local Reconstruction Tree

针对SFP算法在其构造频繁模式树时需扫描数据库两次,算法效率较低的问题,首先提出了一种局部重构树结构OFP,该结构在构造频繁模式时只需要扫描一次数据库即可获取所需信息,同时采用了基于Hash表的辅助存储结构来改进唯一标号图,节省了子图重构时间。然后基于OFP树结构,提出了一种改进的高效频繁模式挖掘算法OSFP。实验结果表明,OSFP算法在内存占用和执行时间上均优于SFP算法。

Construct of frequent pattern FP - tree would reduce the efficiency of the SFP algorithm for it has to scan database twice. For this problem, a kind of tree structure by local reconstructing was proposed, it could get all the information needed while constructing frequent mode by scanning database once. At the same time a kind of storage structure of Hash table was used to improve the numbered graph, and saving time of reconstruction of sub - graph. Based on OFP - tree construct, an improved mining algorithm OSFP in high efficiency of frequent pattern was proposed. The experiment result shows that the improved algorithm is superior on RAM spent and time execution compared to algorithm SFP.