基于矩陣二進(jìn)制編碼遺傳算法的頻繁項(xiàng)集挖掘

杜嘉偉 余粟

摘?要：提出一種基于矩陣二進(jìn)制編碼的改進(jìn)遺傳算法MGA（Matrix Genetic Algorithm ），應(yīng)用于挖掘關(guān)聯(lián)規(guī)則中的頻繁項(xiàng)集。通過對初始種群的編碼以及降維保證了合理的初始適應(yīng)度，并對遺傳算法中交叉算子和變異算子生成新個體與篩選的過程進(jìn)行優(yōu)化，使算法有優(yōu)良的全局和局部搜索能力。實(shí)驗(yàn)結(jié)果顯示，MGA算法的整體挖掘效率與質(zhì)量良好。

關(guān)鍵詞： 遺傳算法;關(guān)聯(lián)規(guī)則;頻繁項(xiàng)集

文章編號： 2095-2163（2021）01-0143-05 中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：A

【Abstract】This paper proposes an improved genetic algorithm MGA （Matrix Genetic Algorithm） based on matrix binary coding， which is applied to mining frequent itemsets in association rules. By encoding the initial population and reducing the dimensionality， a reasonable initial fitness is ensured， and then the process of generating new individuals and screening by the crossover operator and mutation operator in the genetic algorithm is optimized， so that the algorithm has excellent global and local search capabilities. Experimental results show that the overall mining efficiency and quality of the MGA algorithm are good.

【Key words】Genetic Algorithm; association rules; frequent itemsets

0 引?言

頻繁項(xiàng)集是那些出現(xiàn)在二進(jìn)制或者定量數(shù)據(jù)集中的項(xiàng)目集，其出現(xiàn)頻率超過指定的最小支持度，這是關(guān)聯(lián)規(guī)則挖掘的基礎(chǔ)和重要的部分[1]。由于多數(shù)挖掘定量頻繁項(xiàng)目集的方法都是先將數(shù)據(jù)集轉(zhuǎn)換成二進(jìn)制的表現(xiàn)方法[2]，本文擬重點(diǎn)關(guān)注二進(jìn)制頻繁項(xiàng)目集的挖掘。

為了挖掘到最大頻繁項(xiàng)目集，通常會選擇使用精確算法。其中使用率較高的Apriori算法[3]和FPGrowth算法[4]能夠找到目標(biāo)事務(wù)數(shù)據(jù)集中最大頻繁項(xiàng)集，但是隨著挖掘問題變得越來越復(fù)雜，也帶來了一些缺點(diǎn)，如大量的時間和存儲的成本。因此，更多的研究者開始運(yùn)用遺傳算法等啟發(fā)式算法，雖然無法如精確算法一樣得到問題的全局最優(yōu)解，但卻能在基于時間和空間的條件約束下求得問題的近似解，這也將具有更大的現(xiàn)實(shí)意義。

將傳統(tǒng)遺傳算法運(yùn)用到長頻繁項(xiàng)集的挖掘過程，但是并未將算法應(yīng)用到大體量的數(shù)據(jù)集[5]。侯燕等人[6]研究優(yōu)化了遺傳算法對頻繁項(xiàng)集的全局搜索能力，來挖掘關(guān)聯(lián)規(guī)則并分析其性能，有著良好的挖掘效率，但對于頻繁項(xiàng)集的提取率有限。在應(yīng)用方面，已將遺傳算法應(yīng)用于挖掘醫(yī)療信息，并常見于健康醫(yī)療推薦中[7]。有關(guān)聯(lián)規(guī)則研究針對弱關(guān)聯(lián)分析，其中即使用遺傳算法優(yōu)化了數(shù)據(jù)挖掘的過程[8]。

本文提出一種基于矩陣二進(jìn)制編碼的遺傳算法MGA（Matrix Genetic Algorithm ）來從事務(wù)數(shù)據(jù)集中挖掘出頻繁項(xiàng)集。在MGA算法中共執(zhí)行k步挖掘過程，交叉算子對前一次挖掘得到的頻繁k-1項(xiàng)集進(jìn)行交叉計(jì)算生成長度為k的候選項(xiàng)集[9]，變異算子則在候選項(xiàng)集中進(jìn)行剪枝篩選挖掘出頻繁k項(xiàng)集，其中在交叉變異計(jì)算過程中建立了一種編碼模式將剪枝、判別候選項(xiàng)集是否為頻繁項(xiàng)集、挖掘頻繁項(xiàng)集三個部分有機(jī)地融合在一起，還提出一種基于降維的方法來提高挖掘性能。

1 基本概念

1.1 頻繁項(xiàng)集

采用向量和矩陣的概念建立頻繁項(xiàng)集（Frequent itemsets）的挖掘模型[10]。令I(lǐng)={item1，item2...， itemn }是n個數(shù)據(jù)項(xiàng)的集合，且itemj（1≤j≤n）稱為項(xiàng)，D= {t1，t2，…，tm}是m個事務(wù)組成的數(shù)據(jù)集，ti（1≤i≤m）表示為一條事務(wù)，并且ti是I的子集。這里涉及的重要概念可做闡釋分述如下。

（1）項(xiàng)集（Itemset）：就是項(xiàng)的集合。包含k個項(xiàng)的項(xiàng)集稱為k項(xiàng)集。當(dāng)一個k項(xiàng)集計(jì)算所得的支持度滿足設(shè)定的支持度閾值，就將該項(xiàng)集定義為頻繁k項(xiàng)集。

（2）支持度（Support）：描述了多個項(xiàng)集在所有事務(wù)中同時出現(xiàn)的概率。事務(wù)數(shù)據(jù)集中的支持度用sup（x）來表示，支持度閾值用min_sup來表示，在挖掘頻繁項(xiàng)集的過程中，min_sup能夠篩選并枚舉出所有重要的項(xiàng)集?；谝陨厦枋隹赏频枚x如下[1]：

定義1：給定min_sup，若sup（X）>min_sup，那么項(xiàng)目集X是頻繁項(xiàng)目集。

定義2：存在項(xiàng)目集X1、X2，而且X1X2，則sup（X1）≥sup（X2）

1.2 遺傳算法

遺傳算法（Genetic Algorithm，GA）是一種隨機(jī)搜索方法，算法通過模擬生物進(jìn)化的過程，由染色體的交叉和變異生成新個體，以適者生存為目的，淘汰無法適應(yīng)環(huán)境的個體，逐步找到最優(yōu)解。與傳統(tǒng)搜索算法不同，遺傳算法的初始種群是隨機(jī)挑選的，其中個體再根據(jù)適應(yīng)度函數(shù)進(jìn)行標(biāo)記篩選，通過交叉和變異計(jì)算生成后代種群，如此循環(huán)找到最優(yōu)個體即為最優(yōu)解[11]。對研究中主要用到的2個概念擬做簡述如下。

（1）交叉算子：對2個個體按定義的規(guī)則相互交換其部分基因，產(chǎn)生2個繼承到父代有效模式的新個體。為了得到有著多樣性特性的候選項(xiàng)集，采用多點(diǎn)交叉的方式，即在2個不同的基因中的不同位置進(jìn)行交換。

（2）變異算子：對交叉計(jì)算產(chǎn)生的新個體上的基因按定義的規(guī)則進(jìn)行變異，形成新個體。變異計(jì)算的過程增加了后代種群的多樣性，能夠提高局部搜索能力。

2 MGA算法

2.1 編碼搜索空間、項(xiàng)目集、事務(wù)

給定具有m個項(xiàng)目n條事務(wù)的數(shù)據(jù)集D，將MGA的搜索空間視為m x n的矩陣M，文中用矩陣二進(jìn)制（bit string）來編碼，即對一事務(wù)T，若t∈T，則令碼串的第i位為1，否則為0[5]。比如數(shù)據(jù)集I是由5個項(xiàng)目集所構(gòu)成，那么{10010}則表示對應(yīng)的事務(wù){(diào)t1，t4}，同時也表示一個二項(xiàng)集。

給定事務(wù)數(shù)據(jù)集D映射關(guān)系f：D→M，即f（D）=（aij）nxm=M，并且，

其中，Ti為D中事務(wù)的個數(shù)，m為I中數(shù)據(jù)項(xiàng)的個數(shù)[12]。

根據(jù)公式（1），通過一次數(shù)據(jù)庫的掃描，事務(wù)數(shù)據(jù)集D能映射為矩陣M。項(xiàng)集支持度可以通過二進(jìn)制編碼后的項(xiàng)集與矩陣M內(nèi)積所得，項(xiàng)集支持度計(jì)算方法為：存在矩陣二進(jìn)制編碼的事務(wù)集合M，即：

其中，Dl為D中事務(wù)的總個數(shù)，L為I中數(shù)據(jù)項(xiàng)的總個數(shù)。

遍歷向量C中元素，當(dāng)向量中有n個元素等于k，則sup（B）=k。當(dāng)此候選項(xiàng)集的支持度滿足支持度閾值，則此候選項(xiàng)集為頻繁k項(xiàng)集。

2.2 初始種群及其降維

初始種群很大程度上影響著挖掘效率和質(zhì)量。在MGA算法中，首先由遺傳算法隨機(jī)創(chuàng)建初始種群，然后根據(jù)以下推論通過降維來優(yōu)化其中的一部分。

給定一個項(xiàng)集X，存在X1，X2是X的真子集，即X1，X2X，則可得：

同時，根據(jù)先驗(yàn)啟發(fā)式原理：

從中可以推論出：

假設(shè)X-X1與X-X2的支持度為最大，則當(dāng)sup（X1）>sup（X2），那么sup（X-X1）≥sup（X-X2）即項(xiàng)集X中去除支持度較低的X2更有可能是頻繁項(xiàng)集。由此假設(shè)可得，在處理初始種群時，對矩陣M每列求內(nèi)積得出事務(wù)數(shù)據(jù)集中每個項(xiàng)集的支持度，并根據(jù)min_sup篩選中不滿足要求的項(xiàng)集X，最終得到頻繁一項(xiàng)集。

2.3 交叉和變異

根據(jù)先驗(yàn)啟發(fā)式與剪枝原理，在挖掘頻繁k項(xiàng)集的過程中，經(jīng)過頻繁k-1項(xiàng)集交叉變異計(jì)算生成的2個長度為k的候選項(xiàng)集，當(dāng)此集合去除了包含前k-1步已判斷為不頻繁項(xiàng)的項(xiàng)集，那么集合中剩余項(xiàng)集更可能為頻繁k項(xiàng)集。

基于以上的推論，MGA算法對進(jìn)行交叉計(jì)算的項(xiàng)集有所約束，要求進(jìn)行運(yùn)算的2個以二進(jìn)制編碼的項(xiàng)集要同時為n項(xiàng)集，且這2個項(xiàng)集要進(jìn)行交叉計(jì)算的元素位置需為01對位，例如要進(jìn)行交叉計(jì)算的其中一個項(xiàng)集為{11000}，則要求進(jìn)行交叉計(jì)算的另外一個項(xiàng)集為2項(xiàng)集，且項(xiàng)集元素需要為01對位，即另一項(xiàng)集為{00110}或是{00011}。

變異算子則是作用于交叉算子計(jì)算后得到的候選項(xiàng)集，首先判別當(dāng)前項(xiàng)集是否包含非頻繁k-1項(xiàng)集，若是包含則對其剪枝去除，若不包含則根據(jù)公式（2），判斷當(dāng)前候選項(xiàng)集是否為頻繁項(xiàng)集，若為非頻繁項(xiàng)集則進(jìn)行變異計(jì)算，將k項(xiàng)集元素中的01元素翻轉(zhuǎn)生成一個新的k項(xiàng)集之后再進(jìn)行計(jì)算判別，不斷循環(huán)直到得出一個頻繁項(xiàng)集，此過程將剪枝、判別候選項(xiàng)集是否為頻繁項(xiàng)集、挖掘頻繁項(xiàng)集三個過程有機(jī)地融合在一起，避免了不斷掃描數(shù)據(jù)庫的過程，減少了運(yùn)行時間和內(nèi)存消耗。

2.4 適應(yīng)度函數(shù)和候選結(jié)果

適應(yīng)度函數(shù)用于評估個體的質(zhì)量。在MGA中，個體的適應(yīng)度等于該個體的支持度，即：

x但是，為了避免候選項(xiàng)集中存在相同個體，調(diào)整適應(yīng)度函數(shù)為：

式中，數(shù)據(jù)集H是前一次挖掘得到的候選項(xiàng)集。

2.5 MGA算法的偽代碼

算法1 基于矩陣二進(jìn)制編碼的改進(jìn)遺傳算法

3 實(shí)驗(yàn)結(jié)果與分析

在本節(jié)中，使用了某零售商店數(shù)據(jù)集來評估

MGA算法，其中實(shí)驗(yàn)數(shù)據(jù)包含有65 000多條商品交易信息和2 241個交易項(xiàng)目。實(shí)驗(yàn)環(huán)境為64位的Win10的系統(tǒng)，i7-9700KF，CPU 3.6 GHz的計(jì)算機(jī)。

以下從不同支持度閾值的條件下，從挖掘頻繁項(xiàng)集的平均時間、內(nèi)存消耗量、提取率三個方面的性能指標(biāo)來評價MGA和Apriori這兩個算法并進(jìn)行分析。

圖1和圖2分別表示了在不同的min_sup條件下，MGA和Apriori算法挖掘相同電商數(shù)據(jù)集中的頻繁項(xiàng)集的運(yùn)行時間和內(nèi)存消耗量。由實(shí)驗(yàn)結(jié)果可知，隨著支持度的提高，2個算法的運(yùn)行時間和內(nèi)存消耗量都處于下降的趨勢，這是因?yàn)镸GA在運(yùn)行過程中避免了多次掃描數(shù)據(jù)庫，只需要在挖掘頻繁一項(xiàng)集時掃描一次數(shù)據(jù)庫并將其編碼為矩陣表示存入內(nèi)存中，隨后對初始種群進(jìn)行了降維的操作，這減少了冗余候選項(xiàng)集的產(chǎn)生。而在挖掘頻繁項(xiàng)集時，只需要通過公式（2）進(jìn)行矩陣計(jì)算判別當(dāng)前項(xiàng)目集是否為頻繁項(xiàng)集，這也減少了挖掘搜索的時間。

圖3表示了在不同的支持度閾值的條件下，MGA算法、Apriori算法的提取率，圖4表示了迭代次數(shù)和提取率的關(guān)系。由實(shí)驗(yàn)結(jié)果可知，Apriori算法能夠精確地挖掘出所有的最大頻繁項(xiàng)集，提取率保持為100%。MGA算法隨著支持度的升高，提取率越高，但是作為啟發(fā)式近似算法在有限的迭代下不能挖掘所有的頻繁項(xiàng)集。由圖4分析可知，MGA算法的迭代次數(shù)越多，頻繁項(xiàng)集的提取率越高。

4 結(jié)束語

本文提出一種基于二進(jìn)制編碼的遺傳算法MGA從數(shù)據(jù)集中挖掘頻繁項(xiàng)集。對于繁雜的數(shù)據(jù)集，改進(jìn)的遺傳算法MGA通過對事務(wù)集進(jìn)行矩陣二進(jìn)制編碼并通過矩陣計(jì)算挖掘頻繁項(xiàng)集，避免了多次掃描數(shù)據(jù)庫，而對初始種群的降維也降低了矩陣維度，從而減少了挖掘的運(yùn)行時間和內(nèi)存消耗。MGA繼承了遺傳算法優(yōu)良的全局搜索能力，通過優(yōu)化算法中交叉和變異生成新個體的過程，改進(jìn)了算法的局部搜索能力，進(jìn)而提高了頻繁項(xiàng)集整體挖掘效率與質(zhì)量。接下來要考慮在高維數(shù)據(jù)集的情況下，從事在算法過程中動態(tài)地削減數(shù)據(jù)集的維度和頻繁項(xiàng)集的搜索空間，以達(dá)到進(jìn)一步優(yōu)化整體挖掘質(zhì)量與效率的研究。

參考文獻(xiàn)

[1]HAN Jiawei， KAMBER M P J. Data mining： Concepts and techniques [M]. Third Edition. USA：Elsevier， 2011.

[2]ALATAS B， AKIN E. Rough particle swarm optimization and its applications in data mining [J]. Soft Computation， 2008， 12（12）： 1205-1218.

[3]GRAWAL R， SRIKANT R.Fast algorithms for mining association rules[C]//Proceedings of the 20th VLDB International Conference on Very high Database.San Francisco，CA：Morgan Kaufmann，1994：487-499.

[4]HAN Jiawei，PEI Jian，YIN Yiwen.Mining frequent patterns without candidate generation[C]//Proceedings of the 2000 ACM-SIGMOD International Conference on Management of Data.Dallas， Texas， USA：ACM Press，2000：l-12.

[5]王偉，高亮，吳濤. 基于遺傳算法的長頻繁項(xiàng)集挖掘方法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2008，18（4）：19-21.

[6]侯燕，劉辛.基于主從架構(gòu)和GA的模糊關(guān)聯(lián)規(guī)則挖掘算法[J].控制工程，2017，24（2）：276-282.

[7]孫明瑞，臧天儀. 面向健康醫(yī)療的分類關(guān)聯(lián)規(guī)則挖掘研究[J]. 智能計(jì)算機(jī)與應(yīng)用，2020，10（2）：1-6，11.

[8]李忠，安建琴，劉海軍，等. 關(guān)聯(lián)挖掘算法及發(fā)展趨勢[J]. 智能計(jì)算機(jī)與應(yīng)用，2017，7（5）：22-25.

[9]胡濤.基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法[J].電子技術(shù)與軟件工程，2018，2（2）：186.

[10]張軍.基于遺傳算法的頻繁項(xiàng)挖掘算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（12）：161-165.

[11]閻平凡，張長水.人工神經(jīng)網(wǎng)絡(luò)與模擬進(jìn)化計(jì)算[M].北京：清華大學(xué)出版社，2001.

[12]李超，余昭平.基于矩陣的Apriori算法改進(jìn)[J].計(jì)算機(jī)工程，2006，32（23）：68-69.