《數(shù)據(jù)挖掘期中論》word版-文庫(kù)吧
2024-12-23 16:13 本頁(yè)面
【正文】 的情況下，數(shù)據(jù)庫(kù) DB被添加、刪除或修改時(shí)，如何生成更新后的數(shù)據(jù)庫(kù)的關(guān)聯(lián)規(guī)則。它利用已挖掘得到的頻繁項(xiàng)集信息來(lái)避免重復(fù)計(jì)算頻繁項(xiàng)集支持?jǐn)?shù)的時(shí)間開(kāi)銷(xiāo)來(lái)提高算法效率。 FUP2 算法同時(shí)考慮到增加數(shù)據(jù)庫(kù)和修改、刪除數(shù)據(jù)庫(kù)的情況，比較適用于大量的增加數(shù)據(jù)庫(kù)和少量的刪除數(shù)據(jù)庫(kù)的情況。 IUA、 PIUA 算法都是主要考慮在最小支持度和最小置信度發(fā)生變化而數(shù) 據(jù)庫(kù) DB不變時(shí)，如何生成 DB 中的關(guān)聯(lián)規(guī)則。 IUAR 算法主要考慮在最小支持度和最小置信度和數(shù)據(jù)庫(kù) DB 同時(shí)發(fā)生變化時(shí)，如何生成更新后的關(guān)聯(lián)規(guī)則。 并行挖掘算法 并行算法是利用同時(shí)執(zhí)行的諸過(guò)程的集合相互作用和協(xié)調(diào)完成對(duì)給定問(wèn)題的求解。包括Agrawal 等人提出的 CD、 DD、 CaD 算法， Park 等人提出的 PDM 算法， Cheung 等人提出的 DMA和 FDM 算法等。 CD 算法運(yùn)行在空閑的處理器上進(jìn)行并行冗余計(jì)算以減小通信量，速度幾乎可以達(dá)到線性加速比的速度。但它的缺點(diǎn)是通信量和 候選頻繁項(xiàng)集都比較大。 DD 算法通過(guò)吧候選集劃分到各個(gè)處理器來(lái)克服 CD 算法的缺陷，然而 DD算法由于數(shù)據(jù)移動(dòng)方案效率較低導(dǎo)致通信負(fù)載較大、處理器件的交互模式易倒是處理器處于空閑狀態(tài)、每一筆交易記錄都根據(jù)多個(gè)哈希樹(shù)進(jìn)行處理導(dǎo)致冗余計(jì)算等缺點(diǎn)。 CaD 算法師徒通過(guò)劃分?jǐn)?shù)據(jù)庫(kù)和候選集的辦法來(lái)減少處理器之間的數(shù)據(jù)依賴性，使每個(gè)處理器可以獨(dú)立地進(jìn)行計(jì)算。但它在劃分候選集時(shí)要對(duì)整個(gè)的事務(wù)數(shù)據(jù)庫(kù)進(jìn)行劃分并分配到每一個(gè)處理器節(jié)點(diǎn)中，從而消耗了大量的時(shí)間用于通信。 PDM 算法類(lèi)似于 CD 算法，所有處 理器含有相同的雜湊表和候選集。并行候選集生成的過(guò)程是通過(guò)每個(gè)處理器生成一個(gè)候選子項(xiàng)集，然后交換所有處理器上的子項(xiàng)集，然后交換所有處理器上的子項(xiàng)集生成全局候選集來(lái)實(shí)現(xiàn)。但是 PDM 算法對(duì)非大項(xiàng)集的項(xiàng)目和事務(wù)的物理剪枝要涉及大量磁盤(pán)的 I/O 操作。 簡(jiǎn)單的介紹了四種算法后，下面我引用例子對(duì)增量式更新算法和并行挖掘算法進(jìn)行詳細(xì)的介紹。 例 1：設(shè) I =｛ il， i2， ?， im｝是 m個(gè)不同項(xiàng)目的集合 .給定事務(wù)數(shù)據(jù)庫(kù) D，對(duì)于項(xiàng)目集 X∈ I在 D中的支持?jǐn)?shù)是指 D中包含 X的事務(wù)數(shù)，記為 . X在 D中的支持度是指 D中包含 X事務(wù)的百分比，記為X .supD . 如果 X的支持度不小于用戶給定的最小支持度閾值 s，則稱(chēng) X 為頻繁項(xiàng)目集，如果 X 包含 I個(gè)項(xiàng)目，那么又稱(chēng) X為頻繁 I項(xiàng)目集，頻繁 l項(xiàng)目集簡(jiǎn)稱(chēng)頻繁項(xiàng)目 .挖掘出所有頻繁項(xiàng)目集是關(guān)聯(lián)規(guī)則挖掘的核心問(wèn)題，占據(jù)整個(gè)計(jì)算量的大部分。 給定事務(wù)數(shù)據(jù)庫(kù) D，事務(wù)數(shù)據(jù)集 dl及 d2 （ d2cD） .針對(duì)實(shí)際應(yīng)用需求，關(guān)聯(lián)規(guī)則的更新問(wèn)題可以分為如下兩種情況：（ l）最小支持度 s 發(fā)生變化后如何生成 D 中的頻繁項(xiàng)目集；（ 2）事務(wù)數(shù)據(jù)庫(kù) D 發(fā)生變化后如何生成最新事 務(wù)數(shù)據(jù)庫(kù) D + dl d2中的頻繁項(xiàng)目集 . 最小支持度 S發(fā)生變化后關(guān)聯(lián)規(guī)則增量式更新算法 FIUA1： 設(shè)舊的最小支持度為 s， Ll為 D 中頻繁項(xiàng)目的集合， L 為 D 中頻繁項(xiàng)目集的集合 . 同樣地，對(duì)于新的最小支持度 s39。， L39。l為 D 中頻繁項(xiàng)目的集合， L39。為 D中頻繁項(xiàng)目集的集合 . 當(dāng)最小支持度發(fā)生改變時(shí)，可分為兩種
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1