Tóm tắt luận án Tiến sĩ Máy tính: Khai phá luật quyết định trên mô hình dữ liệu dạng khối

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

18
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt luận án Tiến sĩ Máy tính: Khai phá luật quyết định trên mô hình dữ liệu dạng khối

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Đỗ Thị Lan Anh KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN MÔ HÌNH DỮ LIỆU DẠNG KHỐI Chuyên ngành: Khoa học máy tính Mã số: 9 48 01 01 TÓM TẮT LUẬN ÁN TIẾN SĨ MÁY TÍNH Hà Nội – Năm 2020
Công trình được hoàn thành tại: Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Người hướng dẫn khoa học: PGS. TS. Trịnh Đình Thắng Phản biện 1: PGS. TS. Nguyễn Hữu Quỳnh Phản biện 2: PGS. TS. Đỗ Năng Toàn Phản biện 3: PGS. TS. Phạm Văn Cường Luận án sẽ được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Học viện, họp tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi … giờ .., ngày … tháng … năm 201…. Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam
1 MỞ ĐẦU 1. Tính cấp thiết của luận án Khai phá các luật quyết định là quá trình xác định những luật quyết định trên bảng quyết định cho trước, phục vụ cho bài toán phân lớp đối tượng. Đây là một trong những kĩ thuật khai phá dữ liệu khá phổ biến và đã được nhiều chuyên gia trong và ngoài nước nghiên cứu trên cả mô hình quan hệ và các mô hình mở rộng của mô hình quan hệ. Các nghiên cứu trên thế giới và trong 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 = {tix = ti }i =1..n với t  r và t = {ti : id → x dom(Ai) }i =1..n ở đây tix(x) = ti(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ữ
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,n A = id (i ) . Khi đó nếu A được chia thành 2 tập C và D i =1 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 𝑥 (𝑖) , Dx=⋃𝑛𝑖=𝑘+1 𝑥 (𝑖) , xid. Khi đó: U/C={C1,C2,…,Cm}, U/Cx = {𝐶𝑥1 , 𝐶𝑥2 , . . . , 𝐶𝑥𝑡𝑥 }, U/D={D1,D2,…,Dk}, U/Dx = {𝐷𝑥1 , 𝐷𝑥2 , . . . , 𝐷𝑥𝑡𝑥 } 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/Cx, 𝐷𝑥𝑞𝑥 U/Dx, 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
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 ℎ+𝑞 , 𝑖 = 1. . 𝑚, 𝑗 = 1. . ℎ, |𝐶𝑖 | + ∑𝑗′=1 𝑁ij' − ∑ℎ𝑗′=1 𝑀ij' 𝑁ij 𝐴𝑐𝑐(𝐶′𝑖 , 𝐷′𝑗 ) = ℎ+𝑞 , 𝑖 = 1. . 𝑚, 𝑗 = ℎ + 1. . ℎ + 𝑞 |𝐶𝑖 | + ∑𝑗′=1 𝑁ij' − ∑ℎ𝑗′=1 𝑀ij' 𝑁ij ℎ+𝑞 , 𝑖 = 𝑚 + 1. . 𝑚 + 𝑝, 𝑗 = 1. . ℎ + 𝑞 { ∑𝑗=1 𝑁ij 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. 1 Acc(C’m+1,D’j*) = 1 và Cov(C’m+1,D’j*) = . |𝐷𝑗∗ |+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. 1 Acc(C’i*,D’h+1) = và Cov(C’i*,D’h+1) = 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) = , Cov(C’i*,D’k) = |𝐶𝑖∗ |+1 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. |𝐶𝑖∗ ∩𝐷𝑗∗ |+1 |𝐶𝑖∗ ∩𝐷𝑗∗ |+1 Acc(C’i*,D’j*) = và Cov(C’i*,D’j*) = |𝐶𝑖∗ |+1 |𝐷𝑗∗ |+1
14 |𝐶𝑖∗ ∩𝐷𝑘 |+1 - Nếu k  j* thì: Acc(C’i*,D’k)= ; Cov(C’i*,D’k)= |𝐶𝑖∗ |+1 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 |𝐶𝑖∗ ∩𝐷𝑗∗ |−1 |𝐶𝑖∗ ∩𝐷𝑗∗ |−1 Acc(C’i*,D’j*) = và Cov(C’i*,D’j*) = . |𝐷𝑖∗ |−1 |𝐶𝑖∗ |−1 |𝐶𝑖∗ ∩𝐷𝑘 | - Nếu k  j* thì: Acc(C’i*,D’k) = và Cov(C’i*,D’k) = |𝐶𝑖∗ |−1 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