挖掘最大频繁项集的朴素蚁群优化算法

摘要

为了挖掘大型数据库中的最大频繁项集,为其建立了非线性优化模型,并给出一种朴素蚁群算法求解.该算法只需要扫描一次数据库,不使用启发式信息而采用朴素信息素模型,即信息素释放在与每个项关联的有两个边上,从而将边与项紧密联系起来,既构建了蚁群的路径,又挖掘最大频繁项集.采用与问题紧密相关的局部更新、全局更新和局部搜索机制.理论分析和对比实验结果表明了该算法的有效性.%To mining maximal frequent itemsets in large database, a non-linear optimization model is established and then applied a simple ant colony algorithm to solve it. The proposed algorithm scans the database only once. It has no heuristic information but adopt a simple information pheromone model. The pheromones are laid on two edges associated with each item and thus both the tour graph is constructed and the maximum frequent itemsets are mined. The local update, global update and local search mechanism which closely related with the problem is given. Theoretical analysis and comparison results show the effectiveness of the algorithm.