基于多目標進化算法的任務驅(qū)動模式挖掘研究.pdf

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

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

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

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

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

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

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