交易型資料庫之跨交易關聯規則探勘之研究; Mining Inter-Transaction Association Rules in Transactional Databases

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 博碩士論文 > Item 987654321/8733

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/8733

题名:	交易型資料庫之跨交易關聯規則探勘之研究;Mining Inter-Transaction Association Rules in Transactional Databases
作者:	黃國瑜;Kuo-Yu Huang
贡献者:	資訊工程研究所
关键词:	關聯規則;交易型資料庫;時序型樣;資料探勘;Pattern Mining;Temporal Pattern;Transactional Databases;Association Rules;Data Mining
日期:	2006-01-09
上传时间:	2009-09-22 11:33:46 (UTC+8)
出版者:	國立中央大學圖書館
摘要:	在本論文中，我們著重於如何設計一個有效率的演算法在跨交易關聯規則上，例如：週期型樣（Periodic Patterns）、頻繁事件序（Frequent Episodes）、頻繁連續事件（Frequent Continuities）及序列型樣（Sequential Pattern）。首先，我們提出了一個三個步驟的FITS模組用於跨交易關聯規則的探勘上。並且，我們結合了垂直和水平資料格式的優點來改善探勘的效能，我們稱之為「雙格式表示法」。此外，根據我們觀察，我們發現「若一個交易內型樣不為緊密的型樣，亦不可能為一個跨交易的緊密的型樣」。因此，我們運用這個策略於FITS模組，在第一步驟中先探勘緊密的交易內頻繁型樣，然後再進行緊密跨交易的頻繁型樣之探勘工作。我們稱此概念為「雙壓縮策略」。從實驗中，我們發現這策略結合FITS模組在跨交易的緊密型樣探勘上更可減少型樣列舉的個數。此外，FITS模組只要經由些徵的修改即可用於其他的跨交易型樣探勘上。在一系列的實驗中，我們證明了我們所提出的模組無論在通用性上及效能上皆優於先前的研究。雖然在記憶體用量上，我們可能會比先前的方法來的多。但是，只要透過適當的資料切割方式，不僅可減少記憶體的用量，同時在效能上仍然優於先前的研究。雖然FITS模組可運用於週期型樣的探勘上。但由於週期型樣有特定的週期限制，因此FITS模組運用於週期型樣效能上並不理想。基於這個理由，我們為週期型樣設計一個嶄新的SMCA模組。這模組包含了四個子模組，分別為SPMiner（單一週期型樣探勘）、MPMiner（多事件週期型樣探勘）、CPMiner（複雜週期型樣探勘）及APMiner（非同步週期型樣探勘）。SPMiner主要的概念是利用雜湊表快速的計算出有效週期片斷的資訊。而其餘的三個子模組則是利用一個「以週期片斷為基礎」的組合方式來進行型樣的列舉過程。在相關的時間及空間複雜度分析中，皆顯示我們的SMCA模組在週期探勘上優於先前的方法。 In this dissertation, we focus on how to devise an efficient and effective algorithm for discovering inter-transaction associations such as, periodic patterns, frequent continuities, frequent episodes and sequential pattern. Firstly, we propose a 3-phase FITS model in inter-transaction association mining. We adopt both horizontal and vertical formats to increase the mining efficiency. Furthermore, we focus on the application of FITS to closed pattern mining to reduce the number of patterns to be enumerated. The insight is “If an intra-transaction pattern is not a closed pattern, it will not be a closed frequent inter-transaction pattern”. The bi-format and bi-phase reduction are applied to overcome the problem of the duplicate item extensions especially for closed pattern mining. We have applied the FITS model to all inter-transaction mining tasks with a little modification. Although the FITS model can be used for periodic pattern mining, it is not efficient enough since the constraints on periodicy are not fully utilized. Therefore, we propose a more general model, SMCA, to mine asynchronous periodic patterns from a complex sequence and correct some problem of the previous works. A 4-phase algorithm, including SPMiner, MPMiner, CPMiner and APMiner, is devised to discover periodic patterns from a transactional database presented in vertical format. The essential idea of SPMiner is to trace the possible segments for period p by a hash table. Besides, to avoid additional scans over the transactional database, we propose a segment-based combination to reduce redundant generation and testing. The experiments have demonstrated good performance of the proposed model on several inter-transaction patterns. Although the efficiency improvement is based on the requirement of additional memory cost, the memory cost can be further reduced by disk-based or partition-based approaches, which in turn also prove to be better than state-of-the-art algorithms. In summary, the proposed model can be orders of magnitude faster than previous works with a modest memory cost.
显示于类别:	[資訊工程研究所] 博碩士論文

文件中的档案:

档案	大小	格式	浏览次数

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....