談改進(jìn)的Ａｐｒｉｏｒｉ關(guān)聯(lián)挖掘算法的實(shí)踐應(yīng)用

1、談改進(jìn)的關(guān)聯(lián)挖掘算法的實(shí)踐應(yīng)用         09-08-02 10:59:00     作者：范生萬鮑靜    編輯：studa20內(nèi)容摘要：本文介紹了數(shù)據(jù)挖掘技術(shù)在圖書館中的應(yīng)用，并運(yùn)用改進(jìn)的Apriori關(guān)聯(lián)挖掘算法對安徽省圖書館自動(dòng)化系統(tǒng)中讀者流通庫進(jìn)行挖掘，并對挖掘出的結(jié)果及其意義進(jìn)行評價(jià)，從而為圖書館讀者管理、圖書資源的采購提供決策支持。 關(guān)鍵詞：數(shù)據(jù)挖掘 Apriori算法 圖書館管理 讀者管理 數(shù)據(jù)挖掘技術(shù)在商業(yè)領(lǐng)域內(nèi)

2、的應(yīng)用給圖書館帶來了很大的啟發(fā)。圖書館的數(shù)據(jù)庫可以運(yùn)用數(shù)據(jù)挖掘技術(shù)中的關(guān)聯(lián)規(guī)則分析、聚類分析、決策樹、時(shí)間序列分析等數(shù)據(jù)挖掘方法，以找出數(shù)據(jù)庫中蘊(yùn)藏的對于圖書館管理有用的潛在規(guī)則，并且通過描述和預(yù)測，為圖書館的圖書采購、讀者服務(wù)、館藏目錄設(shè)置等管理工作提供決策支持。 關(guān)聯(lián)規(guī)則是與多數(shù)人想象的挖掘過程中最相近的一種數(shù)據(jù)挖掘形式，即尋找在同一事件中出現(xiàn)的不同項(xiàng)的相關(guān)性。關(guān)聯(lián)規(guī)則的研究有助于發(fā)現(xiàn)數(shù)據(jù)庫中不同商品間的聯(lián)系，找出顧客購買行為模式。在圖書館運(yùn)用關(guān)聯(lián)規(guī)則分析可以細(xì)分出讀者群，根據(jù)其借閱情況提供不同的服務(wù)，為圖書館的管理決策提供參考。關(guān)聯(lián)規(guī)則的核心算法是Apriori算法。 關(guān)聯(lián)規(guī)則的基本概念

3、及算法 挖掘流通借閱事務(wù)數(shù)據(jù)庫中所有的關(guān)聯(lián)規(guī)則的問題可以被劃分成如下兩個(gè)子問題： 找出所有具有最小支持度的項(xiàng)集（即頻繁項(xiàng)集），可用Apriori算法來找出頻繁項(xiàng)集。由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，對于每一個(gè)頻繁項(xiàng)集I，找出其中所有的非空子集，然后，對于每一個(gè)這樣的子集a，如果support（I）與support（a）的比值大于最小置信度，則存在規(guī)則a=>（I-a）。 （一）關(guān)聯(lián)規(guī)則算法 關(guān)聯(lián)規(guī)則的挖掘主要是在數(shù)據(jù)庫中找出支持用戶指定的最小支持度S和最小置信度C的關(guān)聯(lián)規(guī)則，從而指導(dǎo)人們的一些管理決策。目前，關(guān)聯(lián)規(guī)則的挖掘方法主要是找出數(shù)據(jù)庫中的頻繁項(xiàng)集，然后由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則。 （二）Apr

4、ior算法 Apriori算法是一種挖掘布爾關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集的算法，它主要是利用逐層搜索的迭代方法來尋找數(shù)據(jù)庫中頻繁出現(xiàn)的項(xiàng)集。主要步驟是：第一步，產(chǎn)生頻繁1-項(xiàng)集L1，掃描數(shù)據(jù)庫D，出現(xiàn)在D中各個(gè)數(shù)據(jù)項(xiàng)的集合就是頻繁1-項(xiàng)候選項(xiàng)集C1，并統(tǒng)計(jì)出每個(gè)數(shù)據(jù)項(xiàng)出現(xiàn)的次數(shù)，次數(shù)大于最小支持計(jì)數(shù)（預(yù)先）定義的項(xiàng)的集合就是頻繁1-項(xiàng)集L1；第K步，產(chǎn)生頻繁K-項(xiàng)集Lk，利用上一步產(chǎn)生的頻繁（K-1）-項(xiàng)集Lk-1，與自己連接產(chǎn)生K-項(xiàng)集候選集Ck，掃描數(shù)據(jù)庫事務(wù)庫，計(jì)算Ck中每個(gè)成員出現(xiàn)的次數(shù)，將小于最小支持度的候選項(xiàng)刪除，最后產(chǎn)生頻繁K-項(xiàng)集。 算法：Apriori使用根據(jù)候選生成的逐層迭代找出頻繁

5、項(xiàng)集 輸入：流通借閱數(shù)據(jù)庫D；最要支持度閾值minsup 輸出：D中的頻繁項(xiàng)集L 算法代碼： 1）L1一所有頻繁項(xiàng)集1-項(xiàng)目集； 2）for（k=2；Lk，k+） 3）Ck=apriori_gen(Lk-1，minsupport） 4）for all CCt do 5）Ct=Subset（Ck，T） 6）For all cCt do 7）c.count+； 8） 9）Lk=cCk|support（c）>=minsup 10） 11）return L=所有的Lk Apriori算法的第1步找出頻繁1-項(xiàng)集的集合L1。在第210步中，Lk-1用于產(chǎn)生候選Ck，以找出Lk。Apriori過程產(chǎn)

6、生候選，第3步使用Apriori性質(zhì)刪除那些具有非頻繁子集的候選，第4步掃描數(shù)據(jù)庫，第5步使用subset函數(shù)找出事務(wù)中的候選的所有子集，第6步和第7步對每個(gè)這樣的候選累加計(jì)數(shù)。最后，所有滿足最小支持度的候選會(huì)形成頻繁項(xiàng)集L。 Apriori-gen過程 Apriori-gen過程由Lk-1產(chǎn)生第K次迭代時(shí)的候選項(xiàng)集Ck，該過程描述如下： For each itemset I1Lk-1 For each itemset I2Lk-1 If （I11=I21）(I12=I22（I1K-2=I2K-2）（I1K-1 =I2 K-2）（I1K-I=I2K-1） Then c=I1，I12，I1K-I

7、，I2K-1）； Ck=Ck U c； For（c的每個(gè)包含k-1個(gè)項(xiàng)目的子集s） If（s不屬于Fk-1） 從Ck中刪除C； Return（Ck）； 改進(jìn)的Apriori算法在圖書館的具體實(shí)現(xiàn) 以安徽省圖書館某年度讀者借閱事務(wù)庫為例，可從圖書館借閱記錄中挖掘出形如“讀者-圖書”強(qiáng)關(guān)聯(lián)規(guī)則。首先要進(jìn)行數(shù)據(jù)清洗，只保留屬性概念中分層最低層的屬性項(xiàng)，將同一個(gè)讀者的所有借閱記錄合并為一條記錄。 （一）算法思想 在讀者借閱記錄關(guān)聯(lián)規(guī)則挖掘過程中有一些特殊的性質(zhì)，因?yàn)槊恳粋€(gè)讀者借閱記錄的長度是固定的，即含有五個(gè)單項(xiàng)，前四個(gè)是屬性值，最后一個(gè)是圖書分類號(hào)，并且要挖掘的規(guī)則最后一項(xiàng)必須是圖書分類號(hào)，且不能出

8、現(xiàn)沖突的屬性值或圖書分類號(hào)?；谶@些特殊性質(zhì)，在數(shù)據(jù)挖掘中對Apriori改進(jìn)算法如下： 1）把壓縮過的事務(wù)集讀入內(nèi)存； 2）掃描事務(wù)集，找到每一類頻繁單項(xiàng)：即頻繁的年齡段、頻繁的學(xué)歷、頻繁的職稱、頻繁的職業(yè)、頻繁的圖書分類。 3） 把各類頻繁的屬性單項(xiàng)和頻繁的圖書分類單項(xiàng)連接成 2 - 候選頻繁項(xiàng)集， k = 2。即生成年齡-圖書類，學(xué)歷-圖書類，職業(yè)-圖書類，職稱-圖書類，分別生成頻繁2項(xiàng)集。 4） 檢查k-候選頻繁項(xiàng)集，記錄其支持度和前件的支持度。頻繁項(xiàng)集的連接條件是前n項(xiàng)是為讀者屬性項(xiàng)，且讀者的屬性項(xiàng)內(nèi)容各不相同，最后一項(xiàng)為相同的圖書分類項(xiàng)。 5） 輸出置信度和支持度達(dá)到要求的頻繁 k - 頻繁項(xiàng)集。置信度為支持度除以前件的支持度。 6） 用得到k - 頻繁項(xiàng)集互相連接得到k+1 - 候選頻繁項(xiàng)集。通過剪枝，可減少連接的頻繁項(xiàng)集的個(gè)數(shù)，提高程序運(yùn)行的效率。下面的是剪枝連接的規(guī)則： a） 如果頻繁項(xiàng)集A 和 B 最后一項(xiàng)不同的時(shí)候不能連接。 b） 含有屬于同一屬性類別的不同單項(xiàng)