Apriori {
input
{ID1:[item1,item2…],ID2:[item3,item2…],…}output
item1->item2,item3…math
频率及条件概率的简单应用
支持度: 频数/样本总量
置信度: 条件概率
如果子集不为频繁集则超集一定不为;反之如果超集是频繁集则子集均为频繁集。parameters
minSupport
minConf
过程
1-4完成了频繁集的搜寻,5及之后产生规则。
list
存放每个用户的itemset
,生成[[],[]]存放所有item并排序,map(frozenset, C1)
第一轮遍历,生成一个
list
存放所有支持度大于minSupport
,大于则insert(0,key)
。遍历的函数scanD
所生成list
的元素是frozenset
。如果can.issubset(tid)
且!ssCnt.has_key(can)
则加入到supportData
。list存放所有频繁物品集,
supportData
存放所有计算过的物品集的支持度,以frozenset
作为key
。两者更新的过程是在apriori
中循环调用aprioriGen
和scanD
,再更新。直到scanD
得到的频繁物品集为空。aprioriGen
的过程,两层循环,遍历上一个(即物品集中个数为目前需要产生的个数-1)频繁物品集,L1 = list(Lk[i])[:k-2];L2 = list(Lk[j])[:k-2]
取前k-2项比较,若相同则retList.append(Lk[i] | Lk[j])
将物品集union。是一个merging过程。如果频繁集
frozenset
中item多于2,先rulesFromConseq
再calcConf
。rulesFromConseq
是个递归过程,
def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
m = len(H[0])
if (len(freqSet) > (m + 1)): #停止条件
Hmp1 = aprioriGen(H, m+1)
Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
if (len(Hmp1) > 1): #至少需要两个元素才能够merge
rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
这里一个问题是,如果len(Hmp1) =1
,但是len(freqSet) > (len(Hmp1[0]) + 1)
仍然成立,因此修改为:
def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
m = len(H[0])
if (len(freqSet) > (m + 1)): #停止条件
if(len(H) > 1):
Hmp1 = aprioriGen(H, m+1)
Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
}
fptree {
概念
闭项:超集的支持度为s,子集的支持度都不超过s。
条件模式基: 即一个item追溯到root的所有路径
条件fp树 : 即根据条件模式基创建的tree
myCondTree, myHead = createTree(condPattBases, minSup)
准备
headertable
:dict
,value
为[count,treeNode]
treeNode
:class
def __init__(self, nameValue, numOccur, parentNode):
self.name = nameValue
self.count = numOccur
self.nodeLink = None
self.parent = parentNode
self.children = {}
主要方法:createTree
updateTree
mineTree
辅助方法:updateHeader
findPrefixPath
ascendTree
- 过程
-
createTree
首先第一次遍历计算count
,headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
将count
简单赋值为1。注意到这里的dataSet类型。
def createInitSet(dataSet):
retDict = {}
for trans in dataSet:
retDict[frozenset(trans)] = 1
return retDict
获得freqItemSet = set(headerTable.keys())
后第二次遍历。先对item排序,orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)]
,再updateTree(orderedItems, retTree, headerTable, count)
。
-
updateTree
,这里就是普通的对树的操作,也是递归。
if len(items) > 1:#call updateTree() with remaining ordered items
updateTree(items[1::], inTree.children[items[0]], headerTable, count)
唯一注意之处,需要updateHeader
。
-
mineTree
和Apriori
中的rulesFromConseq
一样较复杂,包含递归。先生成条件模式基,再生成conditional-fptree,再递归。
if myHead != None:
mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)
循环递归mineTree的过程即生成规则过程,直到频繁2项集都得到。
}