網站首頁 編程語言 正文
摘要：
主要是講解一些數據挖掘中頻繁模式挖掘的Apriori算法原理應用實踐
當我們買東西的時候，我們會發現物品展示方式是不同，購物以后優惠券以及用戶忠誠度也是不同的，但是這些來源都是大量數據的分析，為了從顧客身上獲得盡可能多的利潤，所以需要用各種技術來達到目的。
通過查看哪些商品一起購物可以幫助商店了解客戶的購買行為。這種從大規模數據集中尋找物品間的隱含關系被稱為關聯分析或者關聯規則學習。尋找物品的不同組合用蠻力算法的話效率十分底下，所以需要用智能的方法在時間范圍內尋找頻繁項集。
關聯分析
關聯規則學習是在大規模數據集中尋找有趣關系的任務。這些關系可以有兩種形式：頻繁項集或者關聯規則。頻繁項是經常出線一起物品集合，而關聯規則暗示兩種物品之間存在很強的關系。
{葡萄酒，尿布，豆奶}就是頻繁項集，而尿布->葡萄酒就是關聯規則。
商家可以更好的理解顧客。
而頻繁的定義是什么？就是支持度和可信度
支持度是：數據集中包含這個項的比例。{豆奶} 支持度4/5 {豆奶，尿布}支持度為3/5
可信度：是針對關聯規則定義的。{尿布]->{葡萄酒} 為 支持度（{A,B}）/支持度({A})。根據這兩種衡量方法，但是當物品成千上萬的時候如何計算這種組合清單呢？
Apriori原理
比如四種商品，我們考慮商品的組合問題：
我們目標是尋找一起購買的商品集合。我們使用集合的支持度來度量出現的頻率。隨著物品數目的增加我們比如有N種商品那么就有2^N-1種項集的組合。為了降低計算時間，發現了一種Apriori原理。
Apriori原理：如果某個項集是頻繁的，那么它所有的子集也是頻繁的。
推論：如果一個項集是非頻繁的，那么所i有超集也是非頻繁的。
我們用圖來表示就是：
陰影{2,3}是非頻繁的，那么{0,2,3},{1,2,3},{0,1,2,3}也是非頻繁的。一旦計算出{2,3}的支持度，知道是非頻繁的了。就不用計算{0,2,3],{1,2,3},{0,1,2,3}避免了指數增長。
算法實現
Apriori算法是發現頻繁項集的一種方法，對于兩個輸出參數分別是最小支持度和數據集。首先生成所有單個物品的項目列表，然后查看那個項目集滿足最小支持度。接下把不滿足的去掉。將剩下的合并成為2個兩素項集。重復繼續去掉不滿足最小支持度的項集。
對于數據集的每條交易記錄tran
對于每個候選can:
- 檢查can是否是tran子集
- 增加計數
對每個候選can:
- 如果支持度不小于最小保留
返回所有頻繁項集
代碼如下：
我們先實現兩個函數。一個是最開始生成C1候選集的函數。另外一個是從候選集中選出滿足支持度的頻繁集
def createC1(dataset):
C1=[]
for transaction in dataset:
for item in transaction:
if not [item] in C1:#如果不在項集中
C1.append([item])
C1.sort()
#可以作為key值
return map(frozenset,C1)#每個元素是一個frozenset
#滿足要求的構成L1,然后L1組合成為C2。進一步過濾成為L2
#frozenset可以作為key值
def scanD(D,Ck,minSupport):
#先在記錄中查看所有候選集的次數
ssCnt = {}
for td in D:
for can in Ck:
if can.issubset(td):#如果是那個集合的子集
if not ssCnt.has_key(can):ssCnt[can]=1
else:ssCnt[can]+=1
numCount = len(D)#記錄的總數
#記錄每個項集的支持度
supportData={}
retList=[]
for key in ssCnt.iterkeys():
support = float(ssCnt[key]*1.0/numCount)
if support>=minSupport:
retList.insert(0,key)#加入滿足條件的項集合的序列
supportData[key] = support
return retList,supportData
?測試這兩個函數如下：
x = apriori.loadDataSet()
C1 = apriori.createC1(x)#frozenset每個元素
print C1
#構建事物集
D = map(set,x)#每個元素是集合
L1,supportData0 = apriori.scanD(D,C1,0.5)
print L1得到如下結果：
[frozenset([1]), frozenset([2]), frozenset([3]), frozenset([4]), frozenset([5])][frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])]
而整體算法如下：
當集合項個數大于0時候
- 構建一個K個項組成的候選列表
- 檢查是否每個項集是頻繁的
- 保留頻繁的并且構建K+1項的候選項列表
#前面K-1x項目相同的時候可以生成Lk
def aprioriGen(Lk,k):
#前面k-1項目相同就可以合成
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i+1,lenLk):
L1 = list(Lk[i])[:k-2]#可以考慮1個元素的時候是0直接合并
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):
C1 = createC1(dataset)
D = map(set,dataset)
L1,supportData = scanD(D,C1,minSupport)
L = [L1]
k = 2#項集為2
#頻繁n-1項目總數為
while(len(L[k-2])>0):#因為項集存的位置是0
Ck = aprioriGen(L[k-2],k)
Lk,supK = scanD(D,Ck,minSupport)
supportData.update(supK)#加入字典更新
L.append(Lk)#L+1
k+=1#當空集的時候退出
return L,supportData測試如下：
dataSet = apriori.loadDataSet()
L,supportData = apriori.apriori(dataSet,minSupport=0.7)
print L我們可以獲得如下的頻繁項集
[[frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([2, 5])], []]
挖掘關聯規則
要找到關聯規則。首先需要從頻繁項集開始。我們知道集合中元素是不重復的，但是我們想基于這些元素獲得其他內容。某個元素或者某個元素的集合可以推導另外一個元素。
關聯規則也可以想頻繁項集一樣量化。頻繁項集是需要滿足最小支持度的要求。
對于關聯規則我們就可以用可信度來衡量。一條規則的可信度為P->H定義為support{P|h}/support(P)其實也就是P條件下H的概率滿足最小可信度就是關聯規則
如果某條規則不滿足最小可信度的要求。假設{0,1,2}->{3}不滿足最小可信度的要求。
那么任何{0,1,2}的子集也不會滿足最小可信度的要求。可以利用這個規則來 減少需要測試的規則數目。利用Apriori算法，進行首先從一個頻繁項集合開始，創建一個規則列表。
規則右部包含一個元素，然后對這些規則測試。接下來合并所有剩余 規則來創建一個新的規則列表，其中規則的右部包含兩個元素。這種方法稱為分級法。
#規則生成函數
def generateRules(L,supportData,minConf=0.7):
bigRuleList=[]
for i in range(1,len(L)):#只獲取兩個或者更多的頻繁項集合
for freqSet in L[i]:
H1 = [frozenset([item]) for item in freqSet]#將每個元素拆出來這個是右邊被推出的項集
if (i>1):
rulesFromConseq()
else:
calcConf(freqSet,H1,supportData,bigRuleList,minConf)
return bigRuleList
#計算可信度
def calcConf(freqSet,H,supportData,brl,minConf=0.7):
prunedH = []
for conseq in H:
conf = supportData[freqSet]/supportData[freqSet-conseq]#獲得條件概率（freq-conseq) -> conseq
if conf>=minConf:
print freqSet-conseq,'--->',conseq,'conf:',conf
brl.append((freqSet-conseq,conseq,conf))#加入這個元祖
prunedH.append(conseq)#為后面準備。因為若不滿足規則右邊該元素基礎下添加也不會滿足
return prunedH
#最初的規則生成更多的規則
def rulesFromConseq(freqSet,H,supportData,brl,minConf=0.7):
m = len(H[0])
if (len(freqSet)>(m+1)):#一直到該頻繁項集能包含的右邊推出等于項的個數-1為止例如{1，2，3，4}當{1}-{2,3,4}以后此時H[0]長度為3
Hmp1 = aprioriGen(H,m+1)#右邊推出過程類似生成過程
Hmp1 = calcConf(freqSet,Hmp1,supportData,brl,minConf)#過濾過程返回被推出的右邊的項集的集合
if (len(Hmp1)>1):#若有新規則生成繼續遞歸處理
rulesFromConseq(freqSet,Hmp1,supportData,brl,minConf)測試如下：
#生成所有頻繁項集合
dataSet = apriori.loadDataSet()
L,supportData = apriori.apriori(dataSet,minSupport=0.5)
#生成規則
rules = apriori.generateRules(L,supportData,minConf=0.5)
calcConf中輸出的結果如下：
frozenset([3]) ---> frozenset([1]) conf: 0.666666666667
frozenset([1]) ---> frozenset([3]) conf: 1.0
frozenset([5]) ---> frozenset([2]) conf: 1.0
frozenset([2]) ---> frozenset([5]) conf: 1.0
frozenset([3]) ---> frozenset([2]) conf: 0.666666666667
frozenset([2]) ---> frozenset([3]) conf: 0.666666666667
frozenset([5]) ---> frozenset([3]) conf: 0.666666666667
frozenset([3]) ---> frozenset([5]) conf: 0.666666666667
frozenset([5]) ---> frozenset([2, 3]) conf: 0.666666666667
frozenset([3]) ---> frozenset([2, 5]) conf: 0.666666666667
frozenset([2]) ---> frozenset([3, 5]) conf: 0.666666666667
利用Apriori算法解決實際問題
發現國會投票的模式
加州大學的機器學習數據集合有一個1984年起的國會投票記錄的數據集： 這個數據集合比較老。可以嘗試一些新的數據。其中一個組織是投票工程。提供了一個公共的API。
下面是如何收集數據的過程 而數據獲取過程比較繁瑣。以及鍵值對映射可以看《機器學習實戰》這本書。
我們主要針對已經獲取的txt文本來進行挖掘
構建投票記錄的數據集：
我們希望最后的數據集合格式是每一行代表美國國會的一個成員，每一列是投票的對象。
from votesmart import votesmartvotesmart.apikey = 'a7fa40adec6f4a77178799fae4441030'#votesmart.apikey = 'get your api key first'
現在假設將議案的標題以及ID號保存為recent100bills.txt文件，可以通過getBill來獲取每條議案的內容。
如果要獲取每條議案的投票信息用getBillActionVotes() 上面都是該API提供的功能。我們主要是針對數據的預處理階段。我們需要將BillId轉換成actionID
#只保留包含投票數據的actionId
def getActionIds():
fr = open('recent20bills.txt')
actionIdList=[];billTitleList=[]
for line in fr.readlines():
billNum = int(line.split('\t')[0])
try:
billDetail = votesmart.votes.getBill(billNum)#獲取議案對象
for action in billDetail.actions:
if action.level=='House' and \
(action.stage=='Passage' or \
action.stage=='Amendment Vote'):
actionId = int(action.actionId)
actionIdList.append(actionId)
billTitleList.append(line.strip().split('\t')[1])
except:
print "problem gettin bill %d"%billNum
sleep(1)
return actionIdList,billTitleList我們獲得的是類似Bill:12939 has actionId:34089這樣的信息。我們需要頻繁模式挖掘的話，需要將上面信息轉換成項集或者交易數據庫的東西。一條交易記錄只有一個項出線還是沒出現的信息，并不包含出現的次數。
美國有兩個主要政黨：共和和民主。我們可以將這個特征編碼為0和1.然后對投票.
#基于投票數據的事物列表填充函數
def getTransList(actionIdList,billTitleList):
itemMeaning = ['Republican','Democratic']
for billTitle in billTitleList:
itemMeaning.append('%s -- Nay'%billTitle)
itemMeaning.append('%s -- Yea' % billTitle)
#創建事務字典
transDict = {}
voteCount = 2# 0,1是所屬黨派。2開始是被第幾次投票
for actionId in actionIdList:
sleep(3)
print 'getting votes for actionId: %d' %actionId
try:
voteList = votesmart.votes.getBillActionVotes(actionId)
for vote in voteList:
if not transDict.has_key(vote.candidateName):
transDict[vote.candidateName] = []
if vote.officeParties =='Democratic':
transDict[vote.candidateName].append(1)
elif vote.officeParties=='Republican':
transDict[vote.candidateName].append(0)
if vote.action=='Nay':
transDict[vote.candidateName].append(voteCount)
elif vote.action=='Yea':
transDict[vote.candidateName].append(voteCount+1)
except:
print "problem getting actionId:%d" %actionId
voteCount+=2
return transDict,itemMeaning其實就是獲取的事物集。每一條事物集是[0/1,哪條具體規則]
就是將所有必要信息離散化編號然后統計整個投票過程
最后得到類似的結果：
Prohibiting Federal Funding of National Public Radio -- Yea
-------->
Republican
Repealing the Health Care Bill -- Yea
confidence: 0.995614
發現毒蘑菇的相似特征
有時候不是想要尋找所有的頻繁項集合，只是隊某個特征元素項集感興趣。我們尋找毒蘑菇的公共特征，利用這些特征就能避免遲到有毒的蘑菇。
UCI數據集合重有蘑菇的23種特征的數據集，每一個特征是標稱數據。而我們需要將樣本轉換成特征的集合，枚舉每個特征所有可能的舉止，如果某個樣本 包含特征，那么特征對應的整數應該被包含在數據集中 1 3 9 13 23 25 34 36 38 40 52 54 59 63 67 76 85 86 90 93 98 107 113 每一個樣本都是這樣的特征集合。
如果第一個特征有毒就是2，如果能食用就是1，下一個特征是形狀有6可能值，用整數3-8表示
相當于把需要的特征維度都進行排列離散化。最終只有1個大維特征
mushDatSet = [line.split() for line in open('mushroom.dat').readlines()]
L,suppData = apriori.apriori(mushDatSet,minSupport=0.3)
#尋找毒的公共特征
for item in L[1]:
if item.intersection('2'):print itemfrozenset(['2', '59'])
frozenset(['39', '2'])
frozenset(['2', '67'])
frozenset(['2', '34'])
frozenset(['2', '23'])
frozenset(['2', '86'])
frozenset(['76', '2'])
frozenset(['90', '2'])
frozenset(['2', '53'])
frozenset(['93', '2'])
frozenset(['63', '2'])
frozenset(['2', '28'])
frozenset(['2', '85'])
frozenset(['2', '36'])
那么可以給我們的提示就是如果有特征編號是這些的就不要吃這種蘑菇了
總結：
關聯分析是發現大數據集合元素間關系的工具集。可以用在不同的物品上，主要是在樣本處理上需要將樣本轉換成特征集合。也就是將所有維的特征統一編碼。
原文鏈接：https://blog.csdn.net/hhy518518/article/details/54603797
相關推薦
- 2022-12-10 C++中的結構體vector排序問題_C 語言
- 2022-04-27 Shell中關于exit?0的那些坑_linux shell
- 2022-05-25 Python可變參數*args和**kwargs_python
- 2022-04-28 WPF簡介與基礎開發_實用技巧
- 2022-10-12 常見Android編譯優化問題梳理總結_Android
- 2022-10-20 Swift繼承Inheritance淺析介紹_Swift
- 2022-12-23 Python中的文件輸入輸出問題_python
- 2022-11-20 Golang交叉編譯之跨平臺編譯使用詳解_Golang
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速