基于多目標(biāo)進(jìn)化算法的任務(wù)驅(qū)動(dòng)模式挖掘研究.pdf

1、多目標(biāo)優(yōu)化問題是一類常見于各種科研以及工程應(yīng)用中的問題，與經(jīng)典單目標(biāo)最優(yōu)化問題不同，多目標(biāo)問題中涉及到的各個(gè)目標(biāo)相互之間存在著一定的沖突關(guān)系。目前在多目標(biāo)領(lǐng)域存在很多不同類型的算法來解決該問題，而這其中，進(jìn)化算法由于具有良好并行性、全局搜索以及對(duì)任何函數(shù)類可用等特性，在解決多目標(biāo)優(yōu)化問題上體現(xiàn)出了良好的性能，因此，多目標(biāo)進(jìn)化算法成為解決多目標(biāo)優(yōu)化問題的一個(gè)主流方法，并引起學(xué)者們的廣泛關(guān)注。任務(wù)驅(qū)動(dòng)的模式挖掘作為頻繁模式挖掘領(lǐng)域的一個(gè)分支

2、，由于其廣闊的應(yīng)用場景，例如商品組合推薦、網(wǎng)頁打印區(qū)域推薦等等，已經(jīng)越來越多地引起人們的關(guān)注。在這些任務(wù)驅(qū)動(dòng)的應(yīng)用中，推薦給用戶的模式作為一個(gè)完整的任務(wù)并且該任務(wù)有許多子任務(wù)組成，因此這些模式稱之為任務(wù)驅(qū)動(dòng)模式。考慮到任務(wù)驅(qū)動(dòng)模式中往往是一系列相互關(guān)聯(lián)的子任務(wù)，因此子任務(wù)間的相關(guān)性較高，在挖掘過程中就需要考慮挖掘模式的完整性，以免影響用戶的體驗(yàn)。傳統(tǒng)任務(wù)驅(qū)動(dòng)的模式挖掘算法采用對(duì)事務(wù)數(shù)據(jù)庫(Transaction Database)的字典

3、子集樹進(jìn)行深度優(yōu)先遍歷搜索的方式，在搜索的過程中利用剪枝的策略提高運(yùn)行效率。然而基于字典子集樹遍歷的傳統(tǒng)方法難以在實(shí)際應(yīng)用中開展，因?yàn)樗惴ㄐ枰鶕?jù)具體問題的先驗(yàn)知識(shí)設(shè)置參數(shù)，例如:搜索時(shí)最小的支持度閾值min_sup，最小的占有度閾值min_occ以及支持度與占有度之間的一個(gè)偏好權(quán)值λ等，而且不同的參數(shù)對(duì)算法的結(jié)果影響很大，另外算法的效率也不盡人意。
　　本研究主要內(nèi)容包括：⑴從多目標(biāo)優(yōu)化的角度出發(fā)解決任務(wù)驅(qū)動(dòng)模式挖掘問題，并提出

4、了一種有效的多目標(biāo)模式挖掘算法。在任務(wù)驅(qū)動(dòng)模式挖掘領(lǐng)域中，傳統(tǒng)算法需要用戶設(shè)置一些必要的先驗(yàn)參數(shù)。而這些參數(shù)往往對(duì)傳統(tǒng)算法有較大的影響，不同的參數(shù)使得算法的運(yùn)行時(shí)間以及運(yùn)行效果差別很大。因此，為了獲得較好的性能，傳統(tǒng)算法需要用戶預(yù)先設(shè)置合適的參數(shù)。但在實(shí)際應(yīng)用中，用戶在缺乏具體問題先驗(yàn)知識(shí)的情況下難以選擇出合適的參數(shù)，而且對(duì)于不同的問題其合適的參數(shù)也會(huì)大不相同。為了尋找合適的參數(shù)，用戶需要嘗試不同參數(shù)進(jìn)行多次實(shí)驗(yàn)以尋找最佳效果，這樣使得

5、算法的運(yùn)行代價(jià)昂貴，效率低下，最終難以在實(shí)際應(yīng)用中展開?；诖?，本文考慮多目標(biāo)進(jìn)化算法不需要根據(jù)具體問題設(shè)置先驗(yàn)參數(shù)這一良好特性，將任務(wù)驅(qū)動(dòng)模式挖掘問題轉(zhuǎn)化為一個(gè)3目標(biāo)（支持度，占有度以及覆蓋度）的多目標(biāo)優(yōu)化問題來處理。在經(jīng)典多目標(biāo)進(jìn)化算法NSGA-Ⅱ的基礎(chǔ)上，本文提出了一種有效的多目標(biāo)模式挖掘算法，簡稱MOPM。最后通過在真實(shí)數(shù)據(jù)集Smart Print數(shù)據(jù)集、Taobao數(shù)據(jù)集以及合成數(shù)據(jù)集IBM數(shù)據(jù)集上分別進(jìn)行實(shí)驗(yàn)，結(jié)果表明，MO

6、PM算法不需要根據(jù)具體問題設(shè)置先驗(yàn)參數(shù)，解決了傳統(tǒng)算法中參數(shù)敏感性的問題，而且MOPM算法在實(shí)驗(yàn)效果以及運(yùn)行效率上都較傳統(tǒng)算法有一定的優(yōu)勢。因此，從多目標(biāo)優(yōu)化的角度來解決任務(wù)驅(qū)動(dòng)模式挖掘問題是一種行之有效的方式。⑵提出了一種基于代理模型的多目標(biāo)模式挖掘算法。從第一個(gè)研究工作中可以發(fā)現(xiàn)，用多目標(biāo)優(yōu)化的視角來解決任務(wù)驅(qū)動(dòng)模式挖掘問題能夠有效解決傳統(tǒng)算法遇到的參數(shù)敏感性等挑戰(zhàn)，促進(jìn)了算法在實(shí)際中的應(yīng)用。然而隨著事務(wù)數(shù)據(jù)庫規(guī)模的增大，MOPM算

7、法在運(yùn)行時(shí)效率會(huì)受到很大的影響。通過分析，發(fā)現(xiàn)由于進(jìn)化算法在計(jì)算個(gè)體的3個(gè)目標(biāo)值時(shí)都需要對(duì)事務(wù)數(shù)據(jù)庫的全部數(shù)據(jù)進(jìn)行遍歷，因此真實(shí)評(píng)價(jià)個(gè)體的目標(biāo)值代價(jià)昂貴。基于此，本文提出了一種基于代理模型的多目標(biāo)模式挖掘算法，簡稱SA-MOPM，用以提高算法的運(yùn)行效率。SA-MOPM算法采用改進(jìn)的基于K-Prototype聚類算法的徑向基函數(shù)網(wǎng)絡(luò)模型作為代理模型，使徑向基函數(shù)網(wǎng)絡(luò)模型可以應(yīng)用到離散的任務(wù)驅(qū)動(dòng)模式挖掘問題上。在進(jìn)化過程中利用代理模型對(duì)個(gè)體