[發(fā)明專利]基于改進(jìn)蟻獅優(yōu)化算法和頻繁模式增長的關(guān)聯(lián)規(guī)則提取方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201911049403.4
• 申請(qǐng)日: 2019-10-31
• 公開（公告）號(hào): CN111125182B
• 公開（公告）日: 2023-04-18
• 發(fā)明（設(shè)計(jì)）人: 葉志偉;董達(dá)偉;曹羽
• 申請(qǐng)（專利權(quán)）人: 湖北工業(yè)大學(xué)
• 主分類號(hào): G06F16/2458
• 分類號(hào): G06F16/2458;G06N3/006
• 代理公司: 武漢科皓知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 42222
• 代理人: 魏波

本發(fā)明公開了一種基于改進(jìn)蟻獅優(yōu)化算法和頻繁模式增長的關(guān)聯(lián)規(guī)則提取方法，將頻繁模式樹上路徑的遍歷轉(zhuǎn)化為借助于蟻獅優(yōu)化算法結(jié)合項(xiàng)頭表在頻繁模式樹上路徑的搜索，對(duì)搜索到的路徑即關(guān)聯(lián)規(guī)則利用適應(yīng)度函數(shù)進(jìn)行評(píng)估并保存，挖掘出最佳關(guān)聯(lián)規(guī)則。本發(fā)明不同于頻繁模式增長算法的完全遍歷，而是借助于蟻獅優(yōu)化算法從啟發(fā)式角度進(jìn)行智能搜索，有效縮短了關(guān)聯(lián)規(guī)則挖掘所耗時(shí)間，相比于傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘算法，該發(fā)明更能適應(yīng)海量數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘。

技術(shù)領(lǐng)域

本發(fā)明屬于數(shù)據(jù)挖掘技術(shù)領(lǐng)域，涉及一種關(guān)聯(lián)規(guī)則提取方法，具體涉及一種基于改進(jìn)蟻獅優(yōu)化算法和頻繁模式增長的關(guān)聯(lián)規(guī)則挖掘方法。

背景技術(shù)

大數(shù)據(jù)時(shí)代，我們善于從大量的數(shù)據(jù)中提取出有用的信息，數(shù)據(jù)挖掘近年來成為一個(gè)熱門領(lǐng)域，已經(jīng)討論了許多研究和應(yīng)用以更有效地應(yīng)用相關(guān)技術(shù)。數(shù)據(jù)挖掘最重要的應(yīng)用之一是發(fā)現(xiàn)關(guān)聯(lián)規(guī)則，由R.Agrawal，T。Imielinski和A.Swami引入。關(guān)聯(lián)規(guī)則提取的主要目標(biāo)是發(fā)現(xiàn)數(shù)據(jù)項(xiàng)集之間內(nèi)涵的關(guān)聯(lián)或依賴關(guān)系，即從大量積累的數(shù)據(jù)中找出隱藏的數(shù)據(jù)模式或者知識(shí)，滿足給定的最小支持和置信度的相關(guān)項(xiàng)。為了解決這個(gè)問題，提出了兩種著名的算法：Apriori算法和FP-Growth算法。然而，隨著信息技術(shù)的發(fā)展，即使FPGrowth算法只掃描數(shù)據(jù)集兩次，它仍然無法有效地處理大數(shù)據(jù)集。數(shù)據(jù)挖掘中最為關(guān)鍵的是挖掘效率，但是Apriori算法在大數(shù)據(jù)量上挖掘十分耗時(shí)，需要多次掃描數(shù)據(jù)庫。因此，幾乎所有的關(guān)聯(lián)分析挖掘都集中在算法改進(jìn)上，這對(duì)關(guān)聯(lián)分析挖掘具有重大的推動(dòng)作用。人們針對(duì)Apriori算法存在的問題，提出了許多改進(jìn)的算法。比如：采用Hash技術(shù)來提高候選集生成效率的DHP(Direct?Hashing?and?Pruning)算法，還有動(dòng)態(tài)項(xiàng)集計(jì)數(shù)算法DIC(DynamicItemset?Counting)，和采用分治思想來解決內(nèi)存不夠用的分塊挖掘算法(Partition)等。

如今自然啟發(fā)的元啟發(fā)式算法在這個(gè)領(lǐng)域也漸漸的發(fā)揮自己的作用，作為一種隨機(jī)算法，它被證明是解決這一問題的有效方法。現(xiàn)在已經(jīng)提出并應(yīng)用了許多元啟發(fā)式算法來處理關(guān)聯(lián)規(guī)則挖掘問題，包括粒子群優(yōu)化算法，差分進(jìn)化算法，遺傳算法等。然而，這些算法仍然面臨局部優(yōu)化問題，嚴(yán)重制約了搜索性能。蟻獅優(yōu)化算法是一種新穎的自然啟發(fā)算法，它模仿自然界中的蟻獅的狩獵機(jī)制。憑借在改進(jìn)探索，局部最優(yōu)避免，開發(fā)和收斂方面的競爭結(jié)果，該算法已被用于許多領(lǐng)域，如特征選擇和工程問題。

發(fā)明內(nèi)容

本發(fā)明在蟻獅優(yōu)化算法的基礎(chǔ)上，提出了一種新的方法來更有效地提取關(guān)聯(lián)規(guī)則，能夠快速地對(duì)給定數(shù)據(jù)集進(jìn)行關(guān)聯(lián)規(guī)則挖掘。實(shí)驗(yàn)結(jié)果表明該方法優(yōu)于其他經(jīng)典算法。

本發(fā)明所采用的技術(shù)方案是：一種基于改進(jìn)蟻獅優(yōu)化算法和頻繁模式增長的關(guān)聯(lián)規(guī)則提取方法，其特征在于，包括以下步驟：

步驟1：輸入事務(wù)數(shù)據(jù)集，從文件中讀取出事務(wù)數(shù)據(jù)，每項(xiàng)事務(wù)按字符串的形式逐條保存于事務(wù)列表結(jié)構(gòu)中；

步驟2：針對(duì)讀取到的事務(wù)數(shù)據(jù)集，利用頻繁模式增長算法構(gòu)建該事務(wù)數(shù)據(jù)集的頻繁模式樹；

步驟3：利用已構(gòu)建好的頻繁模式樹創(chuàng)建對(duì)應(yīng)的頭表；

步驟4：遍歷已創(chuàng)建好的頭表，對(duì)頭表中的每一項(xiàng)，在頻繁模式樹中搜索利用蟻獅算法生成的該項(xiàng)條件模式基子集，計(jì)算該項(xiàng)條件模式基子集與該項(xiàng)構(gòu)成的關(guān)聯(lián)規(guī)則的適應(yīng)度；

其中，遍歷頻繁模式樹找到該項(xiàng)的條件模式基，然后以二進(jìn)制隨機(jī)表示條件模式基中的每一項(xiàng)是否被選中，選中則為1，未選中則為0；將條件模式基中所有被選中的項(xiàng)組合在一起作為當(dāng)前關(guān)聯(lián)規(guī)則的左部，即該項(xiàng)條件模式基子集；

其中，適應(yīng)度評(píng)價(jià)函數(shù)為：

其中，support和confidence分別為當(dāng)前選定關(guān)聯(lián)規(guī)則計(jì)算出的支持度和置信度，minsup和minconf為預(yù)設(shè)的最小支持度和最小置信度；