ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ THU HƢƠNG

MỘT SỐ THUẬT TOÁN KHAI PHÁ LUẬT QUYẾT ĐỊNH
TRÊN CƠ SỞ DỮ LIỆU ĐỘNG

LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN

Hà Nội - 2014


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ THU HƢƠNG

MỘT SỐ THUẬT TOÁN KHAI PHÁ LUẬT QUYẾT ĐỊNH
TRÊN CƠ SỞ DỮ LIỆU ĐỘNG

Ngành: Công Nghệ Thông Tin
Chuyên ngành: Kỹ Thuật Phần Mềm
Mã số: 60480103

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC: GS. TS. VŨ ĐỨC THI

Hà Nội - 2014



MỤC LỤC
LỜI CẢM ƠN ..................................................................................................................1
LỜI CAM ĐOAN ............................................................................................................2
MỤC LỤC .......................................................................................................................3
DANH MỤC CÁC KÝ HIỆU .........................................................................................5
DANH MỤC CÁC BẢNG ..............................................................................................6
DANH MỤC CÁC HÌNH ...............................................................................................7
MỞ ĐẦU .........................................................................................................................8
CHƢƠNG 1. CÁC KHÁI NIỆM CƠ BẢN ..............................................................10
1.1. Khai phá dữ liệu là gì .....................................................................................10
1.2. Các khái niệm cơ bản của tập thô ..................................................................12
1.2.1. Tập hợp ....................................................................................................12
1.2.2. Hệ thống thông tin ..................................................................................13
1.2.3. Quan hệ bất khả phân ..............................................................................14
1.2.4. Tập xấp xỉ trên và xấp xỉ dƣới .................................................................15
1.2.5. Bảng quyết định .......................................................................................17
1.2.6. Luật quyết định ........................................................................................18
1.3. Khai phá luật quyết định dựa trên tập thô ......................................................20
1.4. Kết luận chƣơng 1 ..........................................................................................20
CHƢƠNG 2. THUẬT TOÁN TIẾP CẬN GIA TĂNG ĐỂ KHAI PHÁ LUẬT
QUYẾT ĐỊNH TRÊN CƠ SỞ DỮ LIỆU CÓ GIÁ TRỊ THUỘC TÍNH THAY ĐỔI
...................................................................................................................................21
2.1. Định nghĩa về việc thay đổi giá trị thuộc tính ...............................................21
2.2. Mô hình tiếp cận gia tăng và thuật toán .........................................................22
2.2.1. Mô hình bài toán và kiến thức cơ sở tiếp cận thuật toán khi giá trị thuộc
tính thay đổi .......................................................................................................22
2.2.2. Thuật toán tiếp cận gia tăng khi làm thô, làm mịn các giá trị thuộc tính 27
2.2.3. Đánh giá độ phức tạp theo thời gian của thuật toán ................................ 32
2.2.4. Ví dụ minh họa ........................................................................................34

U
𝐴
𝐶
𝐷
𝐵⊂𝐴
IND(B)
[𝑥]𝐼𝑁𝐷(𝐵)
𝐵𝑋
𝐵𝑋
𝐵𝑁𝑋
𝐶𝑖
𝐷𝑗

Ý nghĩa
Tập các đối tƣợng
Tập các thuộc tính
Tập thuộc tính điều kiện
Tập thuộc tính quyết định
B là tập thuộc tính con của A
Quan hệ bất khả phân trên U theo B
Các lớp tƣơng của 𝑥 trong mối quan hệ
IND(B)
Tập xấp xỉ dƣới của X theo B
Tập xấp xỉ dƣới của X theo B
Tập biên của X trên U theo B
Phân lớp điều kiện thứ i
Phân lớp tƣơng đƣơng quyết định thứ j

𝑆𝑢𝑝𝑝(𝐶𝑖 , 𝐷𝑗 )


Bảng 1.1: Ví dụ về một bảng thông tin .........................................................................14
Bảng 1.2: Nhóm các đối tƣợng có bộ giá trị giống nhau ..............................................15
Bảng 1.3: Ví dụ về một bảng quyết định .......................................................................17
Bảng 1.4: Bảng tính độ phủ, độ chính xác ....................................................................19
Bảng 2.1: Bảng quyết định cho ví dụ minh họa ............................................................34
Bảng 2.2: Bảng trích rút các luật quan tâm ...................................................................36
Bảng 3.1: Bảng phân loại thu nhập đầu ngƣời trƣởng thành ở cụm dân cƣ ..................47
Bảng 3.2: Kết quả độ chính xác và độ phủ thời điểm t+1- Thuật toán của Liu ............51
Bảng 3.3: Kết quả tính độ chính xác, độ phủ các luật bằng thuật toán gia tăng ma trận
độ hỗ trợ .........................................................................................................................61


7

DANH MỤC CÁC HÌNH
Hình 1.1: Quá trình khái phá tri thức trong cơ sở dữ liệu .............................................10
Hình 1.2: Mô hình thể hiện tập xấp xỉ trên và xấp xỉ dƣới của X .................................16
Hình 3.1: Tiến trình thêm/ bớt đối tƣợng khỏi hệ thống ...............................................38
Hình 3.2: Màn hình nhập dữ liệu ...................................................................................65
Hình 3.3: Màn hình chọn cơ sở dữ liệu .........................................................................65
Hình 3.4: Màn hình hiển thị dữ liệu của cơ sở dữ liệu ..................................................66
Hình 3.5: Màn hình bổ sung/loại bỏ đối tƣợng .............................................................66
Hình 3.6: Màn hình hiển thị kết quả ..............................................................................67


8

MỞ ĐẦU
Trong những năm gần đây, công nghệ thông tin phát triển mạnh mẽ và đi sâu vào
nhiều lĩnh vực trong cuộc sống. Công nghệ thông tin phát triển đi kèm với sự gia tăng

của dữ liệu khi đƣợc làm thô, làm mịn, thuật toán và đánh giá độ phức tap tính toán
theo thời gian của thuật toán. Chƣơng 3: Trình bày hai thuật toán khai phá luật quyết
định trên bảng dữ liệu động khi có tập đối thƣợng thay đổi. Hai thuật toán này đều
đƣợc xây dựng trên cùng một mô hình chỉ khác nhau về hƣớng tiếp cận. Thuật toán


9
một là thuật toán khai phá luật quyết định theo hƣớng tiếp cận gia tăng ma trận độ
chính xác và ma trận độ phủ. Thuật toán hai là thuật toán khai phá luật quyết định theo
hƣớng tiếp cận gia tăng ma trận độ hỗ trợ. Kết thúc là phần kết luận và đề xuất những
vấn đề cần tiếp tục nghiên cứu.


10

CHƢƠNG 1. CÁC KHÁI NIỆM CƠ BẢN
1.1. Khai phá dữ liệu là gì
Khai phá dữ liệu đã thu hút rất nhiều sự chú ý trong ngành công nghệ thông tin
và trong xã hội nói chung trong những năm gần đây. Do sự sẵn và rộng của lƣợng lớn
dữ liệu và sự cần thiết để chuyển đổi dữ liệu đó thành thông tin hữu ích. Nên khai thác
dữ liệu ra đời và đƣợc xem nhƣ là một kết quả của sự tiến hóa tự nhiên của công nghệ
thông tin.

Tiền xử lý

Chuyển
đổi dữ liệu

Khai phá
dữ liệu

4. Chuyển đổi dữ liệu (dữ liệu đƣợc chuyển hoặc hợp nhất thành các hình thức
thích hợp cho khai thác bằng cách thực hiện tóm tắt hoặc tập hợp)
5. Khai thác dữ liệu (một quá trình cần thiết mà các phƣơng pháp thông minh
đƣợc áp dụng để trích xuất các mẫu dữ liệu)
6. Đánh giá các mẫu (để xác định các mẫu thực sự thú vị đại diện cho kiến
thức dựa trên một số biện pháp)
7. Trình bày tri thức (nơi trực quan và kỹ thuật biểu diễn tri thức đƣợc sử dụng
để trình bày các kiến thức khai thác cho ngƣời sử dụng)


11
Một cách khái quát thì khai phá dữ liệu gồm 3 giai đoạn chính [9]:
Giai đoạn tiền xử lý: Giai đoạn tiền xử lý đƣợc hiểu là các chức năng liên quan đến
việc tiếp nhận, tổ chức và biến đổi dữ liệu. Giai đoạn này có mục tiêu là chuẩn bị dữ
liệu cho giai đoạn sau của việc khai thác dữ liệu. Giai đoạn này gồm các bƣớc từ 1 đến
4.
Giai đoạn khai thác dữ liệu: Giai đoạn này đƣợc định nghĩa bởi việc sử dụng các
thuật toán để trích rút các mẫu dữ liệu. Một số các kỹ thuật đƣợc sử dụng trong giai
đoạn này nhƣ mạng neural, tập thô, thuật toán di truyền, mô hình thống kê và xác suất.
Giai đoạn hậu xử lý: Giai đoạn này chế biến dữ liệu thu đƣợc từ quá trình khai thác
dữ liệu. Nó có khả năng xác nhận tính hữu ích của mẫu dữ liệu đƣợc khai phá.
[4]Khai phá dữ liệu nhƣ là một thuật ngữ đƣợc sử cho các thiết lập cụ thể của sáu
nhiệm vụ sau: Phân lớp dữ liệu, ƣớc lƣợng, dự báo, khai phá luật kết hợp, phân cụm,
mô tả và trực quan. Trong đó ba nhiệm vụ đầu tiên – phân lớp dữ liệu, ƣớc lƣợng, dự
báo là tất cả các ví dụ về hƣớng khai thác dữ liệu hoặc học có giám sát. Trong hƣớng
khai thác dữ liệu này, mục tiêu là sử dụng dữ liệu có sẵn để xây dựng một mô hình mô
tả một hoặc nhiều thuộc tính cụ thể quan tâm (thuộc tính mục tiêu hoặc các thuộc tính
lớp) trong giới hạn của phần còn lại của các thuộc tính có sẵn. Ba nhiệm vụ tiếp theo luật kết hợp, phân nhóm và mô tả là các ví dụ về khai thác dữ liệu vô hƣớng tức
(không có thuộc tính). Nó đƣợc chỉ ra nhƣ là mục tiêu. Mục tiêu là để thiết lập một số
mối quan hệ giữa tất cả các thuộc tính.

Phân cụm là một quá trình phân vùng hoặc phân nhóm một tập các đối tƣợng
thành các nhóm. Trong đó, các đối tƣợng trong cùng một nhóm tƣơng tự nhƣ nhau và
các đối tƣợng trong các nhóm khác nhau là không giống nhau. Phân cụm thƣờng đƣợc
coi là phân lớp không giám sát. Nó thƣờng đƣợc dùng để phân nhóm các khách hàng.
Mô tả và trực quan
Dữ liệu trực quan là một thế mạnh của khai thác dữ liệu mô tả. Nó thƣờng không
dễ dàng cho các hình dung có ý nghĩa. Những hình ảnh đúng thực sự có thể đáng giá
hàng nghìn luật kết hợp khi con ngƣời thực hiện các công việc trích xuất ý nghĩa từ
những hình ảnh thực tế.

1.2. Các khái niệm cơ bản của tập thô [9]
Lý thuyết tập thô đƣợc đề xuất vào năm 1982 bởi Zdzislaw Pawlak. Phƣơng pháp
luận của nó là liên quan tới việc phân loại và phân tích chính xác các thông tin và tri
thức không chắc chắn hoặc không đầy đủ. Nó đƣợc coi là một trong những phƣơng
pháp tiếp cận đầu tiên không dựa trên thống kê trong phân tích dữ liệu. Lý thuyết tập
thô đƣợc phát triển trên một nền tảng toán học vững chắc, cung cấp các công cụ hữu
ích để giải quyết các bài toán phân tích dữ liệu, phát hiện luật, nhận dạng. Mục đích
chính của phân tích dữ liệu dựa trên lý thuyết tập thô nhằm đƣa ra các xấp xỉ để biểu
diễn các đối tƣợng không thể đƣợc phân lớp một cách chắc chắn bằng tri thức có sẵn.
Theo quan điểm của lý thuyết tập thô, mọi tập thô đều liên kết với 2 tập “rõ” là xấp xỉ
dƣới và xấp xỉ trên của nó. Xấp xỉ dƣới bao gồm các đối tƣợng chắc chắn thuộc, còn
xấp xỉ trên chứa tất cả các đối tƣợng có khả năng thuộc về tập đó. Các tập xấp xỉ là cơ
sở để rút ra các kết luận (tri thức) từ cơ sở dữ liệu.
1.2.1. Tập hợp
Một tập hợp là một tập các đối tƣợng có những đặc điểm tƣơng tự, nó là một
phần cơ bản của toán học. Tất cả các đối tƣợng toán học chẳng hạn nhƣ các mối quan
hệ, chức năng, con số có thể đƣợc coi là một tập hợp. Các thành phần khác nhau của
một tập hợp đƣợc gọi là các yếu tố. Mối quan hệ giữa một phần tử và một tập hợp



Thuộc tính
tƣợng
a1
a2
a3
x1
2
1
3
x2
3
2
1
x3
2
1
3
x4
2
2
3
x5
1
1
4
x6
1
2
2
x7

a2= {1, 2}
a3= {1, 2, 3, 4}
Tập cơ bản
Cho x ∈ U, B ⊆ A. Một tập cơ bản B chứa x, ký hiệu là [x]b đƣợc biểu điễn nhƣ sau:
∩ {[(a, v)]|a ∈ B, f x, a = v}
Tập cơ bản là tập con của U bao gồm tất cả các đối tƣợng trên U có thể phân biệt từ x
trong khi sử dụng tất cả các thuộc tính từ B. Trong thuật ngữ tính toán mềm, tập con
đƣợc gọi là hạt thông tin. Khi B là tập hợp con giới hạn trong một thuộc tính duy nhất,
tập con là khối các cặp thuộc tính-giá trị đƣợc định nghĩa bởi thuộc tính cụ thể đó. Do
đó:
[x5] a3= [x8] a3= [(a3, 4)]={x5, x8}
Ngoài ra nếu b = {a2, a3} thì ta sẽ có:
[x5]b = [x8]b = [(a2, 1)] ∩ [(a3, 4)] ={x5, x8}
1.2.3. Quan hệ bất khả phân
Cho hệ thông tin T = (U, A) và B ≠ ∅ và B ⊆ A. Quan hệ bất khả phân trên U
theo B, ký hiệu là IND(B) và đƣợc định nghĩa nhƣ sau:
∀x, y ∈ U, x, y ∈ IND B ⇔ f x, a = f y, a với a ∈ B
Rõ ràng, IND(B) là một quan hệ tƣơng đƣơng trên U. Các lớp tƣơng đƣơng của
IND(B) đƣợc gọi là tập cơ bản trong B bởi vì nó đại diện cho các nhóm nhỏ rõ rệt nhất
của các đối tƣợng. Với đối tƣợng bất kỳ 𝑥 ∈ 𝑈, các lớp tƣơng của 𝑥 trong mối quan hệ
IND(B) đƣợc ký hiệu là [𝑥]𝐼𝑁𝐷(𝐵) . Xây dựng tập cơ bản là bƣớc đầu tiên trong phân
loại với tập thô.
Chúng ta thấy rằng, có một số các đối tƣợng giống hệt nhau trong bảng 1.1. Ví dụ nhƣ
đối tƣợng 1, 3 và 9 là không thể phân biệt đƣợc dựa trên các thuộc tính có sẵn. Chúng
ta nhóm tất cả các đối tƣợng có bộ giá trị thuộc tính giống nhau. Ta đƣợc kết quả nhƣ
bảng 1.2.


15


1.2.4. Tập xấp xỉ trên và xấp xỉ dƣới
Cách tiếp cận bộ thô để phân tích dữ liệu bản lề trên hai khái niệm cơ bản tập xấp
xỉ dƣới và tập xấp xỉ trên. Nó đề cập đến các phần tử chắc chắn thuộc và các phần tử
có khả năng thuộc tập.
Lấy 𝑋 ký hiệu là tập con của tập vũ trụ 𝑈 (𝑋 ⊂ 𝑈). Tập xấp xỉ dƣới và tập xấp xỉ trên
của 𝑋 trong 𝐵(𝐵 ⊆ 𝐴) đƣợc định nghĩa nhƣ sau:
Tập xấp xỉ dƣới
Tập xấp xỉ dƣới đƣợc ký hiệu là 𝐵𝑋 đƣợc định nghĩa là sự kết hợp của tất cả các
tập cơ bản chứa trong 𝑋.
𝐵𝑋 = {𝑥 ∈ 𝑈| 𝑥 𝐼𝑁𝐷 𝐵 ⊂ 𝑋}
Tập xấp xỉ trên
Tập xấp xỉ trên đƣợc ký hiệu là 𝐵𝑋, là sự kết hợp của các tập cơ bản mà giao của
nó với X là tập khác rỗng.
𝐵𝑋 = {𝑥 ∈ 𝑈| 𝑥 𝐼𝑁𝐷 𝐵 ∩ 𝑋 ≠ ∅}
Một đối tƣợng x bất kỳ thuộc vào tập xấp xỉ dƣới của X, nó chắc chắn sẽ thuộc về tập
X. Còn với một đối tƣợng bất kỳ nằm trong tập xấp xỉ trên, chúng ta chỉ có thể nói
rằng nó có thể nằm trong X.
Tập biên
Tập biên của tập X trong U đƣợc định nghĩa là sự sai khác giữa tập xấp xỉ trên
và tập xấp xỉ dƣới, nó chứa các phần tử có ở tập xấp xỉ trên nhƣng không có ở tập xấp
xỉ dƣới.
𝐵𝑁𝑋 = 𝐵𝑋 − 𝐵𝑋
BNX đƣợc gọi là lớp biên của X trong U.
Các tính chất của tập xấp xỉ :


16
1) 𝐵𝑋 ⊆ 𝑋 ⊆ 𝐵𝑋
2) 𝐵∅ = 𝐵∅ = ∅, 𝐵𝑈 = 𝐵𝑈 = 𝑈
3) 𝐵(𝑋 ∪ 𝑌) = 𝐵 𝑋 ∪ 𝐵(𝑌)

giờ, nhiệm vụ của ta là xây dựng tập xấp xỉ trên của tập con X. Để tinh toán đƣợc tập
xấp xỉ trên của X, chúng ta phải tìm kiếm trong bảng 1.2 tất cả các tập cơ bản mà nó có
ít nhất một đối tƣợng chung với tập X. Đó là các tập:
{x1, x3, x9}, {x4}, {x5, x8}
Vậy ta có tập xấp xỉ trên của tập X: 𝐵𝑋 = {𝑥1 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥8 , 𝑥9 } và 𝐵𝑁𝑋 =
{𝑥1 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥8 , 𝑥9 } − x1 , 𝑥3 , x4 , x9 = {𝑥5 , 𝑥8 }
1.2.5. Bảng quyết định [7]
Định nghĩa 1.2: Một hệ thống thông tin mà trong hệ thống này chúng ta phân
biệt đƣợc hai loại thuộc tính của nó, thuộc tính điều kiện và thuộc tính quyết định thì
đƣợc gọi là bảng quyết định. Tập thuộc tính điều kiện và tập thuộc tính quyết định
giúp ta xác định đƣợc các phân lớp trên bảng quyết định. Các phân lớp đƣợc xác định
thông qua thuộc tính điều kiện. Sau khi có các phân lớp, chúng ta sẽ xác định đƣợc các
phân lớp tƣơng đƣơng bằng các thuộc tính quyết định.
Một bảng quyết định cùng một tập thuộc tính điều kiện C và một tập thuộc tính quyết
định D đƣợc ký hiệu 𝑆 = (𝑈, 𝐶, 𝐷) với 𝐶, 𝐷 ≠ ∅, 𝐶 ∩ 𝐷 = ∅, 𝐶 ∪ 𝐷 = 𝐴.
Ví dụ về bảng quyết định:
Thuộc tính
Thuộc tính điều kiện
Ngƣời
quyết định
bệnh
Đau đầu
Đau cơ
Nhiệt độ
Bệnh cúm
p1
không
có
cao
có

Lớp không = { p4, p5}
Mỗi một dòng trên bảng quyết định xác định một luật quyết định. Trong mỗi luật
quyết đinh, quyết định đƣợc thực hiện khi mà các điều kiện chỉ ra các thuộc tính điều
kiện đƣợc thỏa mãn. Ví dụ nhƣ trong bảng 1.3 với điều kiện (nhức đầu, không có),
(đau cơ, có), (nhiệt độ, cao) xác định duy nhất quyết định (bệnh cúm, có).
Luật quyết định ở dòng 2 và dòng 5 trong bảng 1.3 có cùng điều kiện nhƣng quyết
định đƣa ra lại khác nhau. Quyết định này đƣợc gọi là không nhất quán (không chính


18
xác, mâu thuẫn). Ngƣợc lại với các luật này thì ta có các luật quyết định nhất quán
(nhất định, xác định và không mâu thuẫn). Đôi khi, các luật quyết định nhất quán đƣợc
gọi là các luật chắc chắn và các luật không nhất quán đƣợc gọi là các luật có thể xảy
ra. Bảng quyết định chứa các luật không nhất quán gọi là bảng quyết không nhất quán
còn ngƣợc lại là bảng quyết định nhất quán. Số lƣợng các luật nhất quán với tất cả các
luật trong bảng quyết định đƣợc coi là hệ số nhất quán của bảng quyết định. Nó đƣợc
ký hiệu là 𝛾(𝐶, 𝐷) trong đó C, D là các thuộc tính điều kiện và thuộc tính quyết định
của bảng quyết định. 𝛾 𝐶, 𝐷 = 1 thì bảng quyết định là nhất quán còn 𝛾 𝐶, 𝐷 ≠ 1
thì bảng quyết định là không nhất quán. Ở bảng 3 ta có 𝛾 𝐶, 𝐷 = 4/6 vì vậy bảng 1.3
là bảng quyết định không nhất quán.
1.2.6. Luật quyết định
Luật quyết định là gì? [8] Luật quyết định thƣờng đƣợc ở dạng: Nếu (điều kiện
thuộc tinh thỏa mãn) thì (đƣa ra quyết định phù hợp). Thí dụ luật 1 trong bảng 1.3:
Nếu (đau đầu, không) và (đau cơ, có) và (nhiệt độ, cao) thì (bệnh cúm, có). Một tập
các luật quyết định đƣợc gọi là một thuật toán quyết định. Do đó với mỗi một bảng
quyết định, chúng ta có thể kết hợp một thuật toán quyết định bao gồm tất cả các luật
quyết định xảy ra trong bảng quyết định. Hay nói cách khác một trình tự sẽ đƣợc gọi là
một luật quyết định đƣợc tạo ra bởi đối tƣợng x (nằm trong bảng quyết đinh S) và
đƣợc ký hiệu nhƣ sau: 𝑐1 𝑥 , … , 𝑐𝑛 𝑥 → 𝑑1 𝑥 , … , 𝑑𝑚 (𝑥) hoặc viết gọn lại 𝐶 → 𝑥 𝐷.
Trong đó, chúng ta quan tâm tới các độ đo quan trọng và cần thiết của luật quyết định.


Nếu 𝐶𝑖 → 𝐷𝑗 là một luật quyết định thì 𝐷𝑗 → 𝐶𝑖 sẽ đƣợc một luật quyết định ngƣợc của
nó. Các luật quyết định ngƣợc đƣợc dùng để giải thích (các lý do) của một luật quyết
định.
Từ vì dụ ở bảng 3 ta có:
U/C={C1, C2, C3, C4, C5}
U/D = {D1, D2}
C1= {p1}
D1 = {p1, p2, p3, p6}
C2= {p2, p5}
D2 = {p4, p5}
C3={p3}
C4= {p4}
C5= {p6}
Chúng ta có độ mạnh, độ chắc chắn và độ phủ thể hiện ở bảng 1.4 dƣới đây:
Luật
Độ mạnh
Độ chính xác
Độ phủ
1
0.17
1.00
0.25
2
0.17
0.50
0.25
3
0.17
1.00

𝑆𝑢𝑝𝑝(𝐶2 , 𝐷2 ) ⋯ 𝑆𝑢𝑝𝑝(𝐶2 , 𝐷𝑛 )
𝑆𝑢𝑝𝑝 (𝐶, 𝐷) =
⋮
⋮
⋮
⋮
𝑆𝑢𝑝𝑝 𝐶𝑚 , 𝐷1 𝑆𝑢𝑝𝑝(𝐶𝑚 , 𝐷2 ) ⋯ 𝑆𝑢𝑝𝑝(𝐶𝑚 , 𝐷𝑛 )
Ma trận độ chính xác:


20

𝐴𝑐𝑐 (𝐶, 𝐷) =

𝐴𝑐𝑐 𝐶1 , 𝐷1
𝐴𝑐𝑐 𝐶2 , 𝐷1
⋮
𝐴𝑐𝑐 𝐶𝑚 , 𝐷1

𝐴𝑐𝑐(𝐶1 , 𝐷2 )
𝐴𝑐𝑐(𝐶2 , 𝐷2 )
⋮
𝐴𝑐𝑐(𝐶𝑚 , 𝐷2 )

…
⋯
⋮
⋯

𝐴𝑐𝑐(𝐶1 , 𝐷𝑛 )

quyết định. Tập thô thƣờng đƣợc rời rạc hóa, rút gọn và đƣa ra các luật dựa trên tập dữ
liệu huấn luyện hay các phân lớp trên tập dữ liệu mẫu ban đầu trong khai phá dữ liệu.
Nó giúp biễu diễn và đƣa ra kết luận cho các tri thức không chắc chắn. Khai phá luật
quyết định dựa trên tập thô là một hƣớng nghiên cứu rất phố biến hiện nay. Phƣơng
pháp này thƣờng áp dụng kỹ thuật phân lớp của khai phá dữ liệu.

1.4. Kết luận chƣơng 1
Chƣơng 1 trình bày tổng quan về khai phá dữ liệu, các khai niệm cơ bản về tập
thô. Đây là chƣơng đƣa ra các khái niệm cơ bản để tạo tiền đề tiếp cận và tìm hiểu cho
chƣơng sau.


21

CHƢƠNG 2. THUẬT TOÁN TIẾP CẬN GIA TĂNG ĐỂ KHAI PHÁ
LUẬT QUYẾT ĐỊNH TRÊN CƠ SỞ DỮ LIỆU CÓ GIÁ TRỊ THUỘC
TÍNH THAY ĐỔI
Trong lý thuyết tập thô, tập xấp xỉ trên và xấp xỉ dƣới là những khái niệm có tính
thay đổi động nhƣ một hệ thống thông tin thay đổi theo thời gian. Khi tập xấp xỉ thay
đổi, các luật quyết định trƣớc đó sẽ bị thay đổi và đôi khi không còn có giá trị. Vậy,
chúng ta phải làm thế nào để cập nhật tập xấp xỉ dựa trên bản gốc thông tin và thu
đƣợc các luật quyết định có ý nghĩa tại thời điểm này? Đây là một nhiệm vụ quan
trọng có thể giúp ta nâng cao hiệu quả của việc khai phá tri thức.
Trong các ứng dụng thực tế, miền giá trị của các thuộc tính thay đổi theo thời
gian và nó thay đổi thƣờng theo hai xu hƣớng: giá trị mới có thể đƣợc thêm vào hoặc
bị xóa bớt ở trong miền giá trị của thuộc tính, đó là phƣơng thức làm thô và làm mịn
các giá trị thuộc tính. Trong trƣờng hợp này, miền giá trị có thể tăng lên hoặc giảm đi.
Khi giá trị thuộc tính thay đổi thì tri thức thu đƣợc có bị thay đổi không ? Điều này đã
đƣợc làm sáng tỏ trong [2]. Chen và cộng sự đã trình bày một phƣơng pháp tiếp cận
gia tăng để cập nhật động các xấp xỉ khi làm thô và làm mịn các giá trị thuộc tính. Kết

thuộc tính 𝑎𝑙 , 𝑓 𝑥𝑖 , 𝑎𝑙 ≠ 𝑓 𝑥𝑘 , 𝑎𝑙 . Đến một thời điểm nào đó, ta có
𝑈𝑎 𝑙 = {𝑥𝑖 ′ ∈ 𝑈|𝑓 𝑥𝑖 ′ , 𝑎𝑙 = 𝑓(𝑥𝑖 , 𝑎𝑙 )}. Và ta cũng có 𝑓 𝑥𝑖 ′ , 𝑎𝑙 = 𝑓(𝑥𝑘 , 𝑎𝑙 ), với
𝑥𝑖 ′ ∈ 𝑈𝑎 𝑙 . Chúng ta gọi giá trị thuộc tính 𝑓(𝑥𝑖 , 𝑎𝑙 ) đã đƣợc làm thô thành giá trị mới
𝑓(𝑥𝑘 , 𝑎𝑙 ).
Định nghĩa 2.3: Cho hệ thống thông tin 𝐼𝑆 = (𝑈, 𝐴), 𝐵 ⊆ 𝐴, 𝑎𝑙 ∈ 𝐵, 𝑓(𝑥𝑖 , 𝑎𝑙 ) là giá trị
của đối tƣợng 𝑥𝑖 trên thuộc tính 𝑎𝑙 . Đến một thời điểm nào đó, ta có
𝑈𝑎 𝑙 = {𝑥𝑖 ′ ∈ 𝑈|𝑓 𝑥𝑖 ′ , 𝑎𝑙 = 𝑓(𝑥𝑖 , 𝑎𝑙 )}. Và ta có 𝑓 𝑥𝑖 ′ , 𝑎𝑙 = 𝑣 và 𝑣 ∉ 𝑉𝑎 𝑙 , 𝑥𝑖 ′ ∈ 𝑈𝑎 𝑙 .
Thì chúng ta gọi giá trị thuộc tính 𝑓(𝑥𝑖 , 𝑎𝑙 ) trên đối tƣợng 𝑥𝑖 ′ đƣợc làm mịn thành giá
trị 𝑣.

2.2. Mô hình tiếp cận gia tăng và thuật toán
Tiếp cận gia tăng là một phƣơng pháp phổ biến và đƣợc sử dụng nhiều trong khai
phá dữ liệu. Đây là một cách lƣu trữ tất cả dữ liệu và nó cũng cho phép tập huấn lại dữ
liệu. Trong khai phá dữ liệu học gia tăng thƣờng đƣợc áp dụng cho môi trƣờng dữ liệu
luôn thay đổi. Trong đó, phƣơng pháp tiếp cận gia tăng dựa trên kỹ thuật phân lớp là
một phƣơng pháp hay dùng. Nơi mà dữ liệu thay đổi nhƣng không cùng một lúc. Một
phân lớp đƣợc gọi là gia tăng khi nó đủ bốn tiêu chí sau: Có thể học thêm thông tin từ
dữ liệu mới, không yêu cầu truy cập dữ liệu gốc để tạo ra các dữ liệu hiện có, bảo vệ
kiến thức thu đƣợc trƣớc đó, nó có thể chứa các lớp mới mà các lớp này có thể đƣợc
đƣa ra từ dữ liệu mới. Phần 2.2.1 tiếp theo đây sẽ trình bày về thuật toán tiếp cận gia
tăng dựa trên kỹ thuật phân lớp với tập thô.
2.2.1. Mô hình bài toán và kiến thức cơ sở tiếp cận thuật toán khi giá trị thuộc
tính thay đổi
2.2.1.1. Mô hình bài toán tiếp cận:
Chúng ta giả thiết tồn tại 2 thời điểm t và t+1 trong mô hình có hệ thống thông
tin IS = U, A . Với A = C ∪ D; C là tập các thuộc tính điều kiện và U/C =
𝐶1 , 𝐶2 , … , 𝐶𝑚 là các phân lớp điều kiện; D là tập các thuộc tính quyết định và U/D =
{𝐷1 , 𝐷2 , … , 𝐷𝑛 } là các phân lớp quyết định (0
tính quyết định. Trong phạm vi luận văn này, chúng ta chỉ xét tại thởi điểm t+1 chỉ có
một trƣờng hợp thay đổi giá trị thuộc tính.
Sự thay đổi giá trị thuộc tính điều kiện (quyết định) đều ảnh hƣởng tới việc phân
lớp và các phần tử trong lớp tƣơng ứng bị tác động. Để thu đƣợc các phân lớp tƣơng
đƣơng bị thay đổi và thu nạp các phần tử tƣơng ứng với lớp này, ta cần đi sâu nghiên
cứu các tính chất cơ bản của quá trình làm thô và làm mịn các thuộc tính điều kiện
(quyết định). Theo [1], ta có các kết quả và hệ quả sau đây tƣơng ứng với 4 trƣờng hợp
thay đổi của thuộc tính.
(1) Làm thô các giá trị thuộc tính điều kiện:
Tại thời điểm t, hai giá trị 𝑒 và 𝑕 của thuộc tính 𝑎𝑖 ∈ 𝐶 đƣợc làm thô tới giá trị
mới 𝑤, 𝑤 ∉ 𝑉𝑎 𝑖 . Tại thời điểm t+1, tồn tại 2 lớp tƣơng đƣơng 𝐶𝑢 , 𝐶𝑧 đƣợc làm thô
thành lớp tƣơng đƣơng 𝐶𝑤 , khi và chỉ khi ∀ 𝑎𝑖 ≠ 𝑎𝑗 , 𝑓𝑡 𝐶𝑢 , 𝑎𝑗 = 𝑓𝑡 (𝐶𝑧 , 𝑎𝑗 ).
Chứng minh:
Ta chứng minh chiều thuận: Hai lớp tƣơng 𝐶𝑢 , 𝐶𝑧 đƣợc làm thô thành lớp tƣơng
đƣơng 𝐶𝑤 thì suy ra ∀ 𝑎𝑖 ≠ 𝑎𝑗 , 𝑓𝑡 𝐶𝑢 , 𝑎𝑗 = 𝑓𝑡 (𝐶𝑧 , 𝑎𝑗 ):