杜嘉偉 余粟

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

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

文章編號(hào)： 2095-2163（2021）01-0143-05 中圖分類號(hào)：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ò)指定的最小支持度，這是關(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)目集，通常會(huì)選擇使用精確算法。其中使用率較高的Apriori算法[3]和FPGrowth算法[4]能夠找到目標(biāo)事務(wù)數(shù)據(jù)集中最大頻繁項(xiàng)集，但是隨著挖掘問(wèn)題變得越來(lái)越復(fù)雜，也帶來(lái)了一些缺點(diǎn)，如大量的時(shí)間和存儲(chǔ)的成本。因此，更多的研究者開始運(yùn)用遺傳算法等啟發(fā)式算法，雖然無(wú)法如精確算法一樣得到問(wèn)題的全局最優(yōu)解，但卻能在基于時(shí)間和空間的條件約束下求得問(wèn)題的近似解，這也將具有更大的現(xiàn)實(shí)意義。

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

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

1 基本概念

1.1 頻繁項(xiàng)集

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

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

（2）支持度（Support）：描述了多個(gè)項(xiàng)集在所有事務(wù)中同時(shí)出現(xiàn)的概率。事務(wù)數(shù)據(jù)集中的支持度用sup（x）來(lái)表示，支持度閾值用min_sup來(lái)表示，在挖掘頻繁項(xiàng)集的過(guò)程中，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ī)搜索方法，算法通過(guò)模擬生物進(jìn)化的過(guò)程，由染色體的交叉和變異生成新個(gè)體，以適者生存為目的，淘汰無(wú)法適應(yīng)環(huán)境的個(gè)體，逐步找到最優(yōu)解。與傳統(tǒng)搜索算法不同，遺傳算法的初始種群是隨機(jī)挑選的，其中個(gè)體再根據(jù)適應(yīng)度函數(shù)進(jìn)行標(biāo)記篩選，通過(guò)交叉和變異計(jì)算生成后代種群，如此循環(huán)找到最優(yōu)個(gè)體即為最優(yōu)解[11]。對(duì)研究中主要用到的2個(gè)概念擬做簡(jiǎn)述如下。

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

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

2 MGA算法

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

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

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

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

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

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

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

2.2 初始種群及其降維

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

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

同時(shí)，根據(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è)可得，在處理初始種群時(shí)，對(duì)矩陣M每列求內(nèi)積得出事務(wù)數(shù)據(jù)集中每個(gè)項(xiàng)集的支持度，并根據(jù)min_sup篩選中不滿足要求的項(xiàng)集X，最終得到頻繁一項(xiàng)集。

2.3 交叉和變異

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

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

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

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

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

x但是，為了避免候選項(xiàng)集中存在相同個(gè)體，調(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ù)集來(lái)評(píng)估

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

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

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

圖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é)束語(yǔ)

本文提出一種基于二進(jìn)制編碼的遺傳算法MGA從數(shù)據(jù)集中挖掘頻繁項(xiàng)集。對(duì)于繁雜的數(shù)據(jù)集，改進(jìn)的遺傳算法MGA通過(guò)對(duì)事務(wù)集進(jìn)行矩陣二進(jìn)制編碼并通過(guò)矩陣計(jì)算挖掘頻繁項(xiàng)集，避免了多次掃描數(shù)據(jù)庫(kù)，而對(duì)初始種群的降維也降低了矩陣維度，從而減少了挖掘的運(yùn)行時(shí)間和內(nèi)存消耗。MGA繼承了遺傳算法優(yōu)良的全局搜索能力，通過(guò)優(yōu)化算法中交叉和變異生成新個(gè)體的過(guò)程，改進(jìn)了算法的局部搜索能力，進(jìn)而提高了頻繁項(xiàng)集整體挖掘效率與質(zhì)量。接下來(lái)要考慮在高維數(shù)據(jù)集的情況下，從事在算法過(guò)程中動(dòng)態(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]王偉，高亮，吳濤. 基于遺傳算法的長(zhǎng)頻繁項(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ā)展趨勢(shì)[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]閻平凡，張長(zhǎng)水.人工神經(jīng)網(wǎng)絡(luò)與模擬進(jìn)化計(jì)算[M].北京：清華大學(xué)出版社，2001.

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