【導(dǎo)讀】北京科技大學(xué)本科生畢業(yè)設(shè)計（論文）

　　

【正文】 數(shù)據(jù)庫 北京科技大學(xué)本科生畢業(yè)設(shè)計（論文） 25 AIS算法 當(dāng)數(shù)據(jù)庫被掃描時，候選集被產(chǎn)生并計數(shù)，每讀一個事務(wù)，決定上次掃描找到的頻繁集中有哪些包含在事務(wù)中。通過事務(wù)中的其它 項目來擴(kuò)展這些頻繁集，從而得到新的候選集，這些候選集被加到掃描的候選集中，或者增加其相應(yīng)的計數(shù)。這個算法有個很大的缺陷就是產(chǎn)生過多的小候選，因此效率非常低。 APRIORI算法 Apriori 算法是一種最有影響的挖掘關(guān)聯(lián)規(guī)則的算法，它使用了頻繁項集的所有非空子集都必須是頻繁集的這一性質(zhì)。其基本思想是：掃描數(shù)據(jù)庫一遍統(tǒng)計各數(shù)據(jù)項，從而找出頻繁 1項集 1L ，然后利用 1L 來挖掘 2L ，即頻繁 2項集 ； 不斷如此循環(huán)下去直到無法發(fā)現(xiàn)更多的頻繁 k項集為止，每挖掘一層 Lk 就需要掃描整個數(shù)據(jù)庫一遍。利用1Lk? 來獲得 Lk 主要包含兩個步驟，即連接和刪除操作。①連接步驟。為發(fā)現(xiàn) Lk ，可以將 1Lk? 中兩個項集相連接以獲得一個 Lk 的候選集 kC 。 設(shè) 1l 和 2l 為 1kL? 中的兩個項集 (元素 )，記號 ??Jil? 表示 il 中的第 J 個項，假設(shè)交易數(shù) 據(jù)庫中各交易記錄中各項均已 按字典排序，若 h 和 l:中的前 k2 項是相同的， 也就是說若有? ? ? ? ? ?1 2 1( 1 2 ) ( 2 )l l l k? ? ???? ? ?? ? ?12( 1 1 )l k l k? ? ? ?，則 kl 中 1l 和 2l 的內(nèi)容就可以連接到一起。 ②刪除步驟。 kC 是 kL 的一個超集，其中的各元素 (項集 )不一定都是頻繁項集，但所有的頻繁 k項集一定 都在 }k 中，即有 kkLC? 掃描一遍數(shù)據(jù)庫就可以決定 kC 中各候選項集 (元素 )的支持頻度，并由此獲得 kL 中各個元素 (頻繁 k項集 )。其具體步驟如圖 。 利用 3L 來獲得候選 4項集 4C 。雖然所獲得 4C 為 {{I1， I2， I3,I5}}。但由于 {I 1，I2， I3,I5}的支持頻度小于最小支持閾 值，因此從 4C 中除去 {I1,I2,I3,I5}，從而得到 4C 。至此， Apriori 算法由于無法發(fā)現(xiàn)新的項集而結(jié)束。 該算法在產(chǎn)生候選項目集的時候只用到前一次迭代所產(chǎn)生的頻繁項目集，而沒有考慮數(shù)據(jù)庫中的事務(wù)，同時還使用了連接和刪除技術(shù)，這樣就會產(chǎn)生比 AIS 算法少的候選集。該算法能夠比較有效地產(chǎn)生關(guān)聯(lián)規(guī)則，但也存在著以下缺陷 :①算法產(chǎn)生太多冗余的規(guī) 則。當(dāng)數(shù)據(jù)庫太大或支持度、信任度閾 值太低時產(chǎn)生的規(guī)則太多。②算法在效率上存在著問題。主要是因為數(shù)據(jù)庫掃描次數(shù)太多，尋找每個 k項集都需要掃描數(shù)據(jù)庫一北京科技大學(xué)本科生畢業(yè)設(shè)計（論文） 26 次，共需要掃描數(shù)據(jù)庫 k 次。另外，當(dāng)模式太長時產(chǎn)生的候選項目集也多得讓人無法接受。 由于以上原因，人們對 Apriori 算法進(jìn)行了一定的改進(jìn)，希望能夠在提高算法的可靠性、高效性及擴(kuò)展性等方面做一些工作 ： 基于采樣的方法 。該方法主要思想是 ： 隨機(jī)地選取一些樣本數(shù)據(jù)集，使用這些樣本發(fā)現(xiàn)關(guān)聯(lián)規(guī)則，然后用數(shù)據(jù)庫中剩余的部分檢驗并修正得到的結(jié)果。該方法不但能夠減少數(shù)據(jù)庫掃描 的次數(shù)，而且能夠減少 CPU 和 I/O 負(fù)擔(dān)，在執(zhí)行 效率上有很大提高。由于數(shù)據(jù)庫規(guī)模的急劇膨脹，人們認(rèn)為取樣數(shù)據(jù)庫使用其中一部分的數(shù)據(jù)發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的思想是提高算法性能和擴(kuò)展性的一個好的方法。但是該方法存在一個很大的缺點(diǎn)就是產(chǎn)生的結(jié)果不精確，而且如何對數(shù)據(jù)庫進(jìn)行合理取樣而盡可能不丟失信息是目前人們已經(jīng)注意到，但尚未很好解決的公開問題。 北京科技大學(xué)本科生畢業(yè)設(shè)計（論文） 27 圖 25 Apriori 算法的具體挖掘過程 基于 Hash 的方法。由于 kC 中的候選集很多，所以在刪除步驟中所涉及的計算量 (時間 )是非常大的，為了減少 kC 的大小，就需要利用 Apriori 性質(zhì)，一個非頻繁 (k1)北京科技大學(xué)本科生畢業(yè)設(shè)計（論文） 28 項集不可能成為頻繁 k項集的一個子集。因此若一個候選 k項集中任一子集不屬于1kL? ，那么該候選 k項集就不可能成為一個頻繁 k項集，因而也就可以將其從 kC 中刪去。該方法利用 Hash 表來保存所有頻繁項集。該技術(shù)可以大大壓縮要考察的 k項集，但是由于 Hash 表的內(nèi)存耗費(fèi)，算法對于稠 密、大數(shù)據(jù)庫的性能是一個值得考慮的問題。 基于劃分的方法。 Savaserve 等人設(shè)計了一個基于劃分 (partition)的算法，該算法只需要兩次數(shù)據(jù)庫掃描，以挖掘頻繁項集 (如圖 26)。第一遍，先把數(shù)據(jù)庫中的事務(wù)從邏輯上分成 n 個非重疊的部分，使得每個部分能夠放入內(nèi)存進(jìn)行處理，對每一部分找出其頻繁項集 (局部頻繁項集 )，然后匯總產(chǎn)生全局候選項集。第二遍掃描計算全局候選項集的全局支持度，以確定全局頻繁項集。該算法的正確性是由每一個可能的頻繁至少在一個分塊中是頻繁集保證的。該方法具有分布、并行的思想，同樣可以減 輕 CPU 和工/0 負(fù)擔(dān)，提高算法性能和可擴(kuò)展性。 圖 26 通過劃分挖掘 事務(wù)壓縮 (壓縮進(jìn)一步迭代掃描的事務(wù)數(shù) )一個基本的原理就是當(dāng)一個事務(wù)不包含長度為 k 的大項集，則必然不包含長度為 k +1 的大項集。從而我們就可以將這些事務(wù)移去，這樣在下一遍的掃描中就可以減少要進(jìn)行掃描的事務(wù)集的個數(shù)。 不產(chǎn)生候選挖掘頻繁項集算法 上面介紹的是基于 Apriori 的頻繁項集挖掘方法，在許多情況下， Apriori 算法及其優(yōu)化采用候選、檢驗的方法產(chǎn)生關(guān)聯(lián)規(guī)則。然而，它有一些固有的缺陷并非是微不足道北京科技大學(xué)本科生畢業(yè)設(shè)計（論文） 29 的。當(dāng)支持度 閾 值太低或產(chǎn)生的模式長度太長時，基于候選項集的算法可能會浪費(fèi)很多不必要的花費(fèi)。例如，當(dāng)長度為 1 的頻集有 10000 個的時候，長度為 2 的候選集個數(shù)將會超過 10M，并累計和檢查它們的頻繁性。此外，如 果要生成一個很長的規(guī)則的時候，要產(chǎn)生的中間元素也是巨大的。再一個是它可能需要重復(fù)地掃描數(shù)據(jù)庫，通過模式匹配檢查一個很大的候選集合，然而，實際上事務(wù)數(shù)據(jù)庫是非常龐大的，所以每次迭代時產(chǎn)生候選項目集以統(tǒng)計其支持?jǐn)?shù)是非常耗時的，應(yīng)該盡量減少掃描數(shù)據(jù)庫的次數(shù)。下面介紹的 FPGrowth 算法和 DLG 算法就可以挖掘全部項集而不產(chǎn) 生候選并能減少數(shù)據(jù)庫的掃描次數(shù)。 FPGrowth 算法 FPGrowth 算法即頻繁模式增長算法采取分治策略：將提供頻繁項集的數(shù)據(jù)庫壓縮到一棵頻繁模式樹 (FP 一樹 )，但仍保留項集關(guān)聯(lián)信息，然后將這些壓縮后的數(shù)據(jù)庫分成一組條件數(shù)據(jù)庫 (一種特殊類型的投影數(shù)據(jù)庫 )，每個關(guān)聯(lián)一個頻繁項，并分別挖掘每個數(shù)據(jù)庫。該算法將原數(shù)據(jù)庫以高壓縮的方式 (FP 一樹 )存儲在內(nèi)存中，將原來從磁盤的讀取工作直接放入內(nèi)存中進(jìn)行，內(nèi)存中數(shù)據(jù)的存取比在磁盤中快數(shù)萬倍。 FPtree 的定義如下： ①它有一個標(biāo)記為“ null”的根節(jié)點(diǎn)，它 的子節(jié)點(diǎn)為一個項前綴子樹 (item prefix subtree)的集合，還有一個頻繁項 (frequent item)組成的頭表 (header table)。 ②每個項前綴子樹的節(jié)點(diǎn)有三個域 :itemname, count, node_ link 。 itemname 記錄了該節(jié)點(diǎn)所代表的項的名字： count 記錄了所在路徑代表的交易 (transaction)中達(dá)到此節(jié)點(diǎn)的交易個數(shù) :node_ link 指向下一個具有同樣的 itemname 域的節(jié)點(diǎn)，要是沒有這樣一個節(jié)點(diǎn)，就為 null。 ③頻繁項頭表 (frequent item header table)的每個表項 (entry)由兩個域組成 :itemname, node_ link。 node_ link 指向 FPtree。中具有與該表項相同 itemname 域的第一個節(jié)點(diǎn)。 FPGrowth 算法的主要步驟為 : ①掃描數(shù)據(jù)庫一次，產(chǎn)生頻繁 1項集，并得到它們的支持度計數(shù)。頻繁項的集合按支持度計數(shù)的遞減排序，用 L 表示。 北京科技大學(xué)本科生畢業(yè)設(shè)計（論文） 30 ②構(gòu)造 FP樹，首先，創(chuàng)建樹的根節(jié)點(diǎn)，用“ null”標(biāo)記。第二次掃描數(shù)據(jù)庫。每個事務(wù)中的項按 L 中的次序處理 (即按遞減支持度計數(shù)排序 )并對每個事務(wù) 創(chuàng)建一個分支。一般地，當(dāng)為一個事務(wù)考慮增加分枝時，沿共同前綴上的每個節(jié)點(diǎn)的計數(shù)增加 1，為跟隨在前綴之后的項創(chuàng)建節(jié)點(diǎn)并鏈接。為方便樹遍歷，創(chuàng)建一個項頭表，使得每個項通過一個節(jié)點(diǎn)鏈指向它在樹中的出現(xiàn)。這樣，數(shù)據(jù)庫頻繁模式的挖掘問題就轉(zhuǎn)換成挖掘FP 一樹問題。 ③ FP 一樹挖掘如下：由長度為 1 的頻繁模式 (初始后綴模式 )開始，構(gòu)造它的條件模式基 (一個“子數(shù)據(jù)庫”，由 FP樹中與后綴模式一起出現(xiàn)的前綴路徑組成 )。然后構(gòu)造它的 (條件 )FP 一樹，并遞歸地在該樹上進(jìn)行挖掘。模式增長通過后綴模式與由條件 FP樹產(chǎn)生的頻繁模式連接 實現(xiàn)。 FP增長方法將發(fā)現(xiàn)長頻繁模式的問題轉(zhuǎn)換成遞歸地發(fā)現(xiàn)一些短模式，然后連接后綴。它使用最不頻繁的項作后綴，提供了好的選擇性，該方法大大降低了搜索開銷。 DLG 算法 DLG 算法共有三步： 第一步 :掃描數(shù)據(jù)庫一遍，統(tǒng)計每一個項目出現(xiàn)的次數(shù)，且為每一個項目建立比特向量，每個比特向量的長度 是數(shù)據(jù)庫中事物 的數(shù)目。如果一個項目在第 i 個事物中出現(xiàn)， 則該項目的比特向量的第 i 個比特置 1，否則就置 0,與項目 i 相關(guān) 的比特向量表示為 iBV ， iBV 中“ 1”的數(shù)目就是包含項目 i 的事務(wù)數(shù)。就前面給出的數(shù)據(jù)庫 ：1BV =(1DD11D111)， 2BV =(1111D1D11)， 3BV = (DD1D11111)， 4BV =(D1DIDDDDD), 5BV =(1DDDDDDID)。頻繁 1項目集 L =｛ 1,2,3,4,5｝。 第二步 :構(gòu)造關(guān)聯(lián)圖，用以表示頻繁項目之間的關(guān)聯(lián)。對于關(guān)聯(lián)圖來說，如果()ijBV BV i j??中“ 1”的數(shù)目不小于最小支持?jǐn)?shù)，則構(gòu)造一條從項目 i 到項目 J 的有向邊，而且項目 {i, j}是一個頻繁 2 一項集，給出數(shù)據(jù)庫的關(guān)聯(lián)圖如圖 27 所示，且頻繁2項集為 ? ? ? ? ? ? ? ? ? ? ? ?? ?2 1 , 2 1 , 3 1 , 5 2 , 3 2 , 4 2 , 5L ? 。 第三步 :基于關(guān)聯(lián)圖產(chǎn)生頻繁 k項集 (k 2) ， DLG 算法用 k項目集的最后項來擴(kuò)展項目集為 (k +1)項集。設(shè) ? ?12,ki i i??? 是一個頻繁 k項集，如果在關(guān)聯(lián)圖中有一條從 ki 到北京科技大學(xué)本科生畢業(yè)設(shè)計（論文） 31 ui 。的有向邊，那么項目集 ? ?12,ki i i??? 被擴(kuò)展為 (k +1)項目集。如果12i i ik uBV BV BV BV? ? ???? ?中“ 1”的數(shù)目不小于最小支持度，那么 ? ?12,ki i i??? 是頻繁(k+1)項目集。依次執(zhí)行直到不能產(chǎn)生新的頻繁項目集。對頻繁 2項集 {1, 2}來說，在關(guān)聯(lián)圖中項目 2 到項目 3 有一條有向邊，所以 {1, 2}可以被擴(kuò)展為 {1, 2, 3}，1 2 3BV BV BV?? (即 (000000011))中“ 1”的數(shù)目為 2, 不小于最小支持?jǐn)?shù)，所以 {1, 2, 3}是一個頻繁 3項集。同樣可得 {1, 2, 5}也是頻繁 3項集。 3, 5 在關(guān)聯(lián)圖中不再指向其它項，所以 {1, 2, 3}和 {1, 2, 5}都不能再擴(kuò)展，算法終止。 圖 27 所給數(shù)據(jù)庫對應(yīng)的關(guān)聯(lián) 北京科技大學(xué)本科生畢業(yè)設(shè)計（論文） 32 第三章 中醫(yī)醫(yī)案分析系統(tǒng)的實施及結(jié)果分析 中醫(yī)醫(yī)案分析系統(tǒng)是在 Windows XP (CPU 為 P41600MHz，內(nèi)存為 256M)平臺上，Access2020 和 Visual BAS 工 C6. 0 的環(huán)境下，基于當(dāng)今最前沿的數(shù)據(jù)挖掘技術(shù)實現(xiàn)的。本研究按照數(shù)據(jù)挖掘的程序、要求和基本方法對其進(jìn)行處理，試圖探索數(shù)據(jù)挖掘在名老中醫(yī)用藥規(guī)律研究中的方法意義和應(yīng)用策略?；谠紨?shù)據(jù)的可靠性、準(zhǔn)確性和完整性方面的考慮， 本研究以自 2020 年 1 月一 2020 年 10 月 中國中醫(yī)研究院基礎(chǔ)所胸痹急癥研究室主任、國家中醫(yī)藥管理局醫(yī)政司胸痹急癥協(xié)作組組長沈紹功 先生醫(yī)案 65 份為醫(yī)案來 源，以高血壓病為例，采用 Apriori 算法進(jìn)行頻繁項集的搜索，所得醫(yī)案模型幾乎完全符合沈教授在治療高血壓病時常用的處方。 該系統(tǒng)具有如下主要用途 :①依據(jù)數(shù)據(jù)挖掘技術(shù)中數(shù)據(jù)預(yù)處理的要求對中醫(yī)醫(yī)案進(jìn)行錄入 。②對醫(yī)案進(jìn)行查詢 。③應(yīng)用數(shù)據(jù)挖掘算法對用藥規(guī)律進(jìn)行關(guān)聯(lián)挖掘分析 (包括辨證用藥分析、辨病用藥分析和對癥用藥分析 )。 系統(tǒng)體系結(jié)構(gòu) 中醫(yī)醫(yī)案分析系統(tǒng)以門診醫(yī)案為數(shù)據(jù)源，通過數(shù)據(jù)清洗、轉(zhuǎn)換、匯總、抽取等技術(shù)手段，構(gòu)建數(shù)據(jù)集市，在數(shù)據(jù)集市的基礎(chǔ)上，利用數(shù)據(jù)挖掘技術(shù)，構(gòu)造中醫(yī)醫(yī)案模型。中醫(yī)醫(yī)案分析系統(tǒng)的體系結(jié) 構(gòu)分為兩個部分，如圖 38 所示。第一部分是醫(yī)案的錄入、查詢、刪除部分，該部分為中醫(yī)醫(yī)案分析系統(tǒng)提供原始數(shù)據(jù) 。第二部分是該系統(tǒng)的核心部分，該部分首先將第一部分的原始數(shù)據(jù)經(jīng)過清洗、轉(zhuǎn)換、抽取、匯總，裝載到數(shù)據(jù)集市，然后以數(shù)據(jù)集市