靳曉樂,劉峽壁,馬 驍

(北京理工大學(xué) 智能信息技術(shù)北京市重點實驗室,北京 100081)

0 概述

關(guān)聯(lián)分析用于尋找隱藏在大型數(shù)據(jù)集中有意義的關(guān)聯(lián)關(guān)系，是數(shù)據(jù)挖掘的一項重要技術(shù)[1-2]。傳統(tǒng)的關(guān)聯(lián)分析主要包括頻繁項集挖掘和關(guān)聯(lián)規(guī)則挖掘，其中，關(guān)聯(lián)規(guī)則挖掘是基于頻繁項集挖掘的結(jié)果，而頻繁項集挖掘較為耗時。因此，頻繁項集挖掘算法受到廣泛關(guān)注[3-5]。然而,這類算法的計算目標(biāo)是找出共現(xiàn)概率高于用戶定義的最小支持度的項集,從而只關(guān)注項在事務(wù)中的有無和事務(wù)的頻次,并沒有考慮到項在事務(wù)中出現(xiàn)的次數(shù)和項自身的價值,即沒有考慮到項之間的區(qū)別,而用戶不僅僅對數(shù)據(jù)中的高頻次項集感興趣,更關(guān)心的是具有高價值的項集。高效用項集挖掘思想[6]旨在發(fā)現(xiàn)效用價值高的項集,項本身的價值和項在每一條事務(wù)中出現(xiàn)的次數(shù)能夠反映項集的效用。

目前,高效用項集挖掘算法[7]存在以下問題:

1)最小效用閾值是人為設(shè)定,在對數(shù)據(jù)集沒有一定了解的情況下,很難確定最小效用閾值,若最小效用閾值設(shè)置過高,則可能導(dǎo)致沒有高效用項集產(chǎn)生。

2)傳統(tǒng)高效用項集挖掘算法是在全部搜索空間中通過剪枝來減小搜索空間,搜索空間較大。

針對上述問題,本文提出一種基于雙重二元粒子群優(yōu)化(Double Binary Particle Swarm Optimization,DBPSO)的高效用項集挖掘算法。該算法利用最小相對效用閾值與效用上界乘積得到最小效用閾值。通過挖掘候選子空間內(nèi)的高效用項集代替全部搜索空間,并給出分散子空間方法作為候選子空間的確定方式。

1 相關(guān)工作

高效用項集挖掘是關(guān)聯(lián)分析的關(guān)鍵問題之一,由于是指數(shù)級搜索空間,挖掘效率一直不高。目前高效用項集挖掘算法主要包括3種:兩階段算法,一階段算法和基于智能優(yōu)化的算法。

兩階段算法是通過產(chǎn)生-測試2個過程來挖掘高效用項集:通過一定的策略產(chǎn)生候選集、計算每個候選集的真實效用得到最終的高效用集。文獻(xiàn)[8]提出用于剪枝的TWU(Traction Weighted Utilization)模型和Two-Phase算法,該算法以Apriori算法和TWU模型產(chǎn)生候選集,通過掃描數(shù)據(jù)庫計算候選集的真實效用值。由于Apriori多次掃描數(shù)據(jù)庫的問題,文獻(xiàn)[9]提出基于模式增長方式的挖掘算法(Incremental High Utility Pattern,IHUP),需要兩次掃描數(shù)據(jù)庫,即可產(chǎn)生候選集。文獻(xiàn)[10]提出IHUP的改進(jìn)算法UP-Growth,減少候選項集的個數(shù)。文獻(xiàn)[11]為減少基于樹結(jié)構(gòu)建樹產(chǎn)生的耗時,將項集信息存儲在數(shù)組中,提出基于投影的高效用模式挖掘算法(High Utility Pattern Mining on Projection,HUPMP)。從本質(zhì)上看,上述算法均是產(chǎn)生-測試的兩階段算法框架,無論采用Apriori類方法還是FP-growth類方法,雖然在一定程度上進(jìn)行剪枝,但仍然會產(chǎn)生大量候選項集,具有較大的內(nèi)存需求且生成候選項集的過程相當(dāng)耗時,降低挖掘高效用項集的性能。因此,研究人員提出一階段算法,即直接產(chǎn)生挖掘高效用項集而非候選項集。文獻(xiàn)[12]提出HUI-Miner屬于一階段算法,該算法通過使用高效用列表的數(shù)據(jù)結(jié)構(gòu)避免產(chǎn)生候選集,效用列表存儲項集的效用信息和剪枝的必要信息。文獻(xiàn)[13]在HUI-Miner基礎(chǔ)上進(jìn)行優(yōu)化,有效降低了挖掘過程中產(chǎn)生的項集個數(shù)。文獻(xiàn)[14]繼續(xù)在模式增長方式基礎(chǔ)上進(jìn)行研究,提出HUPM-FP算法,與IHUP和UP-growth不同,該算法采用模式增長直接挖掘高效用模式,而不是候選項集,屬于一階段算法。

除了上述利用各種數(shù)據(jù)結(jié)構(gòu)和剪枝策略挖掘[15]全部的高效用項集外,同樣可以將智能計算的優(yōu)化算法應(yīng)用到高效用項集挖掘問題中,該算法雖然不能保證得到全部的高效用項集,但可以通過探索較小的子空間來得到盡可能多的高效用項集,如使用遺傳算法的HUIM-GA[16]、使用基本粒子群優(yōu)化算法的HUIM-BPSO[17-18]。其中,HUIM-GA是首次引進(jìn)進(jìn)化算法到高效用項集挖掘問題,該算法允許負(fù)效用的存在。但由于遺傳算法參數(shù)較多,文獻(xiàn)[17]提出使用基本粒子群算法解決高效用項集挖掘算法?；谏鲜鲅芯?本文使用二元粒子群優(yōu)化算法。

2 本文方法

在高效用項集挖掘中,最小效用閾值的確定直接關(guān)系到高效用項集的個數(shù)及算法的運(yùn)行時間。目前最小效用閾值的確定是通過總效用的比例設(shè)置,然而對效用數(shù)據(jù)庫來說,總效用和項集效用差別很大,在某一個數(shù)據(jù)集上合理的比例在其他數(shù)據(jù)集上可能就變得過高,導(dǎo)致過多耗時卻沒有高效用項集產(chǎn)生。

挖掘高效用項集是在項集中搜索出效用高于最小效用閾值的項集,其本質(zhì)是一個搜索過程,通過搜索子空間代替全部搜索空間可以提高搜索效率。由于粒子群算法實現(xiàn)簡單,性能良好,可以通過離散粒子群算法來確定候選子空間,相當(dāng)于在指數(shù)搜索空間中建立大小為O(kn)的子空間。其中,k為最大迭代次數(shù),n為粒子數(shù)。傳統(tǒng)離散粒子群算法的子空間是在效用最大的項集周圍,導(dǎo)致挖掘的高效用項集個數(shù)較少。如何在不增大候選子空間的情況下使O(kn)的子空間覆蓋更多的高效用項集是本文的研究目標(biāo)。

本文算法通過改進(jìn)最小效用閾值的確定方式,避免了不會產(chǎn)生高效用項集的情況,利用改進(jìn)子空間確定方式,可以實現(xiàn)在和傳統(tǒng)離散粒子群算法相等子空間大小情況下挖掘到更多的高效用項集。DBPSO算法框架如圖1所示。

圖1 DBPSO算法框圖

高效用項集挖掘包含2個過程:一是計算效用上界,和最小相對效用閾值相乘確定最小效用閾值;二是根據(jù)最小效用閾值,使用分散子空間方法對數(shù)據(jù)庫進(jìn)行挖掘,得到高效用項集。由于計算效用上界和分散子空間挖掘高效用項集都是搜索問題,為了提高計算效率,本文對基本離散粒子群算法進(jìn)行改進(jìn),提出雙重二元粒子群優(yōu)化算法。

2.1 DBPSO算法

DBPSO作為智能優(yōu)化算法,應(yīng)用于計算最大效用和挖掘高效用項集,包括粒子編碼、初始種群生成、更新規(guī)則和適應(yīng)度函數(shù)等部分。

粒子初始化是隨機(jī)產(chǎn)生方式,在0到n之間隨機(jī)產(chǎn)生數(shù)k,用來表示粒子中1的個數(shù),再通過適應(yīng)度比例選擇法即輪盤賭方法產(chǎn)生1的位置,其中每個位置的適應(yīng)度采用每一項事務(wù)加權(quán)效用值進(jìn)行度量。更新規(guī)則如下:

gbestk)

(1)

其中,F1為基本離散粒子群更新規(guī)則[19],即對速度通過Sigmoid函數(shù)處理之后轉(zhuǎn)化為位置取1的概率,具體如下:

(2)

(3)

(4)

由于該方法未考慮到位置之間的關(guān)系,F1本質(zhì)為變異操作,因此引入交叉操作F2和F3,其中,F2表示概率為c1的交叉操作,交叉對象為當(dāng)前解與局部最優(yōu)解,F3表示概率為c2的交叉操作,交叉對象為當(dāng)前解與全局最優(yōu)解,由于本文方法包含2個粒子群,因此稱為雙重二元粒子群算法。

迭代前期,粒子的自我認(rèn)知較社會認(rèn)知更重要,迭代后期,正好相反,故可以在迭代過程中,通過調(diào)整c1和c2控制粒子自我認(rèn)知和社會認(rèn)知的比重。隨著迭代次數(shù)的增加,自我認(rèn)知比重由高到低,社會認(rèn)知比重由低到高。即c1和c2采用異步時變方法,定義如下:

(5)

(6)

其中,p0為最小交叉概率,p1為最大交叉概率,curIter為當(dāng)前迭代次數(shù),maxIter為最大迭代次數(shù)。適應(yīng)度函數(shù)對計算最大效用和挖掘高效用項集有不同的表達(dá)形式。

2.2 最小效用閾值確定方法

本文提出利用最小相對效用閾值和效用上界乘積作為最小效用閾值的確定方法,保證最小效用閾值不會大于效用上界,必然存在高效用項集,避免項集總效用比例設(shè)定方式造成沒有高效用項集產(chǎn)生的情況。

以數(shù)據(jù)集ChessHUI[20]為例,說明本文的最小效用閾值確定方法。該數(shù)據(jù)集是由真實數(shù)據(jù)集chess增加人工效用信息而來,其中chess數(shù)據(jù)集是從UCI數(shù)據(jù)集中提取用來驗證頻繁項集挖掘算法的效率和效果,而效用信息分為內(nèi)部效用和外部效用,內(nèi)部效用通過[1,10]均勻分布產(chǎn)生,外部效用服從高斯分布。數(shù)據(jù)集基本參數(shù)如表1所示。

表1 數(shù)據(jù)集參數(shù)

先驗知識和項集效用上界未知,設(shè)定最小效用閾值只能通過總效用的百分比確定,由表1中項集效用上界與數(shù)據(jù)集總效用的比值可以看出,若把比例設(shè)置高于0.32,則最小效用閾值將高于690 130,項集效用上界為685 719,因此,不會有高效用項集產(chǎn)生。為了得到相對合理的最小效用閾值,需要不斷調(diào)整比例,耗時且盲目。

多次調(diào)整總效用比例的原因在于不合理的總效用比例會導(dǎo)致最小效用閾值高于效用上界。若項集效用上界已知,可以通過項集效用上界的比例即相對效用來設(shè)定最小效用閾值,得到的最小效用閾值必小于效用上界,避免沒有高效用項集產(chǎn)生。

效用上界通過DBPSO算法快速計算得到,粒子X的適應(yīng)度值fitness(X)=utility(X),具體算法如下:

算法1DBPSO計算效用上界算法

初始化粒子群;

Do

引理 1 對于樣本模型Yi=m(Xi)+εi,i=1,2,···,n.^mH(x)為m(x)具有帶寬矩陣H的局部線性估計,并滿足文獻(xiàn)[13]中的正則條件.設(shè)x為一個非邊界點,則在給定X1,X2,···,Xn 下^mH 的偏倚為

For 每個粒子Xi

計算其適應(yīng)度f(Xi)

If (適應(yīng)度優(yōu)于粒子Xi的歷史最優(yōu)值)

用Xi更新歷史最優(yōu)個體pbest

End

選取當(dāng)前粒子群中最佳粒子作為gbest

For 每個粒子

按式(2)更新粒子速度

按式(3)、式(4)更新粒子位置

End

While(最大迭代數(shù)未達(dá)到)

得到gbest和f(gbest)

2.3 分散子空間方法

傳統(tǒng)進(jìn)化算法和群智能算法的高效用項集挖掘是將項集的效用作為適應(yīng)度值,導(dǎo)致搜索空間集中在最高效用附近,增大迭代次數(shù),只能得到較少的高效用項集。本文提出分散子空間方法,在不增大搜索子空間大小情況下,使子空間更加分散,挖掘到更多的高效用項集,如圖2所示。

圖2 子空間分散的挖掘高效用項集示意圖

算法搜索n個子空間,將n個子空間挖掘到的高效用項集合并作為高效用項集。n個子空間由適應(yīng)度函數(shù)決定,當(dāng)算法搜索第k個子空間時,其項集X(k)的適應(yīng)度函數(shù)f(X(k))為:

(7)

適應(yīng)度函數(shù)確定以后,通過DBPSO算法挖掘高效用項集,具體算法描述如下:

算法2基于DBPSO的分散子空間挖掘

初始化子空間K=1

Do

Do

初始化粒子群

For 每個粒子Xi

計算其適應(yīng)度f(Xi)和效用值u(Xi)

If (效用值大于最小效用閾值)

將Xi加入高效用項集HUI中

If (適應(yīng)度優(yōu)于Xi的歷史最優(yōu)值)

用Xi更新歷史最優(yōu)個體pbest

End

選取當(dāng)前粒子群中最佳粒子作為gbest

For 每個粒子

按式(2)更新粒子速度;

按式(3)、式(4)更新粒子位置;

按式(1)更新粒子位置

End

While(HUI個數(shù)連續(xù)40次增加)

K=K+1

While(最大迭代數(shù)未達(dá)到)

得到高效用項集HUI

3 實驗結(jié)果與分析

3.1 實驗設(shè)置

3.1.1 實驗環(huán)境與實驗數(shù)據(jù)

實驗環(huán)境如下:Intel Core i7-2600 CPU,10 GB內(nèi)存計算機(jī),操作系統(tǒng)為64位Windows,IDE為IDEA,編程語言為java。實驗數(shù)據(jù)使用ChessHUI[20]。

3.1.2 參數(shù)設(shè)置

在本次實驗中,粒子群大小設(shè)置為30,最大迭代次數(shù)為1 000,即搜索子空間為O(30×1 000)。

HUIM-DBPSO算法參數(shù)確定,包括w、c1、c2、d1、d2和Vmax。

從數(shù)學(xué)上分析慣性因子w和學(xué)習(xí)因子c1(d1)和c2(d2)是等價的[21],故在實驗過程中選擇w的值為1,通過更改c1(d1)和c2(d2)調(diào)整參數(shù)。收斂情況與c1和c2的關(guān)系如圖3所示。

圖3 最大效用與c1和c2關(guān)系變化曲線

從圖3可以看出,當(dāng)c1和c2呈負(fù)相關(guān)時,隨著迭代次數(shù)的增加,c1減小,c2增加時,收斂最快,證明算法采用異步時變的正確性。

算法收斂情況與d1和d2關(guān)系如圖4所示。由圖4(a)可以看出,不同的d2值對算法收斂性有一定影響,較大的d2值收斂較快,但當(dāng)d2大于6之后,收斂性基本不變。由圖4(b)可以看出,不同的d1值對算法收斂性沒有明顯影響。同時由圖4(a)看出,采用從2到10均勻變化的d2值并不會提高收斂速度,故在本文實驗中,設(shè)置d1=0,d2=6。

圖4 最大效用與d1和d2關(guān)系變化曲線

算法收斂與Vmax的關(guān)系如圖5所示。由圖5可以看出,當(dāng)Vmax>4時,收斂速度小于Vmax=4;當(dāng)Vmax<4時,不僅收斂速度慢,同時收斂值也不是最優(yōu),即陷入局部最優(yōu),故實驗設(shè)置Vmax=4。

圖5 最大效用與Vmax變化曲線

3.2 實驗結(jié)果

下文從收斂速度、高效用項集數(shù)量和執(zhí)行時間證明方法的正確性和有效性。

3.2.1 收斂速度

計算效用上界和挖掘高效用項集過程使用對基本二元粒子群優(yōu)化算法改進(jìn)的DBPSO算法,通過對比BBPSO和DBPSO在計算效用上界過程的收斂速度證明DBPSO算法更新規(guī)則的合理性和有效性,結(jié)果如圖6所示。

圖6 2種算法效用值對比

從圖6可以看出,BBPSO算法能夠在第62次迭代時收斂到最優(yōu)值685 719,融入交叉操作后的DBPSO算法能夠提高收斂速度,在第51次收斂到最優(yōu)值,證明本文方法是可行的。

DBPSO算法將交叉算子以粒子群的方式融入BBPSO算法中,其實質(zhì)是利用交叉算子將項與項之間的關(guān)系信息加入到粒子更新過程,相比BBPSO,使用了更多的信息,因此加快了算法的收斂速度。

3.2.2 高效用項集數(shù)量

原始適應(yīng)度函數(shù)使用效用信息,在進(jìn)化過程中,只搜尋最高效用區(qū)域,但對高效用項集挖掘問題,高效用項集不集中在某一塊區(qū)域,本文提出的改進(jìn)適應(yīng)度函數(shù)能夠使得在不增大子空間的前提下,使子空間更加分散,從而覆蓋更多的高效用項集。

高效用項集個數(shù)和適應(yīng)度函數(shù)的關(guān)系如圖7所示。從圖7(a)可以看出,使用原始適應(yīng)度函數(shù),即用文獻(xiàn)[18]算法,當(dāng)算法收斂后,增加迭代次數(shù),只能在最大效用項集附近搜索,得到的高效用項集較少,而使用改進(jìn)的適應(yīng)度函數(shù)后,隨著迭代次數(shù)的增加,搜索的區(qū)域也不斷增加,得到更多的高效用項集。算法結(jié)束后所挖掘到的高效用項集個數(shù)對比如圖7(b)所示,可以看出,使用改進(jìn)的適應(yīng)度函數(shù),可以產(chǎn)生接近全部的高效用項集,而使用原始適應(yīng)度函數(shù),得到的高效用項集為全部高效用項集的一半左右甚至更低,證明了分散子空間方法的正確性和有效性。

圖7 高效用項集個數(shù)與適應(yīng)度函數(shù)關(guān)系

3.2.3 執(zhí)行時間

基于粒子群優(yōu)化算法的高效用項集挖掘?qū)儆诙A段算法,是在產(chǎn)生候選項集后通過精確計算項集的效用確定是否為高效用項集。與傳統(tǒng)二階段算法的區(qū)別在于粒子群算法通過迭代遍歷的位置成為候選項集,而傳統(tǒng)的二階段算法是在指數(shù)空間中剪枝不合理的子空間,剩余的子空間成為候選項集。UP-Growth算法是目前廣泛應(yīng)用且效果較優(yōu)的二階段算法,將分散子空間方法和其進(jìn)行對比,能夠表明方法的高效性。對比結(jié)果如表2所示。

表2 DBPSO和UP-Growth對比結(jié)果

在表2中,DBPSO算法執(zhí)行時間低于UP-Growth算法,通過候選項集個數(shù)可以看出,DBPSO算法減小了傳統(tǒng)算法的搜索空間,雖然沒有得到全部的高效用項集,但效率明顯提高。

4 結(jié)束語

本文提出一種基于雙重二元粒子群優(yōu)化的高效用項集挖掘算法。該算法不僅通過以粒子群引入交叉算子的方式加快收斂速度,而且通過改變適應(yīng)度函數(shù)的分散子空間方法挖掘更多的高效用項集。實驗結(jié)果表明,相比傳統(tǒng)的二階段高效用項集挖掘算法,本文算法節(jié)約100倍左右時間,具有較高的效率。下一步將考慮從算法的并行計算角度加快算法運(yùn)行效率。