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