基于分割圖集的頻繁閉圖挖掘算法

0 引言

頻繁子圖挖掘是圖挖掘的重要研究方向，它為進一步的圖分類和圖聚類研究工作提供必要的支持，但頻繁子圖挖掘所獲得的結果往往是非常龐大的，如在圖模式挖掘和圖分類經常使用的實驗數據NCI／CA中，當最小支持度為5％時大約產生i00萬個頻繁圖模式，在此基礎上很難對頻繁子圖作進一步的分類或聚類研究。針對這個問題，2003年Yah等人提出了挖掘頻繁閉圖的CloseGraph算法，所謂閉圖就是指在圖集中不存在和它具有相同支持度的真超圖。與挖掘頻繁子圖相比，它能大大減少挖掘得到的圖模式，如上所述，在最小支持度為5％的實驗數據NCL／CA中，只有不到2 000個頻繁閉圖模式。更為重要的是，挖掘頻繁閉圖模式不會丟失任何有用的信息，因為從頻繁閉圖模式集合能恢復所有的頻繁子圖模式，而且在實際應用中，領域專家只對頻繁閉圖模式感興趣。