关联规则算法Apriori的学习与实现

x

100

} . Apriori

需要扫描数据库

100

次。

针对

Apriori

算法存在的缺点，

人们对

Apriori

算法进行了多方 面的改进，

希望能够找出一个

高效、可靠的挖掘频繁项集的算法 。这些算法大多是以

Apriori

为核心，或是其变体，或是

其扩展。如增量更新算法、并行算法等

下面是使用

Java

语言实现的

Apriori

算法，实现了

AprioriAlgorithm

类，包含了频繁项集的

挖掘过程和频繁关联规则的挖掘过程。

另外 ，有一个辅助类

ProperSubsetCombination

用于计算一个频繁项集的真子集，采用组合

原理，基于数值编码原理实现的组合求解 集合的真子集。

算法实现

（一）核心类

Apriori

算法的核心实现类为

AprioriAlgorithm

，实现的

Java

代码如下所示：

< br>

package ation;

import p;

import t;

import or;

import

import

import p;

public class AprioriAlgorithm {

private Map> txDatabase; //

事务数据库

private Float minSup; //

最小支持度

private Float minConf; //

最小置信度

private Integer txDatabaseCount; //

事务数据库中的事务数

private Map>> freqItemSet; //

频繁项集集合

private Map, Set>> assiciationRules; //

频繁关联规则集合

public AprioriAlgorithm(Map> txDatabase,Float minSup,Float minConf)

{

base = txDatabase;

= minSup;

f = minConf;

baseCount = ();

freqItemSet = new TreeMap>>();

assiciationRules = new HashMap, Set>>();

}

public Map, Float> getFreq1ItemSet() {

Map, Float> freq1ItemSetMap = new HashMap, Float>();

Map, Integer> candFreq1ItemSet = dFreq1ItemSet();

Iterator<, Integer>> it = et().iterator();

while(t()) {

, Integer> entry = ();

//

计算支持度

Float supported = new Float(ue().toString())/new Float(txDatabaseCount);

if(supported>=minSup) {

((), supported);

}

}

return freq1ItemSetMap;

}

public Map, Integer> getCandFreq1ItemSet() {

Map, Integer> candFreq1ItemSetMap = new HashMap, Integer>();

Iterator<>> it = et().iterator();

//

统计支持数，生成候选频繁

1-

项集

while(t()) {

> entry = ();

Set itemSet = ue();

for(String item : itemSet) {

Set key = new HashSet();

(());

if(!nsKey(key)) {

Integer value = 1;

(key, value);

}

else {

Integer value = 1+(key);

(key, value);

}

}

}

return candFreq1ItemSetMap;

}

public Set> aprioriGen(int m, Set> freqMItemSet) {

Set> candFreqKItemSet = new HashSet>();

Iterator> it = or();

Set originalItemSet = null;

while(t()) {

originalItemSet = ();

Iterator> itr = rator(originalItemSet, freqMItemSet);

while(t()) {

Set identicalSet = new HashSet(); //

两个项集相同元素的集合

(

集合的

交运算

)

(originalItemSet);

Set set = ();

All(set); // identicalSet

中剩下的元素是

identicalSet

与

set

< br>集合中公有的

元素

if(() == m-1) { // (k-1)-

项集中

k-2

个相同

Set differentSet = new HashSet(); //

两个项集不同元素的集合

(

集合

的差运算

)

(originalItemSet);

All(set); //

因为有

k-2

个相同，

则

differentSet

中一定剩下一个元素，

即

differentSet

大小为

1

(set); //

构造候选

k-

项 集的一个元素

(set

大小为

k-1, differentSet

大小

为

k)

(differentSet); //

< br>加入候选

k-

项集集合

}

}

}

return candFreqKItemSet;

}

private Iterator> getIterator(Set itemSet, Set> freqKItemSet)

{

Iterator> it = or();

while(t()) {

if((())) {

break;

}

}

return it;

}

public Map, Float> getFreqKItemSet(int k, Set> freqMItemSet) {

Map, Integer> candFreqKItemSetMap = new HashMap, Integer>();

//

调用

aprioriGen

方法，得到候选频繁

k-

项集

Set> candFreqKItemSet = iGen(k-1, freqMItemSet);

//

扫描事务数据库

Iterator<>> it = et().iterator();

//

统计支持数

while(t()) {

> entry = ();

Iterator> kit = or();

while(t()) {

Set kSet = ();

Set set = new HashSet();

(kSet);

All(ue()); //

候选频繁

k-

项集与事务数据库中元素做差元算

if(y()) { //

如果拷贝

set

为空，支持数加

1

if((kSet) == null) {

Integer value = 1;

(kSet, value);

}

else {

Integer value = 1+(kSet);

(kSet, value);

}

}

}

}

//

计算支持度，生成频繁

k-

项集，并返回

return support(candFreqKItemSetMap);

}