一種基于不確定數(shù)據(jù)的高效剪枝挖掘算法

李 峰

（湖南工程學(xué)院 計(jì)算機(jī)與通信學(xué)院，湘潭411104）

當(dāng)今數(shù)據(jù)挖掘已經(jīng)被廣泛地應(yīng)用在各領(lǐng)域大型知識(shí)庫(kù)信息檢索和發(fā)現(xiàn)中.在各種各樣的數(shù)據(jù)挖掘?qū)嵺`中發(fā)展了很多數(shù)據(jù)挖掘方法，特別是頻繁模式挖掘.頻繁模式挖掘既可以分析項(xiàng)目之間的重復(fù)關(guān)系，又可以在用戶給定的最小頻繁閾值上發(fā)現(xiàn)重復(fù)出現(xiàn)的特定模式.

1 頻繁模式挖掘

1.1 確定頻繁模式挖掘

根據(jù)挖掘的數(shù)據(jù)屬性不同，頻繁模式挖掘可分為確定頻繁模式挖掘和不確定頻繁模式挖掘.Apriori［1］和FP-Growth［2］就是典型的確定頻繁模式挖掘算法.在確定頻繁模式挖掘中人們?cè)O(shè)置緊湊的樹(shù)結(jié)構(gòu)，例如FP-tree和LP-tree［3］，這樣可以有效地將信息存儲(chǔ)在搜索樹(shù)中.在實(shí)際研究中，人們對(duì)確定頻繁模式挖掘采用了很多方法.例如，高效用模式挖掘［4］在銷(xiāo)售數(shù)據(jù)中考慮了利潤(rùn)和產(chǎn)品數(shù)量，Top-k頻繁模式挖掘［5］采用了挖掘k個(gè)極大頻繁模式.因此，通過(guò)考慮現(xiàn)實(shí)世界中的特定情況，不同挖掘算法可以在特定領(lǐng)域挖掘更多有價(jià)值的知識(shí).

1.2 不確定頻繁模式挖掘

現(xiàn)實(shí)世界由于測(cè)量的不精確、傳輸?shù)牟环€(wěn)定，獲得的數(shù)據(jù)一般是不確定的，所以基于不確定圖進(jìn)行挖掘才更有實(shí)際意義.人們研究了大量不確定子圖挖掘算法.如Zhang［6］給出了不確定圖中的子圖分離和判定方法；LI等［7］提出一種高效子圖挖掘算法；張碩等［8］探討不確定圖數(shù)據(jù)庫(kù)中高效查詢處理方法；Zou等［9］提出一種新穎的不確定圖子圖挖掘算法.

1.3 剪枝挖掘算法

剪枝模式挖掘最早是由Gadelha等［10］提出，后來(lái)Deng等［11］提出了MERIT剪枝模式挖掘算法.該方法使用WPPC-tree的樹(shù)結(jié)構(gòu)將項(xiàng)目名、收益和訂單信息都保存到每個(gè)節(jié)點(diǎn)，并在掃描樹(shù)節(jié)點(diǎn)時(shí)根據(jù)包含在節(jié)點(diǎn)中的項(xiàng)目名稱對(duì)節(jié)點(diǎn)信息依次進(jìn)行分組，生成中間檢索集.當(dāng)生成的檢索集長(zhǎng)度為K時(shí)，使用等價(jià)類(lèi)檢查每個(gè)子集是否為剪枝挖掘模式.由于在挖掘過(guò)程中檢測(cè)過(guò)頻，該算法無(wú)法發(fā)現(xiàn)所有剪枝挖掘模式.

后來(lái)Le Tuong等提出了DMERIT算法，該算法在進(jìn)行模式挖掘過(guò)程時(shí)不使用模式等價(jià)關(guān)系，只為每個(gè)模式設(shè)置一個(gè)檢測(cè)集，因此它可以挖掘所有剪枝模式.通過(guò)剪枝挖掘算法能有效地解決生產(chǎn)中的產(chǎn)品生產(chǎn)和管理問(wèn)題.

但傳統(tǒng)剪枝模式挖掘算法不能完全智能化執(zhí)行制造業(yè)管理者的決策，因?yàn)閭鹘y(tǒng)的剪枝挖掘算法只考慮產(chǎn)品利潤(rùn)，不涉及組件成本.因此傳統(tǒng)的剪枝挖掘算法在產(chǎn)品可靠性不高的情況下，只會(huì)采用模糊方法挖掘頻繁模式，所以需要大量的時(shí)間，效率相對(duì)較低，不能快速獲取制造業(yè)管理者所需要的決策樹(shù).

但在現(xiàn)實(shí)中，當(dāng)生產(chǎn)過(guò)程發(fā)生變化時(shí)，工廠管理者不僅需要考慮組件與產(chǎn)品利潤(rùn)的關(guān)系，還要考慮組件成本.為了解決傳統(tǒng)剪枝挖掘算法低效和可靠性不高的問(wèn)題，提出了一種基于加權(quán)剪枝模式挖掘算法，該方法在以組件成本為權(quán)重的情況下，采用基于低估值約束的有效剪枝方法，并通過(guò)基于組件權(quán)重的挖掘索引器來(lái)發(fā)現(xiàn)頻繁模式.通過(guò)這種方法，不僅獲得了可靠的結(jié)果，而且提高了資源的可用性.

本文的貢獻(xiàn)主要包括以下兩個(gè)方面：

（1）提供了一種新穎的基于低估值約束的有效剪枝方法，該方法能有效地挖掘頻繁模式.

（2）算法使用了權(quán)重因子，通過(guò)基于組件權(quán)重的挖掘索引器來(lái)剪枝，大大縮短了計(jì)算時(shí)間，而且不會(huì)影響利潤(rùn)計(jì)算的準(zhǔn)確性.

2 基于剪枝模式的挖掘

2.1 剪枝模式

假設(shè)D={p1,p2,p3,…,pn}是基于權(quán)重的產(chǎn)品數(shù)據(jù)庫(kù).I={i1,i2,i3,…,im}是D中所有不同項(xiàng)的集合.每個(gè)產(chǎn)品pk(1≤k≤n)由唯一的PID鍵值確定.PID鍵值是數(shù)據(jù)庫(kù)I中包含的項(xiàng)和產(chǎn)品利潤(rùn)的集合.表1是一個(gè)產(chǎn)品數(shù)據(jù)庫(kù)的示例，其中包括產(chǎn)品及其利潤(rùn).例如p3產(chǎn)品由G項(xiàng)和D項(xiàng)組成，其利潤(rùn)為130萬(wàn)元.

定義1（收益模式）若X={i1,i2,i3,…,im}表示項(xiàng)目，pk表示產(chǎn)品.X增益就是產(chǎn)品利潤(rùn)之和，表示如下：

表1 產(chǎn)品利潤(rùn)表

定義2（最大收益閾值）給定用戶設(shè)定收益百分比θ，最大收益MaxGain就是數(shù)據(jù)庫(kù)中所有產(chǎn)品最大收益百分比，表示如下：

例如在表1中若θ是40%，MaxGain則是0.4×0.08=3.2%.

基于定義2能得出剪枝模式，若X的收益小于等于MaxGain，模式X就是剪枝模式，也就是說(shuō)，X滿足下面公式

2.2 剪枝模式算法描述

為了從product數(shù)據(jù)庫(kù)中發(fā)現(xiàn)加權(quán)剪枝挖掘模式，依次執(zhí)行以下過(guò)程.第一步，通過(guò)掃描一次數(shù)據(jù)庫(kù)，提取長(zhǎng)度為1的剪枝挖掘模式的候選模式集合.第二步，使用數(shù)據(jù)庫(kù)和候選對(duì)象生成剪枝樹(shù)，并讓候選對(duì)象按頻率降序排序，創(chuàng)建低估值約束.最后根據(jù)剪枝樹(shù)的信息建立基于組件權(quán)重的挖掘索引器，挖掘頻繁模式.

2.3 詳細(xì)的算法

2.3.1 基于樹(shù)結(jié)構(gòu)剪枝挖掘模式算法

下面是基于樹(shù)結(jié)構(gòu)剪枝挖掘模式算法.

輸入：產(chǎn)品庫(kù)D，項(xiàng)目WI，最大利潤(rùn)閾值MGT輸出：剪枝挖掘模式

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)采用Inter i5-5200 3.00 GHz的CPU，4 GB內(nèi)存，win7操作系統(tǒng)，所有程序使用C++語(yǔ)言編程.可從2個(gè)大數(shù)據(jù)庫(kù)，UCI數(shù)據(jù)庫(kù)和FIMI數(shù)據(jù)庫(kù)，獲得初始實(shí)驗(yàn)數(shù)據(jù).在UCI數(shù)據(jù)庫(kù)中選取Churn數(shù)據(jù)集，在FIMI數(shù)據(jù)庫(kù)中選取Mush和Pums數(shù)據(jù)集.

三個(gè)數(shù)據(jù)集都是多元數(shù)據(jù)集，其中Churn包含3150個(gè)產(chǎn)品項(xiàng)和402組數(shù)據(jù)項(xiàng)，而Mush和Pums的產(chǎn)品項(xiàng)和組數(shù)據(jù)項(xiàng)分別為8124、120和49046、7117.在數(shù)據(jù)集中，每件產(chǎn)品的利潤(rùn)設(shè)置從100到1500，由一個(gè)隨機(jī)函數(shù)RAND（800，50）產(chǎn)生，這里800是平均利潤(rùn)，50是每次變動(dòng)幅度.為了更加真實(shí)，讓利潤(rùn)滿足正態(tài)分布函數(shù)N（800，1600）.在三個(gè)數(shù)據(jù)集的實(shí)驗(yàn)中用PM和MERIT、DMERIT相比較，結(jié)果如圖1、圖2、圖3、圖4所示.

圖1、圖2分別表示在Pums和Mush數(shù)據(jù)集中候選模式的數(shù)量（PATTERNS）和最大收益百分比（Max Gain)之間的關(guān)系.可以看到挖掘出的候選模式的數(shù)量隨著MaxGain的增加而增加.MERIT和DMERIT有相似的挖掘結(jié)果，挖掘效率都不高.特別當(dāng)MaxGain的值大于4.05%的時(shí)候，挖掘出的候選模式的數(shù)量都明顯增加.我們的方法（PM）相對(duì)前2種算法生成的候選模式更少，因此可以更快更有效地進(jìn)行頻繁模式挖掘，而且不會(huì)隨MaxGain增加急速增加，算法穩(wěn)定有效.

圖1 在Pums中候選模式隨著MaxGain變化

圖2 在Mush中候選模式隨著MaxGain變化

圖3、圖4分別表示在Churn和Mush數(shù)據(jù)集中，運(yùn)行時(shí)間隨著MaxGain的增加而增加.在圖中不難發(fā)現(xiàn)當(dāng)MaxGain超過(guò)3.9%時(shí)，MERIT和DMERIT運(yùn)行時(shí)間急劇增加，運(yùn)行效率大幅降低.在圖中可以看到相對(duì)其他2種算法，本方法（PM）有著更少的運(yùn)行時(shí)間，且時(shí)間消耗不會(huì)隨著MaxGain增加突然增加，變化明顯相對(duì)平穩(wěn).所以說(shuō)算法更加快捷、穩(wěn)定.

圖3 在Churn中運(yùn)行時(shí)間隨著MaxGain變化

圖4 在Mush中運(yùn)行時(shí)間隨著MaxGain變化

4 結(jié)論

本文提出了一種基于不確定數(shù)據(jù)高效剪枝挖掘算法，通過(guò)使用基于低估值的約束和基于組件權(quán)重的挖掘索引器進(jìn)行的有效剪枝挖掘，不但考慮了利潤(rùn)信息，而且考慮了權(quán)重信息.實(shí)驗(yàn)證明本文算法在挖掘不確定數(shù)據(jù)庫(kù)的頻繁模式時(shí)相對(duì)于現(xiàn)有算法耗時(shí)更少，效率更高.