數(shù)據(jù)挖掘從大數(shù)據(jù)庫(kù)中挖掘關(guān)聯(lián)規(guī)則(編輯修改稿)
2024-10-06 09:03 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ? 不會(huì)打破交易中的任何模式 ? 包含了序列模式挖掘所需的全部信息 ? 緊密 ? 去除不相關(guān)信息 —不包含非頻繁項(xiàng) ? 支持度降序排列 : 支持度高的項(xiàng)在 FPtree中共享的機(jī)會(huì)也高 ? 決不會(huì)比原數(shù)據(jù)庫(kù)大（如果不計(jì)算樹(shù)節(jié)點(diǎn)的額外開(kāi)銷 ) ? 例子 : 對(duì)于 Connect4 數(shù)據(jù)庫(kù) ,壓縮率超過(guò) 100 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 20 用 FPtree挖掘頻繁集 ? 基本思想 (分而治之 ) ? 用 FPtree地歸增長(zhǎng)頻繁集 ? 方法 ? 對(duì)每個(gè)項(xiàng)，生成它的 條件模式庫(kù) , 然后是它的 條件 FPtree ? 對(duì)每個(gè)新生成的條件 FPtree， 重復(fù)這個(gè)步驟 ? 直到結(jié)果 FPtree為 空 , 或只含 維一的一個(gè)路徑 (此路徑的每個(gè)子路徑對(duì)應(yīng)的相集都是頻繁集 ) 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 21 挖掘 FPtree的主要步驟 1) 為 FPtree中的每個(gè)節(jié)點(diǎn)生成條件模式庫(kù) 2) 用條件模式庫(kù)構(gòu)造對(duì)應(yīng)的條件 FPtree 3) 遞歸構(gòu)造條件 FPtrees 同時(shí)增長(zhǎng)其包含的頻繁集 ? 如果條件 FPtree直包含一個(gè)路徑，則直接生成所包含的頻繁集。 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 22 步驟 1: 從 FPtree 到條件模式庫(kù) ? 從 FPtree的頭表開(kāi)始 ? 按照每個(gè)頻繁項(xiàng)的連接遍歷 FPtree ? 列出能夠到達(dá)此項(xiàng)的所有前綴路徑，得到條件模式庫(kù) 條件模式庫(kù) item cond. pattern base c f:3 a fc:3 b fca:1, f:1, c:1 m fca:2, fcab:1 p fcam:2, cb:1 {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 頭表 Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 23 FPtree支持條件模式庫(kù)構(gòu)造的屬性 ? 節(jié)點(diǎn)褳接 ? 任何包含 ai, 的可能頻繁集，都可以從 FPtree頭表中的 ai沿著 ai 的節(jié)點(diǎn)鏈接得到 ? 前綴路徑 ? 要計(jì)算路徑 P 中包含節(jié)點(diǎn) ai 的頻繁集，只要考察到達(dá) ai 的路徑前綴即可，且其支持度等于節(jié)點(diǎn) ai 的支持度 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 24 步驟 2: 建立條件 FPtree ? 對(duì)每個(gè)模式庫(kù) ? 計(jì)算庫(kù)中每個(gè)項(xiàng)的支持度 ? 用模式庫(kù)中的頻繁項(xiàng)建立 FPtree m條件模是庫(kù) : fca:2, fcab:1 {} f:3 c:3 a:3 mconditional FPtree All frequent patterns concerning m m, fm, cm, am, fcm, fam, cam, fcam ? ? {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 頭表 Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 25 通過(guò)建立條件模式庫(kù)得到頻繁集 Empty Empty f {(f:3)}|c {(f:3)} c {(f:3, c:3)}|a {(fc:3)} a Empty {(fca:1), (f:1), (c:1)} b {(f:3, c:3, a:3)}|m {(fca:2), (fcab:1)} m {(c:3)}|p {(fcam:2), (cb:1)} p 條件 FPtree 條件模式庫(kù) 項(xiàng) 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 26 第 3步 : 遞歸挖掘條件 FPtree {} f:3 c:3 a:3 m條件 FPtree ―am‖的條件模式庫(kù) : (fc:3) {} f:3 c:3 am條件 FPtree ―cm‖的條件模式 : (f:3) {} f:3 cm條件 FPtree ―cam‖條件模式庫(kù) : (f:3) {} f:3 cam條件 FPtree 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 28 特例 : FPtree 中的 唯一 前綴路徑 ? 假定一個(gè) (條件 ) FPtree T 又一個(gè)共享唯一前綴路徑 P ? 挖掘可分解為如下兩個(gè)步驟 ? 用一個(gè)節(jié)點(diǎn)代替此前綴路徑 P ? 分別計(jì)算這兩個(gè)部分的結(jié)果 ? a2:n2 a3:n3 a1:n1 {} b1:m1 C1:k1 C2:k2 C3:k3 b1:m1 C1:k1 C2:k2 C3:k3 r1 + a2:n2 a3:n3 a1:n1 {} r1 = 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 29 頻繁集增長(zhǎng)的原理 ? 模式增長(zhǎng)的特征 ? 令 ? 為 DB的一個(gè)頻繁集， B 為 ? 的條件模式庫(kù)， ? 是 B中的一個(gè)項(xiàng)，要使 ? ? ? 是 DB中的頻繁集，當(dāng)且僅當(dāng) ? 是 B 的頻繁項(xiàng) . ? ―abcdef ‖ 是頻繁集 ,當(dāng)且僅當(dāng) ? ―abcde ‖ 是頻繁集 , 且 ? ―f ‖ 在包含 “ abcde ‖的事務(wù)中是頻繁的。 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 30 為什么 頻繁集增長(zhǎng) 速度快？ ? 我們的性能研究顯示 ? FPgrowth 比 Apriori快一個(gè)數(shù)量級(jí) , 同樣也比 treeprojection 快。 ? 原因 ? 不生成候選集，不用候選測(cè)試。 ? 使用緊縮的數(shù)據(jù)結(jié)構(gòu) ? 避免重復(fù)數(shù)據(jù)庫(kù)掃描 ? 基本操作是計(jì)數(shù)和建立 FPtree 樹(shù) 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 31 FPgrowth vs. Apriori: 相對(duì)于支持度的擴(kuò)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1