FP-Growth-Algorithmus ist ein klassischer Algorithmus zum Mining häufiger Muster. Es handelt sich um einen sehr effizienten Algorithmus zum Mining von Sammlungen von Elementen, die häufig zusammen aus Datensätzen auftreten. In diesem Artikel werden Sie ausführlich in das Prinzip und die Implementierungsmethode des FP-Wachstumsalgorithmus eingeführt.
1. Grundprinzip des FP-Wachstumsalgorithmus
Die Grundidee des FP-Wachstumsalgorithmus besteht darin, einen FP-Baum (häufiger Itemset-Baum) zu erstellen, um die häufigen Itemsets im Datensatz darzustellen und häufige Items zu extrahieren aus dem FP-Tree-Set. FP-Tree ist eine effiziente Datenstruktur, die häufige Itemsets durchsuchen kann, ohne Kandidaten für häufige Itemsets zu generieren.
FP-Tree besteht aus zwei Teilen: Wurzelknoten und Baumknoten. Der Wurzelknoten hat keinen Wert, während die Baumknoten den Namen eines Elements und die Häufigkeit des Vorkommens des Elements enthalten. FP-Tree enthält auch Links, die auf dieselben Knoten verweisen. Diese Links werden „Link-Zeiger“ genannt.
Der Prozess des FP-Wachstumsalgorithmus besteht aus zwei Teilen: Erstellen eines FP-Baums und Mining häufiger Elementmengen:
Löschen Sie für jede Transaktion nicht häufige Elemente und berechnen Sie die Häufigkeit entsprechend der Unterstützung der häufigen Elemente Sortieren Sie nach Größe, um eine häufige Elementmenge zu erhalten.
Durchlaufen Sie jede Transaktion und fügen Sie die häufigen Itemsets jeder Transaktion in der Reihenfolge ihres Auftretens ein. Wenn der Knoten bereits vorhanden ist, erhöhen Sie seine Anzahl. Wenn er nicht vorhanden ist, fügen Sie einen neuen Knoten ein.
Die Methoden zum Mining häufiger Itemsets aus FP-Tree umfassen:
Beginnen Sie am Ende des FP-Tree und suchen Sie die bedingte Musterbibliothek jedes Itemsets Transaktion, die dieses Itemset enthält. Anschließend wird rekursiv ein neuer FP-Baum für die bedingte Musterbibliothek erstellt und häufige Elementmengen im Baum durchsucht.
Im neuen FP-Baum wird jedes häufig vorkommende Element nach Unterstützung sortiert, eine Reihe von Kandidaten erstellt und rekursiv abgebaut. Wiederholen Sie den obigen Vorgang, bis alle häufigen Itemsets gefunden wurden.
2. Implementierung des FP-Growth-Algorithmus
Die Implementierung des FP-Growth-Algorithmus kann die Programmiersprache Python verwenden. Das Folgende ist ein einfaches Beispiel, um die Implementierung des FP-Growth-Algorithmus zu demonstrieren.
Definieren Sie zunächst einen Datensatz, zum Beispiel:
dataset = [['v', 'a', 'p', 'e', 's'],
['b', 'a', 'k', 'e'],
['a', 'p', 'p', 'l', 'e', 's'],
['d', 'i', 'n', 'n', 'e', 'r']]Dann schreiben Sie eine Funktion zum Generieren eines geordneten Artikelsatzes, zum Beispiel:
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_itemsUnter diesen wird die Funktion create_ordered_items verwendet, um einen geordneten Artikelsatz entsprechend der Anzahl zu erhalten Vorkommen des Artikels.
Als nächstes schreiben Sie eine Funktion zum Erstellen des FP-Baums:
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)Die Funktion create_tree wird zum Erstellen des FP-Baums verwendet.
Schreiben Sie abschließend eine Funktion zum Mining häufiger Itemsets:
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_itemsmine_fp_tree-Funktion wird zum Mining häufiger Itemsets verwendet.
3. Zusammenfassung
Der FP-Growth-Algorithmus ist ein effizienter Algorithmus zum Mining häufiger Muster. Durch die Erstellung eines FP-Baums können häufige Elementmengen abgebaut werden, ohne dass häufige Elementmengen in Frage kommen. Python ist eine Programmiersprache, die sich sehr gut für die Implementierung des FP-Growth-Algorithmus eignet. Durch die Verwendung von Python können wir diesen Algorithmus schnell implementieren und in der Praxis zum Mining häufiger Itemsets verwenden. Ich hoffe, dieser Artikel kann Ihnen helfen, die Prinzipien und Implementierungsmethoden des FP-Growth-Algorithmus besser zu verstehen.
Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung des FP-Growth-Algorithmus in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
