0

我正在实现 FP 增长算法，目前我可以从一组事务中建立一个 FP 树。下一步是挖掘前缀路径并从中构建树。这是我的节点类：

class Node:
    def __init__(self, name, count, parent):
        self.name = name
        self.count = count
        self.parent = parent
        self.children = {}

类中有更多用于创建树的函数，但这些函数与我当前的问题并不相关（我认为）。每个节点都有一个父节点，一些节点有子节点，树被存储为代表根节点的对象。每个节点的子节点存储在与节点关联的字典中，其键是项目的名称，值是节点对象。

我有以下函数适用于单节点实例以查找前缀路径（基本上是父节点，然后是父节点的父节点，依此类推，直到根节点）：

def get_prefix(node, path=[], level=0):
    if node.name not in path:
        path.append(node.name)
    # check if parent node is root node
    if node.parent.parent != None:
        path = get_prefix(node.parent, path, level=level+1)[0]
    if level == 0:
        path.remove(node.name)
    return [path, node.count, node.name]

这适用于以下类型的输入：

get_prefix(root_node.children['2'].children['3'].children['1'].children['5'])

返回

[['1', '3', '2'], 1, '5']

我想我应该注意到我正在使用这个数据集，来自 Han 等人的数据挖掘：概念和技术：

transactions = [['1', '2', '5'],
                ['2', '4'],
                ['2', '3'],
                ['1', '2', '4'],
                ['1', '3'],
                ['2', '3'],
                ['1', '3'],
                ['1', '2', '3', '5'],
                ['1', '2', '3']]

min_support = 2

到目前为止，一切都很好。但是当我尝试在整个树中查找长度大于 1 的所有前缀路径时，总是会出错。我要做的是编写一个函数，该函数接受根节点并返回树中所有节点的所有前缀路径的字典或列表。我已经尝试了几次，有几种方式：

def get_all_prefixes(root, prefixes={}):
    for child in list(root.children.values()):
        print('On child node ' + child.name)
        # get prefix path info for current node
        prefix_list = get_prefix(child)
        # if item from node already in prefixes keys, then
        # append prefix path results to value
        if len(prefix_list[0]) > 1:
            if prefix_list[2] in prefixes.keys():
                print('Appending ' + str(prefix_list[0]) + ' for ' + str(child.name))
                prefixes[prefix_list[2]].append([prefix_list[0], prefix_list[1]])
            # otherwise create new key in prefixes
            else:
                print('Inititalizing ' + str(prefix_list[0]) + ' for ' + str(child.name))
                prefixes[prefix_list[2]] = [[prefix_list[0], prefix_list[1]]]
        print('Prefix path before recursion:')
        print(prefixes)
        prefixes = get_all_prefixes(child, prefixes)
        print('Prefix path after recursion:')
        print(prefixes)
#         get_all_prefixes(child, prefixes)
    
    return prefixes

这将返回：

{'1': [[['2', '3'], 2], [['2', '3'], 2], [['2', '3'], 2]],
 '5': [[['2', '3'], 1], [['2', '3'], 1]],
 '4': [[['2', '3'], 1], [['2', '3'], 1]],
 '3': [[['2', '3'], 4], [['2', '3'], 2]]}

另一个尝试：

def get_prefix_list(root, prefixes=[]):
    cur_prefix = get_prefix(root)
    prefixes.append([cur_prefix, root.name, root.count])
    for child in root.children.values():
#         prefixes.append(get_prefix_list(child)[0])
        get_prefix_list(child)
    return prefixes

返回

[[[['2', '3'], 0, 'root'], 'root', 0],
 [[['2', '3'], 7, '2'], '2', 7],
 [[['2', '3'], 2, '1'], '1', 2],
 [[['2', '3'], 1, '5'], '5', 1],
 [[['2', '3'], 1, '4'], '4', 1],
 [[['2', '3'], 1, '4'], '4', 1],
 [[['2', '3'], 4, '3'], '3', 4],
 [[['2', '3'], 2, '1'], '1', 2],
 [[['2', '3'], 1, '5'], '5', 1],
 [[['2', '3'], 2, '3'], '3', 2],
 [[['2', '3'], 2, '1'], '1', 2]]

我不确定自己做错了什么，而且无论我花多长时间思考这个问题，我最终都会以稍微不同（并且仍然错误）的方式做同样的事情。

递归调用很可能是问题所在，自从我不得不使用递归以来已经有一段时间了。遍历这棵树并收集前缀路径的正确方法是什么？

编辑：澄清一下，FP 增长是频繁的模式增长，如下所述：https ://scholar.google.com/scholar_url?url=https://web.iitd.ac.in/~bspanda/fptree.pdf&hl=en&sa =X&ei=Wt1aYbjZHdWR6rQPoZm​​ruAk&scisig=AAGBfm2FZzJEsEwGApOtUPol2gdVBtQ38Q&oi=学者

部分解决方案：我实现了以下代码：

def create_path(node, path):
    if node.parent != None:
        path.append(node.name)
        create_path(node.parent, path)

def get_prefix_list(root, prefix_list=[]):
    for child in root.children.values():
        path = []
        create_path(child, path)
        if len(path) > 1:
            prefix_list.append([path[1:], child.name, child.count])
        for x in get_prefix_list(child):
            if x not in prefix_list:
                prefix_list.append([x, child.name, child.count])
    return prefix_list

def get_prefix_dict(root, min_sup):
    prefix_list = get_prefix_list(root)
    prefix_dict = {}
    for x in prefix_list:
        if x[1] in prefix_dict.keys():
            prefix_dict[x[1]].append([x[0], x[2]])
        else:
            prefix_dict[x[1]] = [[x[0], x[2]]]
    return prefix_dict

这将为初始 FP 树返回正确的前缀路径字典，这很棒。但是，一旦我进入必须从通过挖掘前缀路径创建的树中找到前缀路径的步骤，我就会遇到问题。这是项目“5”的前缀路径生成树之一：

Name: root
Level: 0
Count: 0
Children: ['2']

   Name: 2
   Level: 1
   Count: 2
   Parent: root
   Children: ['1']

      Name: 1
      Level: 2
      Count: 2
      Parent: 2
      Children: ['3']

         Name: 3
         Level: 3
         Count: 1
         Parent: 1
         Children: []

这是我们所期望的，并且到目前为止看起来不错。但是当我尝试在它上面运行我的前缀查找功能时：

get_prefix_dict(cond_fp_trees['5'], min_support)

我得到这个废话：

{'1': [[['2'], 2],
  [['3', '2'], 2],
  [['3'], 2],
  [['2'], 2],
  [['2'], 2],
  [['2'], 2]],
 '5': [[['1', '2'], 1], [['1', '3', '2'], 1]],
 '4': [[['1', '2'], 1], [['2'], 1]],
 '3': [[['2'], 4], [['1', '2'], 1], [['1', '2'], 1], [['1', '2'], 1]]}

现在我真的很困惑，因为即使在那棵树中也没有“4”项。这些物品是从哪里来的？为什么我的函数在这棵树上的行为不像在初始 FP 树上那样？

4

0 回答 0