FP-Tree的表示方法是什麼？

FP-tree是對輸入資料的簡潔描述。它是透過一次讀取一個事務的資料集，並將每個事務對映到FP-tree中的一個路徑來構建的。多個事務可能有許多共同的項，它們的路徑可能會重疊。

路徑重疊越多，使用FP-tree架構實現的壓縮就越多。如果FP-tree的大小足以放入主記憶體，這將使我們能夠直接從記憶體中的架構中提取頻繁項集，而不是對儲存在磁碟上的資料進行重複的遍歷。

樹中的每個節點包含一個專案的標籤以及一個計數器，該計數器顯示對映到給定路徑的多個事務。最初，FP-tree只包含由空符號定義的根節點。

FP-tree的構建過程如下：

首先掃描資料集以確定每個專案的支援度計數。不頻繁的專案將被丟棄，而頻繁專案的支援度計數將被保留。

演算法對資料進行第二次遍歷以構建FP-tree。在檢視第一個事務{a, b}後，將建立標記為a和b的節點。將形成一條從null→a→b的路徑來表示該事務。路徑上的每個節點的頻率計數為1。

在檢視第二個事務{b, c, d}後，將為專案b、c和d建立一組新的節點。然後形成一條路徑null→b→c→d來表示該事務。

此路徑上的每個節點的頻率計數也為1。儘管前兩個事務有一個頻繁項b，但它們的路徑是不相交的，因為這些事務不共享頻繁的字首。

第三個事務{a, c, d, e}與第一個事務共享一個頻繁字首項（即a）。因此，第三個事務的路徑null→a→c→d→e與第一個事務的路徑null→a→b重疊。由於它們的路徑重疊，節點a的頻率計數增加到2，而新建立的節點c、d和e的頻率計數仍然為1。

這個過程將持續到每個事務都被對映到FP-tree中的一個路徑為止。FP-tree的大小小於未壓縮資料的大小，因為市場籃子資料中的多個事務共享許多共同的項。

更新於：2022年2月11日

745 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告