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

　　

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