有限掃描算法

在頻繁項集發現算法中，經常需要對每個不同規模的項集採用一遍掃描過程。如果記憶體太小以致無法容納數據和提供對某規模頻繁項集進行計數所需的空間，要計算所有頻繁項集似乎沒有辦法可以避免k遍掃描。有限掃描算法是指能夠在兩遍之內發現全部或大部分頻繁項集的算法。

基本介紹

• 中文名：有限掃描算法
• 外文名：Finite scanning algorithm
• 領域：數據挖掘
• 目的：發現頻繁項集
• 掃描次數：最多兩次

簡介

在數據挖掘中，有限掃描算法簡單來說對大規模項集最多進行兩次掃描就可以發現大部分頻繁項集的算法。常見的有限掃描算法有抽樣方法，即只利用數據樣本而不是全部數據集進行計算，以及SON算法和Toivonen算法，這兩種算法對項集只需掃描兩遍，可以得到一個精確解。

算法類型

SON算法

SON算法是Savasere等於1995 年提出的一種基於Apriori 算法的分區算法 ( partition algorithm) 。SON 算法的思想源於對於給定的項集只需要對整個事務數據集掃描一次即可得到其支持度，進而判斷其是否為頻繁項集。所以只需要找出一個項集的集合，使得這個集合包含事務數據集上所有的頻繁項集。SON 算法將事務數據集劃分為多個互不重疊的分區，然後分別在每個分區上計算出本分區的頻繁項集，最後將各個分區計算得到的結果匯總成一個項集的集合，該集合將包含事務數據集上所有的頻繁項集。SON 算法的正確性基於如果一個項集是全局頻繁的，那么該項集至少在一個分區中是局部頻繁的。

從以上分析容易看出，SON 算法對事務數據集進行了兩次掃描。第一次掃描，將生成一個項集的集合，該集合包含所有的頻繁項集； 第二次掃描，將對上一次掃描得到的每個項集進行計數，得到其支持度，根據最小支持度獲得最終的頻繁項集。算法的執行分為兩個階段。在階段一中，該算法將整個事務數據集邏輯上劃分為互不重疊的分區，每個分區互相獨立，分別為每個分區單獨的計算出本分區上的局部頻繁項集。最後，把所有分區上計算得到的局部頻繁項集匯總起來得到一個全局的候選項集。在階段二中，根據上一階段得到的候選項集，計算每個候選項集在整個事務數據集上的支持度，並以此判斷是否滿足最小支持度，從而得到最終的結果。

Toivonen算法

Toivonen算法首先在抽樣數據集上發現頻繁項集，但是採用的支持度閾值較低以保證在整個數據及上的頻繁項集的丟失幾率較低。下一步是檢查購物籃整個檔案，此時不僅要對所有樣本數據集上的頻繁項集計數，而且要對反例邊界（那些自己還沒發現頻繁但是其所有直接子集都頻繁的項集）上的項集計數。如果反例邊界上的人以及和都在整個數據集上不頻繁，那么結果是確切的。但是如果反例邊界上的一個集合被發現是頻繁的，那么需要在一個新的樣本數據集上重複整個處理過程。

接下來的問題是發現流中的頻繁項集，流和數據檔案的區別在於，流元素只有到達後才可用，並且通常情況下到達速率很高以至於無法存儲整個流來支持簡單查詢，另外，一個流會隨著時間推移而不斷變化，當前的頻繁項也許過段時間就不再頻繁。

而且流不會結束，只要某個項集反覆在流中出現，它最終都會超過支持度閾值。為了解決這個問題，我們將支持度閾值看成是項集出現的購物籃所占的比例。

發現流的頻繁項集需要對流進行抽樣，我們可以先收集一定量的購物籃並將它存為一個檔案，在該檔案上執行頻繁項集算法，然後這同時可以收集另外一個檔案，當第一次疊代完成且收集到的新購物籃流數據數目足夠時開始運行第二次疊代。定期從流中收集新的數據進行疊代，新的疊代進行，如果任一項集的購物籃出現的比例顯著低於比例閾值，則該項集可以從所有的頻繁項集集合中去掉，頻繁項集集合包含沒有被刪除的項集和新檔案中發現的頻繁項集。

抽樣方法

在統計學中，抽樣（Sampling）是一種推論統計方法，它是指從目標總體（Population，或稱為母體）中抽取一部分個體作為樣本（Sample），通過觀察樣本的某一或某些屬性，依據所獲得的數據對總體的數量特徵得出具有一定可靠性的估計判斷，從而達到對總體的認識。抽樣過程主要包括以下幾個階段：定義總體（母體）、確定抽樣框、確定抽樣方法、決定樣本量、實施抽樣計畫、抽樣與數據收集以及回顧抽樣過程。

目標是所要研究的對象的全體。例如，製造商檢查某個批次的產品質量是否合格，目標總體就是這一批次的產品。抽樣總體是用於從中抽取樣本的總體。按理，抽樣總體應該與目標總體一致，但實踐中時常發生不一致的情況。例如，科學家通過小白鼠試驗來檢測藥物用於人類總體的效果。

抽樣框，在抽樣之前，總體應劃分成抽樣單位，抽樣單位互不重疊且能合成總體，總體中的每個個體只屬於一個單位。抽樣框是一份包含所有抽樣單元的名單。

簡單隨機抽樣（simple random sampling），也叫純隨機抽樣。從總體N個單位中隨機地抽取n個單位作為樣本，使得每一個容量為樣本都有相同的機率被抽中。特點是：每個樣本單位被抽中的機率相等，樣本的每個單位完全獨立，彼此間無一定的關聯性和排斥性。簡單隨機抽樣是其它各種抽樣形式的基礎。通常只是在總體單位之間差異程度較小和數目較少時，才採用這種方法。

系統抽樣（systematic sampling），也稱等距抽樣。將總體中的所有單位按一定順序排列，在規定的範圍內隨機地抽取一個單位作為初始單位，然後按事先規定好的規則確定其他樣本單位。先從數字1到k之間隨機抽取一個數字r作為初始單位，以後依次取r+k、r+2k……等單位。這種方法操作簡便，可提高估計的精度。

分層抽樣（stratified sampling）。將抽樣單位按某種特徵或某種規則劃分為不同的層，然後從不同的層中獨立、隨機地抽取樣本。從而保證樣本的結構與總體的結構比較相近，從而提高估計的精度。

整群抽樣（cluster sampling）。將總體中若干個單位合併為組，抽樣時直接抽取群，然後對中選群中的所有單位全部實施調查。抽樣時只需群的抽樣框，可簡化工作量，缺點是估計的精度較差。

頻繁項集

項集：最基本的模式是項集，它是指若干個項的集合。頻繁模式是指數據集中頻繁出現的項集、序列或子結構。頻繁項集是指支持度大於等於最小支持度(min_sup)的集合。其中支持度是指某個集合在所有事務中出現的頻率。頻繁項集的經典套用是購物籃模型。

頻繁項集挖掘是數據挖掘研究課題中一個很重要的研究基礎，它可以告訴我們在數據集中經常一起出現的變數，為可能的決策提供一些支持。頻繁項集挖掘是關聯規則、相關性分析、因果關係、序列項集、局部周期性、情節片段等許多重要數據挖掘任務的基礎。因此，頻繁項集有著很廣泛的套用，例如：購物藍數據分析、網頁預取、交叉購物、個性化網站、網路入侵檢測等。

對頻繁項集挖掘算法進行研究的方向大概可歸納為以下四個方面：一、在遍歷方向上採取自底向上、自頂向下以及混合遍歷的方式；二、在搜尋策略上採取深度優和先寬度優先策略；三、在項集的產生上著眼於是否會產生候選項集；四、在資料庫的布局上，從垂直和水平兩個方向上考慮資料庫的布局。對於不同的遍歷方式，資料庫的搜尋策略和布局方式將會產生不同的方法，研究表明，沒有什麼挖掘算法能同時對所有的定義域和數據類型都優於其他的挖掘算法，也就是說，對於每一種相對較為優秀的算法，它都有它具體的適用場景和環境。所以，應該了解不同挖掘算法的不同特性和適用場景，掌握不同算法的適用環境和條件，這樣才可以使研究者清楚算法的改進點，明白自己的研究方向，從而使用戶更加方便地把算法套用到實際的生產活動中。

隨著大數據時代的到來，傳統的算法，比如 Apriori 算法、FP-growth 算法等，都無法處理這些處理大量的數據，主要原因有：一、時間消耗太大。面對大量數據，即使是比 Apriori快一個數量級的 FP-growth 算法，也無法在較短的時間內完成挖掘任務；二、記憶體無法滿足要求。由於 Apriori 算法（包括類 Apriori算法）需要產生大量的候選項集，所以在處理大量數據的時候，就會由於記憶體消耗殆盡而無法使算法繼續進行下去，即使是不需要生成候選項集的 FP-growth 算法，也會因為 FP-tree 太大無法放入記憶體，而使得算法無法運行。面對這樣的問題，眾多的研究學者開始著眼研究基於多處理器系統的並行頻繁項集挖掘算法，以及基於 Hadoop 等分散式集群的分散式頻繁項集挖掘算法。比如 Agrawal 等人 CD算法、DD 算法和 Ca D 算法，以及 Zaiane 等人的 MLFPT算法和 Li 等人的 PFP 算法等等，都是一些很優秀的並行或分散式頻繁項集挖掘算法。頻繁項集挖掘是數據挖掘研究領域中的一個重要課題，它是關聯規則、因果關係、相關性分析、情節片段、序列項集、局部周期性等許多數據挖掘任務的基礎。所以，頻繁項集有著廣泛的實際套用，例如：購物藍數據分析、網頁預取、交叉購物、個性化網站以及網路入侵檢測等。