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