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

鄧靖秋

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

0 引言

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

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

1 頻繁項(xiàng)集挖掘算法

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

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

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

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

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

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

1.2 FP-growth算法

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

1.2.1 構(gòu)建FP 樹

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

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

1.2.2 挖掘FP 樹

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

1.3 Eclat算法

根據(jù)文獻(xiàn)[15]可知，Apriori 算法和FP-growth 算法都是以事務(wù)-項(xiàng)的格式，定義為：{TID:itemset}，一條事務(wù)對應(yīng)一個(gè)或多個(gè)項(xiàng)，這種數(shù)據(jù)格式稱為水平格式。而Eclat 算法則采用項(xiàng)-事務(wù)數(shù)據(jù)格式表示，一般定義為：{item:TIDset}，其中item 是項(xiàng)的名稱，TIDset 是包含item 的事務(wù)標(biāo)識(shí)符的集合，這種數(shù)據(jù)格式被稱作垂直格式的數(shù)據(jù)集合。同時(shí)Eclat 中還加入了倒排的思想，將事務(wù)中的項(xiàng)item 作為key，每個(gè)項(xiàng)對應(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)換后的倒排表可加快頻繁項(xiàng)集的生成速度，轉(zhuǎn)換后的數(shù)據(jù)庫D 如表4。

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

接著從k=1 開始，可計(jì)算得到頻繁1-項(xiàng)集如表5所示。

表5 頻繁1-項(xiàng)集

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

表6 頻繁2-項(xiàng)集

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

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

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

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