Abstract: Concerning the problem of low traversal efficiency when searching the FP-tree for conditional pattern bases, a new no-header-table FP-Growth algorithm was proposed. The algorithm employed a recursively backtracking way to search for conditional pattern bases, avoiding traversing the same FP-tree path multiple times. Compared with FP-Growth algorithm in terms of theoretical analysis and actual mining performance, this algorithm greatly reduced the searching cost and improved the mining efficiency of frequent patterns by 2-5 times. Finally, the algorithm was used to mine association rules in telecommunication network alarms. The high mining speed, with the coverage of 83.3% against correct rules, shows that it is superior to FP-Growth both in time and space performance.

Key words: item header table, frequent pattern, association rule, alarm association, data mining

摘要： 针对FP-Growth算法中频繁模式树的遍历低效问题,提出了一种无项头表的频繁模式增长算法。该算法利用递归回溯的方式遍历频繁模式树以求取条件模式基,解决了对同一树路径多次重复遍历的问题。从理论分析和实际挖掘能力两方面,将新算法与FP-Growth算法进行了对比。结果表明,新算法有效减少了条件模式基的搜索开销,使频繁模式挖掘的效率提高了2~5倍,在时间和空间性能上均优于FP-Growth算法。将该算法应用于通信告警关联规则挖掘,较快地挖掘出了关联规则结果,且正确规则的覆盖率达到了83.3%。

关键词: 项头表, 频繁模式, 关联规则, 告警关联, 数据挖掘