挖掘频繁项集得到 FP 树后，需要对每一个频繁项，逐个挖掘频繁项集。具体过程为：首先获得频繁项的前缀路径，然后将前缀路径作为新的数据集，以此构建前缀路径的条件 FP 树。然后对条件 FP 树中的每个频繁项，获得前缀路径并以此构建新的条件 FP 树。不断迭代，直到条件 FP 树中只包含一个频繁项为止。下面以元素 c 为例，从上文图 4 创建好的 FP 树中挖掘频繁项集。
首先，获得以 c 元素的前缀路径{a:2,b:2}，注意此处 a 和 b 的频数为 2 是因为 c 的频数为 2，所以与 c 共同出现的 a 和 b 的频数就都为 2。
接着，创建条件 FP 树，具体的创建过程和上一节创建 FP 树的过程一样，如图 5 所示。
图 5. c 元素的前缀路径构成的条件 FP 树 注意此时头指针表中包含两个元素，所以对每个元素，需要获得前缀路径，并将前缀路径创建成条件 FP 树，直到条件 FP 树中只包含一个元素时返回。
- 对元素 a，获得前缀路径为{}，则频繁项集返回{c,a};
- 对元素 b，获得前缀路径{a}，则将前缀路径创建成条件 FP 树，如图 6 所示。注意此时条件 FP 树中只包含一个元素，故返回频繁项集{c,b,a}。由于元素 b 也是频繁项，所以{c,b}也是频繁项集。
再加上{c}本身就是频繁项集，所以 c 对应的频繁项集有：{c} {c,a} {c,b} {c,b,a}。
图 6. b 元素的前缀路径构成的条件 FP 树 将其他元素 a,b,d 同样按照上述对 c 的操作，得到表 3 所示频繁项集。
表 3. 元素 a,b,c,d 对应的频繁项集元素频繁项集 a {a} b {b} {b,a} c {c} {c,a} {c,b} {c,b,a} d {d} {d,a}
关联规则挖掘原理关联规则挖掘首先需要对上文得到的频繁项集构建所有可能的规则，然后对每条规则逐个计算置信度，输出置信度大于最小置信度的所有规则。以频繁项集{a,b,c}为例，构建所有可能的规则：{b,c} -> {a}, {a,c} -> {b},{a,b} -> {c},{c} -> {a,b},{b} -> {a,c},{a} -> {b,c}。对每条规则计算置信度后，输出满足要求的规则即可。
实现步骤: 自己动手实现 FP-growth以上都为理论部分，下面开始介绍如何自己动手实现代码。
首先，需要创建一个树形的数据结构，叫做 FP 树。如清单 1 所示，该树结构包含结点名称 nodeName，结点元素出现频数 count，父节点 nodeParent，指向下一个相同元素的指针 nextSimilarItem，子节点集合 children。
清单 1. FP 树结构1
2
3
4
5
6
7
| class TreeNode:
def __init__(self, nodeName, count, nodeParent):
self.nodeName = nodeName
self.count = count
self.nodeParent = nodeParent
self.nextSimilarItem = None
self.children = {}
|
接着，用第一步构造出的数据结构来创建 FP 树。如清单 2 所示，代码主要分为两层。第一层，扫描数据库，统计出各个元素的出现频数；第二层，扫描数据库，对每一条数据记录，将数据记录中不包含在频繁元素中的元素删除，然后将数据记录中的元素按出现频数排序。将数据记录逐条插入 FP 树中，不断更新 FP 树，更新的过程会在清单 3 中介绍。
清单 2. 创建 FP 树1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| def createFPTree(frozenDataSet, minSupport):
#scan dataset at the first time, filter out items which are less than minSupport
headPointTable = {}
for items in frozenDataSet:
for item in items:
headPointTable[item] = headPointTable.get(item, 0) + frozenDataSet[items]
headPointTable = {k:v for k,v in headPointTable.items() if v >= minSupport}
frequentItems = set(headPointTable.keys())
if len(frequentItems) == 0: return None, None
for k in headPointTable:
headPointTable[k] = [headPointTable[k], None]
fptree = TreeNode("null", 1, None)
#scan dataset at the second time, filter out items for each record
for items,count in frozenDataSet.items():
frequentItemsInRecord = {}
for item in items:
if item in frequentItems:
frequentItemsInRecord[item] = headPointTable[item][0]
if len(frequentItemsInRecord) > 0:
orderedFrequentItems = [v[0] for v in sorted(frequentItemsInRecord.items(), key=lambda v:v[1], reverse = True)]
updateFPTree(fptree, orderedFrequentItems, headPointTable, count)
return fptree, headPointTable
|
清单 3 主要用来更新 FP 树，这里用到了递归的技巧。每次递归迭代中，处理数据记录中的第一个元素处理，如果该元素是 fptree 节点的子节点，则只增加该子节点的 count 树，否则，需要新创建一个 TreeNode 节点，然后将其赋给 fptree 节点的子节点，并更新头指针表关于下一个相同元素指针的信息。迭代的停止条件是当前迭代的数据记录长度小于等于 1。
清单 3. 更新 FP 树1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def updateFPTree(fptree, orderedFrequentItems, headPointTable, count):
#handle the first item
if orderedFrequentItems[0] in fptree.children:
fptree.children[orderedFrequentItems[0]].increaseC(count)
else:
fptree.children[orderedFrequentItems[0]] = TreeNode(orderedFrequentItems[0], count, fptree)
#update headPointTable
if headPointTable[orderedFrequentItems[0]][1] == None:
headPointTable[orderedFrequentItems[0]][1] = fptree.children[orderedFrequentItems[0]]
else:
updateHeadPointTable(headPointTable[orderedFrequentItems[0]][1], fptree.children[orderedFrequentItems[0]])
#handle other items except the first item
if(len(orderedFrequentItems) > 1):
updateFPTree(fptree.children[orderedFrequentItems[0]], orderedFrequentItems[1::], headPointTable, count)
|
清单 4 开始挖掘频繁项集，这里也是递归迭代的思路。对于头指针表中的每一个元素，首先获取该元素结尾的所有前缀路径，然后将所有前缀路径作为新的数据集传入 createFPTree 函数中以创建条件 FP 树。然后对条件 FP 树对应的头指针表中的每一个元素，开始获取前缀路径，并创建新的条件 FP 树。这两步不断重复，直到条件 FP 树中只有一个元素为止。
清单 4. 挖掘频繁项集1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def mineFPTree(headPointTable, prefix, frequentPatterns, minSupport):
#for each item in headPointTable, find conditional prefix path, create conditional fptree, then iterate until there is only one element in conditional fptree
headPointItems = [v[0] for v in sorted(headPointTable.items(), key = lambda v:v[1][0])]
if(len(headPointItems) == 0): return
for headPointItem in headPointItems:
newPrefix = prefix.copy()
newPrefix.add(headPointItem)
support = headPointTable[headPointItem][0]
frequentPatterns[frozenset(newPrefix)] = support
prefixPath = getPrefixPath(headPointTable, headPointItem)
if(prefixPath != {}):
conditionalFPtree, conditionalHeadPointTable = createFPTree(prefixPath, minSupport)
if conditionalHeadPointTable != None:
mineFPTree(conditionalHeadPointTable, newPrefix, frequentPatterns, minSupport)
|
清单 5 展示了获取前缀路径的步骤。对于每一个相同元素，通过父节点指针不断向上遍历，所得的路径就是该元素的前缀路径。
清单 5. 获取前缀路径1
2
3
4
5
6
7
8
9
10
11
12
13
| def getPrefixPath(headPointTable, headPointItem):
prefixPath = {}
beginNode = headPointTable[headPointItem][1]
prefixs = ascendTree(beginNode)
if((prefixs != [])):
prefixPath[frozenset(prefixs)] = beginNode.count
while(beginNode.nextSimilarItem != None):
beginNode = beginNode.nextSimilarItem
prefixs = ascendTree(beginNode)
if (prefixs != []):
prefixPath[frozenset(prefixs)] = beginNode.count
return prefixPath
|
清单 6 展示了挖掘关联规则的代码，这里也用到了递归迭代的技巧。对于每一个频繁项集，构造所有可能的关联规则，然后对每一个关联规则计算置信度，输出置信度大于阈值的关联规则。
清单 6. 挖掘关联规则1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| def rulesGenerator(frequentPatterns, minConf, rules):
for frequentset in frequentPatterns:
if(len(frequentset) > 1):
getRules(frequentset,frequentset, rules, frequentPatterns, minConf)
def getRules(frequentset,currentset, rules, frequentPatterns, minConf):
for frequentElem in currentset:
subSet = removeStr(currentset, frequentElem)
confidence = frequentPatterns[frequentset] / frequentPatterns[subSet]
if (confidence >= minConf):
flag = False
for rule in rules:
if(rule[0] == subSet and rule[1] == frequentset - subSet):
flag = True
if(flag == False):
rules.append((subSet, frequentset - subSet, confidence))
if(len(subSet) >= 2):
getRules(frequentset, subSet, rules, frequentPatterns, minConf)
|
|
