一種基於數據壓縮的改進的Apriori算法的製作方法
2023-07-14 17:32:41 1
專利名稱：一種基於數據壓縮的改進的Apriori算法的製作方法
技術領域：
本發明涉及對一種Apriori算法的改進算法。
背景技術：
關聯規則挖掘用來發現大量數據中項集之間的有趣的關聯或相關聯繫，它在數據挖掘中是一個重要的課題，最近幾年已被業界所廣泛研究。關聯規則挖掘的一個典型例子是購物籃分析。關聯規則研究有助於發現交易資料庫中不同商品(項)之間的聯繫，找出顧客購買行為模式，如購買了某一商品對購買其他商品的影響。分析結果可以應用於商品貨架布局、貨存安排以及根據購買模式對用戶進行分類。Agrawal等於1994年提出了一個挖掘顧客交易資料庫中項集間的關聯規則的重要方法Apriori，其核心是基於兩階段頻繁集思想的遞推算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。該算法的基本思想是:首先找出所有的頻繁項集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然後由頻繁集產生強關聯規則，這些規則必須滿足最小支持度和最小可信度。一旦這些規則被生成，那麼只有那些大於用戶給定的最小可信度的規則才被留下來。為了生成所有頻繁項集，使用了遞推的方法。Apriori的總體性能由第一步決定，第二步相對容易實現。傳統的Apriori算法具有兩個主要的缺陷:1.會產生大量的候選集；2.會重複地掃描資料庫；為解決上述問題，本發明利用資料庫中數據的特點，提出一種基於數據壓縮的Apriori算法的改進算法，同時在候選集的選擇上進行預先判斷，以減少所產生的候選集的數目。本發明的再一目的是減少掃描資料庫的次數，以提高查詢的速度。發明概述為了實現上述目的，本發明採用了壓縮資料庫的辦法。設有由m個項{Λ，、...、}組成的數據集合，資料庫中的每一項均由該集合中的元素組成，即Tk= U1, I2...1j，資料庫共包含N條事務記錄，資料庫中所有組合的總數為:M = Cim +C2m +Cl+...+ Ckm+...+CZ = 2m-1當N > M時，對資料庫進行壓縮，提取出資料庫中的有效信息，生成資料庫項和該數據項數量的映射表DB_Map_Tbale，映射函數為H(key)。這裡引入轉換函數f (X)，F (X)的作用是將資料庫項轉換為DB_Map_Tbale中該項對應的鍵值。如:對於Tk = (I1, I2...1jlF (Tk) = keyk進一步，對DB_Map_Tbale中內容排序，將該映射表DB_Map_TabIe中的所有健值對〈key, value)按 key 的大小升序排列，即 KEY = {key1； key2,...keyj , Icey1 < key2< … 2)。每次從η-1項頻繁集中選出沒有合併過的兩個頻繁集Ιχ，Ιγ，如果Ix，Iy這兩個集合的前η-2項相同，第η-1項不同，則它們符合原始算法的合併條件。本發明在此基礎上額外加入新的判斷條件，判斷將要合併的兩個頻繁集Ix，Iy中不同的兩項ix，、所組成的2項集ixy = {ix，iy}是否是2項頻繁集IF的子集，若4 c ^，則將Ιχ U Iy加入候選集的集合In中。根據Apriori算法的原理，當在第一個階段要計算每一個候選集合Ik = U1,I2-..Ιχ}的支持度SUP(Ik)時,從處開始順序掃描DB_Map_Tbale,引入函數(Kkey1),(Kkey1) =I= (I1, I2,...1j那麼
權利要求
1.一種基於數據壓縮的改進的Apriori算法,包括步驟: 判斷資料庫中的事物記錄條數N大於該資料庫中所有數據項的所有可能的組合數M時，生成資料庫項與該數據項數量的映射表DB_Map_Table ； 將該映射表DB_Map_Table中的所有健值對〈key, value)按key的大小升序排列，即KEY = {key1； key2,...keyj , keyi < key2 <...< keym ； 利用Apriori算法從DB_Map_Table表的第化處開始掃描該DB_Map_Table表，以計算每個候選集Ik = U1, I2-..IJ的支持度。
2.根據權利要求1的基於數據壓縮的改進的Apriori算法，其特徵在於生成所述映射表DB_Map_Table的過程包括以下步驟:設置長度為 m 的 bitmask = <0000...0〉； 順序讀取資料庫的每一項，對於所讀取的資料庫的項Tk = {Ix，Iy,...1J，調用f(X)，將bitmask = <0000...0〉對應的x, y,…z位設置為I,生成Tk對應的bitvector = ； bitvector = 轉化為對應的十進位鍵值keyk ； 調用count = H(keyk),若返回的結果為O,則H(keyk) = I,若返回值大於0,H(keyk)=count+1 ； 重複以上步驟直至掃描完整個資料庫。
3.根據權利要求 1或2的基於數據壓縮的改進的Apriori算法，其特徵在於還包括:引入函數(Kkey1), (Kkey1) =I= (I1, I2,...1j ,並且根據公式 mSUP(4) = Y.HUKdikey,) e d(z+))計算每個候選集合的支持度。keyk
4.根據前述權利要求之一的基於數據壓縮的改進的Apriori算法,其特徵在於還包括:使用Apriori算法生成I (I > 2)項候選集時，判斷將要合併的兩個頻繁集Ix，Iy中不同的兩項ix，iy所組成的2項集ixy = {ix，iy}是否是2項頻繁集If的子集，若『 c/f，則將Ix U Iy加入候選集的集合In中。
全文摘要
一種基於數據壓縮的改進的Apriori算法，包括步驟判斷資料庫中的事物記錄條數N大於該資料庫中所有數據項的所有可能的組合數M時，生成資料庫項與該數據項數量的映射表DB_Map_Table；將該映射表DB_Map_Table中的所有健值對按照key的大小升序排列；使用Apriori算法生成I(I＞2)項候選集時，判斷將要合併的兩個頻繁集中不同的項所組成的二項集是否為2項頻繁集的子集，如果是，則將將要合併的兩個頻繁集的合集加入候選集。本發明的效果在於，減小了原有事務資料庫的大小，減少了資料庫的掃描次數，減少了算法運行過程中候選集的生成，從而在保證算法正確的同時有效地提高了算法的速度和效率。
文檔編號G06F17/30GK103176976SQ201110430528
公開日2013年6月26日 申請日期2011年12月20日 優先權日2011年12月20日
發明者高海洋, 沈強, 張軒溢, 唐朝偉, 趙志軍, 慈松, 唐暉 申請人:中國科學院聲學研究所, 無錫中科智能信息處理研發中心有限公司