工業(yè)大數(shù)據(jù)背景下頻繁項集挖掘算法對比分析及研究展望

鄧靖秋

（四川大學(xué)計算機學(xué)院，成都610065）

0 引言

數(shù)據(jù)庫中的知識發(fā)現(xiàn)（Knowledge Discovery in Databases，KDD）是指利用機器學(xué)習(xí)、模式識別、統(tǒng)計等領(lǐng)域的方法從大量數(shù)據(jù)中提取知識[1]，而這些知識并不是數(shù)據(jù)庫結(jié)構(gòu)中明確可用的，需要通過某些特殊處理后再進行提取。現(xiàn)今比較具有代表性的四種現(xiàn)代數(shù)據(jù)挖掘技術(shù)為：粗糙集理論（RST）、關(guān)聯(lián)規(guī)則挖掘（ARM）、新興模式挖掘（EP）以及形式概念分析（FCA）。這些方法的主要優(yōu)點之一是它們的描述能力，即當用于派生規(guī)則時，在結(jié)構(gòu)-活動關(guān)系中便具有了明確的物理意義。一般地進行大數(shù)據(jù)挖掘常用的關(guān)聯(lián)規(guī)則挖掘技術(shù)，根據(jù)文獻[2]描述為，假設(shè)有一個數(shù)據(jù)庫D，第一步找出支持度大于或等于最小支持度（minsup）閾值的全部項集，從而得到所有的頻繁項集；第二步通過從滿足最小支持度閾值找出的頻繁項集中挖掘大于或等于最小置信度（minconf）閾值的關(guān)聯(lián)規(guī)則，從而得到強關(guān)聯(lián)規(guī)則。其中滿足最小支持度保證了挖掘的規(guī)則具有重要性，而滿足最小置信度則保證挖掘規(guī)則的可靠性。

大數(shù)據(jù)（Big Data）指的是大容量的、復(fù)雜的、不斷增長的、具有多個自主來源的數(shù)據(jù)集。隨著網(wǎng)絡(luò)、數(shù)據(jù)存儲和數(shù)據(jù)采集能力的快速發(fā)展，大數(shù)據(jù)在物理、生物和生物醫(yī)學(xué)等各科學(xué)工程領(lǐng)域迅速擴張，數(shù)據(jù)量呈指數(shù)增長[3-4]。圍繞工業(yè)大數(shù)據(jù)研究并發(fā)現(xiàn)其內(nèi)在價值變得尤為重要，現(xiàn)今工業(yè)大數(shù)據(jù)的5V 特性主要體現(xiàn)在：大容量（Volume）、多樣性（Variety）、速度（Velocity）、價值（Value）、真實性（Veracity）[5]，盡管數(shù)據(jù)量極其豐富，但因為缺少有效的挖掘技術(shù)和分析工具從中提取有用的東西，工業(yè)大數(shù)據(jù)的內(nèi)在價值現(xiàn)階段也還未得到有效的體現(xiàn)。

1 頻繁項集挖掘算法

考慮一個項的集合I。每條事務(wù)都有它唯一的標記符號，這個標記符記為TID，在給定的一個數(shù)據(jù)庫表中，表中每一行對應(yīng)交易中的一條事務(wù)，對事務(wù)T 來說，X 表示一個項集，如果有X?T，則表示事務(wù)T 中包含一個為X 的項。項集的支持度計數(shù)為發(fā)生該事件的事務(wù)數(shù)，即事務(wù)A、B 同時出現(xiàn)的頻率，用數(shù)學(xué)公式表示為：Support（A==>B）=P（A n B），支持度（sup）是某事務(wù)所占比重重要性的衡量，而頻繁項集為支持度至少滿足某個閾值的所有項集。假設(shè)有如下數(shù)據(jù)庫S 如表1，minsup 值人為設(shè)定為4。

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

則根據(jù)設(shè)定的最小支持度閾值4，統(tǒng)計數(shù)據(jù)庫S 中各項支持度，過濾掉不滿足sup=4 的事務(wù)項并按照支持度大小降序排序，得到如表2 滿足的頻繁1-項集，更新后的事務(wù)數(shù)據(jù)庫S 如表2 所示。

表2 更新后數(shù)據(jù)庫S

對于現(xiàn)今頻繁項集挖掘算法來說，其開銷主要在于產(chǎn)生所需的所有頻繁項集，一般的挖掘頻繁項算法包括：Apriori、FP-growth、Eclat、DHP、MBS、HBS、DIC[6]、Clique、dEclat、MaxEclat[7]等算法，其中文獻[8]中提到的DHP 算法，利用Hash 修剪技術(shù)解決了對于在生成頻繁k-項集時遇到的性能不佳問題，通過減少數(shù)據(jù)庫事務(wù)的數(shù)據(jù)量，從而更高效地生成頻繁項目集；文獻[9]中提出的兩種本文提出的兩種新的算法MBS 和HBS 采用逆向思維通過有效地發(fā)現(xiàn)非頻繁項之間的關(guān)聯(lián)規(guī)則，同時也可以有效地挖掘有限長度頻繁項之間的關(guān)聯(lián)規(guī)則，兩種算法也只需要遍歷數(shù)據(jù)庫兩次，并且利用剪枝函數(shù)interest（X,Y）來顯著減少搜索空間，使用interest度量correlation 相關(guān)性（X,Y）和CPIR（X,Y），從中提取感興趣的規(guī)則；文獻[10]提出一種最小生成樹的聚類算法Partition，相似記錄被聚合到包含K 個最小記錄的組中，對于具有明顯聚類效應(yīng)的數(shù)據(jù)可以顯著降低數(shù)據(jù)的信息損失從而加速k-項集的尋找過程；文獻[11]提出一種在圖形處理單元上并行化求解區(qū)間圖最大組合的算法Clique；文獻[12]提出了一種在對傳統(tǒng)Elcat算法基礎(chǔ)上，通過優(yōu)化數(shù)據(jù)垂直結(jié)構(gòu)，減輕項集迭代歸一負擔(dān)的dEclat 算法。據(jù)統(tǒng)計，現(xiàn)今采用的大部分頻繁項集的挖掘算法中，Apriori 算法、FP-growth 算法、Eclat 算法仍是在求解關(guān)聯(lián)規(guī)則挖掘問題上較為經(jīng)典的三種算法。

1.1 Apriori算法

Apriori 算法是層次算法的經(jīng)典算法之一，是Agrawal 和Srikant 于1994 年提出的，其主要是針對布爾關(guān)聯(lián)規(guī)則的挖掘算法[13]，它作為層次算法的代表算法，采用一層一層搜索的策略，利用候選項集作為中間工廠，通過頻繁k 項集生成頻繁k+1 項集。Apriori 針對挖掘布爾型數(shù)據(jù)挖掘頻繁項集，利用自底向上的方法，從挖掘頻繁1-項集作為起點，根據(jù)上一層產(chǎn)生的序列逐步找出高階頻繁項集的過程。

該算法的基本流程是：第一次掃描給定數(shù)據(jù)庫，記錄每條事務(wù)中每個項出現(xiàn)的頻數(shù)，將頻數(shù)低于最小支持度閾值的單項集進行刪除處理后整合剩下所有項集，產(chǎn)生頻繁1-項集。在頻繁1-項集的基礎(chǔ)上進行連接操作生成2-候選項集，再對其修剪操作得到頻繁2-項集，迭代上述過程直到不再產(chǎn)生更高階的頻繁項集即可結(jié)束，此時結(jié)果即挖掘出的所有頻繁項集。

1.2 FP-growth算法

FP-growth 算法是Han 等人提出來的一種從事務(wù)集中挖掘頻繁項集而不產(chǎn)生候選集的算法[14]。算法思路采用一棵FP 樹存儲數(shù)據(jù)庫中的事務(wù)，對數(shù)據(jù)庫掃描兩次，在整個挖掘過程中采用遞歸策略迭代挖掘。算法過程大致分為兩步：第一步，構(gòu)造一顆FP 樹；第二步，對第一步中構(gòu)造出的FP 樹進行遞歸操作，得到所有的頻繁項結(jié)果集。

1.2.1 構(gòu)建FP 樹

（1）第一次掃描數(shù)據(jù)庫，首先統(tǒng)計數(shù)據(jù)集中每個元素出現(xiàn)的頻數(shù)，即計算每個元素支持度，剔除元素支持度小于minsup 值的元素，接著將數(shù)據(jù)集中的每條記錄按照支持度大小進行降序排序，剩下的這些元素即為頻繁1-項集列表F-List；

（2）對更新后的數(shù)據(jù)庫第二次掃描，記錄數(shù)據(jù)庫中每條事務(wù)出現(xiàn)的項的順序，根據(jù)記錄結(jié)果創(chuàng)建一顆FP樹，設(shè)樹的根結(jié)點為null，若待增加的記錄與FP 樹中的路徑相同時，只用更新該元素對應(yīng)的頻數(shù)，即將該元素結(jié)點頻數(shù)相應(yīng)加1，若待增加的記錄與FP 樹存在不相同時，則將該項添加到FP 樹的一個分支當中，即新增一個新的結(jié)點。

1.2.2 挖掘FP 樹

通過得到的FP 樹，采用自底向上遞歸的思想，對每一個頻繁項進行逐個挖掘，首先得到頻繁項的前綴路徑，將前綴路徑看作新的數(shù)據(jù)集構(gòu)建前綴路徑的條件模式基（cpb），接著對該條件模式基中的某個頻繁項又繼續(xù)獲得其前綴路徑并構(gòu)建新的條件模式基，以此不停迭代，直到條件模式基（cpb）中只剩下一個頻繁項為止。

1.3 Eclat算法

根據(jù)文獻[15]可知，Apriori 算法和FP-growth 算法都是以事務(wù)-項的格式，定義為：{TID:itemset}，一條事務(wù)對應(yīng)一個或多個項，這種數(shù)據(jù)格式稱為水平格式。而Eclat 算法則采用項-事務(wù)數(shù)據(jù)格式表示，一般定義為：{item:TIDset}，其中item 是項的名稱，TIDset 是包含item 的事務(wù)標識符的集合，這種數(shù)據(jù)格式被稱作垂直格式的數(shù)據(jù)集合。同時Eclat 中還加入了倒排的思想，將事務(wù)中的項item 作為key，每個項對應(yīng)的事務(wù)TIDset作為value，數(shù)據(jù)表示清晰，算法執(zhí)行過程中只需要對數(shù)據(jù)庫掃描一次即可。

Eclat 算法基本流程表示為：通過掃描一次數(shù)據(jù)庫改變數(shù)據(jù)格式。假設(shè)給定水平格式的數(shù)據(jù)庫D，如表3。

表3 數(shù)據(jù)格式為水平結(jié)構(gòu)的數(shù)據(jù)庫D

轉(zhuǎn)換數(shù)據(jù)格式為垂直格式，通過轉(zhuǎn)換后的倒排表可加快頻繁項集的生成速度，轉(zhuǎn)換后的數(shù)據(jù)庫D 如表4。

表4 數(shù)據(jù)格式為垂直結(jié)構(gòu)的更改后的數(shù)據(jù)庫D

接著從k=1 開始，可計算得到頻繁1-項集如表5所示。

表5 頻繁1-項集

通過取得頻繁k-項集的TIDset 事務(wù)集的交集計算對應(yīng)頻繁（k+1）-項集的TIDset 事務(wù)集，每次k 的值增加1，則由頻繁1-項集構(gòu)造生成的頻繁2-項集結(jié)果如表6 所示：

表6 頻繁2-項集

繼續(xù)由頻繁2-項集構(gòu)造頻繁3-項集，頻繁3-項集構(gòu)造頻繁4-項集，…，頻繁k-項集構(gòu)造頻繁k+1 項集（k為正整數(shù)），直到最后結(jié)果不再產(chǎn)生頻繁k-項集即可。

2 經(jīng)典挖掘算法對比分析

通過對現(xiàn)今使用頻率較高的三種經(jīng)典頻繁項集挖掘算法原理介紹，對于各自優(yōu)缺點做如下對比分析，如表7。

表7 三類經(jīng)典挖掘項集算法比較

3 基于工業(yè)大數(shù)據(jù)下挖掘關(guān)聯(lián)信息分析研究

隨著人工智能的發(fā)展，基于對工業(yè)大數(shù)據(jù)關(guān)聯(lián)信息的挖掘成為廣大科研人員研究的熱點之一[16]，其主要任務(wù)是挖掘大數(shù)據(jù)集中潛在的有價值的關(guān)聯(lián)關(guān)系以及動態(tài)數(shù)據(jù)中規(guī)則的變化規(guī)律，從而可以利用得到的知識反作用于數(shù)據(jù)，為事件發(fā)生做一些有效的預(yù)測和推斷，這一舉措在很多行業(yè)和領(lǐng)域都有著重大的研究意義和應(yīng)用前景，例如工業(yè)大數(shù)據(jù)背景下，對機械生產(chǎn)質(zhì)量管理問題的研究，通過挖掘生產(chǎn)中有關(guān)質(zhì)量問題的關(guān)聯(lián)信息，逆向補抓作用生產(chǎn)過程，有效地進行質(zhì)量監(jiān)控和管理，生產(chǎn)更多合格產(chǎn)品，從而提高生產(chǎn)效率。但在海量數(shù)據(jù)產(chǎn)生的今天，對于傳統(tǒng)單機的關(guān)聯(lián)規(guī)則挖掘算法在頻繁項集挖掘步驟上耗時多且挖掘出的項集規(guī)模過于龐大，可能導(dǎo)致后期的關(guān)聯(lián)規(guī)則挖掘無法進行。為解決這一問題，考慮結(jié)合現(xiàn)今通用的大數(shù)據(jù)框架，將傳統(tǒng)的頻繁項集挖掘算法移植運用到大數(shù)據(jù)并行化平臺，利用并行的思想進行海量數(shù)據(jù)挖掘，同時對經(jīng)典挖掘算法進行相應(yīng)移植后的優(yōu)化，提取出定量的有規(guī)律有意義的數(shù)據(jù)信息，有效提高大數(shù)據(jù)下海量數(shù)據(jù)挖掘的效率。

4 結(jié)語

基于工業(yè)大數(shù)據(jù)背景下的數(shù)據(jù)之間關(guān)聯(lián)信息的挖掘，經(jīng)典的三種挖掘算法在各自算法原理上都有一定的局限性，本文對其進行了特點分析，同時也對在工業(yè)大數(shù)據(jù)背景下如何快速、高效挖掘數(shù)據(jù)之間信息進行研究分析。通過減少候選項集數(shù)量，優(yōu)化均衡分組，結(jié)合大數(shù)據(jù)框架并行挖掘從而得以實現(xiàn)。

本文研究的算法為傳統(tǒng)單機頻繁項集挖掘算法，但隨著現(xiàn)今大數(shù)據(jù)時代的不斷發(fā)展，數(shù)據(jù)量不斷地擴展，產(chǎn)生的關(guān)聯(lián)規(guī)則也隨之增多，因此未來研究工作地重點可能主要包括：

（1）對于算法中生成大量候選項集的問題，采用對原始數(shù)據(jù)進行壓縮的方法，如何對原始數(shù)據(jù)進行高效的壓縮操作是未來研究的難點之一；

（2）設(shè)計更加優(yōu)化的挖掘算法，將其移植到并行的大數(shù)據(jù)平臺上，考慮移植后算法分組策略問題，從而有效解決負載均衡問題；

（3）現(xiàn)今大部分挖掘算法采用以挖掘正的關(guān)聯(lián)規(guī)則的思路進行挖掘，這將會產(chǎn)生過多的結(jié)果集，從實際工程項目出發(fā)，正確衡量正負結(jié)果比，當挖掘的正規(guī)則結(jié)果集過于龐大時，考慮從挖掘負的關(guān)聯(lián)規(guī)則入手，將挖掘少量負關(guān)聯(lián)規(guī)則反作用于正關(guān)聯(lián)規(guī)則得到定量的規(guī)則結(jié)果集，同時如何對結(jié)果集進行劃分歸類也是一大難關(guān)；

（4）最小支持度minsup 閾值的設(shè)定存在一定的人為影響性，設(shè)計一種能夠通過針對不同數(shù)據(jù)規(guī)模自動生成最優(yōu)最小支持度閾值的算法幫助在規(guī)則挖掘中等到更有效的信息；

（5）除了基本數(shù)據(jù)模式的挖掘算法研究之外，多層次的、多維度的挖掘算法也需要移植到并行化數(shù)據(jù)平臺進行實行，同時現(xiàn)今的挖掘的需求不僅僅局限于對文本數(shù)據(jù)集的挖掘，視頻、圖像、音頻等數(shù)據(jù)類型也將會成為今后關(guān)聯(lián)挖掘的研究內(nèi)容，如何對這種繁瑣的數(shù)據(jù)類型進行關(guān)聯(lián)挖掘也將會成為一項重大的挑戰(zhàn)。