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

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

【關鍵詞】 ? 質(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 ? 〔文獻標識碼〕 ?A ? ? ? ? ? ? 〔文章編號〕 1674 - 3229（2021）03- 0000 - 00

0 ? ? 引言

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

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

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

1 ? ? 相關理論和研究

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ù)常被應用到密碼學、生物科學和軍事領域。

1.2 ? 定義與性質(zhì)

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

定義1：質(zhì)數(shù)序列--將預處理事務數(shù)據(jù)庫D中的事務根據(jù)頻繁事務項與質(zhì)數(shù)的映射關系進行相應的轉(zhuǎn)換而得到的序列。如TID為1的事務{(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ù)集—將預處理事務數(shù)據(jù)庫D中的所有事務都轉(zhuǎn)換成質(zhì)數(shù)序列，并計算出相應的質(zhì)數(shù)積，并統(tǒng)計質(zhì)數(shù)積相同的個數(shù)，按照質(zhì)數(shù)積的大小進行降序排序，由質(zhì)數(shù)積和統(tǒng)計計數(shù)形成的數(shù)據(jù)集。如表1預處理數(shù)據(jù)庫D對應的質(zhì)數(shù)積數(shù)據(jù)集表3所示

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

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

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

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

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

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

證：設兩個事務T1和T2，對應的質(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所對應的項集必是T1和T2最大的共同事務項的集合。

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

2 ? ? 挖掘算法研究

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

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

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

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

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

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

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

刪除質(zhì)數(shù)積整除關系數(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ù)并將結果存放在較小的質(zhì)數(shù)積所在列的對角線元素位置上，若該相加的值大于等于最小支持度計數(shù)則將該最大公約數(shù)作為候選最大頻繁項集;完成第一遍最大公約數(shù)的計算后，繼續(xù)向上開始第二遍向右分別求最大公約數(shù)，以此類推，若最左側的最大公約數(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)建樹結構，也不存在遞歸調(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- -）{ ?//從最后一行即行標為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相關元素空間;

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)換成相應的最大頻繁項集

}

}

4 ? ? 實驗驗證

采用PNMax、FP-Max和DMFIA三種不同的算法對相同數(shù)據(jù)庫集進行挖掘比較，三種算法挖掘出的最大頻繁項集結果一致，從而驗證了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 ? ? ?結論與展望

PNMax算法在質(zhì)數(shù)積二維數(shù)組的協(xié)助下可以通過數(shù)值運算即可快速地挖掘出最大頻繁項集，即不需要創(chuàng)建FP-Tree樹結構也不要遞歸調(diào)用，大大提高了執(zhí)行效果和減少系統(tǒng)資源的浪費。下一步工作希望能將該算法運用到SPARK平臺上實現(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].軟件學報，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] 馬達，王佳強.一種基于壓縮FP-樹的最大頻繁項集挖掘算法[J].長春理工大學學報（自然科學版），2009，32（3）：457-461

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

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

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

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