[發明專利]基于Eclat的多元時間序列關聯規則挖掘方法

在審

• 申請號: 201710763342.2
• 申請日: 2017-08-30
• 公開（公告）號: CN107562865A
• 公開（公告）日: 2018-01-09
• 發明（設計）人: 張春慨
• 申請（專利權）人: 哈爾濱工業大學深圳研究生院
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 深圳市科吉華烽知識產權事務所(普通合伙)44248
• 代理人: 胡吉科

技術領域

本發明屬于數據挖掘技術領域，具體涉及一種大規模數據下的進行關聯規則挖掘的方法。

背景技術

目前國內外都有一些關于近似關聯規則挖掘研究，由于他們研究的側重點不同，用的關聯規則的挖掘算法不同，挖掘到的關聯規則的特點也不同。一般的近似關聯規則挖掘的步驟分為兩個階段，先進行預處理操作，在海量的原始數據上進行壓縮，平滑，去噪，線性化近似，分割時間序列，聚類等，然后在已經處理過的數據集上進行近似關聯規則挖掘算法的實施。

傳統的關聯規則挖掘算法針對的是離散數據，挖掘出的關聯規則并不能體現時間的先后順序。第一次應用在時間序列上的關聯規則的挖掘算法的提出是在1998年Das提出的。研究對象是從單時間序列挖掘的關聯規則開始，后來擴展到多時間序列的挖掘。在處理時間序列數據時，把時間序列劃分成長度相等的子序列，然后為每個趨勢不同的子序列分配一個符號表示。這種算法關注的子序列的趨勢主要有三種，上升，下降，平衡。因此，對于不同時間長度，趨勢相同的子序列并不能區分。后來學者把FP-growth算法應用在時間序列關聯規則挖掘方面。FP-growth算法是一種高效可擴展的算法，通過模式增長的方式，用擴展前綴樹結構FP-tree，這個概要存儲結構用于存儲關于頻繁模式的壓縮和關鍵信息，在很多情況下都比Apriori效果更好。后來在此基礎上又出現了很多改良的算法。CFP-mine算法是基于壓縮的FP樹，基于約束子樹的方法，減少內存的調用，并且用了數組的方法，減少了遍歷次數。

最經典的關聯規則挖掘算法是Agrawal于1993年提出的Apriori算法，Apriori算法是一種挖掘關聯規則的頻繁項集算法，通過逐層搜索的迭代算法，在每次生成候選的頻繁項集的時候都要經過掃描，計數，比較，連接，剪枝這幾個步驟。但是利用Apriori算法挖掘關聯規則在驗證候選頻繁K項集的時候要對整個數據集進行掃描不止一遍，其時間效率很低。EH-Apriori挖掘算法在Apriori算法的基礎上進行了兩點改進，一是挖掘過程進行了預處理，二是將數據集的數據Hash到一個很大的表。后來Han等學者于2000年研究了關聯規則的相關性質提出了FP-growth算法。FP-growth算法是通過建立具有前綴性質的FP-tree來僅僅遍歷一遍數據庫，就可以挖掘到頻繁模式，從而提高挖掘效率。實驗證明FP-growth算法的性能比Apriori快了一個數量級。Apriori與FP-growth均采用水平項集來挖掘數據，ZAKI于2000年提出Eclat算法，該算法采用垂直數據表示來挖掘關聯規則。垂直數據表示數據集由項目和所有包含該項目的事務的標識的集合組成算法采用交叉計數的方式使得候選集的生成與支持度計數的計算可以同時完成。實踐證明采用垂直數據表示的算法的性能一般優于采用水平數據表示的算法。

由于時間序列數據量大，實時產生等特點，傳統數據挖掘算法無法及時有效的挖掘到所需的知識。取樣是一種在普通的資源上獲取近似規則的有效手段，以其在處理大規模數據集中表現出的良好性能而得到了廣泛深入的研究，是提高關聯規則算法效率和可擴展性的一種簡單、有效的方式。常用的設計方法有直方圖方法、取樣方法和小波方法等。由于取樣方法良好的伸縮性和靈活性使其成為構建數據流概要的一個非常重要的方法。所有這些研究的最終目標都是利用盡可能小的樣本集最佳地近似原始數據集上的信息(找到合適的樣本大小和最優樣本集)，但這一結果的獲得離不開對取樣誤差(數據集之間差異)的有效度量。目前缺乏系統的研究和統一、有效的模型。基于取樣策略的關聯規則挖掘算法，乃至整個數據挖掘算法的樣本集與原始數據集之間、樣本集與樣本集之間包含興趣信息差異的計算是整個取樣過程的一個中心問題。

近些年一種使用局部敏感哈希(LSH)技術輔助關聯規則挖掘的方法逐漸開始流行。這種方法借鑒了信息檢索領域快速計算相似度的手段來優化關聯規則挖掘中的步驟，從而達到快速挖掘的目的。這種方式采用哈希函數對數據進行壓縮，能夠比較好的處理海量數據。并且經過理論和實踐的驗證，數據壓縮帶來的信息損失可以控制在一定范圍內，挖掘規則的精準性也可以得到保障。在保證一定精確度的前提下,取樣方法顯著減小了所處理數據集的規模，使得眾多數據挖掘算法得以應用到大數據集以及數據流數據上。

發明內容

為解決現有技術中存在的問題，本發明設計了一種基于Eclat的關聯規則挖掘方法，顯著的加快關聯規則挖掘速度，達到及時獲取時間序列數據分析結果的目標，雖然犧牲了挖掘的精確性，但可以大大的提高挖掘效率、節約機器內存。

本發明具體通過如下技術方案實現：