數據挖掘Apriori算法

數據挖掘（Data Mining）就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數據中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。挖掘的原始數據可以是結構化的，如關系數據庫中的數據；也可以是半結構化的，如文本、圖形和圖像數據；甚至是分布在網絡上的異構型數據。

數據挖掘的幾種主要形式:

規則挖掘：?

如果一個事務中含有X，則該事務中很可能含有Y。具體形式為{X}→{Y}，即通常可以描述為:當一個事務中顧客購買了一樣東西{啤酒}(這里X=“啤酒”)則很可能他同時還購買了{尿布}(這里Y= "尿布")，這就是關聯規則。

Apriori算法描述

Apriori算法采用的方法：首先產生頻繁1項集L₁，然后用L₁經過自連接、剪枝生成L₂（頻繁2-項集），然后L₂有生成L₃，依次迭代直到無法生成新的頻繁項集為止。然后根據給定的最小可信度，利用生成的頻繁項集產生強關聯規則。

第一階段：產生頻繁項集 該過程通過以下步驟實現：

（1）所有單獨的項都是候選項集C₁。任何支持度值比給定的最小支持度小的項都將從候選項集C₁中剔除，形成頻繁1-項集L₁。

（2）兩個通過自連接形成具有2個項的候選項集。通過再次掃描數據庫確定這些候選項的支持度。保留大于之前設定的最小支持度閾值的候選項，形成頻繁2-項集。

（3）下一步形成含有3個項的候選項集C₃，重復之前的操作直到無法生成新的頻繁項集為止。

代碼描述

# -*- coding: utf-8 -*- """ Apriori exercise. Created on Fri Nov 27 11:09:03 2015 @author: alexChen """ def loadDataSet():'''創建一個用于測試的簡單的數據集'''return [ [ 1, 3, 4 ], [ 2, 3, 5 ], [ 1, 2, 3, 5 ], [ 2, 5 ] ] def createC1( dataSet ):'''構建初始候選項集的列表，即所有候選項集只包含一個元素，C1是大小為1的所有候選項集的集合'''C1 = []for transaction in dataSet:for item in transaction:if [ item ] not in C1:C1.append( [ item ] )C1.sort()return map( frozenset, C1 ) def scanD( D, Ck, minSupport ):'''計算Ck中的項集在數據集合D(記錄或者transactions)中的支持度,返回滿足最小支持度的項集的集合，和所有項集支持度信息的字典。'''ssCnt = {}for tid in D:# 對于每一條transactionfor can in Ck:# 對于每一個候選項集can，檢查是否是transaction的一部分# 即該候選can是否得到transaction的支持if can.issubset( tid ):ssCnt[ can ] = ssCnt.get( can, 0) + 1numItems = float( len( D ) )retList = []supportData = {}for key in ssCnt:# 每個項集的支持度support = ssCnt[ key ] / numItems# 將滿足最小支持度的項集，加入retListif support >= minSupport:retList.insert( 0, key )# 匯總支持度數據supportData[ key ] = supportreturn retList, supportData if __name__ == '__main__':# 導入數據集myDat = loadDataSet()# 構建第一個候選項集列表C1C1 = createC1( myDat )# 構建集合表示的數據集 DD = map( set, myDat )# 選擇出支持度不小于0.5 的項集作為頻繁項集L, suppData = scanD( D, C1, 0.5 )print u"頻繁項集L：", Lprint u"所有候選項集的支持度信息：", suppData# Aprior算法 def aprioriGen( Lk, k ):'''由初始候選項集的集合Lk生成新的生成候選項集，k表示生成的新項集中所含有的元素個數'''retList = []lenLk = len( Lk )for i in range( lenLk ):for j in range( i + 1, lenLk ):L1 = list( Lk[ i ] )[ : k - 2 ];L2 = list( Lk[ j ] )[ : k - 2 ];L1.sort();L2.sort()if L1 == L2:retList.append( Lk[ i ] | Lk[ j ] )return retList def apriori( dataSet, minSupport = 0.5 ):# 構建初始候選項集C1C1 = createC1( dataSet )# 將dataSet集合化，以滿足scanD的格式要求D = map( set, dataSet )# 構建初始的頻繁項集，即所有項集只有一個元素L1, suppData = scanD( D, C1, minSupport )L = [ L1 ]# 最初的L1中的每個項集含有一個元素，新生成的# 項集應該含有2個元素，所以 k=2k = 2while ( len( L[ k - 2 ] ) > 0 ):Ck = aprioriGen( L[ k - 2 ], k )Lk, supK = scanD( D, Ck, minSupport )# 將新的項集的支持度數據加入原來的總支持度字典中suppData.update( supK )# 將符合最小支持度要求的項集加入LL.append( Lk )# 新生成的項集中的元素個數應不斷增加k += 1# 返回所有滿足條件的頻繁項集的列表，和所有候選項集的支持度信息return L, suppData

第二階段：產生關聯規則

從事務數據庫 D 中挖掘出頻繁所有的頻繁項集后，就可以比較容易的獲得相應的關聯規則，即滿足可信度> min_conf 的頻繁項集產生強關聯規則。由于規則是由頻繁項集產生，所以每個規則自動滿足最小支持度min_sup。使用頻繁項集X生成關聯規則。

代碼描述如下：

# 規則生成與評價 def calcConf( freqSet, H, supportData, brl, minConf=0.7 ):'''計算規則的可信度，返回滿足最小可信度的規則。freqSet(frozenset):頻繁項集H(frozenset):頻繁項集中所有的元素supportData(dic):頻繁項集中所有元素的支持度brl(tuple):滿足可信度條件的關聯規則minConf(float):最小可信度'''prunedH = []for conseq in H:conf = supportData[ freqSet ] / supportData[ freqSet - conseq ]if conf >= minConf:print freqSet - conseq, '-->', conseq, 'conf:', confbrl.append( ( freqSet - conseq, conseq, conf ) )prunedH.append( conseq )return prunedH def rulesFromConseq( freqSet, H, supportData, brl, minConf=0.7 ):'''對頻繁項集中元素超過2的項集進行合并。freqSet(frozenset):頻繁項集H(frozenset):頻繁項集中的所有元素，即可以出現在規則右部的元素supportData(dict):所有項集的支持度信息brl(tuple):生成的規則'''m = len( H[ 0 ] )# 查看頻繁項集是否大到移除大小為 m 的子集if len( freqSet ) > m + 1:Hmp1 = aprioriGen( H, m + 1 )Hmp1 = calcConf( freqSet, Hmp1, supportData, brl, minConf )# 如果不止一條規則滿足要求，進一步遞歸合并if len( Hmp1 ) > 1:rulesFromConseq( freqSet, Hmp1, supportData, brl, minConf ) def generateRules( L, supportData, minConf=0.7 ):'''根據頻繁項集和最小可信度生成規則。L(list):存儲頻繁項集supportData(dict):存儲著所有項集（不僅僅是頻繁項集）的支持度minConf(float):最小可信度'''bigRuleList = []for i in range( 1, len( L ) ):for freqSet in L[ i ]:# 對于每一個頻繁項集的集合freqSetH1 = [ frozenset( [ item ] ) for item in freqSet ]# 如果頻繁項集中的元素個數大于2，需要進一步合并if i > 1:rulesFromConseq( freqSet, H1, supportData, bigRuleList, minConf )else:calcConf( freqSet, H1, supportData, bigRuleList, minConf )return bigRuleList

第三階段，測試：

if __name__ == '__main__':# 導入數據集myDat = loadDataSet()# 選擇頻繁項集L, suppData = apriori( myDat, 0.5 )rules = generateRules( L, suppData, minConf=0.7 )print 'rules:\n', rules

總結

以上是生活随笔為你收集整理的数据挖掘Apriori算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。