【摘要】：多目標優(yōu)化問題是一類常見于各種科研以及工程應用中的問題,與經典單目標最優(yōu)化問題不同,多目標問題中涉及到的各個目標相互之間存在著一定的沖突關系。目前在多目標領域存在很多不同類型的算法來解決該問題,而這其中,進化算法由于具有良好并行性、全局搜索以及對任何函數(shù)類可用等特性,在解決多目標優(yōu)化問題上體現(xiàn)出了良好的性能,因此,多目標進化算法成為解決多目標優(yōu)化問題的一個主流方法,并引起學者們的廣泛關注。任務驅動的模式挖掘作為頻繁模式挖掘領域的一個分支,由于其廣闊的應用場景,例如商品組合推薦、網頁打印區(qū)域推薦等等,已經越來越多地引起人們的關注。在這些任務驅動的應用中,推薦給用戶的模式作為一個完整的任務并且該任務有許多子任務組成,因此這些模式稱之為任務驅動模式�？紤]到任務驅動模式中往往是一系列相互關聯(lián)的子任務,因此子任務間的相關性較高,在挖掘過程中就需要考慮挖掘模式的完整性,以免影響用戶的體驗。傳統(tǒng)任務驅動的模式挖掘算法采用對事務數(shù)據(jù)庫(Transaction Database)的字典子集樹進行深度優(yōu)先遍歷搜索的方式,在搜索的過程中利用剪枝的策略提高運行效率。然而基于字典子集樹遍歷的傳統(tǒng)方法難以在實際應用中開展,因為算法需要根據(jù)具體問題的先驗知識設置參數(shù),例如:搜索時最小的支持度閾值min_sup,最小的占有度閾值min_occ以及支持度與占有度之間的一個偏好權值λ等,而且不同的參數(shù)對算法的結果影響很大,另外算法的效率也不盡人意�；谝陨蠁栴},本文對任務驅動模式挖掘問題進行了探索與研究,考慮從多目標優(yōu)化的角度解決任務驅動模式挖掘問題,具體研究工作分為如下兩部分:(1)本文從多目標優(yōu)化的角度出發(fā)解決任務驅動模式挖掘問題,并提出了一種有效的多目標模式挖掘算法。在任務驅動模式挖掘領域中,傳統(tǒng)算法需要用戶設置一些必要的先驗參數(shù)。而這些參數(shù)往往對傳統(tǒng)算法有較大的影響,不同的參數(shù)使得算法的運行時間以及運行效果差別很大。因此,為了獲得較好的性能,傳統(tǒng)算法需要用戶預先設置合適的參數(shù)。但在實際應用中,用戶在缺乏具體問題先驗知識的情況下難以選擇出合適的參數(shù),而且對于不同的問題其合適的參數(shù)也會大不相同。為了尋找合適的參數(shù),用戶需要嘗試不同參數(shù)進行多次實驗以尋找最佳效果,這樣使得算法的運行代價昂貴,效率低下,最終難以在實際應用中展開�；诖�,本文考慮多目標進化算法不需要根據(jù)具體問題設置先驗參數(shù)這一良好特性,將任務驅動模式挖掘問題轉化為一個3目標(支持度,占有度以及覆蓋度)的多目標優(yōu)化問題來處理。在經典多目標進化算法NSGA-II的基礎上,本文提出了一種有效的多目標模式挖掘算法,簡稱MOPM。最后通過在真實數(shù)據(jù)集Smart Print數(shù)據(jù)集、Taobao數(shù)據(jù)集以及合成數(shù)據(jù)集IBM數(shù)據(jù)集上分別進行實驗,結果表明,MOPM算法不需要根據(jù)具體問題設置先驗參數(shù),解決了傳統(tǒng)算法中參數(shù)敏感性的問題,而且MOPM算法在實驗效果以及運行效率上都較傳統(tǒng)算法有一定的優(yōu)勢。因此,從多目標優(yōu)化的角度來解決任務驅動模式挖掘問題是一種行之有效的方式。(2)本文提出了一種基于代理模型的多目標模式挖掘算法。從第一個研究工作中可以發(fā)現(xiàn),用多目標優(yōu)化的視角來解決任務驅動模式挖掘問題能夠有效解決傳統(tǒng)算法遇到的參數(shù)敏感性等挑戰(zhàn),促進了算法在實際中的應用。然而隨著事務數(shù)據(jù)庫規(guī)模的增大,MOPM算法在運行時效率會受到很大的影響。通過分析,發(fā)現(xiàn)由于進化算法在計算個體的3個目標值時都需要對事務數(shù)據(jù)庫的全部數(shù)據(jù)進行遍歷,因此真實評價個體的目標值代價昂貴�；诖�,本文提出了一種基于代理模型的多目標模式挖掘算法,簡稱SA-MOPM,用以提高算法的運行效率。SA-MOPM算法采用改進的基于K-Prototype聚類算法的徑向基函數(shù)網絡模型作為代理模型,使徑向基函數(shù)網絡模型可以應用到離散的任務驅動模式挖掘問題上。在進化過程中利用代理模型對個體進行評估,因此可以大大降低適應度評估的代價。最后,本文在真實數(shù)據(jù)集Smart Print數(shù)據(jù)集、Taobao數(shù)據(jù)集以及合成數(shù)據(jù)集IBM數(shù)據(jù)集上分別進行實驗,結果顯示,在精度降低有限范圍內,SA-MOPM算法的運行效率比MOPM算法有著更大的優(yōu)勢。因此,基于代理模型的多目標模式挖掘算法是解決大規(guī)模數(shù)據(jù)集上任務驅動模式挖掘問題的有效方法。
[Abstract]:......
【學位授予單位】：安徽大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP18

【相似文獻】

相關期刊論文 前10條

1 王宇新;田佳;郭禾;吳樹朋;楊元生;;應用模糊方法的設計模式挖掘策略研究[J];計算機工程與應用;2010年02期

2 陸億紅;王子仁;黃燕;;適合稀少空間特征的同位模式挖掘算法[J];浙江工業(yè)大學學報;2007年04期

3 郭燕萍;辛伯宇;;高選票例外模式挖掘研究與實現(xiàn)[J];電腦開發(fā)與應用;2007年08期

4 徐顯九;楊燕;岳愛萍;;高效的用戶移動模式挖掘方法[J];計算機應用研究;2007年09期

5 李帆;夏士雄;張磊;;基于模糊理論的不確定軌跡模式挖掘[J];微電子學與計算機;2011年08期

6 李中元;邊馥苓;;空間同位模式挖掘研究進展[J];地理空間信息;2013年06期

7 邢東山,沈鈞毅,宋擒豹;用戶瀏覽偏愛模式挖掘算法的研究[J];西安交通大學學報;2002年04期

8 劉洪輝;吳岳芬;;用戶行為模式挖掘問題的研究[J];計算機技術與發(fā)展;2006年05期

9 付曉翠;許盈;車路;;游戲訪問模式挖掘的研究與應用[J];鄭州大學學報(理學版);2007年04期

10 顏一鳴;郭鑫;李仁發(fā);;一種非確定樹模式挖掘算法[J];計算機工程與應用;2011年15期

相關會議論文 前10條

1 王肅;杜軍平;高田;;基于本體與知識背景的模式挖掘框架研究[A];2009年中國智能自動化會議論文集（第二分冊）[C];2009年

2 繆裕青;尹東;;分布式存儲結構的頻繁閉合模式挖掘并行算法[A];2007年全國開放式分布與并行計算機學術會議論文集(下冊)[C];2007年

3 王淼;尚學群;謝華博;李戰(zhàn)懷;;行常量差異共表達基因模式挖掘算法研究[A];第29屆中國數(shù)據(jù)庫學術會議論文集（B輯）（NDBC2012）[C];2012年

4 劉玉葆;蔡嘉榮;印鑒;黃志蘭;;基于最大訪問模式挖掘的數(shù)據(jù)庫異常行為檢測[A];第二十三屆中國數(shù)據(jù)庫學術會議論文集（研究報告篇）[C];2006年

5 陸葉;王麗珍;陳紅梅;趙麗紅;;基于可能世界的不確定空間co-location模式挖掘研究[A];NDBC2010第27屆中國數(shù)據(jù)庫學術會議論文集(B輯)[C];2010年

6 王麗珍;陸葉;陳紅梅;肖清;;基于前綴樹結構的空間co-location模式挖掘算法研究[A];NDBC2010第27屆中國數(shù)據(jù)庫學術會議論文集(B輯)[C];2010年

7 胡偉成;曹三省;李丹;;一種基于QPop增量時域分割升維的媒體內容應用模式挖掘改進算法[A];第二十二屆中國數(shù)據(jù)庫學術會議論文集（技術報告篇）[C];2005年

8 薛丹;李德敏;裴仁林;;移動計算中基于PrefixSpan算法的用戶移動模式挖掘[A];第二十一屆中國數(shù)據(jù)庫學術會議論文集（技術報告篇）[C];2004年

9 宋國杰;馬帥;唐世渭;楊冬青;;基于模式挖掘的交通預測模型[A];第十九屆全國數(shù)據(jù)庫學術會議論文集（技術報告篇）[C];2002年

10 夏慶;馬元元;孫志揮;;路徑遍歷模式挖掘方法的改進[A];第十六屆全國數(shù)據(jù)庫學術會議論文集[C];1999年

相關重要報紙文章 前1條

1 辛苑薇;誰將分享“大數(shù)據(jù)”的智慧盛宴？[N];21世紀經濟報道;2012年

相關博士學位論文 前7條

1 Shafqat Ali Shad;移動用戶軌跡與行為模式挖掘方法研究[D];中國科學技術大學;2013年

2 錢烽;同位模式挖掘研究[D];浙江大學;2012年

3 劉勇;圖模式挖掘技術的研究[D];哈爾濱工業(yè)大學;2010年

4 覃桂敏;復雜網絡模式挖掘算法研究[D];西安電子科技大學;2012年

5 王樂;數(shù)據(jù)流模式挖掘算法及應用研究[D];大連理工大學;2013年

6 林耀進;多源環(huán)境中數(shù)據(jù)預處理與模式挖掘的研究[D];合肥工業(yè)大學;2014年

7 曾海泉;時間序列挖掘與相似性查找技術研究[D];復旦大學;2003年

相關碩士學位論文 前10條

1 楊陽;云計算環(huán)境下時空軌跡伴隨模式挖掘研究[D];南京師范大學;2015年

2 李海;基于用戶軌跡數(shù)據(jù)的周期活動模式挖掘[D];江蘇科技大學;2015年

3 周青峰;云計算環(huán)境下的模式挖掘算法研究[D];浙江工商大學;2015年

4 陳瑞;基于分治子圖和極大有序團樹的co-location模式挖掘研究[D];云南大學;2015年

5 尹騰騰;軟件執(zhí)行軌跡中行為模式挖掘算法研究[D];燕山大學;2015年

6 陳明福;縮小候選集的Top-k高效模式挖掘算法研究[D];重慶大學;2015年

7 張子瀚;面向大數(shù)據(jù)的高效用模式挖掘方法研究[D];北方工業(yè)大學;2016年

8 張剛領;一種基于團的閉頻繁Co-location模式挖掘方法[D];云南大學;2016年

9 江萬國;基于領域驅動的空間高效用Co-location模式挖掘[D];云南大學;2016年

10 吳錫宇;基于約束的城市co-location模式挖掘[D];云南大學;2016年

，

本文編號：2310846