基於增量式關聯規則技術的動態大數據模型高效建立方法
2023-05-09 14:17:06
基於增量式關聯規則技術的動態大數據模型高效建立方法
【專利摘要】本發明公開了一種基於增量式關聯規則技術的動態大數據模型高效建立方法，包括以下步驟：步驟1：利用關聯規則挖掘算法為初始事務資料庫創建初始增量式頭表結構；步驟2：將增量式頭表結構轉化為基於內存的樹形結構，並以XML文檔形式保存在硬碟中；步驟3：掃描資料庫的新增內容，建立新增資料庫的增量式頭表並轉化為相應的XML文檔，將歷史XML文檔與新增資料庫的XML文檔合併構建更新後事務資料庫的XML文檔，然後即可利用更新的XML文檔來挖掘頻繁模式。
【專利說明】基於增量式關聯規則技術的動態大數據模型高效建立方法
【技術領域】
[0001]本發明涉及計算機數據挖掘領域，特別是一種適用於動態數據處理的基於增量式關聯規則技術的動態大數據模型高效建立方法。
【背景技術】
[0002]近年來，數據挖掘引起了信息產業界的極大關注，其主要原因是存在大量數據，可以廣泛使用，並且迫切需要將這些數據轉換成有用的信息和知識。數據挖掘能從大量的、不完全隨機的數據中提取隱含在其中的人們事先不知道的潛在有用信息。數據挖掘主要從數據泛化的角度進行數據總結。獲取的信息和知識可以廣泛用於各種應用，包括商務管理、生產控制、市場分析、工程設計和科學探索等。
[0003]Internet的迅猛發展將人類帶入了信息社會和網絡經濟時代，對企業發展和個人生活都產生了深刻的影響。雲計算、物聯網等新興服務促使人類社會的數據種類和規模正以前所未有的速度增長，大數據時代正式到來。數據從簡單的處理對象開始轉變為一種基礎性資源，如何更好的管理和利用大數據已經成為普遍關注的話題。面對龐大的資料庫，每次掃描挖掘都要耗費很長時間，特別是當大數據時代來臨，掃描代價過高，讓人無法容忍。另一方面事務資料庫一直在更新變化產生很多新的數據，如何在變化更新的資料庫上進行數據的高效挖掘也成為如今數據挖掘領域的研究熱點，因此需要高效的算法來挖掘數據關聯規則對數據進行有效的更新，維護和管理。
[0004]在數據挖掘處理理論和技術方面，工業界和學術界從不同的角度對服務推薦系統進行了大量研究。例如IBM、Oracle和Microsoft等公司從90年代初就成立了從事數據挖掘和知識發現方面的研究機構，並獲得了大量的研究成果。事務資料庫關聯規則挖掘算法大致可分為兩類:採用廣度遍歷解空間的方法和採用深度遍歷的方法。最典型的利用廣度遍歷的方法是R.Agrawal等在「Fast algorithms for miningassociation rules，，中提出的 Apriori 算法(Proc.20th Int.Conf.Very Large DataBases, VLDB.1215:487-499，1994)。Apriori算法是最有影響的挖掘布爾關聯規則頻繁項集的算法，其核心思想是利用候選集找到頻繁項集。J.Han等在「Mining frequent patternswithout candidate generation」中提出的FP_growth算法是採用深度遍歷的單層關聯規則挖掘算法(ACM SIGMOD Record.29 (2): 1—12，2000)。S.Rao 等人在 「 ImplementingImproved Algorithm Over APR10RI Data Mining Association Rule Algorithml，，中將Apriori算法的基礎上進行了改進,將Apriori算法與FP_growth算法結合起來,在資料庫更新時利用FP_gr0Wth算法挖掘新增資料庫，從而避免反覆掃描資料庫，降低了掃描代價(International Journal of Computer Science and Technology.3 (I)，2012)。隨著大數據時代的到來，事務資料庫越來越龐大，資料庫也在不斷變化更新，而資料庫的更新意味著有新的事務添加到資料庫中，在支持度和置信度閾值不變的條件下，關聯規則更新問題則可以簡化為尋找新的頻繁項目集，為了減少處理數據時所需的代價，因此需要更高效的數據挖掘模型來進行數據處理。
【發明內容】
[0005]本發明旨在克服現有技術中存在的不足，提供一種基於增量式關聯規則技術的動態大數據模型高效建立方法，利用增量式挖掘方法有效處理大規模資料庫的更新，減少計算資源浪費。
[0006]本發明公開了一種基於增量式關聯規則技術的動態大數據模型高效建立方法，包括以下步驟:
[0007]步驟1:利用關聯規則挖掘算法一Apriori算法為初始事務資料庫TDB創建初始增量式頭表結構XH-struct。
[0008]掃描事務資料庫兩次即可建立增量式的頭表結構XH-struct,當頻繁項讀入內存時，有相同首相的將通過指針域連結成一個隊列，XH中的指針域指向隊列的隊首。在XH-struct中，項目集按照字典順序進項排序，增量式頭表結構XH-struct的頭表記為XH，XH中的每一項都含有三個屬性:{ID，Sup, Poi}，ID是項目編號，Sup是項目的支持度，Poi是指針域，XH中包含了所有的項，即頻繁項和不頻繁項，因為當資料庫更新時，有新增資料庫，原來的不頻繁項可能變為頻繁項，所以在我們的方法中將其保留在頭表中。
[0009]步驟2:將增量式頭錶轉化為基於內存的樹形結構HT，再將其轉化為XML文檔形式，因此可將頭表結構從內存轉移到硬碟中。
[0010]頭表XH與相應的XML文檔是等價的，對它們的操作也是等價的。原有頭表XH中的每一項都作為樹形結 構HT根節點root的子節點記為項目節點item，每個子節點有兩個屬性:{Na, Sup}，Na是項目名，Sup是項目的支持度。每個子節點有若干個孩子節點具體的事務記為事務節點trans，事務節點的父親節點就是它們在增量式頭表結構中的首相。事務節點利用屬性TID來標記是資料庫中的哪個事務，最後事務節點的孩子節點即葉子節點保存了資料庫中的所有事務。頭表XH的前兩個屬性項目名Na和支持度Sup依然以屬性的形式保存在XML文檔中，XH中的隊列首指針在XML文檔中轉化為了項目節點的第一個子節點。
[0011 ] XML文檔類型定義(DTD)如下:
[0012]
[0013]
[0014]
[0015]
[0016]
[0017]
[0018]步驟3:當資料庫更新時，只需對新增資料庫Λ TDB進行掃描計算，建立新增資料庫的增量式頭表並轉化為相應的XML文檔，將歷史XML文檔與新增資料庫的XML文檔合併構建更新後事務資料庫的XML文檔；
[0019]對新增資料庫Λ TDB進行掃描計算，找到新增頻繁集，建立Λ TDB的相應XML文檔，然後將歷史XML文檔與Λ TDB的XML合併構建更新後事務資料庫(TDB+ Δ TDB)的XML文檔，然後即可利用更新的XML文檔來挖掘頻繁模式。
[0020]本發明利用關聯規則挖掘算法一Apriori算法為事務資料庫建立增量式頭表結構，將頭錶轉化為基於內存的樹形結構，再將其轉化為XML文檔形式保存於硬碟中，在事務資料庫更新時只需對新增資料庫進行掃描，建立新增資料庫的增量式頭表並轉化為相應的XML文檔，構建更新後資料庫的相應XML文檔，然後即可利用更新的XML文檔來挖掘頻繁模式。
[0021 ] 與現有技術相比，本發明的效果體現在:
[0022]I)在一般的關聯規則挖掘算法中，頭表是保存在內存的，當資料庫發生變化時，原有的頭表就無法使用了，通過將增量式頭表結構轉化為XML文檔保存於硬碟，即可重複利用。
[0023]2)在大數據時代，資料庫龐大且不斷更新，掃描代價過大，利用本文提出的方法只需對新增數據進行掃描，降低了掃描代價，提高了效率。
【專利附圖】
【附圖說明】
[0024]圖1本發明流程圖。
[0025]圖2為本發明實施例1中的初始資料庫的增量式頭表結構圖。
[0026]圖3為本發明實施例1中的樹形結構圖。
[0027]圖4為本發明實施例1中的新增資料庫的增量式頭表結構圖。
【具體實施方式】:
[0028]本發明提出了一種基於增量式關聯規則技術的動態大數據模型高效建立方法，包括以下步驟:步驟1:利用關聯規則挖掘算法一Apriori算法為初始事務資料庫TDB創建初始增量式頭表結構；步驟2:將增量式頭錶轉化為基於內存的樹形結構，再將其轉化為XML文檔形式，因此可將頭表結構從內存轉移到硬碟中；步驟3:當資料庫更新時，只需對新增資料庫進行掃描計算，建立新增資料庫的增量式頭表並轉化為相應的XML文檔，然後將歷史XML文檔與新增資料庫的XML合併構建更新後事務資料庫的XML文檔，然後即可利用更新的XML文檔來挖掘頻繁模式。
[0029]本發明首先利用關聯規則挖掘算法一Apriori算法為初始事務資料庫TDB創建初始增量式頭表結構。掃描事務資料庫兩次即可建立增量式的頭表結構XH-struct，當頻繁項讀入內存時，有相同首相的將通過指針域連結成一個隊列，XH中的指針域指向隊列的隊首。在XH-struct中，項目集按照字典順序進項排序，增量式頭表結構XH-struct的頭表記為XH，XH中包含了所有的項，即頻繁項和不頻繁項，因為當資料庫更新時，有新增資料庫，原來的不頻繁項可能變為頻繁項，所以在我們的方法中將其保留在頭表中。
[0030]將增量式頭錶轉化為基於內存的樹形結構HT，再將其轉化為XML文檔形式，因此可將頭表結構從內存轉移到硬碟中。頭表Μ與相應的XML文檔是等價的，對它們的操作也是等價的。原有頭表XH中的每一項都作為樹形結構HT根節點root的子節點記為項目節點item,每個子節點有若干個孩子節點具體的事務記為事務節點trans,事務節點的父親節點就是它們在增量式頭表結構中的首相。事務節點利用屬性TID來標記是資料庫中的哪個事務，最後事務節點的孩子節點即葉子節點保存了資料庫中的所有事務。頭表XH的前兩個屬性項目名Na和支持度Sup依然以屬性的形式保存在XML文檔中，XH中的隊列首指針在XML文檔中轉化為了項目節點的第一個子節點。[0031]當資料庫更新時，只需對新增資料庫Λ TDB進行掃描計算，找到新增頻繁集，建立Δ TDB的相應XML文檔，然後將歷史XML文檔與Λ TDB的XML合併構建更新後事務資料庫(TDB+ Δ TDB)的XML文檔，然後即可利用更新的XML文檔來挖掘頻繁模式。
[0032]實施例1
[0033]本實施例以一個事務資料庫的頻繁集挖掘為例，表1給出了事務資料庫，先根據Apriori算法的性質，為初始事務資料庫創建增量式頭表ΧΗ，如圖2所示。
[0034]表1.事務資料庫
[0035]
【權利要求】
1.一種基於增量式關聯規則技術的動態大數據模型高效建立方法，其特徵在於:包括以下步驟: 步驟1:利用關聯規則挖掘算法為初始事務資料庫TDB創建初始增量式頭表結構XH-struct ； 步驟2:將增量式頭錶轉化為基於內存的樹形結構HT，並以XML文檔形式保存在硬碟中； 步驟3:掃描資料庫的新增數據Λ TDB，建立新增資料庫的增量式頭表並轉化為相應的XML文檔，將歷史XML文檔與新增資料庫的XML文檔合併構建更新後事務資料庫的XML文檔，然後即可利用更新的XML文檔來挖掘頻繁模式。
2.根據權利要求1所述的基於增量式關聯規則技術的動態大數據模型高效建立方法，其特徵在於，步驟I中，設I = Ii1, i2,…im}是由m個不同項目組成的集合，事務資料庫TDB中的每個事務T是I中一組項目的集合，則:T ^ /，每個事務都有唯一的標識符TID。
3.根據權利要求2所述的基於增量式關聯規則技術的動態大數據模型高效建立方法，其特徵在於，步驟I中，利用關聯規則在事務資料庫中找出滿足用戶給定的最小支持度min_SUp和最小置信度min_cof的強關聯規則，項目集U在事務資料庫中出現的頻率是包含項目集U的事務數，?Φ0,記為項目集頻率F (U)，即為項目集的支持度，如果F (U) > min_sup，則U為頻繁項集，若F (U) ( min_sup，則U為不頻繁項集。
4.根據權利要求3所述的基於增量式關聯規則技術的動態大數據模型高效建立方法，其特徵在於，步驟I中，利用關聯規則挖掘算法為初始事務資料庫創建初始增量式頭表結構XH-struct，增量式頭表結構XH-struct的頭表記為XH，頻繁項和不頻繁項都包含在頭表XH中，XH中的每一項都包含三個屬性:{ID，Sup, Poi}，ID是項目編號，Sup是項目的支持度，Poi是指針域。
5.根據權利要求4所述的基於增量式關聯規則技術的動態大數據模型高效建立方法，其特徵在於，步驟2中，將增量式頭錶轉化為基於內存的樹形結構HT，並以XML文檔形式保存在硬碟中，原有頭表XH中的每一項都作為樹形結構HT根節點root的子節點item，每個子節點有兩個屬性:{Na, Sup}，Na是項目名，Sup是項目的支持度，每個子節點有若干個孩子節點具體的事務記為事務節點trans,事務節點用屬性標識符TID來標記資料庫中的一條事務。
6.根據權利要求5所述的基於增量式關聯規則技術的動態大數據模型高效建立方法，其特徵在於，步驟3中，當資料庫更新時，只對新增資料庫Λ TDB進行掃描計算，建立新增資料庫的增量式頭表並轉化為相應的XML文檔，將歷史XML文檔與新增資料庫的XML文檔合併構建更新後事務資料庫的XML文檔，然後利用更新的XML文檔來挖掘頻繁模式。
【文檔編號】G06F17/30GK103927373SQ201410168643
【公開日】2014年7月16日 申請日期:2014年4月24日 優先權日:2014年4月24日
【發明者】程道華, 劉盛強, 張慶, 彭清衝, 況培, 田潔, 李方林 申請人:湖北航雲端科技有限公司