AprioriAll 算法

算法簡介

Aprioriall算法被廣泛的套用到顧客購買行為的分析，網路訪問模式的分析，科學試驗的分析，疾病治療的早起診斷，自然災害的預測，DNA序列的破譯等。

AprioriAll算法，在每一次掃描(pass) 資料庫時,利用上一次掃描時產生的大序列生成候選序列,並在掃描的同時計算它們的支持度( support) ,滿足支持度的候選序列作為下次掃描的大序列。第1 次掃描時,長度為1 的頻繁序列模式作為初始的大1 —序列。具體步驟如下：

1) 排序階段利用客戶標識customer 2id作為主關鍵字以及事務發生的時間transaction 2 time作為次關鍵字對資料庫D排序,該步驟將原始的事務資料庫轉換成客戶序列的資料庫.

2) 發現頻繁項集階段利用關聯規則挖掘算法找出所有的頻繁項目集.

3) 轉換階段在已經轉換的客戶序列中,每一個事務被包含於該事物中的所大項目集來替換,如果一個序列不包含任何大項目集,則在已經轉換的序列中不應該保留這項事務.

4) 序列階段利用核心算法找出所有的序列模式.

AprioriAll算法

輸入：大項集階段轉換後的序列資料庫

輸出：所有最長序列

(1) L1={large1- sequence}；//大項集階段得到的結果

(2) For（k=2；Lk-1≠0；k++）do begin

(3) Ck=Candidate – generate（Lk-1）//Ck是從Lk-1中產生的新的候選者

(4) For each customer – sequence c in thedatabase do//對資料庫中的每一個顧客序列c

(5) Increment the count of all candidates in Ck that arecontained in c；//對包含於c中Ck內的所有候選者計數

(6) Lk=Candidates in Ckwithminimumsuport；//Lk為Ck中滿足最小支持度的候選者

(7) End

(8) Answer=Maximal Sequences in ∪kLk

其中候選集生成算法Ck=Candidate –generate（Lk-1）如下：

輸入：所有的大（k – 1）序列的集合

輸出：候選Ck

(1) Insert into Ck//首先進行Lk-1與Lk-1的連線運算

select p.litemset1,…,p.litemseti-1,q.litemseti-1

from LK-1p,Lk-1q//p和q是Lk-1 中兩個不同的序列串

wherep.litemset1=q.litemset1,…,

p.litemsetk-2=q.litemsetk-2;