臺灣博碩士論文加值系統

因為網路與儲存資料技術的快速發展，出現很多大數據的應用，因此要如何從大量的資料中找到具有意義的資訊，便成為一個相當重要的課題。在過去，效益探勘被提出用來找出基於潛在利益的重要項目集。然而，因為效益探勘的過程複雜，因此判斷探勘程式是否正確是非常耗時且對其應用相當重要。在本篇論文中，我們採用了一種軟體測試的技術稱為蛻變測試來驗證效益探勘程式的正確性，其會利用蛻變關係來協助測試。當程式的輸入改變，若程式的輸出會遵循蛻變關係所定義的結果則我們可以更有信心的認為程式是正確的；但如果不符合，則程式一定存在錯誤。我們針對效益探勘問題提出十五個蛻變關係，並將這些關係分為與演算法相關和與演算法無關兩種。這些關係是依據下面兩個面向設計：變更最小閥值及不調整閥值但改變交易資料庫的內容。在實驗中，我們分別使用了真實和模擬的資料集並根據蛻變分數來評估這些蛻變關係。實驗結果顯示由於第三個和第十個蛻變關係是嚴格的關係，因此他們擁有最好的檢驗效果。

Because the internet and storage technology are developing rapidly, many new applications have emerged focusing on big data. Finding meaningful information from large amounts of data has thus become an important issue. In the past, utility mining was proposed to find significant itemsets based on their potential benefits. Because the utility-mining process is complex, judging the correctness of its program is very time-consuming and also crucial to its applications. In this paper, we adopt a famous software-testing technique called metamorphic testing to verify the correctness of a utility-mining program. The metamorphic testing uses metamorphic relations as an aid to test the correctness. When input conditions are changed, the program is correct with more confidence if the corresponding outputs follow the rules, but if they do not, errors certainly exist in the program. We design fifteen metamorphic relations for utility mining to verify the correctness of its programs. We categorize these relations into algorithm-independent (MR1 to MR7) and algorithm-dependent (MR8 to MR15). These relations are designed based on two aspects: changing the minimum utility threshold and modifying the content of a transaction database. In the experiments, we use a real dataset and a synthetic dataset to evaluate the proposed metamorphic relations by the mutation score. The experimental results show that the third and tenth metamorphic relations demonstrate the best performance because they are strict relations.

論文審定書 i
誌謝 ii
摘要 iii
Abstract iv
Contents vi
List of Figures x
List of Tables xi
Chapter 1 Introduction 1
Chapter 2 Related Work 3
2.1. High-Utility Itemset Mining 3
2.2. Two-Phase Algorithm for High-Utility Itemset Mining 5
2.3. Metamorphic Testing 8
Chapter 3 Proposed Metamorphic Relations for Utility Mining 10
3.1. Notation 10
3.1.1. Source/Follow-up Input 11
3.1.2. Source/Follow-up Output 11
3.2. Algorithm-independent Metamorphic Relations 12
3.2.1. The First Metamorphic Relations: Decreasing the Minimum Threshold 12
3.2.2. The Second Metamorphic Relations: Increasing the Minimum Threshold 15
3.2.3. The Third Metamorphic Relation: Adding a New Item and a New Transaction 16
3.2.4. The Fourth Metamorphic Relation: Appending a New Item to Old Transactions 19
3.2.5. The Fifth Metamorphic Relation: Adding a New Item and a New Transaction (II). 22
3.2.6. The Sixth Metamorphic Relation: Adding a New Item and a New Transaction (III) 25
3.2.7. The Seventh Metamorphic Relation: Adding a New Item and a New Transaction (IV) 29
3.3. Algorithm-dependent Metamorphic Relations 32
3.3.1. The Eighth and Ninth Metamorphic Relations 32
3.3.2. The Tenth Metamorphic Relation: Adding a New Item and a New Transaction 36
3.3.3. The Eleventh Metamorphic Relation: Appending a New Item to Old Transactions 39
3.3.4. The Twelfth Metamorphic Relation: Adding a New Item and a New Transaction (II) 43
3.3.5. The Thirteenth Metamorphic Relation: Adding a New Item and a New Transaction (III) 45
3.3.6. The Fourteenth Metamorphic Relation: Adding a New Item and a New Transaction (IV) 49
3.3.7. The Fifteenth Metamorphic Relation: Removing an Item from Old Transactions (IV) 52
Chapter 4 Experiments and Analyses 58
4.1. Experimental Environment 58
4.2. Experimental Settings 59
4.3. Experimental Results for the Chess_utility Dataset 59
4.3.1. Influence of the Number of Transactions 60
4.3.2. Influence of Minimum Thresholds 61
4.3.3. Average Mutation Score of Each Metamorphic Relation with the Chess_utility Dataset 63
4.4. Experimental Results for the Synthetic Dataset 63
Chapter 5 Conclusion and Future Work 66
5.1. Conclusion 66
5.2. Future Work 66
References 68

[1]R. Agrawal, T. Imielińsk, and A. Swami, “Mining association rules between sets of items in large database,” The ACM SIGMOD International Conference on Management of Data, pp. 207-216, 1993.
[2]P. Fournier-Viger, C. W. Lin, A. Gomariz, T. Gueniche, A. Soltani, Z. Deng, and H. T. Lam, The SPMF Open-Source Data Mining Library Version 2. Proc. 19th European Conference on Principles of Data Mining and Knowledge Discovery, Part III, Springer LNCS 9853, pp. 36-40.
[3]T. Y. Chen, S. C. Cheung, and S. M. Yiu, “Metamorphic testing: a new approach for generating next test cases,” Technical Report HKUST-CS98-01, Department of Computer Science, Hong Kong University of Science and Technology, 1998.
[4]H. Yao, H. J. Hamilton, and C. J. Butz, “A foundational approach to mining itemset utilities from databases,” The Third SIAM International Conference on Data Mining, pp. 482-486, 2004.
[5]H. Yao and H. J. Hamilton, “Mining itemset utilities from transaction database,” Data and Knowledge Engineering, Vol. 59, No. 3, pp. 603-626, 2006.
[6]Y. Liu, W. Liao, and A. Choudhary, “A two-phase algorithm for fast discovery of high utility itemsets,” The Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2005.
[7]B. Vo, L. V. Nguyen, V. V. Vu, M. T. H. Lam, T. T. M. Duong, T. T. Manh, T. T. T. Nguyen, L. T. T. Nguyen, and T. P. Hong, "Mining correlated high utility itemsets in one phase," IEEE Access, Vol. 8, pp. 90465-90477, 2020
[8]T. Y. Chen, J. W. Ho, H. Liu, and X. Xie, “An innovative approach for testing bioinformatics programs using metamorphic testing,” BMC Bioinformatics, Vol. 10, Issue 1, pp. 24, 2009.
[9]S. Segura, G. Fraser, A. B. Sanchez, and A. Ruiz-Cortes, “A survey on metamorphic testing,” IEEE Transactions on Software Engineering, Vol. 42, No. 9, 2016.
[10]J. W. Zhang, X. Y. Xie, and Z. Y. Zhang, “How reliable is your outsourcing service for data mining? A metamorphic method for verifying the result integrity,” International Conference on Software Analysis, Testing, and Evolution, pp. 120-136, 2018.
[11]X. Xie, Z. Y. Zhang, T. Y. Chen, Y. Liu, P. L. Poon, and B. Xu, “METTLE: a metamorphic testing approach to assessing and validating unsupervised machine learning systems,” IEEE Transactions on Reliability, 2020.
[12]J. C. W. Lin, Y. Djenouri, G. Srivastava and J. M. -T. Wu, “Large-scale closed high-utility itemset mining,” 2021 International Conference on Data Mining Workshops (ICDMW), pp. 591-598, 2021.
[13]T.P. Hong, C.C. Chiu, J.H. Su, and C.H. Chen, “Applicable metamorphic testing for erasable-itemset mining,” IEEE Access, Vol. 10, pp. 38545-38554, 2022.
[14]T. P. Hong, C. Y. Lin, W. M. Huang, K. S. M. Li, L. S. L. Wang, and J. C. W. Lin, “Using tree structure to mine high temporal fuzzy utility itemsets,” IEEE Access, Vol. 8, pp. 153692-153706, 2020.
[15]C. X. Ma and J. Zhang, “DHUI: a new algorithm for mining high utility itemsets,” 2009 International Conference on Machine Learning and Cybernetics, pp. 173-177, 2009.
[16] Y. S. Ma, J. Offutt and Y. R. Kwon, “MuJava: an automated class mutation system,” Software Testing, Verification and Reliability, Vol. 15, Issue 2, pp. 97-133, 2015.
[17]Pushp and S. Chand, “Mining of high utility itemsets with negative utility values for incremental datasets,” 2021 International Conference on Computational Performance Evaluation (ComPE), Shillong, India, pp. 431-436, 2021.
[18]T. P. Hong, W. T. Hung, W. M. Huang and Y. C. Tsai, “Incremental fuzzy utility mining with tree structure,” 2022 IEEE International Conference on Big Data (Big Data), pp. 6202-6206, 2022.
[19]J. F. Qu, P. Fournier-Viger, M. Liu, B. Hang and C. Hu, “Mining high utility item-sets using prefix trees and utility vectors,” IEEE Transactions on Knowledge and Data Engineering, Vol. 35, No. 10, pp. 10224-10236, 2023.
[20]Y. Ma, D. Towey, T. Yueh Chen and Z. Quan Zhou, “Metamorphic testing of fake news detection software,” 2021 IEEE 45th Annual Computers, Software, and Applications Conference (COMPSAC), pp. 1508-1513, 2021.
[21]F. U. Rehman and M. Srinivasan, “Metamorphic testing for machine learning: applicability, challenges, and research opportunities,” 2023 IEEE International Conference On Artificial Intelligence Testing (AITest), pp. 34-39, 2023.
[22]D. Towey, Z. Luo, Z. Zheng, P. Zhou, J. Yang, P. Ingkasit, C. Lao, M. Pike, and Y. Zhang, “Metamorphic testing of an automated parking system: an experience report,” 2023 IEEE 47th Annual Computers, Software, and Applications Conference, pp. 1774-1779, 2023.
[23]N. B. Chaleshtari, F. Pastore, A. Goknil and L. C. Briand, “Metamorphic testing for web system security,” IEEE Transactions on Software Engineering, Vol. 49, No. 6, pp. 3430-3471, 2023.
[24]U. Yun, H. Kim, T. Ryu, Y. Baek, H. Nam, J. Lee, B. Vo, and W. Pedrycz, “Prelarge-based utility-oriented data analytics for transaction modifications in Internet of Things,” IEEE Internet of Things Journal, Vol. 8, No. 24, pp. 17333-17344, 2021
[25]H. Kim, T. Ryu, C. Lee, S. Kim, B. Vo, J. C. W. Lin, and U. Yun, “Efficient method for mining high utility occupancy patterns based on indexed list structure,” IEEE Access, Vol. 11, pp. 43140-43158, 2023
[26]IBM Quest Data Mining Projection, Quest synthetic data generation code, 1996, Available at http://www.almaden.ibm.com/cs/quest/syndata.htm.