資源描述:
《apriori算法中頻繁項(xiàng)集求法的改進(jìn)》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、Apriori算法中頻繁項(xiàng)集求法的改進(jìn)摘要:分析傳統(tǒng)Apriori效率較低的原因,采用0-1矩陣改進(jìn)數(shù)據(jù)庫事務(wù)集的描述,提高Apriori中統(tǒng)計(jì)匹配的時(shí)間效率;分析各頻繁項(xiàng)集的計(jì)數(shù),改進(jìn)傳統(tǒng)Apriori算法完全從低維頻繁項(xiàng)集產(chǎn)生高維頻繁項(xiàng)集的方式,通過先求出1項(xiàng)頻繁集和最大頻繁項(xiàng)集,減少中間的頻繁項(xiàng)集剪枝數(shù)量,從而達(dá)到提高算法效率的目的?! £P(guān)鍵詞:0-1矩陣;統(tǒng)計(jì)匹配;剪枝 1關(guān)聯(lián)規(guī)則[1]挖掘及Apriori算法概述 一提到關(guān)聯(lián)規(guī)則挖掘就會(huì)令人聯(lián)想到“尿布與啤酒”的故事,這是借助數(shù)據(jù)挖
2、掘技術(shù)對大量原始交易數(shù)據(jù)進(jìn)行分析揭示的一條規(guī)律。Apriori[2]算法是由美國學(xué)者R.Agra*n矩陣的0-1矩陣,其中m為數(shù)據(jù)庫事務(wù)集D的大小,即包含多少個(gè)事務(wù),n為集合I的計(jì)數(shù)?! 〔捎?-1矩陣描述數(shù)據(jù)庫事務(wù)集能帶來如下好處: ?。?)運(yùn)算簡單;便于統(tǒng)計(jì),橫向統(tǒng)計(jì)“1”的個(gè)數(shù)就是事務(wù)T包含的項(xiàng)數(shù),縱向統(tǒng)計(jì)“1”的個(gè)數(shù)就是1項(xiàng)集的統(tǒng)計(jì)數(shù);(2)使用0-1矩陣算法,提高統(tǒng)計(jì)項(xiàng)集時(shí)候的匹配效率,傳統(tǒng)的統(tǒng)計(jì)匹配效率正比于n,采用0-1矩陣匹配時(shí)間效率正比于n;(3)減少對數(shù)據(jù)庫的掃描,排序后,
3、求頻繁k項(xiàng)集的時(shí)候,統(tǒng)計(jì)項(xiàng)集時(shí)不需要掃描數(shù)據(jù)庫,只需要統(tǒng)計(jì)包含大于等于k個(gè)項(xiàng)目數(shù)的事務(wù);(4)易于對數(shù)據(jù)庫事務(wù)集按事務(wù)包含的項(xiàng)目數(shù)大小降序排序;(5)易于求出最大頻繁項(xiàng)集。 2.2改進(jìn)后的算法MyApriori描述 要提高Apriori算法的效率,一般來說就是要考慮兩個(gè)方面的問題:一是減少對數(shù)據(jù)庫的掃描,二是在剪枝的時(shí)候減少統(tǒng)計(jì)項(xiàng)集的次數(shù)。采用0-1矩陣,并排序以后,可以減少對數(shù)據(jù)庫的掃描,在求k項(xiàng)頻繁項(xiàng)集時(shí)候,只需要掃描包含大于等于k個(gè)項(xiàng)目的項(xiàng)集,不需要掃描全部的數(shù)據(jù)庫。傳統(tǒng)Apriori
4、算法采用從頻繁1項(xiàng)集開始,由頻繁k-1項(xiàng)集產(chǎn)生頻繁k項(xiàng)集,中間產(chǎn)生大量候選集,對這些候選集要進(jìn)行統(tǒng)計(jì)并剪枝,運(yùn)算量大;通過多次試驗(yàn)發(fā)現(xiàn):對于1項(xiàng)頻繁集,2項(xiàng)頻繁集,……,m-1項(xiàng)頻繁集,m項(xiàng)頻繁集(m項(xiàng)頻繁集為最大頻繁項(xiàng)集),其數(shù)量分布有一定規(guī)律,就是兩頭的數(shù)量相對較少,尤其是最大頻繁項(xiàng)集數(shù)量不多,中間頻繁項(xiàng)集的數(shù)量較多,數(shù)量分布整體呈現(xiàn)為“紡錘狀”??梢韵韧ㄟ^統(tǒng)計(jì)的方法求出最大頻繁項(xiàng)集,然后利用“頻繁項(xiàng)集的所有非空子集一定也是頻繁的”這一定理,再由k-1項(xiàng)頻繁項(xiàng)集產(chǎn)生k項(xiàng)頻繁項(xiàng)集時(shí),剔除最大頻
5、繁項(xiàng)集的子集的項(xiàng)集,只需要統(tǒng)計(jì)分析剩余的項(xiàng)集是否為頻繁項(xiàng)集即可,減少了剪枝的運(yùn)算量,優(yōu)化算法。算法MyApriori:輸入原始數(shù)據(jù)庫事務(wù)集矩陣A,輸出0-1矩陣FI表示的各項(xiàng)頻繁項(xiàng)集。 上述算法的優(yōu)點(diǎn):在減少了剪枝的運(yùn)算量,減少了數(shù)據(jù)庫的掃描次數(shù);缺點(diǎn)是對原始數(shù)據(jù)庫0-1化處理、排序和統(tǒng)計(jì)產(chǎn)生最大頻繁MAXFI增加了額外開銷,其中0-1化處理、排序要對數(shù)據(jù)庫各掃描1次,統(tǒng)計(jì)產(chǎn)生最大頻繁MAXFI也摘要:分析傳統(tǒng)Apriori效率較低的原因,采用0-1矩陣改進(jìn)數(shù)據(jù)庫事務(wù)集的描述,提高Aprior
6、i中統(tǒng)計(jì)匹配的時(shí)間效率;分析各頻繁項(xiàng)集的計(jì)數(shù),改進(jìn)傳統(tǒng)Apriori算法完全從低維頻繁項(xiàng)集產(chǎn)生高維頻繁項(xiàng)集的方式,通過先求出1項(xiàng)頻繁集和最大頻繁項(xiàng)集,減少中間的頻繁項(xiàng)集剪枝數(shù)量,從而達(dá)到提高算法效率的目的。 關(guān)鍵詞:0-1矩陣;統(tǒng)計(jì)匹配;剪枝 1關(guān)聯(lián)規(guī)則[1]挖掘及Apriori算法概述 一提到關(guān)聯(lián)規(guī)則挖掘就會(huì)令人聯(lián)想到“尿布與啤酒”的故事,這是借助數(shù)據(jù)挖掘技術(shù)對大量原始交易數(shù)據(jù)進(jìn)行分析揭示的一條規(guī)律。Apriori[2]算法是由美國學(xué)者R.Agra*n矩陣的0-1矩陣,其中m為數(shù)據(jù)庫事務(wù)
7、集D的大小,即包含多少個(gè)事務(wù),n為集合I的計(jì)數(shù)?! 〔捎?-1矩陣描述數(shù)據(jù)庫事務(wù)集能帶來如下好處: ?。?)運(yùn)算簡單;便于統(tǒng)計(jì),橫向統(tǒng)計(jì)“1”的個(gè)數(shù)就是事務(wù)T包含的項(xiàng)數(shù),縱向統(tǒng)計(jì)“1”的個(gè)數(shù)就是1項(xiàng)集的統(tǒng)計(jì)數(shù);(2)使用0-1矩陣算法,提高統(tǒng)計(jì)項(xiàng)集時(shí)候的匹配效率,傳統(tǒng)的統(tǒng)計(jì)匹配效率正比于n,采用0-1矩陣匹配時(shí)間效率正比于n;(3)減少對數(shù)據(jù)庫的掃描,排序后,求頻繁k項(xiàng)集的時(shí)候,統(tǒng)計(jì)項(xiàng)集時(shí)不需要掃描數(shù)據(jù)庫,只需要統(tǒng)計(jì)包含大于等于k個(gè)項(xiàng)目數(shù)的事務(wù);(4)易于對數(shù)據(jù)庫事務(wù)集按事務(wù)包含的項(xiàng)目數(shù)大小降
8、序排序;(5)易于求出最大頻繁項(xiàng)集?! ?.2改進(jìn)后的算法MyApriori描述 要提高Apriori算法的效率,一般來說就是要考慮兩個(gè)方面的問題:一是減少對數(shù)據(jù)庫的掃描,二是在剪枝的時(shí)候減少統(tǒng)計(jì)項(xiàng)集的次數(shù)。采用0-1矩陣,并排序以后,可以減少對數(shù)據(jù)庫的掃描,在求k項(xiàng)頻繁項(xiàng)集時(shí)候,只需要掃描包含大于等于k個(gè)項(xiàng)目的項(xiàng)集,不需要掃描全部的數(shù)據(jù)庫。傳統(tǒng)Apriori算法采用從頻繁1項(xiàng)集開始,由頻繁k-1項(xiàng)集產(chǎn)生頻繁k項(xiàng)集,中間產(chǎn)生大量候選集,對這些候選集要進(jìn)行統(tǒng)計(jì)并剪枝,運(yùn)算量大;通過多次試驗(yàn)發(fā)現(xiàn):