[[alternative]]一個多項目集的混合循序樣式探勘演算法

碩士[[abstract]]在資料探勘研究中，循序樣式探勘為重要的探勘問題，目的是從原始資料發生時間作為資料前後順序之依據，找到出現次數超過使用者設定門檻值之頻繁循序樣式。依據循序樣式中，相鄰項目於各個交易之間是否為相鄰情況下，可分為連續、非連續和混合循序樣式三種，根據過去混合循序樣式探勘研究，我們發現探勘其樣式的交易內容都是以一個項目為主，而缺少多項目集的研究。我們提出一個新的演算法MIHSPM(Multiple Itemset Hybrid Sequential Pattern Mining Algorithm)，找出多項目集的混合循序樣式。 MIHSPM演算法有以下四個步驟:1. 掃描資料庫，產生一階頻繁樣式。2. 建立一階頻繁樣式的順序表格。3. 進行樣式順序表格合併，產生二階頻繁樣式。4. 以前序分割樣式順序表格，找出全部的混合循序樣式。 在實驗的部分，我們以模擬資料庫測試其演算法的效能及分析相關模擬參數之敏感度。最後，我們將MIHSPM演算法應用於糖尿病患之病歷資料探勘，病患之血糖的樣式演進型式，以供推測血糖樣式變化之原因。[[abstract]]Sequential pattern mining is an important research topic at data mining. Its main purpose is to find out serial patterns according to orders in occurrence time with frequency exceeding user defined threshold. Based on whether consecutive items in sequential patterns should also be consecutive in the transactions, it could be classified into the following three categories: The first is continuous patterns; the second is discontinuous patterns; the third is hybrid patterns that combine both continuous patterns and discontinuous patterns. Transaction contents of sequential patterns in previous researches are for a single item. We propose a new algorithm, MIHSPM, to find multiple item set hybrid sequential patterns. The four steps of MISHPM are as follows: 1. Scan database to generate frequent length-1 patterns. 2. Build pattern order table of frequent length-1 patterns. 3. Join all pattern order tables to generate frequent length-2 patterns. 4. Partition pattern order tables according pattern''s prefixes and recursively join pattern order tables. We use synthetic databases to test our algorithm''s performance and analyze the sensitivity of related parameter. Finally, we apply our algorithm to mining anamnesis records of diabetes patients, and find out frequent glucose evolution patterns.[[tableofcontents]]目錄 第1章 緒論 1 1.1 研究背景與動機 1 1.2 研究目的 7 1.3 論文架構 7 第2章 文獻探討 9 2.1 探勘資料集特性 9 2.2 探勘循序樣式類型 9 2.2.1. 相似樣式探勘(Finding similar patterns) 10 2.2.2. 週期性樣式探勘(Finding periodic patterns) 10 2.2.3. 常見樣式探勘(Finding frequent patterns) 10 2.2.4. 循序樣式維護(Incremental mining of sequential patterns) 13 2.3 探勘方法(Mining approach) 13 2.3.1. 候選樣式產生與測試方法 13 2.3.2. 樣式成長方法 21 2.3.3. 找出最大項目集循序樣式方法 23 2.3.4. 記憶體索引探勘方法 24 2.3.5. 多支持度的探勘方法 24 2.3.6. 加入正規化表示(regular expression)式探勘方法 25 2.4 目前循序樣式探勘的應用 25 第3章 MIHSPM演算法 26 3.1 演算法定義 27 3.2 掃描資料庫，產生一階頻繁樣式 34 3.3 建立全部一階頻繁樣式的順序表格 34 3.3.1. 順序表格資料結構 35 3.3.2. 順序表格建立 35 3.4 進行樣式順序表格合併，產生二階頻繁樣式 37 3.5 以前序分割全部資料庫，找出所有的混合循序樣式 42 3.6 MIHSPM混合循序樣式與SPADE演算法之比較 46 3.6.1. 頻繁樣式討論與比較 47 3.6.2. 演算過程候選樣式個數討論與比較 48 3.7 二階候選樣式產生討論 50 第4章 完全性證明 52 第5章 實驗 56 5.1 實驗環境和產生交易序列資料庫 56 5.2 實驗數據與討論 57 第6章 MIHSPM應用於糖尿病患資料探勘 64 6.1 糖尿病介紹 64 6.2 資料說明 66 6.3 資料刪除 67 6.4 資料篩選 68 6.5 資料轉換 68 6.6 應用MIHSPM進行探勘 69 6.7 探勘結果樣式分析與解釋 70 第7章 結論 72 圖目錄 圖1. 循序樣式探勘類型 10 圖2. SPADE探勘過程所形成的晶格 18 圖3. GFP2中的候選樹 20 圖4. GFP2中的補償串列 20 圖5. MIHSPM演算法虛擬碼 33 圖6. MIHSPM演算法流程圖 34 圖7. 建立一階頻繁樣式順序表格函數 37 圖8. 表生二階候選樣式之順序表格合併 39 圖9. MIHSPM的generate-frequent-long-sequences函數 40 圖10. 順序樣式表格合併pot_join函數 41 圖11. 前序樣式集合分割(樣式長度為2) 42 圖12. 前序樣式集合分割(樣式長度為3) 43 圖13. 產生三階候選樣式之順序表格合併 45 圖14. 交易序列數和執行時間的比較 58 圖15. 執行時間和項目種類個數的比較 59 圖16. 樣式個數和樣式種類個數的比較 59 圖17. 執行時間和交易序列長度的比較 60 圖18. 樣式個數和交易序列長度的比較 61 圖19. 各長度樣式個數在不同交易長度的分佈 61 圖20. 執行時間和交易項目個數的比較 62 圖21. 樣式個數和交易項目個數的比較 62 圖22.各長度樣式個數在不同交易項目個數的分佈 63 表目錄 表1. 範例資料庫 14 表2. 轉換後的顧客序列資料庫 14 表3. 大型項目集轉換表 15 表4. 轉換大型項目集後的顧客序列資料庫 15 表5. AprioriALL演算法探勘表4資料庫的過程pass1 15 表6. AprioriALL演算法探勘表4資料庫的過程pass2 15 表7. AprioriALL演算法探勘表4資料庫的過程pass3 16 表8. AprioriALL演算法探勘表4資料庫的過程pass4 16 表9. 根據表1所建立的各項目出現的位置 17 表10. 以前序分割的等價類別 EC={} 18 表11. 以前序分割的等價類別(EC)合併 EC={30, 40} 18 表12. 根據表2的資料庫建置的投影資料庫以及循序樣式 23 表13. 循序樣式演算法特性比較 27 表14. 顧客交易資料庫 28 表15. 根據表14探勘出的一階頻繁樣式(minSupp=2) 35 表 16. 根據表14和表15.建立一階頻繁樣式順序表格 35 表17. 長度為1的樣式合併情況 38 表18. 合併產生長度為3的候選樣式 43 表 19. 頻繁樣式比較表 47 表 20. 產生候選樣式比較表 48 表21. 模擬資料庫的參數說明 56 表22. 實驗資料庫參數 57 表23. 糖尿病血糖測量標準(單位:mg/dl) 66 表24. 糖尿病資料集記錄格式 66 表25. 檢查項目碼對照表 67 表26. 血糖檢查項目碼對照表 69 表27. 胰島素檢查項目碼對照表 69 表28. 糖尿病病患資料探勘數據 70 表29. 糖尿病患資料探勘結果 70[[note]]學號: 694520254, 學年度: 9