admin管理员组文章数量:1531791
设全集U = {a, b, c, d, e}
,其元素a,b, c, d, e称为项.
数据集:
D = [
{a, b},
{b, c, d},
{d, e},
{b, c, e},
{a,b, c, d}
]
项的集合如{a,b}
称为项集(cell), 包含k个项的集合称为k项集.
数据集D中包含项集A的集合占所有元素集的比例称为A的支持度(support).如{a}
的支持度为2/5.
若项集满足人为设定的最小支持度,则称为频繁集.
频繁集的任意子集一定是频繁集, 非频繁集的超集一定为非频繁集.
定义关联规则{a} -> {b}
的可信度(confidence)为:support({a} U {b}) / support({a})
.
关联分析的目的在于寻找频繁集以及关联规则。
寻找频繁集
非频繁集的超集一定为非频繁集,我们从空集开始根据包含关系构建一棵树:
根据数据集创建单项集:
def createUnit(dataSet): # create cell with one element
universe = []
for cell in dataSet:
for item in cell:
if not [item] in universe:
universe.append([item])
return map(frozenset, universe)
遍历每一个项集中的每一项,将项添加到全集中, 最后使用map由全集创建单项集.
使用frozenset而非set,是因为frozenset可以在dict中作为键, 而set不能.
从候选集中筛选频繁集:
def filterCandidates(dataSet, candidates, limit):
cellCount = {}
for cell in dataSet:
for candidate in candidates:
if candidate.issubset(cell):
if not candidate in cellCount:
cellCount[candidate] = 1
else:
cellCount[candidate] += 1
cellNum = len(dataSet)
selected = []
supports = {}
for cell in cellCount:
support = float(cellCount[cell]) / cellNum
if support >= limit:
selected.insert(0, cell)
supports[cell] = support
return selected, supports
该方法接受三个参数, 数据集dataSet, 候选集列表candidates, 和最小支持度limit.
遍历dataSet中的所有项集,统计各候选集超集的个数, 用于计算候选集的支持度.
过滤所有候选集, 返回支持度达到要求的项集(频繁集).
根据k-1项集创建所有k项集:
def createKCell(origins, k):
cells = []
originCount = len(origins)
for i in range(originCount):
for j in range(i + 1, originCount):
list1 = list(origins[i])[:k - 2]
list2 = list(origins[j])[:k - 2]
list1.sort()
list2.sort()
if list1 == list2: # if first k-2 elements are equal
cells.append(origins[i] | origins[j]) # set union
return cells
该方法接受两个参数,k-1项集列表origins和k. 通过并集运算建立k项集.
从单项集开始寻找频繁集:
def apriori(dataMat, limit=0.5):
units = createUnit(dataMat)
dataSet = map(set, dataMat)
origin, supports = filterCandidates(dataSet, units, limit)
candidates = [origin]
k = 2
while (len(candidates[k - 2]) > 0):
cellK = createKCell(candidates[k - 2], k)
cellK, supportK = filterCandidates(dataSet, cellK, limit)
supports.update(supportK)
candidates.append(cellK)
k += 1
return candidates, supports
寻找关联规则
频繁集之间存在着关联规则:
实现filterRules方法获得可信度满足要求的规则, 每条规则用三元组来描述:(A, B, confidence)代表规则A->B的可信度为confidence.
def filterRules(cells, consequences, supports, bigRuleList, limit=0.7):
prunedConsequences = []
for consequence in consequences:
confidence = supports[cells] / supports[cells - consequence]
if confidence >= limit:
rule = (cells - consequence, consequence, confidence)
bigRuleList.append(rule)
prunedConsequences.append(consequence)
return prunedConsequences
该方法接受5个参数:
cells:频繁集列表
consequences: 所有可放在规则右侧的元素组成的列表
supports: cells中各频繁集的支持度
bigRuleList: 已知规则的列表, 该方法会将满足要求的规则添加到该列表中
limit: 规则可信度的下限
该方法返回满足条件的规则的右侧元素组成的列表.
当规则右侧的元素的数目大于2时, 尝试对其进行合并:
def rulesFromConseq(cells, consequences, supports, bigRuleList, limit=0.7):
m = len(consequences[0])
if len(cells) > (m + 1): # try further merging
new_consequences = createKCell(consequences, m + 1)
new_consequences = filterRules(cells, new_consequences, supports, bigRuleList, limit)
if len(new_consequences) > 1: # need at least two sets to merge
rulesFromConseq(cells, new_consequences, supports, bigRuleList, limit)
该方法的参数与filterRules方法相同, 使用递归来实现.
利用上面两个工具函数来编写寻找关联规则的方法:
def generateRules(cells, supports, limit=0.7):
bigRuleList = []
for i in range(1, len(cells)):
for cell in cells[i]:
consequences = [frozenset([item]) for item in cell]
if i > 1:
rulesFromConseq(cell, consequences, supports, bigRuleList, limit)
else:
filterRules(cell, consequences, supports, bigRuleList, limit)
return bigRuleList
接受频繁集列表及其支持度作为参数, 遍历各频繁集根据给定的可信度范围寻找关联规则.
编写test方法进行测试:
def test():
dataSet = [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
cells, supports = apriori(dataSet, 0.5)
# print(cells)
rules = generateRules(cells, supports)
print(rules)
# units = createUnit(dataSet)
# print(units)
# cells, supports = filterCandidates(dataSet, units, 0.5)
# print(cells, supports)
# cells = createKCell(selected, 2)
# print(cells)
顺便展示一下各函数的用法, 完整代码可以看这里
转载于:https://wwwblogs/Finley/p/5858123.html
版权声明:本文标题:Apriori算法进行关联分析 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1726826330a1086120.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论