資源描述：
《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)：
