Tóm tắt Luận án Khai phá luật quyết định trên mô hình dữ liệu dạng khối

ong nước ta đều nhằm mục đích tìm ra tri thức có ý nghĩa, cụ thể là các luật trên các mô hình dữ liệu khác nhau với các hướng nghiên cứu khác nhau. Một hướng tiếp cận với mô hình dữ liệu dạng khối của nhóm tác giả với mục đích theo dõi được các luật diễn ra trong một quá trình thay đổi theo thời gian, giai đoạn chính là mong muốn đóng góp được của luận án. 2. Mục tiêu nghiên cứu của luận án Mục tiêu của luận án tập trung giải quyết ba bài toán: - Tìm các luật quyết định trên khối và trên lát cắt. - Tìm các luật quyết định giữa các nhóm đối tượng trên khối khi có sự thay đổi giá trị thuộc tính, cụ thể là khi làm mịn, hoặc làm thô giá trị thuộc tính. - Tìm các luật quyết định giữa các nhóm đối tượng trên khối khi bổ sung, loại bỏ phần tử của khối. 3. Bố cục của luận án Luận án gồm phần mở đầu, 3 chương tiếp theo và cuối cùng là phần kết luận. 2 Chương đầu trình bày một số khái niệm cơ sở về mô hình dữ liệu dạng khối, khai phá dữ liệu, khai phá luật quyết định và quan hệ tương đương. Chương 2 trình bày hai kết quả nghiên cứu: thứ nhất là đề xuất thuật toán MDLB để tìm các luật quyết định trên khối và lát cắt của khối. Thứ hai là đề xuất thuật toán MDLB_VAC nhằm tìm ra các luật quyết định trên khối trong trường hợp giá trị thuộc tính thay đổi. Thêm vào đó, đưa ra các nghiên cứu lí thuyết về khai phá trên khối, tính toán độ phức tạp và cài đặt thử nghiệm các thuật toán đề xuất. Chương 3 xây dựng mô hình tăng hoặc giảm tập đối tượng của khối quyết định; đề xuất hai thuật toán gia tăng MDLB_OSC1 và MDLB_OSC2 để tìm các luật quyết định trên khối quyết định khi tập đối tượng thay đổi và cài đặt thử nghiệm. CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ 1.1. Khai phá dữ liệu 1.1.1. Định nghĩa khai phá dữ liệu Khai phá dữ liệu là khâu chủ yếu trong quá trình phát hiện ra tri thức trong cơ sở dữ liệu. Quá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự báo, ra quyết định trong kinh doanh, quản lý, các hoạt động sản xuất, 1.1.2. Một số kỹ thuật khai phá dữ liệu - Phân lớp (Classification). - Dự đoán (Prediction). - Luật kết hợp (Association Rule). - Phân cụm (Clustering). 1.2. Khai phá luật quyết định 3 1.2.1. Hệ thông tin Định nghĩa 1.1 (Hệ thông tin) Hệ thông tin là một bộ bốn S = (U,A,V,f) trong đó U là tập đối tượng là một tập hữu hạn, khác rỗng các đối tượng (U còn được gọi là tập vũ trụ) và A là tập thuộc tính là một tập hữu hạn, khác rỗng các thuộc tính; V là tập giá trị, trong đó 𝑉 = ∪ 𝑎∈𝐴 𝑉𝑎với Va là tập giá trị của thuộc tính a  A, f là hàm thông tin f : U x A→V, trong đó a  A, u  U: f(u,a)  Va. 1.2.2. Quan hệ không phân biệt được Cho hệ thông tin S = (U,A,V,f) với mỗi tập con các thuộc tính P  A, tồn tại một quan hệ hai ngôi trên U, ký hiệu là IND(P), được xác định như sau: IND(P) = {(u,v)  U x U|u(a) = v(a), a  P) IND(P) được gọi là quan hệ không phân biệt được (Indiscernibility Relation). 1.2.3. Bảng quyết định Bảng quyết định là một hệ thông tin đặc biệt trong đó tập thuộc tính 𝐴 được chia thành hai tập khác rỗng rời nhau C và D (A= CD, CD = ) tương ứng được gọi là tập thuộc tính điều kiện C và tập thuộc tính quyết định D. Bảng quyết định được ký hiệu là: DS = (U,CD,V,f) hay đơn giản là DS = (U,CD). 1.2.4. Luật quyết định Định nghĩa 1.4 (Luật quyết định) Cho bảng quyết định DS = (U,CD), giả sử U/C = {C1,C2,,Cm} và U/D = {D1,D2,,Dn} là các phân hoạch được sinh bởi C, D. Với Ci  U/C, Dj  U/D một luật quyết định được biểu diễn dưới dạng: Ci → Dj , i=1..m, j=1..n. 4 1.3. Mô hình dữ liệu dạng khối 1.3.1. Khối Định nghĩa 1.8 Gọi R = (id;A1,A2,...,An) là một bộ hữu hạn các phần tử, trong đó id là tập chỉ số hữu hạn khác rỗng, Ai (i=1..n) là các thuộc tính. Mỗi thuộc tính Ai (i=1..n) có miền giá trị tương ứng là dom(Ai ). Một khối r trên tập R, kí hiệu r(R) gồm một số hữu hạn phần tử mà mỗi phần tử là một họ các ánh xạ từ tập chỉ số id đến các miền trị của các thuộc tính Ai, (i=1..n). Nói một cách khác: t  r(R)  t = {ti: id → dom(Ai)} i =1..n 1.3.2. Lát cắt Cho R = (id;A1,A2,...,An), r(R) là một khối trên R. Với mỗi x id ta kí hiệu r(Rx) là một khối với Rx = ({x};A1,A2,...,An) sao cho: tx  r(Rx )  tx = {t i x = t i }i =1..n với t  r và t = {t i : id → dom(Ai) }i =1..n ở đây t i x(x) = t i(x) với i=1..n. Khi đó r(Rx) được gọi là một lát cắt trên khối r(R) tại điểm x. Từ đây, để đơn giản chúng ta sử dụng kí hiệu: x(i)=(x;Ai); id(i) = {x(i)|x  id}. Ta gọi x(i) (x id, i = 1..n) là thuộc tính chỉ số của lược đồ khối R = (id;A1,A2,...,An ). 1.3.3. Đại số quan hệ trên khối Phép hợp Phép giao Phép trừ Tích Đề các Tích Đề các theo tập chỉ số Phép chiếu Phép chọn Phép kết nối Phép chia 1.4 . Kết luận chương 1 Chương một của luận án trình bày tổng quan về khai phá dữ x 5 liệu, các kỹ thuật khai phá dữ liệu, kiến thức về khai phá luật quyết định, lớp tương đương Phần cuối của chương trình bày một số khái niệm cơ bản của mô hình dữ liệu dạng khối: khối, lát cắt của khối tại một điểm, đại số quan hệ trên khối. Những kiến thức này sẽ là cơ sở cho các vấn đề được trình bày ở các chương tiếp theo của luận án. CHƯƠNG 2. KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN KHỐI DỮ LIỆU CÓ GIÁ TRỊ THUỘC TÍNH THAY ĐỔI 2.1 Một số khái niệm xây dựng trên khối 2.1.1 Khối thông tin Định nghĩa 2.1 Cho lược đồ khối R = (id;A1,A2,...,An), r là một khối trên R. Khi đó khối thông tin là một bộ bốn IB = (U,A,V,f) với U là tập các đối tượng thuộc r gọi là không gian các đối tượng, A = ⋃ 𝑖𝑑(𝑖)𝑛𝑖=1 là tập các thuộc tính chỉ số của đối tượng, V = ⋃ 𝑉𝑥(𝑖)𝑥(𝑖)∈𝐴 , 𝑉𝑥(𝑖) là tập giá trị của các đối tượng ứng với thuộc tính chỉ số x(i), f là hàm thông tin UxA→ V thỏa mãn: uU,  x(i)A ta có f(u, x(i)) 𝑉𝑥(𝑖) . 2.1.2 Quan hệ không phân biệt được Định nghĩa 2.3 Cho khối thông tin IB = (U,A,V,f). Khi đó với mỗi tập thuộc tính chỉ số P A ta xác định một quan hệ tương đương, kí hiệu IND(P) định nghĩa như sau: IND(P) = {(u,v) UxU |  x(i)P: f(u,x(i))=f(v,x(i))}, và gọi là quan hệ không phân biệt được. 2.1.3 Khối quyết định Định nghĩa 2.5 Cho khối thông tin IB = (U,A,V,f) với U là không gian 6 các đối tượng, A = . Khi đó nếu A được chia thành 2 tập C và D sao cho: C=⋃ 𝑥(𝑖)𝑘𝑖=1,𝑥∈𝑖𝑑 , D=⋃ 𝑥 (𝑖)𝑛 𝑖=𝑘+1,𝑥∈𝑖𝑑 , thì khối thông tin IB gọi là khối quyết định và kí hiệu là DB=(U,CD,V,f). 2.1.4 Luật quyết định trên khối và trên lát cắt Định nghĩa 2.7 Cho khối quyết định DB = (U,CD), với U là không gian các đối tượng: C = ⋃ 𝑥(𝑖)𝑘𝑖=1,𝑥∈𝑖𝑑 , D =⋃ 𝑥 (𝑖)𝑛 𝑖=𝑘+1,𝑥∈𝑖𝑑 , và Cx=⋃ 𝑥(𝑖)𝑘𝑖=1 , D x=⋃ 𝑥(𝑖)𝑛𝑖=𝑘+1 , xid. Khi đó: U/C={C1,C2,,Cm}, U/C x = {𝐶𝑥1, 𝐶𝑥2, . . . , 𝐶𝑥𝑡𝑥}, U/D={D1,D2,,Dk}, U/D x = tương ứng là các phân hoạch được sinh ra bởi C, Cx, D, Dx. Một luật quyết định trên khối có dạng: Ci → Dj, i=1..m, j=1..k, và trên lát cắt tại điểm x có dạng: Cxi → Dxj , i=1..tx, j=1..hx . Định nghĩa 2.8 Cho khối quyết định DB=(U,CD), CiU/C, DjU/D, 𝐶𝑥𝑝𝑥U/C x, 𝐷𝑥𝑞𝑥U/D x, i=1..m, j=1..n, p{1,2,,tx}, q{1,2,,hx}, xid. Khi đó, độ hỗ trợ, độ chính xác và độ phủ của luật quyết định Ci→ Dj trên khối là: - Độ hỗ trợ: Sup(Ci,Dj) = |CiDj)|, - Độ chính xác: Acc(Ci,Dj) = |𝐶𝑖∩𝐷𝑗| |𝐶𝑖| , - Độ phủ: Cov(Ci,Dj) = |𝐶𝑖∩𝐷𝑗| |𝐷𝑗| . Định nghĩa 2.9 Cho khối quyết định DB=(U,CD), CiU/C, DjU/D ( ) 1 n i i id = {𝐷𝑥1, 𝐷𝑥2, . . . , 𝐷𝑥𝑡𝑥} 7 tương ứng là các lớp tương đương điều kiện và các lớp tương đương quyết định được sinh bởi C, D, Ci→ Dj là một luật quyết định trên khối DB, i=1..m, j=1..n. - Nếu Acc(Ci→ Dj) = 1 thì Ci→ Dj gọi là một luật quyết định chắc chắn. - Nếu 0 < Acc(Ci→ Dj) < 1 thì Ci→ Dj gọi là một luật quyết định không chắc chắn. Định nghĩa 2.10 Cho khối quyết định DB=(U,CD), CiU/C, DjU/D, i=1..m, j=1..n tương ứng là các lớp tương đương điều kiện và các lớp tương đương quyết định được sinh bởi C, D; ,  là hai ngưỡng cho trước (, (0,1)). Khi đó, nếu Acc (Ci,Dj)   và Cov (Ci,Dj)   thì ta gọi Ci→ Dj là luật quyết định có ý nghĩa. 2.2 Thuật toán khai phá luật quyết định trên khối và trên lát cắt (MDLB). Thuật toán MDLB gồm các bước sau: - Bước 1: Phân các lớp tương đương điều kiện, quyết định trên khối (trên lát cắt). - Bước 2: Tính ma trận độ hỗ trợ trên khối (trên lát cắt) - Bước 3: Tính ma trận độ chính xác, ma trận độ phủ - Bước 4: Tìm luật quyết định trên khối. 2.3. Khai phá luật quyết định trên khối có giá trị thuộc tính thay đổi Định nghĩa 2.11(Định nghĩa làm mịn giá trị thuộc tính chỉ số trên khối) Cho khối quyết định DB= (U,CD,V,f), với U là không gian các đối tượng, a CD, Va là tập các giá trị hiện có của thuộc tính chỉ số a. Giả sử Z={xsU | f(xs,a) = z} là tập các đối 8 tượng có giá trị z trên thuộc tính chỉ số a. Nếu Z được phân hoạch thành hai tập W và Y sao cho: Z=WY, WY= với W={xpU| f(xp,a) = w, wVa}, Y={xqU| f(xq,a) = y, yVa}, thì ta nói giá trị z của thuộc tính chỉ số a được làm mịn thành hai giá trị mới w và y. Định nghĩa 2.12(Định nghĩa làm thô giá trị thuộc tính chỉ số trên khối) Cho khối quyết định DB=(U,CD,V,f), với U là không gian các đối tượng, a CD, Va là tập các giá trị hiện có của thuộc tính chỉ số a. Giả sử f(xp,a)=w, f(xq,a)=y tương ứng là giá trị của xp, xq trên thuộc tính chỉ số a (pq). Nếu tại thời điểm nào đó ta có: f(xp,a)= f(xq,a)=z, (zVa) thì ta nói hai giá trị w, y của a được làm thô thành giá trị mới z. Định lý 2.1 Cho khối quyết định DB = (U,CD,V,f ), với U là không gian các đối tượng, a  CD, Va là tập các giá trị hiện có của thuộc tính chỉ số a. Khi đó, hai lớp tương đương Ep, Eq nào đó (Ep, EqU/E, E{C,D}) được làm thô thành lớp tương đương mới Es khi và chỉ khi aj  a: f(Ep,aj) = f(Eq,aj). Định lý 2.2 Cho khối quyết định DB = (U,CD,V,f ), với U là không gian các đối tượng, a CD, Va là tập các giá trị hiện có của thuộc tính chỉ số a. Khi đó, lớp tương đương Es (EsU/E, E{C,D}) được làm mịn thành hai lớp tương đương mới Ep, Eq nào đó khi và chỉ khi ta có thể đặt: f(Ep,a)=w, f(Eq,a)=y và Ep Eq=Es, w, yVa, w y. Định lý 2.3 Cho khối quyết định DB = (U, CD). ,  là hai ngưỡng cho trước (, (0,1)). Khi đó nếu Ci → Dj là một luật quyết định 9 có ý nghĩa trên khối quyết định thì nó cũng là một luật quyết định có ý nghĩa trên một lát cắt bất kì của khối quyết định tại xid. 2.3.1 Làm mịn, thô các lớp tương đương điều kiện trên khối quyết định và trên lát cắt. Mệnh đề 2.3 Cho khối quyết định DB = (U, CD, V, f ), a=x(i) C, Va là tập các giá trị hiện có của thuộc tính chỉ số điều kiện a, giá trị z của a được làm mịn thành hai giá trị mới w và y. Khi đó, nếu lớp tương đương điều kiện Cs U/C, (f(Cs,a)=z ) được làm mịn thành hai lớp tương đương điều kiện mới Cp,Cq (f(Cp,a)=w, f(Cq,a)=y, với w,yVa ) nào đó thì trên lát cắt rx, tồn tại lớp tương đương Cxi thỏa mãn: Cs  Cxi , cũng được làm mịn thành hai lớp tương đương điều kiện mới Cxi’ và Cxi’’ sao cho: Cp Cxi’, Cq Cxi’’ (f(Cxi’,a)=w, f(Cxi’’,a)=y). Mệnh đề 2.5 Cho khối quyết định DB = (U,CD,V,f), a=x(i) C, Va là tập các giá trị hiện có của thuộc tính chỉ số điều kiện a, các giá trị w và y của a được làm thô thành giá trị mới z. Khi đó, nếu hai lớp tương đương điều kiện Cp,CqU/C, (f(Cp,a)=w, f(Cq,a)=y) nào đó được làm thô thành lớp tương đương điều kiện mới Cs U/C (f(Cs,a)=z) thì trên lát cắt rx tồn tại hai lớp tương đương điều kiện Cxi, Cxj thỏa mãn: Cp Cxi, Cq Cxj, cũng được làm thô thành lớp tương đương điều kiện mới Cxk sao cho: Cs  Cxk. 2.3.2 Làm mịn, thô các lớp tương đương quyết định trên khối và trên lát cắt Mệnh đề 2.7 10 Cho khối quyết định DB = (U,CD,V,f), a=x(i) D, Va là tập các giá trị hiện có của thuộc tính chỉ số quyết định a, giá trị z của a được làm mịn thành hai giá trị mới w và y. Khi đó, nếu lớp tương đương quyết định Ds U/D (f(Ds,a)=z) được làm mịn thành hai lớp tương đương quyết định mới Dp,Dq (f(Dp,a)=w, f(Dq,a)=y, với w,yVa) nào đó thì trên lát cắt rx, tồn tại lớp tương đương Dxi thỏa mãn: Ds  Dxi , cũng được làm mịn thành hai lớp tương đương quyết định mới Dxi’ và Dxi’’ sao cho: Dp Dxi’, Dq Dxi’’ (f(Dxi’,a)=w, f(Dxi’’,a)=y). Mệnh đề 2.9 Cho khối quyết định DB = (U,CD,V,f), a=x(i) D, Va là tập các giá trị hiện có của thuộc tính chỉ số quyết định a, các giá trị w và y của a được làm thô thành giá trị mới z. Khi đó, nếu hai lớp tương đương quyết định Dp,Dq, (f(Dp,a)=w, f(Dq,a)=y) nào đó được làm thô thành lớp tương đương quyết định mới Ds U/D (f(Ds,a)=z) thì trên lát cắt rx tồn tại hai lớp tương đương quyết định Dxi, Dxj thỏa mãn: Dp Dxi, Dq Dxj, cũng được làm thô thành lớp tương đương quyết định mới Dxk sao cho: Ds  Dxk. 2.3.4 Thuật toán khai phá luật quyết định trên khối có giá trị thuộc tính chỉ số thay đổi (MDLB_VAC). Thuật toán MDLB_VAC gồm các bước sau: Bước 1: Tính ma trận độ hỗ trợ Sup(C,D) của khối ban đầu. Bước 2: Tính gia tăng ma trận độ hỗ trợ trên khối Sup(C’,D’) sau khi làm thô/mịn giá trị thuộc tính chỉ số. 11 Bước 3: Tính ma trận độ chính xác Acc(C’,D’), ma trận độ phủ Cov(C’,D’) sau khi làm thô/mịn giá trị thuộc tính chỉ số từ ma trận Sup(C’,D’) Bước 4: Sinh luật quyết định trên khối. 2.4 Độ phức tạp của các thuật toán tính ma trận Sup trên khối và lát cắt. Mệnh đề 2.13: Thuật toán tính ma trận độ hỗ trợ cho khối quyết định và cho lát cắt tại điểm xid cùng có độ phức tạp là O(|U|2). Mệnh đề 2.14: Thuật toán tính ma trận độ hỗ trợ cho khối quyết định và cho lát cắt tại điểm xid sau khi làm thô các giá trị của thuộc tính chỉ số điều kiện cùng có độ phức tạp là O(|U|2). Mệnh đề 2.15: Thuật toán tính ma trận độ hỗ trợ cho khối quyết định và cho lát cắt tại điểm xid sau khi làm mịn giá trị của thuộc tính chỉ số điều kiện cùng có độ phức tạp là O(|U|2). 2.6 Kết luận Chương này trình bày những kết quả đầu tiên của luận án: Xây dựng một số khái niệm cơ bản về khai phá luật trên khối. Trên cơ sở đó một số tính chất, mệnh đề, định lí liên quan đã được phát biểu và chứng minh. - Xây dựng thuật toán MDLB tìm luật quyết định trên khối và trên lát cắt. - Đề xuất và chứng minh một số kết quả về mối quan hệ giữa việc làm thô, làm mịn các giá trị của thuộc tính điều kiện hoặc quyết định trên khối và lát cắt. Đồng thời, đề xuất thuật toán MDLB_VAC tính các ma trận độ hỗ trợ trên khối và trên lát cắt, tìm ra các luật quyết định có ý nghĩa khi giá trị thuộc tính chỉ số thay đổi. 12 CHƯƠNG 3. KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN KHỐI CÓ TẬP ĐỐI TƯỢNG THAY ĐỔI 3.1 Mô hình bổ sung và loại bỏ các đối tượng trên khối và trên lát cắt. Mệnh đề 3.1: Cho khối quyết định DB = (U,CD,V,f), AN và DM là tập các đối tượng bổ sung và loại bỏ tương ứng đối với khối quyết định DB. Khi đó ta có: Acc(C’,D’)=Acc(C’i,D’j)ij với: i =1..m+p, j = 1..h+q và 𝐴𝑐𝑐(𝐶′𝑖 , 𝐷′𝑗) = { |𝐶𝑖 ∩ 𝐷𝑗| + 𝑁ij −𝑀ij |𝐶𝑖| + ∑ 𝑁ij' − ∑ 𝑀ij' ℎ 𝑗′=1 ℎ+𝑞 𝑗′=1 , 𝑖 = 1. .𝑚, 𝑗 = 1. . ℎ, 𝑁ij |𝐶𝑖| + ∑ 𝑁ij' −∑ 𝑀ij' ℎ 𝑗′=1 ℎ+𝑞 𝑗′=1 , 𝑖 = 1. .𝑚, 𝑗 = ℎ + 1. . ℎ+ 𝑞 𝑁ij ∑ 𝑁ij ℎ+𝑞 𝑗=1 ,  𝑖 = 𝑚 + 1. .𝑚 + 𝑝, 𝑗 = 1. .  ℎ+ 𝑞 Mệnh đề 3.3 Cho khối quyết định DB = (U,CD,V,f), AN và DM là tập các đối tượng bổ sung và loại bỏ tương ứng đối với khối quyết định DB. Khi đó ta có: Cov(C’,D’) = Cov(C’i,D’j)ij (m+p)x(h+q), với i =1..m+p, j=1..h+q và 𝐶𝑜𝑣(𝐶′𝑖 , 𝐷′𝑗) = { |𝐶𝑖 ∩ 𝐷𝑗| + 𝑁𝑖𝑗 −𝑀𝑖𝑗 |𝐷𝑗| + ∑ 𝑁𝑖′𝑗 − ∑ 𝑀𝑖′𝑗 𝑚 𝑖′=1 𝑚+𝑝 𝑖′=1 , 𝑖 = 1. .𝑚, 𝑗 = 1. . ℎ 𝑁𝑖𝑗 |𝐷𝑗| + ∑ 𝑁𝑖′𝑗 − ∑ 𝑀𝑖′𝑗 𝑚 𝑖′=1 𝑚+𝑝 𝑖′=1 , 𝑖 = 𝑚 + 1. .𝑚 + 𝑝, 𝑗 = 1. . ℎ 𝑁𝑖𝑗 ∑ 𝑁𝑖′𝑗 𝑚+𝑝 𝑖′=1 , 𝑖 = 1. .𝑚 + 𝑝, 𝑗 = ℎ + 1. . ℎ+ 𝑞 3.2 Tính toán gia tăng Acc và Cov khi bổ sung và loại bỏ các đối tượng trên khối quyết định. 3.2.1 Bổ sung đối tượng x vào khối quyết định 13 Trường hợp 1: Sinh lớp điều kiện mới và lớp quyết định mới. Acc(C’m+1,D’h+1) = 1 và Cov(C’m+1,D’h+1) = 1, j=1..h: Acc(C’m+1,D’j) = Cov(C’m+1,D’j) = 0, i=1..m: Acc(C’i,D’h+1) = Cov(C’i,D’h+1) = 0. Mặt khác, i=1..m, j=1..h: Acc(C’i,D’j) = Acc(Ci,Dj) , và Cov(C’i,D’j) = Cov(Ci,Dj) . Trường hợp 2: Chỉ sinh lớp điều kiện mới. Acc(C’m+1,D’j*) = 1 và Cov(C’m+1,D’j*) = 1 |𝐷𝑗∗|+1 . Nếu k j* thì: Acc(C’m+1,D’k) = Cov(C’m+1,D’k) = 0. Nếu i  m+1 thì: Acc(C’i,D’j*) = Acc(Ci,Dj*), Cov(C’i,D’j*) = |𝐶𝑖∩𝐷𝑗∗| |𝐷𝑗∗|+1 . Mặt khác, i  m+1, j  j*: Acc(C’i,D’j) = Acc(Ci,Dj) và Cov(C’i,D’j) = Cov(Ci,Dj). Trường hợp 3: Chỉ sinh lớp quyết định mới. Acc(C’i*,D’h+1) = 1 |𝐶𝑗∗|+1 và Cov(C’i*,D’h+1) = 1. Nếu i  i* thì: Acc(C’i,D’h+1) = Cov(C’i,D’h+1) = 0. Nếu k  h+1 thì: Acc(C’i*,D’k) = |𝐶𝑖∩𝐷𝑘| |𝐶𝑖∗|+1 , Cov(C’i*,D’k) = Cov(Ci*,Dk). Mặt khác, i  i*, j  h+1: Acc(C’i,D’j) = Acc(Ci,Dj) và Cov(C’i,D’j) = Cov(Ci,Dj). Trường hợp 4: Không sinh thêm lớp điều kiện mới hoặc lớp quyết định mới. Acc(C’i*,D’j*) = |𝐶𝑖∗∩𝐷𝑗∗|+1 |𝐶𝑖∗|+1 và Cov(C’i*,D’j*) = |𝐶𝑖∗∩𝐷𝑗∗|+1 |𝐷𝑗∗|+1 14 - Nếu k  j* thì: Acc(C’i*,D’k)= |𝐶𝑖∗∩𝐷𝑘|+1 |𝐶𝑖∗|+1 ; Cov(C’i*,D’k)= Cov(Ci*,Dk). - Nếu u  i* thì: Acc(C’u,D’j*) = Acc(Cu,Dj*) và Cov(C’u,D’j*) = |𝐶𝑢∩𝐷𝑗∗| |𝐷𝑗∗|+1 - Nếu i  i* và j  j* thì: Acc(C’i,D’j) = Acc(Ci,Dj) và Cov(C’i,D’j) = Cov(Ci,Dj). 3.2.2 Loại bỏ phần tử x ra khỏi khối quyết định Acc(C’i*,D’j*) = |𝐶𝑖∗∩𝐷𝑗∗|−1 |𝐷𝑖∗|−1 và Cov(C’i*,D’j*) = |𝐶𝑖∗∩𝐷𝑗∗|−1 |𝐶𝑖∗|−1 . - Nếu k  j* thì: Acc(C’i*,D’k) = |𝐶𝑖∗∩𝐷𝑘| |𝐶𝑖∗|−1 và Cov(C’i*,D’k) = Cov(Ci*,Dk) . - Nếu u  i* thì: Acc(C’u,D’j*) = Acc(Cu,Dj*) và Cov(C’u,D’j*) = |𝐶𝑢∩𝐷𝑗∗| |𝐷𝑗∗|−1 . - Nếu i  i* và j  j* thì: Acc(C’i,D’j) = Acc(Ci,Dj) và Cov(C’i,D’j) = Cov(Ci,Dj). 3.3 Thuật toán sinh luật quyết định bằng phương pháp tính gia tăng ma trận Acc và Cov sau khi bổ sung, loại bỏ các phần tử (MDLB_OSC1) Bước 1: Tính ma trận độ chính xác Acc(C,D) và độ phủ Cov(C,D) của khối trước khi bổ sung, loại bỏ đối tượng. Bước 2: Tính gia tăng ma trận độ chính xác Acc(C’,D’) và độ phủ Cov(C’,D’) sau khi bổ sung, loại bỏ đối tượng. Bước 3: Loại bỏ dòng/cột trong các ma trận Acc(C’,D’) và Cov(C’,D’) mà có toàn giá trị 0. Bước 4: Sinh luật quyết định trên khối. 3.4 Độ phức tạp của các thuật toán MDLB_OSC1 15 Mệnh đề 3.5: Độ phức tạp thuật toán xác định Acc và Cov là O(|U|2 ). Mệnh đề 3.6: Độ phức tạp thuật toán tính gia tăng Acc và Cov khi bổ sung N đối tượng là O(N|U|2). Mệnh đề 3.7: Độ phức tạp thuật toán tính gia tăng Acc và Cov khi loại bỏ M đối tượng là O(M|U|2). Mệnh đề 3.8: Độ phức tạp thuật toán xóa dòng/cột của ma trận Acc và Cov có toàn giá trị 0 là O(|U|2). 3.5 Tính toán gia tăng Sup khi bổ sung và loại bỏ các đối tượng trên khối quyết định và lát cắt. Khi bổ sung N đối tượng và loại bỏ M đối tượng ta có: Sup(C’i,D’j) = Sup(Ci,Dj) + Nij – Mij, i=1..m+p, j=1..h+q ở đó Mij = 0 và Sup(Ci,Dj)=0, i=m+1..m+p, j=h+1..h+q 3.6 Thuật toán sinh luật quyết định bằng phương pháp tính gia tăng ma trận Sup sau khi bổ sung và loại bỏ các đối tượng (MDLB_OSC2). Bước 1: Tính ma trận độ hỗ trợ Sup(C,D) trước khi khối được bổ sung, loại bỏ đối tượng. Bước 2: Tính gia tăng ma trận độ hỗ trợ Sup(C’,D’) sau khi bổ sung, loại bỏ đối tượng. Bước 3: Loại bỏ dòng/cột trong ma trận Sup(C’,D’) mà có toàn giá trị 0. Bước 4: Tính các ma trận Acc(C’,D’) và Cov(C’,D’) thông qua các giá trị của ma trận Sup(C’,D’) Bước 5: Sinh luật quyết định trên khối. 3.7 Độ phức tạp của các thuật toán MDLB_OSC2 Mệnh đề 3.9: Độ phức tạp thời gian của thuật toán tính gia tăng ma trận Sup khi bổ sung N đối tượng là O(N|U|). 16 Mệnh đề 3.10: Độ phức tạp thời gian của thuật toán tính gia tăng ma trận Sup khi loại bỏ M đối tượng là O(M|U|). Mệnh đề 3.11: Độ phức tạp thời gian của thuật toán tính gia tăng ma trận Sup để trích rút các luật quyết định có ý nghĩa khi bổ sung, loại bỏ các đối tượng là O(|U|2). Mệnh đề 3.12: Độ phức tạp thời gian của thuật toán tính gia tăng ma trận Sup khi bổ sung N đối tượng xét trên lát cắt của khối tại điểm xid là O(N|U|). Mệnh đề 3.13: Độ phức tạp thời gian của thuật toán tính gia tăng ma trận Sup khi loại bỏ M đối tượng xét trên lát cắt của khối tại điểm xid là O(M|U|). 3.10 Thực nghiệm 3.10.1 Mục tiêu thực nghiệm (1) Đánh giá tính thực thi của các thuật toán tìm luật kết hợp trên khối và thuật toán gia tăng tìm luật trên khối trong trường hợp khối có giá trị thuộc tính thay đổi. (2) Đánh giá tính thực thi và hiệu quả thời gian thực hiện của thuật toán tính gia tăng ma trận độ chính xác, ma trận độ phủ so với thuật toán tính gia tăng ma trận độ hỗ trợ để tìm ra luật quyết định trên khối khi tập đối tượng thay đổi. 3.10.2 Dữ liệu thử nghiệm Việc thử nghiệm được thực hiện trên 3 tập dữ liệu lấy từ khoa Nhi A, B của Bệnh viện Bạch Mai cơ sở 2 từ ngày 10/03/2020 đến ngày 14/03/2020. Dữ liệu được thu thập và đã qua quá trình tiền xử lí với mỗi bộ dữ liệu đều gồm 3 thuộc tính chỉ số điều kiện là các triệu chứng bệnh gồm sốt, ho, sổ mũi và 2 17 thuộc tính chỉ số quyết định là phác đồ điều trị và mức độ sốt vi rút theo dõi qua 4 ngày. Số phần tử của các bộ dữ liệu là: Tên CSDL BVBM2KNA BVBM2KNB KID PATIENT FEVER VIRUS Số đối tượng 160 1360 939 Bảng 3.2: Các thông tin cơ bản về cơ sở dữ liệu thực nghiệm 3.10.3 Công cụ và môi trường thử nghiệm Công cụ thực hiện lập trình các thuật toán là ngôn ngữ Java. Môi trường thử nghiệm là máy tính PC với cấu hình Intel(R) Core™ i5 2.5Ghz, RAM 4G, Windows 7 OS. 3.10.4. Kết quả thực nghiệm Sau khi chạy 3 thuật toán trên các bộ dữ liệu ta thu được các kết quả như sau: - Với bài toán 1: tìm luật quyết định trên khối và lát cắt của khối: Hình 3.5: Luật quyết định tìm được trên khối 18 Khi thay đổi min_acc và min_cov thì số lượng luật thu được cũng thay đổi: - Với bài toán 2: tìm luật quyết định trên khối và lát cắt của khối khi làm mịn, làm thô giá trị thuộc tính Hình 3.8: Tính các ma trận Sup, Acc, Cov trước và sau khi làm mịn 19 Hình 3.11: Luật quyết định tìm được sau khi làm mịn, thô giá trị thuộc tính - Với bài toán 3: tìm luật quyết định trên khối và lát cắt của khối khi bổ sung, loại bỏ phần tử + Kết quả của chương trình tính theo phương pháp 1(tính gia tăng ma trận Acc, Cov): 20 + Kết quả của chương trình tính theo phương pháp 2 (tính gia tăng ma trận Sup): Ta thấy 2 phương pháp này cho cùng một kết quả tập luật với cùng một tập nguồn, chỉ khác nhau về thời gian thực hiện: 3.11 Kết luận Từ mô hình bổ sung và loại bỏ đối tượng trên khối quyết định và trên lát cắt được đề xuất, một số tính chất của các ma trận 21 Acc và Cov đã được chứng minh. Trên cơ sở đó, hai thuật toán tìm các luật quyết định trên khối và trên lát cắt đã được đưa ra: - Thuật toán MDLB_OSC1 tính gia tăng ma trận Acc, Cov để tìm ra các luật quyết định có ý nghĩa trên khối và trên lát cắt. - Thuật toán MDLB_OSC2 tính gia tăng ma trận độ hỗ trợ Sup để tìm ra các luật quyết định có ý nghĩa. Cuối chương là phần so sánh hai thuật toán đề xuất và cài đặt thực nghiệm. KẾT LUẬN 1) Những kết quả chính của luận án Luận án tập trung nghiên cứu bài toán khai phá luật quyết định trên khối trong một số trường hợp với các kết quả chính như sau: - Xây dựng mô hình khai phá luật quyết định trên khối với các khái niệm, định lí, tính chất đã được chứng minh. - Đề xuất 03 thuật toán tìm luật quyết định trên khối trong các trường hợp: dữ liệu khối cố định; giá trị thuộc tính chỉ số thay đổi; và trong trường hợp tập đối tượng thay đổi. 2) Hướng phát triển của luận án - Tiếp tục nghiên cứu vấn đề khai phá luật quyết định trên khối có các thuộc tính thay đổi, dữ liệu không đầy đủ - Khai phá các luật quyết định có ý nghĩa trên chuỗi khối quyết định được liên kết với nhau (tương đồng với công nghệ blockchain). NHỮNG ĐÓNG GÓP MỚI CỦA LUẬN ÁN 22 Luận án có các đóng góp mới như sau: - Xây dựng mô hình khai phá luật quyết định trên khối với các khái niệm, định lí, mệnh đề đã được chứng minh. - Đề xuất ba thuật toán tìm luật quyết định trên khối trong các trường hợp: dữ liệu khối cố định; giá trị thuộc tính chỉ số thay đổi; và trong trường hợp tập đối tượng thay đổi. DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CT1. Trịnh Đình Thắng, Trần Minh Tuyến, Đỗ Thị Lan Anh, “Khai phá luật quyết định trên khối dữ liệu có giá trị thuộc tính thay đổi”, Kỷ yếu Hội thảo Quốc gia lần thứ XIX: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Hà Nội, 01- 02/10/2016, Tr 163 – 169. CT2. Trịnh Đình Thắng, Trần Minh Tuyến, Đỗ Thị Lan Anh, Nguyễn Thị Quyên, “Một số kết quả về khai phá luật quyết định trên khối dữ liệu có giá trị thuộc tính thay đổi”, Kỷ yếu Hội nghị Kh