跳到主要內容

臺灣博碩士論文加值系統

(44.200.171.74) 您好!臺灣時間:2022/08/12 20:32
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林義超
研究生(外文):Yi-Chau Lin
論文名稱:在大型資料庫中使用一個以新的雜湊及分割為基礎的搜尋高頻項目集演算法
論文名稱(外文):Using a New Two-dimensional Hash Table and Division-based Algorithm for Discovering Large Itemsets in Large Databases
指導教授:蔡正發蔡正發引用關係
指導教授(外文):Cheng-Fa Tsai
學位類別:碩士
校院名稱:國立屏東科技大學
系所名稱:資訊管理系
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:74
中文關鍵詞:大項目集雙維雜湊法分割資料庫
外文關鍵詞:Large ItemsetsTwo-dimensional Hash TableDatabase Division
相關次數:
  • 被引用被引用:2
  • 點閱點閱:360
  • 評分評分:
  • 下載下載:64
  • 收藏至我的研究室書目清單書目收藏:1
  近年來,在資料庫中進行資料挖掘已變得非常盛行,銷售商能利用所挖掘的資料去改善其主要的行銷策略。關聯式法則挖掘之目的乃在於挖掘出資料庫中各種物品的關聯性。從交易的資料庫中發掘出各種物品的關聯性,使決策者能夠利用這些資訊去制定企業的行銷策略,例如:交叉行銷方式及型錄的設計。
  許多被提出的演算法已經被利用在挖掘出大的高頻資料項目集。由Agrawal所提出的Apriori演算法已經算是最好的關聯式法則挖掘方法之一;Park所提出的DHP演算法則是延伸Apriori的方法,利用雜湊表(Hash table)事先來減少候選2-項目集的數量,由於Apriori的方法對於候選2-項目集會產生相當龐大的資料量,致使在搜尋資料庫時必須花費很長的一段時間,因此利用雜湊表(Hash table)能夠有效濾除不必要的項目集,進而達到減少搜尋資料庫的次數;Brin所提出的DIC演算法也是根據Apriori的方法演變而來,主要目的就是減少花費在搜尋資料庫的時間,其方法是將資料庫分割成許多區域,在任何開始的區段都可以加入新產生的候選項目集,不必如Apriori在判斷一個新的候選項目集必須從頭去搜尋完整的資料庫。
  在本篇論文中主要有三項貢獻:(1)利用雙維雜湊法(Two-dimensional Hash method)有效的產生大的資料項目集,(2)利用資料庫分割(Division approach)有效的減少資料項目集在資料庫中所需的掃描時間,(3)有效的減少資料庫搜尋的次數。在本論文中所提出的THD演算法結合了兩種主要的技術,分別為雙維雜湊(Two-dimensional hash)與分割法(division)。利用THD來產生候選大項目集是非常有效率的。在本篇論文的實驗結果中與近幾年來在IEEE期刊所發表的著名演算法(Apiori、DHP以及DIC)做比較,很明顯的可以看出其效能之差異,這也顯示了本論文所出的演算法明顯的優於其它演算法。
  Recently, mining of databases has attracted a growing amount of attention in database communities due to its wide applicability in retail industry to improving marketing strategy. Association rule mining finds interesting association or correlation relationships among a large set of data items. The discovery of interesting transaction records can help in selective marketing, business management and many business decision marking processes, such as cross-marketing and catalog design.
  Many algorithms have been proposed to discover the large itemsets. The Apriori algorithm by Agrawal has merged as one of the best association rule mining (ARM) algorithm. The DHP algorithm proposed by Park extends the Apriori method by utilizing a hash table to precompute approximate support of 2-itemsets during the first iterations. The DIC algorithm proposed by Brin is a generalization of Apriori.
  The contribution of this thesis is threefold: (1) efficient generation for large itemsets by two-dimensional hash method, (2) effective reduction on itemsets scan required by the Division approach, (3) the option of reducing the number of database scans required. Our proposed two-dimensional hash and division-based techniques, THD algorithm, is very efficient for the generation of candidate large itemsets, where the number of candidate large itemsets generated by THD is, smaller than that by many methods such as the Apriori algorithm, DHP algorithm, and DIC algorithm. According to our simulation results, the proposed approach is efficient than any existing algorithms.
摘要 I
Abstract III
誌謝 V
目錄 VI
圖目錄 VIII
表目錄 X
第1章 緒論 1
1.1 研究背景 1
1.1.1 關聯式法則 2
1.1.2分類法 3
1.1.3分群法 4
1.1.4序列型樣 5
1.2研究動機 6
1.3 研究目的 8
1.4 研究流程 9
1.5 論文架構 10
第2章 文獻探討 12
2.1 Apriori演算法 12
2.2 DHP演算法 16
2.3 DIC演算法 20
2.4 Partition演算法 21
2.5優缺點的比較 22
第3章 研究方法 24
3.1 HD演算法 25
3.2 THD演算法 27
3.2.1 雙維雜湊表 31
3.2.2 資料庫區段 36
3.3資料分佈的限制 38
第4章 實驗結果與分析 40
4.1 在相同長度的條件之下 41
4.1.1 平均長度為6 (T=6) 41
4.1.2 平均長度為10 (T=10) 44
4.1.3 平均長度為15 (T=15) 46
4.2 在相同資料庫大小的條件之下 49
4.2.1 資料庫為D10K 49
4.2.2 資料庫為D100K 51
4.2.3 資料庫為D200K 54
4.3 非相關項目集的減少量 56
4.4 資料庫區段的數目 64
4.5 XOR、AND和OR雜湊函數的比較 66
第5章 結論 68
參考文獻 70
作者簡介 74
圖 目 錄
圖1-1 KDD流程 2
圖1-2 資料分類過程 4
圖1-3 研究流程 10
圖2-1 Apriori演算法 14
圖2-2 apriori-gen function 14
圖2-3 Apriori運算過程之範例 15
圖2-4 雜湊表和產生C2的範例 18
圖2-5 縮減原始資料庫 19
圖2-6 Apriori和DIC搜尋資料庫比較 21
圖3-1 HD algorithm 26
圖3-2 Main algorithm of THD 28
圖3-3 THD_candidate function 29
圖3-4 THD_support function 30
圖3-5 範例資料庫(一) 經h1運作之後的結果 33
圖3-6 範例資料庫(一) 經h2運作之後的結果 34
圖3-7 範例資料庫(一) 雙維雜湊表 35
圖4-1 在T=6的條件下,在不同資料庫大小的執行時間 43
圖4-2 在T=10的條件下,在不同資料庫大小的執行時間 46
圖4-3 在T=15的條件下,在不同資料庫大小的執行時間 48
圖4-4 在D=10K的條件下,在不同平均交易長度的執行時間 51
圖4-5 在D=100K的條件下,在不同平均交易長度的執行時間 53
圖4-6 在D=200K的條件下,在不同平均交易長度的執行時間 56
圖4-7在不同資料區段數目下HD與THD演算法的執行時間比較 65
圖4-8 XOR、AND和OR三種函數執行時間之比較 67
表 目 錄
表1-1 序列型樣範例 5
表2-1 四種主要挖掘關聯式法則演算法的優缺點比較 23
表3-1 HD和THD演算法之參數的意義 24
表3-2 範例資料庫(一) 32
表3-3 範例資料庫(二) 37
表4-1 實驗資料庫之參數的意義 40
表4-2 實驗資料庫 41
表4-3 在T=6條件下的執行時間 42
表4-4 在T=10條件下的執行時間 44
表4-5 在T=15條件下的執行時間 47
表4-6 在D=10K條件下的執行時間 49
表4-7 在D=100K條件下的執行時間 52
表4-8 在D=200K條件下的執行時間 54
表4-9 T6I4D10K非相關項目集的減少量 57
表4-10 T6I4D100K非相關項目集的減少量 57
表4-11 T6I4D200K非相關項目集的減少量 58
表4-12 T10I4D10K非相關項目集的減少量 58
表4-13 T10I4D100K非相關項目集的減少量 59
表4-14 T10I4D200K非相關項目集的減少量 60
表4-15 T15I4D10K非相關項目集的減少量 61
表4-16 T15I4D100K非相關項目集的減少量 62
表4-17 T20I4D10K非相關項目集的減少量 63
表4-18 XOR、AND和OR三種函數的執行時間 66
中文部份
[1]王仁傑,有效找出較長資料項目型樣的關聯法則之研究,逢甲大學資訊工程研究所碩士論文,民國八十九年六月。
[2]朱清和,雜湊演算法的設計與實現,國立交通大學電信工程研究所碩士論文,民國八十八年六月。
[3]張紹勳、蔡志敏,演算法入門與進階─使用C語言,松崗出版社,民國九十年。
英文部分
[4]A. Savasere, E. Omiecinski, S. Navathe, “An Efficient Algorithm for Mining Association Rules in Large Database,” Proc. 21th VLDB, Zurich, Switzerland, pp. 432-444, 1995.
[5]H. Toivonen, “Sampling large databases for association rules,” In Proc. 22nd VLDB Conference, Bombay, India, pp. 134-145, Sept. 1996.
[6]IBM Almaden Research Center “Quest Synthetic Data Generation Code,”http://www.almaden.ibm.com/cs/quest/syndata.html.
[7]J. Han, J. Pei, and Y. Yin, “Mining frequent patterns without candidate generation,” Proc. of the ACM SIGMOD Int’l Conf. on Management of Data, Dallas, Texas, USA, pp. 1-12, May 2000.
[8]Jiawei Han, Micheline Kamber, “Data Mining: Concepts and Techniques,” San Mateo, CA: Morgan Kaufmann Publishers, 2001.
[9]J.R. Quinlan, “C4.5: Programs for Machine Learning,” San Mateo, CA: Morgan Kaufmann Publishers, 1993.
[10] J.S. Park, M.S. Chen, and P.S. Yu, “Using a Hash-Based Method with Transaction Trimming for Mining Association Rules,” IEEE Trans. on Knowledge and Data Eng., vol. 9, no. 5, pp. 813-825, Sept./Oct. 1997.
[11] K. Alsabti, S. Ranka, and V. Singh, “An Efficient K-Means Clustering Algorithm,” PPS/SPDP Workshop on High performance Data Mining, Orlando, Florida, USA, 1997.
[12] K. Krishna and M. Naraimha Murty, “Genetic K-means Algorithm,” IEEE Transactions on System, Man and Cybernetics-Part B: Cybernelics, vol. 29, no. 3, pp. 433-439, 1998.
[13] M. Houtsma, A. Swami, “Set-oriented Mining for Association Rules in relational database,” In Proceedings of 11th Intl. Conf. on Data Engineering (ICDE’95), Taipei, Taiwan, pp. 25-33, March 1995.
[14] M.S. Chen, J. Han, and P.S. Yu, “Data Mining: An Overview from a Database perspective,” IEEE Trans. on Knowledge and Data Eng., vol. 8, no. 6, pp. 866-883, December, 1996
[15] Mohammed J. Zaki, “Parallel and Distributed Association Mining: A Survey,” IEEE Concurrency, vol. 7, no. 4, pp. 14-25, Oct.-Dec. 1999.
[16] Pieter Adriaans, Dolf Zantinge, Data Mining. Addison Wesley Longman, 1996
[17] R. Agrawal, T. Imielinski, and A. Swami, “Mining Association Rules between Sets of Items in Large Databases,” Proc. of the ACM SIGMOD Conf. on Management of Data, Washington, D.C., pp. 207-216, May 1993.
[18] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules in Large Databases,” Proc. 20th Int’l Conf. Very large Data Bases, pp. 478-499, Sept. 1994.
[19] R. Agrawal and R. Srikant, “Mining Sequential Patterns,” In Proceedings of 11th Intl. Conf. on Data Engineering (ICDE’95), Taipei, Taiwan, pp. 3-14, March 1995.
[20] Roberto J. Bayardo Jr., “Efficiently Mining Long Patterns from Databases,” Proc. of the ACM SIGMOD Int’l Conf. On Management of Data, pp. 85-93, Seattle, Washington, June 1998.
[21] S. Brin, R. Motwani, J.D. Ullman, and S. Tsur, “Dynamic Itemset Counting and Implication Rules for Market Basket Data,” Proc. ACM SIGMOD Conf. on Management of Data, ACM Press, New York, pp. 255-264, 1997.
[22] Y. Bao, X. Du, Ishii N., “Improving performance of the k-nearest neighbor classifier by tolerant rough sets,” Cooperative Database Systems for Advanced Applications, 2001. CODAS 2001. The Proc. of the Third International Symposium on, Beijing, China, pp. 167-171, 2000.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top