基于近似个体协同的进化子结构发现

Evolutionary Algorithm for Substructure Discovery Based on Approximate Individual Cooperation

SUBDUE是一个主流的图数据挖掘算法。为克服其贪婪式查找易陷入局部极值的问题,将进化算法与爬山算法相结合并引入图数据挖掘,较好地权衡了算法的探查和利用能力。另外,针对图数据挖掘中普遍存在的实例易丢失的问题,采用了个体协同的查找方法,该方法与常见的种群间协同进化算法不同,可以使同一种群中的个体进行协同查找,重新找回丢失的实例。同时,还给出了一种具有多项式时间复杂度的近似图匹配算法以改善个体间协同的性能。实验结果表明,以上措施增强了算法的执行效率及寻优能力,能够获得更优的解。

SUBDUE is a representative graph-based data mining algorithm.To overcome the limit that the greedy search adopted by SUBDUE may often give sub-optimal solutions,a hybrid evolutionary algorithm,which balances the exploration and exploitation of search by combining the hill-climbing and EA,is developed to perform data mining on graphical databases.In addition,during the searching process,losing instances is common and vital to the algorithm performance.To address this issue,adopt the individual cooperation strategy which is greatly different from the common cooperatively evolutionary approach based on population cooperation.The new strategy enables individuals in the same population to search in a cooperative way and gets back the lost instances.At the same time,an approximate graph matching algorithm with polynomial time complexity is also proposed to improve the performance of the process of individual cooperation.Experimental results show that these measures successfully improve the efficiency and the searching capability of the algorithm and can get better results.