Kết hợp học quan hệ và học thống kê cho phân
lớp dữ liệu đa quan hệ

Đặng Đức Thảo

Trường Đại học Công nghệ
Luận văn ThS chuyên ngành: Công nghệ thông tin; Mã số: 1 01 10
Người hướng dẫn: PGS.TS. Trần Đình Quế
Năm bảo vệ: 2007


Abstract: Trình bày các vấn đề cơ bản của phân lớp dữ liệu đa quan hệ, sự khác biệt
giữa dữ liệu đa quan hệ và dữ liệu phẳng, một số cách tiếp cận giải quyết bài toán
phân lớp dữ liệu đa quan hệ. Tập trung khảo sát hệ thống FOIL - một hệ thống lập
trình quy nạp tiêu biểu được sử dụng rộng rãi nhất, cách tiếp cận kết hợp hệ thống
FOIL với mô hình thống kê và đề xuất cho việc mở rộng cách tiếp cận kết hợp FOIL
với mô hình Naive Bayes. Áp dụng các kỹ thuật kết hợp này trong bài toán phân lớp
tài liệu trong cơ sở dữ liệu thư viện địa chất

Keywords: Công nghệ thông tin, Cơ sở dữ liệu, Lập trình, Phân lớp dữ liệu, Đa quan
hệ

Content
MỞ ĐẦU
Đặt vấn đề
Ngày nay, thông tin chủ yếu được lưu trữ trong các cơ sở dữ liệu. Phân lớp dữ liệu
trên các cơ sở dữ liệu này là một bài toán hết sức quan trọng và được áp dụng để giải quyết
nhiều bài toán thực tế như phát hiện dự đoán lỗi, đánh giá thị trường Để giải quyết bài toán
phân lớp, nhiều giải thuật đã được phát triển như giải thuật SVM ([26], [27]), cây quyết định
([2], [3], [46]), mô hình Naïve Bayes ([6], [22], [23], [25], [28]) Tuy nhiên phần lớn các
giải thuật này đều nhằm xử lý dữ liệu ở dạng phẳng hay dạng bảng đơn trong mô hình cơ sở

dữ liệu. Trong khi đó, hầu hết dữ liệu ngày nay đều được lưu trữ trong các cơ sở dữ liệu đa
quan hệ. Để áp dụng được các kỹ thuật phân lớp dữ liệu này đòi hỏi cần phải thực hiện sự
chuyển đổi từ dữ liệu đa quan hệ về dạng dữ liệu phẳng. Việc chuyển đổi này có nguy cơ dẫn
đến việc sinh ra không gian dữ liệu lớn và có khả năng làm mất mát thông tin [20].
Nhiều cách tiếp cận đã được phát triển cho bài toán phân lớp dữ liệu đa quan hệ như
cây quyết định quan hệ [30], luật quan hệ kết hợp [31]…Trong đó, cách tiếp cận dựa trên lập
trình logic quy nạp (Inductive Logic Programming - ILP) là cách tiếp cận nổi bật nhất và
được sử dụng rộng rãi nhất như hệ thống FOIL của Quinlan [51]. Tuy vậy về cơ bản, FOIL
cũng như các hệ thống dựa trên ILP thường không thích nghi được khi áp dụng trên các tập
dữ liệu lớn hay các tập dữ liệu có nhiễu ([30], [31]). Điều này đã dẫn đến phát triển các
phương pháp nhằm nâng cao hiệu quả của các hệ thống dựa trên ILP nói chung và hệ thống
FOIL nói riêng. Trong số các cách tiếp cận để phát triển FOIL thì cách tiếp cận kết hợp FOIL
với các kỹ thuật học thống kê là một trong những cách tiếp cận quan trọng và phát triển nhất
trong những năm gần đây ( [13], [14], [15], [16], [24], [32], [33], [44], [48], [49], [50]).
Mặt khác, tại Trung tâm Thông tin Lưu trữ Địa chất, Cục Địa chất và Khoáng sản
Việt Nam, chúng tôi có một cơ sở dữ liệu quan hệ về thông tin các tài liệu tại Thư viện Địa
chất. Trải qua một thời gian dài phát triển từ năm 1997 đến nay, số lượng bản ghi trong cơ sở
dữ liệu vào khoảng hơn 24000 bản ghi. Đây là một cơ sở dữ liệu rất quan trọng đối với Thư
viện Địa chất nói riêng cũng như cho lĩnh vực khoa học địa chất nói chung. Mỗi bản ghi
trong cơ sở dữ liệu này tương ứng với các thông tin về một tài liệu trong thư viện như tên tài
liệu, tên dịch, nguồn trích, ký hiệu kho, ISBN, chủ đề, tác giả, từ khóa…Trong đó, trường
thông tin chủ đề là trường thông tin rất quan trọng. Nó giúp người quản lý có thể phân loại tài
liệu cũng như tìm kiếm hay tạo báo cáo theo các chủ đề khác nhau. Tuy nhiên, đến năm 2005
trường thông tin chủ đề này mới được bổ sung vào cấu trúc cơ sở dữ liệu. Do đó, trong số
hơn 24000 bản ghi có trong cơ sở dữ liệu, chỉ có khoảng 2000 bản ghi đã được cập nhật chủ
đề. Vấn đề được đặt ra là liệu có thể ứng dụng các phương pháp phân lớp dữ liệu quan hệ,
đặc biệt là các cách tiếp cận dựa trên nghiên cứu kết hợp giữa FOIL và học thống kê, để giải
quyết bài toán phân loại chủ đề cho các bản ghi còn lại trong mô hình cơ sở dữ liệu thư viện
địa chất này.
Mục tiêu của luận văn

Luận văn này nhằm đến hai mục tiêu chính:
 Nghiên cứu kỹ thuật phân lớp dữ liệu đa quan hệ dựa trên lập trình logic quy nạp,
hệ thống FOIL và đặc biệt là các cách tiếp cận kết hợp học thống kê vào hệ thống
FOIL nhằm nâng cao hiệu quả trong việc giải quyết các bài toán phân lớp.
 Áp dụng kỹ thuật phân lớp dữ liệu quan hệ dựa trên kết hợp học thống kê và hệ
thống FOIL vào bài toán phân lớp tài liệu trong cơ sở dữ liệu Thư viện Địa chất dựa
theo chủ đề.
Tóm tắt nội dung luận văn
Chương 1: Phân lớp dữ liệu đa quan hệ. Trong chương này, luận văn sẽ trình bày
các vấn đề cơ bản của phân lớp dữ liệu đa quan hệ, sự khác biệt giữa dữ liệu đa quan hệ và dữ
liệu phẳng. Đồng thời, nêu một số cách tiếp cận giải quyết bài toán phân lớp dữ liệu đa quan
hệ.
Chương 2: Lập trình logic quy nạp. Trong chương này, luận văn sẽ trình bày về lập
trình logic quy nạp và tập trung trình bày hệ thống FOIL – một hệ thống lập trình quy nạp
tiêu biểu và được sử dụng rộng rãi nhất.
Chương 3: Kết hợp FOIL với học thống kê. Trong chương này, luận văn sẽ trình
bày về cách tiếp cận kết hợp hệ thống FOIL với mô hình thống kê, tiêu biểu là mô hình Naïve
Bayes và mở rộng của nó. Đồng thời cũng sẽ trình bày một số đề xuất cho việc mở rộng cách
tiếp cận kết hợp FOIL và mô hình Naïve Bayes.
Chương 4: Thực nghiệm và kết quả. Trong chương này, luận văn sẽ trình bày quá
trình thực nghiệm và các kết quả đạt được. Từ đó, đưa ra các kết luận dựa trên thực nghiệm
đối với hai mục tiêu chính của luận văn. Thứ nhất là các kết quả so sánh của cách tiếp cận kết
hợp FOIL với mô hình NB; đề xuất kết hợp FOIL và BAN và sử dụng ước lượng m trong kết
hợp FOIL với mô hình NB. Thứ hai là áp dụng các kỹ thuật kết hợp này trong bài toán phân
lớp tài liệu trong cơ sở dữ liệu thư viện địa chất theo chủ đề.
Kết luận nêu lên tổng kết của luận văn, ý nghĩa và mục tiêu đạt được cũng như các
hướng nghiên cứu sắp tới.

References
[1] C.F. Aliferis, D. Hardin, P. P. Massion (2002) “Machine Learning Models For Lung

Cancer Classification Using Array Comparative Genomic Hybridization”. In:
Proceedings of the 2002 American Medical Informatics Association (AMIA) Annual
Symposium, 2002, page 7-11.
[2] A. Atramentov (2003) “Multi-relational decision tree algorithm - implementation and
experiments”. MS. Thesis. Iowa State University, Ames, Iowa.
[3] A. Berson, S. Smith, K. Thearling “An Overview of Data Mining Techniques”:

[4] J.Bockhorst, I. Ong (2004) “FOIL-D: Efficiently Scaling FOIL for Multi-relational
Data Mining of Large Dataset”,
[5] D. Caragea (2004) “Learning classifiers from distributed, semantically heterogeneous,
autonomous data sources”. Ph.D Thesis. Iowa State University.
[6] D. Caragea, J. Pathak, J. Bao, A. Silvescu, C. Andorf, D. Dobbs, V. Honavar (2004)
“Information Integration and Knowledge Acquisition from Semantically
Heterogeneous Biological Data Sources”. In: Proceedings of the 2nd International
Workshop on Data Integration in Life Sciences (DILS'05), San Diego, CA.
[7] B. Cestnik, I. Bratko (1991) “On estimating probabilities in tree pruning”. In Proc.
Fifth European Working Session on Learning, page 151-163. Y.Kodratoff, Springer,
Berlin.
[8] B. Cestnik (1990) “Estimating probabilities: A crucial task in machine learning”. In
Proc. Ninth European Conference on Artificial Intelligence, page 147-149. Pitman,
London.
[9] B. Cestnik (1990) “Estimating probabilities in machine learning”. Ph D thesis,
Faculty of Electrical Engineering and Computer Science, University of Ljubljana,
Ljubljana, Slovenia.
[10] P. K. Chan, Wei Fan, A. L. Prodromidis, S. J. Stolfo (1999) “Distributed Data Mining
in Credit Card Fraud Detection”. IEEE Intelligent Systems, Bd. 14, Nr. 6, S. 67 74,
1999.
[11] J. Cheng, R. Greiner (1999) “Comparing Bayesian Network Classifiers”. In
Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI'99),
pages 101 107. Morgan Kaufmann Publishers, 1999.

[12] P. Clark, T. Niblett (1989) “The CN2 induction algorithm”. Machine Learning, 3(4):
page 261-283.
[13] M.Craven & S.Slattery (1998) “Combining Statiscal and Relational Methods for
learning in Hypertext Domains”. In Proc. Eighth International Conference on
Inductive Logic Programming, Springer-Verlag.
[14] M.Craven & S.Slattery (2001) “Relational learning with statiscal predicate invention:
Better models for hypertext”. Machine Learning, 43(1-2) page 97-119, 2001.
[15] J. Davis, I. Ong, D. Page, I. Dutra (2004) “Using Bayesian classifiers to combine
rules”. In Third workshop on Multi-relational Data Mining (MRDM-2004) in
conjunction with the Tenth ACM SIGKDD International Conference of Knowledge
Discovery and Data Mining (KDD-2004), Seatle, Washington, USA.
[16] J. Davis, E. Burnside, D. Page, I. Dutra (2005) “An intergrated approach to learning
Bayesian networks of rules”. In Proc. Sixteenth European Conference on Machine
Learning (ECML-2005), volume 3720 of Lecture Notes in Computer Science, page
84-95, Springer.
[17] S.Dzeroski (1991) “Handling noise in inductive logic programming”. Master’s thesis,
Faculty of Electrical Engineering and Computer Science, University of Ljubljana,
Ljubljana, Slovenia.
[18] N.Lavrac & S.Dzeoski (1994) “Inductive Logic Programming: Techniques and
Applications”. Ellis Horwood, Chichester.
[19] S.Dzeoski & N.Lavrac, editor (2001) “Relational Data Mining”. Springer, Berlin.
[20] S.Dzeroski (2003) “Multi-relational data mining: An introduction”, SIGKDD
Explorations 5(1) page 1-16 (2003)
[21] S. Dzeoski & I. Bratko (1992) “Using m-estimate in inductive logic programming”. In
Proc. Workshop on Logical Approaches to Machine Learning, Tenth European
Conference on Artificial Intelligence, Viena, Austria.
[22] Charles Elkan (1997) “Naïve Bayesian Learning”. Department of Computer Science -
Harvard University.
[23] L. De Ferrari (2005) “Mining housekeeping genes with a Naive Bayes classifier”
Master of Science Thesis, School of Informatics University of Edinburgh.

[24] P. Flach, N.Lachile (2004) “Naïve Bayesian classification of structure data”. Machine
Learning, 57(3), page 233-269.
[25] N. Friedman, D. Geiger, M. Goldszmidt (1997) “Bayesian Network Classifiers”.
Journal of Machine Learning, volume 29, number (2-3), page 131-163.
[26] I. Guyon, J. Weston, S. Barnhill, V. Vapnik (2000) “Gene Selection for Cancer
Classification using Support Vector Machines”. Journey of Machine Learning Volume
46 , Issue 1-3 Pages: 389 – 422. ISSN:0885-6125 ( 2002)
[27] Thorsten Joachims (2001) “A Statistical Learning Model of Text Classification for
Support Vector Machines”. In: Proceedings of {SIGIR}-01, 24th {ACM} International
Conference on Research and Development in Information Retrieval.
[28] Eamonn J. Keogh, Michael J. Pazzani (1999) “Learning Augmented Bayesian
Classifiers: A Comparison of Distribution-based and Classification-based
Approaches”. In: Proceedings of the Seventh International Workshop on Artificial
Intelligence and Statistics (Ft. Lauderdale, FL, 1999) page 225-230.
[29] M.Kirsten, S.Wrobel, T.Horvath (2001) “Distance based approaches to Relational
Learning and Clustering”. In [19] page 213-232.
[30] S. Kramer & G.Widmer (2001) “Inducing Classification and Regression Tree in First
Order Logic”. In [19] pages 140-159.
[31] L.Dehaspe & H.Toivonen (2001) “Discover of Relational Association Rules”. In [19]
page 189-212.
[32] N. Landwehr, K. Kersting, L.Raedt (2005) “Integrating Naive Bayes and FOIL”. In
Proc. Twentieth National Conference on Artificial Intelligence (AAAI-2005), page
795-800, Pittsburgh, Pennsylvania, USA.
[33] N. Landwehr, K. Kersting, L.Raedt (2007) “Integrating Naive Bayes and FOIL”. In
Journal of Machine Learning Research 8, page 481-507.
[34] N. Lavrac (1990) “Principles of knowledge acquisition in expert systems”. Ph D thesis,
Faculty of Technical Science, University of Maribor, Maribor, Slovenia.
[35] N.Lavrac, S.Dzeroski, M.Grobenik (1991) “Learning nonrecursive definitions of
relation with LINUS”. In Proc. Fifth European Working Session on Learning, page
265-281. Kodratoff, Y., Springer, Berlin.

[36] Xiaoli Li, Bing Liu (2002) “Learning to Classify Texts Using Positive and Unlabeled
Data”. In: Proceedings of Eighteenth International Joint Conference on Artificial
Intelligence (IJCAI-03).
[37] J. Lloyd (1987). “Foundations of Logic Programming”. Springer, Berlin, 2nd editon.
[38] J.Lloyd (1990) editor, “Computational Logic”. Springer, Berlin.
[39] R.Michalski (1983) “A theory and methodology of inductive learning”. In Machine
Learning: An artificial inteligence approach, volume I, page 83-134, Tioga, Palo Alto,
CA.
[40] R. Michalski, I. Mozetic, J. Hong, N. Lavrac (1986) “The multipurpose incremental
learning system AQ15 and its testing application on three medical domains”. In Proc.
Fifth National Conference on Artificial Intelligence, page 1041-1045. Morgan
Kaufmann, San Mateo, CA.
[41] D. Michie, D.J.Spiegelhalter, C.C. Taylor (1994). “Machine Learning, Neural and
Statistical Classification”.
[42] S.Muggleton. (1991) “Inductive logic programming” New Generation Computing,
8(4): page 295-318.
[43] S.Muggleton, editor (1992) “Inductive Logic Programming” Academic Press, London.
[44] J. Neville, D. Jensen, B. Gallagher (2003) “Simple estimators for relational Bayesian
classifier”. In Proc. Third IEEE International Conference on Data mining (ICDM
2003), page 609-612, Melbourne, Florida, USA. IEEE Computer Society.
[45] K. Nigam, A.K. Mccallum, S. Thrun, T. Mitchell (2000) “Text Classification from
Labeled and Unlabeled Documents using EM”. Journal of Machine Learning,
volume 39, number 2/3, page 103-134.
[46] C. Phua, D. Alahakoon, V. Lee (2004) “Minority Report in Fraud Detection:
Classification of Skewed Data”. ACM SIGKDD Explorations Newsletter Volume
6, Issue 1 (June 2004) Special issue on learning from imbalanced datasets page 50–
59.
[47] G. Plotkin (1969) “A note on inductive generalization”. In D. Michie, editor, Machine
Intelligence 5, page 153-163, Edinburgh University Press, Edinburgh.
[48] U. Pompe, I.Kononenko (1995) “Naïve Bayesian classifier within ILP-R”. In Proc. of

Fifth International Workshop on Inductive Logic Programming (ILP-1995), page 417-
436, Tokyo, Japan, 1995.
[49] A. Popescul, H. Ungar, S. Lawrence, M. Pennock (2002) “Towards Structural
Logistic Regression: combining relational and Statistical Learning”. Multi-Relational
Data Mining Workshop at KDD-2002.
[50] A. Popescul, H. Ungar, S. Lawrence, M. Pennock (2003) “Statiscal Relational
Learning for Document Mining”. In Proceedings of IEEE Intermational Conference
on Data Mining, ICDM 2003.
[51] J. Quinlan (1990) “Learning logical definitions from relations”. Machine Learning,
5(3): page 239-266.
[52] A. Srinivasan, S. Muggleton, D.King, Sternberg (1996) “Theories for mutagenicity: A
study of first-order and feature based induction”. Artificial Intelligence, 85: page 277-
299.
[53] R. Tailby, R. Dean, B. Milner, D. Smith (2006) “Email classification for automated
service handling”. In: Proceedings of the 2006 ACM symposium on Applied
computing, Dijon, France SESSION: Information access and retrieval (IAR) Page
1073 – 1077.
[54] Van Laer & De Raedt (2001) “How to Ugrade Propositional Learners to First Order
Logic: A Case Study”. In [19] page 235-261.
[55] X.Yin, J. Han, J. Yang, S. Yu (2006) “Crossmine: Efficient Classification Across
Multiple Database Relations”. IEEE Transactions on Knowledge and Data
Engineering, vol. 18, no. 6, pp. 770-783, Jun., 2006.