《電子技術應用》
您所在的位置:首頁 > 通信與網絡 > 設計應用 > 使用垂直數據格式挖掘頻繁項集
使用垂直數據格式挖掘頻繁項集
來源:微型機與應用2011年第18期
陳 偉
(淮南聯合大學 計算機系,安徽 淮南232038)
摘要: 關聯規則是數據挖掘的主要技術之一,它是描述數據庫中一組數據項之間的某種潛在關系的規則。關聯規則挖掘算法——Apriori算法,主要過程是對頻繁項集的挖掘,而在對頻繁項集的挖掘中首先要生成候選頻繁項集,然后再從候選集中確定出滿足最小支持度計數的頻繁項集,這會耗費大量的CPU開銷。使用垂直數據格式挖掘頻繁項集可避免候選項目集的求解。
Abstract:
Key words :

摘  要: 關聯規則是數據挖掘的主要技術之一,它是描述數據庫中一組數據項之間的某種潛在關系的規則。關聯規則挖掘算法——Apriori算法,主要過程是對頻繁項集的挖掘,而在對頻繁項集的挖掘中首先要生成候選頻繁項集,然后再從候選集中確定出滿足最小支持度計數的頻繁項集,這會耗費大量的CPU開銷。使用垂直數據格式挖掘頻繁項集可避免候選項目集的求解。
關鍵詞: 關聯規則;Apriori算法;頻繁項集;垂直數據格式

    通常,關聯規則挖掘是指從一個大型的數據集中發現有趣的關聯或相關關系,即從數據集中識別出頻繁出現的屬性值集(Sets of Attribute-Values),也稱為頻繁項集(Frequent Itemsets,簡稱頻繁集),然后再利用這些頻繁集創建描述關聯規則的過程。
1 關聯規則挖掘算法
    關聯規則挖掘算法——Apriori算法是使用候選項集找頻繁項集的過程。
    Apriori算法通過對數據庫D的多趟掃描來發現所有的頻繁項目集。在第一趟掃描數據庫時,對項集I中的每一個數據項計算其支持度,確定出滿足最小支持度的頻繁1項集的集合L1,然后,L1用于找頻繁2項集的集合L2,如此下去……在后續的第k次掃描中,首先以k-1次掃描中所發現的含k-1個元素的頻繁項集的集合Lk-1為基礎,生成所有新的候選項目集CK(Candidate Itemsets),即潛在的頻繁項目集,然后掃描數據庫D,計算這些候選項目集的支持度,最后從候選集CK中確定出滿足最小支持度的頻繁k項集的集合Lk,并將Lk作為下一次掃描的基礎。重復上述過程直到不再發現新的頻繁項目集[1]。
2 關聯規則算法的改進
    從Apriori算法中由k頻繁項集生成k+1頻繁項集時,首先生成候選項目集Ck+1,該函數不僅要對k項集的所有符合Apriori算法條件的數據進行交集,并且要判斷候選項目集的所有子集是否在k頻繁項集中。該函數生成的許多候選項目集并不是要找的頻繁項集,但在掃描數據庫時,要記錄下這些數據的出現次數,這會耗費大量的CPU開銷。如果D中的事務數很大,k頻繁項集中項數很多,則侯選項目集的元素個數就會很大,例如2 000個頻繁1項集,將產生2 000×999/2=999 000個候選2項集。如此巨大數量的候選項目集,對它進行出現次數的統計時開銷非常大,這也是整個算法性能優劣的關鍵所在。
 (1)使用垂直數據格式挖掘頻繁項集
   Apriori算法是從TID項集格式(即{TID:itemset})的事務集挖掘頻繁模式,其中TID是事務標識符,而itemset是事務TID中購買的商品集。這種數據格式稱作水平數據格式。另外,數據也可以用項-TID集格式(即{item:TID_set})表示,其中item是項的名稱,而TID_set是包含item事務標識符的集合。這種格式稱作垂直數據格式。下面使用垂直數據格式進行有效的挖掘頻繁項集。
    首先,通過掃描一次數據庫D,在求頻繁l項集的同時,把數據由水平格式轉化為垂直格式,即記錄下每個項集在事務數據庫中出現時該條數據在數據庫D中的TID號,則項集的支持度計數直接是項集的TID集的長度。從k=2開始,根據Apriori性質中相交條件的項集進行Apriroi連接運算,使用頻繁k項集來構造候選k+1項集。通過取頻繁k項集的TID集的交計算對應的k+1項集的TID集。如果該TID集的長度大于最小支持度計數,則該記錄為頻繁項集。重復該過程,每次k值增加1,直到不能再找到頻繁項集或候選項集。
 

    通過挖掘可以驗證最終得到的頻繁項集和用Apriori算法得到的結果是相同的[2-3]。

3 改進算法的分析

 


    理論上,改進算法應快于算法Apriori,原因如下:
    (1)該算法不用求候選頻繁項集,從而省去了項集進行連接步以后對該項集所有子集的判斷,這會節省大量
的CPU開銷,尤其是當數據庫D中的數據比較多,同時候選項集比較多時,例如頻繁1項集2 000個,根據Apriori性質,則候選頻繁1項集要有2 000×999/2=999 000個,但其中也許只有少數是要找的頻繁2項集。Apriori算法要求其中所有999 000個在數據庫中的頻繁度。
    (2) 除了由頻繁k項集產生候選k+1項集時利用Apriori性質之外,這種方法的另一優點是不需要掃描數據庫來確定k+1項集(k≥1)的支持度。這是因為每個k項集的TID集攜帶了計算該支持度所需的完整信息。
    該算法的缺點是TID集可能很長,長集合不僅需要大量空間,而且求交運算需要大量計算時間。
參考文獻
[1] 韓家煒. 數據挖掘概念與技術[M].北京:機械工業出版社,2000.
[2] 陸楠.關聯規則的挖掘及其算法的研究[D]. 長春:吉林大學,2007.
[3] 羅可,張學茂. 一種高效的頻集挖掘算法[J]. 長沙理工大學學報(自然科學版),2006,3(3):84-90.
[4] 汪光一. 關聯規則挖掘算法的研究[D]. 北京:北京交通大學,2007.
[5] 高峰,謝劍英. 發現關聯規則的增量式更新算法[J].計算機工程,2000(12):49-50.
[6] KANTARDZIC M(美).數據挖掘-概念、模型、方法和算法[M]. 北京:清華大學出版社,2003.

此內容為AET網站原創,未經授權禁止轉載。
亚洲一区二区欧美_亚洲丝袜一区_99re亚洲国产精品_日韩亚洲一区二区
久久国产精品黑丝| 亚洲愉拍自拍另类高清精品| 亚洲靠逼com| 在线观看日韩| 狠狠色狠狠色综合系列| 国产香蕉久久精品综合网| 国产精品视频大全| 国产精品高潮呻吟| 国产精品免费观看在线| 欧美视频在线观看视频极品| 欧美日韩免费在线| 欧美日韩一区二区三区免费看| 欧美精品激情| 欧美激情一区二区三区蜜桃视频 | 国产字幕视频一区二区| 国产亚洲精品久久飘花| 国产日韩欧美精品一区| 国产精品视频最多的网站| 国产精品视频成人| 国产性猛交xxxx免费看久久| 国产亚洲免费的视频看| 激情伊人五月天久久综合| 今天的高清视频免费播放成人 | 欧美激情精品久久久久久| 你懂的视频一区二区| 亚洲一区二区三区四区五区午夜 | 亚洲一二三区精品| 亚洲在线电影| 香蕉久久夜色| 久久精品国产77777蜜臀| 久久精品亚洲精品国产欧美kt∨| 久久久天天操| 欧美成人视屏| 欧美日韩精品在线观看| 国产精品美女久久久久久2018| 国产精品免费观看视频| 国产一区二区三区自拍| 又紧又大又爽精品一区二区| 91久久精品国产91久久性色tv| 亚洲激情在线播放| 在线亚洲欧美| 欧美一区二区黄色| 最新日韩在线| 亚洲一区二区3| 久久大香伊蕉在人线观看热2| 久久美女性网| 欧美精品亚洲二区| 欧美日韩伦理在线| 国产精品视频网| 激情偷拍久久| 99热精品在线观看| 欧美一区二区视频在线| 亚洲人成毛片在线播放| 亚洲视频1区2区| 久久精品色图| 欧美绝品在线观看成人午夜影视| 国产精品都在这里| 精品动漫3d一区二区三区| 亚洲乱码一区二区| 欧美一区激情视频在线观看| 亚洲免费黄色| 欧美主播一区二区三区| 欧美激情一区二区三级高清视频 | 亚洲午夜女主播在线直播| 性色av香蕉一区二区| 日韩亚洲欧美中文三级| 欧美中文字幕精品| 国产精品99久久久久久久vr| 欧美精品久久久久久| 国产精品久久久久久亚洲调教 | 国产日韩欧美在线| 亚洲国产一区二区精品专区| 亚洲一区日本| 亚洲精品无人区| 欧美在线视频一区| 欧美日本一区| 国产一区日韩一区| 亚洲深夜福利网站| 亚洲精选中文字幕| 久久久国产一区二区三区| 欧美三级视频在线播放| 在线成人中文字幕| 午夜精品一区二区三区四区 | 亚洲一区999| 欧美大片第1页| 国产一区二区丝袜高跟鞋图片| 99国产麻豆精品| 亚洲日韩欧美视频| 久久偷窥视频| 国产女主播一区二区| 洋洋av久久久久久久一区| 亚洲日本电影在线| 久久久美女艺术照精彩视频福利播放| 欧美三日本三级三级在线播放| 在线播放日韩| 欧美一区二区三区四区高清| 亚洲一区久久久| 欧美精品在线一区| 伊人久久综合| 欧美一区国产在线| 欧美一区在线视频| 国产精品久久综合| aa日韩免费精品视频一| 亚洲精品日韩在线观看| 久久免费精品日本久久中文字幕| 国产精品老女人精品视频| 日韩视频精品| av成人免费观看| 欧美77777| 黄色成人在线免费| 久久精品国产精品亚洲精品| 久久国产日韩| 国产亚洲欧美日韩日本| 亚洲嫩草精品久久| 欧美影院久久久| 国产精品视频一二| 亚洲视频电影图片偷拍一区| 一本色道久久综合亚洲精品不卡| 欧美成人午夜激情| 亚洲高清久久网| 最新日韩在线视频| 欧美高清视频在线| 亚洲人成亚洲人成在线观看| 亚洲美女黄色片| 欧美大片91| 亚洲精品国精品久久99热一 | 一区二区欧美日韩| 欧美人体xx| 亚洲免费久久| 亚洲在线视频免费观看| 国产精品久久久久久久免费软件| 亚洲一区成人| 久久成人在线| 加勒比av一区二区| 亚洲精品精选| 欧美伦理91i| 一区二区三区欧美视频| 亚洲欧美国产高清va在线播| 国产精品日本精品| 午夜在线精品偷拍| 久久久精品免费视频| 国语自产精品视频在线看8查询8| 亚洲国产色一区| 欧美国产欧美综合| a4yy欧美一区二区三区| 性欧美xxxx大乳国产app| 国产午夜精品福利| 亚洲黄色成人| 欧美日韩的一区二区| 亚洲一本大道在线| 欧美资源在线观看| 一区二区在线观看视频在线观看| 亚洲黄网站黄| 欧美久久久久| 亚洲一区制服诱惑| 久久久综合网站| 亚洲国产一区二区a毛片| 亚洲午夜精品福利| 国产欧美在线| 亚洲日本aⅴ片在线观看香蕉| 欧美日韩精品不卡| 亚洲综合精品四区| 蜜臀久久99精品久久久久久9| 日韩网站在线看片你懂的| 亚洲欧美久久| 影音先锋另类| 亚洲资源av| 狠狠色伊人亚洲综合成人| 一区二区电影免费在线观看| 国产伦精品免费视频| 亚洲国产小视频在线观看| 欧美日韩一区在线播放| 欧美伊久线香蕉线新在线| 欧美精品九九| 性色av香蕉一区二区| 欧美日韩国产精品自在自线| 亚洲免费在线电影| 欧美国产日韩亚洲一区| 亚洲自拍偷拍一区| 欧美成人免费大片| 亚洲免费一在线| 欧美精品1区| 欧美一区二区三区免费大片| 欧美日产在线观看| 欧美一级专区免费大片| 欧美日韩免费看| 久久精品五月| 国产精品乱码人人做人人爱| 91久久精品国产91久久| 国产精品欧美日韩| 亚洲精品美女在线观看播放| 国产精品色在线| 夜夜嗨av一区二区三区免费区| 国产午夜一区二区三区| 夜夜狂射影院欧美极品| 激情视频一区二区| 欧美一区二区在线看| 亚洲另类在线一区| 欧美成人按摩| 翔田千里一区二区|