(3.238.173.209) 您好!臺灣時間:2021/05/12 14:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:劉家銘
論文名稱:利用負相關線上挖掘關聯式規則
論文名稱(外文):Online Generation of Association Rules by Negative Correlation
指導教授:賈坤芳
學位類別:碩士
校院名稱:國立中興大學
系所名稱:資訊科學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:70
中文關鍵詞:資訊挖掘關聯式法則線上挖掘負相關
外文關鍵詞:Data MiningAssociation RulesOnline MiningNegative Correlation
相關次數:
  • 被引用被引用:5
  • 點閱點閱:173
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:26
  • 收藏至我的研究室書目清單書目收藏:2
挖掘關聯式法則主要是從資料庫中找出項目間的關係,提供給決策者作為決策的參考。最常見的挖掘演算法為Apriori演算法,它利用循序漸進式的方法,多次掃描資料庫,來挖掘出關聯式規則,但缺點是耗時且不具有彈性。線上挖掘演算法則可以讓使用者任意更動門檻值,並且在更動門檻值後,短時間內回應所有規則給使用者,解決了Apriori缺乏彈性和耗時的缺點,但線上挖掘主要的缺點是所需空間太大。此外,不管是傳統的演算法或線上挖掘演算法,都有可能會挖掘出不是真正相關的規則,因而誤導了使用者做出錯誤的決策。
本研究利用刪除負相關的項目集來預先儲存項目集絡,提供使用者作線上挖掘關聯式規則,不但可以較其他線上挖掘演算法節省空間,還可避免產生負相關的關聯式規則。實驗證實,在1000個屬性、100000筆交易紀錄的資料庫中,利用預先建構的非負相關項目集絡作線上挖掘時,可以在使用者更動門檻值後,0.2秒之內產生所有相對應的規則。在儲存空間方面,最好的情況可以節省28.72%,最差的情況和其他線上挖掘演算法相同。在品質方面,最多能過濾掉27.54%的負相關關聯式規則,提供較精簡的規則給使用者,避免誤導使用者。
第一章 簡介 1
第二章 相關研究 6
2.1 APRIORI演算法 6
2.2 APRIORI演算法的改善 7
2.2.1 DHP(Direct Hashing and Pruning) 演算法 8
2.2.2 DIC(Dynamic Itemset Count) 演算法 9
2.2.3 分段式挖掘(Partition)演算法 9
2.2.4 隨機取樣(Random Sampling)資訊挖掘演算法 10
2.3 線上挖掘演算法 11
2.3.1 預先處理式線上挖掘演算法 12
2.3.2 循序漸進式線上挖掘演算法 19
2.4 相關式規則(CORRELATION RULES) 21
第三章 問題定義及方法描述 23
3.1 問題描述 23
3.2 動機 24
3.3 利用刪除負相關項目集建立項目集絡 26
3.3.1 負相關(Negative Correlation) 26
3.3.2 方法描述 28
3.3.3 演算法 32
3.3.4 複雜度分析 35
3.4 挖掘非負相關的關聯式規則 36
3.4.1 方法描述 36
3.4.2 演算法 36
3.4.3 複雜度分析 38
3.5 實例:建構NNIL與挖掘關聯式規則 38
第四章 實驗及結果分析 43
4.1 測試環境 43
4.2 實驗設計 45
4.3 實驗結果及分析 46
4.4 相關研究比較 56
4.4.1 與其他線上挖掘演算法比較 56
4.4.2 與相關式規則比較 58
第五章 結論及未來研究 59
參考文獻 61
參考文獻
[AFK97] A. Amir, R. Feldman, and R. Kashi, “A new and versatile method for association generation,” Principles of Data Mining and Knowledge Discovery, First European Symposium, PKDD ''97, 1997, pages 221-231.
[AS94] R. Agrawal and R. Srikant, “Fast algorithms for mining association rules,” Proc. of the 20th VLDB Conference, 1994, pages 487-499.
[AY98] C. C. Aggarwal and P. S. Yu, “Online generation of association rules,” Proc. of the IEEE ICDE''98, 1998, pages 402-411.
[BC94] D. J. Berndt and J. Clifford, “Using dynamic time warping to find patterns in times series,” Proc. of the KDD-94 :AAAI Workshop on Knowledge Discovery in Database, 1994, pages 359-370.
[BMS97] S. Brin, R. Motwani, and C. Silverstein, “Beyond market basket: generalizing association rules to rorrelations,” Proc. of the ACM SIGMOD, 1997, pages 265-276.
[BMUT97] S. Brin, R. Motwani, J. D. Ullman, and S. Tsur, “Dynamic itemset counting and implication rules for market basket data,” Proc. of the ACM SIGMOD, 1997, pages 255-264.
[Che98] C. J. Chen, A pre-fetch mechanism for proxy servers: using association rules, Master Thesis, Institute of Computer Science, National Chung-Hsing University, Taiwan,1998.
[CHSVZ98] P. Cabeba, P. Hadjinian, R. Stadler, J. Verhees and A. Zanasi, Discovering data mining from concept to implementation, New Jersey, Prentice Hall PTR, 1998.
[Hid99] C. Hidber, “Online association rule mining,” Proc. of the ACM SIGMOD, 1999, pages 145-156.
[IBM96] “IBM Almaden-Quest data mining synthetic data generation code”, http://www.almaden.ibm.com/cs/quest/syndata.html, 1996
[JH00] K.-F. J. Jea and C.-H. Hsu, “Using reduced itemset lattice to support online mining for dynamic databases,” Proc. of the 2000 International Computer Symposium Workshop on Software Engineering and Database Systems, Taiwan, 2000, pages 99-106.
[Lan69] H.O. Lancaster, The Chi-squared Distribution, John Wiley & Sons, New York, 1969.
[Meo00] R. Meo, “Theory of dependence values,” ACM Trans. Database System, Vol. 25, No. 3, 2000, pages 380—406
[MSB97] S. Madan, W. K. Son, and K. E. Bollinger, “Applications of data mining for power systems,” Proc. of the Engineering Innovation: Voyage of Discovery IEEE 1997 Canadian Conference, Vol.2, 1997, pages 403-406.
[NRV96] J. Nearhos, M. Rothman, and M. Viveros, “Applying data mining techniques to a health insurance information system,” Proc. of the 22nd VLDB Conference, 1996, pages 286-294.
[PCY95] J. S. Park, M. S. Chen, and P. S. Yu, “An effective hash based algorithm for mining association rules,” Proc. of the ACM SIGMOD, 1995 , pages 175-186.
[Rat97] T. Rathburn, “Data-mining in the financial markets,” PC AI, Vol. 11, No. 4, 1997, pages 19-20.
[SON95] A. Savasee, E. Omiecinski, and S. Navathe, “An efficient algorithm for mining association rules in large databases,” Proc. of the 21st VLDB Conference, 1995, pages 432-444.
[Tan98] J. Tang, “Using incremental pruning to increase the efficiency of dynamic itemset counting for mining association rules,” Proc. of the 1998 ACM 7th International Conference on Information and Knowledge Management, 1998, pages 273—280.
[Toi96] H. Toivonen, “Sampling large databases for association rules,” Proc. of the 22nd VLDB Conference, 1996, pages 134-145.
[ZPLO96] M. J. Zaki, S. Parthasarathy, W. Li, and M. Ogihara, “Evaluation of sampling for data mining of association rules,” Proc. of the Seventh International Workshop on Data Engineering, 1997, pages 42-50.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔