FIS-ES算法：一种高效频繁项集挖掘新方法

需积分: 0 192 浏览量更新于2024-09-09 收藏 198KB PDF 举报

"这篇论文提出了一种新的频繁项集挖掘算法——FIS-ES，该算法基于扩展集合操作，旨在提高在低最小支持度条件下的挖掘速度和减少空间占用。通过对传统集合操作的扩展，FIS-ES算法在理论和实践上都显示出了优于Apriori算法的性能。论文指出，当面对小的最小支持度时，FIS-ES算法能更快地找到最大频繁项集，并且占用更少的内存资源，这使得它与Apriori算法形成良好的互补，适用于不同的数据挖掘场景。此外，该研究还涉及到了关联规则的挖掘，这是数据挖掘中的一个重要领域，用于发现数据中的有趣关系和模式。论文详细分析了算法的复杂度，并通过实验验证了其优越性。" 在数据挖掘领域，频繁项集挖掘是寻找数据库中频繁出现的项组合的过程，而关联规则则是在这些频繁项集中找出有意义的关系或规律。传统的Apriori算法是一种经典的频繁项集挖掘方法，它利用下闭合性质来减少搜索空间，但在处理低支持度的频繁项集时效率较低，因为需要多次扫描数据库。 FIS-ES算法对Apriori算法进行了改进，引入了扩展集合操作的概念。这种扩展可能包括对集合操作的优化，如并集、交集和差集，以更有效地处理频繁项集的生成。通过这种方式，FIS-ES能够在数据挖掘过程中减少不必要的计算和存储开销，尤其是在处理大规模数据集时，这一点显得尤为重要。论文中提到的实验结果进一步证实了FIS-ES的优势。在最低支持度较低的情况下，FIS-ES的挖掘速度明显快于Apriori，同时所需内存更少。这意味着对于那些需要快速发现低频模式的应用，FIS-ES可能是更优的选择。这种互补性意味着在实际应用中，根据数据的特性可以选择合适的算法，以达到最佳的挖掘效果。 FIS-ES算法的提出是对频繁项集挖掘领域的贡献，它提供了一个在特定条件下更高效、更节省资源的解决方案。这项工作不仅加深了我们对关联规则挖掘的理解，也为未来算法设计提供了新的思路，特别是在处理大数据集和低支持度问题时。

收稿日期: 2005-11-21; 修返日期: 2006-11-08

基金项目: 国家自然科学基金重大资助项目( 90104005)

一种新的频繁项集挖掘算法

刘德喜

1, 2, 3

, 何炎祥

1, 3

, 邢显黎

( 1. 武汉大学计算机学院, 湖北武汉 430079; 2. 襄樊学院物理系 , 湖北襄樊 441053; 3. 武汉大学语言与信

息研究中心, 湖北武汉 430079)

摘要: 首先对传统集合操作进行了扩展, 提出基于扩展集合操作的最大频繁项集生成算法 FIS-ES, 并从理论

和实验上对算法的复杂度进行了详细的分析。实验表明 , 在最小支持度较小的情况下 , FIS-ES 比 Apriori 算法具

有更快的挖掘速度、更少的空间占用等优点 , 与 Apriori 有很好的互补性。

关键词: 扩展集合操作; 关联规则; FIS-ES 算法

中图法分类号 : P208; TP393 文献标识码: A 文章编号 : 1001-3695( 2007) 02-0017-03

Novel Frequent Itemset Mining Algorithm

LIU De-xi

1,2, 3

, HE Yan-xiang

1, 3

, XING Xian-li

( 1. School of Computer, Wuhan University, Wuhan Hubei 430079, China; 2. Dept. of Physics, Xiangfan University, Xiangfan Hubei 441053,

China; 3. Center for Study of Language & Information, Wuhan University, Wuhan Hubei 430079, China)

Abstract: The traditional set operator has been extended, and then the FIS-ES algorithmisproposed on the basis of extended

set operators. Experiments show that the newalgorithmhas advantages such as more efficient and less space used in the lower

minimum support condition. It is a good complementarity for Apriori algorithm.

Key words: Extended Set Operator; Association Rule; FIS-ES Algorithm

关联规则的挖掘分为两步

[ 1,7]

: 首先找出满足最小支持度

要求的频繁项集; 然后根据频繁项集生成满足最小置信度要求

的关联规则集。其中, 第二步比较成熟, 挖掘关联规则的总体

性能则由第一步决定。经典频繁项集挖掘算法 Apriori

[ 1,2]

的

主要问题是由于多次重复扫描而带来的 I/O 代价过高, 因此,

之后的研究提出了许多减少数据库扫描次数的方法, 比较有

代表性的是分块、采样等

[ 2～6]

。近年来, 通过减少项目集的搜

索空间来减少数据库的扫描次数已经被广泛研究, 典型的代表

有 Han 提出的 FP-增长算法

[ 4]

。该方法不用候选频繁集, 而是

通过状态树记录扫描信息, 一次扫描数据库生成频繁项集。本

文算法将利用扩展后的集合操作, 通过一次扫描数据库, 逐步

生成最终的最大频繁项集。

1 基本概念

定义 1( 集合上的亚操作 )

[ 8]

设 S

和 S

是定义在相空

间上的两个项目集, I 是定义在相空间上的一个项。定义如下

操作:

亚属于( ∈

sub

) I∈

sub

当且仅当 I

∈S

使得 I I

亚包含(

sub

) S

∈

sub

当且仅当 I

∈S

有 I

∈

sub

亚交( ∩

sub

) S

∩

sub

= |I∈

sub

且 I∈

sub

}

亚并( ∪

sub

) S

∪

sub

= |I∈

sub

或 I∈

sub

}

亚操作是对传统集合操作的扩展, 扩展后的集合操作可以

有效地应用于频繁项集的挖掘中。下面将给出一些性质。

性质 1( 基本性质)

( 1) 亚属于和亚包含的传递性

( I

, I

∈

sub 2

∈

sub

1 sub

, S

2 sub

3 1 sub

(

)

亚交和亚并的放缩性

∩

sub

)

∩

sub

∩

sub

)

∩

sub

= S

∩

sub

∪

sub 1

∪

sub

)

∪

sub 1

∪

sub

)

= S

∪

sub

( 3) 亚交和亚并与传统交和并

( S

∪S

2 1

∪

sub

)

( S

∩S

2 1

∩

sub

)

性质 2( 亚并和亚交操作的相关性质)

亚并和亚交操作同时满足自含性、交换律、结合律、分配律

等集合操作的性质。

( 1) 自含性

∩

sub

1 sub

; S

∪

sub

1 sub

(

)

交换律

∪

sub

∪

sub

∩

sub

∩

sub

(

)

结合律

∪

sub

∪

sub

= S

∪

sub

( S

∪

sub

)

∩

sub

∩

sub

= S

∩

sub

( S

∩

sub

)

(

)

分配律

∩

sub

( S

∪

sub

) =( S

∩

sub

) ∪

sub

( S

∩

sub

)

∪

sub

( S

∩

sub

) =( S

∪

sub

) ∩

sub

( S

∪

sub

)

性质的证明略。

2 基于扩展集合操作的频繁项集挖掘算法( FIS-ES)

2. 1 理论依据

FIS-ES 算法与 Apriori 算法具有相同的理论依据, 即 Aprio-

·71·第 2 期刘德喜等: 一种新的频繁项集挖掘算法

















{

(

)

(

)

(

)

(

下载后可阅读完整内容，剩余3页未读，立即下载

weixin_39840914

粉丝: 436
资源: 1万+

FIS-ES算法：一种高效频繁项集挖掘新方法

最新资源