尹士閃，馬增強(qiáng)，毛晚堆

（1.石家莊鐵道大學(xué) 教務(wù)處，河北 石家莊050043；2.石家莊鐵道大學(xué) 電氣與電子工程學(xué)院，河北 石家莊050043；3.石家莊鐵道大學(xué) 工程訓(xùn)練中心，河北 石家莊050043）

0 引 言

數(shù)據(jù)挖掘 （data mining）是一門交叉學(xué)科，是從存放在數(shù)據(jù)庫、數(shù)據(jù)倉庫或其它信息庫中的大量數(shù)據(jù)中挖掘有興趣知識的過程。關(guān)聯(lián)規(guī)則挖掘則是數(shù)據(jù)挖掘中最活躍的研究方法之一［1－3］。Agrawal等于1993年首先提出了關(guān)聯(lián)規(guī)則問題，隨后他們建立了項目集格空間理論，提出了著名的Apriori算法［4－14］。Apriori其核心算法就是根據(jù)頻集理論的一種逐層迭代搜索方法，通過項目集元素數(shù)目不斷增長來逐步完成頻繁項目集的發(fā)現(xiàn)。算法過程中需要多次掃描事務(wù)數(shù)據(jù)庫，并產(chǎn)生龐大的候選集來完成頻繁項目集的發(fā)現(xiàn)，如此大的候選集對時間和存儲空間都是一種挑戰(zhàn)。針對Apriori算法的這些缺點(diǎn)，近年來，許多學(xué)者對此提出了許多不同的算法。比較典型算法有DHP，Partition，Sampling，F(xiàn)P－tree。在這些研究基礎(chǔ)之上，本文提出了一個有效生成頻繁項目集的算法，它是采用一種鏈?zhǔn)酱鎯Y(jié)構(gòu)用來存儲頻繁項目集，并生成最大頻繁項目集，通過改變事務(wù)的存儲方式和增加鏈?zhǔn)酱鎯Ψ绞侥軌蚋咝У纳勺畲箢l繁項目集，避免了多次掃描事務(wù)數(shù)據(jù)庫，減少了龐大的候選集的生成，從而提高了效率。

1 關(guān)聯(lián)規(guī)則基本概念及理論

定義1（項目） 關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)集記作D（D為事務(wù)數(shù)據(jù)庫），D＝ ｛t1，t2，…，tn｝，tk＝ ｛i1，i2，…，ij｝（k＝1，2，…，n）為一條事務(wù)；tk中的元素ij（j＝1，2，…，p）稱為項目 （Item）。

定義2（項目集） 設(shè)I＝ ｛i1，i2，…，im｝是事務(wù)數(shù)據(jù)庫D中全體項目組成的集合，I的任何子集X稱為D的項目集 （Itemset），｜X｜＝k稱集合X為k項目集。設(shè)tk和X分別為D中的事務(wù)和項目集，如果X tk，稱事務(wù)tk包含項目集X。

定義3（規(guī)則的支持度） 事務(wù)數(shù)據(jù)庫D中包含項目集X的事務(wù)數(shù)稱為項目集X的支持?jǐn)?shù)，記為δx。項目集X的支持率，記作：Support（X），即概率P（X），support（X）＝δx/｜D｜×100%。

定義4（規(guī)則的可信度） 規(guī)則A→B具有可信度C，表示C是包含A項集的同時也包含B項集，相對于包含A項集的百分比，這是條件概率P（B/A）。

定義5（頻繁項目集） 如果一個k－項目集，它的支持度≥minsup（最小支持度），則稱該k－項目集為頻繁k－項目集。

定義6（最大頻繁項目集） 如果一項目集X是頻繁的，并且不存在任意項目集Y（XY），使得Y是事務(wù)集D的頻繁項目集，則稱項目集X為事務(wù)集D的最大頻繁項目集。

由以上的定義可以看出，任何頻繁項目集都是某一最大頻繁項目集的子集，最大頻繁項目集包含所有頻繁項目集，且項目集的規(guī)模要小幾個數(shù)量級，所以可以把發(fā)現(xiàn)頻繁項目集的問題轉(zhuǎn)化為發(fā)現(xiàn)最大頻繁項目集的問題。

理論1 如果X是頻繁項目集，那么X的任何非空子集都是頻繁項目集。

理論2 如果X是非頻繁項目集，那么X的任何超集都是非頻繁項目集。

2 關(guān)聯(lián)規(guī)則算法的基本思想

為了便于本文關(guān)聯(lián)規(guī)則算法的論述，把基于頻繁項目集鏈?zhǔn)酱鎯Ψ椒ǖ年P(guān)聯(lián)規(guī)則算法簡稱為CSSFI算法。

2.1 Apriori的基本思想

Apriori算法所采用的是逐層迭代搜索方法，通過項目集元素數(shù)目不斷增長來逐步完成頻繁項目集發(fā)現(xiàn)的。首先產(chǎn)生1－頻繁項目集L1，然后是2－頻繁項目集L2，直到頻繁項目集為空時算法停止。在第k次循環(huán)中，過程先產(chǎn)生k－1－候選項目集的集合Ck－1，然后通過掃描數(shù)據(jù)庫生成支持度并測試產(chǎn)生k－頻繁項目集Lk。每次找出一個Lk，就需要掃描數(shù)據(jù)庫一次。

在第一遍掃描中，計算單個項目的支持度，確定哪些項目是頻繁項目，即它們需具有最小支持度。在后來的掃描中，均將前一次掃描得到的頻繁項目作為基礎(chǔ)項目，利用這個基礎(chǔ)項目產(chǎn)生出新的頻繁項目集，這樣的頻繁項目集稱作候選項目集，并且在掃描數(shù)據(jù)的過程中計算這些候選項目集的實際支持度計數(shù)。掃描結(jié)束后，確定哪些候選項目集才是真正的頻繁項目，然后將是頻繁項目的這些候選項目集作為下一次掃描用的基礎(chǔ)項目。重復(fù)此過程直到?jīng)]有新的頻繁項目集產(chǎn)生為止。

2.2 CSSFI算法的基本思想

CSSFI算法主要針對Apriori算法中的兩點(diǎn)不足進(jìn)行改進(jìn)，這兩點(diǎn)不足如下：

（1）多次掃描事務(wù)數(shù)據(jù)庫，需要很大的I/O負(fù)載：對每次k循環(huán)，候選集Ck中的每個元素都必須通過掃描數(shù)據(jù)庫一次來驗證其是否加入Lk。假如一個頻繁大項目集包含10個項，那么就至少需要掃描事務(wù)數(shù)據(jù)庫10遍。

（2）產(chǎn)生龐大的過渡候選項目集：由Lk－1產(chǎn)生k－候選集Ck是指數(shù)增長的，例如104個1－頻繁項目集就有可能產(chǎn)生接近107個元素的2－候選項目集。如此大的候選集對時間和主存空間都是一種挑戰(zhàn)。

CSSFI算法通過改變事務(wù)數(shù)據(jù)庫中事務(wù)的存儲方式，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲頻繁項目集，并生成最大頻繁項目集，通過這種方法能夠減小掃描事物數(shù)據(jù)庫的次數(shù)和生成候選集的數(shù)量，克服了Apriori算法的瓶頸，從而減少了生成最大頻繁項目集的時間，提高了算法的效率。

3 CSSFI算法的實現(xiàn)過程

生成最大頻繁項目集算法共分3步，分別為：①變更事務(wù)數(shù)據(jù)庫存儲和表達(dá)方式，初始化存儲鏈表，生成項目集和頻繁1－項目集；②構(gòu)造頻繁項目集鏈表；③根據(jù)頻繁項目集的定義及性質(zhì)，對候選項目集鏈表進(jìn)行處理，生成最大頻繁項目集。

3.1 初始化階段

把事務(wù)數(shù)據(jù)庫中的事務(wù)轉(zhuǎn)化成比特向量表達(dá)方式。即，在一個事物中出現(xiàn)第i個項目，則把對應(yīng)項目的比特向量置為1，否則置為0。例如，項目集I＝ ｛A，B，C，D，E，F(xiàn)｝，事務(wù)數(shù)據(jù)庫 T＝ ｛（ADE）， （BCD）， （ABCD），（BEF）｝，轉(zhuǎn)化為比特向量表達(dá)式為 T＝ ｛（100110），（011100），（11110）， （010011）｝，同時，生成有序1―項目集，計算各個項目的支持度，按支持度從大到小進(jìn)行排序，假設(shè)最小支持度為2，則生成頻繁1―項目集為I1＝｛（B，3），（D，3），（A，2），（C，2），（E，2），（F，1）｝，把最小主持度小于2的都去掉，實際上，頻繁1―項目集為I1＝ ｛（B，3），（D，3），（A，2），（C，2），（E，2）｝，如表1為事務(wù)數(shù)據(jù)庫，表2為頻繁1―項目集。

表1 事務(wù)數(shù)據(jù)庫

表2 頻繁1―項目集

3.2 構(gòu)造頻繁項目集鏈表

經(jīng)過初始化階段之后，進(jìn)入構(gòu)造頻繁項目集鏈表階段。具體方法為：掃描一遍事務(wù)數(shù)據(jù)庫T，選取頻繁項目集中支持度最小的頻繁項目，如果事務(wù)中包含此頻繁項目，則將此事務(wù)作為鏈表信息加入到該頻繁項目對應(yīng)的鏈表中，否則檢查是否包含支持度較小的頻繁項目，如果包含，將此事務(wù)加入到此頻繁項目對應(yīng)的鏈表中，以此類推，直到遍歷整個事務(wù)數(shù)據(jù)庫結(jié)束。在把事務(wù)加入到該頻繁項目對應(yīng)的鏈表的同時，把該事務(wù)中包含其他頻繁項目出現(xiàn)次數(shù)加1。如圖1是頻繁項目集初始鏈表結(jié)構(gòu)。

圖1 頻繁項目集初始鏈表結(jié)構(gòu)

3.3 生成最大頻繁項目集

設(shè)最大頻繁項目集M為空，從支持度最小的頻繁項目鏈表出發(fā)，檢查除此頻繁項目以外其它頻繁項目出現(xiàn)的次數(shù)，如果他們出現(xiàn)的次數(shù)都大于或等于此頻繁項目的支持?jǐn)?shù)，則把這些頻繁項目 （包含此支持度最小的頻繁項目）進(jìn)行組合，生成所有頻繁項目集并加入到最大頻繁項目集M中，程序結(jié)束；否則將那些出現(xiàn)次數(shù)大于或等于最小支持度的頻繁項目 （包含此支持度最小的頻繁項目）組合生成頻繁項目集，同時加入頻繁項目集M中，然后，對支持度最小的頻繁項目鏈表進(jìn)行處理，即把項目集鏈表中所有事務(wù)對應(yīng)此頻繁項目的比特向量置為0，對處理后的事務(wù)，按照構(gòu)造頻繁項目集鏈表的方法分別插入到其它的頻繁項目集鏈表中；以此類推進(jìn)行循環(huán)，直到程序結(jié)束，生成最大頻繁項目集M。

例如，從事務(wù)數(shù)據(jù)庫T中生成所有最小支持度為2的最大頻繁項目集，首先從支持度最小的頻繁項目E開始，頻繁項目集E的鏈表中包含兩個事務(wù) （100110）和（010011），而其他頻繁項目C、A、D、B出現(xiàn)的次數(shù)為0，1，1，1，沒有頻繁項目出現(xiàn)的次數(shù)和E的支持度相同，支持度也小于minsup（最小支持度），不能生成頻繁項目集。接著從事務(wù) （100110）和 （010011）中去掉E項目，變?yōu)椋?00100）和 （010001），然后按照生成頻繁項目集鏈表的方法，將他們插入到頻繁項目C、A、D、B鏈表中，這樣包含較小支持度C的事務(wù)為 （01100）和 （111100），頻繁項目A、D、B出現(xiàn)的次數(shù)為1，2，2，D和B與C出現(xiàn)的次數(shù)相同，但另外一個項目的支持度小于minsup，因此生成頻繁項目集 ｛（C、D），（C、B），（D、B），（C、D、B）｝，按同樣的方法生成頻繁項目集 ｛（A、D）｝，最后合并生成最大頻繁項目集 ｛（A、D），（C、D），（C、B），（D、B），（C、D、B）｝，具體過程如下：

（1）處理支持度最小的頻繁項目E（見圖2）。

圖2 處理頻繁項目E鏈表

（2）處理支持度較小的頻繁項目C（見圖3）。

圖3 處理頻繁項目C鏈表

生成頻繁項目集 ｛（C、D）， （C、B）， （D、B）， （C、D、B）｝。

（3）處理的頻繁項目A （見圖4）。

圖4 處理頻繁項目A 鏈表

生成頻繁項目集 ｛（A、D）｝，程序結(jié)束。

最后生成最大頻繁項目集 ｛（A、D）， （C、D）， （C、B），（D、B），（C、D、B）｝。

3.4 算法的程序?qū)崿F(xiàn)

本算法采用類語言的方式進(jìn)行了描述，具體程序如下：

/＊變量說明部分＊/

N：事務(wù)數(shù)據(jù)庫中事務(wù)總數(shù)；

M：項目數(shù)；

minsup：最小支持度；

I［M］：存儲項目集；

L［］：頻繁項目集鏈表；

max＿fi［］［］：存儲最大頻繁項目集

L［］struct

｛

item ［］ char［］//頻繁項目名稱

item＿sup ［］ int［］//對應(yīng)item在此鏈表事務(wù)中出現(xiàn)的次數(shù)

tran［］ char［］//存儲包含此頻繁項目的事務(wù)，鏈表

L＿leng［］ int //鏈表長度

｝//L ［0］為頻繁1－項目集

T ［］：事務(wù)數(shù)據(jù)庫

/＊初始化階段：把事務(wù)用比特向量方式存儲＊/

For（j＝1；j＜＝N；j＋＋）do

begin

Begin

While i＜＝M do

begin

i＋＋；

if I ［i］∈T ［j］then b ［i］＝1；I ［i］.

count＋＋；//count為項目I［i］的支持度

else b ［i］＝0

end

T ［j］＝b；/＊b以比特向量方式存儲T ［j］＊/

end

/＊生成頻繁1－項目集＊/

for all I ［i］do begin

if I［i］.count＞＝minsup then

L ［0］.item ［j］［1］＝I［i］；

L ［0］.item＿sup ［j］［1］＝I［i］.count；j＋＋；

else i＋＋

end

L ［0］＝sort（L ［0］）/＊把頻繁1－項目集進(jìn)行排序，按支持度的大小從小到大進(jìn)行排序，支持度相同時按字典順序進(jìn)行排序＊/

/＊構(gòu)造頻繁項目集鏈表＊/

L ［1］＝L ［0］

For（i＝1；i＜＝N；i＋＋）do

begin

for j＝1to｜L ［1］.item ［］［1］｜j＋＋do

begin

if L ［1］.item ［j］［1］∈T ［i］then begin

/＊把包含此頻繁項目的事務(wù)加入到對應(yīng)的鏈表中＊/

L［1］.tran ［j］［］＝ L［1］.tran ［j］［］∪T ［i］；

L［1］.L＿sup ［j］［1］＋＋；//把對應(yīng)的item＿sup ［j］＋1

Insert（L ［1］.item ［j］，T ［i］）/＊把 T［i］中其他項目加入到L ［1］.item ［j］中，同時把對應(yīng)的item＿sup ［j］［2，3，4，…］＋1＊/

end

end

end

/＊生成最大頻繁項目集＊/

C［］：臨時存儲頻繁項目集

While（遍歷L1，k＝1，k＜＝｜L ［1］｜）

Begin

temp＿i＝L ［1］.item＿sup ［k］［1］

c ［1］＝L ［1］.item ［k］［1］

/＊選出此頻繁項目鏈表中其他項目出現(xiàn)次數(shù)大于等于此頻繁項目支持度的項目＊/

For i＝2to i＜＝｜L ［1］.item｜do

begin

if L ［1］.item＿sup ［k］［i］＞＝temp＿i then

Begin

c＝c∪L ［1］.Item ［k］［i］

end

end

delete （L ［1］.tan ［k］，c ［1］）//刪除此鏈表事務(wù)中此頻繁項目

max＿fi［k］＝Combination （c）//把c中項目進(jìn)行任意組合，結(jié)果加入最大頻繁項目集max＿fi中；

if temp＿i＞＝｜c(diǎn)｜ then begin break；//程序結(jié)束

else insert（L ［1］，L ［1］.tan ［k］）//把刪除此頻繁項目的事務(wù)加入到其他頻繁項目鏈表中，再進(jìn)行最大頻繁項目集的搜尋

end end

4 實驗結(jié)果及分析

本文使用Intel（R）Core（TM）2duo CPU 2.93GHz，2.0GB內(nèi)存的微機(jī)，對Apriori算法和DHP算法及CSSFI算法在產(chǎn)生候選集數(shù)量和運(yùn)行時間上進(jìn)行了對比實驗，所用數(shù)據(jù)集來源于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫［15］，共10個數(shù)據(jù)集，如表3所示。

表3 數(shù)據(jù)集

當(dāng)最小支持度為0.5時，表4，表5表示產(chǎn)生的候選集數(shù)量和運(yùn)行時間對比表。

表4 3種算法產(chǎn)生的候選集數(shù)

實驗結(jié)果表明，在10個測試數(shù)據(jù)集中，CSSFI算法在集中的7個數(shù)據(jù)集上產(chǎn)生的候選集數(shù)量少于其它兩種算法，在其中的7個數(shù)據(jù)集上運(yùn)行時間地獄其它兩種算法，這是由于CSSFI算法產(chǎn)生的候選集有大幅度的減少的結(jié)果。當(dāng)最大頻繁項目集的項目數(shù)越大時，CSSFI算法的效率顯得越突出。

表5 3種算法的運(yùn)行時間

5 結(jié)束語

本文提出了一種基于頻繁項目集鏈?zhǔn)酱鎯Ψ椒ǖ年P(guān)聯(lián)規(guī)則算法 （CSSFI），該算法采用比特向量方式存儲事務(wù)和建立頻繁項目集鏈表，通過處理頻繁項目集鏈表生成最大頻繁項目集，并用類語言對算法進(jìn)行了程序?qū)崿F(xiàn)。從和Apriori算法和DHP算法的比較結(jié)果來看，CSSFI算法的效率得到了很大的提高，從而證明了CSSFI算法是可行的、有效的。在對CSSFI算法的仔細(xì)分析和研究基礎(chǔ)上，發(fā)現(xiàn)該算法在數(shù)據(jù)庫容量擴(kuò)容時，性能有所下降，這是在以后的研究中需要繼續(xù)探討的問題。

［1］CHEN Wenwei.The data warehouse and data mining ［M］.Beijing：Tsinghua University Press，2006：143－155 （in Chinese）.［陳文偉.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘教程 ［M］.北京：清華大學(xué)出版社，2006：143－155.］

［2］MAO Guojun.Data mining：Principle and algorithm ［M］.Beijing：Tsinghua University Press，2005：5－6 （in Chinese）.［毛國君.數(shù)據(jù)挖掘原理與算法 ［M］.北京：清華大學(xué)出版社，2005：5－6.］

［3］ZHANG Ke，ZHANG Xiaogang.Data mining algorithm and engineering application ［M］.Beijing：Mechanical Industry Press，2006：50－61 （in Chinese）.［章兢，張小剛.數(shù)據(jù)挖掘算法及其工程應(yīng)用 ［M］.北京：機(jī)械工業(yè)出版社，2006：50－61.］

［4］DUAN Yang－guang，WEI Yu－ke.Algorithm for mining frequent patterns based on circular orthogonal linked list ［J］.Computer Technology and Development，2009，19 （10）：73－77（in Chinese）.［段仰廣，偉玉科.基于循環(huán)十字鏈表的頻繁模式挖掘算法 ［J］.計算機(jī)技術(shù)與發(fā)展，2009，19 （10）：73－77.］

［5］ZHANG Guanglu，LEI Jingsheng.An improved Apriori algorithm for mining association rules ［J］.Computer Technology and Development，2010，20 （6）：84－92 （in Chinese）.［張廣路，雷景生.一種改進(jìn)的Apriori關(guān)聯(lián)規(guī)則挖掘算法 ［J］.計算機(jī)技術(shù)與發(fā)展，2010，20 （6）：84－92.］

［6］WANG Hua，HU Xuegang.Mining algorithm of maximal frequent itemsets suitable to specific database ［J］.Computer Engineering，2008，34 （14）：63－65 （in Chinese）.［王華，胡學(xué)鋼.特定數(shù)據(jù)最大頻繁集挖掘算法 ［J］.計算機(jī)工程，2008，34 （14）：63－65.］

［7］PAN Yi－ting，HANG Hong－juan.An improved maximal frequent itemsets mining algorithm ［J］.Computer Engineering and Science，2009，31 （8）：63－65 （in Chinese）. ［潘益婷，張紅娟.一種改進(jìn)的最大頻繁項目集挖掘算法 ［J］.計算機(jī)工程與科學(xué)，2009，31 （8）：63－65.］

［8］YANG Yu，WANG Yong.Optimized method for mining maximum frequent itemsets ［J］.Computer Engineering and Applications，2006，42 （31）：171－173 （in Chinese）. ［唐瑜，王勇.挖掘最大頻繁項集的優(yōu)化方法 ［J］.計算機(jī)工程與應(yīng)用，2006，42 （31）：171－173.］

［9］SHANG Zhigang，YIN Shaohong.Research of mining maximum frequent itemsets based on dynamic programming ［J］.Computer ＆ Digital Engineering，2009，37 （10）：51－54 （in Chinese）.［尚志剛，尹紹宏.基于動態(tài)規(guī)劃的最大頻繁項目集挖掘研 究 ［J］.計算機(jī) 與 數(shù) 字 工 程，2009，37 （10）：51－54.］

［10］ZHU Ye，YE Gaoying.Improvement of Apriori algorithm in association rule mining ［J］.Modern Electronic Technique，2008，31 （18）：78－80 （in Chinese）. ［朱燁，葉高英.關(guān)聯(lián)規(guī)則挖掘Apriori算法的改進(jìn) ［J］.現(xiàn)代電子技術(shù)，2008，31（18）：78－80.］

［11］QIU Chang－chun.On the association rules of 1wining algorithm containing item constraint ［J］.Journal of Hubei Institute of Education，2006，23 （8）：21－23 （in Chinese）. ［邱長春.基于項目約束的關(guān)聯(lián)規(guī)則挖掘方法的研究 ［J］.湖北教育學(xué)院學(xué)報，2006，23 （8）：21－23.］

［12］ MA Li－sheng.Fast algorithm for mining frequent itemsets［J］.Computer Engineering and Design，2009，30 （8）：1903－1906（in Chinese）.［馬麗生.快速挖掘頻繁項目集算法［J］.計算機(jī)工程與設(shè)計，2009，30 （8）：1903－1906.］

［13］LI Yun，LI Qing－shan.Algorithm for mining constrained maximal frequent itemsets ［J］.Computer Engineering and Applications，2007，43 （17）：160－163 （in Chinese）. ［李蕓，李青山.基于約束的最大頻繁項集挖掘算法 ［J］.計算機(jī)工程與應(yīng)用，2007，43 （17）：160－163.］

［14］FENG Feng.A Fast Updating Alogrithm for mining maximum frequent itemsets［J］.Journal of Hefei University，2007，17（4）：46－49 （in Chinese）.［馮鳳.快速更新挖掘最大頻繁項集 ［J］.合肥學(xué)院學(xué)報，2007，17 （4）：46－49.］

［15］David Aha.UCI Machine learning repository：Center for machine learning and intelligent systems ［DB］.http：//archive.ics.uci.edu/ml/datasets.html，2010.