基于矩陣二進制編碼遺傳算法的頻繁項集挖掘

杜嘉偉 余粟

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

關鍵詞： 遺傳算法;關聯規則;頻繁項集

文章編號： 2095-2163（2021）01-0143-05 中圖分類號：TP301.6 文獻標志碼：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 引?言

頻繁項集是那些出現在二進制或者定量數據集中的項目集，其出現頻率超過指定的最小支持度，這是關聯規則挖掘的基礎和重要的部分[1]。由于多數挖掘定量頻繁項目集的方法都是先將數據集轉換成二進制的表現方法[2]，本文擬重點關注二進制頻繁項目集的挖掘。

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

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

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

1 基本概念

1.1 頻繁項集

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

（1）項集（Itemset）：就是項的集合。包含k個項的項集稱為k項集。當一個k項集計算所得的支持度滿足設定的支持度閾值，就將該項集定義為頻繁k項集。

（2）支持度（Support）：描述了多個項集在所有事務中同時出現的概率。事務數據集中的支持度用sup（x）來表示，支持度閾值用min_sup來表示，在挖掘頻繁項集的過程中，min_sup能夠篩選并枚舉出所有重要的項集。基于以上描述可推得定義如下[1]：

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

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

1.2 遺傳算法

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

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

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

2 MGA算法

2.1 編碼搜索空間、項目集、事務

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

給定事務數據集D映射關系f：D→M，即f（D）=（aij）nxm=M，并且，

其中，Ti為D中事務的個數，m為I中數據項的個數[12]。

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

其中，Dl為D中事務的總個數，L為I中數據項的總個數。

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

2.2 初始種群及其降維

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

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

同時，根據先驗啟發式原理：

從中可以推論出：

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

2.3 交叉和變異

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

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

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

2.4 適應度函數和候選結果

適應度函數用于評估個體的質量。在MGA中，個體的適應度等于該個體的支持度，即：

x但是，為了避免候選項集中存在相同個體，調整適應度函數為：

式中，數據集H是前一次挖掘得到的候選項集。

2.5 MGA算法的偽代碼

算法1 基于矩陣二進制編碼的改進遺傳算法

3 實驗結果與分析

在本節中，使用了某零售商店數據集來評估

MGA算法，其中實驗數據包含有65 000多條商品交易信息和2 241個交易項目。實驗環境為64位的Win10的系統，i7-9700KF，CPU 3.6 GHz的計算機。

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

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

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

4 結束語

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

參考文獻

[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]王偉，高亮，吳濤. 基于遺傳算法的長頻繁項集挖掘方法[J]. 計算機技術與發展，2008，18（4）：19-21.

[6]侯燕，劉辛.基于主從架構和GA的模糊關聯規則挖掘算法[J].控制工程，2017，24（2）：276-282.

[7]孫明瑞，臧天儀. 面向健康醫療的分類關聯規則挖掘研究[J]. 智能計算機與應用，2020，10（2）：1-6，11.

[8]李忠，安建琴，劉海軍，等. 關聯挖掘算法及發展趨勢[J]. 智能計算機與應用，2017，7（5）：22-25.

[9]胡濤.基于關聯規則的數據挖掘算法[J].電子技術與軟件工程，2018，2（2）：186.

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

[11]閻平凡，張長水.人工神經網絡與模擬進化計算[M].北京：清華大學出版社，2001.

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