臺灣博碩士論文加值系統

約略集合是由波蘭Z. Pawlak 在1982年提出，用來處理含糊資訊的新數學方法，它能夠從資料中發現潛在的重要事實，但是過去的文獻中指出傳統的約略集合不能確保決策表的分類是可信任的，因此，University of Texas Austin的 Bill Tseng教授提出REA (Rule-Extraction Algorithm)來解決這問題，但是產生的SI(strength index)不一定只有一個，可能會有數個同價值的SI，所以Tseng教授又提出AREA (Alternative Rule Extraction Algorithm)來解決擷取規則不完整這問題，另外，約略集合演算法雖然可以有效的產生分類規則，但是卻無法在新增一個物件後產生新規則。過去大多的研究是無法解決這類大型資料庫增量式問題，因此，本研究以AREA為基礎的增量式規則擷取演算法來解決上面描述的問題，但AREA可能會產生重複的規則，因此有稍作修改。最後，透過本文提的演算法當有新物件或屬性新增時，不需要重頭對原始資料進行規則歸納，就可以很快速的產生完整規則且不重複的規則，此演算法解決了新資料新增的問題因此也減少了多重新計算的時間。

Rough set theory, proposed by Pawlak in 1982 can be seen as a new mathematical approach to vagueness. It is capable of discovering important facts hidden in that data. However, previous literature indicated these rough set approaches cannot guarantee that the classification of a decision table is credible. Therefore, Tseng (2006) proposed the REA (Rule-Extraction Algorithm) to solve the problem. But the desired reducts are not necessarily unique since several reducts could include the same value of SI. Thus, Tseng (2008) proposed AREA (Alternative Rule Extraction Algorithm) to solve the non-complete rules problem. In addition, the current algorithms of rough set have the ability to generate a set of classification rules efficiently, but they cannot generate rules incrementally when new objects are given. And numerous studies of incremental approaches are not capable to deal with the problems of large database. Therefore, in this study, an incremental rule-extraction algorithm is proposed based on the AREA to solve the aforementioned problem. In addition, the AREA maybe generating repetitive rules, the algorithm is developed to exclude these repetitive rules in the solution search procedure. Using this algorithm, when a new object or attribute are added up to information system, it is unnecessary to re-compute rule sets from the very beginning, that can quick generate the complete and not repetitive rule. Resolve the incremental issues of new data add-in, hence a lot of time are saved.

List of Contents
誌 謝 i
摘 要 ii
Abstract iii
List of Contents iv
List of Figure v
List of Tables vi
1. Introduction 1
2. Literature Review 3
2.1 Approximations concepts in the rough set theory 3
2.2 Rough set based rule induction 7
2.2.2 Attribute reduction process 8
2.2.2 Rule induction process 10
2.3 The Related Incremental Approaches 15
2.4 Summary 17
3. Solution Approach 17
3.1 The Proposed Object Incremental Methodology 18
3.1.1 Structure of the proposed incremental rough set based rule induction 18
3.1.2 The proposed incremental object algorithm (IOA) 26
3.1.3 The time complexity of the proposed incremental algorithm (REMOVE) 30
3.2 The Proposed Attribute Incremental Methodology 31
3.2.1 Structure of the proposed incremental rough set based rule induction 31
3.2.2 The proposed incremental attribute algorithm (IAA) 36
3.2.3 The time complexity of the proposed incremental algorithm (REMOVE) 38
4. Case Study 39
4.1 Object Incremental 39
4.2 Attribute Incremental 51
5. Conclusion 64
References 65
Appendix A 71
Appendix B 78
Appendix C 85
Appendix D 92


List of Figure
Figure 3-1. Overall Architecture of the proposed Incremental Methodology. 18
Figure 3-2. The procedure of object incremental algorithm based on rule sets. 20
Figure 3-3. The procedure of step 7 from Figure 3-2. 22
Figure 3-4. The procedure of step 6 from Figure 3-2. 23
Figure 3-5. The procedure of step 8 from Figure 3-2. 24
Figure 3-6. The procedure of step 5 from Figure 3-2. 25
Figure 3-7. The procedure of the proposed attribute incremental algorithm. 32
Figure 3-8. The procedure of case-A-I from Figure 3-7. 33
Figure 3-9. The procedure of case-A-II from Figure 3-7. 34
Figure 3-10. The procedure of case-A-III from Figure 3-7. 35
Figure 4-1. The procedure of Case-O-I. 42
Figure 4-2. The procedure of Case-O-II. 45
Figure 4-3. The procedure of Case-O-IV. 48
Figure 4-4. The procedure of Case-A-I. 53
Figure 4-5 The procedure of Case-A-II. 57
Figure 4-6 The procedure of Case-A-III. 60









List of Tables
Table 3-1. An information table. 5
Table 3-2. The incremental attribute. 6
Table 4-1. The original information. 40
Table 4-2. Extended table. 40
Table 4-3. The final decision rules and alternative rules. 41
Table 4-4. The resulting concise rules. 41
Table 4-5. The incremental object in Case-O-I. 42
Table 4-6. Compute the reduct and SI of object 9. 43
Table 4-7. The result from steps 4 to 5 44
Table 4-8. The incremental object in Case-O-II. 45
Table 4-9. Compute SI of these reducts. 46
Table 4-10. The final decision rules and alternative rules. 47
Table 4-11. The incremental object in Case-O-IV. 48
Table 4-12. The summarized result from steps 1 to 4 49
Table 4-13. The summarized result from steps 7. 50
Table 4-14. The final decision rules and alternative rules. 50
Table 4-15. The original information. 52
Table 4-16. The final decision rules and alternative rules. 52
Table 4-17. The incremental attribute in Case-A-I. 53
Table 4-18. Add the new attribute set and identify the empty set of lower approximation. 54
Table 4-19.The result from steps 1 to2. 55
Table 4-20. The final decision rules and alternative rules. 56
Table 4-21. The incremental attribute in Case-A-II 58
Table 4-22 Add the new attribute set. 58
Table 4-23. The result from steps 2 to3. 59
Table 4-24. The final decision rules and alternative rules. 60
Table 4-25. The incremental attribute in Case-A-III. 61
Table 4-26. Add the new attribute set. 61
Table 4-27. The result from steps 2 to3. 62
Table 4-28. The final decision rules and alternative rules. 63

A.G. Jackson, Z. Pawlak, S.R. LeClair, 1998, "Rough sets applied to the discovery of materials knowledge," Journal of Alloys and Compounds, Vol. 279, No. 1, pp.14-21.
Bazan, J., Skowron, A. & Synak, P., 1994 "Dynamic reducts as a tool for extracting laws from decision tables," Proceedings of the Symp. on Methodologies for Intelligent Systems, Berlin, Germany, pp.346–355.
B.S. Ahn, S.S. Cho, C.Y. Kim, 2000, "The integrated methodology of rough set theory and artificial neural network for business failure prediction," Expert Systems with Applications, Vol. 18, No. 2, pp. 65–74.
Carey Goh, Rob Law, 2003, "Incorporating the rough sets theory into travel demand analysis," Tourism Management, Vol. 24, No. 5, pp.511-517.
Chen Degang, Wang Changzhong, Hu Qinghua, 2007, "A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets," Information Sciences, Vol. 177, No. 17, pp.3500-3518.
Dominik Ślezak, 2002, "Approximate Entropy Reducts," Fundamenta Informaticae, Vol. 53, No. 3-4, pp.365-390.
Degang Chen, E.C.C. Tsang, Daniel s. Yeung, Xizhao Wang, 2005, "The parametrization reduction of soft sets and its applications," Computers & Mathematics with Applications, Vol. 49, No. 5-6, pp.757-763.
Frank Witlox, Hans Tindemans, 2004, "The application of rough sets analysis in activity-based modeling. Opportunities and constraints," Expert Systems with Applications, Vol.27, No. 4, pp.585-592.
Ilona Jagielska, Chris Matthews, Tim Whitfort, 1999, "An investigation into the application of neural networks, fuzzy logic, genetic algorithms, and rough sets to automated knowledge acquisition for classification problems," Neurocomputing, Vol. 24, No. 1-3, pp.37-54.
James J.H. Liou, Gwo-Hshiung Tzeng, 2010, "A dominance-based rough set approach to customer behavior in the airline market," Information Sciences, Vol. 180, No. 11, pp.2230-2238.
James J.H. Liou , Gwo-Hshiung Tzeng, 2010, "A dominance-based rough set approach to customer behavior in the airline market, Information Sciences , Vol. 180, No.11, pp2230-2238.
Jan G. Basan, Andrzej Skowron, Piotr Synak, 1994, "Dynamic reducts as a tool for extracting laws from decision tables," Lecture Notes in Computer Science, Vol. 869, No.11, pp. 346-355.
Jerzy Błaszczyński, Roman Słowiński , 2003, "Incremental induction of decision rules from dominance-based rough approximations," Electronic Notes in Theoretical Computer Science, Vol. 82, No. 4, pp. 40-51.
Jhieh-Yu Shyng, Fang-Kuo Wang, Gwo-Hshiung Tzeng, Kun-Shan Wu, 2007, "Rough set theory in analyzing the attributes of combination values for the insurance market," Expert Systems with Applications, Vol. 32, No. 1, pp.56-64.
JingTao Yao , Joseph P. Herbert , 2009, "Financial time-series analysis with rough sets," Applied Soft Computing , Vol. 9, No. 3, pp.1000-1007.
Krzysztof Pancerz, 2009, "Some issues on extensions of information and dynamic information systems," Studies in Computational Intelligence, Vol. 205, pp.79-106.
Li Peng ,Wang Xiao-long ,Guan Yi, 2008, "Question classification with incremental rule learning algorithm based on rough set," Journal of Electronics & Information Technology, Vol. 30, No. 5, pp.1127-1130.
Lihe Guan, 2009, "An incremental updating algorithm of attribute reduction set in decision tables," Proceedings of 6th International Conference on Fuzzy Systems and Knowledge Discovery, Tianjin, China, pp.421-425.
Liu, Y., Xu, C., & Pan, Y., 2004, "An incremental rule extracting algorithm based on Pawlak reduction," IEEE International Conference on Systems, Zhejiang, China, pp. 5964-5968.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Michael Wimmer, Xiaowei Xu, 1998, "Incremental clustering for mining in a data warehousing environment," Proceedings of the Twenty-Fourth International Conference on Very Large Data Bases, New York, pp.323–333.
Marzena Kryszkiewicz, 1998, "Rough set approach to incomplete information systems," Information Sciences, Vol. 112, No.1-4, pp.39-49.
Masahiro Inuiguchi, 2005, "Several approaches to attribute reduction in variable precision rough set model," Modeling Decisions for Artificial Intelligence, Vol. 3558, pp.215-226.
Nadeem Ahmed Syed, Huan Liu, Kah Kay Sung, 1999, "Handling concept drifts in incremental learning with support vector machines," Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, New York, pp. 317 – 321.
Ning Shan, Wojciech Ziarko, 2007, "Data-based acquisition and incremental modification of classification rules," Computational Intelligence, Vol. 11, No.2, pp.357-370.
Ning Zhong, Ju-Zhen Dong, Setsuo Ohsuga, Tsau Young Lin, 1998," An incremental, probabilistic rough set approach to rule discovery," IEEE International Conference on Fuzzy Systems, Anchorage, AK , pp.933-938.
Pece V. Gorsevski, Piotr Jankowski, 2008, "Discerning landslide susceptibility using rough sets," Computers, Environment and Urban Systems, Vol. 32, No. 1, pp.53-65.
P.K. Maji, A.R. Roy and R. Biswas, 2002, "An application of soft sets in a decision making problem," Computers & Mathematics with Applications, Vol. 44, No. 8-9, pp.1077-1083.
Puntip Pattaraintakorn, Nick Cercone, 2008, "Integrating rough set theory and medical applications," Applied Mathematics Letters, Vol. 21, No. 4, pp.400-403.
Raymond R. Tan, 2005, "Rule-based life cycle impact assessment using modified rough set induction methodology," Environmental Modelling & Software, Vol. 20, No. 5, pp.509-513.
Salvatore Greco, Benedetto Matarazzo, Roman Slowinski, 2001, "Rough sets theory for multicriteria decision analysis," European Journal of Operational Research, vol. 129, No. 1, pp.1-47.
S. Asharaf, M. Narasimha Murty, and S.K. Shevade, 2006, "Rough set based incremental clustering of interval data," Pattern Recognition Letters, Vol. 27, No. 6, pp.515-519.
Sen Guo, Zhi-Yan Wang, Zhi-Cheng Wu, He-Ping Yan, 2005, "A novel dynamic incremental rules extraction algorithm based on rough set theory," In Proceedings of the fourth international conference on machine learning and cybernetics, Guangzhou, China, pp.18-21.
Shusaku Tsumoto, 1998, "Automated extraction of medical expert system rules from clinical databases based on rough set theory," Information Sciences, Vol. 112, No.1-14, pp.67-84.
Stefan R¨uping, 2001, "Incremental learning with support vector machines," First IEEE International Conference on Data Mining, Washington, USA, pp. 641-642.
Tae-Kyun Kim, Josef Kittler, Roberto Cipolla, 2006, "Incremental learning of locally orthogonal subspaces for set-based object recognition," The British Machine Vision Conference (BMVC), Edinburgh, pp.559–568.
Tong Lingyun, An Liping, 2002, "Incremental learning of decision rules based on rough set theory," Proceedings of the 4m World Congress on Intelligent Control and Automation, Tianjin, China, pp.420-425.
T.Y. Lin, Y. Y. Yao, 1996, "Mining soft rules using rough sets and neighborhoods," Proceedings of the Symposium on Modelling, Analysis and Simulation, Computational Engineering in Systems Applications, Lille, France, pp.1095-1100.
Tzu-Liang (Bill) Tseng, Chun-Che Huang, Fuhua Jiang, and Johnny C. Ho, 2006, “Applying a hybrid data mining approach to prediction problems: A case of preferred suppliers prediction,” International Journal of Production Research, Vol. 44, No. 14, pp.2935-2954.
Tzu-Liang (Bill) Tseng, Chun-Che Huang, Johnny C. Ho, 2008, "Autonomous Decision Making in Customer Relationship Management: A Data Mining Approach, " Proceeding of the Industrial Engineering Research 2008 Conference, Vancouver, British Columbia, Canada.
Wojciech Ziarko, 1993, "Variable precision rough set model," Journal of Computer and System Sciences, Vol. 46, No. 1, pp.39-59.
Wojciech Ziarko, 2004, "Incremental learning with hierarchies of rough decision tables," Proceedings of North American Fuzzy Information Processing Society Conference, Banff, Alberta, pp.802-808.
Wei-Wen Wu, 2009, "Exploring core competencies for R&D technical professionals," Expert Systems with Applications, Vol. 36, No. 5, pp.9574-9579.
Wei-Zhi Wu, Ju-Sheng Mi, Wen-Xiu Zhang, 2003, "Generalized fuzzy rough sets," Information Sciences, Vol. 151, pp.263-282.
Xiangyang Wang, Jie Yang, Richard Jensen, Xiaojun Liu, 2006, "Rough set feature selection and rule induction for prediction of malignancy degree in brain glioma," Computer Methods and Programs in Biomedicine, Vol. 83, No. 2, pp. 147-156.
Yu-Neng Fan, Tzu-Liang (Bill) Tseng, Ching-Chin Chern, Chun-Che Huang, 2009, "Rule induction based on an incremental rough set," Expert Systems with Applications , Vol. 36, No. 9, pp.11439-11450.
Yu-Ping Ou Yang, How-Ming Shieh, Gwo-Hshiung Tzeng, Leon Yen, Chien-Chung Chan, 2008, "Business Aviation Decision-Making Using Rough Sets," Lecture Notes in Computer Science, Vol. 5306 , pp329-338.
Zdzisław Pawlak, 1982, "Rough sets," International Journal of Information & Computer Sciences, vol. 11, pp.341-356.
Zdzisław Pawlak, 1991, Rough Sets: Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Boston.
Zdzis law Pawlak, Andrzej Skowron, 2007, "Rudiments of rough sets," Information Sciences, Vol. 177, No. 1, pp.3-27.