改善FP-growth資料挖掘演算法在巨大資料庫的效能

[[abstract]]FP-growth 對於從交易資料庫裡挖掘關聯規則而言是一個非常重要的方 法，但其在挖掘頻繁項目集前，需要先將在交易資料庫裡的所有挖掘頻繁項目建 立成一樹狀結構(FP-tree)，並且保留這個樹狀結構在記憶體。在挖掘關聯規則 的過程中如果電腦的記憶體不足，則會許多的硬碟存取動作導致FP-growth 演算 法的效率不佳。在這篇論文我們針對FP-Growth 的記憶體問題提出一個演算法， 以改善FP-growth 演算法在巨大資料庫的效能。我們所提的演算法分成3 部分， 在第一部分我們會先將交易資料庫的物品項目，分成許多群，而每一群的項目數 目都小於一個由使用者根據記憶體大小自行決定的門檻值。在第二部分我們針對 每群的項目進行FP-Growth，以便挖掘出各部分的頻繁項目集，而在挖掘的過程 中我們修改原來的樹狀架構以有效找尋頻繁項目集所出現的交易編號，並使用一 個壓縮表示法來表示這些尋頻繁項目集和交易編號。在第三部分，我們則利用這 些壓縮的頻繁項目集和交易編號，去整合出所有跨群的頻繁項目集。我們所提的 方法可以使得項目分群更平衡及更彈性，並且可以解決在尋找頻繁項目集過程中 的記憶體問題