基于HFUFP-tree的增量挖掘算法研究.pdf

1、數(shù)據(jù)挖掘是近年來(lái)計(jì)算機(jī)研究領(lǐng)域的一個(gè)重要發(fā)展方向，在銀行、電信、保險(xiǎn)、零售等領(lǐng)域有著廣泛的應(yīng)用。其巨大的商業(yè)潛力和應(yīng)用價(jià)值，吸引了眾多研究單位、企業(yè)從事數(shù)據(jù)挖掘技術(shù)的研究和開(kāi)發(fā)工作，每年都有新的數(shù)據(jù)挖掘算法和模型問(wèn)世，人們對(duì)它的研究日益廣泛和深入。
　　 關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領(lǐng)域中最為活躍的研究方向之一。關(guān)聯(lián)規(guī)則在許多商業(yè)決策的制定方面發(fā)揮著不可替代的作用，如分類設(shè)計(jì)，交叉購(gòu)物和賤賣分析等。當(dāng)前關(guān)聯(lián)規(guī)則挖掘算法總體上可分成兩類

2、：靜態(tài)挖掘算法和動(dòng)態(tài)挖掘算法。靜態(tài)挖掘關(guān)聯(lián)規(guī)則算法的研究相對(duì)來(lái)說(shuō)比較深入，近年來(lái)，動(dòng)態(tài)挖掘算法逐漸成為研究的熱點(diǎn)問(wèn)題之一。
　　 隨著互聯(lián)網(wǎng)技術(shù)和數(shù)據(jù)庫(kù)技術(shù)的發(fā)展，各種數(shù)據(jù)量呈快速增長(zhǎng)勢(shì)頭，并以增量形式增長(zhǎng)，導(dǎo)致關(guān)聯(lián)規(guī)則挖掘過(guò)程中，重新掃描海量的初始數(shù)據(jù)庫(kù)需要付出極高的額外成本，造成關(guān)聯(lián)規(guī)則挖掘算法的效率顯著降低。與靜態(tài)關(guān)聯(lián)規(guī)則挖掘算法相比，F(xiàn)UFP-tree和Pre-FUFP等動(dòng)態(tài)增量挖掘算法，在一定程度上克服了靜態(tài)關(guān)聯(lián)規(guī)則挖

3、掘算法在該方面存在的缺陷，但是在某些情況下仍需要重新掃描初始數(shù)據(jù)庫(kù)。如Pre-FUFP算法，其主要依據(jù)項(xiàng)目組在數(shù)據(jù)庫(kù)異動(dòng)前后是否為頻繁項(xiàng)的情形，將各項(xiàng)目組分成四種情況來(lái)分別對(duì)FP-tree結(jié)構(gòu)作調(diào)整。大部分情況下Pre-FUFP算法僅需掃描數(shù)據(jù)庫(kù)中數(shù)據(jù)異動(dòng)的部分，但是當(dāng)有項(xiàng)目組從非頻繁項(xiàng)轉(zhuǎn)變成頻繁項(xiàng)時(shí)，其仍然需要重新掃描整個(gè)數(shù)據(jù)庫(kù)。因此，針對(duì)數(shù)據(jù)頻繁異動(dòng)情況下，開(kāi)展面向數(shù)據(jù)異動(dòng)部分的動(dòng)態(tài)增量挖掘算法研究顯得十分必要。
　　 本文

4、在深入分析Pre-FUFP動(dòng)態(tài)挖掘算法的基礎(chǔ)上，針對(duì)Pre-FUFP在某些情況下，仍需重新掃描初始數(shù)據(jù)庫(kù)的問(wèn)題，開(kāi)展研究工作，以改良Pre-FUFP算法存在的當(dāng)項(xiàng)目組從非頻繁項(xiàng)變成頻繁項(xiàng)時(shí)需重新掃描數(shù)據(jù)庫(kù)的問(wèn)題。本文的主要工作和取得的成果如下：
　　 (1) 簡(jiǎn)要介紹了關(guān)聯(lián)規(guī)則挖掘的相關(guān)理論知識(shí)，并深入分析了靜態(tài)關(guān)聯(lián)規(guī)則挖掘算法和動(dòng)態(tài)關(guān)聯(lián)規(guī)則挖掘算法中幾個(gè)具有代表性的挖掘算法，包括Apriori算法及其改進(jìn)算法，F(xiàn)P-tree算

5、法以及Pre-FUFP算法。闡述了上述算法的特點(diǎn)、步驟、適用的背景及其優(yōu)缺點(diǎn)。重點(diǎn)討論了目前廣受關(guān)注的增量式挖掘算法Pre-FUFP算法，并指出了該算法存在的局限。
　　 (2) 提出了一種基于層次結(jié)構(gòu)的HFUFP-tree（HierarchicAlFast Updated FP-tree）增量挖掘算法。該算法將所有的交易記錄壓縮在一棵HFUFP-tree中，通過(guò)引入較高支持度閾值與較低支持度閾值和MF(Mark-frequen

6、cy)結(jié)點(diǎn)與MPF(Mark-Pre-frequency)結(jié)點(diǎn)，從而將HFUFP-tree從邏輯上劃分為三層。當(dāng)數(shù)據(jù)庫(kù)發(fā)生異動(dòng)后，將各項(xiàng)目組分成九種情況來(lái)分別對(duì)HFUFP-tree結(jié)構(gòu)加以調(diào)整，而不需重新掃描數(shù)據(jù)庫(kù)和構(gòu)建樹(shù)結(jié)構(gòu)，便能快速的挖掘關(guān)聯(lián)規(guī)則。
　　 (3)從精度和效率兩方面，首先對(duì)HFUFP-tree算法與Pre-FUFP算法的性能進(jìn)行了分析。精度方面，兩種算法完全相等，效率方面，在項(xiàng)目狀態(tài)變化頻繁情況下，HFUFP-