模式挖掘是數(shù)據(jù)挖掘中最重要的領(lǐng)域,高效用項集挖掘是模式挖掘中的研究熱點之一。由于演化計算能夠避免高效用項集搜索空間組合爆炸式增長,近幾年基于演化計算的高效用項集挖掘算法越來越受到關(guān)注。學(xué)者們提出了基于遺傳算法（Genetic Algorithm,GA）、粒子群算法（Particle Swarm Optimization,PSO）、蝙蝠算法（Bat Algorithm,BA）等演化計算的高效用項集挖掘算法。這些方法通常通過迭代的改變編碼向量產(chǎn)生新的候選項集。與GA、PSO、BA算法不同,我們提出了一個基于蟻群算法的高效用項集挖掘算法（HUIM-ACO）,這種算法構(gòu)造性地產(chǎn)生候選項集。在HUIM-ACO算法中,我們使用搜索路徑來表達候選項集。最初我們將每個搜索路徑按照概率進行初始化,每一步增加一個項目。同時我們提出了信息素矩陣,用于存儲兩個不同項目的信息素值,允許局部更新和全局更新,而且設(shè)計的螞蟻路徑能夠有效計算高效用項集。與基于GA和PSO的高效用項集挖掘算法相比,HUIM-ACO算法能夠在更短的時間內(nèi)挖掘出更多的高效用項集。為了進一步提升HUIM-ACO算法的性能,在HUIM-ACO算... 

【文章來源】：北方工業(yè)大學(xué)北京市

【文章頁數(shù)】：63 頁

【學(xué)位級別】：碩士

【部分圖文】：

螞蟻系統(tǒng)流程圖

第二章問題描述10每個節(jié)點都表示特定項集，這個項集可以被螞蟻評估是否是高效用項集。圖2-2是遞歸構(gòu)建的螞蟻路徑圖。圖2-2螞蟻路徑圖2.3.2偽隨機比例規(guī)則HUIM-ACS算法使用當(dāng)前節(jié)點和候選節(jié)點組成項集的TWU值作為啟發(fā)式函數(shù)，只計算螞蟻第一次到達相關(guān)節(jié)點的TWU值。在偽隨機比例規(guī)則中當(dāng)前節(jié)點和候選節(jié)點組成項集的TWU值有以下三種情況。（1）成對的項目沒有任何TWU值信息。（2）處理包含所有成對項目的TWU值。（3）一些沒有處理的成對項目的TWU值。2.3.3全局更新規(guī)則HUIM-ACS算法簡化了傳統(tǒng)的全局更新公式，在每次迭代中只是使用項集效用值加強信息素濃度并且忽略揮發(fā)參數(shù)。且在每次迭代中不總是加強信息濃度，這樣避免了螞蟻路徑圖中一些區(qū)域路徑上信息素濃度過大。這樣對挖掘高效用項集是有利的，因為需要挖掘出更多的解而不是單一的最優(yōu)解。2.4本章小結(jié)高效用模式挖掘主要是從給定的數(shù)據(jù)集中挖掘出所有大于指定閾值的項集。AC算法是最早提出的螞蟻種群優(yōu)化算法，主要流程是初始化螞蟻種群，螞蟻移動完成一次循環(huán)后在經(jīng)過的路徑上釋放信息素，滿足終止條件后算法結(jié)束。ACS

第三章基于ACO的高效用模式挖掘算法173.3.2運行時間首先，我們闡述提出的HUIM-ACO算法性能。圖3-1展示了每個算法在4個數(shù)據(jù)上運行時間的對比。我們通過改變每個數(shù)據(jù)集的最小效用閾值來測量各個算法在4個數(shù)據(jù)集上的運行時間。圖3-14個數(shù)據(jù)集的運行時間就Accident數(shù)據(jù)集而言，HUIM-BPSO運行了4天后都沒有返回任何結(jié)果，因此在圖3-1中沒有標(biāo)記出這個算法的任何結(jié)果，我們從圖3-1中可以看出提出的HUIM-ACO算法比HUIM-BPSO算法和Bio-HUIF-GA算法快出一個量級。就Chess和Connect數(shù)據(jù)集，HUIM-ACO比Bio-HUIF-PSO快了一個數(shù)量級。值得注意的是HUIM-ACO算法運行時間總是很穩(wěn)定，并且?guī)缀鯖]有受最小效用閾值改變的影響。3.3.3挖掘結(jié)果數(shù)量因為演化HUIM算法無法確保在一定的循環(huán)次數(shù)后所有項集的挖掘，我們比對了各個演化算法挖掘的HUIs數(shù)量。與3.4.2小結(jié)同理，我們沒有繪制出在Accident數(shù)據(jù)集中HUIM-BPSO算法的結(jié)果。

【參考文獻】：
期刊論文
[1]基于多效用閾值的分布式高效用序列模式挖掘[J]. 曾毅,張福泉.  計算機工程與設(shè)計. 2020(02)
[2]基于投影二維表的最大頻繁模式挖掘算法[J]. 王利軍.  西昌學(xué)院學(xué)報(自然科學(xué)版). 2019(04)
[3]基于Spark平臺的FP-Growth算法優(yōu)化與實現(xiàn)[J]. 黃婕.  湖南工業(yè)大學(xué)學(xué)報. 2020(01)
[4]一種快速挖掘top-k高效用模式的算法[J]. 吳倩,王林平,羅相洲,崔建群,王海.  計算機應(yīng)用研究. 2017(11)
[5]基于MapReduce的top-k高效用模式挖掘算法[J]. 吳倩,王林平,羅相洲,崔建群,王海.  計算機應(yīng)用研究. 2017(10)
[6]基于相似度的自適應(yīng)異類多種群蟻群算法[J]. 張鵬,薛宏全,原欣偉.  計算機工程與應(yīng)用. 2014(19)
[7]并行蟻群算法中的自適應(yīng)交流策略(英文)[J]. 陳崚,章春芳.  軟件學(xué)報. 2007(03)
[8]基于變異和動態(tài)信息素更新的蟻群優(yōu)化算法[J]. 朱慶保,楊志軍.  軟件學(xué)報. 2004(02)
[9]基于分布均勻度的自適應(yīng)蟻群算法[J]. 陳崚,沈潔,秦玲,陳宏建.  軟件學(xué)報. 2003(08)

碩士論文
[1]高效用模式挖掘算法研究及應(yīng)用[D]. 羅相洲.華中師范大學(xué) 2017
[2]基于高效用模式挖掘的推薦方法研究[D]. 吉紅蕾.北方工業(yè)大學(xué) 2014



本文編號：3047938