【数据挖掘】数据挖掘总结 ( 模式挖掘 | Apriori 算法 | 支持度 | 置信度 | 关联规则 ) ★★

2023-03-28 20:32:33 浏览数 (1)

文章目录

  • 一、 支持度 置信度
  • 二、 频繁项集
  • 三、 非频繁项集
  • 四、 Apriori 算法过程
  • 五、模式挖掘示例

一、 支持度 置信度

给定

rm X , Y

两个项集 , 并且有

rm X geq Y

;

支持度 :

rm X Rightarrow Y

的支持度是

rm X , Y

两个项集在数据库

rm D

中 同时出现的概率 , 即

rm Pr(X cup Y)

置信度 :

rm X Rightarrow Y

的置信度度是

rm X

出现的前提下 ,

rm Y

项集在数据库

rm D

中同时出现的概率 , 即

rm Pr(Y|X) = cfrac{Pr(X cup Y)}{Pr(X)}

一般情况下 置信度 大于 支持度 ;

支持度用于找出 频繁项集 ;

置信度用于找出 关联规则 ;

二、 频繁项集

项集

rm X

的 支持度

rm support(X)

, 大于等于 指定的 最小支持度阈值

rm minsup

,

则称该 项集

rm X

为 频繁项集 ,

又称为 频繁项目集 ;

三、 非频繁项集

项集

rm X

的 支持度

rm support(X)

, 小于 指定的 最小支持度阈值

rm minsup

,

则称该 项集

rm X

为 非频繁项集 ,

又称为 非频繁项目集 ;

四、 Apriori 算法过程

原始数据集

rm D

,

1

项集

rm C_1

,

2

项集

rm C_2

,

cdots

,

rm k

项集

rm C_k

, 这些项集都是候选项集 ,

根据 原始数据集

rm D

, 创造

1

项集

rm C_1

, 然后对

rm C_1

执行 数据集扫描函数 , 找到其中的 频繁

1

项集

rm L_1

,

根据 频繁

1

项集

rm L_1

, 创造

2

项集

rm C_2

, 然后对

rm C_2

执行 数据集扫描函数 , 找到其中的 频繁

2

项集

rm L_2

,

vdots

根据 频繁

rm k-1

项集

rm L_{k-1}

, 创造

rm k

项集

rm C_k

, 然后对

rm C_k

执行 数据集扫描函数 , 找到其中的 频繁

rm k

项集

rm L_k

,

参考博客 : 【数据挖掘】关联规则挖掘 Apriori 算法 ( Apriori 算法过程 | Apriori 算法示例 )

五、模式挖掘示例

如下事物数据库 , 最小支持度

rm 60%

, 最小置信度

rm 80%

;

TID

Item

T1

{ M , O , N , K , E , Y } rm { M, O, N , K, E, Y } {M,O,N,K,E,Y}

T2

{ D , O , N , K , E , Y } rm { D, O, N , K, E, Y } {D,O,N,K,E,Y}

T3

{ M , A , K , E } rm { M, A , K, E } {M,A,K,E}

T4

{ M , U , C , K , Y } rm { M, U, C , K, Y } {M,U,C,K,Y}

T5

{ C , O , O , K , I , E } rm { C, O, O , K, I , E } {C,O,O,K,I,E}

rm { M, O, N , K, E, Y }

T2

rm { D, O, N , K, E, Y }

T3

rm { M, A , K, E }

T4

rm { M, U, C , K, Y }

T5

rm { C, O, O , K, I , E }

( 1 ) 使用 Apriori 算法找出所有频繁项集 ;

( 2 ) 写出关联规则 ;

( 1 ) 使用 Apriori 算法找出所有频繁项集 :

根据原始数据集

rm D

创造

1

项集

rm C_1

, 如下 :

Item

支持度

{ A } rm { A } {A}

20 % rm 20% 20%

{ C } rm { C } {C}

40 % rm 40% 40%

{ E } rm { E } {E}

80 % rm 80% 80%

{ I } rm { I } {I}

20 % rm 20% 20%

{ K } rm { K } {K}

80 % rm 80% 80%

{ M } rm { M } {M}

60 % rm 60% 60%

{ N } rm { N } {N}

40 % rm 40% 40%

{ O } rm { O } {O}

60 % rm 60% 60%

{ U } rm { U } {U}

20 % rm 20% 20%

{ Y } rm { Y } {Y}

60 % rm 60% 60%

rm { A }
rm 20%
rm { C }
rm 40%
rm { E }
rm 80%
rm { I }
rm 20%
rm { K }
rm 80%
rm { M }
rm 60%
rm { N }
rm 40%
rm { O }
rm 60%
rm { U }
rm 20%
rm { Y }
rm 60%

对

1

项集

rm C_1

执行数据集扫描函数 , 找到频繁

1

项集

rm L_1

, 即筛选出支持度大于等于

rm 60%

的

1

项集 :

Item

支持度

{ E } rm { E } {E}

80 % rm 80% 80%

{ K } rm { K } {K}

80 % rm 80% 80%

{ M } rm { M } {M}

60 % rm 60% 60%

{ O } rm { O } {O}

60 % rm 60% 60%

{ Y } rm { Y } {Y}

60 % rm 60% 60%

rm { E }
rm 80%
rm { K }
rm 80%
rm { M }
rm 60%
rm { O }
rm 60%
rm { Y }
rm 60%

根据 频繁

1

项集

rm L_1

创造

2

项集

rm C_2

, 如下 :

Item

支持度

{ E , K } rm { E , K } {E,K}

80 % rm 80% 80%

{ E , M } rm { E, M } {E,M}

40 % rm 40% 40%

{ E , O } rm { E,O } {E,O}

60 % rm 60% 60%

{ E , Y } rm { E,Y } {E,Y}

40 % rm 40% 40%

{ K , M } rm { K,M } {K,M}

40 % rm 40% 40%

{ K , O } rm { K,O } {K,O}

60 % rm 60% 60%

{ K , Y } rm { K,Y } {K,Y}

60 % rm 60% 60%

{ M , O } rm { M,O } {M,O}

20 % rm 20% 20%

{ M , Y } rm { M,Y } {M,Y}

40 % rm 40% 40%

{ O , Y } rm { O,Y } {O,Y}

40 % rm 40% 40%

rm { E , K }
rm 80%
rm { E, M }
rm 40%
rm { E,O }
rm 60%
rm { E,Y }
rm 40%
rm { K,M }
rm 40%
rm { K,O }
rm 60%
rm { K,Y }
rm 60%
rm { M,O }
rm 20%
rm { M,Y }
rm 40%
rm { O,Y }
rm 40%

对

2

项集

rm C_2

执行数据集扫描函数 , 找到频繁

2

项集

rm L_2

, 即筛选出支持度大于等于

rm 60%

的

2

项集 :

Item

支持度

{ E , K } rm { E , K } {E,K}

80 % rm 80% 80%

{ E , O } rm { E,O } {E,O}

60 % rm 60% 60%

{ K , O } rm { K,O } {K,O}

60 % rm 60% 60%

{ K , Y } rm { K,Y } {K,Y}

60 % rm 60% 60%

rm { E , K }
rm 80%
rm { E,O }
rm 60%
rm { K,O }
rm 60%
rm { K,Y }
rm 60%

根据 频繁

2

项集

rm L_2

创造

3

项集

rm C_3

, 如下 :

Item

支持度

{ E , K , O } rm { E , K, O } {E,K,O}

60 % rm 60% 60%

{ E , O , Y } rm { E,O , Y} {E,O,Y}

40 % rm 40% 40%

{ K , O , Y } rm { K,O , Y} {K,O,Y}

40 % rm 40% 40%

rm { E , K, O }
rm 60%
rm { E,O , Y}
rm 40%
rm { K,O , Y}
rm 40%

对

3

项集

rm C_3

执行数据集扫描函数 , 找到频繁

3

项集

rm L_3

, 即筛选出支持度大于等于

rm 60%

的

3

项集 :

Item

支持度

{ E , K , O } rm { E , K, O } {E,K,O}

60 % rm 60% 60%

rm { E , K, O }
rm 60%

最终得出结果 :

频繁

1

项集 :

rm {E},{K},{M},{O},{Y},

频繁

2

项集 :

rm {E,K},{E,O},{K,O},{K,Y}

频繁

3

项集 :

rm {E,K,O}

( 2 ) 写出关联规则 ;

置信度大于等于

rm 80%

就说明有关联规则 ;

基于 频繁

2

项集

rm L_2

的关联规则 :

​

置信度

E ⇒ K rm E Rightarrow K E⇒K

E K E = 4 4 = 1 rm cfrac{EK}{E} = cfrac{4}{4} = 1 EEK​=44​=1

K ⇒ E rm K Rightarrow E K⇒E

E K K = 4 5 = 0.8 rm cfrac{EK}{K} = cfrac{4}{5} = 0.8 KEK​=54​=0.8

E ⇒ O rm E Rightarrow O E⇒O

E O E = 3 4 = 0.75 rm cfrac{EO}{E} = cfrac{3}{4} = 0.75 EEO​=43​=0.75

O ⇒ E rm ORightarrow E O⇒E

E O O = 3 3 = 1 rm cfrac{EO}{O} = cfrac{3}{3} = 1 OEO​=33​=1

K ⇒ O rm K Rightarrow O K⇒O

K O K = 3 5 = 0.6 rm cfrac{KO}{K} = cfrac{3}{5} = 0.6 KKO​=53​=0.6

O ⇒ K rm O Rightarrow K O⇒K

K O O = 3 3 = 1 rm cfrac{KO}{O} = cfrac{3}{3} = 1 OKO​=33​=1

K ⇒ Y rm K Rightarrow Y K⇒Y

E K E = 3 5 = 0.6 rm cfrac{EK}{E} = cfrac{3}{5} = 0.6 EEK​=53​=0.6

Y ⇒ K rm Y Rightarrow K Y⇒K

E K E = 3 3 = 1 rm cfrac{EK}{E} = cfrac{3}{3} = 1 EEK​=33​=1

rm E Rightarrow K
rm cfrac{EK}{E} = cfrac{4}{4} = 1
rm K Rightarrow E
rm cfrac{EK}{K} = cfrac{4}{5} = 0.8
rm E Rightarrow O
rm cfrac{EO}{E} = cfrac{3}{4} = 0.75
rm ORightarrow E
rm cfrac{EO}{O} = cfrac{3}{3} = 1
rm K Rightarrow O
rm cfrac{KO}{K} = cfrac{3}{5} = 0.6
rm O Rightarrow K
rm cfrac{KO}{O} = cfrac{3}{3} = 1
rm K Rightarrow Y
rm cfrac{EK}{E} = cfrac{3}{5} = 0.6
rm Y Rightarrow K
rm cfrac{EK}{E} = cfrac{3}{3} = 1

基于 频繁

3

项集

rm L_3

的关联规则 :

​

置信度

E ⇒ K , O rm E Rightarrow K,O E⇒K,O

E K O E = 3 4 = 0.75 rm cfrac{EKO}{E} = cfrac{3}{4} = 0.75 EEKO​=43​=0.75

K , O ⇒ E rm K,O Rightarrow E K,O⇒E

E K O K O = 3 3 = 1 rm cfrac{EKO}{KO} = cfrac{3}{3} = 1 KOEKO​=33​=1

K ⇒ E , O rm K Rightarrow E,O K⇒E,O

K E O K = 3 5 = 0.6 rm cfrac{KEO}{K} = cfrac{3}{5} = 0.6 KKEO​=53​=0.6

E , O ⇒ K rm E,ORightarrow K E,O⇒K

E O K E O = 3 3 = 1 rm cfrac{EOK}{EO} = cfrac{3}{3} = 1 EOEOK​=33​=1

O ⇒ E , K rm O Rightarrow E,K O⇒E,K

O E K O = 3 4 = 0.75 rm cfrac{OEK}{O} = cfrac{3}{4} = 0.75 OOEK​=43​=0.75

E , K ⇒ O rm E,K Rightarrow O E,K⇒O

E K O E K = 3 4 = 0.75 rm cfrac{EKO}{EK} = cfrac{3}{4} = 0.75 EKEKO​=43​=0.75

rm E Rightarrow K,O
rm cfrac{EKO}{E} = cfrac{3}{4} = 0.75
rm K,O Rightarrow E
rm cfrac{EKO}{KO} = cfrac{3}{3} = 1
rm K Rightarrow E,O
rm cfrac{KEO}{K} = cfrac{3}{5} = 0.6
rm E,ORightarrow K
rm cfrac{EOK}{EO} = cfrac{3}{3} = 1
rm O Rightarrow E,K
rm cfrac{OEK}{O} = cfrac{3}{4} = 0.75
rm E,K Rightarrow O
rm cfrac{EKO}{EK} = cfrac{3}{4} = 0.75

根据置信度

rm geq 80%

关联规则有 :

rm L_2

关联规则 :

rm E Rightarrow K

,

rm K Rightarrow E

,

rm ORightarrow E

,

rm O Rightarrow K

,

rm Y Rightarrow K

;

rm L_3

关联规则 :

rm K,O Rightarrow E

,

rm E,ORightarrow K

;

数据挖掘 数据库 函数 数据 算法

0 人点赞