李瑞庭臺灣大學：資訊管理學研究所羅子威Lo, Tzu-WeiTzu-WeiLo2007-11-262018-06-292007-11-262018-06-292006http://ntur.lib.ntu.edu.tw//handle/246246/54418隨著無線射頻識別技術的逐漸普及，預料市場上將會產生許多相關應用。因此，我們提出了一個在擁有無線射頻識別技術之商場內的應用。我們收集顧客購物時所走過的路徑以及最後所購買的商品，想要探勘頻繁購物路徑與頻繁商品集合的關聯法則。因此，在本篇論文中，我們提出了一個演算法來探勘頻繁購物路徑與頻繁商品集合的關聯法則。我們的演算法分為兩個階段。第一個階段，我們建立了一個對應圖形來記錄商場的感應器方格配置架構以及交易資料庫。第二階段，我們用深度優先搜尋法來搜尋這個對應圖形以產生頻繁購物路徑與頻繁商品集合的關聯法則。利用這個對應圖形來探勘頻繁購物路徑與頻繁商品集合的關聯法則，不會產生不必要的候選項目，花費更少的資料庫瀏覽次數，以及可以妥善的利用這個問題的特性--『一個感應器相鄰的感應器最多只有四個』。因此，我們所提出的方法較PrefixSpan的方法來的有效率。實驗結果顯示，我們所提出的方法比PrefixSpan的方法快上大約二至十倍。When the RFID technique is becoming popular, we expect there will be a lot of applications based on it. Thus, we design an application in a hypermarket with an RFID system. We collect the shopping paths and items of customers, and find the RFSPIs (Relationship between Frequent Shopping paths and items). Therefore, in this thesis, we propose an algorithm to mine the RFSPIs. Our proposed method consists of two phases. First, we construct a mapping graph to record the information of a grid sensor structure and a transaction database. Second, we traverse the mapping graph in the DFS manner to find the RFSPIs. By using the mapping graph to mine the RFSPIs, we don’t generate unnecessary candidates, need fewer database scans, and properly utilize the characteristic of the problem that a sensor has at most four neighboring sensors. Therefore, our proposed method is more efficient than the PrefixSpan-based method. The experiment results show that our proposed method outperforms the PrefixSpan-based method by one order of magnitude.Table of Contents i List of Figures ii Chapter 1 Introduction 1 Chapter 2 Related Work 6 Chapter 3 Problem Definition 8 Chapter 4 Our Proposed Algorithm 10 4.1 Construct the mapping graph 10 4.2 Graph-based mining algorithm 14 4.3 Discussion of cyclic path pattern 24 Chapter 5 Performance Analysis 25 5.1 Synthetic datasets 25 5.2 Performance evaluation 26 Chapter 6 Conclusions and Future Work 33 References 35406350 bytesapplication/pdfen-US資料探勘關聯法則序列型樣最大頻繁項目集合頻繁購物路徑與頻繁商品集合的關聯法則無線射頻識別技術data miningassociation rulessequential patternsmaximal frequent itemsetRFSPIRFIDotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54418/1/ntu-95-R93725027-1.pdf