Hệ quyết định nhất quán và luật quan trọng - Nguyễn Đức Thọ

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 39, 10 - 2015 69 HỆ QUYẾT ĐỊNH NHẤT QUÁN VÀ LUẬT QUAN TRỌNG Nguyễn Đức Thọ1, Nguyễn Bá Tường2*, Nguyễn Hữu Đông2 Tóm tắt: Trong bài này nhóm tác giả giới thiệu một số tính chất liên quan đến các ma trận độ hỗ trợ, độ chính xác và độ phủ của các luật quyết đinh. Mục đích chính của bài viết là trình bày thuật toán tìm luật quan trọng sau khi dựa vào các tính chất được nêu ở trên. Đó là dựa vào các ma trận thưa của độ phủ, độ chính xác để tìm các luật quan trọng trong hệ quyết định nhất quán. Từ khóa: Tập thô, Độ hỗ trợ, Độ chính xác, Độ phủ, Khai thác dữ liệu. 1. ĐẶT VẤN ĐỀ Các luật trong hệ quyết định dựa trên nền lý thuyết tập thô được phát triển và nghiên cứu trong [1, 2, 3]. Mô hình xác suất tối thiểu của các luật được nghiên cứu để phân loại luật dựa vào độ chính xác và độ phủ cao được các tác giả quan tâm nghiên cứu và đã trình bày trong [4, 5]. Bản chất cốt lõi và cũng là kỹ thuật cơ bản khi nghiên cứu các luật trong hệ quyết định là xác định độ đo chất lượng của luật, các khái niệm về độ đo chất lượng của luật được nêu và xét trong [1, 4, 5, 6, 7, 8, 9, 14, 15]. Trong bài viết này chúng tôi tiếp tục nghiên cứu và phát triển các ý tưởng trên và dựa vào các ma trận độ hỗ trợ, độ chính xác, độ phủ v.v để xét và nghiên cứu phát triển các tri thức mới. Trong bài viết chúng tôi đã đưa ra được một số tính chất của các ma trận liện quan các luật từ đó nêu được thuật toán tìm luật quan trọng đơn giản và hiệu quả. 2. TỔNG QUAN VỀ LÝ THUYẾT HỆ TIN Các khái niệm cơ bản trong bài viết của chúng tôi được trích trong các tài liệu [1, 5, 6, 14, 15]. Định nghĩa 2.1. Hệ tin đầy đủ là S = ( U, A ), với U là tập hữu hạn khác rỗng các đối tượng, A là tập khác rỗng các thuộc tính. Giá trị thuộc tính a A của đối tượng u  U là a(u) và a(u) khác rỗng ( not null). Định nghia 2.2. Hệ quyết định đầy đủ DS = (U, C  D) là hệ tin đầy đủ, trong đó U là tập hữu hạn khác rỗng các đối tượng, A= C  D, với C là tập khác rỗng các thuộc tính được gọi là các thuộc tính điều kiện và D là tập các thuộc tính được gọi là các thuộc tính quyết định và C  D =  . Định nghĩa 2.3. Cho S = ( U, A) là hệ tin đầy đủ. Với mỗi tập con B  A, ta xác định quan hệ tương đương IND(B)  UxU, với IND(B) = { (u,v) UxU:  a B, a(u) = a(v)}. Phân hoạch của U sinh bởi IND(B) ký hiệu là U/B. Lớp tương đương ứng với u U là [u]B và [u]B = { v  U: (u,v) IND(B)} Định nghĩa 2.4. Cho DS = ( U, C  D ) là hệ quyết định đầy đủ. Ta sẽ ký hiệu U/C = { C1, C2, , Cm}, với Ci ( i = 1, 2, , m) là lớp điều kiện; U/D = { D1, D2, , Dn}, với Dj ( j= 1, 2, , n) là lớp quyết định. Ci U/C & Dj U/D, độ hỗ trợ ( support), độ chính xác (accuracy), độ phủ (coverage), độ lệch (error ratio) của luật Ci → Dj được xác định như sau: Độ hỗ trợ của luật Ci → Dj , ký hiệu Supp(Ci|Dj ) và Supp(Ci|Dj ) = | Ci  DJ| / | U| ; Độ chính xác của luật Ci → Dj, ký hiệu Acc(Ci|Dj ) và Acc(Ci|Dj ) = | Ci  DJ| / | Ci|; Độ phủ của luật Ci → Dj, ký hiệu Cov(Ci|Dj ) và Cov(Ci|Dj ) = | Ci  DJ| / | Dj|. Độ lệch của luật Ci → Dj, ký hiệu E(Ci|Dj ) và E(Ci|Dj ) = 1- Acc(Ci|Dj ). Ở đây | Ci| và | Dj| là lực lượng của các tập Ci và Dj tương ứng. Từ định nghĩa ta có các ma trận độ hỗ trợ, độ chính xác và độ phủ như sau: Công nghệ thông tin & Khoa học máy tính N. Đ. Thọ, N.B. Tường, N.H. Đông, “Hệ quyết định nhất quán và luật quan trọng.” 70 Supp(C|D) =                 ) D|Supp(C ... )D|Supp(C ) D|Supp(C . . ) D|Supp(C )... D|Supp(C ) D|Supp(C ) D|Supp(C )... D|Supp(C ) D|Supp(C nm2m1m n22212 n12111 Cov(C|D) =                   ) D|Cov(C ... )D|cov(C ) D|Cov(C . . ) D|Cov(C )... D|Cov(C ) D|Cov(C ) D|Cov(C )... D|Cov(C ) D|Cov(C nm2m1m n22212 n12111 Tương cho các a trận độ chính xác Acc(C⃒D) và độ lệch E(C⃒D). Tính chất 2.1.[15] 0  Acc(Ci|Dj )  1 và   n j 1 ji ) D|Acc(C = 1, Ci U/C. Tính chất 2.2.[15] 0  Cov(Ci|Dj )  1 và   m i 1 ji )D|Cov(C = 1, Dj U/D. Định nghĩa 2.5. Hệ quyết định DS = ( U, C  D ) là nhất quán ( consistent) nếu Ci U/C Dj U/D sao cho Ci  Dj. Định nghĩa 2.6. Cho DS = ( U, C  D ) là hệ quyết định; U/C = { C1, C2, , Cm}, U/D = { D1, D2, , Dn}. Ta nói luật Ci → Dj là luật quan trọng nếu Acc(Ci|Dj )  minAcc và Cov(Ci|Dj )  minCov. Trong đó các ngưỡng minAcc và minCov do người dùng xác định. 3. MỘT SỐ TÍNH CHẤT CỦA MA TRẬN ĐỘ HỖ TRỢ, ĐỘ CHÍNH XÁC, ĐỘ PHỦ VÀ THUẬT TOÁN TÌM CÁC LUẬT QUAN TRỌNG 3.1. Các tính chất Cho DS = ( U, C  D ) là hệ quyết định; U/C = { C1, C2, , Cm} và U/D = { D1, D2, , Dn}. Khi đó ta có mn luật quyết định Ci → Dj. Một cách tự nhiên ta có trị trung bình cộng của support, accuracy, coverage và độ lệch của các luật. Đinh nghiã 3.1. Trị trung bình cộng của supports, accuracy và coverage của S xác định tương ứng như sau: AVG(Supp(S)) = nm. 1   m i 1   n j 1 ji ) D|Supp(C AVG(Acc(S)) = nm. 1   m i 1   n j 1 ji ) D|Acc(C AVG(Cov(S)) = nm. 1   m i 1   n j 1 ji ) D|Cov(C | Tính chất 3.1. 0  supp(Ci|Dj )  1 và   n j 1 ji ) D|Supp(C = | Ci | / | U|, Ci U/C Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 39, 10 - 2015 71 Chứng minh  x  Ci  Dj sao cho x  Dj và vì Dj Dk = if k  J nên   n j 1 ji ) D|Supp(C = | U| |D C | 1i  + | U| |D C | 2i  + + | U| |D C | ni  = | U| |)D...D(D C | n21i  = | U| | U C | i  = | U| | C | i Tính chất 3.2. 0  Supp(Ci|Dj )  1 và   m i 1 ji ) D|Supp(C = | DJ | / | U|, Dj U/D. Chứng minh Tương tự như tính chất 3.1 ta có   m i 1 ji ) |DSupp(C = | U| |D C | j1  + | U| |D C | j2  + + | U| |D C | jm  = | U| |)C...C(C D | m21j  = | U| | U D | j  = | U| | D | j Tính chất 3.3.   m i 1   n j 1 ji ) |DSupp(C = 1. Chứng minh Theo tính chất 3.1 ta có   m i 1   n j 1 ji ) |DSupp(C =   m i 1 | U| | Ci | = | U| | U| = 1. Tính chất 3.4. AVG(Supp(S)) = nm. 1   m i 1   n j iCSupp 1 ( | D j ) = nm. 1 . Chứng minh tính chất 3.4 suy trực tiếp từ tính chất 3.3. Tính chất 3.5. AVG(Acc(S)) = nm. 1   m i 1   n j 1 ji ) D|Acc(C = n 1 Chứng minh tính chất 3.5 suy trực tiếp từ tính chất 2.1 Tính chất 3.6. AVG(Cov(S)) = nm. 1   m i 1   n j 1 ji ) D|Cov(C = m 1 Chứng minh tính chất 3.6 suy từ tính chất 2.2. Tính chất 3.7.   n j 1 E(Ci|Dj) = n-1. Chứng minh Công nghệ thông tin & Khoa học máy tính N. Đ. Thọ, N.B. Tường, N.H. Đông, “Hệ quyết định nhất quán và luật quan trọng.” 72   n j 1 E(Ci|Dj) =   n j 1 ( 1 - | Ci  DJ| / | Ci|) = n -   n j 1 | Ci  DJ| / | Ci| = n – (| Ci  D1| + | Ci  D2|+ + | Ci  Dn|)/| Ci| = n – ( |Ci  ( D1 D2  ...  Dn)|)/ | Ci| = n - | Ci|/| Ci| = n-1. Tính chất 3.8.   m i 1   n j 1 E(Ci|Dj) = m(n-1). Chứng minh tính chất 3.8 suy từ tính chất 3.7. Tính chất 3.9. AVG(E(S)) = nm. 1   m i 1   n j 1 E(Ci|Dj) = n n 1 Chứng minh tính chất 3.9 được suy từ định nghĩa và tính chất 3.8. Tính chất 3.10. Cho DS = ( U, C  D ) là hệ quyết định nhất quán; U/C = { C1, C2, , Cm}, U/D = { D1, D2, , Dn}. Với Ci  U/C ta có: a. Giá trị mỗi phần tử của ma trận Acc(C|D) chỉ có thể là 0 hoặc 1. b. Trên mỗi dòng của ma trận Acc(C|D) có duy nhất một số 1 c. Trên mỗi dòng của ma trận Cov(C|D) có duy nhất một phần tử Cov(Ci|Dj) = j i D C 3.2. Thuật toán tìm các luật quan trọng Lưu ý: liên quan giữa hai ma trận Acc(C|D) và Cov(C|D) là Acc(Ci|Dj) =1 Cov(Ci|Dj) = j i D C . Thuật toán tìm các luật quan trọng Input DS = ( U, C  D ) là hệ quyết định nhất quán, minAcc, minCov; Output Tập các luật quan trọng IR. Thuật toán 1. Tính U/C = {C1, C2, , Cm} 2. Tính U/D = {D1, D2, , Dn} 3. Tính Acc(C|D) 4. Tính Cov(C|D) 5. IR:=  6. Với mỗi Cov(Ci|Dj) trong Cov(C|D) nếu Cov(Ci|Dj) > minCov then IR:= IR  Ci → Dj 7. Kết thúc vòng lặp 6 ta có tập luật quan trọng IR. 4. MÔ PHỎNG VÍ DỤ Trong phần này chúng ta minh họa một ví dụ để làm sáng tỏ các ý tưởng vừa nêu ở các phần trên. Cho hệ quyết định nhất quán như trong bảng 1 với U = { x1, x2, , x8 }, C = { a1, a2, a3}, D ={d}. Khi đó U/C = {C1, C2, C3, C4, C5} và C1= { x1, x8 }, C2 = { x2}, C3 = { x3, x7 }, C4 = { x4 }, C5 = { x5, x6 }; U/D = {D1, D2} và D1= { x1, x2, x5, x6, x8 }, D2 = { x3, x4, x7} Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 39, 10 - 2015 73 Bảng 1. Hệ quyết định nhất quán. U a1 a2 a3 d x1 1 1 1 1 x2 1 1 0 1 x3 2 0 0 0 x4 0 0 0 0 x5 2 2 0 1 x6 2 2 0 1 x7 2 0 0 0 x8 1 1 1 1 Supp(C|D) =                 0.00 0.25 0.125 0.00 0.25 0.00 0.00 0.125 0.00 0.25 Acc(C|D) =                 0.00 1.00 1.00 0.00 1.00 0.00 0.00 1.00 0.00 1.00 Cov(C|D) =                 0.00 0.40 0.33 0.00 0.66 0.00 0.00 0.2 0.00 0.40 Trong trường hợp này ta có n = 2, m = 5 và AVG(supp(S)) = 0.1, AVG(Acc(S)) = 0.5, AVG(cov(S)) = 0.2. Từ Cov(C|D), nếu đặt minAcc = 0.5 và minCov = 0.4 ta có tập luật quan trọng: IR = { C1 → D1, C3 → D2, C5 → D1}. 5. KẾT LUẬN Trong bài viết nhóm tác giả đã nêu được một số tính chất quan trọng liên quan các ma trận độ hỗ trợ, độ chính xác, độ phủ của các luật quyết định trong hệ quyết định. Từ đó nêu được thuật toán tìm luật quan trọng đơn giản và hiệu quả. Các kết quả trong bài viết sẽ làm cơ sở để các tác giả tiếp tục nghiên cứu và phát triển các kết quả mới. TÀI LIỆU THAM KHẢO [1]. Z. Pawlak, “Rough set theory and its application”. Journal of telecommunications and Information technology 3/2002. [2]. M. Beynon, N. Driffeld, “An illustration of variable precision rough sets model: an analysis of the finding of the UK Monopollies and Mergers Commission”. Computers and operations Research, 32, 2005, pp. 1739-1759. Công nghệ thông tin & Khoa học máy tính N. Đ. Thọ, N.B. Tường, N.H. Đông, “Hệ quyết định nhất quán và luật quan trọng.” 74 [3]. C. Su, J. Hsu, “Precision parameter in the variable precision rough sets model: an application”. The International Journal of Management Science, 34, 2006, pp. 149-157. [4]. S. Tsumoto, “Extraction of expert decision process from clinical databases using rough set model”. In Proceeding of PKDD 1997, pp. 58-67. [5]. S. sumoto, “Accuracy and coverage in rough set rule induction”. In: J. Alpigini et al. (Eds): RSCTC 2002, LNAI, 2475, pp. 373-380. [6]. W. Zarko, “Variable precision rough set model”. Journal of Computer and System Science, 46, 1993, pp. 39-59. [7]. Y. Yao, S.K.M. Wong, “A decision theoretic frmamework for approximating concept”. International Journal of Man-machine Studies, 37, 1992, pp. 793-809. [8]. Y. Yao, “Decision- theoretic rough set model”. In: The Second Iternational Conference on Rough Set and Knowledge Technology, LNAI, 4481, Springer, Heidelberg 2007, pp.1-12. [9]. Y. Yao, “Probabilistic rough set approximations”. International Journal of Approximate Reasoning, 49, 2008, pp. 255-271. [10]. A. Skowron, C. Rauszer, “The discernibility matrices and function in information system”. Intelligent Decision Support, Dordrecht, Kluwer Academic publishers, 1992, pp. 331-362. [11]. L. Tong, L. An, “Incremental learning of decision rules based on rough set theory”. In: Proceedings of the Word Congress on Intelligent Control and Automation (WCICA 2002), pp. 420-425. [12]. B. Jerzy, R. Slominski, “Incremental Induction of decision rules from dominance-based rough set approximation”. Electronic Notes in Theoretical ComputerScience, 82, 2003, pp. 40-51. [13]. Z. Zheng, G.Y. Wang, “RRIA: A rough set and rule tree based incremental knowledge acquisition algorithm”. Fundamenta Informaticae, 59(2-3), 2004, pp. 299-231. [14]. D. Liu, P. Hu, C. Jiang, “The methodology of the variable precision rough set increment study based on completely information system”. In the third International Conference on Rough Sets and Knowledge Technolgy, LNAI 5009, Springer, Heidlberg 2008, pp. 276-283. [15]. D. Liu, T. Li, D. Ruan, W. Zou, “An Incremental Approach for inducing knowledge from Dinamic Information Systems”. Fundamenta Informaticae, 94, 2009, pp. 245-260. ABSTRACT AN ALGORITHM FOR COMPUTING IMPORTANT RULES IN CONSISTENT DECISION SYSTEM Rough set analysis are closely related with accuracy and coverage. There have been studies and results of accuracy and coverage for rule induction have been discussed and showed in [1, 5, 6, 14, 15]. In this paper, the following characteristics of accuracy and coverage are further investigated. Keywords: The rough set, Support, Accuracy, Coverage, Data mining. Nhận bài ngày 30 tháng 7 năm 2015 Hoàn thiện ngày 20 tháng 8 năm 2015 Chấp nhận đăng ngày 22 tháng 10 năm 2015 Địa chỉ: 1 Học viện Kỹ thuật quân sự; 2 Đại học Sư phạm kỹ thuật Hưng Yên.