關(guān)于Top-N最頻繁項集挖掘的研究

朱顥東，李紅嬋

(鄭州輕工業(yè)學(xué)院計算機(jī)與通信工程學(xué)院 鄭州 450002)

隨著最頻繁項集數(shù)目的增加，文本關(guān)聯(lián)規(guī)則的個數(shù)及其相應(yīng)的挖掘算法的時空復(fù)雜度都急劇上升，使最頻繁項集的挖掘成為文本關(guān)聯(lián)規(guī)則挖掘中研究的重點和難點[1-15]。在最頻繁項集挖掘過程中，最小支持度閾值是一個十分關(guān)鍵的參數(shù)，該參數(shù)一般都是通過人工指定，但主觀指定方式很難符合客觀實際。參數(shù)值指定過高，導(dǎo)致一些有價值的規(guī)則丟失；參數(shù)值指定過低，導(dǎo)致規(guī)則數(shù)量劇增，生成許多無用規(guī)則，降低挖掘算法的性能。文獻(xiàn)[1]表明：當(dāng)語料庫的文檔為1 000篇、文本事務(wù)集的特征數(shù)目達(dá)到100個、最小支持度閾值為0.1時，其頻繁項集的數(shù)目高達(dá)2 316個，產(chǎn)生的規(guī)則數(shù)量十分巨大，但有用的規(guī)則卻很少。

為了解決上述問題，已有眾多學(xué)者提出了一些相關(guān)的算法[1-15]，大都擯棄最小支持度閾值，通過指定最頻繁項集的數(shù)量N控制所生成的頻繁項集規(guī)模。這些算法的不足之處在于：由于沒有設(shè)定最小支持度閾值，在挖掘過程中很可能對支持度較小的頻繁項集也進(jìn)行處理，使算法的時空復(fù)雜度較高，尤其在文檔數(shù)量巨大時，時空復(fù)雜度會更高。

為了克服IntvMatrix算法的不足，本文借用文獻(xiàn)[3]動態(tài)調(diào)整支持度閾值的思想，提出一種基于集合和倒排表的Top-N最頻繁項集挖掘算法。通過實驗對比，該算法優(yōu)于NApriori算法和IntvMatrix算法。

1 相關(guān)知識

定義 1 把全部項集依照支持度從大到小排序，假設(shè)NS等于第N位項集的支持度，則最頻繁項集：

因為支持度等于NS的項集個數(shù)可能有多個，Top-N中的最頻繁項集的數(shù)目有可能多于N個。例如，如果第N+1、N+2、…、N+m個項集的支持度也是NS，則Top-N由N+m個頻繁項集組成。

定義 2 把全部k-項集依照支持度從大到小排序，假設(shè)NSk等于第N位的k-項集的支持度，則最頻繁k-項集：

命題 1 假設(shè)Top-N的最小支持度是NS，Top-Nk的最小支持度是NSk，則NS>=NSk。

證明 假設(shè)NS

由命題2可知，在生成Top-N的過程中，當(dāng)前最小支持度閾值被逐步增大，減少了候選項集的規(guī)模，提高了算法效率。

2 本文所提推論

倒排表是一種高級索引結(jié)構(gòu)，由詞表和文檔表兩部分組成。詞表由文檔集中的特征詞組成，對詞表的任一特征詞，在文檔表中都有一行與包含該特征詞的文檔ID所對應(yīng)。在IR領(lǐng)域，倒排表常用于文本索引，可以提高查找速度。

表1為一個文檔事務(wù)數(shù)據(jù)庫，表2是其相應(yīng)的倒排表。

表1 文檔事務(wù)數(shù)據(jù)庫

表2 相應(yīng)的倒排表

倒排表雖然在一定程度上提高了單一特征詞的查找效率，也即1-項集的查找效率，但是對其他k-項集而言，很難獲得相應(yīng)的支持度，這是因為倒排表使得出現(xiàn)在同一事務(wù)中的各個項之間變得相互獨立；并且從表2還可以看出，倒排表存在大量空元素，極大地浪費了內(nèi)存空間。因此，本文對倒排表進(jìn)行了改造。

(1) 在詞表中，各項按其文檔頻從大到小的順序排序，并用序號表明其位置。此時的詞表由序號、項名、指向文本事務(wù)集合的指針3部分組成。

(2) 文檔表中，每一行表示一個集合，集合元素由特征出現(xiàn)的文本事務(wù)號組成。此時表中各項以其所包含的元素個數(shù)降序排列。表3為改造后對應(yīng)的倒排表。

根據(jù)推論2，在進(jìn)行連接操作時就不需要再次掃描數(shù)據(jù)庫，如連接時a與e只需對它們的指針?biāo)傅募先〗患湍軌蛱岣咚惴ㄐ?。a與e連接結(jié)果如表4所示。

表3 改造表1后的倒排表

表4 a與e連接結(jié)果

推論 3 設(shè)Lk為K-頻繁項集的集合，如果Lk中的項集個數(shù)不大于K，則Lk為極大頻繁項集。

證明 經(jīng)典Apriori算法指出，任何強項集的子集必定是強項集。因此可知，如果存在Lk+1(即K+1頻繁項集的集合)，則?lk+1∈Lk+1，lk+1一定有K+1個k-頻繁子集在Lk中，因此，如果Lk的項集個數(shù)不大于K，則必定不能生成Lk+1。推論得證。

根據(jù)推論3，在產(chǎn)生(k+1)-項候選頻繁項集之前，先統(tǒng)計k-項頻繁集中項集的個數(shù)，如果數(shù)目<=k，則算法可以終止，也能提高算法效率。

推論 4 設(shè)?lk∈Lk(Lk為k-頻繁項集)，?Item∈lk，如果Item在Lk中的支持?jǐn)?shù)小于K，則lk不能用于生成Lk+1。

證明 經(jīng)典Apriori算法指出，任何強項集的子集必定是強項集。因此可知，?lk+1∈Lk+1，lk+1中必然存在K+1個k-頻繁項集屬于Lk。明顯有?Item∈lk，在lk的K+1個k-頻繁項集中，Item的支持?jǐn)?shù)至少為K。所以，?Item∈lk，且Item在Lk中的支持?jǐn)?shù)小于K，則lk不能用于生成Lk+1。推論得證。

根據(jù)推論4，如果某個k-項頻繁項集中的一項在其中出現(xiàn)的次數(shù)

3 本文算法

3.1 本文算法思想

借用文獻(xiàn)[3]中動態(tài)調(diào)整支持度閾值的思想，利用文中所給出的幾個命題和結(jié)論，將倒排表和集合相結(jié)合，可以獲得一個Top-N最頻繁項集挖掘算法。

3.2 算法描述

輸入：文本事務(wù)數(shù)據(jù)庫D，最小支持?jǐn)?shù)0δ(初始值為1)，頻繁項集數(shù)N；

輸出：Top-N最頻繁項集。

步驟 1 掃描D以產(chǎn)生改造的倒排表W。

3.3 本文算法過程說明

Procedure Delete(Lk?1)//從Lk?1中刪除包含項次數(shù)小于k?1的項集；

4 實驗驗證及其分析

4.1 實驗驗證

實驗使用數(shù)據(jù)集由從新華網(wǎng)上下載的新聞材料組成。新聞材料的發(fā)表日期范圍為2006～2008年，共1 500篇，經(jīng)預(yù)處理后(忽略所有的報頭)，挖掘該數(shù)據(jù)集的頻繁項集并進(jìn)行實驗，比較本文算法與文獻(xiàn)[3]提出的NAprioir算法和文獻(xiàn)[5]提出的IntvMatrix算法的性能差異。

實驗 1 比較3種算法在所選擇數(shù)據(jù)集上挖掘出的規(guī)則數(shù)目和有效規(guī)則數(shù)，結(jié)果如表5所示。

表5 3種算法的有效規(guī)則率對比

實驗 2 比較3種算法對不同規(guī)模的頻繁項集進(jìn)行挖掘時所消耗的時間，從實驗結(jié)果選取差別較明顯的實驗數(shù)據(jù)作對比圖，如圖1所示。

圖1 3種算法執(zhí)行時間對比

4.2 實驗分析

從表5可以看出，由于本文算法采用支持?jǐn)?shù)動態(tài)自適應(yīng)調(diào)整策略，所挖掘的規(guī)則有效率較高；IntvMatrix算法的規(guī)則有效率次之；Napriori算法產(chǎn)生了大量無意義的規(guī)則，規(guī)則有效率最低。

從圖1可以看出，在頻繁項集個數(shù)相同的情況下，本文算法的時間性能明顯優(yōu)于IntvMatrix和Napriori算法，分析其原因在于：

(1) 本文算法采用倒排索引這種數(shù)據(jù)結(jié)構(gòu)組織事務(wù)集，提高了檢索速度。

(2) 本文算法掃描數(shù)據(jù)庫過程的步驟1中，以改造后的倒排表組織文檔并對其進(jìn)行掃描，這是該算法唯一一次掃描數(shù)據(jù)庫，對于海量數(shù)據(jù)庫來說，其時間效率的提高很明顯。

(3) 本文算法中Count(Lk?1)函數(shù)用來計算Lk?1中頻繁集的個數(shù)，根據(jù)推論3，如果Lk?1中頻繁項集的個數(shù)小于k，則無需再生成Lk，此時算法可以結(jié)束，也提高了算法的時間效率。

(4) 根據(jù)推論4，Delete(Lk?1)函數(shù)用來從Lk?1中刪除包含項次數(shù)小于k?1的項集，從而減少k-項候選集的數(shù)目，可以解決“候選項集瓶頸”問題，也提高了算法的時間效率。

(5) 本文算法中，Candidate_gen(Lk′?1)函數(shù)主要用于生成k-項候選集，它分別調(diào)用jion(l1,l2)和has_infrequent_subset(c,Lk?1)兩個函數(shù)。其中jion(l1,l2)函數(shù)用于實現(xiàn)頻繁項集的連接及求兩個事務(wù)集合的交集(推論2)；has_infrequent_subset(c,Lk?1)函數(shù)用于判斷一個k-項候選集的k?1子集之中是否有非頻繁項集，如果有則該k-項候選集被刪除，否則該k-項候選集被加入到k-項候選集集合之中(推論1)。

5 結(jié) 束 語

本文針對高維文本特征空間中僅以最小支持度閾值為約束條件產(chǎn)生的頻繁項集規(guī)模難以確定的不足，在分析NApriori和IntvMatrix兩個經(jīng)典算法的基礎(chǔ)上，提出了一種基于倒排表和集合的TOP-N最頻繁項集算法。通過分析和實驗表明，無論是在規(guī)則有效率方面，還是時間效率方面，本文算法都優(yōu)于NApriori算法和IntvMatrix算法，使本文算法在文本關(guān)聯(lián)規(guī)則挖掘中有一定的應(yīng)用價值。

[1] 陳曉云. 文本挖掘若干關(guān)鍵技術(shù)研究[D]. 上海: 復(fù)旦大學(xué), 2005.CHEN Xiao-Yun. Research on several key technology of text mining[D]. Shanghai: Fudan University, 2005.

[2] HAN Jia-wei, PEI Jian, YIN Yi-wen. Mining frequent patterns without candidate generation:a frequent pattern tree approach[J]. Data Mining and Knowledge Discovery, 2004,8(1): 53-87.

[3] FU A W C, KWONG R W W , TANG J. MiningN-most interesting itemsets[C]//Proceedings of 2000 ISMIS. Berlin:Springer, 2000: 59-67.

[4] BODON F. A survey on frequent itemset mining[C]//Proceedings of the ACM SIGKDD Workshop on OSDM ’04.Chicago, USA: [s.n.], 2004: 523-531.

[5] 陳曉云, 胡運發(fā).N個最頻繁項集挖掘算法[J]. 模式識別與人工智能, 2007, 20(4): 512-518.CHEN Xiao-yun, HU Yun-fa. Mining algorithms ofN-most frequent itemsets[J]. PR & AI, 2007, 20(4): 512-518.

[6] HAJJ M E, ZAIANE O R. Inverted matrix: Efficient discovery of frequent items in large datasets in the context of interactive mining[C]//2003 Int’1 Conf on Data Mining and Knowledge Discovery (ACM SIGKDD). California,USA: [s.n.], 2003: 109-118.

[7] HAJJ M E, ZAIANE O R. Non recursive generation of frequent k-itemsets from frequent pattern tree representations[C]//Proceedings of 5th International Conference on Data Warehousing and Knowledge Discovery.Melbourne: Australia, 2003: 371-380.

[8] RACZ B. NonordFP：an FP-growth variation without rebuilding the FP-tree[C]//Proceedings of the IEEE ICDM Workshop on FIMI ’04. Brighton, UK: [s.n.], 2004:1089-1097.

[9] LIU Gui-mei, LU Hong-jun. AFOPT: an efficient implemefitation of pattern growth approach[C]//Proceedings of the IEEE ICDM Workshop on FIMI ’04. Brighton, UK:[s.n.], 2004: 2056-2067.

[10] 陳 耿, 朱玉全, 楊鶴標(biāo), 等. 關(guān)聯(lián)規(guī)則挖掘中若干關(guān)鍵技術(shù)的研究[J]. 計算機(jī)研究與發(fā)展, 2005, 42(10):1785-1789.CHEN Geng, ZHU Yu-quan,Yang He-biao. Study of some key techniques in mining association rule[J]. Journa1 of Computer Research and Development, 2005, 42(10):1785-1789.

[11] 陳曉云, 陳 祎, 王 雷, 等．基于分類規(guī)則樹的頻繁模式文本分類[J]. 軟件學(xué)報, 2006, 17(5): 1017-1025.CHEN Xiao-yun, CHEN Wei, WANG Lei, et a1. Text categorization based on classification rules tree by frequent patterns[J]. Journal of Software, 2006, 17(5): 1017-l025.

[12] WU Fan, CHIANG S W, LINJ R. A new approach to mine frequent patterns using item-transformation methods[J].Information Systems, 2007, 32(7): 1056-1072.

[13] 戰(zhàn)力強, 劉大昕. 頻繁項集快速挖掘算法研究[J]. 哈爾濱工程大學(xué)學(xué)報, 2008, 29(3): 266-271.ZHAN Li-qiang, LIU Da-xin. Study on fast algorithm of frequent item-set mining [J]. Journal of Harbin Engineering University, 2008, 29(3): 266-271.

[14] 田 宏, 董愛杰. 基于向量矩陣的頻繁項集挖掘算法[J].大連交通大學(xué)學(xué)報, 2008, 29(3): 74-77.TIAN Hong, DONG Ai-jie. A frequent itemsets mining algorithm based on vector matrix[J]. Journal of Dalian Jiaotong University, 2008, 29(3): 74-77.

[15] 張忠平, 李 巖, 楊 靜. 基于矩陣的頻繁項集挖掘算法[J]. 計算機(jī)工程, 2009, 35(1): 84-86.ZHANG Zhong-ping, LI Yan, YANG Jing. Frequent itemsets mining algorithm based on matrix[J]. Computer Engineering, 2009, 35(1): 84-86.