FP-Tree不同實作方式之效能比較

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：3

、訪客IP：3.136.234.163

姓名

趙書榮(Shu-Jun Chao) 查詢紙本館藏

畢業系所

資訊管理學系

論文名稱

FP-Tree不同實作方式之效能比較
(FP-Tree in different implement methods to compare the performances)

相關論文

★ 零售業商業智慧之探討	★ 有線電話通話異常偵測系統之建置
★ 資料探勘技術運用於在學成績與學測成果分析 -以高職餐飲管理科為例	★ 利用資料採礦技術提昇財富管理效益 -以個案銀行為主
★ 晶圓製造良率模式之評比與分析－以國內某DRAM廠為例	★ 商業智慧分析運用於學生成績之研究
★ 運用資料探勘技術建構國小高年級學生學業成就之預測模式	★ 應用資料探勘技術建立機車貸款風險評估模式之研究－以A公司為例
★ 績效指標評估研究應用於提升研發設計品質保證	★ 基於文字履歷及人格特質應用機械學習改善錄用品質
★ 以關係基因演算法為基礎之一般性架構解決包含限制處理之集合切割問題	★ 關聯式資料庫之廣義知識探勘
★ 考量屬性值取得延遲的決策樹建構	★ 從序列資料中找尋偏好圖的方法 - 應用於群體排名問題
★ 利用分割式分群演算法找共識群解群體決策問題	★ 以新奇的方法有序共識群應用於群體決策問題

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

摘要
目前挖掘關聯規則的演算法可依需不需產生candidate itemset的作法分為兩類，例如Frequent-Pattern tree與Apriroi-like approach。此兩者最主要的差異在於，FP-tree並不產生candidate itemsets，它將資料庫壓縮在Frequent-Pattern tree的結構中，避免多次的高成本的資料庫掃瞄；後者是需要產生candidate itemset的方法。
而本文的目的是以應用Frequent-Pattern tree之理論，在實作方面以不同資料結構技術作效能比較測試，得到以那一種資料結構應用在Frequent-Pattern tree上執行時間之效能較佳。
在本文中共建立了(一)FP-tree_tail演算法，tail為在head table中增加一個tail欄位，(二)FP-tree_hash演算法，hash為以hash function計算出每個node所在位置方式建立FP-tree，(三)FP-tree_hash+tail演算法，為結合(一)、(二)之優點，所完成之演算法.，並將以上三個演算法與傳統FP-tree演算法一起比較，以找出各演算法之優缺點。經由本文實驗測試資料數據中，發現在各種實驗參數下，傳統FP-tree演算法所需花費之時間，為三個改良FP-tree演算法的數十倍。

摘要(英)

now the algorithm in the association rules can be seperated two kinds.first is Apriori-like approach.second is Frequent-Pattern tree.main different between the above is the Frequent-Pattern tree did not to generate the candidate itemsets.its avoid a huge cost to scan database many times.
this paper apply three different data structure(FP-tree_tail,FP-tree_hash,FP-tree_hash+tail) to improve Frequent-Pattern tree algorithm .then to compare the performance about them ,
accroding to the test data we found the performance of the FP-tree alogrithm are worst then the other algorithms many times.

關鍵字(中)

★ 資料挖掘
★ 關聯規則
★ 演算法
★ FP-tree

關鍵字(英)

★ data mining
★ association rule
★ algorithm
★ FP-tre

論文目次

目錄
第一章序論 1
第二章文獻探討 3
第三章研究動機 7
3．1 新增Head table 串列item問題 7
3．2 以樹狀結構建立Frequent Pattern Tree問題 10
第四章演算法 13
4．1 FP-tree_tail演算法 13
4．1．1 FP-tree_tail之node資料結構 13
4．1．2 Head node 結構 14
4．1．3 建立Head table Link程式 14
4．2 FP-tree_hash演算法 15
4．2．1 Hash table 容量大小 15
4．2．2 Hash function 15
4．2．3 FP-tree_hash 之node資料結構 17
4．2．4 Head table node資料結構 18
4．2．5 Hash 演算法 18
4．3 FP-tree_hash+tail演算法 21
4．3．1 Head table node資料結構 21
4．3．2 FP-tree_hash＋tail演算法 21
第五章實驗模擬 23
5．1 實驗設計 23
5．2 結果分析 24
5．3 實驗結論 27
第六章結論與建議 29
參考文獻　　　　 30

參考文獻

1. 陳彥良、凌俊青、許秉瑜，2001『在包裹式資料庫中挖掘數量關連規則』，資訊管理學報，第七卷‧第二期：215~229頁。
2. 陳彥良等，民90，『資料間隱含關係的挖掘與展望』，二十一世紀台灣湧現中的資訊管理議題專家研討會，大溪，鴻禧山莊。
3. Agrawal, R. and Srikant, R. "Fast Algorithms for Mining Association Rules," Proc. of the 20th Int’’l Conference on Very Large Databases, Santiago, Chile, Sep. 1994.
4. Chen, M.S., Han, J. and Yu, P.S. "Data Mining: An Overview from a Database Perspective,’’ IEEE Transactions on Knowledge and Data Engineering, (8:6) 1996, pp: 866-883.
5. Han, J. and Kamber, M. Data mining: Concepts and Techniques, Academic Press, 2001.
6. Han, J., Pei, J. and Yin, Y. "Mining Frequent Patterns without Candidate Generation," Proc. 2000 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’’00), Dallas, TX, May 2000, pp: 1-12.
7. Li, S., Shen, H. and Cheng, L. "New Algorithms For Efficient Mining Of Association Rules," Information Sciences (118:1-4) 1999, pp:251-268.
8. Park, J-S., Chen, M-S. and Yu, P. S. "Using a Hash-Based Method with Transaction Trimming for Mining Association Rules," IEEE Trans. on Knowledge and Data Engineering (19:5) 1997, pp:813-825.
9. Pasquier, N., Bastide, Y., Taouil, R. and Lakhal, L. "Efficient Mining Of Association Rules Using Closed Itemset Lattices," Information Systems (24:1) 1999, pp:25-46.
10. Savasere, A., Omiecinski, E. and Navathe, S. "An Efficient Algorithm for Mining Association Rules in Large Databases," Proc. Int’’l Conf. Very Large Data Bases, Zurich, Switzerland, Sep. 1995, pp:432-444.
11. Toivonen, H. "Sampling Large Databases For Association Rules," The 22th International Conference on Very Large Databases (VLDB’’96), Mumbay, India, Sep. 1996, pp:134-145.

指導教授

陳彥良(Y.L.Chen)

審核日期

2002-10-22

推文