1、隨著大數(shù)據(jù)時代的來臨以及數(shù)據(jù)集容量的迅速增長，基于并行/分布式計算的頻繁模式挖掘相比受內存和節(jié)點限制的傳統(tǒng)技術在處理海量數(shù)據(jù)集時有較為明顯的優(yōu)勢。正是處于當前的背景下，本研究論文提出一個有效的基于隨機抽樣的關聯(lián)分析算法用來從大規(guī)模數(shù)據(jù)集內發(fā)現(xiàn)近似頻繁項集。
　　本算法的核心在于選擇一個數(shù)據(jù)集的隨機樣本來挖掘近似頻繁項集。標準的Apriori和FP-Growth算法往往需要多次掃描整個數(shù)據(jù)集來找到具體的頻繁項集，對于極大數(shù)據(jù)集而言，

2、這必然會付出相當高的存儲和計算代價。為了更有效地進行大數(shù)據(jù)集挖掘，本文提出兩個新的基于隨機抽樣的技術從事務型數(shù)據(jù)集樣本中提取高質量的近似頻繁項集，并且給予較高的概率保證該近似項集是數(shù)據(jù)集內真實頻繁項集的超集。
　　其中一個方法應用計算學習理論中的經(jīng)驗Rademacher復雜度，結合集中不等式，來推導出一個基于數(shù)據(jù)集樣本經(jīng)驗Rademacher復雜度的近似上界，進而運用統(tǒng)計學習理論中的相關結論來找到項集絕對頻率誤差上確界的一個近似上

3、界。另一個方法則直接利用經(jīng)典的Bernstein不等式的變形來限定項集的絕對頻率誤差。然后將PAC學習框架應用于這兩種頻繁項集抽樣方法的分析中，通過頻繁項集的(ε,δ)-近似來推導出各自的滿足PAC樣本完整性的近似樣本邊界，最后算法根據(jù)該邊界值選取相應的數(shù)據(jù)集樣本來挖掘近似頻繁項集。
　　自頻繁項集發(fā)現(xiàn)問題被提出以來，后續(xù)有許多文獻致力于研究基于抽樣技術的頻繁項集發(fā)現(xiàn)方法。同時隨著單機串行計算瓶頸的出現(xiàn)，越來越多的研究工作開展基于

4、并行/分布式計算平臺的頻繁項集發(fā)現(xiàn)任務。本研究論文的擴展實驗既采用真實的retail數(shù)據(jù)集，也包括人造數(shù)據(jù)集T10I4D100K，分別從數(shù)據(jù)集樣本挖掘實驗中返回的近似頻繁項集的召回率，準確率以及頻率誤差估計三方面來評估方法的正確性，同時從串行計算（基于單機）和并行計算（基于Hadoop偽分布式平臺）兩方面綜合評估方法的運行時間，最后對提出的不同的理論方法的性能以及對樣本空間的需求進行了對比。
　　根據(jù)目前所了解的知識情況，本研究首

5、次將經(jīng)驗Rademacher復雜度以及Bernstein不等式應用于基于抽樣技術的頻繁項集發(fā)現(xiàn)問題中，并利用統(tǒng)計學習中的相關結論推導出相對緊湊的理論樣本邊界，該邊界相比現(xiàn)有的Riondato和Upfal提出的基于VC維的頻繁項集發(fā)現(xiàn)理論樣本邊界更為緊湊，因而具有更優(yōu)的執(zhí)行效率。同時，我們研究方法建議的樣本復雜度是近似誤差倒數(shù)1/ε和置信參數(shù)倒數(shù)1/δ的多項式函數(shù)，故而也是PAC可學習的。我們采用計算學習理論中一些經(jīng)典的概念和技術來解決一