[發明專利]數據關聯規則挖掘實現方法與系統

有效

• 申請號: 200910091865.2
• 申請日: 2009-08-31
• 公開（公告）號: CN101996102A
• 公開（公告）日: 2011-03-30
• 發明（設計）人: 高丹;徐萌;鄧超;羅治國;周文輝;孫少陵;何清;曾立
• 申請（專利權）人: 中國移動通信集團公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F17/30
• 代理公司: 北京同達信恒知識產權代理有限公司 11291
• 代理人: 郭潤湘

技術領域

本發明涉及數據業務，尤其涉及一種數據關聯規則挖掘實現方法與相應的實現系統。

背景技術

在數據挖掘處理中，數據關聯規則(Association?Rule)的挖掘目的，是發現在大量的數據項之間存在的值得關注的關聯或相關關系，典型應用是零售業的購物籃分析。所謂購物籃分析是指對數據進行關聯規則研究，有助于發現交易數據庫中不同商品(或不同項)之間的聯系，找出顧客購買行為的模式，例如，如果面包和牛奶經常被顧客同時購買，則把它們擺放在一起有助于增加兩種商品的銷售量。為了衡量一條規則的重要程度，關聯規則通常采用支持度(support)和可信度(confidence)作為度量標準。支持度可以表示商品在超市銷售中的重要程度，可信度反映了商品之間的關聯程度。如果在購買面包的交易中，有60％的交易既購買了面包又購買了牛奶，則稱關聯規則“面包牛奶”(表示如果購買面包則購買牛奶)的可信度為60％。

關聯規則(表示A與B同時存在)在事務數據庫D中的支持度，可用概率表示；關聯規則在事務數據庫D中的可信度，是在事務數據庫D中的那些包含A的事務中，B也同時出現的概率，即條件概率。

一個項集X在事務數據庫D中的支持度，是事務數據庫D中包含X的事務count(X)占事務總數N的百分比，即概率P(X)。對于一個項集X，如果其支持度大于或等于預先給定的支持度閾值min_sup，則稱X為頻繁項集(FI：Frequent?Itemset)或頻繁模式。

FP-growth算法(頻繁模式增長算法)只需要對數據庫進行兩次掃描：第一次掃描得到頻繁1-項集；第二次掃描構建FP-Tree。最后挖掘FP-Tree得到強關聯規則。算法的核心是FP-Tree(Frequent?Pattern?Tree，頻繁模式樹)的構建。FP-Tree通過合并一些重復路徑，實現了數據的壓縮，從而使得將頻繁項集加載到內存中成為可能，從而提高了運算效率。FP-growth算法的具體實現如下：

(1)掃描一遍數據庫，獲取所有頻繁項集。以下表一所述數據記錄為例，得到的頻繁項集為：{(c：4)，(f：4)，(a：3)，(b：3)，(m：3)，(p：3)}，“：”之后的數字表示對應數據項的出現頻率(即出現次數)。上述頻繁項集是首先按照各數據項出現頻率從大到小排序，再按照字母順序(即規定的數據項順序)排序，并刪除出現次數小于最小支持度的相應數據項。需要注意的是這里的排序非常重要，之后每個數據記錄中的各項都要按照這個順序進行排列，排列順序是有效合并重復路徑的前提。

表一