臺灣博碩士論文加值系統

為了提升產業界及企業內部運作及管理的效率及時效性，來探討關聯式資料庫的虛值，便成為一個重要的議題，許多學者採用不同的理論架構來解決虛值的問題，提出的理論以模糊集理論和基因演算法的概念最為常見，在本篇論文中，我們提出模糊基因演算法來估計關聯式資料庫中的虛值，此研究方法實為基因演算法概念的進一步推廣，並能達到更準確的虛值平均的估計值。

Different approaches to the estimation of null values in relational database systems have been developed in attempts to help enterprises operate effectively and properly. Bearing this in mind, many researchers have identified a number of theoretical frameworks, such as the applications of the fuzzy set theory and genetic algorithms, in order to deal with this problem. This thesis proposes a fuzzy genetic algorithm to estimate null values of attributes in relational database systems. This fuzzy genetic algorithm is regarded as a generalization of genetic algorithms. The proposed method, therefore; arrives at a higher average estimated accuracy rate than the existing methods.

Table of Content
The Paper Title . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Defence Committees'' Evaluation Sheet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Authorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Chinese Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
English Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .vi
Table of Content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
Charts and Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
1. Introduction 1
1.1 The background of the research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 The motivation of the research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2
1.3 The purpose and importance of the research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 The procedure of the research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
1.5 The organization of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
2. Literature Review 7
2.1 Relational database systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Domains, attribut, tuples and relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Null values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Null values and SQL language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Fuzzy sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6 Basic concepts of generating fuzzy rules from relational database systems . . . . . . . 16
2.7 Genetic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.8 Basics of genetic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.9 Encoding a problem with genetic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.10 One selecting method: elitism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.11 Genetic optimization tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23
3. Research Methods 25
3.1 Review of Chen-and-Yeh''s method, Chen-and-Chen''s and Chen-and-Huang''s
method: the structure of fuzzy representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25
3.2 Rule base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26
3.3 Estimating null values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Tuning the weights of the attributes using GAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.5 Calculation of the ‾tness degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.6 Selection operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.7 Crossover operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37
3.8 Mutation operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.9 Estimating null values in relational database systems (I) . . . . . . . . . . . . . . . . . . . . . . . . 41
3.10 Estimating null values with fuzzy genetic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.11 Estimating null values in relational database systems (II) . . . . . . . . . . . . . . . . . . . . . . 49
4. The Experimental Results 55
4.1 The result obtained by Chen-and-Huang''s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 The result obtained by our FGA method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5. Conclusions 61

[1] Y. M. Babad and J.A Hoffer, Even no data has a value," Commun ACM,vol. 27, no. 8, pp. 748-757, 1984.
[2] P. Bosc and H. Prade, An introduction to fuzzy sets and possibility the-ory based approaches to the treatment of uncertainty and imprecision indatabase management systems," In Proceedings of the Second Workshop onuncertainty Management in Information Systems: From Needs to Solutions(Catalina, California), 1993.
[3] P.P Bonnissone and R.M. Tong, Editorial: reasoning with uncertainty inexpert systems," Int. J. Man Mach. Stud., vol. 22, pp. 241-250, 1985.
[4] C.H. Chang and S.M. Chen, A new method to generate fuzzy rule fromnumerical data based on the exclusion of attribute terms," Proceedings ofthe 2000 International Computer Symposium: Workshop on Arti‾cial In-telligence, Chiayi, Taiwan, Republic of China, pp. 57-64, 2000.
[5] S.M. Chen and H.H. Chen, Estimating null values in the distributed rela-tional databases environment," Cybernetics and Systems, vol.31, no.8, pp.851-871, 2000.
[6] S.M. Chen and C.M. Huang, Generating weighted fuzzy rules from rela-tional database systems for estimating null values using genetic algorithms,"IEEE Trans. Fuzzy Systems vol.11, no.4, pp.495-506, 2003.
[7] S.M. Chen and H.R. Hsiao, A new method to estimate null values in rela-tional database systems based on automatic clustering techniques," Infor-mation Sciences, vol.169, pp.47-69, 2005.53
[8] S.M. Chen and W.T. Jong, Fuzzy query translation for relational databasesystems," IEEE Transactions on Systems, Man, and Cybernetics-Part B:Cybernetics vol. 27, no. 4, pp. 714-721, 1997.
[9] S.M. Chen and S.W. Lee, A new method to generate fuzzy rules relationaldatabase systems for estimating null values," Cybernetics and Systems ofInternational Journal vol.34, pp.33-57, 2003.
[10] S.M. Chen and H.L. Lin, Generating weighted fuzzy rules from traininginstances using genetic algorithms to handle the Iris data classi‾cation prob-lem," Journal of Information Science and Engineering, vol. 22, pp. 175-188,2006.
[11] S.M. Chen, S.H. Lee, and C.H. Lee, A new method for generating fuzzyrules from numerical data for handling classi‾cation problems," AppliedArti‾cial Intelligence, vol.15, pp. 645-664, 2001.
[12] S.M. Chen, S.H. Lee, and C.H. Lee, Generating fuzzy rules from numericaldata for handling fuzzy classi‾cation problems," Proceedings of the 1999National Computer Symposium, Taipei, Taiwan, Republic of China, vol. 2,pp. 36-343, 1999.
[13] E.F. Codd, Extending the database relational model to capture moremeaning," ACM Trans. Database Systems, pp.397-434, 1979.
[14] E.F Codd, A relational model for large shared data banks," CACM, vol.13, no. 6, June, 1970.
[15] C.H. Cheng and J.W. Wang, A new approach for estimating null value inrelational database," Soft Computing, vol.10, pp.104-114, 2006.54
[16] S.M. Chen and M.S. Yeh, Generating fuzzy rules from relational databasesystems for estimating null values," Cybernetics and Systems, vol. 29, no.6, pp. 363-367, 1997.
[17] S.M. Chen and M.S. Yeh, A method for generating fuzzy rules from rela-tional database systems for estimating null values," In: Leondes CT (ed)Intelligent systems: technology and applications, vol 4. CRC Press, BocaRaton, pp. 157-179, 2002.
[18] J.L. Castro and J.M. Zurita, An inductive learning algorithm in fuzzysystems," Fuzzy Sets and Systems, vol. 89, no. 2, pp. 193-203, 1997.
[19] C. J. Date, An introduction to database systems," Reading, MA: Addison-Wesley, 1995.
[20] D. Dubois and H. Prade, Possibility Theory: An Approach to the Comput-erized Processing of Uncertainty, Plenum, New York, 1988.
[21] D. Dubois and H. Prade, Certainty and uncertainty of (vague) knowledgeand generalized dependencies in fuzzy databases," In Proceedings of theInternational Fuzzy Engineering Symposium on 91 (Yokohama), pp. 239-249, 1991.
[22] R. Elmasri and S.B. Navathe, Fundamentals of database systems," Read-ing, MA: Addison-Wesley, 2004.
[23] D.E. Goldberg and J. Richardson, Genetic algorithms with sharing formultimodal function optimization," Genetic Algorithms and Their Appli-cations: Proceeding 2nd International Conference Genetic Algorithms, pp.41-49, Cambridge, MA, 1989.55
[24] G. Grahne, The problem of incomplete information in relationaldatabases," In Lecture Notes in Computer Science, vol. 554, Springer-Verlag, Berlin, 1991.
[25] J. Han J and M. Kamber, Data mining: concepts and techniques. MorganKaufmann, New York, 2000.
[26] J.H. Holland, Adaptation in natural and arti‾cial systems," MIT Press,Cambridge, MA, 1975.
[27] Z. Michalewicz and J.B. Krawezyk, A modi‾ed genetic algorithm for op-timal control problems," Computing Mathematics Applications, vol. 23, pp.3-94, 1992.
[28] K.F. Man, K.S. Tang, and S. Kwong, Genetic algorithms: concepts andapplications," IEEE Transactions on Industrial Electronics, vol. 43, no. 5,pp. 519-533, 1996.
[29] V. Owei, An intelligent approach to handling imperfect information inconcept-based natural language queries," ACM Trans. of Information Sys-tems, vol. 20, No. 3, pp. 291-328, 2002.
[30] S. Parsons, Current approaches to handling imperfect information in dataand knowledge bases," IEEE TKDE, vol. 8, No. 3, pp. 353-372, 1996.
[31] L.A. Zadeh, Fuzzy sets," Informative Control, vol. 8, pp. 338-353, 1965.