臺灣博碩士論文加值系統

隨著資訊技術的蓬勃發展，使企業擁有越來越多獲取資訊的管道，可將整體企業之運作記錄，累積出龐大之資料庫。如何從累積之資料庫中找尋有用之資訊，早已是企業關注之議題，藉此發展出資料探勘(data mining)技術，其中又以關聯規則(association rule)技術應用最為廣泛。基於網路科技的發展與全球化經營，企業之交易資料庫可說是無時無刻不斷在變動，而在異動資料庫中若要保持探勘結果的正確性，於傳統之探勘方法不免需不斷重新探勘資料以保持其正確性。產生過多多餘候選項目，導致掃描資料庫次數過多；無法判斷掃描目標項目位於哪些交易資料中，而需掃描多餘交易資料；以及異動式資料庫中為求探勘結果正確性，需重複探勘已探勘之原始資料，為傳統探勘關聯規則之Apriori演算法於異動式資料庫中執行探勘之缺點。
本研究以Apriori演算法為基礎，改良其演算過程，提出兩演算法。其一，將傳統之水平式資料庫於讀取時轉換為垂直式資料庫，如此一來便可只針對需掃描之項目做存取的動作，免除多餘交易資料掃描，每次檢查一項目之出現次數僅需掃描兩筆資料即可達成，藉此加快探勘效率。其二，提出一演算步驟改良典型Apriori演算法產生候選項目集之過程，將產生候選項目集時先將其排序，使多餘候選項目集產生數量確實精簡，減少掃描多餘項目集，再次加快探勘速度。並於此兩方法中皆提出適當之更新演算法，使其於變動資料庫中可即時探勘關聯規則，並保持其正確性，以符合企業需求，提供即時且正確之重要決策制定參考。

With the development of information technology, enterprises have a lot of way to get information and can use this technology store about a lot of enterprise’s transaction or record in data base. How to find the useful information in database has become the subject which the enterprises pay attention. Association rules technology is generally in data mining. Based on the Internet Technology development and the globalization of business, the transaction database of enterprise is constantly changing all the time, and in order to keep the accuracy of exploring result in dynamic database, the traditional explore method in order to keep the information accuracy so it unavoidable must to exploring information again constantly; Because generated too many redundant candidate itemsets so it causes too many times to scan the database; Is need to scan the redundant transaction data because there is not recognize this items belong to which transaction. In order to preserve the accuracy when mining the dynamic database, we need repeatedly scan database. This is above the traditional Apriori algorithm to mining association rules of the weakness in the dynamic database. This research is based on Apriori Algorithm to improve its process. This paper proposed two improve algorithms.
One of VS_Apriori(Vertial Scan Apriori) algorithm is to transform database from horizontal to vertical. This can be avoided scan redundant of Transaction data.Any item count just need to scan two transactions in data base so as to increase mining efficiency. In addition,SVS_Apriori algorithm (Sort & Vertial Scan Apriori)that is improved from Apriori generate candidate itemsets process. First, itemsets sort by ascending so that can avoid generate too many candidate itemset and can increase mining efficiency again. And propose appropriate methods to update these two algorithms so as to these algorithms can use in dynamic database in real-time and correctly, to fit in with the business needs and provide immediate and accurate to the important decision-making.

摘要 ..................................................................................................................... iv
Abstract ...................................................................................................................... v
誌謝 ....................................................................................................................vii
目 錄 ...................................................................................................................viii
表 目 錄 ..................................................................................................................... xi
圖 目 錄 ....................................................................................................................xii
第一章 緒論 .............................................................................................................. 1
1.1 研究背景與動機 .............................................................................................. 1
1.3 研究範圍與限制 .............................................................................................. 5
第二章 相關文獻與探討 ........................................................................................ 10
2.1 資料探勘理論與相關技術 ............................................................................ 10
2.2 關聯規則 ........................................................................................................ 14
2.3 相關演算法演算法 ........................................................................................ 15
2.3.1 Apriori演算法............................................................................................ 15
2.3.1.1 Apriori演算步驟................................................................................ 15
2.3.1.2 Apriori演算實例................................................................................ 17
2.3.2 new_Apriori演算法................................................................................... 19
2.3.2.1 new_Apriori演算步驟....................................................................... 19
2.3.2.2 new_Apriori演算實例....................................................................... 20
2.3.3 un_Apriori演算法...................................................................................... 22
2.3.3.1 un_Apriori演算步驟.......................................................................... 22
2.3.3.2 un_Apriori新增資料演算步驟.......................................................... 23
ix
2.3.3.3 un_Apriori刪除資料演算步驟.......................................................... 24
2.3.3.4 un_Apriori演算實例.......................................................................... 26
第三章 利用VS_Apriori演算法於變動資料庫中探勘關聯規則........................ 29
3.1 VS_Apriori演算法核心演算法..................................................................... 29
3.2 VS_Apriori新增資料演算法......................................................................... 35
3.3 VS_Apriori刪除資料演算法......................................................................... 39
3.4 VS_Apriori演算法實例說明......................................................................... 43
3.4.1 VS_Apriori核心演算法實例..................................................................... 43
3.4.2 VS_Apriori新增演算法實例..................................................................... 46
3.4.3 VS_Apriori刪除演算法實例..................................................................... 50
第四章 利用SVS_Apriori演算法於變動資料庫中探勘關聯規則..................... 53
4.1 SVS_Apriori演算法核心演算法.................................................................. 53
4.2 SVS_Apriori新增資料演算法...................................................................... 57
4.3 SVS_Apriori刪除資料演算法...................................................................... 61
4.4 SVS_Apriori演算法實例說明...................................................................... 65
4.4.1 SVS_Apriori核心演算法實例.................................................................. 65
4.4.2 SVS_Apriori新增演算法實例.................................................................. 70
4.4.3 SVS_Apriori刪除演算法實例.................................................................. 75
第五章 系統建置與效能分析 ................................................................................ 81
5.1 實驗設備與系統環境 .................................................................................... 81
5.1.1 實驗設備 .................................................................................................... 81
5.1.2 資料庫參數說明 ........................................................................................ 81
5.2 核心演算法之效能評估 ................................................................................ 82
5.3 更新演算法之效能評估 ................................................................................ 87
第六章 結論與未來發展 ........................................................................................ 90
x
6.1 研究結論 ........................................................................................................ 90
6.2 未來研究方向 ................................................................................................ 91
參考文獻 .................................................................................................................... 92

1.曾憲雄、蔡秀滿等，資料探勘Data Mining，旗標出版公司，民96年。
2.鄭滄祥、魏志平等，非對稱性分類分析之實證評估，第十四屆國際資訊管理學術研討會，民國92年。
3.陳垂呈，以有效率分群化演算法發掘消費者最適性之產品項目，TANET 2002(台灣區網際網路研討會)，民國91年。
4.陳垂呈，應用布林運算快速分群化交易項目，TANET2001(台灣區網際網路研討會)，民國90年。
5.顏秀珍、李玉璽、王思穎，從交易資料庫中挖掘客戶的購物行為，第十四屆物件導向技術及應用演討會，民國92年。
6.連宏明，從交易資料庫中發掘含有時間間隔的序列型樣，輔仁大學資訊工程研究所，碩士論文，民國90年。
7.賴瓊惠，使用布林演算法找出在大型資料庫中多階層序列型樣，台灣科技大學資訊管理研究所，碩士論文，民國90年。
8.黃仁鵬、蔡季嵐，挖掘關聯規則之階段搜尋演算法-GSA，電子商務學報，第九卷，第四期，民國96年。
9.陳垂呈、蕭惠文、賴韋霖、陳建佑、謝維珍、陳宗義，探勘關聯規則之有效率演算法，2008數位生活科技研討會，民國97年。
10.Han J., Kamber M., “Data Mining: Concepts and Techniques,”Morgan Kaufmann, 2006.
11.Berry M. J. A., Linoff, G. S., “Data Mining Techniques for Marketing, Sales, and Customer Support,” New York: John Wiley, 2004.
12.Hui S. C., Jha, G., “Data Mining for Customer Service Support,” Information and Management, Vol. 38, pp. 1-13, 2000.

13.Chen M. S., Han, J.,Yu P. S., “Data Mining: An Overview from a Database Perspective,” IEEE Trans. on Knowledge and Data Engineering, Vol. 8, No. 6, pp. 866-883, 1996.
14.Agrawal R., Srikant R., “Fast Algorithms for Mining Association Rules in Large Database, “ Proceedings of the 20th International Conference on Very Large Data Bases, pp. 487-499, 1994.
15.Frawley W., Piatesky-Shapiro G., Matheus C., “Knowledge discovery in databases:an overview”, AI Magazin, Fall 1992, pp213-228, 1992.
16.Fayyad U. M., Piatesky-Shapiro G., Smithy P., “The KDD process for extracting useful knowledge form volumes of data”, Communication of the ACM, Vol. 39, pp.27-34, 1996.
17.Berry M. J. A., Linoff G., Data Mining Techique For Marketing, Sale and Customer Support, John Wiley and Sons, 1997.
18.Quinlan J.R., “Induction of Decision Trees,” Machin Learing, Vol.1, pp.81-106, 1986.
19.Ng R., Han J., “Efficient and Effective Clustering Method for Spatial Data Mining”, Proceedings of International Conference Very Large Data Bases, pp.144-155, 1994.
20.Agrawal R., Srikant R., “Mining Sequential Patterns,” Proceedings of the 7th International Conference on Data Engineering, pp.3-14, 1995.
21.Agrawal R.,Imielinski T., Swami A., “Mining Association Rules Between Sets Items in Large Database,” In proc. Of the ACM SIGMOD Conference on Management of Data, pp.207-216, 1993.
22.Shinguang Ju, Chen Chen, “MMFI:an Effective Algorithm for Mining Maximal Frequent Itmesets,” International Symposiums on Information Processing, 2008.
23.Wei Kian Chen, Dustin Baumgartner, Ryan Millikin, “Extracting Borderline Associations,” IEEE Symposium on Computational Intelligence and Data Mining, 2007.
24.Jian P., Jiawei H., Hong L., Shojiro N.,Shiwei T., Dongqing Y., “H-Mine:Fast and space-preserving frequent patten mining in large databases,” IIE Transactions, Vol. 39, pp.593-605, 2005.
25.Fan Wu, Shih-Wen Chiang, Jiunn-Rong Lin, “A new approach to mine frequent patterns using item-transformation methods,” Information System, Vol.32, pp.1056-1072, 2007.
26.Jie Dong, Min Han, “BitTableFI:An efficient mining frequent itemsets algorithm,” Knowledge_Base System, Vol. 20, pp.329-335, 2007.
27.Coenen F., Leng p., Ahmed S., “Data Structure for Association Rule Mining:T-trees and P-trees,” Proceedings of the IEEE Transactions on Knowledge and Data Engineering, Vol. 16, pp. 744-778, 2004.
28.Han J., Pei J., Yin Y., “Mining Frequent Patterns without Candidate Generation,” Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pp. 1-12,2000.
29.Li Z. C., HE P. L., Lei M., “A High Efficient AprioriTid Algorithm for Mining Association Rule,” Proceedings of the Fourth International Conference on Machine Learning and Cybernetics, pp. 1812-1815, 2005.
30.Liu P. Q., Li Z. Z.,Zhao Y. L., “Effective Algorithm of Mining Frequent Itemsets for Association Rules,” Proceedings of the Third International Conference on Machine Learning and Cybernetics, pp. 1447-1451, 2004.
31.Srikant R., Agrawal R., “Mining Generalized Association Rule,” Proceedings of the 21th International Conference on Very Large Data Bases, pp.407-417, 1995.
32.Enrique Lazcorreta, Rederico Botella, “Towards personalized recommendation by tow-step modified Apriori data mining algorithm,” Expert Systems with Applications, Vol. 35, pp. 1422-1429, 2008.
33.Dongme Sun, Shaohua Teng, Wei Zhang, Haibin Zhu, “An Algorithm to Improve the Effectiveness of Apriori,” Proc. 6th IEEE Int. Conf. on Cognitive Informatics, 2007.
34.Ja-Hwung Su, Wen-Yang Lin, “CBW:An Efficient Algorithm for Frequent Itemset Mining,” Proceedings of the 37th Hawaii International Conference on System Sciences, 2004.