工業大數據背景下頻繁項集挖掘算法對比分析及研究展望

鄧靖秋

（四川大學計算機學院，成都610065）

0 引言

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

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

1 頻繁項集挖掘算法

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

表1 事務數據庫S

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

表2 更新后數據庫S

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

1.1 Apriori算法

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

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

1.2 FP-growth算法

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

1.2.1 構建FP 樹

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

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

1.2.2 挖掘FP 樹

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

1.3 Eclat算法

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

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

表3 數據格式為水平結構的數據庫D

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

表4 數據格式為垂直結構的更改后的數據庫D

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

表5 頻繁1-項集

通過取得頻繁k-項集的TIDset 事務集的交集計算對應頻繁（k+1）-項集的TIDset 事務集，每次k 的值增加1，則由頻繁1-項集構造生成的頻繁2-項集結果如表6 所示：

表6 頻繁2-項集

繼續由頻繁2-項集構造頻繁3-項集，頻繁3-項集構造頻繁4-項集，…，頻繁k-項集構造頻繁k+1 項集（k為正整數），直到最后結果不再產生頻繁k-項集即可。

2 經典挖掘算法對比分析

通過對現今使用頻率較高的三種經典頻繁項集挖掘算法原理介紹，對于各自優缺點做如下對比分析，如表7。

表7 三類經典挖掘項集算法比較

3 基于工業大數據下挖掘關聯信息分析研究

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

4 結語

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

本文研究的算法為傳統單機頻繁項集挖掘算法，但隨著現今大數據時代的不斷發展，數據量不斷地擴展，產生的關聯規則也隨之增多，因此未來研究工作地重點可能主要包括：

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

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

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

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

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