關聯規則簡介與apriori演算法

1. 關聯規則中Apriori演演算法的一個小問題

Apriori演算法可以歸為3個步驟，連接、剪枝和支持度計數。其實沒省略，你看Apriori的定義就知道，兩個k項集連接要求前k-1項相同才能連接。所以你說的{1,3}和{2,3}不能連接，只有{2,3}和{2,5}可以連接生成{2,3,5}.

2. 關聯規則的簡介

在描述有關關聯規則的一些細節之前，先來看一個有趣的故事： 尿布與啤酒的故事。
在一家超市裡，有一個有趣的現象：尿布和啤酒赫然擺在一起出售。但是這個奇怪的舉措卻使尿布和啤酒的銷量雙雙增加了。這不是一個笑話，而是發生在美國沃爾瑪連鎖店超市的真實案例，並一直為商家所津津樂道。沃爾瑪擁有世界上最大的數據倉庫系統，為了能夠准確了解顧客在其門店的購買習慣，沃爾瑪對其顧客的購物行為進行購物籃分析，想知道顧客經常一起購買的商品有哪些。沃爾瑪數據倉庫里集中了其各門店的詳細原始交易數據。在這些原始交易數據的基礎上，沃爾瑪利用數據挖掘方法對這些數據進行分析和挖掘。一個意外的發現是：跟尿布一起購買最多的商品竟是啤酒！經過大量實際調查和分析，揭示了一個隱藏在尿布與啤酒背後的美國人的一種行為模式：在美國，一些年輕的父親下班後經常要到超市去買嬰兒尿布，而他們中有30%～40%的人同時也為自己買一些啤酒。產生這一現象的原因是：美國的太太們常叮囑她們的丈夫下班後為小孩買尿布，而丈夫們在買尿布後又隨手帶回了他們喜歡的啤酒。 關聯規則最初提出的動機是針對購物籃分析(Market Basket Analysis)問題提出的。假設分店經理想更多的了解顧客的購物習慣。特別是，想知道哪些商品顧客可能會在一次購物時同時購買？為回答該問題，可以對商店的顧客事物零售數量進行購物籃分析。該過程通過發現顧客放入「購物籃」中的不同商品之間的關聯，分析顧客的購物習慣。這種關聯的發現可以幫助零售商了解哪些商品頻繁的被顧客同時購買，從而幫助他們開發更好的營銷策略。
1993年，Agrawal等人在首先提出關聯規則概念，同時給出了相應的挖掘演算法AIS，但是性能較差。1994年，他們建立了項目集格空間理論，並依據上述兩個定理，提出了著名的Apriori演算法，至今Apriori仍然作為關聯規則挖掘的經典演算法被廣泛討論，以後諸多的研究人員對關聯規則的挖掘問題進行了大量的研究。 根據韓家煒等觀點，關聯規則定義為：
假設是項的集合。給定一個交易資料庫D，其中每個事務(Transaction)t是I的非空子集，即，每一個交易都與一個唯一的標識符TID(Transaction ID)對應。關聯規則在D中的支持度(support)是D中事務同時包含X、Y的百分比，即概率；置信度(confidence)是D中事務已經包含X的情況下，包含Y的百分比，即條件概率。如果滿足最小支持度閾值和最小置信度閾值，則認為關聯規則是有趣的。這些閾值是根據挖掘需要人為設定。
基本概念表1：關聯規則的簡單例子 關聯規則挖掘過程主要包含兩個階段：第一階段必須先從資料集合中找出所有的高頻項目組(Frequent Itemsets)，第二階段再由這些高頻項目組中產生關聯規則(Association Rules)。
關聯規則挖掘的第一階段必須從原始資料集合中，找出所有高頻項目組(Large Itemsets)。高頻的意思是指某一項目組出現的頻率相對於所有記錄而言，必須達到某一水平。一項目組出現的頻率稱為支持度(Support)，以一個包含A與B兩個項目的2-itemset為例，我們可以經由公式(1)求得包含{A,B}項目組的支持度，若支持度大於等於所設定的最小支持度(Minimum Support)門檻值時，則{A,B}稱為高頻項目組。一個滿足最小支持度的k-itemset，則稱為高頻k-項目組(Frequent k-itemset)，一般表示為Large k或Frequent k。演算法並從Large k的項目組中再產生Large k+1，直到無法再找到更長的高頻項目組為止。
關聯規則挖掘的第二階段是要產生關聯規則(Association Rules)。從高頻項目組產生關聯規則，是利用前一步驟的高頻k-項目組來產生規則，在最小信賴度(Minimum Confidence)的條件門檻下，若一規則所求得的信賴度滿足最小信賴度，稱此規則為關聯規則。例如：經由高頻k-項目組{A,B}所產生的規則AB，其信賴度可經由公式(2)求得，若信賴度大於等於最小信賴度，則稱AB為關聯規則。 就沃爾馬案例而言，使用關聯規則挖掘技術，對交易資料庫中的紀錄進行資料挖掘，首先必須要設定最小支持度與最小信賴度兩個門檻值，在此假設最小支持度min_support=5% 且最小信賴度min_confidence=70%。因此符合此該超市需求的關聯規則將必須同時滿足以上兩個條件。若經過挖掘過程所找到的關聯規則「尿布，啤酒」，滿足下列條件，將可接受「尿布，啤酒」的關聯規則。用公式可以描述Support(尿布，啤酒)>=5%且Confidence(尿布，啤酒)>=70%。其中，Support(尿布，啤酒)>=5%於此應用範例中的意義為:在所有的交易紀錄資料中，至少有5%的交易呈現尿布與啤酒這兩項商品被同時購買的交易行為。Confidence(尿布，啤酒)>=70%於此應用範例中的意義為:在所有包含尿布的交易紀錄資料中，至少有70%的交易會同時購買啤酒。因此，今後若有某消費者出現購買尿布的行為，超市將可推薦該消費者同時購買啤酒。這個商品推薦的行為則是根據「尿布，啤酒」關聯規則，因為就該超市過去的交易紀錄而言，支持了「大部份購買尿布的交易，會同時購買啤酒」的消費行為。
從上面的介紹還可以看出，關聯規則挖掘通常比較適用與記錄中的指標取離散值的情況。如果原始資料庫中的指標值是取連續的數據，則在關聯規則挖掘之前應該進行適當的數據離散化（實際上就是將某個區間的值對應於某個值），數據的離散化是數據挖掘前的重要環節，離散化的過程是否合理將直接影響關聯規則的挖掘結果。

3. 有誰懂apriori演算法啊

經典Apriori演算法分兩部分：一是頻繁項的產生，二是根據頻繁項產生關聯規則；
重點的是第一部，會開銷很多時間；
其中頻繁項的產生又分成2部分：一是連接步，一是剪枝步；
推薦書籍；數據挖掘概念與技術
數據挖掘導論

這個頻繁項產生比較麻煩，文字打不清楚，不懂的再問我，我最近在做畢設。

4. apriori演算法是什麼

Apriori演算法是第一個關聯規則挖掘演算法，也是最經典的演算法。它利用逐層搜索的迭代方法找出資料庫中項集的關系，以形成規則，其過程由連接（類矩陣運算）與剪枝（去掉那些沒必要的中間結果）組成。該演算法中項集的概念即為項的集合。包含K個項的集合為k項集。項集出現的頻率是包含項集的事務數，稱為項集的頻率。如果某項集滿足最小支持度，則稱它為頻繁項集。

演算法應用

隨著高校貧困生人數的不斷增加，學校管理部門資助工作難度也越加增大。針對這一現象，提出一種基於數據挖掘演算法的解決方法。將關聯規則的Apriori演算法應用到貧困助學體系中，並且針對經典Apriori挖掘演算法存在的不足進行改進，先將事務資料庫映射為一個布爾矩陣，用一種逐層遞增的思想來動態的分配內存進行存儲，再利用向量求＂與＂運算，尋找頻繁項集。