頻繁子圖挖掘算法gSpan的實(shí)現(xiàn)
項(xiàng)目地址：https://github.com/betterenvi/gSpan
頻繁子圖挖掘是數(shù)據(jù)挖掘中一個(gè)非常廣泛的應(yīng)用。頻繁子圖挖掘是指從大量的圖中挖掘出滿足給定支持度的頻繁子圖，同時(shí)算法需要保證這些頻繁圖不能重復(fù)。頻繁模式挖掘主要就是應(yīng)用兩種策略（這里不討論基于垂直增長(zhǎng)的方法）——Apriori和Growth蜀铲。最早的AGM和FSG就分別實(shí)現(xiàn)了這兩重策略的基本思想审残。gSpan是一個(gè)非常高效的算法骑冗，它利用dfs-code序列對(duì)搜索樹(shù)進(jìn)行編碼，并且制定一系列比較規(guī)則淌山，從而保證最后只得到序列“最小”的頻繁圖集合拯勉。
我用Python實(shí)現(xiàn)了面向無(wú)向圖竟趾、有向圖的GSpan耙考，在實(shí)現(xiàn)時(shí)，參考了gboost潭兽，一個(gè)gSpan的C++實(shí)現(xiàn)。在挖掘無(wú)向圖的頻繁子圖時(shí)斗遏，經(jīng)過(guò)多輪比較山卦，我的實(shí)現(xiàn)和gboost的輸出一致。
當(dāng)前（時(shí)間：2016-10-29）诵次，gboost還不支持有向圖的頻繁子圖挖掘账蓉。在我的實(shí)現(xiàn)中，支持面向有向圖的頻繁子圖挖掘逾一，可以挖掘那些至少有一個(gè)點(diǎn)能夠到達(dá)其他任一點(diǎn)的頻繁子圖铸本，但是還沒(méi)有全面測(cè)試過(guò)，正確性不敢保證遵堵。只在兩個(gè)簡(jiǎn)單的數(shù)據(jù)集上箱玷，運(yùn)行了數(shù)次，暫時(shí)還未發(fā)現(xiàn)錯(cuò)誤陌宿。歡迎大家訪問(wèn)我的項(xiàng)目https://github.com/betterenvi/gSpan锡足，如果能夠幫忙看看面向有向圖的挖掘是否正確，將十分感謝壳坪！
