1996 年，Toivonen 在文章《Sampling Large Databases for Association Rules》中提出了基於抽樣的頻繁項集挖掘算法——Sampling算法。他希望利用抽樣方式，從原數據集中抽取適量的樣本，以便將樣本直接放入記憶體中，接著再對樣本進行頻繁項集挖掘，以此減少挖掘時間。因為挖掘樣本變小了，所以能夠比較快速地得到頻繁項集。
基本介紹
- 中文名：Sampling算法
- 外文名：Sampling algorithm
- 領域：數據挖掘
- 目的：快速地得到頻繁項集
- 時間：1996
- 提出者：Toivonen
定義,頻繁項集挖掘,抽樣,單機挖掘算法,
定義
頻繁項集的挖掘工作需要花費大量的時間，主要是因為資料庫中的數據量非常龐大，加上需要多次掃描資料庫（尤其是 Apriori 及其改進算法），所以挖掘工作需要花費大量的時間。如果能有效地減少數據量，這樣就能提高挖掘的效率，基於這樣的考慮。Toivonen提出Sampling算法。Sampling算法屬於一種單機挖掘算法，對機器性能要求較低，採用抽樣方式從數據集中抽取一定數據的樣本，由於樣本數據較小，能較快得到頻繁項集。但是，由於採用抽樣技術，這必然會產生抽樣誤差，Toivonen也因此建議適量降低最小支持度以避免遺漏頻繁項集。Toivonen 提出的 Sampling 算法利用隨機抽樣進行樣本抽取，由於樣本數據量較小，所以挖掘所需的時間也就較短，提高了效率，因此它具有簡單高效的優點。但是，也是因為採用了隨機抽樣技術，這必然會結果帶來誤差，如果數據扭曲嚴重的話，會使得樣本不具有代表性，從而使挖掘結果與實際結果相差很大。
頻繁項集挖掘
頻繁項集挖掘是數據挖掘研究課題中一個很重要的研究基礎，它可以告訴我們在數據集中經常一起出現的變數，為可能的決策提供一些支持。頻繁項集挖掘是關聯規則、相關性分析、因果關係、序列項集、局部周期性、情節片段等許多重要數據挖掘任務的基礎。因此，頻繁項集有著很廣泛的套用，例如：購物藍數據分析、網頁預取、交叉購物、個性化網站、網路入侵檢測等。，對頻繁項集挖掘算法進行研究的方向大概可歸納為以下四個方面：一、在遍歷方向上採取自底向上、自頂向下以及混合遍歷的方式；二、在搜尋策略上採取深度優和先寬度優先策略；三、在項集的產生上著眼於是否會產生候選項集；四、在資料庫的布局上，從垂直和水平兩個方向上考慮資料庫的布局。對於不同的遍歷方式，資料庫的搜尋策略和布局方式將會產生不同的方法，研究表明，沒有什麼挖掘算法能同時對所有的定義域和數據類型都優於其他的挖掘算法，也就是說，對於每一種相對較為優秀的算法，它都有它具體的適用場景和環境。
抽樣
抽樣就是從研究總體中選取一部分代表性樣本的方法。例如我們要研究某城市居民的生活方式問題，那么整個城市居民都是我們的研究對象。但限於研究條件等原因，我們難以對每一個居民進行調查研究，而只能採用一定的方法選取其中的部分居民作為調查研究的對象，這種選擇調查研究對象的過程就是抽樣。採用抽樣法進行的調查就稱為抽樣調查。抽樣調查是最常用的調查研究方法之一，它已被廣泛套用到社會調查、市場調查和輿論調查等多個領域。
抽樣對調查研究來說至關重要。社會科學研究的對象通常是非常複雜的，涉及到社會生活的方方面面，既包括個體行動者，也包括群體甚至整個社區或社會。但在大多數情況下，我們難以對全部的對象做研究，而只能研究其中的一部分。對這部分研究對象的選擇就要依靠抽樣來完成，如此可以節省研究的成本和時間。但我們的研究又不是停留在所選取的樣本本身，而是通過對有代表性的樣本的分析來研究總體。故抽樣的目的，就是從研究對象總體中抽選一部分作為代表進行調查分析，並根據這一部分樣本去推論總體情況。
根據機率論原理常用的抽樣形式主要分為隨機抽樣和非隨機抽樣兩大類。二者的區別在於：前者按照隨機原則來抽取樣本，而後者不按隨機原則抽取樣本。
隨機抽樣
隨機抽樣又稱機率抽樣，是指嚴格按照隨機原則來抽取樣本，要求總體中每個單位都有被抽取的同等機會。由隨機抽樣所抽取的樣本稱為隨機樣本，這類樣本具有較高的代表性。隨機抽樣法又分為下列五種不同的抽樣方法：
簡單隨機抽樣，也稱純隨機抽樣，是指按照隨機原則從總體單位中直接抽取若干單位組成樣本。它是最基本的機率抽樣形式，也是其他幾種隨機抽樣方法的基礎。
等距隨機抽樣也稱機械隨機抽樣或系統隨機抽樣，是指按照一定的間隔，從根據一定的順序排列起來的總體單位中抽取樣本的一種方法。具體做法是：首先將總體各單位按照一定的順序排列起來，編上序號；然後用總體單位數除以樣本單位數得出抽樣間隔；最後採取簡單隨機抽樣的方式在第一個抽樣間隔內隨機抽取一個單位作為第一個樣本，再依次按抽樣間隔做等距抽樣，直到抽取最後一個樣本為止。
分層隨機抽樣，也稱類型隨機抽樣，是指首先將調查對象的總體單位按照一定的標準分成各種不同的類別(或組)，然後根據各類別(或組)的單位數與總體單位數的比例確定從各類別(或組)中抽取樣本的數量，最後按照隨機原則從各類(或組)中抽取樣本。
整群隨機抽樣，又稱聚類抽樣，是先把總體分為若干個子群，然後一群一群地抽取作為樣本單位。它通常比簡單隨機抽樣和分層隨機抽樣更實用，像後者那樣，它也需要將總體分成類群，所不同的是，這些分類標準往往是特殊的。具體做法是：先將各子群體編碼，隨機抽取分群數碼，然後對所抽樣本群或組實施調查。因此，整群抽樣的單位不是單個的分子，而是成群成組的。凡是被抽到的群或組，其中所有的成員都是被調查的對象。這些群或組可以是一個家庭、一個班級，也可以是一個街道、一個村莊。
分段隨機抽樣，也稱多段隨機抽樣或階段隨機抽樣，是一種分階段從調查對象的總體中抽取樣本進行調查的方法。它首先要將總體單位按照一定的標準劃分為若干群體，作為抽樣的第一級單位；再將第一級單位分為若干小的群體，作為抽樣的第二級單位；以此類推，可根據需要分為第三級或第四級單位。然後，按照隨機原則從第一級單位中隨機抽取若干單位作為第一級單位樣本，再從第一級單位樣本中隨機抽取若干單位作為第二級單位樣本，以此類推，直至獲得所需要的樣本。
非隨機抽樣
在實際的調查過程中，還有一類抽樣方法，稱之為非隨機抽樣，即它不是嚴格按照隨機原則抽取樣本，而是根據調查者的主觀經驗和主觀判斷選擇樣本的。
與隨機抽樣相比，雖然這類非隨機動抽樣的代表性差，提供的資料信息較零散，難以從樣本調查的結論中對總體做出準確的推斷。但是，由於它非常簡便易行，並能通過對樣本的調查而大致了解總體的某些情況，對調查研究工作很有啟發性。因此，它適用於那種調查對象的總體難以具體界定，以及不需要準確推斷總體情況的調查。常用非隨機抽樣的方法主要有以下幾種：
偶遇抽樣，也稱方便抽樣，是指調查者將自己在特定場合下偶然遇到的對象作為樣本的一種方法。如在商店門口、街頭路口、車站碼頭、公園廣場等公共場所，隨便選取某些顧客、行人、旅客、觀眾等作為樣本進行調查研究.這種方法比較簡單方便，適用於探索性研究，但樣本的代表性較差，具有很大的偶然性。
立意抽樣，也稱主觀抽樣，它是調查者根據自己的主觀印象、以往的經驗和對調查對象的了解來選取樣本的一種方法；這種抽樣適用於那些總體範圍較小、總體單位之間的差異較大的調查。
這種主觀抽樣所抽取的樣本是否具有代表性、所得出的結論是否準確，完全取決於調查者本人的判斷能力，以及對調查對象的了解程度。因此這種方法具有很大的主觀隨意性。但是當對總體狀況較為熟悉時，用這一抽樣法所選擇的樣本也有較高的代表性。例如當在們對某一群體作調查時，就可以根據我們所了解的群體情況選取某些樣本做研究。
配額抽樣，也稱定額抽樣，即調查者首先確定所要抽取樣本的數量，再按照一定的標準和比例分配樣本，然後從符合標準的對象中任意地抽取樣本。其方法類似於分層隨機抽樣，但它不是按照隨機原則抽取樣本。例如，我們可以根據研究目的，把總體按性別、民族等變數進行分組，然後分配相應的樣本數選取樣本。
這種配額抽樣比前兩種方法所抽取的樣本更有代表性，而且簡便易行，在民意調查中經常使用。但這種方法也具有很大的主觀隨意性和局限性，如蓋洛普採用此抽樣法曾幾次成功地預測了美國的總統大選，但在1948年總統選舉的民意調查中卻失敗了。人們有時把這一方法與隨機抽樣法結合起來使用，其效果會更好些。
滾雪球抽樣，即以少量樣本為基礎，逐漸擴大樣本的規模，直至找出足夠的樣本。此法適用於對調查總體不甚清楚的情況，常用於探索性的實地研究，特別適用於對小群體關係的研究。例如我們要了解某個人經常交往的社會圈子，就可以通過這個人提供的線索找到更多與他有關聯的人。其具體做法是，先找到一個或幾個符合研究目的的對象，然後再根據這些對象所提供的線索找另外相關的對象，依次進行，直至達到研究目的。但滾雪球抽樣法所選擇的樣本有時會有很大的隨意性和特殊性，因而代表性不高。
單機挖掘算法
關聯規則挖掘的整個過程主要分兩步來完成：第一步是找出資料庫中所有滿足最小支持度閾值的頻繁項集；第二步是由頻繁項集產生所有滿足最小置信度閾值的關聯規則。由於關聯規則挖掘的整體性能主要是由第一步的性能所決定，因此，關聯規則挖掘的關鍵和難點都集中在了頻繁項集的挖掘上。隨著關聯分析技術的不斷發展，眾多的研究學者提出了許多優秀的頻繁項集挖掘算法，包括單機（single-machine）挖掘算法、基於 MPI（Message Passing Interface）的挖掘算法、基於 Map Reduce 的挖掘算法和基於 Spark 的挖掘算法。
單機（single-machine）挖掘算法指的是運行在一台機器上的頻繁項集挖掘算法，它們的特點是數據量小，對機器的記憶體大小和計算性能要求不高，在一台機器上即可完成挖掘任務。一些經典的算法，如 Apriori 和 FP-growth 等經典的頻繁項集挖掘算法，都是單機頻繁項集挖掘算法。
