基于質(zhì)數(shù)理論的最大頻繁項集挖掘研究

【摘 ? 要】 ? 利用質(zhì)數(shù)的特性，采用質(zhì)數(shù)積代替事務(wù)將事務(wù)數(shù)據(jù)庫轉(zhuǎn)換成質(zhì)數(shù)積數(shù)據(jù)集，采用數(shù)據(jù)集二維數(shù)組保存質(zhì)數(shù)積之間的整除關(guān)系和最大公約數(shù)信息。PNMax算法利用數(shù)據(jù)集二維數(shù)組可以快速地挖掘出最大頻繁項集，并且數(shù)據(jù)集二維數(shù)組在挖掘過程中將持續(xù)減少所占的空間。最后通過實驗驗證了算法的可行性和優(yōu)越性。

【關(guān)鍵詞】 ? 質(zhì)數(shù);質(zhì)數(shù)積;最大頻繁項集;PNMax

Research on Mining Maximum Frequent Itemsets Based

on Prime Number Theory

Wang Lijun

（Department of Information Engineering， Anhui Institute of Economics Management， Hefei 230031， Anhui）

Abstract：Using the characteristics of prime number， the transaction database is transformed into a data set of prime product by using the product of prime number instead of transaction， and the two-dimensional array of data set is used to save the integer division relationship and the greatest common divisor information between the products of prime number. PNMax algorithm can quickly mine the maximum frequent itemsets by using this array， and this array will continue to reduce the space occupied in the mining process. Finally， the feasibility and superiority of the algorithm are verified by experiments.

Key words： prime number; product of prime numbers; maximum frequent itemsets;PNMax

〔中圖分類號〕 ?TP301.6 ? 〔文獻(xiàn)標(biāo)識碼〕 ?A ? ? ? ? ? ? 〔文章編號〕 1674 - 3229（2021）03- 0000 - 00

0 ? ? 引言

挖掘最大頻繁模式的經(jīng)典算法有FP-Max[1]、DMFIA[2]、MaxMiner[3]和MAFIA[4]等。FP-Max算法相當(dāng)于FP-growth[5]算法的擴展，生成初始FP-Tree[5]會需要長期存放，依舊采用遞歸方式進(jìn)行挖掘，需要產(chǎn)生大量的條件模式樹消耗大量的時空資源，并采用最大頻繁項目樹MFI-Tree[1]來保存最大頻繁項目集。DMFIA算法依舊采用FP-Tree樹存放事務(wù)信息，但該算法會產(chǎn)生過多冗余的候選項目集影響算法的執(zhí)行效率。每種經(jīng)典的算法都有各自的優(yōu)勢，但仍存在改進(jìn)的空間。因此可以從優(yōu)化存儲事務(wù)信息的存儲結(jié)構(gòu);減少產(chǎn)生條件存儲結(jié)構(gòu)的數(shù)量和規(guī)模;減少挖掘事務(wù)項的數(shù)量等策略來提高挖掘最大頻繁模式算法的時空效率。

許多學(xué)者提出了一些新的改進(jìn)方案，比如PFPMax算法[6]、NCFP-Max算法[7]等，PFPMax算法是基于壓縮FP-樹和數(shù)組技術(shù)的最大頻繁模式挖掘算法，壓縮FP-樹是對FP-Tree進(jìn)行改進(jìn)，使得項頭表的數(shù)目有所減少，從而達(dá)到減少遞歸調(diào)用的次數(shù)，并結(jié)合數(shù)組技術(shù)實現(xiàn)挖掘最大頻繁模式;NCFP-Max算法可以實現(xiàn)不產(chǎn)生條件模式樹，采用類似二維表格的項目表格進(jìn)行位運算來獲取最大頻繁項集。

筆者將提出一種基于質(zhì)數(shù)理論的最大頻繁項集挖掘算法PNMax，該算法可以在不需要創(chuàng)建FP-Tree樹結(jié)構(gòu)的情況下，利用質(zhì)數(shù)積二維數(shù)組進(jìn)行數(shù)值運算來挖掘最大頻繁項集。最后以實驗方式驗證了算法的可行性和優(yōu)越性。

1 ? ? 相關(guān)理論和研究

1.1 ? 質(zhì)數(shù)

質(zhì)數(shù)（Prime Number）是一個大于1的自然數(shù)，而且除了1和本身外，不存在其他因數(shù)的數(shù)稱為質(zhì)數(shù)，也叫素數(shù)。

所有大于1的自然數(shù)，要么其本身就是質(zhì)數(shù)，否則就可以分解成幾個質(zhì)數(shù)之積，并且這種分解是唯一的。

素數(shù)在數(shù)論中有著很重要的地位。質(zhì)數(shù)具有很多性質(zhì)：

（1）質(zhì)數(shù)的因數(shù)只有1和本身;

（2）質(zhì)數(shù)的個數(shù)有無限個;

（3）所有大于10 的質(zhì)數(shù)的個位數(shù)都是1，3，7，9;

（4）大于3的素數(shù)只有6n-1和6n+1兩種形式（n為大于等于1的整數(shù)），但符合這兩種形式的數(shù)不一定是質(zhì)數(shù)，如25不是質(zhì)數(shù);

質(zhì)數(shù)常被應(yīng)用到密碼學(xué)、生物科學(xué)和軍事領(lǐng)域。

1.2 ? 定義與性質(zhì)

頻繁事務(wù)項與質(zhì)數(shù)映射方法：設(shè)定最小支持度計數(shù)為min_sup，掃描一次事務(wù)數(shù)據(jù)庫D后刪除事務(wù)中的非頻繁事務(wù)項，并將事務(wù)中的事務(wù)項根據(jù)事務(wù)項支持度計數(shù)大小進(jìn)行降序，排序后得到的預(yù)處理事務(wù)數(shù)據(jù)庫D， 獲得項頭表L，將支持度計數(shù)最大的頻繁事務(wù)項映射為質(zhì)數(shù)2，第二大的事務(wù)項映射為質(zhì)數(shù)3，以此類推。舉例設(shè)置最小支持度計數(shù)為4，預(yù)事務(wù)數(shù)據(jù)庫D如表1所示，得到的項頭表L如表2所示。

定義1：質(zhì)數(shù)序列--將預(yù)處理事務(wù)數(shù)據(jù)庫D中的事務(wù)根據(jù)頻繁事務(wù)項與質(zhì)數(shù)的映射關(guān)系進(jìn)行相應(yīng)的轉(zhuǎn)換而得到的序列。如TID為1的事務(wù){(diào)c，d，f，g}轉(zhuǎn)換為質(zhì)數(shù)序列{2，3，7，11}。

定義2：質(zhì)數(shù)積--將質(zhì)數(shù)序列中的所有質(zhì)數(shù)相乘得到的數(shù)值。如質(zhì)數(shù)序列{2，3，7，11}的質(zhì)數(shù)積為462。

定義3：質(zhì)數(shù)積數(shù)據(jù)集—將預(yù)處理事務(wù)數(shù)據(jù)庫D中的所有事務(wù)都轉(zhuǎn)換成質(zhì)數(shù)序列，并計算出相應(yīng)的質(zhì)數(shù)積，并統(tǒng)計質(zhì)數(shù)積相同的個數(shù)，按照質(zhì)數(shù)積的大小進(jìn)行降序排序，由質(zhì)數(shù)積和統(tǒng)計計數(shù)形成的數(shù)據(jù)集。如表1預(yù)處理數(shù)據(jù)庫D對應(yīng)的質(zhì)數(shù)積數(shù)據(jù)集表3所示

性質(zhì)1：若兩個事務(wù)的質(zhì)數(shù)積數(shù)值相等，則這兩個事務(wù)包含的事務(wù)項完全相同。

證：根據(jù)預(yù)處理事務(wù)數(shù)據(jù)庫的特點，每個事務(wù)中包含的事務(wù)項最多出現(xiàn)一次，根據(jù)頻繁事務(wù)項與質(zhì)數(shù)的映射關(guān)系，則每一個質(zhì)數(shù)序列中包含的質(zhì)數(shù)最多也出現(xiàn)一次，另外質(zhì)數(shù)只存在1和本身的因子，不存在其他的因子，故質(zhì)數(shù)積相等的兩個事務(wù)包含的事務(wù)項也相同

性質(zhì)2：若兩個事務(wù)的質(zhì)數(shù)積不相同，且存在整除關(guān)系，則質(zhì)數(shù)積大對應(yīng)的事務(wù)包含的項集是質(zhì)數(shù)積小的事務(wù)對應(yīng)項集的超集。

證：設(shè)事務(wù)T1對應(yīng)的項集為{d1，d2，d3，…，dk}，對應(yīng)的質(zhì)數(shù)序列為{p1，p2，p3，…，pk}，則該事務(wù)的質(zhì)數(shù)積TV1= p1*p2*p3*…*pk，若事務(wù)T2的質(zhì)數(shù)積TV2不等于TV1，且可以整除TV1，則TV2=（ p1*p2*p3*…*pk）*TVother，根據(jù)頻繁事務(wù)項與質(zhì)數(shù)的映射關(guān)系，TV2對應(yīng)的事務(wù)T2中必包含p1、p2、p3、…、pk所對應(yīng)的事務(wù)項d1、d2、d3、…、dk，因此T2是T1的超集，T1是T2的真子集。

舉例說明：質(zhì)數(shù)積462可以整除質(zhì)數(shù)積42，462的質(zhì)數(shù)序列為{2，3，7，11}，對應(yīng)的事務(wù)為{c，d，f，g}，質(zhì)數(shù)積42的質(zhì)數(shù)序列為{2，3，7}，對應(yīng)的事務(wù)為{c，d，f}，則{c，d，f，g}是{c，d，f}的超集。

性質(zhì)3：若兩個事務(wù)的質(zhì)數(shù)積存在最大公約數(shù)g，且g不為1，則這兩個事務(wù)存在若干個相同的事務(wù)項。g也可以表示為一個質(zhì)數(shù)或質(zhì)數(shù)的乘積，g所對應(yīng)的項集即為這兩個事務(wù)最大的共同事務(wù)項的集合。

證：設(shè)兩個事務(wù)T1和T2，對應(yīng)的質(zhì)數(shù)積為TV1和TV2，TV1和TV2的最大公約數(shù)為g，則TV1=g*TVother1，TV2=g*TVother2，根據(jù)質(zhì)數(shù)積的產(chǎn)生方式和質(zhì)數(shù)的特性，可知g也可以表示一個質(zhì)數(shù)或質(zhì)數(shù)的乘積，g所對應(yīng)的項集必是T1和T2最大的共同事務(wù)項的集合。

舉例說明：質(zhì)數(shù)積462與質(zhì)數(shù)積330的最大公約數(shù)為66，則66對應(yīng)的質(zhì)數(shù)序列為{2，3，11}，對應(yīng)的項集為{c，d，g}是462對應(yīng)的事務(wù){(diào)c，d，f，g}和330對應(yīng)的事務(wù){(diào)c，d，e，g}的最大共同事務(wù)項組成的項集。

2 ? ? 挖掘算法研究

本論文主要研究如何快速地挖掘最大頻繁模式，通過頻繁事務(wù)項與質(zhì)數(shù)的映射轉(zhuǎn)換后，預(yù)處理事務(wù)數(shù)據(jù)庫轉(zhuǎn)換成了質(zhì)數(shù)積數(shù)據(jù)集，挖掘最大頻繁模式的計算變成數(shù)值運算。每一個事務(wù)都是用質(zhì)數(shù)積代替，另外，筆者將引用二維數(shù)組來存儲質(zhì)數(shù)積之間的整除關(guān)系和最大公約數(shù)信息，有了該二維數(shù)組的協(xié)助，我們不需要再建立FP-tree樹結(jié)構(gòu)和條件子FP-tree樹結(jié)構(gòu)，更不會采用遞歸挖掘方式挖掘最大頻繁模式。

定義4：質(zhì)數(shù)積二維數(shù)組--若質(zhì)數(shù)積數(shù)據(jù)集包含m條記錄，則需要創(chuàng)建一個規(guī)模為m*（m-1）/2的二維動態(tài)數(shù)組，該質(zhì)數(shù)積二維數(shù)組有兩個方面的功能，功能一存儲質(zhì)數(shù)積之間的整除關(guān)系和相關(guān)的計數(shù)信息;功能二是在功能一完成后才能使用的，用于存儲質(zhì)數(shù)積之間的最大公約數(shù)和相關(guān)的計數(shù)信息。

質(zhì)數(shù)積二維數(shù)組的初始化：數(shù)組的對角線的元素值為相應(yīng)質(zhì)數(shù)積的質(zhì)數(shù)積計數(shù)，其他元素值初始值為0，再根據(jù)質(zhì)數(shù)積之間的整除關(guān)系將相應(yīng)的元素值改為1（如462與42是整除關(guān)系，則將462與42交疊的元素值改為1），完成整除關(guān)系的元素值的修改后形成的初始質(zhì)數(shù)積二維數(shù)組。

利用質(zhì)數(shù)積二維數(shù)組挖掘最大頻繁模式算法需要運用挖掘方法一和挖掘方法二兩種方法，才可以提取出全部的最大頻繁模式。

挖掘方法一：利用質(zhì)數(shù)積的整除關(guān)系獲取部分最大頻繁項集;

具體描述：從最大的質(zhì)數(shù)積開始向右運算，可通過質(zhì)數(shù)積整除關(guān)系數(shù)組的非對角線元素值來判斷質(zhì)數(shù)積與其他質(zhì)數(shù)積是否存在整除關(guān)系，若兩個質(zhì)數(shù)積對應(yīng)的元素值為1，則表示這兩個數(shù)存在整除關(guān)系，若存在整除關(guān)系則將除數(shù)的所在列的對角線元素的計數(shù)加上被除數(shù)的質(zhì)數(shù)積計數(shù)（如462與42存在整除關(guān)系，則對角線元素值加1），以此類推，最終得到的質(zhì)數(shù)積二維數(shù)組如圖1所示。質(zhì)數(shù)積整除關(guān)系數(shù)組的對角線元素值大于等于最小支持度計數(shù)的質(zhì)數(shù)積所對應(yīng)的項集將作為候選最大頻繁項集，本例中42、15、14和10符合要求，由于42與14存在整除關(guān)系，因存在整除關(guān)系即項集之間就存在包含關(guān)系，根據(jù)最大頻繁項集的真子集都不是最大頻繁項集，故14舍棄。則最大頻繁質(zhì)數(shù)積項集為{42：4，15：5，10：5}

挖掘方法二：利用質(zhì)數(shù)積的最大公約數(shù)獲取剩余最大頻繁項集

刪除質(zhì)數(shù)積整除關(guān)系數(shù)組中候選質(zhì)數(shù)積所在列，本例中即刪除42、15、14和10所在的列，將最大質(zhì)數(shù)積所在列的對角線元素值初始化為該質(zhì)數(shù)積計數(shù)，剩下所有列的元素值對挖掘最大頻繁項集無影響，故不做清零操作，從剩下的最大質(zhì)數(shù)積開始向右分別與其他質(zhì)數(shù)積求最大公約數(shù)，并將最大公約數(shù)存放在兩個質(zhì)數(shù)積數(shù)交疊的元素位置上，并將這大質(zhì)數(shù)積所在列的對角線元素值加上小質(zhì)數(shù)積的質(zhì)數(shù)積計數(shù)并將結(jié)果存放在較小的質(zhì)數(shù)積所在列的對角線元素位置上，若該相加的值大于等于最小支持度計數(shù)則將該最大公約數(shù)作為候選最大頻繁項集;完成第一遍最大公約數(shù)的計算后，繼續(xù)向上開始第二遍向右分別求最大公約數(shù)，以此類推，若最左側(cè)的最大公約數(shù)已經(jīng)是質(zhì)數(shù)則停止運算，以質(zhì)數(shù)積462為例，其演算過程如下圖：

運算完462的最大公約數(shù)計算后，繼續(xù)運算330的最大公約數(shù)直到倒數(shù)第二個質(zhì)數(shù)積即110。利用質(zhì)數(shù)的最大公約數(shù)的求解方法得到候選最大頻繁項集為{6：4，22：4}，因6是42的因子故舍棄，將{22：4}加入最大頻繁質(zhì)數(shù)積項集后，最終的最大頻繁質(zhì)數(shù)積項集為{42：4，15：5，10：5，22：4}。

利用解碼器將各個質(zhì)數(shù)積還原成項集得到的最大頻繁項集為{{c，d，f：4}，{d，e：5}，{c，e：5}，{c，g：4}}

上述最大頻繁模式挖掘過程需要充分的利用質(zhì)數(shù)積二維數(shù)組，這兩個挖掘方法中描述的運算都是簡單的數(shù)值運算，且該數(shù)組也是數(shù)值型數(shù)組即可，存儲空間較小，且挖掘過程中不需要創(chuàng)建樹結(jié)構(gòu)，也不存在遞歸調(diào)用。

3 ? ? 偽算法描述

筆者將基于質(zhì)數(shù)理論的最大頻繁項集挖掘算法為PNMax的偽算法為：

定義函數(shù) PNMaxFunction （）

形參：初始質(zhì)數(shù)積二維數(shù)組PNArray，最小支持度計數(shù)min_sup

輸出：最大頻繁項集集合max_fi

PNMaxFunction （PNArray， min_sup）{

max_fi= ?; ? //定義并初始化最大頻繁項集集合max_fi

PN_max_fi= ?; ? //定義并初始化最大頻繁質(zhì)數(shù)積項集集合PN_max_fi

獲取PNArray的行數(shù)m;

FC1（）; ?//調(diào)用FC1（）方法，執(zhí)行挖掘方法一

FC2（）; ?//調(diào)用FC1（）方法，執(zhí)行挖掘方法二

FC3（）; ?//調(diào)用FC3（）方法，刪除非最大頻繁質(zhì)數(shù)積項集并轉(zhuǎn)換成最大頻繁項集

FC1（）{ ?//定義挖掘方法一的功能

For（i=m-1;i>=1;i- -）{ ?//從最后一行即行標(biāo)為m-1開始遍歷

For（j=1;j<=m-1;j++）{

If（PNArray[i][j]==1）{

PNArray[m-1-j][0]+=PNList[j][1];// 包含統(tǒng)計計數(shù)加上被除數(shù)的質(zhì)數(shù)積計數(shù)

}

}

}

For（k=m-1;k>=0;k- -）{

If（PNArray[k][0]>=min_sup）{

PNList[m-1-k][0]加入PN_max_fi;

刪除PNList中行號為m-1-k的行;

}

}

}

FC2（）{ ?//定義挖掘方法二的功能

獲取PN_max_fi中元素的個數(shù)n;

刪除加入PN_max_fi的質(zhì)數(shù)積的PNArray相關(guān)元素空間;

For（p=m-n-1;p>=1;p- -）

PNArray[p][0]= PNList[m-n-1-p][1]; ? //初始化正在運算的質(zhì)數(shù)積的統(tǒng)計值

For（q= m-n-1;q>=1;q--）{

For（r=1;r<=q;r++）{

If（q= =p{

PNArray[q][r]=GCD（PNList[m-n-1-p][0]， PNList[（m-n-1-p）++][0]）;

}else{

PNArray[q][r]=GCD（PNArray[q+1][1]， PNArray[q+1][ ++r]）;

}

PNArray[q--][0]= PNArray[q [0]+ PNList[（m-n-1-p）++][1];//統(tǒng)計最大公約數(shù)包含個數(shù)

If（PNArray[q--][0]>= min_sup）{

將PNArray[q][r]加入PN_max_fi;

}

}

}

FC3（）{

刪除PN_max_fi中可以作為其他質(zhì)數(shù)積除數(shù)的質(zhì)數(shù)積;

將PN_max_fi剩下的質(zhì)數(shù)積轉(zhuǎn)換成相應(yīng)的最大頻繁項集

}

}

4 ? ? 實驗驗證

采用PNMax、FP-Max和DMFIA三種不同的算法對相同數(shù)據(jù)庫集進(jìn)行挖掘比較，三種算法挖掘出的最大頻繁項集結(jié)果一致，從而驗證了PNMax的可行性，通過圖表的方式顯示挖掘的執(zhí)行時間和內(nèi)存消耗情況分別如圖3和圖4所示，分析圖表驗證PNMax算法的優(yōu)越性。

PNMax算法在兩種類型的數(shù)據(jù)集上都具有較好的執(zhí)行效率，PNMax算法的時間效率明顯優(yōu)于FP-Max和DMFIA算法，隨著支持度閾值減少，PNMax算法的優(yōu)越性越來越明顯，因此PNMax算法更加優(yōu)越。

5 ? ? ?結(jié)論與展望

PNMax算法在質(zhì)數(shù)積二維數(shù)組的協(xié)助下可以通過數(shù)值運算即可快速地挖掘出最大頻繁項集，即不需要創(chuàng)建FP-Tree樹結(jié)構(gòu)也不要遞歸調(diào)用，大大提高了執(zhí)行效果和減少系統(tǒng)資源的浪費。下一步工作希望能將該算法運用到SPARK平臺上實現(xiàn)分布式運算。

參考文獻(xiàn)：

[1] Grahne G，Zhu J. High Performance Mining of Maximal Frequent Itemsets[EB/OL]. 2003-06-05/2014-07-06

[2] 宋余慶，朱玉全，孫志揮等.基于FP-Tree的最大頻繁項目集挖掘算法[J].軟件學(xué)報，2003，14（9）：1586-1592

[3] R J Bayardo.Efficiently mining long patterns from databases[C] .ACM SIGMOD Record：ACM，1998：85-93

[4]Burdick D，Calimlim M，Gehrke J.Mafia：A Maximal Frequent Itemset Algorithm for Transactional Database[A].In：Stuart Feldman ed，Proceeding of the 17th International Conference on Data Engineering[C].Washington：IEEE Computer Society Press，2001：443-452

[5]Han J，Pei J，Yin Y.Ming frequent patterns without candidate generation[C].ACM SIGMOD Record：ACM，2000：29（2）：1-12

[6] 馬達(dá)，王佳強.一種基于壓縮FP-樹的最大頻繁項集挖掘算法[J].長春理工大學(xué)學(xué)報（自然科學(xué)版），2009，32（3）：457-461

[7] 趙志剛，王芳，萬.基于OWSFP_tree的最大頻繁項目集挖掘算法 [J]. 計算機工程與設(shè)計，2013，34（5）：1687-1690

[收稿日期] ? 2020-03-16

[基金項目] ? 安徽省高校自然科學(xué)重點項目“基于spark分布式計算平臺的高校教學(xué)大數(shù)據(jù)分析方法研究”（KJ2019A0965）;安徽經(jīng)濟(jì)管理學(xué)院教學(xué)研究項目 “基于SPOC平臺的“五位一體”的高職教學(xué)模式推進(jìn)研究”（yjjyxm201903）。

[作者簡介] ? 王利軍，（1983- ），男，碩士，安徽經(jīng)濟(jì)管理學(xué)院信息工程系講師，研究方向：為數(shù)據(jù)挖掘、計算機應(yīng)用。