Apriori算法分析和改進(jìn),基于Markov異常檢測(cè)模型

《Apriori算法分析和改進(jìn),基于Markov異常檢測(cè)模型》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、Apriori算法分析和改進(jìn)一Apriori算法介紹1.1Apriori算法思想Apriori算法的基本思想是:首先找出事務(wù)中所有的頻集,這些頻集出現(xiàn)的頻繁性需要大于或等于預(yù)先設(shè)定的最小支持度。隨后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則,這些規(guī)則必須大于最小支持度和最小可信度。為了生成所有頻集,使用了遞推的方法。1.2Apriori算法步驟1.制定最小支持度及最小置信度。2.對(duì)數(shù)據(jù)集所有事務(wù)進(jìn)行掃描,對(duì)每個(gè)項(xiàng)出現(xiàn)的次數(shù)計(jì)數(shù),刪除那些出現(xiàn)計(jì)數(shù)值小于閾值的項(xiàng)集,這樣就得到L1頻繁項(xiàng)集;3.利用頻繁1-項(xiàng)集合的結(jié)合,產(chǎn)生候選2-項(xiàng)集合C2(Candi－da

2、te2-itemset)。4.對(duì)C2中每個(gè)候選項(xiàng)集的支持計(jì)數(shù),確定頻繁項(xiàng)集2-項(xiàng)集的集合L2,并利用這些頻繁2-項(xiàng)集合L2的結(jié)合,產(chǎn)生候選3-項(xiàng)集合C3。5.重復(fù)掃描數(shù)據(jù)庫(kù)產(chǎn)生更高層次的頻繁項(xiàng)集合,再結(jié)合產(chǎn)生下一級(jí)候選項(xiàng)集,直到窮盡數(shù)據(jù)集中的所有頻繁項(xiàng)集。Apriori算法描述如下:(1)C1={candidate1-itemsets};(2)L1={c∈C1

3、c.count≥minsupport};(3)For(k=2,Lk-1≠Φ,k++)//直到不能再生成最大項(xiàng)目集為止(4)Ck=sc_candidate(Lk-1);//生成

4、含k個(gè)元素的侯選項(xiàng)目集(5)foralltransactionst∈D//辦理處理(6)Ct=count_support(Ck,t);//包含在事務(wù)t中的侯選項(xiàng)目集(7)forallcandidatesc∈Ct(8)c.count=c.count+1;(9)next(10)Lk={c∈Ck

5、c.count≥minsupport};(11)next(12)resultset=resultset∪Lk其中,D表示數(shù)據(jù)庫(kù),minsupport表示給定的最小支持度,re－sultset表示所有最大項(xiàng)目集。1.3Apriori算法的不足在Ap

6、riori算法中候選項(xiàng)集是逐層產(chǎn)生,而產(chǎn)生此層的頻集,必須要掃描整個(gè)數(shù)據(jù)庫(kù)一次,然后再結(jié)合頻集產(chǎn)生下一層級(jí)的候選項(xiàng)集合,直到頻集無(wú)法結(jié)合產(chǎn)生候選項(xiàng)集。Apriori算法一定要等到掃描完整個(gè)數(shù)據(jù)庫(kù)后才做結(jié)合,因?yàn)樵趻呙璧倪^(guò)程中,有些候選項(xiàng)集在若干的區(qū)段中的支持度已大于等于使用者制定的最小支持度,因此在掃描這些若干個(gè)區(qū)段后,便可以找出頻集,并直接結(jié)合產(chǎn)生下一個(gè)層級(jí)的候選物項(xiàng)集?；谏鲜鲈?Apriori算法可能會(huì)存在下述問(wèn)題。(1)所挖掘的規(guī)則存在大量冗余。(2)因計(jì)算項(xiàng)過(guò)多而造成執(zhí)行能緩慢,主要的原因在于頻繁項(xiàng)集合產(chǎn)生過(guò)多的候選項(xiàng)集

7、,尤其是候選22項(xiàng)集的情況最為嚴(yán)重。二Apriori算法的典型改進(jìn)及其比較2.1FIS-ES算法FIS-ES算法對(duì)傳統(tǒng)集合操作進(jìn)行了擴(kuò)展,提出了基于擴(kuò)展集合操作的最大頻繁項(xiàng)集生成法FIS-ES,算法通過(guò)從數(shù)據(jù)庫(kù)中檢測(cè)是否有符合最小支持度要求的頻繁項(xiàng),并刪除該頻繁項(xiàng)的真子集,循環(huán)操作直到讀完數(shù)據(jù)庫(kù)中的記錄為止。該算法通過(guò)只保留最大的頻繁項(xiàng)集,從而壓縮了搜索空間、提高了數(shù)據(jù)挖掘的效率。2.2基于PCL模型的頻繁項(xiàng)集求解算法從近幾年頻繁項(xiàng)集挖掘算法的研究趨勢(shì)來(lái)看,為了提高算法的效率,提出了一系列的混合搜索策略和高效剪枝策略。在基于Apri

8、ori算法性質(zhì)基礎(chǔ)上,胡學(xué)鋼等在《基于剪枝概念格模型的頻繁項(xiàng)集表示及挖掘》一文提出了基于PCL模型的頻繁項(xiàng)集求解算法,改善了頻集挖掘算法的時(shí)空性能。2.3FP-DFS算法在文獻(xiàn)中作者以FP-tree為基本數(shù)據(jù)結(jié)構(gòu),首先通過(guò)新的搜索策略和剪枝策略,將事務(wù)數(shù)據(jù)庫(kù)D壓縮為內(nèi)存中的FP-tree,然后按照相反次序逐個(gè)處理項(xiàng)集中的項(xiàng)目,每次迭代得到以某個(gè)項(xiàng)目開頭的所有頻繁項(xiàng)集。從而提高算法的搜索效率,減少了對(duì)內(nèi)存的占用,算法的空間復(fù)雜性低。2.4使用概率的方法求候選頻繁項(xiàng)集的Apriori改進(jìn)算法針對(duì)Apriori算法存在的可能產(chǎn)生大量的候選

9、集的缺點(diǎn),該算法通過(guò)使用概率的方法估算任意數(shù)據(jù)項(xiàng)集同時(shí)出現(xiàn)的概率來(lái)求候選頻繁項(xiàng)集。首先創(chuàng)建數(shù)組來(lái)記錄各個(gè)屬性項(xiàng)獨(dú)立出現(xiàn)的概率,設(shè)定最小概率,得到m個(gè)多個(gè)頻繁1項(xiàng)集,由m個(gè)頻繁1項(xiàng)集的獨(dú)立出現(xiàn)概率,估算出任意兩個(gè)屬性項(xiàng)同時(shí)出現(xiàn)的概率,得到候選頻繁2項(xiàng)集,通過(guò)迭代,由候選頻繁數(shù)據(jù)項(xiàng)集的支持度求出頻繁項(xiàng)集。2.5基于事務(wù)地址索引表來(lái)約簡(jiǎn)事務(wù)的Apriori優(yōu)化算法針對(duì)Apriori算法需要重復(fù)地掃描數(shù)據(jù)庫(kù)的缺陷,基于事務(wù)地址索引表來(lái)約簡(jiǎn)事務(wù)的Apriori優(yōu)化算法提出使用一個(gè)有效約簡(jiǎn)事務(wù)數(shù)據(jù)庫(kù)中事務(wù)的策略對(duì)算法進(jìn)行優(yōu)化。該算法中給出了一個(gè)

10、有效約簡(jiǎn)事務(wù)的方法,就是通過(guò)創(chuàng)建事務(wù)地址索引表縮小了對(duì)事務(wù)數(shù)據(jù)庫(kù)記錄的搜索范圍,實(shí)現(xiàn)了分區(qū)域的快速定位,從而減少解空間,優(yōu)化了候選集的計(jì)數(shù)過(guò)程,一定程度上提高了Apriori算法的執(zhí)行效率,但是該算法還是需要對(duì)事務(wù)數(shù)據(jù)庫(kù)多次掃描。2.