《電子技術應用》
您所在的位置:首頁 > 通信與網絡 > 設計應用 > 使用垂直數據格式挖掘頻繁項集
使用垂直數據格式挖掘頻繁項集
來源:微型機與應用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亚洲国产精品_日韩亚洲一区二区
亚洲国产成人精品久久久国产成人一区 | 欧美一区永久视频免费观看| 亚洲免费成人av| 亚洲区第一页| 亚洲高清在线视频| 在线观看一区视频| 亚洲国产成人精品女人久久久| 国产一区在线播放| 国产视频一区二区在线观看| 国产精品推荐精品| 国产精品一香蕉国产线看观看| 国产精品免费看久久久香蕉| 国产精品欧美一区二区三区奶水 | 欧美精品aa| 欧美大片一区二区| 欧美精品福利视频| 欧美理论电影在线观看| 欧美日韩精品二区| 欧美四级伦理在线| 国产精品老女人精品视频| 国产精品久久婷婷六月丁香| 国产精品播放| 国产精品一区二区三区四区五区| 国产区欧美区日韩区| 国产综合久久| 亚洲大片精品永久免费| 亚洲黄色免费电影| 日韩视频三区| 亚洲一区成人| 欧美一站二站| 亚洲精品国精品久久99热| 亚洲精一区二区三区| 中国成人黄色视屏| 亚洲女女女同性video| 久久av一区二区三区| 久久久免费av| 欧美国产一区二区三区激情无套| 欧美日本成人| 国产精品电影观看| 国产一区二区三区高清| 亚洲国产毛片完整版| 日韩午夜激情电影| 亚洲综合日本| 91久久精品国产91久久性色tv| 亚洲六月丁香色婷婷综合久久| 中文一区字幕| 欧美一区二区在线看| 麻豆av一区二区三区久久| 欧美美女日韩| 国产精品理论片在线观看| 国产一区久久| 亚洲久久一区二区| 欧美一区成人| 亚洲精品视频在线| 午夜精品久久久久久| 免费不卡欧美自拍视频| 欧美午夜精品电影| 国内精品伊人久久久久av影院 | 一区免费视频| 亚洲免费观看高清在线观看| 亚洲免费在线视频一区 二区| 欧美伊人久久大香线蕉综合69| 亚洲免费观看在线视频| 午夜精品一区二区三区在线播放| 久久亚洲综合网| 欧美午夜激情小视频| 激情欧美一区二区三区在线观看| 亚洲精品人人| 欧美亚洲一区二区三区| 一本一本a久久| 久久一区二区视频| 欧美午夜一区二区福利视频| 精品成人国产在线观看男人呻吟| 一区二区av在线| 亚洲经典三级| 久久99在线观看| 欧美日本在线| 在线成人h网| 亚洲一区二区免费视频| 亚洲精选视频免费看| 久久精品国产999大香线蕉| 欧美日韩国产色视频| 韩日欧美一区| 亚洲综合国产激情另类一区| 99在线热播精品免费| 久久三级视频| 国产精品一区二区视频| 日韩视频在线观看国产| 亚洲国产天堂久久综合| 亚洲欧美春色| 欧美日韩免费一区| 亚洲国产精品ⅴa在线观看 | 久久精品国产精品亚洲综合| 亚洲中午字幕| 欧美精品一区视频| 激情综合久久| 羞羞色国产精品| 亚洲欧美另类在线| 欧美日韩在线观看一区二区三区| 1000部国产精品成人观看| 欧美一级片在线播放| 亚洲欧美视频一区| 欧美四级在线观看| 亚洲另类一区二区| 亚洲美女啪啪| 欧美不卡一区| 激情久久婷婷| 久久精品一区二区三区四区 | 国际精品欧美精品| 亚洲欧美中文字幕| 欧美一级视频精品观看| 国产精品福利在线| 国产精品99久久不卡二区| 在线视频亚洲| 欧美激情一区二区三区不卡| 亚洲国产黄色片| 亚洲精品欧美激情| 欧美成人免费全部| 亚洲高清久久网| 亚洲激情在线| 欧美v日韩v国产v| 亚洲国产人成综合网站| 亚洲激情图片小说视频| 免费观看成人网| 在线欧美日韩| 亚洲精品网址在线观看| 欧美激情麻豆| 日韩午夜在线视频| 亚洲一级片在线看| 国产精品入口| 羞羞答答国产精品www一本 | 欧美午夜精品久久久久久久| 亚洲午夜激情免费视频| 亚洲欧美日韩国产一区二区三区| 国产精品久久久久aaaa九色| 亚洲制服av| 久久精品国产一区二区电影| 黄色成人在线免费| 亚洲精品在线观看免费| 欧美精品免费播放| 一区二区三区高清在线| 午夜精品久久久久久99热| 国产日本欧美一区二区| 久久精品99无色码中文字幕| 欧美a级在线| 亚洲精品综合久久中文字幕| 亚洲一区视频在线观看视频| 国产精品永久入口久久久| 欧美尤物巨大精品爽| 欧美91大片| 在线亚洲一区二区| 久久疯狂做爰流白浆xx| 在线观看国产精品网站| 日韩视频专区| 国产精品嫩草影院av蜜臀| 欧美一站二站| 欧美极品一区二区三区| 亚洲午夜视频在线| 久久亚洲国产精品一区二区| 亚洲精品一品区二品区三品区| 亚洲一区二区三区中文字幕在线| 国产精品中文字幕欧美| 亚洲国产一区二区在线| 欧美日韩国产一级| 亚洲欧美怡红院| 欧美v亚洲v综合ⅴ国产v| 中日韩男男gay无套| 欧美专区福利在线| 亚洲欧洲另类| 性高湖久久久久久久久| 在线成人av.com| 亚洲男人的天堂在线aⅴ视频| 国产真实久久| 这里只有视频精品| 国内精品国产成人| 亚洲午夜免费福利视频| 国产一区999| 在线一区免费观看| 国内自拍视频一区二区三区| 9色国产精品| 国产一区91| 亚洲性视频网站| 伊人成综合网伊人222| 亚洲图片欧洲图片av| 国产主播一区二区三区四区| 中国av一区| 黄色成人片子| 亚洲欧美日韩综合| 最新国产の精品合集bt伙计| 欧美一区日韩一区| 亚洲精品四区| 久久午夜精品| 亚洲一卡二卡三卡四卡五卡| 欧美大片在线看| 欧美一级网站| 国产精品v欧美精品v日韩| 亚洲激情不卡| 国产亚洲欧美日韩在线一区| 中文欧美在线视频| 在线观看日韩av电影|