Apriori算法的改進(jìn)及應用

實(shí)踐與經(jīng)驗Apriori算法的改進(jìn)及應用葉福蘭1施忠興(1.福州外語(yǔ)外貿職業(yè)技術(shù)學(xué)院計算機信息系,福州350018;2福州外語(yǔ)外貿職業(yè)技術(shù)學(xué)院圖書(shū)館,福州350018)摘要:描述Apon算法并指出其缺點(diǎn),提出利用哈希技術(shù)及壓縮組合項集技末對 Apriori算法進(jìn)行改進(jìn),結合實(shí)例詳蛔介紹改進(jìn)的基本思想及具體過(guò)程,利用實(shí)驗對改進(jìn)算法的效率進(jìn)行分析,提出改進(jìn)算法在圖書(shū)館個(gè)性化服務(wù)中的應用關(guān)鍵詞:Apon算法;改進(jìn);個(gè)性化服務(wù)1 Apriori算法描述及缺點(diǎn)有事務(wù)中出現的概率是期望置信度;而Y在有Ⅹ出Apriori算法是第一個(gè)關(guān)聯(lián)規則挖掘算法,它開(kāi)創(chuàng )現的事務(wù)中出現的概率是置信度,通過(guò)置信度對期望性地使用基于支持度的剪枝技術(shù),系統地控制候選項置信度的比值反映了在加入“X出現”的條件后,Y的集指數增長(cháng),是最有影響的挖掘布爾型頻繁項目集的出現概率發(fā)生了多大的變化。在上例中作用度為70%算法,是所有關(guān)聯(lián)規則挖掘算法的核心,其基本思想20%=3.5。是重復掃描數據庫,根據一個(gè)頻繁集的任意子集都是定義3由關(guān)聯(lián)挖掘到相關(guān)性分析頻繁集的原理,可以從長(cháng)度為k的頻繁集迭代地產(chǎn)生大部分關(guān)聯(lián)規則挖掘算法都使用支持度-置信度長(cháng)度為k+的候選集,再掃描數據庫以驗證其是否為框架。盡管最小支持度和置信度閾值能夠排除大量無(wú)頻繁集。趣的規則,但是仍然會(huì )產(chǎn)生一些用戶(hù)不感興趣甚至是Aprior算法在數據挖掘中具有里程碑的作用,但誤導的關(guān)聯(lián)規則。是存在著(zhù)以下缺點(diǎn)如果P(AUB)=P(AP(B),項集A的出現依賴(lài)于(1)頻繁掃描事務(wù)數據庫;(2)不適于大型數據庫項集B的出現。A與B出現的相關(guān)性由下式度量:的關(guān)聯(lián)規則挖掘;(3)不適于稠密集的關(guān)聯(lián)規則挖掘PuB) PA PBCOTAR(1)(4)可能生成的關(guān)聯(lián)規則過(guò)于龐大;(5) Apriori算法的若corA<1則負相關(guān);cor=1則獨立(沒(méi)有相關(guān)適應面較窄。性); ctAb>1則正相關(guān)(一個(gè)出現蘊涵另一個(gè)的出2相關(guān)概念現)。定義1期望置信度( Expected Confidence)3對減少計算支持度計數的工作量上的改進(jìn)設事務(wù)T中有e%的事務(wù)支持項集Y,e%稱(chēng)為關(guān)聯(lián)規則=>Y的期望置信度。期望置信度描述了在沒(méi)31相關(guān)性質(zhì)有任何條件影響時(shí),Y在所有事務(wù)中出現的概率有多性質(zhì)1對于一個(gè)k-項集I,若包含I1,r2],…I大。如果某天共有1000個(gè)顧客到商場(chǎng)購買(mǎi)物品,其中k1的事務(wù)集合分別為T(mén)Tn,…,T,則包含I的|有200個(gè)顧客購買(mǎi)了牛奶,則上述的關(guān)聯(lián)規則的期望事務(wù)集合為T(mén)。置信度為20%。性質(zhì)1說(shuō)明包含一個(gè)項集的事務(wù)集合等于包含定義2作用度(Iif)該項集的元素的事務(wù)的交集,因此我們只要知道所有作用度是置信度與期望置信度的比值。作用度描包含項的事務(wù),就可以求出包含該項集的事務(wù),進(jìn)而述X的出現對Y的出現有多大的影響。因為Y在所知中國煤化工收稿日期:2009-07-02修稿日期:2009-08-25CNMHG作者簡(jiǎn)介:葉福蘭(1981-),女,研究生,研究方向為數據挖掘MODERN COMPUTER 2009.995實(shí)踐與經(jīng)驗3.2改進(jìn)算法的基本思想表2哈希表(1)首先,逐個(gè)掃描事務(wù)數據庫,產(chǎn)生1-項候選支持度計數集合C1,在掃描每個(gè)事務(wù)時(shí),除了記錄包含該項的事TTA TTT,務(wù)編號外,還要對每個(gè)項計數。這樣掃描完一遍數據庫后,得到的候選集C1中,每個(gè)項集都包含一個(gè)相應的事務(wù)編號列表及對應的事務(wù)數,用哈希表來(lái)表示該項的支持度計數即為該項所包含的事務(wù)數。哈希表的結構為:(項集 Item set,事務(wù)標識符列表 Tid list,支表3頻繁1-項集L1持度計數 support);(2)從C1中刪除不滿(mǎn)足最小支持支持度計數度計數項集,得到L;(3)L41進(jìn)行自然連接,生成C,對C的計數根據性質(zhì)1利用C1求得。對于2-項集L的生成,無(wú)須掃描事務(wù)數據庫只要掃描哈希表第i行和第j行中相同元素的個(gè)數若要計算K-項集[LJ…l}的支持度計數,只要掃描對于2-項集的生成,由頻繁1-項集自然連接生Hash表中第,k行相同元素個(gè)數即可。成2-項集,對于2-項集中各項的支持度計數只需判由此可見(jiàn),此方法在計算支持度計數時(shí),只需掃斷項中元素所在行的公共事件數目,即為支持度計數描Hash表的部分行,無(wú)需對Hash表全部掃描,也不值。例如2-項集(文學(xué),工業(yè)},只要在哈希表中掃描文需要掃描整個(gè)數據庫,從而使 Apriori算法的效率大學(xué)所在的行及工業(yè)所在行,找出相同的事務(wù)編號個(gè)大提高,實(shí)現高效挖掘頻繁項集的目的。數,因文學(xué)行中的事務(wù)編號為T(mén),T4T,工業(yè)行中的事33政進(jìn)算法舉例務(wù)編號為T(mén),TTT發(fā)現無(wú)公共事務(wù),所以(文學(xué)下面以具體實(shí)例說(shuō)明哈希表的構建過(guò)程及頻繁工業(yè)的支持度計數值為0同理可求出其他2-項集及項集的產(chǎn)生,表1是某高校讀者的借閱信息,設最小對應的支持度計數,結合最小支持度計數,得到頻繁支持度計數為3:2-項集,如表4所示表1讀者借閱信息表表4頻繁2一項集I2支持度計借聞1借2借網(wǎng)3借閔4高數候選3項集的生成由I2直接連接而成,各項的支算機■■外迅業(yè)外持度計數為各項所在行的公共事務(wù)數,結合最小支持業(yè)高數■綜合外訴度計數及先驗原理,得到頻繁3項集,如表5所示表5頻繁3-項集以讀者借閱圖書(shū)為依據,首先掃描讀者借閱信息現|數據庫,產(chǎn)生C,包含項集及對應的事務(wù)編號將其用匚持度計教高數,計算機,外語(yǔ)代|哈希表列出,表中各行元素為各圖書(shū)所在項的事務(wù)編計號,支持度計數為該行的事務(wù)數。例如高數出現在事4對減少頻繁項集的進(jìn)一步改進(jìn)務(wù) TIT3TtT,T9中,則高數行的元素為(TTTT事務(wù)數為5,即支持度計數為6。依此類(lèi)推,創(chuàng )建計算性質(zhì)2如果頻繁k-項集還能產(chǎn)生頻繁k+1項集總機,工業(yè),外語(yǔ)綜合,文學(xué)所在行的元素生成的哈希則頻繁k+1項集中包含某項的個(gè)數必大于或等于k。第表如表2所示。由性質(zhì)2,可以實(shí)現對該集中出現元素個(gè)數進(jìn)行計從表可得到1-項集,其中第(1≤i≤6項的支持數事中國煤化工個(gè)數不到k的話(huà)可以度計數為第i行元素的個(gè)數,并結合最小支持度計數CNM引起的所有組合。3得到頻繁1-項集C,如表3所示對支持度計數篩選得MODERN COMPUTER 2009.996實(shí)踐與經(jīng)驗到,要求某項在各項在L4中出現次數大于或等于k,置信度和作用度加以判斷分析,經(jīng)篩選得出的關(guān)聯(lián)規若小于k,則刪除該項并在L中刪除所有包含已經(jīng)淘則見(jiàn)表7所示汰掉的元素的事務(wù)記錄,處理過(guò)程如表6所示,步驟時(shí)間耗費(單位你)1中要求各項出現次數大于或等于1,步驟2中要求各項出現次數大于或等于2,例如(文學(xué)}與{工業(yè)在L2中出現的次數為1,則刪除{文學(xué))與(工業(yè)},并刪除L有包含這兩項的項(文學(xué),計算機與(工業(yè),外語(yǔ)}表6處理過(guò)程限頻L各在L肀幽現次傲「瓢集L計算機計算機事務(wù)集記錄數(單位:條文學(xué),計算機高數,計算機計算機圖1計算機,外語(yǔ){外語(yǔ)除(文學(xué)與1業(yè)})3■高數,計算機,外語(yǔ)」表7篩選得出的關(guān)聯(lián)規則5改進(jìn)算法與 Apriori算法的比較里信度期望置信度作用度通過(guò)上述介紹,可以看到改進(jìn)的算法與 Aprior算法的共同之處是通過(guò)掃描數據得到那些支持度不今界機外語(yǔ)小于用戶(hù)給定的最小支持度 Minsupport的頻繁項集規則高數,計算機]=>(外語(yǔ)},置信度為100%,作l4,不同之處在于:第一,改進(jìn)的算法首先將數據庫變用度為1.29,說(shuō)明高數,計算機)與{外語(yǔ)}是正相關(guān)換成了Hash表,因此,在計算支持度時(shí)僅需對k-項的,即讀者借閱高數,計算機圖書(shū)的同時(shí)有借閱外語(yǔ)集中出現的項進(jìn)行掃描,無(wú)需對整個(gè)Hash表掃描;第圖書(shū)的趨勢;規則(高數外語(yǔ)}=>(計算機的置信度雖二,改進(jìn)的算法在考慮組合候選項目集C前,對將參然為60%,作用度為09(小于1),這樣的關(guān)聯(lián)規則沒(méi)與組合的元素進(jìn)行計數處理,根據計數結果決定排除有意義;規則(計算機,外語(yǔ))=>{高數)的置信度為些不符合組合條件的元素,這就降低了組合的可能75%,作用度為1.35,說(shuō)明借閱計算機和外語(yǔ)的讀者性,直接減少了循環(huán)判斷的次數。很有可能再借高數;規則{高數=>(計算機,外語(yǔ))的置6算法實(shí)驗分析信度為60%,作用度為135,意味著(zhù)讀者借閱高數圖為了證實(shí)對 Apriori算法改進(jìn)后的效果,實(shí)驗采用書(shū)同時(shí)蘊涵再借計算機和外語(yǔ)的趨勢ⅡASS系統中的真實(shí)借閱數據,進(jìn)行圖書(shū)關(guān)聯(lián)性的挖參考文獻掘。在事務(wù)較少的情況下, Apriori算法的性能較好,但是隨著(zhù)事務(wù)數的增加,改進(jìn)的 Apriori算法的效率明顯[鮑靜.關(guān)聯(lián)規則挖掘及其在圖書(shū)流通數據中的應用研究?jì)?yōu)于未改進(jìn)的算法,兩種算法的效率比較如圖1所示。碩士學(xué)位論文合肥:合肥工業(yè)大學(xué),20072]姜晗.關(guān)聯(lián)規則的精簡(jiǎn)方法研究[碩士學(xué)位論文]浙江7改進(jìn)的 Apriori算法在圖書(shū)館個(gè)性化服浙江師范大學(xué),2005務(wù)中的應用廣武數據挖掘技術(shù)在教務(wù)管理系統中的應用碩士學(xué)計位論文]遼寧:遼寧科技大,2007預測讀者的信息需求,挖掘數據背后隱藏的信息李緒成,王保?？負P(guān)聯(lián)規則中Apio算法的一種改機掌握讀者借閱規律,是圖書(shū)館開(kāi)展個(gè)性化服務(wù)的基礎。進(jìn)計算機工程,2002,7(28):104-105讀者借閱數據經(jīng)過(guò)改進(jìn)的 Apriori算法過(guò)程,得5陸覺(jué)民,鄭字數據挖掘技術(shù)的改進(jìn)在圖書(shū)館個(gè)性化服務(wù)第到所需要的頻繁集I={高數,計算機,外語(yǔ)},可得對中國煤化工08,65-67應的關(guān)聯(lián)規則及相應的置信度,在此基礎上再給出置信度為55%對頻繁項目集產(chǎn)生強關(guān)聯(lián)規則,并以期望a yHsCNMHG厘系統中的應用碩士學(xué)川人于,∠(下轉第126頁(yè))MODERN COMPUTER 2009.9實(shí)踐與經(jīng)驗性,如何改善供應鏈各節點(diǎn)的脆弱性,如何更有效地降3王進(jìn)發(fā)李勵.軍事供應鏈管理.國防大學(xué)出版社2004低集中管理和數據共享帶來(lái)的安全風(fēng)險,軍隊后勤人[4]Sherbrooke, C.C., 1992, Optimal Inventory Modelling of才的培養等,這些在以后的工作中都需要進(jìn)一步研究。Systems: Multi-Echelon Techniques, Wiley, NewYork[5]Pyke, D F, 1990"Priority Repair and Dispatch Policies for參考文南Repairable Item Logistics System", Naval Researeh Lo-曾洪寧韓永生,楊青,基于供應鏈的企業(yè)應用集成研究gisties37, 1-30計算機應用研究,2007(增刊)6萬(wàn)杰寇紀淞,李敏強供應鏈中分配機制對牛鞭效應的[2]宋華.電子商務(wù)與電子供應鏈管理.人民大學(xué)出版社影響研究.系統工程學(xué)報,2002,172004Research on Logistics System IntegrationBased on Supply ChainHUANG SenLIU Feng(The Second Artillery Engineering University, Xi'an 710025)Abstract For currently the information island between users, begetter, depot and maintenance depart-and the demand forn,puts forward a descheme of integration which can improve the efficiency and save the outlay of logistics.(上接第97頁(yè))Improvement and Application of Apriori algorithmu-lanSHI Zhong-xing(1. Department of Computer Information, Fuzhou Technical College of Foreign Studies, Fuzhou 3500182. Library of Fuzhou Technical College of Foreign Studies, Fuzhou 350018)Abstract: Describes Apriori algorithm and pointes out its disadvantages and puts forward the use ofhash combination of technology and compression technology to Apriori itemset algorithmimprovements, combines with detailed examples to improve the basic idea and the specific第三一五期processes, analyzes the use of experiments foralgorithm proposed in the library of中國煤化工Keywords: Apriori Algorithm; Improvement; PersonalizedYHECNMHGMODERN COMPUTER 2009.9126