交易型資料庫之跨交易關聯規則探勘之研究

摘要

在本論文中，我們著重於如何設計一個有效率的演算法在跨交易關聯規則上，例如：週期型樣（Periodic Patterns）、頻繁事件序（Frequent Episodes）、頻繁連續事件（Frequent Continuities）及序列型樣（Sequential Pattern）。首先，我們提出了一個三個步驟的FITS模組用於跨交易關聯規則的探勘上。並且，我們結合了垂直和水平資料格式的優點來改善探勘的效能，我們稱之為「雙格式表示法」。此外，根據我們觀察，我們發現「若一個交易內型樣不為緊密的型樣，亦不可能為一個跨交易的緊密的型樣」。因此，我們運用這個策略於FITS模組，在第一步驟中先探勘緊密的交易內頻繁型樣，然後再進行緊密跨交易的頻繁型樣之探勘工作。我們稱此概念為「雙壓縮策略」。從實驗中，我們發現這策略結合FITS模組在跨交易的緊密型樣探勘上更可減少型樣列舉的個數。此外，FITS模組只要經由些徵的修改即可用於其他的跨交易型樣探勘上。在一系列的實驗中，我們證明了我們所提出的模組無論在通用性上及效能上皆優於先前的研究。雖然在記憶體用量上，我們可能會比先前的方法來的多。但是，只要透過適當的資料切割方式，不僅可減少記憶體的用量，同時在效能上仍然優於先前的研究。雖然FITS模組可運用於週期型樣的探勘上。但由於週期型樣有特定的週期限制，因此FITS模組運用於週期型樣效能上並不理想。基於這個理由，我們為週期型樣設計一個嶄新的SMCA模組。這模組包含了四個子模組，分別為SPMiner（單一週期型樣探勘）、MPMiner（多事件週期型樣探勘）、CPMiner（複雜週期型樣探勘）及APMiner（非同步週期型樣探勘）。SPMiner主要的概念是利用雜湊表快速的計算出有效週期片斷的資訊。而其餘的三個子模組則是利用一個「以週期片斷為基礎」的組合方式來進行型樣的列舉過程。在相關的時間及空間複雜度分析中，皆顯示我們的SMCA模組在週期探勘上優於先前的方法。