1、nApriori算法是挖掘布爾關聯規則頻繁項集的算法nApriori算法利用頻繁項集性質的先驗知識（prior knowledge），通過逐層搜索的迭代方法，即將k-項集用于探察(k+1)-項集，來窮盡數據集中的所有頻繁項集。n先找到頻繁1-項集集合L1,然后用L1找到頻繁2-項集集合L2，接著用L2找L3，直到找不到頻繁k-項集，找每個Lk需要一次數據庫掃描。APRIORI算法nApriori算法利用的是Apriori性質：頻繁項集的所有非空子集也必須是頻繁的。n模式不可能比A更頻繁的出現nApriori算法是反單調的，即一個集合如果不能通過測試，則該集合的所有超集也不能通過相同的測試。nA

2、priori性質通過減少搜索空間，來提高頻繁項集逐層產生的效率算法應用n經典的關聯規則數據挖掘算法Apriori 算法廣泛應用于各種領域，通過對數據的關聯性進行了分析和挖掘，挖掘出的這些信息在決策制定過程中具有重要的參考價值。nApriori算法廣泛應用于商業中，應用于消費市場價格分析中，它能夠很快的求出各種產品之間的價格關系和它們之間的影響。通過數據挖掘，市場商人可以瞄準目標客戶，采用個人股票行市、最新信息、特殊的市場推廣活動或其他一些特殊的信息手段，從而極大地減少廣告預算和增加收入。百貨商場、超市和一些老字型大小的零售店也在進行數據挖掘，以便猜測這些年來顧客的消費習慣。nApriori算法

3、應用于網絡安全領域，比如時候入侵檢測技術中。早期中大型的電腦系統中都收集審計信息來建立跟蹤檔，這些審計跟蹤的目的多是為了性能測試或計費，因此對攻擊檢測提供的有用信息比較少。它通過模式的學習和訓練可以發現網絡用戶的異常行為模式。采用作用度的Apriori算法削弱了Apriori算法的挖掘結果規則，是網絡入侵檢測系統可以快速的發現用戶的行為模式，能夠快速的鎖定攻擊者，提高了基于關聯規則的入侵檢測系統的檢測性。nApriori算法應用于高校管理中。隨著高校貧困生人數的不斷增加，學校管理部門資助工作難度也越加增大。針對這一現象，提出一種基于數據挖掘算法的解決方法。將關聯規則的Apriori算法應用到貧

4、困助學體系中，并且針對經典Apriori挖掘算法存在的不足進行改進，先將事務數據庫映射為一個布爾矩陣，用一種逐層遞增的思想來動態的分配內存進行存儲，再利用向量求與運算，尋找頻繁項集。實驗結果表明，改進后的Apriori算法在運行效率上有了很大的提升，挖掘出的規則也可以有效地輔助學校管理部門有針對性的開展貧困助學工作。算法思想n該算法的基本思想是：首先找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然后由頻集產生強關聯規則，這些規則必須滿足最小支持度和最小可信度。然后使用第1步找到的頻集產生期望的規則，產生只包含集合的項的所有規則，其中每一條規則的右部只有一項，這里采用的是中規

5、則的定義。一旦這些規則被生成，那么只有那些大于用戶給定的最小可信度的規則才被留下來。為了生成所有頻集，使用了遞歸的方法。 算法實現Apriori算法利用頻繁項集性質的先驗知識（prior knowledge），通過逐層搜索的迭代方法，即將k-項集用于探察(k+1)-項集，來窮盡數據集中的所有頻繁項集。先找到頻繁1-項集集合L1,然后用L1找到頻繁2-項集集合L2，接著用L2找L3，直到找不到頻繁k-項集，找每個Lk需要一次數據庫掃描。nApriori算法由連接和剪枝兩個步驟組成。n連接：為了找Lk，通過Lk-1與自己連接產生候選k-項集的集合，該候選k項集記為Ck。nLk-1中的兩個元素L1和

6、L2可以執行連接操作 的條件是nCk是Lk的超集，即它的成員可能不是頻繁的，但是所有頻繁的k-項集都在Ck中（為什么？）。因此可以通過掃描數據庫，通過計算每個k-項集的支持度來得到Lk 。n為了減少計算量，可以使用Apriori性質，即如果一個k-項集的(k-1)-子集不在Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除。)1 1()22(.)22()1 1 (21212121klklklklllll21ll n算法：Apriori。使用逐層迭代方法基于候選產生找出頻繁項集。n輸入：nD:實物數據庫；nMin_sup:最小支持度計數閾值。n輸出：L：D中的頻繁項集。n方法：nL1=fin

7、d_frequent_1-itemsets(D);nfor(k=2;Lk-1 !=；k+)nCk=apriori_gen(Lk-1);nFor each 事務 tD/掃描D用于計數nCt=subset(Ck,t);/得到t的子集，它們是候選nfor each候選cC;nC.count+;nnLk=cC|c.count=min_stpnnreturn L=UkLk；Apriori偽代碼nProcedure apriori_gen(Lk-1:frequent(k-1)-itemsets)nfor each項集l1Lk-1nfor each項集l2Lk-1nIf (l11=l21) (l12=l22

8、) (l1k-2=l2k-2) (l1k-1=l2k-1) thennc=l1l2/連接步：產生候選nif has_infrequent_subset(c,Lk-1)thenndelete c;/剪枝部；刪除非頻繁的候選nelse add c to Ck；nnreturn Ck；nprocedure has_infrequent_subset (c:candidate k-itemset;nLk-1：frequent (k-1)-itemset)/使用先驗知識nfor each(k-1)-subset s of cnIf s Lk-1thennreturn TRUE;nreturn FALSE

9、;Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetA,B,CB, C, EItemsetsupB, C, E2n1 . 連接：nC3=L2 L2= A,C,B,C,B,

10、EC,E A,C,B,C,B,EC,E = A,B,C,A,C,E,B,C,En2使用Apriori性質剪枝：頻繁項集的所有子集必須是頻繁的，對候選項C3，我們可以刪除其子集為非頻繁的選項：nA,B,C的2項子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以刪除這個選項；nA,C,E的2項子集是A,C,A,E,C,E，其中A,E 不是L2的元素，所以刪除這個選項；nB,C,E的2項子集是B,C,B,E,C,E，它的所有2項子集都是L2的元素，因此保留這個選項。n3這樣，剪枝后得到C3=B,C,E從以上的算法執行過程可以看到Apriori算法的缺點:第一:在每一步產生侯選項目集時循環產

11、生的組合過多， 沒有排除不應該參與組合的元素;第二:每次計算項集的支持度時，都對數據庫D中的全部 記錄進行了一遍掃描比較，如果是一個大型的數據 庫的話，這種掃描比較會大大增加計算機系統的 I/O開銷。而這種代價是隨著數據庫的記錄的增加 呈現出幾何級數的增加。 因此人們開始尋求一種能減少這種系統1/O開銷的更為快捷的算法。Apriori算法的缺點改進Apriori算法的方法n方法1：基于hash表的項集計數n將每個項集通過相應的hash函數映射到hash表中的不同的桶中，這樣可以通過將桶中的項集技術跟最小支持計數相比較先淘汰一部分項集。n方法2：事務壓縮（壓縮進一步迭代的事務數）n不包含任何k-

12、項集的事務不可能包含任何(k+1)-項集，這種事務在下一步的計算中可以加上標記或刪除。n方法3：劃分n挖掘頻繁項集只需要兩次數據掃描nD中的任何頻繁項集必須作為局部頻繁項集至少出現在一個部分中。n第一次掃描：將數據劃分為多個部分并找到局部頻繁項集n第二次掃描：評估每個候選項集的實際支持度，以確定全局頻繁項集。n方法4：選樣（在給定數據的一個子集挖掘）n基本思想：選擇原始數據的一個樣本，在這個樣本上用Apriori算法挖掘頻繁模式n通過犧牲精確度來減少算法開銷，為了提高效率，樣本大小應該以可以放在內存中為宜，可以適當降低最小支持度來減少遺漏的頻繁模式n可以通過一次全局掃描來驗證從樣本中發現的模式

13、n可以通過第二此全局掃描來找到遺漏的模式n方法5：動態項集計數n在掃描的不同點添加候選項集，這樣，如果一個候選項集已經滿足最少支持度，則在可以直接將它添加到頻繁項集，而不必在這次掃描的以后對比中繼續計算方法4：選樣（在給定數據的一個子集挖掘）基本思想：選擇原始數據的一個樣本，在這個樣本上用Apriori算法挖掘頻繁模式通過犧牲精確度來減少算法開銷，為了提高效率，樣本大小應該以可以放在內存中為宜，可以適當降低最小支持度來減少遺漏的頻繁模式可以通過一次全局掃描來驗證從樣本中發現的模式可以通過第二此全局掃描來找到遺漏的模式方法5：動態項集計數在掃描的不同點添加候選項集，這樣，如果一個候選項集已經滿足

14、最少支持度，則在可以直接將它添加到頻繁項集，而不必在這次掃描的以后對比中繼續計算一種Apriori的改進算法實現在Apriori算法中，尋找最大項目集的基本思路是:第一步:簡單統計所有含一個元素的項目出現的頻率，并找出那些大于或等于最小支持度的項目集，產生一維頻繁項目集Lt。第二步:循環處理直到未能再產生維數更高的頻繁項目集。 循環過程是:在第k步中，根據k-1步生成的k-1維頻繁項目集來產生k維候選項目集，由于在產生k-1維頻繁項目集時，我們可以實現對該集中出現元素的個數進行計數處理，因此對某元素而言，若它的計數個數不到k-1的話，可以事先刪除該元素，從而排除由該元素將引起的大規格所有組合。第三步：按Apriori算法再檢驗新的K 維頻繁項目集的所有k-1維項目集是否已經包含在已經求出的K-1維頻繁項目集。若其中有一個沒有包含，則也可刪去該組合，這樣得到一個真正有用的K維頻繁項目集選項目集。第四步：得到了這個候選項目集后，可以對數據庫D的每一個事務tid進行掃描，若該事務中至少含有候選項目集CK中的一員，則保留該項事務，否則把該事物記錄與數據庫末端沒有作刪除標記的事務記錄對換，并對移到數據庫末端的事務記錄作刪除標一記，整個數據庫掃描完畢后為新的事務數據庫D 中。一種Aprio