Penjelasan terperinci algoritma FP-Growth dalam Python

Algoritma FP-Growth ialah algoritma perlombongan corak kerap klasik Ia adalah algoritma yang sangat cekap untuk melombong koleksi item yang sering muncul bersama-sama daripada set data. Artikel ini akan memperkenalkan anda kepada prinsip dan kaedah pelaksanaan algoritma FP-Growth secara terperinci.

1. Prinsip Asas Algoritma FP-Growth

Idea asas algoritma FP-Growth ialah membina FP-Tree (pokok set item kerap) untuk mewakili set item kerap dalam set data, dan Set item kerap melombong daripada FP-Tree. FP-Tree ialah struktur data yang cekap yang boleh melombong set item kerap tanpa menghasilkan set item kerap calon.

FP-Tree mengandungi dua bahagian: nod akar dan nod pokok. Nod akar tidak mempunyai nilai, manakala nod pokok termasuk nama item dan bilangan kali item itu berlaku. FP-Tree juga termasuk pautan yang menghala ke nod yang sama, pautan ini dipanggil "penunjuk pautan".

Proses algoritma FP-Growth merangkumi dua bahagian: membina FP-Tree dan melombong set item kerap:

1. Membina FP-Tree:

Untuk Bagi setiap transaksi, item bukan kerap dipadamkan dan diisih mengikut sokongan item kerap untuk mendapatkan set item kerap.

Lintas setiap urus niaga, dan masukkan set item kerap setiap transaksi ke dalam FP-Tree dalam susunan penampilan Jika nod sudah wujud, tambahkan bilangannya, masukkan nod baharu. .

2. Melombong set item kerap:

Kaedah melombong item set kerap dari FP-Tree termasuk:

Mulakan dari bawah FP-Tree , cari perpustakaan corak bersyarat bagi setiap set item, dan pustaka corak bersyarat mengandungi semua transaksi yang mengandungi set item. Kemudian, FP-Tree baharu dibina secara rekursif untuk perpustakaan corak bersyarat, dan set item yang kerap dalam pepohon dicari.

Dalam FP-Tree baharu, setiap item yang kerap diisih mengikut sokongannya, satu set calon dibina dan dilombong secara rekursif. Ulangi proses di atas sehingga semua item set yang kerap ditemui.

2. Pelaksanaan algoritma FP-Growth

Algoritma FP-Growth boleh dilaksanakan menggunakan bahasa pengaturcaraan Python. Berikut ialah contoh mudah untuk menunjukkan pelaksanaan algoritma FP-Growth.

Mula-mula, tentukan set data, contohnya:

dataset = [['v', 'a', 'p', 'e', 's'],
           ['b', 'a', 'k', 'e'],
           ['a', 'p', 'p', 'l', 'e', 's'],
           ['d', 'i', 'n', 'n', 'e', 'r']]

Kemudian, tulis fungsi untuk menjana set item tersusun, contohnya:

def create_ordered_items(dataset):
    # 遍历数据集，统计每个项出现的次数
    item_dict = {}
    for trans in dataset:
        for item in trans:
            if item not in item_dict:
                item_dict[item] = 1
            else:
                item_dict[item] += 1

    # 生成有序项集
    ordered_items = [v[0] for v in sorted(item_dict.items(), key=lambda x: x[1], reverse=True)]
    return ordered_items

Di mana, fungsi create_ordered_items ialah digunakan untuk mengikuti Dapatkan set item yang dipesan dengan bilangan kejadian item.

Seterusnya, tulis fungsi untuk membina FP-Tree:

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

    def increase_count(self, count):
        self.count += count

def create_tree(dataset, min_support):
    # 生成有序项集
    ordered_items = create_ordered_items(dataset)

    # 建立根节点
    root_node = TreeNode('Null Set', 0, None)

    # 建立FP-Tree
    head_table = {}
    for trans in dataset:
        # 过滤非频繁项
        filtered_items = [item for item in trans if item in ordered_items]
        # 对每个事务中的项集按频繁项的支持度从大到小排序
        filtered_items.sort(key=lambda x: ordered_items.index(x))
        # 插入到FP-Tree中
        insert_tree(filtered_items, root_node, head_table)

    return root_node, head_table

def insert_tree(items, node, head_table):
    if items[0] in node.children:
        # 如果节点已存在，则增加其计数
        node.children[items[0]].increase_count(1)
    else:
        # 如果节点不存在，则插入新的节点
        new_node = TreeNode(items[0], 1, node)
        node.children[items[0]] = new_node
        # 更新链表中的指针
        if head_table.get(items[0], None) is None:
            head_table[items[0]] = new_node
        else:
            current_node = head_table[items[0]]
            while current_node.node_link is not None:
                current_node = current_node.node_link
            current_node.node_link = new_node

    if len(items) > 1:
        # 对剩余的项进行插入
        insert_tree(items[1:], node.children[items[0]], head_table)

Fungsi create_tree digunakan untuk membina FP-Tree.

Akhir sekali, tulis fungsi untuk melombong itemset kerap:

def find_freq_items(head_table, prefix, freq_items, min_support):
    # 对头指针表中的每个项按照出现的次数从小到大排序
    sorted_items = [v[0] for v in sorted(head_table.items(), key=lambda x: x[1].count)]
    for item in sorted_items:
        # 将前缀加上该项，得到新的频繁项
        freq_set = prefix + [item]
        freq_count = head_table[item].count
        freq_items.append((freq_set, freq_count))
        # 构建该项的条件模式库
        cond_pat_base = get_cond_pat_base(head_table[item])
        # 递归地构建新的FP-Tree，并寻找频繁项集
        sub_head_table, sub_freq_items = create_tree(cond_pat_base, min_support)
        if sub_head_table is not None:
            find_freq_items(sub_head_table, freq_set, freq_items, min_support)

def get_cond_pat_base(tree_node):
    cond_pat_base = []
    while tree_node is not None:
        trans = []
        curr = tree_node.parent
        while curr.parent is not None:
            trans.append(curr.name)
            curr = curr.parent
        cond_pat_base.append(trans)
        tree_node = tree_node.node_link
    return cond_pat_base

def mine_fp_tree(dataset, min_support):
    freq_items = []
    # 构建FP-Tree
    root_node, head_table = create_tree(dataset, min_support)
    # 挖掘频繁项集
    find_freq_items(head_table, [], freq_items, min_support)
    return freq_items

Fungsi mine_fp_tree digunakan untuk melombong set item kerap.

3. Ringkasan

Algoritma FP-Growth ialah algoritma perlombongan pola kerap yang cekap Dengan membina FP-Tree, item kerap boleh dilombong tanpa menghasilkan set item kerap calon. Python ialah bahasa pengaturcaraan yang sangat sesuai untuk melaksanakan algoritma FP-Growth Dengan menggunakan Python, kita boleh melaksanakan algoritma ini dengan cepat dan menggunakannya dalam amalan untuk melombong itemset yang kerap. Saya harap artikel ini dapat membantu anda memahami dengan lebih baik prinsip dan kaedah pelaksanaan algoritma FP-Growth.

Atas ialah kandungan terperinci Penjelasan terperinci algoritma FP-Growth dalam Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!