基于上卷和下鉆技術的關聯規則挖掘與應用

蘭占江，張春生，林慶明，恩 英

（1.內蒙古民族大學計算機科學與技術學院，內蒙古 通遼 028043；2.內蒙古民族大學蒙醫藥學院，內蒙古 通遼 028043）

隨著信息與通信技術的飛速發展，產生的數據越來越多，全球的數據量呈爆炸式猛漲。各行各業都積累了大量的數據，人類已經進入了大數據時代，面對海量并且復雜的數據，人們日益發現這些數據蘊含著對人類有用的信息，是人類經濟社會發展的重要財富，有效的數據分析與挖掘將推動國家、企業乃至整個社會的高效、可持續發展。然而面對海量復雜的數據，如何能從中更快更準確地發現有價值的信息，成為當務之急。目前，影響大數據處理效率主要有3個因素：樣本數量、特征數量、特征值數量［1］。其中，關于樣本數量能否約減目前還存在爭議，統計學領域的專家一般認為樣本數量可以約減，而大數據領域的專家一般不支持樣本數量約減，他們認為一旦約減了樣本數量就會導致大量數據缺失，可能失去大數據概念本身，同時也可能造成信息缺失；對于屬性值的數量同樣影響大數據處理效率，一般要進行數據平整，但對數據的平整過大會降低挖掘精度；特征數量以指數級影響大數據處理的時間效率，對大數據特征數據量進行優化具有一定的潛力，但特征約減也同樣影響挖掘精度。為提高大數據分析處理的效率問題，大部分的研究內容都是從改變大數據處理的系統架構、優化算法效率、數據預處理出發的。系統采用分布式架構，分散數據存儲，處理數據采用并行的方式進行，適應了大數據處理要求，提高了大數據挖掘的安全性和效率［2-5］；通過改變索引結構，進而提高數據處理效率［6］；采用不同的數據預處理技術，極大地減少數據分析時的處理量，提高數據分析處理的效率［7］。總的來說，都取得了頗多的成果，但無論是改變索引結構還是數據預處理，都是從不同的角度降低原始數據包含的信息量，從而提高挖掘的效率，也降低數據挖掘所產生的有效關聯規則的數量，也可能在一定程度上損失挖掘結果的精度，這一點已經引起人們的關注，為此，提出了基于上卷和下鉆技術的關聯規則挖掘。

文中提出的基于上卷和下鉆技術的關聯規則挖掘不同于簡單的關聯規則挖掘，上卷是將原始數據的屬性特征經過有經驗知識專家的指導，將其屬性特征進行合并得到上卷特征，從而在進行關聯規則挖掘時得到更多的關聯規則，提高數據挖掘的效率。下鉆是根據某一屬性的特征進行下鉆挖掘，使其得到的挖掘結果更為精確。

綜上所述，目前的關聯規則挖掘成果沒有在原始數據的基礎上進行屬性聚集，甚至是出現了屬性的約減，用挖掘的精度換取了挖掘的效率。筆者從原始數據出發，通過屬性的特征上卷，使特征的數量減少，進而提高挖掘的效率，通過對挖掘結果的分析，確定下鉆挖掘的目標，保證挖掘結果的精確性。

1 數據來源

本文的數據來源于《傳統蒙藥與方劑》一書中治療熱癥的方劑［8］，進行數據預處理和基于上卷和下鉆技術的關聯規則挖掘，書中收集了35個治療熱癥的方劑，涉及92種藥物和72種主治［9］。

2 關聯規則挖掘技術

數據挖掘技術是指從大量不規則的數據中挖掘出用戶感興趣的規則的過程。數據挖掘技術能為用戶提供規則支持，已經廣泛應用于人工智能、模式識別等領域。目前，根據功能可將數據挖掘主要分為關聯規則挖掘、聚類分析、偏差分析，而其中應用最廣泛和熱門的數據挖掘算法是Apriori關聯規則挖掘算法［10］。

數據挖掘技術的核心是關聯規則挖掘，關聯規則挖掘是從數據庫中發現隱藏在數據庫中對人們有用的數據項之間的內在關系，挖掘出的關聯規則可為預測提供依據。關聯規則的表現形式簡單，最早應用于零售業，在沃爾瑪超市的交易記錄中，理貨員發現一個不可思議的規則，30%~40%的年輕父親在購買尿布的同時購買啤酒，根據這條規則，超市將貨品的擺放進行調整，結果發現超市的銷售額上漲［11］。關聯規則挖掘主要是從大量的項集中找出不同項集之間的關聯。關聯規則的發現包含2個階段：尋找頻繁項集和生成關聯規則。第一階段，給出現的項集進行計數，每一個項稱為一個項集，如果出現次數大于最小支持度閾值，則該項集為頻繁項集；第二階段，將出現的頻繁項集生成關聯規則，其中，大于給定最小置信度閾值的稱為強關聯規則［12］。其中，支持度閾值和置信度閾值都由用戶定義，代表關聯產生關聯規則的約束。目前，關聯規則挖掘已得到廣泛應用，如農業、銀行、醫療等領域。

在眾多的關聯規則挖掘算法中，Apriori 算法是最經典的算法，于1994年由AGRAWAL 等［13］提出，它使用廣度優先搜索技術，是目前應用最廣的關聯規則挖掘算法。但Apriori 算法也存在許多缺點，例如，在生成頻繁項集時會產生大量的候選項集，關聯規則算法所挖掘出來的規則數會隨之呈指數增長，并多次掃描數據庫，掃描次數等于最大頻繁項目集的長度，效率較低。因此，之后許多成果在圍繞Apriori 算法的基礎上進行研究，提出了若干種改進算法，其中HAN 等［14］提出的FP-growth 算法，其中FP 代表Frequent Pattern，它使用遞歸處理方式，不產生候選項集，只需掃描兩次數據庫，第一次掃描得到頻繁項集，第二次掃描過濾掉非頻繁項集，并且生成FP樹；PARK等［15］提出的DHP算法，它使用哈希技術，在第一次掃描數據庫時同時產生哈希表，有效提高了運算速度。筆者采用Apriori經典關聯規則挖掘算法，用于挖掘頻繁項集并生成關聯規則。引入支持度（Support）和置信度（Confidence）2個概念。

支持度是用來指所有事務在項集中出現的頻率，計算公式如下：

支持度表示A和B同時出現的概率，反映了關聯規則的重要性。

置信度是指A和B同時出現概率占A出現概率的比值，計算公式如下：

置信度是關聯規則準確性的度量。其中，同時滿足最小支持度和最小置信度的規則成為強關聯規則，Apriori 算法用廣度優先搜索技術，逐層搜索的迭代方式，通過連接和剪枝2個步驟，由頻繁K-項集逐步搜索直到生成頻繁（K+1）-項集，找到最大頻繁項集，在尋找頻繁項集時利用Apriori的一個重要性質，頻繁項集的所有非空子集都必定是頻繁的，非頻繁項集的所有父集都是非頻繁的［16］。

3 上卷技術和下鉆技術

特征的上卷和下鉆是基于聯機分析處理（OLAP）的技術，OLAP 最早于1993 年由關系數據庫之父E.F.CODD 提出［17］，OLAP 源于OLTP（聯機事務處理），OLAP 的實現以數據倉庫為平臺，是針對數據倉庫的數據立方體的分析技術，是數據倉庫系統中的重要組成部分，為決策者和高級管理人員做決策提供支持［18］。隨著數據挖掘技術的發展，在2003 年左右OLAP 與數據挖掘技術結合，提取數據立方體的特征的研究出現［19］，因此，OLAP 與關聯規則挖掘的有效結合能夠達到擴展挖掘功能，提高挖掘效率的目的［20-21］。隨著大數據時代的到來，特征的上卷和下鉆技術應用于大數據領域的數據挖掘具有一定的優勢和潛力。筆者將特征的上卷和下鉆技術應用于大數據的關聯規則挖掘中，特征上卷使得特征的數量減少，因此，挖掘效率會提高，同時挖掘的關聯規則數量更多，基于特征的下鉆挖掘使得挖掘到的關聯規則更精確，用戶對其更感興趣。

3.1 上卷特征

定義1 上卷特征：將具有一定相同類別屬性的特征聚集為更高層次的類別特征，這個新特征定義為上卷特征。

RU_特征名={R1，R2，...，Rk，RU_R1，RU_R2，...，RU_Rm }

其中，RU_特征名為上卷特征名，它由若干原始特征Ri（i=1，...，k）或若干上卷特征RU_Rj（j=1，...，m）構成，也可以全部由原始特征Ri（i=1，...，k）或上卷特征RU_Rj（j=1，...，m）構成。

例如：RU_面類={ 面包，饅頭，大餅，面條}；RU_食品={ RU_面類，RU_肉類，RU_米類}

3.2 下鉆特征

定義2 下鉆特征：上卷特征的組成部分稱為下鉆特征。例如：{ 面包，饅頭，大餅，面條} 是RU_面類的下鉆特征；{ RU_面類，RU_肉類，RU_米類}是RU_食品的下鉆特征。

3.3 特征層次樹

特征層次樹的構建作為特征的上卷和下鉆的前提條件，特征層次樹一般有上卷特征和原始特征構成，上卷特征作為特征層次樹的中間結點和根節點，原始特征作為特征層次樹的葉子節點，例如由上面的上卷特征和下鉆特征構建的特征層次樹見圖1。

圖1 特征層次樹Fig. 1 Feature hierarchy tree

在現實生活中的樣本集不一定具有明顯的層次特征，往往原始數據都是雜亂無章的，這就需要在特征上卷和下鉆之前進行合理的特征預處理，使特征具有明顯的類別，這樣才能夠實現上卷。而特征的上卷需要在專家或者有相關領域知識的人指導下進行，特別是在特征層次的選擇時，如果上卷的粒度過大，則挖掘產生的結果過于籠統，使得挖掘的準確性難以保證；如果挖掘的粒度過小，則挖掘產生的結果過于詳細，起不到通過特征上卷使得挖掘效率提高的目的，因此，對于特征層次的選擇一定要具有可預見性，須在領域專家的參與下進行評估。

4 上卷和下鉆技術的關聯規則挖掘在蒙醫熱癥數據中的應用

關聯規則挖掘技術日益成熟，已經在各個領域得到了很好的應用和發展，對各個領域的發展都有一定的推動作用，特別是在醫學領域的研究取得了可喜的成績，其中，在中醫方劑方面通過關聯規則挖掘發現了隱藏在數據內部的隱規則，為中醫臨床和中醫藥研發具有一定的指導作用［22］，并且提高了診療的智能化水平和中醫藥的研發效率。蒙醫是我國醫學的重要組成部分，其作為我國民族醫學的典范，是蒙古族人民長期同疾病作斗爭的重要依據，是我國民族醫學的瑰寶，具有完整的理論依據和鮮明的民族特色。目前，關聯規則挖掘在中醫研究領域十分火熱，但是在蒙醫領域的關聯規則挖掘較少，因此，筆者采用蒙醫熱癥作為實驗數據，為蒙醫臨床應用提供可靠的決策指導和提高決策規則生成的時間效率。

4.1 蒙醫熱癥數據特征上卷

蒙醫熱癥是指由血、希拉過盛而引起的急性熱病的總稱［23］。熱癥具有發病突然、類型多變等特點，治療熱癥的方劑大多以寒涼性藥物為主。熱癥共有72種主治疾病，根據蒙醫藥專家的指導以及查閱資料，將72種主治按照蒙醫6種基本疾病癥狀理論［24-25］進行上卷得到二級主治18種，再將二級主治根據6種基本疾病癥狀理論進行上卷得到一級主治7種。熱癥主治三級上卷見表1。

表1 熱癥主治三級上卷Tab. 1 Level III Volume I of indications of heat syndrome

4.2 基于目標的下鉆挖掘

經過反復探究，盡可能保證實驗結果的準確性，采用較高的支持度和置信度，實驗采用置信度70%，3種支持度40%、35%、30%，利用經典關聯規則挖掘的Apriori算法對熱癥數據的72種主治和藥物分別進行3個級別主治的關聯規則挖掘。支持度采用40%的主治與藥物挖掘結果見表2，支持度采用35%的主治與藥物挖掘結果見表3，支持度采用30%的主治與藥物挖掘結果見表4。

表2 支持度40%主治與藥物關聯規則挖掘結果Tab. 2 40% support：the results of mining association rules between main symptoms and drugs

表3 支持度35%主治與藥物關聯規則挖掘結果Tab. 3 35% support：the results of mining association rules between main symptoms and drugs

表4 支持度30%主治與藥物關聯規則挖掘結果Tab. 4 30% support：the results of mining association rules between main symptoms and drugs

4.3 實驗結果分析

上述3 組實驗中每組采用相同支持度和置信度進行Apriori關聯規則挖掘，從挖掘結果來看，通過對熱癥主治屬性進行三級上卷后，可以看出屬性上卷時得到的頻繁項集數量和關聯規則數量有明顯的提升，使得在下鉆挖掘時得到的關聯規則精度更高，更有利于指導決策，同時，挖掘效率也有所提高，達到了上卷下鉆技術的目的，提高了挖掘效率，也保證了挖掘結果的精度。在置信度為70%，支持度分別為40%、35%、30%時對三級主治進行挖掘。當支持度為40%時，一級主治得到的最大頻繁項集為5 條，強關聯規則為1 條，二級主治得到的最大頻繁項集為3條，無強關聯規則，三級主治得到的最大頻繁項集為2 條，無強關聯規則。當支持度為35%時，一級主治得到的最大頻繁項集為9 條，強關聯規則為2 條；二級主治得到的最大頻繁項集為9 條，強關聯規則1 條；三級主治得到的最大頻繁項集為4 條，無強關聯規則。當支持度為30%時，一級主治得到的最大頻繁項集為15條，強關聯規則為4條；二級主治得到的最大頻繁項集為14條，強關聯規則2條；三級主治得到的最大頻繁項集為5條，無強關聯規則。得到的頻繁項集數量變化見圖2，得到的關聯規則數量變化見圖3，得到生成規則所用時間變化見圖4。

圖2 頻繁項集數量變化Fig. 2 The number of frequent item sets changes

圖3 關聯規則數量變化Fig. 3 Change in the number of association rules

圖4 生成規則所用時間變化Fig. 4 Change in time taken to generate rules

5 結束語

為了提高大數據處理的效率問題，同時保證挖掘結果的精度，在Apriori關聯規則挖掘的基礎上引入了上卷和下鉆技術，由于符合上卷下鉆技術的數據集有限，因此，筆者首先以蒙醫藥熱癥數據為例，通過屬性上卷實現了屬性約簡，提高了挖掘效率，通過基于目標的下鉆挖掘，得到的頻繁項集數量和關聯規則數量增加，保證挖掘結果的精度，更好地挖掘數據背后隱藏的有價值信息，實現信息價值的最大化，也為基于上卷和下鉆技術的大數據處理提供了參考。今后可將上卷下鉆技術應用于決策樹挖掘，進一步驗證上卷下鉆技術對于提高數據處理效率和保證挖掘結果精度的可行性，使其在數據處理領域得到廣泛應用。