ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN

THÔNG

PHẠM THANH TUẤN

NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP

TÌM CÁC LUẬT KẾT HỢP PHÂN LỚP TRÊN TẬP MẪU HỌC

VÀ ỨNG DỤNG TRONG CHẨN ĐOÁN BỆNH

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Thái Nguyên, 2019

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN

THÔNG

PHẠM THANH TUẤN

NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP

TÌM CÁC LUẬT KẾT HỢP PHÂN LỚP TRÊN TẬP MẪU HỌC

VÀ ỨNG DỤNG TRONG CHẨN ĐOÁN BỆNH

Chuyên ngành: Khoa học máy tính

Mã số: 8 48 01 01

Người hướng dẫn khoa học: TS. Lê Văn Phùng

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Thái Nguyên, 2019

i

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện, dưới sự

hướng dẫn khoa học của TS. Lê Văn Phùng. Các số liệu và kết quả trình bày

trong luận văn là trung thực, chưa được công bố bởi bất kỳ tác giả này hay ở

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

bất kỳ công trình nào khác.

ii

LỜI CẢM ƠN

Trong quá trình thực hiện đề tài “Nghiên cứu một số phương pháp tìm

các luật kết hợp phân lớp trên tập mẫu học và ứng dụng trong chẩn đoán bệnh”,

tôi đã nhận được rất nhiều sự giúp đỡ, tạo điều kiện của tập thể Ban Giám hiệu,

Phòng Đào tạo, khoa Công nghệ thông tin và các phòng chức năng của trường

Đại học Công nghệ thông tin và truyền thông, Đại học Thái Nguyên. Tôi xin

bày tỏ lòng cảm ơn chân thành về sự giúp đỡ quý báu đó.

Tôi xin được bày tỏ lòng biết ơn sâu sắc đến TS. Lê Văn Phùng là thầy

giáo trực tiếp hướng dẫn, chỉ bảo giúp tôi hoàn thành luận văn này.

TÁC GIẢ LUẬN VĂN

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Phạm Thanh Tuấn

iii

MỤC LỤC

LỜI CAM ĐOAN .............................................................................................. i

LỜI CẢM ƠN ................................................................................................... ii

DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT ....................................... v

DANH MỤC BẢNG BIỂU ............................................................................. vi

DANH MỤC HÌNH VẼ .................................................................................. vii

MỞ ĐẦU ........................................................................................................ viii

CHƯƠNG 1. PHÂN LỚP VÀ PHƯƠNG PHÁP XÂY DỰNG CÂY

PHÂN LỚP THEO TẬP MẪU HỌC ............................................................ 1

1.1. Tổng quan về kỹ thuật khai phá dữ liệu ..................................................... 1

1.1.1. Khái niệm về khai phá dữ liệu ................................................................ 1

1.1.2. Một số phương pháp khai phá dữ liệu hiện đại và thông dụng ............... 2

1.1.3. Các ứng dụng khai phá dữ liệu ............................................................... 3

1.2. Những vấn đề chung nhất về phân lớp và phương pháp phân lớp cơ bản . 7

1.2.1 Khái niệm phân lớp dữ liệu ...................................................................... 7

1.2.2. Các bước tiến hành phân lớp dữ liệu ...................................................... 7

1.2.3. Phân lớp theo cây quyết định .................................................................. 9

1.2.4. Phân lớp kiểu Bayes .............................................................................. 12

1.2.5. Phân lớp dựa trên các quy tắc IF-THEN ............................................... 13

1.2.6. Phân lớp dựa trên luật kết hợp .............................................................. 16

1.2.7. Phân lớp dựa vào K-lân cận gần nhất ................................................... 18

1.2.8. Phân lớp dựa vào giải thuật di truyền ................................................... 19

1.2.9. Phân lớp theo cách tiếp cận tập thô ....................................................... 20

1.2.10. Phân lớp theo cách tiếp cận tập mờ .................................................... 21

1.3. Khái niệm về tập mẫu học và phương pháp xây dựng cây phân lớp ....... 24

1.3.1. Định nghĩa tập mẫu học ........................................................................ 24

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

1.3.2. Xây dựng cây phân lớp dựa theo Khóa ................................................. 24

iv

1.3.3. Xây dựng cây phân lớp nhờ các luật kết hợp phân lớp (Class

Association Rules) trong bảng mẫu học ......................................................... 27

CHƯƠNG 2. MỘT SỐ PHƯƠNG PHÁP TÌM CÁC LUẬT KẾT HỢP

PHÂN LỚP TRÊN TẬP MẪU HỌC .......................................................... 29

2.1. Phương pháp phân lớp dựa trên luật kết hợp ........................................... 29

2.1.1. Các bước tiến hành phân lớp dựa trên luật kết hợp .............................. 29

2.1.2. Tạo luật kết hợp bằng cây quyết định ................................................... 29

2.2. Một số thuật toán cổ điển xây dựng cây phân lớp dựa trên luật kết hợp . 29

2.2.1. Thuật toán CBA-RG ............................................................................. 30

2.2.2. Thuật toán CBA-CB .............................................................................. 32

2.3. Thuật toán hiện đại ................................................................................... 34

2.3.1. Thuật toán CBA cải tiến ........................................................................ 34

2.3.2. Ví dụ áp dụng thuật toán cải tiến .......................................................... 37

CHƯƠNG 3. CHƯƠNG TRÌNH THỬ NGHIỆM TÌM CÁC LUẬT KẾT

HỢP PHÂN LỚP DỰA TRÊN TẬP MẪU HỌC....................................... 42

3.1. Bài toán thử nghiệm ................................................................................. 42

3.1.1. Bài toán và tập mẫu học đầu vào .......................................................... 42

3.1.2. Chọn thuật toán thử nghiệm .................................................................. 46

3.2. Môi trường thử nghiệm ............................................................................ 47

3.2.1. Chọn môi trường chứa dữ liệu đầu vào ................................................ 47

3.2.2. Chọn ngôn ngữ lập trình ....................................................................... 47

3.3. Nội dung và kết quả thử nghiệm .............................................................. 47

3.3.1. Mô hình thuật toán thử nghiệm ............................................................. 47

3.3.3. Một số giao diện chính của chương trình thử nghiệm .......................... 50

3.4. Đánh giá chương trình thử nghiệm .......................................................... 51

3.5. Mở rộng bài toán ...................................................................................... 51

KẾT LUẬN .................................................................................................... 60

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

TÀI LIỆU THAM KHẢO ............................................................................ 62

v

DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT

1. DM – Data Mining.

2. CSDL – Cơ sở dữ liệu.

3. CBA - Classification-Based Associon

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

4. CMAR - Classification based on Multiple Asociation Rule

vi

DANH MỤC BẢNG BIỂU

Bảng 1.1. Ví dụ về tập mẫu học…………………………………….….....15

Bảng 1.2. Các bộ huấn luyện đã được phân lớp trong CSDL……….…....20

Bảng 1.3. Ví dụ tập mẫu học được phân lớp dựa theo khóa…………...…33

Bảng 2.1. Ví dụ tập mẫu học để tìm các luật kết hợp phân lớp theo thuật toán

cải tiến……………………………………………………...…………..47

Bảng 2.2. Bảng tổng hợp………………………………………..………...49

Bảng 2.3a. Khoản mục…………………………………………..…….…...50

Bảng 2.3b. Các luật kết hợp phân lớp phổ biến 1 – Khoản mục……..….…50

Bảng 2.3c. Các luật kết hợp phân lwps 2 – Khoản mục………..……….…50

Bảng 3.1. Tập mẫu học……………………………………………………55

Bảng 3.2. Bảng mẫu học được số hóa…………………………………….56

Bảng 3.3. Bảng tổng hợp kết quả thu được…………………………...…..59

Bảng 3.4. Bảng mấu học (mở rộng) đầu vào……………………………...60

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Bảng 3.5. Bảng mẫu học mở rộng được số hóa………………………......64

vii

DANH MỤC HÌNH VẼ

Hình 1.1. Cây quyết định cho việc chơi Gold………….………………...….16

Hình 1.2. Một tập thô xấp xỉ tập các bộ của C khi dùng các tập xấp xỉ trên và

dước của C. Các vùng hình chũ nhật biểu diễn các lớp tương

đương………………………………………………………...………………27

Hình 1.3. Các giá trị mờ thật với thu nhập, biểu diễn mức thành viên các giá

trị thu nhập theo các loại {thấp, trung bình, cao}……………...................…28

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Hình 1.4. Cây phân lớp xây dựng với 2 trường hợp…………………………34

viii

MỞ ĐẦU

1. Lý do chọn đề tài

Thế kỷ XXI được xem là một kỷ nguyên của công nghệ thông tin. Cùng

với việc ứng dụng công nghệ thông tin ở hầu hết các lĩnh vực trong nhiều năm

qua dẫn đến lượng dữ liệu, thông tin của nhân loại được lưu trữ ngày một tăng.

Nguồn dữ liệu khổng lồ ấy được tích lũy với tốc độ bùng nổ từ rất nhiều lĩnh

vực: khoa học, kinh doanh, giao dịch, thương mại, chứng khoán,… Vậy chúng

ta có thể khai thác được gì từ “núi” dữ liệu tưởng chừng như bỏ đi ấy.

Cùng với việc tăng không ngừng khối lượng dữ liệu, các hệ thống thông

tin cũng được chuyên môn hóa, phân hạch hóa theo các lĩnh vực như sản xuất,

tài chính, buôn bán thị trường .v.v, tuy nhiên các hệ quản trị cơ sở dữ liêu truyền

thống chỉ khai thác được một lượng thông tin nhỏ không còn đáp ứng đủ những

yêu câu, những thách thức mới. Do vậy một khuynh hướng mới được ra đời đó

là kỹ thuật phát hiện tri thức trong cơ sở dữ liệu. Khai phá dữ liệu (Data Mining

– DM) ra đời phần nào đó đã giải quyết hữu hiệu những yêu cầu, thách thức

đó.

Một trong những lĩnh vực nghiên cứu các phương pháp ứng dụng khai

phá dữ liệu, tìm kiếm tri thức, kết xuất tri thức… từ dữ liệu là tìm kiếm các

Luật kết hợp phân lớp (Class Association Rules) cũng được nghiên cứu từ nhiều

năm trước đây và đã có những kết quả khả quan và mang lại hướng ứng dụng

có hiệu quả cao. Ngày nay, kỹ thuật khai phá dữ liệu dựa trên việc tìm kiếm

các luật kết hợp phân lớp đã được áp dụng và mang lại hiệu quả cho nhiều

ngành, nhiều lĩnh vực như: Kinh tế, tài chính, khoa học - kỹ thuật, ngân hàng,

thương mại, giáo dục, y tế… các kỹ thuật khai phá dự liệu bằng Luật kết hợp

phân lớp rất đa dạng và phong phú như các kỹ thuật dựa trên các thuật toán

CBA-RG, CBA-CB,…

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Với mong muốn nắm vững hơn các quá trình phát hiện tri thức từ dữ liệu

ix

sử dụng Luật kết hợp phân lớp nhằm phục vụ công tác nghiên cứu chuyên môn

cũng như mong muốn đưa các kỹ thuật khai phá dữ liệu sử dụng Luật kết hợp

phân lớp vào thực tế nên tôi lựa chọn thực hiện luận văn tốt nghiệp với đề tài

“Nghiên cứu một số phương pháp tìm các luật kết hợp phân lớp trên tập mẫu

học và ứng dụng trong chẩn đoán bệnh”. Mục đích thực hiện luận văn này là

tổng hợp các kiến thức về kỹ thuật khai phá dữ liệu bằng phương pháp tìm các

luật kết hợp phân lớp trên tập mẫu học.

2. Đối tượng và phạm vi nghiên cứu:

Đối tượng nghiên cứu là những kỹ thuật phân lớp dựa trên luật kết hợp

Phạm vi nghiên cứu tập trung vào các thuật toán tìm kiếm Luật kết hợp

phân lớp cổ điển và hiện đại.

3. Hướng nghiên cứu của đề tài:

Nghiên cứu các kỹ thuật khai phá dữ liệu nói chung, trong đó chú trọng

việc tìm các luật kết hợp phân lớp trên tập mẫu học.

Nghiên cứu những bài toán ứng dụng phương pháp cải tiến tìm các luật

kết hợp phân lớp trên tập mẫu học.

4. Phương pháp nghiên cứu:

Kết hợp lý thuyết với đánh giá thực nghiệm.

Sưu tập và tổng hợp các kết quả nghiên cứu về khai phá dữ liệu, thuật

toán tìm các luật kết hợp phân lớp từ nguồn sách của các nhà xuát bản trong và

ngoài nước, các luận văn cao học, luận án tiến sĩ và các bài báo khoa học.

Phân tích bài toán ứng dụng và chọn lọc thuật toán thử nghiệm thích hợp

(dự kiến là áp dụng thuật toán cải tiến).

5. Ý nghĩa khoa học, thực tiễn của đề tài:

* Ý nghĩa khoa học

Đề tài đi sâu nghiên cứu một mảng kỹ thuật khai phá dữ liệu nhằm hỗ

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

trợ cho mục đích sử dụng khác nhau. Có mục đích tìm các nhân tố tích cực, có

x

mục đích tìm các lỗi lưu trữ trong tập dữ liệu, có mục đích tìm kiếm nhận dạng

tội phạm, gian lận tài chính hoặc cũng có thể làm dự báo, phân tích thị trường,....

Trong phạm vi ứng dụng rộng rãi như đã nêu ở trên, việc nghiên cứu các

thuật toán tìm các luật kết hợp phân lớp dựa trên tập mẫu học đã mang ý nghĩa

khoa học và thực tiễn rất lớn. Đề tài thực hiện với hy vọng sẽ đóng góp phần

khoa học nhất định trong việc tổng hợp, đánh giá một nhiệm vụ khai phá dữ

liệu quan trọng nhằm phát hiện những tri thức có ý nghĩa lớn, bảo đảm cơ sở

toán học trong chuyên ngành khoa học máy tính.

* Ý nghĩa thực tiễn

Góp phần chứng tỏ khả năng ứng dụng phong phú của khai phá dữ liệu,

áp dụng trực tiếp vào việc chuẩn đoán bệnh trong các bệnh viện.

Dựa trên việc nghiên cứu một số phương pháp tìm các luật phân lớp trên

tập mẫu học, đã làm rõ và phong phú thêm về thuật toán mới, thuật toán cải

tiến để ứng dụng vào thực tế.

Luận văn có thể được sử dụng làm tài liệu tham khảo cho các sinh viên

đại học, học viên ngành Công nghệ thông tin nghiên cứu về khai phá dữ liệu

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

bằng luật kết hợp phân lớp.

1

CHƯƠNG 1.

PHÂN LỚP VÀ PHƯƠNG PHÁP XÂY DỰNG CÂY PHÂN LỚP THEO

TẬP MẪU HỌC

1.1. Tổng quan về kỹ thuật khai phá dữ liệu

Trong máy tính, thuật ngữ dữ liệu được xem như là các đặc tính được

biết đến mà có thể ghi lại và lưu trữ trên các thiết bị ghi nhớ của máy tính. Dữ

liệu là những mô tả về sự vật, con người và sự kiện trong thế giới thực.

Dữ liệu bao gồm số, ký tự, văn bản, hình ảnh, đồ họa, âm thanh, đoạn

phim,…. Có một số giá trị nào đó đối với người sử dụng và chúng được lưu

trữ, xử lý trong máy tính.

Ví dụ:

- Dữ liệu về khách: tên, địa chỉ, điện thoại, thẻ tín dụng...

- Dữ liệu về xe ô tô của khách: hãng xe, đời xe, năm sản xuất…

- Dữ liệu về nhật ký sử chữa: ngày phục vụ, tên thợ sửa chữa, số tiền

thanh toán…

Trong hoạt động kinh tế xã hội của con người, người ta thường chia ra

hai loại dữ liệu là loại dữ liệu phản ảnh cấu trúc nội bộ của cơ quan (nhân sự,

nhà xưởng, thiết bị,… dữ liệu ít biến động) và loại dữ liệu phản ánh hoạt động

của tổ chức (sản xuất, mua bán, giao dịch,…). Trong doanh nghiệp, không kể

con người và thiết bị, dữ liệu cùng với xử lý là hai thành phần cơ bản của hệ

thống: dữ liệu thường dùng để ghi nhận thực trạng.

1.1.1. Khái niệm về khai phá dữ liệu

Theo bách khoa toàn thư, khai phá dữ liệu (DM) là khâu chủ yếu trong

quá trình phát triển tri thức từ dữ liệu để trợ giúp cho việc làm quyết định trong

quản lý. DM sử dụng nhiều phương pháp của phân tích thống kê, của lý thuyết

nhận dạng, của các hệ học, các mạng nơ-ron nhân tạo… nhắm phát hiện các

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

mẫu hình tri thức trực tiếp từ các kho dữ liệu. DM và phát triển tri thức là những

2

hướng nghiên cứu mới trong tổ chức và khai thác các hệ thống thông tin và trợ

giúp quyết định.

Thuật ngữ DM do Fayyad Smyth và Piatestky-Shapiro đề xuất năm 1989.

Có rất nhiều định nghĩa khác nhau về DM đã được đưa ra. Theo định nghĩa đơn

giản nhất, DM là việc trích lọc tri thức từ một lượng lớn dữ liệu. Nó còn có một

số tên gọi khác như “trích lọc tri thức”, “phân tích dữ liệu/mẫu”, “khảo cổ dữ

liệu”. “nạo vét dữ liệu”,….

Giáo sư Tom Mitchell đã đưa ra định nghĩa về DM như sau: “DM là việc

sử dụng dữ liệu lịch sử để khám phá những quy tắc và cải thiện những quyết

định trong tương lai”. Với cách tiếp cận thực tế hơn, tiến sĩ Fayyad đã phát biểu

: “DM thường được xem là việc khám phá tri thực trong các CSDL, là một quá

trình trích xuất những thông tin ẩn, trước đây chữ biết và có khả năng là hữu

ích dưới dạng các quy luật, ràng buộc, quy tắc trong CSDL”. Các nhà thống kê

thì xem “DM như một quá trình phân tích được thiết kế thăm dò và/hoặc các

mối quan hệ mang tính hệ thống giữa các biến và sau đó sẽ hợp thực hóa các

kết quả tìm được bằng cách áp dụng các mẫu đã phát hiện được cho tập con

mới của dữ liệu”.

Nói chung, DM là cốt lõi của quá trình phát hiện tri thức. Nó gồm có các

giải thuật DM chuyên dùng, một số quy định về hiệu quả tính toán chấp nhận

được. DM nhằm tìm ra những mẫu mới, mẫu có tính chất không tầm thường,

những thông tin tiềm ẩn mang tính dự đoán chưa được biết đến và có khả năng

mang lại lợi ích. Nói gọn hơn, DM là việc tìm kiếm các kiến thức/các mẫu hấp

dẫn trong kho dữ liệu.

DM là hoạt động trọng tâm của quá trình phát hiện tri thức.

1.1.2. Một số phương pháp khai phá dữ liệu hiện đại và thông dụng

Với hai đích chính của khai thác dữ liệu là dự đoán (Prediction) và mô tả

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

(Description), người ta thường sử dụng các phương pháp sau cho khai phá dữ

3

liệu:

- Phân lớp (Classification)

- Hồi quy (Regression)

- Phân nhóm (Clustering)

- Tổng hợp (Summarization)

- Mô hình ràng buộc (Dependency modeling)

- Dò tìm biến đổi và độ lệch (Change and Deviation Dectection)

- Biểu diễn mô hình (Model Representation)

- Kiểm định mô hình (Model Evaluation)

- Phương pháp tìm kiếm (Search Melthod)

1.1.3. Các ứng dụng khai phá dữ liệu

Khai phá dữ liệu (DM) được vận dụng trong nhiều lĩnh vực khác nhau

nhằm khai thác nguồn dữ liệu phong phú được lưu trữ trong các hệ thống thông

tin. Tùy theo bản chất của từng lĩnh vực, việc vận dụng Data mining có những

cách tiếp cận khác nhau.

DM được vận dụng có hiệu quả để giải quyết các bài toán phức tạp trong

những ngành đòi hỏi kĩ thuật cao như: tìm kiếm mỏ dầu từ ảnh viễn thám, xác

định vùng gãy trong ảnh địa chất để dự đoán thiên tai, cảnh báo hỏng hóc trong

các hệ thống sản xuất.

Phân nhóm và dự đoán là những công cụ rất cần thiết cho việc quy hoạch

và phát triển hệ thống quản lý và sản xuất trong thực tế như: dự đoán tái sử

dụng điện năng cho các công ty cung cấp điện, lưu lượng viễn thông cho các

công ty điện thoại, mức độ tiêu thụ sản phẩm cho các nhà sản xuất, giá trị của

sản phẩm trên thị trường cho các công ty tài chính hay phân nhóm khách hàng

tiềm năng.

Ngoài ra DM còn được áp dụng trong việc giải quyết các vấn đề xã hội

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

như: phát hiện tội phạm hay tăng cường an ninh xã hội và mang lại những hiệu

4

quả thiết thực cho các hoạt động trong đời sống hàng ngày. Việc ứng dụng DM

phân theo ngành phân bố trong khoảng 5 năm gần đây với tỷ lệ sau.

* Phân tích dữ liệu gen và sinh học y học

- Trong sinh học, DM dùng để tìm kiếm, so sánh các hệ gen và thông tin

di truyền, tìm mối liên hệ giữa các hệ gen và chuẩn đoán một số bệnh di truyền.

DM đã trở thành một công cụ mạnh và đóng góp thiết thực vào việc phân

tích gen theo các cách sau:

Nghiên cứu tương tự và so sánh các chuỗi gen: Một nghiên cứu quan

trọng trong phân tích gen là nghiên cứu tương tự là so sánh các chuỗi gen. các

chuỗi gen được cô lập từ các mô bệnh khỏe và có thể được so sánh với nhau để

nhận dạng những khác biệt giữa hai lớp gen.

Phân tích kết hợp: Nhận dạng các chuỗi gen cùng xảy ra, phân tích kết

hợp có thể được sử dụng giúp chúng ta xác định các loại gen thường kết hợp

với nhau để gây nên bệnh.

Phân tích hướng đi: Liên kết các gen ở các giai đoạn khác nhau của quá

trình phát triển bệnh, nếu một chuỗi hoạt động của các gen ở những giai đoạn

khác nhau của bệnh được xác định, thì có thể giúp chúng ta chế tạo ra các dược

phẩm can thiệp vào từng giai đoạn của bệnh. Do đó, có thể tạo được cách điều

trị bệnh hiệu quả hơn.

- Trong y học: DM giúp tìm ra mối liên hệ giữa các triệu chứng, chuẩn

đoán bệnh.

* Phân tích dữ liệu tài chính

Trên phương diện tài chính và thị trường chứng khoán, DM dùng để phân

tích tình hình tài chính phân tích đầu tư, phân tích cổ phiếu.

Dữ liệu tài chính nhận được tương đối hoàn chỉnh, đáng tin cậy và chất

lượng cao làm thuận lợi cho việc phân tích dữ liệu, DM một cách hệ thống. Các

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

ứng dụng của DM vào lĩnh vực tài chính như:

5

- Dự đoán trả tiền vay và phân tích chính sách tín dụng khách hàng: Dự

đoán trả tiền vay và phân tích chính sách tín dụng khách hàng là vấn đề quan

trọng đối với việc kinh doanh của ngân hàng. Có nhiều yếu tố (chẳng hạn: tỉ lệ

trả lên thu nhập, mức học vấn, vùng dân cư, lịch sử tín dụng,…) có thể ảnh

hưởng mạnh hoặc yếu đến việc thực hiện trả tiền vay và sự đánh giá mức độ tín

nhiệm khách hàng. Các phương pháp DM như lựa trọn đặc trưng, xếp hạng các

thuộc tính liên quan có thể giúp xác định các yếu tố quan trọng và loại bỏ những

yếu tố không liên quan. Do đó, ngân hàng có thể điều chỉnh chính sách cho vay

đối với những khách hàng mà trước đây ngân hàng đã từ chối nhưng nay tỉ lệ

mạo hiểm đối với họ là thấp dựa vào các phân tích trên.

- Phát hiện các tội phạm tài chính: để phát hiện việc chuyển tiền bất chính

vào ngân hàng và tội phạm tài chính, việc tích hợp thông tin từ các CSDL khác

nhau (CSDL giao dịch ngân hàng, CSDL về lịch sử tội phạm) là rất quan trọng.

Sau khi có dữ liệu tổng hợp chúng ta có thể dựa trên các công cụ của DM để

phát hiện ra mẫu khác thường.

* Dịch vụ bán lẻ

Trong thông tin thương mại: dùng để phân tích dữ liệu người dùng, phân

tích dữ liệu maketing, phân tích đầu tư, phát hiện gian lận.

Dịch vụ bán lẻ là một trong lĩnh vực của DM. Một lượng dữ liệu khổng

lồ đã và đang thu nhập ngày càng tăng, đặc biệt với sự gia tăng về sự tiện lợi,

lợi ích và tính phổ biến của việc kinh doanh trên web, thương mại điện tử. Dữ

liệu bán lẻ cung cấp một kho dữ liệu phong phú cho việc khai phá dữ liệu.

Khai phá dữ liệu bán lẻ có thể giúp chúng ta xác định hành vi mua hàng

của khách hàng, phát hiện những mẫu mua hàng của người dùng, những khuynh

hướng mua hàng.

Thiết kế các chiến dịch kinh doanh: giữ khách hàng – phân tích lòng

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

trung thành của khách hàng: lòng trung thành của khách hàng và khuynh hướng

6

mua hàng có thể được phân tích một cách hệ thống.

* Công nghiệp viễn thông

Trong thông tin kĩ thuật: DM dùng để phân tích các sai hỏng, điều khiển

và lập lịch trình.

Công nghiệp viễn thông đã phát triển nhanh từ các dịch vụ điện thoại cục

bộ và điện thoại đường dài cho đến các dịch vụ truyền thông khác như Voice,

FAX, Image, E-mail, truyền dữ liệu web, các giao lộ dữ liệu khác, tích hợp viễn

thông, mạng máy tính, internet, các phương tiện truyền thông khác đã và đang

thực hiện. Điều này tạo ra một yêu cầu lớn về DM để giúp hiểu thêm việc kinh

doanh, xác định các mẫu viễn thông, chặn đứng các hoạt động lừa dối tạo nhằm

điều kiện sử dụng các tài nguyên tốt hơn và nâng cao được chất lượng dịch vụ.

Về phân tích nhu cầu: dữ liệu viễn thông là các dữ liệu đa chiều đích

thực, với các chiều như: giờ gọi, thời gian gọi, vị trí người gọi, vị trí người được

gọi, kiểu cuộc gọi. Phân tích đa chiều với các dữ liệu kiểu này có thể giúp xác

định nhu cầu và hành vi của các nhóm người dùng từng vùng,… Từ đó cung

cấp các dịch vụ, thiết bị phù hợp hơn.

Về phân tích các mẫu gian lân và xác định các mẫu khác thường: Việc

xác định những người dùng gian lận tiềm năng và những mẫu sử dụng không

điển hình là rất quan trọng. Những mẫu này có thể được khám phá bởi phân

tích đa chiều, phân tích cụm, phân tích phần tử ngoài cuộc.

* Công nghiệp viễn thông

Khai phá dữ liệu được sử dụng rất nhiều để phân tích dữ liệu, hỗ trợ ra

quyết định.

* Khai thác dữ liệu Web

Các trang web nổi tiếng trên thế giới đã làm dịch vụ tìm kiếm cho đông

đảo khách hàng nhờ việc liên kết và sưu tập một khối lượng dữ liệu khổng lồ

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

như Google, Alexa Internet archive, IBM webfountain, Internet Archive,….

7

1.2. Những vấn đề chung nhất về phân lớp và phương pháp phân lớp cơ

bản

1.2.1 Khái niệm phân lớp dữ liệu

- Khái niệm

Phân lớp dữ liệu là một quy trình để tìm ra một tập các mô hình để mô

tả và phân lớp các lớp dữ liệu hoặc khái niệm nhằm mục đích phân loại dữ liệu

hoặc dự đoán lớp của những đối tượng chưa biết.

Việc đưa ra những mô hình phân lớp được dựa trên việc phân tích một

tập mẫu học (Training Data), tức là các đối tượng dữ liệu đã biết trước lớp của

chúng. Trên cơ sở đó rút ra các luật phân lớp. Các luật này sẽ được áp dụng cho

tập dữ liệu có cùng cấu trúc như tập mẫu học.

Chúng ta cũng phân biệt kỹ thuật phân lớp (Data classification) với kỹ

thuật phân cụm dữ liệu (Data Clustering).

Phân cụm dữ liệu (Data Clustering) nhằm mục đích nhóm các đối tượng

trong tập dữ liệu thành các nhóm (hoặc lớp) sao cho các đối tượng trong một

nhóm thì giống nhau về những tiêu thức nào đó và chúng sẽ khác với các đối

tượng trong nhóm khác.

Phân lớp dữ liệu (Data Classification) được dựa trên việc phân tích một

mẫu học đã biết trước nhãn của lớp.

Phân cụm dữ liệu không dựa trên tập mẫu học đã biết mà sử dụng các

phương pháp, mô hình khác nhau và các tiêu thức phân loại để tiến hành phân

nhóm tập dữ liệu. Có nhiều phương pháp được sử dụng cho kỹ thuật phân cụm,

ví dụ: phân cụm dựa trên khoảng cách (Distance – Base Clustering), hoặc phân

cụm dựa trên ràng buộc (Constrain - Base Clustering)…

1.2.2. Các bước tiến hành phân lớp dữ liệu

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Quá trình phân lớp dữ liệu có thể được chia làm các bước như sau:

8

* Bước 1 – Thu thập và tiền xử lý: thu thập tạo bảng mẫu học và xử lý

trước khi đưa vào xây dựng mô hình.

Tập mẫu học là một bảng quan hệ dạng chuẩn, trong đó có một cột là thuộc

tính ghi lại giá trị phân lớp (class-attributes), và các cột khác ghi lại các giá trị

dựa vào đó để phân lớp (non-class attributes).

Tập mẫu học được thu thập hoặc rút ra từ tập dữ liệu thực tế.

Các nội dung tiền xử lý bao gồm:

- Làm sạch dữ liệu (Data cleaning): loại bỏ những tạp nhiễu ảnh hưởng

đến mô hình (có thể dùng các kỹ thuật làm sạch khác nhau)

- Phân tích mức thích hợp của thuộc tính: loại bỏ ra khỏi tập mẫu những

thuộc tính không cần thiết (ví dụ như thuộc tính ngày trong tuần đối với những

ứng dụng không liên quan)

- Chuẩn hóa dữ liệu: nhằm loại bỏ dự bị thường dữ liệu hoặc loại bỏ sự

thừa dữ liệu.

- Chuyển hóa dữ liệu (data transformation): dữ liệu có thể được xử lý tới

mức khái niệm ở mức cao hơn. Ví dụ giá trị thuộc tính thu nhập có được chuyển

về các giá trị cao, thấp, trung bình.

* Bước 2 – Học (Learning): Tập mẫu học được phân tích bằng một

thuật toán phân lớp nó tạo ra một mô hình bao gồm các luật phân lớp.

Trong bước này có thể sử dụng nhiều phương pháp và thuật toán khác

nhau để xây dựng mô hình.

* Bước 3 – Phân lớp: Mô hình được sử dụng cho việc phân lớp. Đầu

tiên cần phải đánh giá độ chính xác của mô hình (bằng một số phương pháp

khác nhau). Nếu độ chính xác của mô hình chấp nhận được thì mô hình sẽ được

sử dụng cho việc phân lớp các đối tượng dữ liệu khác mà chưa biết lớp của

chúng.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

- Đánh giá phương pháp phân lớp

9

Các phương pháp phân lớp có thể được đánh giá theo các tiêu chuẩn sau:

a) Độ chính xác của dự đoán: liên quan đến khả năng dự đoán đúng nhãn

của lớp đối với các đối tượng mới.

b) Tốc độ: liên quan đến các chi phí thời gian, bộ nhớ dùng để sử dụng

mô hình.

c) Phạm vi: liên quan đến việc sử dụng mô hình cho những tập dữ liệu

lớn.

d) Độ dễ hiểu (interpretability): liên quan đến mức độ dễ hiểu của mô hình.

1.2.3. Phân lớp theo cây quyết định

- Mô tả phương pháp

- Đầu vào của quy trình xây dựng cây quyết định phân lớp là một tập

mẫu học (training examples) là một bảng quan hệ dạng chuẩn, gồm có các thuộc

tính C1, C2, C3.... trong đó C1, C2, C3 là các thuộc tính không phân lớp (non-

class), có thể là các kiểu nhị phân (binary), định danh (nomimal), hoặc liên tục

(số nguyên hoặc thực). C là thuộc tính phân lớp (lớp) (ví dụ có thể nhận các giá

trị yes, no hoặc true, false). Các phần tử của tập mẫu học này được phân thành

các lớp tùy thuộc vào giá trị có thể của thuộc tính C.

Cây quyết định phân lớp (gọi tắt là cây quyết định) bao gồm các nút, và

các đường nối giữa các nút biểu diễn quá trình kiểm tra phân lớp theo tập mẫu

học.

Cây phân lớp được dùng để phân loại một tập các phần tử trong một bảng

quan hệ hoặc dùng để dự báo phân lớp đối với một mẫu (example) chưa biết.

Ví dụ: ta có số liệu quan sát về thời tiết cho việc chơi gofl. Tập các mẫu

học T được cho ở bảng dưới đây.

- Thuộc tính phân lớp: PLAY

- Các thuộc tính không phân lớp: OUTLOOK, TEMPERATURE,

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

HUMIDITY, WINDY.

10

Bảng 1.1 Ví dụ về tập mẫu học

OUTLOOK TEMPERATURE HUMIDITY WINDY PLAY

78 FALSE play overcast 83

65 TRUE play overcast 64

90 TRUE play overcast 72

75 FALSE play overcast 81

96 FALSE play rain 70

80 FALSE play rain 68

70 TRUE Don’t play rain 65

80 FALSE play rain 75

80 TRUE Don’t play rain 71

85 FALSE Don’t play sunny 85

90 TRUE Don’t play sunny 80

95 FALSE Don’t play sunny 72

70 FALSE play sunny 69

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

70 TRUE play sunny 75

11

Ta có một cây phân lớp cho việc chơi gofl như trong hình 1.1.

outlook

rain overca

sunn y Humidity

Windy

Play

fals <= true

>7

Play Play

Don’t play Don’t play

Hình 1.1. Cây quyết cho việc chơi gofl

Hình 1.1. Cây quyết định cho việc chơi gofl [13]

Để phân loại cho một mẫu (một phần tử/bản ghi/dòng của bảng dữ liệu)

khi sử dụng cây quyết định, mẫu đó sẽ được di chuyển xuống từ gốc cây tới

một lá nào đó. Tại mỗi nút quyết định, người ta sẽ kiểm tra các giá trị thuộc

tính của mẫu, và mẫu sẽ được đi tiếp theo nhánh ứng với đầu ra kết quả của

pháp kiểm tra. Khi mẫu di chuyển tới một nút lá nó sẽ được phân lớp theo nhãn

của lá.

Có nhiều thuật toán để xây dựng cây quyết định phân lớp. Người ta sẽ

xây dựng cây Quyết định bằng cách chia đệ quy một tập hợp mẫu học (training

set) thành các tập con bằng các phép kiểm tra để phân chia. Một hướng tiếp cận

từ trên xuống dưới, chia để trị được mô tả như sau:

- Nếu tiêu chuẩn kết thúc thỏa mãn, nó sẽ trả về một cây là một lá được

gán nhãn là lớp phổ biến trong các mẫu học tại nút hiện tại.

- Nếu không nó sẽ xây dựng một cây như một nút quyết định bằng việc

tìm một phép kiểm tra mà dựa trên nó một thuộc tính sẽ được coi là tốt nhất

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

cho việc chia tập mẫu học thành các tập con mà mỗi tập sẽ tương ứng với một

12

đầu ta có thể của phép kiểm tra. Đối với mỗi tập con này lại được xây dựng một

cây con với việc sử dụng quy trình như trên.

1.2.4. Phân lớp kiểu Bayes

Các phân lớp kiểu Bayes thuộc loại thống kê. Chúng có thể dự đoán về

khả năng là thành viên của lớp, như xác suất mà một bộ nhận được thuộc về

một lớp nào đó. Cách phân lớp kiểu Bayes dựa trên lý thuyết của Bayes. Các

nghiên cứu khi so sánh các thuật toán phân lớp đã tìm ra một lớp Bayes đơn

giản nổi tiếng như bộ phân loại bình dị (naive) để so sánh trong thực hành với

cây quyết định và bộ phận loại mạng nơ-ron được chọn. Các bộ phận loại Bayes

cũng đạt đọ chính xác và tốc độ cao khi dùng cho CSDL lớn.

Các bộ phận phân loại bình dị thừa nhận rằng sự ảnh hưởng của một giá

trị thuộc tính vào một lớp đã cho là độc lập với các giá trị của các thuộc tính

khác. Giả thiết này được gọi là “độc lập theo điều kiện của lớp”. Nó được tạo

ra để đơn giản tính toán, theo nghĩa này, được gọi là “bình dị”. Các mạng Bayes

là các mô hình đồ họa, không như các bộ phận phân loại Bayes bình dị, cho

phép biểu diễn các phụ thuộc trong tập con các thuộc tính. Các mạng Bayes có

thể được sử dụng phân lớp.

Lý thuyết Bayes được đặt tên sau Thomas Bayes, một tu sỹ người Anh

lập dị, người sớm tìm hiểu lý thuyết quyết định và xác suất ở thế kỷ VIII. Cho

x là một bộ dữ liệu. Theo thuật ngữ Bayes, x được xem là “bằng chứng”. Thông

thường nó được mô tả bằng các bộ đo tạo trên một tập n thuộc tính. Cho H là

một số giả thiết, chẳng hạn như là bộ dữ liệu x thuộc về lớp C. Đối với các vấn

đề về phân lớp, chúng ta muốn xác định P(H/X), xác suất mà giả thiết H gán

cho “bằng chứng” hoặc bộ dữ liệu X thuộc vào lớp C, dựa vào đó chúng ta biết

về mô tả thuộc tính của X.

P(H/X) là xác suất của H điều kiện X. Ví dụ, giả sử bộ dữ liệu được hạn

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

chế trong phạm vi các khách hàng đã mô tả với các thuộc tính tuổi và thu nhập,

13

X là khách 35 tuổi có thu nhập 40.000$. Giả sử H là giả thiết khách hàng sẽ

mua một máy tính. Lúc đó P(H/X) là xác suất mà khách hàng X sẽ mua một

máy tính dựa trên việc chúng ta đã biết tuổi và thu nhập của khách hàng.

Trái lại, P(H) là tiền xác suất của H. Đối với ví dụ của chúng ta, đây là

xác suất mà một khách nào đã cho nào đó sẽ mua một máy tính, không quan

tâm đến tuổi và thu nhập hoặc một thông tin nào khác. Hậu xác suất P(H/X)

dựa trên nhiều thông tin hơn (ví dụ như thông tin về khách hàng) so với thông

tin tiền xác suất P(H). P(H/X) độc lập với X.

Tương tự, P(X/H) là hậu xác suất của X xác định điều kiện trên H. Đó là

xác suất mà khách hàng X có tuổi 35 thu nhập 40.000$ sẽ mua một máy tính.

P(X) là tiền xác suất của X. Trong ví dụ của chúng ta, đó là xác suất mà

một người trong tập khách hàng của chúng ta có tuổi 35 và thu nhập 40.000$.

Việc ước lượng xác suất này như thế nào? P(H), P(X/H) và P(X) có thể

được ước lượng từ dữ liệu đưa ra. Lý thuyết của Bayes là có ích. Nó cung cấp

một cách tính hậu xác suất P(H/X) từ P(X), P(X/H) và P(X):

P ( 𝑃( ) = 𝐻 𝑋 X H) P(H) 𝑃(𝑋)

1.2.5. Phân lớp dựa trên các quy tắc IF-THEN

Chúng ta nghiên cứu các cách phân loại dựa trên quy tắc ở nơi các mô

hình học được trình diễn bằng một tập quy tắc IF-THEN. Trước hết chúng ta

xem các quy tắc nào được dùng để phân loại. Sau đó chúng ta xét các cách có

thể phát sinh hoặc từ cây quyết định hoặc trực tiếp từ dữ liệu huấn luyện nhờ

việc sử dụng một thuật toán “phủ thường xuyên”.

Các quy tắc là một phương pháp tốt để trình diễn thông tin hoặc một

lượng tri thức. Một bộ phân loại dựa trên quy tắc sử dụng một tập các quy tắc

IF-THEN để phân loại. Một quy tắc IF-THEN là một biểu diễn dạng:

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

IF điều kiện THEN kết luận

14

Ví dụ:

R1: IF tuổi = trẻ AND sinhvien = yes THEN muamaytinh = yes

Sau IF là tiền điều kiện bao gồ nhiều hơn một kiểm thử giá trị thuộc tính,

sau THEN là kết quả. Kết quả chứa một lớp dự đoán (ví dụ lớp khách sẽ mua

máy tính).

Ta có thể viết khác:

R1: (tuổi = trẻ)^(sinhvien = yes) -> (muamaytinh = yes)

Nếu điều kiện (tất cả các thuộc tính test) trong vế trái quy tắc đúng đối

với bộ dữ liệu, ta nói chúng thỏa mãn (hay nói đơn giản là quy tắc đó thỏa mãn

điều kiện trái) và nói rằng quy tắc đó phủ bộ đó.

Cho bộ X, từ tập dữ liệu đã phân lớp có nhãn, gọi nphủ là số các bộ được

phủ bởi quy tắc R, gọi nđúng là số các bộ thỏa mãn đúng quy tắc R, còn /D/ là số

các bộ trong D. Chúng ta có thể xác định độ phủ và độ đúng của quy tắc R như

sau:

nphủ /D /

Độ phủ (R) =

ndúng nphủ

Độ đúng (R) =

Nghĩa là độ phủ của quy tắc là tỷ lệ của các bộ mà được phủ bởi quy tắc

trên tổng số các bộ dữ liệu. Còn độ đúng của quy tắc là tỷ lệ các bộ đúng trên

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

tổng các bộ được phủ bởi quy tắc.

15

Bảng 1.2: Các bộ huấn luyện đã được phân lớp trong CSDL

Class: buys credit- RID age income student computer rating

fair youth high No no 1

excellent youth high No no 2

middle high No fair yes 3 aged

senior medium No fair yes 4

senior fair low Yes yes 5

senior low Yes excllent no 6

middle low yes excllent yes 7 aged

fair youth medium no no 8

fair youth low yes yes 9

fair senior medium yes yes 10

yes youth medium excellent yes 11

middle medium no excellent yes 12 aged

middle high yes fair yes 13 aged

senior medium no excellent no 14

Xét quy tắc R1 trên, có 2 bộ (bộ thứ 9 và thứ 11) được phủ trong 14 bộ.

Trong 2 bộ phủ đó, tất cả đều đúng. Vậy độ phủ (R1) = 2/14 = 14,28%, còn độ

đúng = 2/2 = 100%.

Ngoài quy tắc IF-THEN, người ta còn sử dụng nhiều quy tắc khác nữa

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

như quy tắc trích rút từ một cây quyết định, quy tắc quy nạp nhờ sử dụng thuật

16

toán phủ theo dãy,…

1.2.6. Phân lớp dựa trên luật kết hợp

Các mẫu thường xuyên và các quy tắc tương quan hoặc kết hợp tương

ứng của chúng đặc trưng cho các mối quan hệ thú vị giữa các thuộc tính điều

kiện và các nhãn của lớp, do vậy chúng được dùng để phân lớp rất hiệu quả.

Các luật kết hợp chỉ ra các kết hợp mạnh giữa các cặp giá trị thuộc tính (hoặc

các chỉ mục) mà xảy ra thường xuyên trong tập dữ liệu cho trước. Các luật kết

hợp được dùng rộng rãi để phân tích các mẫu mua sắm của khách hàng trong

một cửa hiệu. Chẳng hạn việc phân tích có lợi trong nhiều quyết định – thực

hiện xử lý, như là vị trí sản phẩm, thiết kế catalog và quảng cáo khuếch trương.

Việc phát hiện ra luật kết hợp dựa trên việc khai phá tập mục thường xuyên. ở

đây, chúng ta tìm hiểu sâu về việc phân lớp kết hợp, nơi mà các luật kết hợp

được phát sinh và được phân tích phục vụ mục đích phân loại. Ý tưởng chung

là chúng ta có thể tìm kiếm các kết hợp mạnh giữa các mẫu thường xuyên (các

kết hợp của các cặp giá trị thuộc tính) và các nhãn lớp. Vì các luật kết hợp khai

thác các kết hợp có độ tin cậy cao trong số nhiều thuộc tính tại một thời điểm.

Trong nhiều trường hợp, việc phân loại theo kết hợp đã được tìm là chính xác

hơn một số phương pháp phân loại truyền thống, như thuật toán C4.5… Chúng

ta sẽ xem xét 3 phương pháp chính là CBA, cmAR, và CPAR.

Trước hết chúng ta nhắc lại việc khai phá theo luật kết hợp nói chung.

Các luật kết hợp được khai phá theo tiến trình 2 bước bao gồm khai phá tập

mục thường xuyên sau đó là việc sinh luật:

- Bước thứ nhất, tìm các mẫu của các cặp giá trị thuộc tính mà xảy ra lặp

đi lặp lại trong tập dữ liệu, nơi mà mỗi cặp giá trị thuộc tính được xem như một

chỉ mục. Các cặp giá trị thuộc tính kết quả có dạng các tập chỉ mục thường

xuyên.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

- Bước thứ hai, phân tích các tập chỉ mục thường xuyên để sinh luật kết

17

hợp. Tất cả các luật kết hợp phải thỏa mãn một số tiêu chuẩn “chính xác” (độ

tin cậy) và tỷ lệ có mặt trên dữ liệu (độ ủng hộ).

Gọi D là tập dữ liệu, mỗi bộ trong D có n là thuộc tính A1,A2,…,An và

một thuộc tính nhãn lớp Aclass. Tất cả các thuộc tính liên tục được rời rạc hóa

và được coi là thuộc tính chủng loại. Một chỉ mục p là một cặp giá trị thuộc

tính có dạng (Ai, ), ở đây: A1 là một thuộc tính nhận giá trị . Một bộ dữ liệu

X = (x1,x2,…,xn) thỏa mãn một chỉ mục p =( Ai, ) nếu và chỉ nếu xi, = , với

xi là giá trị thứ I của X. Luật kết hợp có thể có một số chỉ mục điều kiện và một

số chỉ mục kết quả. Chúng ta quan tâm đến các luật khai phá với luật kết hợp

có dạng p1^p2^…^pk => Aclass = C, với k=1,…,n. Luật R đưa ra là tỷ lệ các bộ

phận trong D có khả năng thỏa mãn các chỉ mục điều kiện và có nhãn lớp C

được gọi là độ tin cậy của D.

Ví dụ:

Luật kết hợp R: tuổi = trẻ AND tín dụng = OK => mua máy tính = yes

[ độ ủng hộ 20%, độ tin cậy 93%] nghĩa là 93% khách hàng trong D là trẻ và

có thẻ tín dụng (OK) có khả năng thuộc lớp có mua máy tính (nhãn lớp C). Tỷ

lệ các bộ trong D thỏa mãn điều kiện:

tuổi = trẻ AND tín dụng = OK mà có nhãn lớp là C

được gọi là ủng hộ của R, nghĩa là 20% khách hàng trong D là trẻ, có thẻ tín

dụng và có mua máy tính.

Một trong những thuật toán sớm nhất và đơn giản nhất để phân loại theo

luật kế hợp là CBA (Classification-Based Associon). CBA sử dụng một cách

tiếp cận lặp tới việc khai phá tập mục thường xuyên, tương tự như mô tả đối

với thuật toán Apriori. Tập các luật cuối cùng thỏa mãn ngưỡng cực tiểu độ tin

cậy và cực tiểu độ ủng hộ được tìm và được kết luận để kết luận trong bộ phân

loại. CBA sử dụng một phương pháp tự khám để cấu trúc bộ phân loại xếp

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

quyền ưu tiên theo thứ tự giảm dần dựa trên độ ủng hộ và tin cậy của chúng.

18

Nói chung CBA được tìm theo kinh nghiệm và chính xác hơn thuật toán C4.5.

CMAR (Classification based on Multiple Asociation Rule) khác CBA về

mặt chiến thuật khai phá tập thường xuyên và cách xây dựng bộ phân lớp.

CMAR chấp nhận một phương án của thuật toán FP-growth để tìm tập các luật

cuối cùng thỏa mãn các ngưỡng tối thiểu về độ tin cậy và độ ủng hộ. FP-growth

sử dụng một cấu trúc cây được gọi là FP- cây để đăng ký tất cả các thông tin

của tập chỉ mục thường xuyên chứa đựng trong tập dữ liệu đã cho D. Các tập

mục thường xuyên được khai phá từ FP- cây. CMAR sử dụng một FP- cây nổi

bật nhằm duy trì phân bố các nhóm lớp trong số các bộ thỏa mãn mỗi tập thường

xuyên. Theo cách này, cho phép sinh ra các luật tổ hợp cùng với việc khai phá

tập mục thường xuyên trong một bước đơn.

CBA và CMAR chấp nhận các phương pháp khai phá tập mục thường

xuyên để sinh ra các luật kết hợp ứng viên bao gồm tất cả các kết hợp các cặp

(các tập mục) giá tri thuộc tính thỏa mãn cực tiểu độ ủng hộ. Các luật này sau

đó được kiểm tra và một tập con của nó được chọn để trình diễn bộ phân loại.

Tuy nhiên các phương pháp như thế sẽ sinh ra một lượng lớn các luật.

Tiếp cận theo các cách để sinh luật (CPAR – Classification base on

Predictive Asociation Rules ) dựa trên một thuật toán phân lớp nổi tiếng như

FOLL (First Order Inductive Learner). FOLL xây dựng các quy tắc để phân

biệt các bộ chính diện (mua máy tính = yes) từ các bộ phản diện (mua máy tính

= no). Đối với đa lớp, FOLL được áp dụng cho từng lớp.

1.2.7. Phân lớp dựa vào K-lân cận gần nhất

Phương pháp k- lân cận gần nhất dựa trên cách học tương tự. Các mẫu

học được mô tả bằng các thuộc tính số n – chiều. Mỗi mẫu được xem như một

điểm trong không gian n – chiều. Bằng cách này tất cả các mẫu học được lưu

trong không gian mẫu n – chiều. Đối với một mẫu chưa biết lớp, mô hình sẽ

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

tìm một tập mẫu gồm k mẫu học mà gần mẫu chưa biết nhất. Khái niệm gần ở

19

đây được định nghĩa theo thuật ngữ khoảng cách Ơclit.

Khoảng cách Ơclit giữa 2 điểm X = (x1, x2, …, xn) và Y = (y1, y2, …, yn)

𝑛 d(X,Y) = √∑ (𝑥𝑖 − yi)2 𝑖=1

được định nghĩa:

Mẫu chưa biết sẽ được gán cho lớp phổ biến nhất trong tập lân cận này.

Có thể tham khảo và xem thuật toán của phương pháp này trong các công trình

Duda and Hart, James.

1.2.8. Phân lớp dựa vào giải thuật di truyền

Các thuật toán di truyền cố gắng hợp nhất các ý tưởng tiến hóa tự nhiên.

Đại thể, quá trình phân loại theo di truyền như sau. Một quần thể khởi tạo được

tạo ra bao gồm các luật được sinh ra tự nhiên. Mỗi luật được biểu diễn bằng

một các chuỗi bit. Ví dụ đơn giản như sau: giả sử rằng các mẫu trông một tập

huấn luyện cho trước được mô tả bởi 2 thuộc tính Boolean A1 và A2, hai lớp

C1 và C2. Quy tắc “IF A1 AND NOT A2 THEN C2” có thể mã hóa bằng chuỗi

bit “100” , ở đây 2 bit đầu biểu diễn thuộc tính A1 và A2, bit bên phải biểu diễn

lớp (0). Tương tự quy tắc “IF NOT A1 AND NOT A2 THEN C1” có thể mã

hóa bằng “001”. Nếu một thuộc tính có k giá trị, với k > 2, thì k bit có thể được

sử dụng để mã hóa các giá trị của thuộc tính đó. Các lớp có thể cũng được mã

hóa ở dạng tương tự.

Dựa trên khái niệm “sống sót” của phần tử thích hợp nhất, một quần thể

mới được hình thành bao gồm các quy tắc hợp nhất trong quần thể hiện tại là

hậu thế của các quy tắc này. Điển hình là các phần tử thích nghi của một quy

tắc được đánh giá bởi tính chính xác phân loại của nó trên một tập mẫu huấn

luyện.

“Hậu thế” được tạo bằng áp dụng các toán tử di truyền như chuyển đổi

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

và đột biến. Trong chuyển đổi, các dãy con từ các cặp các quy tắc được đổi

20

thành dạng cặp các quy tắc mới. Trong đột biến, các bit được chọn ngẫu nhiên

trong các chuỗi của quy tắc được đảo ngược.

Các quá trình sinh ra các quần thể mới dựa trên cá quần thể ưu tiên của các

quy tắc liên tục cho đến khi một quần thể P tiến hóa, ở đây mỗi quy tắc trong P

thỏa mãn một ngưỡng thích hợp đã mô tả.

Các thuật toán di truyền xử lý dữ liệu đồng bộ và sử dụng để phân loại

gống như các bài toán tối ưu. Trong khai phá dữ liệu, chúng ta có thể được dùng

để ước lượng sự thích hợp của thuật toán khác.

1.2.9. Phân lớp theo cách tiếp cận tập thô

Lý thuyết tập thô có thể được sử dụng để phân loại khám phá các mối quan

hệ có ý nghĩa cấu trúc với dữ liệu mơ hồ và hỗn loạn. Nó dùng với các thuộc

tính có giá trị rời rạc. Các thuộc tính có giá trị liên tục do vậy phải được rời rạc

hóa trước khi sử dụng.

Lý thuyết tập thô được dựa trên việc thành lập các lớp tương đương trong

giới hạn dữ liệu huấn luyện cho trước. Tất cả các bộ dữ liệu hình thành một lớp

tương đương là không phân biệt được. Nghĩa là, các mẫu là đồng nhất đối với

thuộc tính mô tả trong dữ liệu. Một số lớp không thể phân biệt được theo nghĩa

các thuộc tính có thể chấp nhận. Các tập thô có thể được dùng để xấp xỉ hoặc

xác định các lớp “thô”. Một tập thô được xác định trên lớp C được xấp xỉ bằng

2 tập – một xấp xỉ dưới của C và một xấp xỉ trên của C. Tập xấp xỉ dưới của C

gồm tất cả các bộ dữ liệu chắc chắn nằm trong C. Tập xấp xỉ trên của C gồm

tất cả các bộ không nói rõ là không thuộc C. Hai tập này được minh họa như

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

hình dưới đây

21

Hình 1.2: Một tập thô xấp xỉ tập các bộ của C khi dùng các tập xấp xỉ trên và

dưới của C. Các vùng hình chũ nhật biểu diễn các lớp tương đương [6]

Các tập thô cũng có thể được sử dụng để lựa chọn các tập con thuộc tính

(loại bỏ các thuộc tính không có ích cho việc phân loại) và phân tích. Vấn đề là

tìm các tập con cực tiểu các thuộc tính mà có thể mô tả đầy đủ các khái niệm

trong tập dữ liệu. Tuy nhiên các thuật toán giảm cường độ tính toán đã được đề

xuất. Có một phương pháp, ví dụ như, một mạ trận nhận dạng được dùng để

lưu sự khác biệt giữa các giá trị thuộc tính đối với mỗi cặp các bộ dữ liệu. Ngoài

tập huấn luyện, người ta nghiên cứu nhiều hơn ma trận này để khám phá các

thuộc tính dư thừa.

1.2.10. Phân lớp theo cách tiếp cận tập mờ

Các hệ thống dựa trên luật để phân lớp có bất lợi đối với các thuộc tính

liên tục. Ví dụ, xét quy tắc sau đối với sự chấp thuận sử dụng thẻ tín dụng của

khách hàng:

IF(năm công tác>=2) AND (thu nhập>=50000)

THEN thẻ tín dụng = được dùng

Theo quy tắc này, một khách hàng đã làm việc ít nhất 2 năm sẽ nhận thẻ

tín dụng nếu thu nhập chỉ là 49000. Một ngưỡng cứng nhắc như thế dường như

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

không ổn. Chúng ta có thể rời rạc hóa thu nhập theo chủng loại như {thu nhập

22

thấp, trung bình, cao}, sau đó sử dụng lý thuyết mờ với ngưỡng hoặc là các

biên “mờ” để phân loại.

Mỗi loại biểu diễn một tâp mờ. Chú ý rằng một giá trị thu nhập x có thể

có thành viên trong nhiều hơn một tập mờ. Các giá trị thành viên của x trong

mỗi tập mờ không nhất thiết có tổng bằng 1.

Hình 1.3: Các giá trị mờ thật với thu nhập, biểu diễn mức thành viên các giá

trị thu nhập theo các loại {thấp, trung bình, cao [6]

Theo hình trên, thu nhập trên hay dưới 49.000 là thuộc loại cao, mặc dù

chưa cao bằng 50.000. Các hệ thống logic mờ cung cấp các đồ họa điển hình

để yêu cầu thông tin NSD cho các giá trị thuộc tính chuyển đổi để mờ hóa các

giá trị thật.

Lý thuyết tập mờ cũng được biết như lý thuyết xác suất. Nó được đề xuất

bởi Lotfi Zadeh năm 1965 như một sự lựa chọn thay thế nhau giữa 2 lý thuyết

truyền thống là xác suất và logic. Chúng cho chúng ta mức trừu tượng cao và

cách giải quyết vừa phải có độ đo chính xác của dữ liệu. Điều quan trọng nhất,

lý thuyết tập mờ cho phép chúng ta giải quyết các yếu tố không chính xác và

mơ hồ (48.000 hay 49.000). Không giống như khái niệm tập “rõ”, trong lý

thuyết “mờ” các phần tử có thể thuộc vào nhiều hơn một tập mờ. Ví dụ, thu

nhập 49000 thuộc trong 2 tập trung bình và cao nhưng ở mức độ khác nhau.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Khi sử dụng ký hiệu của lý thuyết mờ chúng ta có:

23

mthu nhập trung bình(49.000) = 0,15 và m thu nhập cao(49.000) = 0,96

Ở đây m kí hiệu cho hàm thành viên, hoạt động trên tập mờ về thu nhập

(trung bình hay cao). Trong lý thuyết mờ, các giá trị thành viên trong mỗi phần

tử x (ví dụ như là 49.000) có tổng không bằng 1. Điều này không giống như lý

thuyết xác suất (rằng buộc theo một tiên đề về tổng).

Lý thuyết tập mờ có ích cho các hệ thống khai phá dữ liệu khi thực hiện

phân lớp dựa trên các luật. Nó cung cấp các toán tử/thao tác để tổ hợp các độ

đo mờ. Giả thiết rằng, bổ sung vào trong tập mờ đối với thu nhập, chúng ta xác

định các tập mờ người lao động ít tuổi hơn, người nhiều tuổi hơn cho thuộc tính

năm công tác. Giả sử chúng ta có môt quy tắc, thử nhiệm thu nhập cao, người

nhiều tuổi trong phần IF của quy tắc. Nếu hai độ đo mờ này là AND cùng nhau

thì cực tiểu độ đo của chúng được lấy là độ đo của quy tắc. Nói khác đi:

m(thu nhập cao AND người cao tuổi)(x) = min(mthu nhập cao(x),mngười cao tuổi(x))

Có thể nói đây là mắt xích một liên kết mạnh, một liên kết yếu. nếu 2 độ

đo là OR thì cực đại độ đo của chúng được chọn là độ đo của quy tắc, nghĩa là:

m(thu nhập cao OR người cao tuổi)(x) = max(mthu nhập cao(x),mngười cao tuổi(x))

Bằng trực giác, ta nói rằng xâu mạnh, một xâu mạnh nhất.

Cho một bộ để phân loại, có hơn 1 quy tắc có thể dùng. Mỗi quy tắc áp

dụng góp phần gợi ý hành viên trong các loại đó. Một cách điển hình, các giá

trị đúng đối với chủng loại dự đoán là được lấy tổng, và các tổng này được tổ

hợp.

Các hệ thống logic mờ đã được dùng trong nhiều lĩnh vực để phân loại,

bao gồm nghiên cứu thị trường, tài chính, chăm sóc sức khỏe, và kỹ nghệ môi

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

trường.

24

1.3. Khái niệm về tập mẫu học và phương pháp xây dựng cây phân lớp

1.3.1. Định nghĩa tập mẫu học

Một tập mẫu học (training examples) là một bảng quan hệ dạng chuẩn,

gồm có các thuộc tính C1, C2…Cm, C trong đó C1, C2…Cm là các thuộc tính

không phân lớp (non-class), có thể là các kiểu nhị phân (binary), định danh

(nomimal), hoặc liên tục (số nguyên hoặc thực). C là thuộc tính phân lớp (lớp)

(ví dụ có thể nhận các giá trị yes, no hoặc true, false). Các phần tử của tập mẫu

học này được phân thành các lớp tùy thuộc vào giá trị có thể của thuộc tính C.

1.3.2. Xây dựng cây phân lớp dựa theo Khóa

Phương pháp phân lớp bằng cây quyết định ID3 và C4.5 được coi là hai

phương pháp điển hình. Các thuật toán này thường có những hạn chế đó là phân

mảnh tạo ra việc cần phân chia dữ liệu nhiều lần để bắt được tất cả các mẫu

học(training examples). Việc phân chia lặp này làm giảm mất tính tổng quát

của chúng đồng thời có thể làm bất lợi cho độ chính xác của việc phân lớp. Vấn

đề lặp tạo nên việc một phân chia của cây con được cấu trúc nhiều lần và dẫn

đến cây sẽ sâu hơn và khó hiểu được hơn. Đặc biệt với số các thuộc tính lớn và

số bản ghi của tập mẫu học là lớn thì thường sẽ tạo ra cây phân lớp có kích

thước và độ sâu lớn dẫn đến thời gian phân loại lâu hơn và cây khó hiểu hơn.

Phần trình bày dưới đây, luận văn sẽ trình bày thêm một phương pháp

mở rộng, đó là phương pháp xây dựng cây phân lớp dựa trên khóa của mẫu học.

Giả sử D là tập mẫu học (Training set) là một quan hệ trên lược đồ R(A1,

A2,…Am,C), trong đó A1,A2…Am là các thuộc tính không phân lớp của D.

Không mất tính tổng quát, giả sử khóa K={A1,A2..As}, tất nhiên s ≤ m.

Ta xét tập mẫu học Dk mới được xây dựng từ D bằng cách chiếu D lên

KC, có nghĩa là Dk sẽ chỉ gồm các bản ghi có các giá trị thuộc tính là các khóa

và giá trị thuộc tính phân lớp C. Hay nói cách khác Dk là một quan hệ trên lược

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

đồ Rk(A1,A2..As,C).

25

Gọi T là cây phân lớp với tập mẫu học là Dk.

Mệnh đề 3.1. Cây phân lớp T được xây dựng trên tập mẫu học khóa Dk phân

lớp chính xác Dk thì cũng phân lớp chính xác tập mẫu học D.

Chứng minh

Trước hết ta cũng dễ thấy rằng k là khóa của D thì K cũng là khóa của

Dk. Thật vậy do KC R, vì vậy nếu K → R trên D thì K → Rk trên Dk và nếu

K là tối tiểu trên D thì K cũng tối tiểu trên Dk.

Giả sử với một mẫu học bất kì t’ Dk được T phân chính xác vào lớp c’

 C.

Xét một mẫu học t  D tương ứng với t’ (có nghĩa là t và t’ trùng nhau

trên A1,A2,..As). Áp dụng phân lớp bằng T đối với t. Giả sử t được phân vào

lớp c  C, khi đó c’=c vì do K là khóa trên D nên K xác định duy nhất một bản

ghi tD. Hay nói một cách khác trên D chỉ có duy nhất một bản ghi có giá trị

trùng với t’ và giá trị c phải trùng với c’. Hay nói một cách khác nếu T phân t’

vào lớp c’ thì T cũng phân t vào lớp c’.

Mệnh đề được chứng minh.

Do số thuộc tính của Rk ít hơn hoặc cùng lắm là bằng số thuộc tính của

R nên số lượng tính toán để xây dựng cây phân lớp trên Dk là nhỏ hơn số lượng

tính toán để xây dựng cây quyết định trên D, đặc biệt khi khóa K được chọn là

có ít phần tử.

Từ đây, chúng ta có thể thực hiện thuật toán xây dựng cây phân lớp với

cải tiến sau:

Thuật toán 15 (Xây dựng cây quyết định dựa theo khóa)

Bước 1: Xác định khóa K của tập mẫu học D (giả sử C là thuộc tính phân

lớp). Trong các khóa tìm được ta chọn khóa tối tiểu có ít phần tử nhất thì tốt.

Bước 2: Áp dụng thuật toán xây dựng cây phân lớp trên tập mẫu học KC.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Thuật toán xác định khóa K của tập mẫu học D được trình bày trong [[3]. Lê

26

Văn Phùng (2018), CSDL quan hệ].

Ví dụ:

Xét tập mẫu học sau, trong đó I là thuộc tính phân lớp.

Ta có một khóa của tập mẫu học là: {A,B}

Bảng 1.3: Ví dụ tập mẫu học được phân lớp dựa theo khóa [8]

B A C D E F K I

1 1 2 1 1 2 0 Y

2 1 1 1 1 2 I Y

1 3 1 0 2 1 1 N

4 1 2 0 1 1 1 N

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

1 2 1 0 1 1 1 Y

27

Có thể xây dựng 2 cây phân lớp như trong hình dưới đây.

T1

E

T2

A

2

3

1

N N 1 F

2

2

1

B D Y Y

1,2

4

C

2

1

Y N N

0 Y a) Cây phân lớp được xây dựng b) Cây phân lớp được xây dựng

không dựa theo khóa dựa theo khóa {A,B}

Hình 1.4: Cây phân lớp xây dựng với 2 trường hợp

a) không dựa theo khóa b) có dựa theo khóa

Chúng ta nhận thấy cây T1 được xây dựng không dựa trên các thuộc tính

khóa (trường hợp a), có độ sâu hơn so với cây T2 được xây dựng từ thuộc tính

khóa (trường hợp b).

1.3.3. Xây dựng cây phân lớp nhờ các luật kết hợp phân lớp (Class

Association Rules) trong bảng mẫu học

Giả sử D là tập dữ liệu mẫu học. Ta gọi một cặp giá trị (thuộc tính, giá

trị) là một khoản mục.

Gọi I là tập các khoản mục trong D, Y là tập các nhãn của lớp. Chúng ta

nói rằng một trường hợp d ∈ D chứa một tập con X của I (X ⊆ I), nếu X ⊆ d.

Một luật kết hợp lớp (CAR) là một phép kéo theo dạng X → y, ở đây X ⊆ I, y

∈ Y. Một luật X → y đúng trên D với độ chắc chắn là c nếu c% các trường hợp

của D chứa X thì cũng chứa nhãn lớp y.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

c% = (số trường hợp chứa (X ∪ y))/ (Số trường hợp chứa X)*100

28

Luật X → y có số hỗ trợ là s trên D nếu s% các trường hợp của D có chứa

X và được gán với nhãn lớp y

s% = số trường hợp chứa (X ∪ y)/ |D| * 100

Với mỗi số Minsup cho trước, nếu luật thỏa mãn: c ≥ Minsup thì gọi nó

là luật phổ biến (frequent rule item).

Với mỗi số Minconf cho trước, nếu luật thỏa mãn s ≥ Minconf thì gọi

nó là luật chính xác.

Để thuận tiện ta lưu ý (X ∪ y) có thể viết là: X.y.

Giả sử Y = {y1, y2, …, ym} là tập các nhãn của lớp.

Ví dụ < (A,1), (B,1), (class,1) > với A, B là các thuộc tính. Nếu số đếm

hỗ trợ của condset {(A,1), (B,1)} là 3, số hỗ trợ của mục luật là 2 và tổng số

các trường hợp của D là 10 thì khi đó ta có: số hỗ trợ mục luật là 20%, và hệ số

chắc chắn là 66,7%. Nếu minsup = 10% thì mục luật thỏa mãn tiêu chuẩn

minsup, ta gọi là phổ biến.

Đối với tất cả các mục luật mà có cùng condset, mục luật nào có hệ số

chắc chắn cao nhất sẽ được chọn là luật có thể (possible rule-PR) biểu diễn tập

hợp các mục luật này. Nếu có nhiều hơn một mục luật với cùng độ chắc chắn

cao nhất, chúng ta sẽ chọn ngẫu nhiên 1 mục luật. Ví dụ, chúng ta có 2 mục

luật có cùng condset:

1. {(A, 1), (B, 1), (class, 1)>

2. {(A, 1), (B, 1), (class, 2)>

Giả sử rằng số hỗ trợ của condset là 3. Số hỗ trợ của mục luật 1 là 2 và

mục luật thứ hai là 1. Khi đó hệ số chắc chắn của mục luật 1 là 66,7% trong khi

đó hệ số chắc chắn của mục luật thứ hai là 33,3%. Nếu chúng ta chỉ chọn các

mục luật có hệ số chắn chắn >60% thì khi đó ta chỉ chọn mục luật sau:

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

(A,1), (B,1) → (class,1) (supt = 20% và confd = 66,7%)

29

CHƯƠNG 2.

MỘT SỐ PHƯƠNG PHÁP TÌM CÁC LUẬT KẾT HỢP PHÂN LỚP

TRÊN TẬP MẪU HỌC

2.1. Phương pháp phân lớp dựa trên luật kết hợp

2.1.1. Các bước tiến hành phân lớp dựa trên luật kết hợp

Phương pháp phân lớp dựa trên luật kết hợp có 3 bước sau:

a) Tìm tất cả các luật phân lớp CAR vừa chính xác, vừa phổ biến.

b) Xây dựng mô hình phân lớp dựa vào phương pháp oristic. Ở đây các

mục luật được sắp xếp theo thứ tự tăng dần của kích thước về trái mục luật và

ưu tiên theo hệ số phổ biến hệ số chắc chắn. Thuật toán được xây dựng có thể

phải duyệt qua tập dữ liệu một vài lần tùy theo độ dài nhất của các mục luật tìm

được.

c) Thực hiện việc phân lớp theo mô hình đưa ra. Để phân lớp một mẫu X

(chưa biết lớp), trước hết luật nào thỏa mãn X (X chứa nó) thì sẽ được dùng để

phân lớp X. Nếu có nhiều luật cùng thỏa mãn thì sẽ ưu tiên theo độ chắc chắn

và độ phổ biến.

2.1.2. Tạo luật kết hợp bằng cây quyết định

Tri thức được biểu diễn trong cây quyết định có thể được trích rút và biểu

diễn bằng các luật kết hợp dạng IF – THEN.

Một luật có thể được tạo thành từ mỗi con đường đi từ gốc đến lá của cây.

Mỗi một cây (thuộc tính, giá trị) trên đường sẽ là một thành phần trong luật. Ví

dụ xét cây quyết định được mô tả ở Hình 1.3. Ta có thể biểu diễn các luật như:

IF OUTLOOK = sunny And HUMIDITY > 75 THEN PLAY = don’play

IF OUTLOOK = overcast THEN PLAY = play

Việc biểu diễn ở dạng luật kết hợp như ở trên làm cho người dùng dễ

hiểu và đặc biệt có ích khi cây quyết định được xây dựng là rất lớn.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

2.2. Một số thuật toán cổ điển xây dựng cây phân lớp dựa trên luật kết hợp

30

Các thuật toán xây dựng cây phân lớp dựa trên luật kết hợp phân lớp CBA-

RG và CBA-CB được Liu, Hsu and Ma giới thiệu vào năm 1998 [7] cũng gần

giống với phương pháp xây dựng cây phân lớp dựa trên phụ thuộc hàm lớp

(CFD) xấp xỉ được Kwok-Wa Lam, Victor C. S. Lee giới thiệu vào năm 2004

[8] Các phương pháp mới này khác với các phương pháp truyền thống ở chỗ sẽ

đi tìm các “thuộc tính hợp”, cho các nút của cây quyết định (một nút có nhiều

hơn một thuộc tính) dẫn đến việc làm cho cây nhỏ hơn và dễ hiểu hơn và không

ngăn cản hiệu quả của độ chính xác. Với các thuộc tính hợp cho các nút của

cây, có thể vượt qua các hạn chế của việc xây dựng cây quyết định.

Thuật toán phân lớp sử dụng luật kết hợp và cây quyết định nêu trên dựa

trên nền tảng thuật toán của luật phổ biến trong bảng quan hệ. Độ phức tạp tính

toán của các thuật toán này là O(m2 .n) (với m là số phần tử của tập dữ liệu, n

– là số thuộc tính). Công đoạn tính toán chủ yếu tập trung vào việc phát hiện

các luật kết hợp phân lớp phổ biến.

Thuật toán bao gồm 2 bước chính với hai thuật toán tương ứng:

1- Thuật toán CBA-RG

2- Thuật toán CBA-CB

2.2.1. Thuật toán CBA-RG

Thuật toán dùng để tìm tập đầy đủ các luật CAR thoản mãn ràng buộc độ

hỗ trợ tối thiểu do người dùng đặt ra (gọi là minsup) và thỏa mãn ràng buộc độ

chắc chắn tối thiểu (gọi là minconf).

Thuật toán CBA-RG tạo ra tất cả các luật phổ biến bằng việc duyệt nhiều

lần trên dữ liệu. Ở lần duyệt thứ nhất, nó tính số hỗ trợ của các mục luật riêng

và quyết định liệu nó là phổ biến không. Trong mỗi một chu trình con duyệt,

nó bắt đầu với tập hạt giống của các mục luật là phổ biến trong mục duyệt trước.

Nó sử dụng tập hạt giống này để tạo ra các mục luật có khả năng phổ biến, gọi

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

chúng là các mục luật dự tuyển. Thực tế, các số hỗ trợ cho các mục luật dự

31

tuyển này được tính trong quá trình duyệt dữ liệu. Tại cuối giai đoạn duyệt nó

quyết định mục luật dự tuyển nào là thực sự phổ biến. Từ tập hợp các mục luật

phổ biến này nó tạo ra các luật phổ biến phân lớp (CAR).

Ký hiệu k- mục luật là mục luật mà condset của nó có k mục. Đặt F là tập

của các k- mục luật phổ biến. Mỗi phần tử của tập này là có dạng sau:

< (condset, condsupcount), (y, rulesupcount) >.

Đặt Ck là tập của các k- mục luật dự tuyển, thuật toán CBA-RG được đưa

ra như sau:

* Thuật toán CBA-RG

1 F1 = {large 1-ruleitems};

2 CAR1 = genRules(F1);

3 prCAR1 = pruneRules(CAR1);

4 For (k = 2; Fk-1 # ∅ ; K++) do

5 Ck = candidateGen(Fk-1);

6 For each data case d ∈ D do

7 Cd = ruleSubset(Ck,d);

8 For each candidate c ∈ Cd do

c.condsupCount++; 9

If d.class = c.class then c.rulesupcount++ 10

end 11

end 12

13 Fk = {c ∈ Ck | c.rulesupCount ≥ minsup};

14 CARk = genRules(CARk);

16 end

17 CAR = ∪k CARk;

18 PrCAR = ∪k prCARk;

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Dòng 1-3 biểu diễn lần duyệt đầu tiên của thuật toán. Nó đếm số mục và

32

lớp có trong tập dữ liệu để xác định các (1-ruleitems) phổ biến (dòng 1). Từ tập

hợp của các 1- ruleitems, một tập các CAR (gọi CAR1) được tạo ra bằng thủ

tục genRules (dòng 2) (xem phần trước). CAR1 được thực hiện việc cắt tỉa

(dòng 3) (cũng có thể là tùy chọn). Việc cắt tỉa cũng được làm với CARk của

mỗi chu trình duyệt (dòng 15). Hàm pruneRules sử dụng phương pháp cắt tỉa

dựa trên tỉ lệ sai sót bi quan trong C4.5. Nó tỉa một luật như sau: nếu tỉ lệ sai

sót bi quan của luật r là lớn hơn tỉ lệ sai sót bi quan của luật r (nhận được bằng

việc xóa một điều kiện của r), thì luật r bị tỉa. Việc cắt tỉa này có thể cắt bỏ một

số các luật được tạo ra (xem mục đánh giá).

Mỗi một chu trình duyệt bước k, thuật toán thực hiện 4 thao tác chính. Đầu

tiên tập luật phổ biến Fk1-1 tìm trong (bước thứ (k-1) được sử dụng để tạo ra các

tập luật dự tuyển Ck có sử dụng hàm candidateGen (dòng 5)). Sau đó nó quét

CSDL và cập nhật hệ số hỗ trợ của các mục luật dự tuyển trong Ck (dòng 6-12).

Sau ki các mục luật phổ biến này được xác định tới dạng Fk (dòng 13), thuật

toán xây dựng tập luật CARk bằng việc sử dụng hàm genRules (dòng 14). Cuối

cùng việc cắt tỉa luật được thực hiện (dòng 15) trên những luật này.

Hàm dự tuyển CandidateGen giống với hàm Apriori – gen trong thuật toán

Apriori. Hàm ruleSubset lấy một tập các mục luật dự tuyển Ck và một tập các

trường hợp d để tìm ra tất cả các mục luật trong Ck mà condset của nó được hỗ

trợ bởi d. Việc thực hiện này và các thao tác từ dòng 8-10 cũng tương tự như

trong thuật toán Apriori. Tập hợp cuối của các luật kết hợp phân lớp trong CAR

(dòng 17). Những luật còn lại sau khi cắt tỉa sẽ được giữ trong prCAR (dòng

18)

2.2.2. Thuật toán CBA-CB

Thuật toán tiến hành xây dựng một cây phân loại từ các luật hợp thành lớp

CAR này.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Thuật toán CBA-CB xây dựng cây phân loại dựa vào các luật CAR (hoặc

33

prCAR). Để xây dựng cây quyết định tốt nhất liên quan đến việc ước lượng tất

cả các tập con có thể của nó trên tập mẫu học và chọn ra một tập con mà có số

đo sai số nhỏ nhất. Sẽ có 2m tập con như thế, với m là số các luật, có thể nhiều

hơn 1000. Tuy vậy cây quyết định được xây dựng là tốt hơn so với thuật toán

C4.5.

Một phiên bản thô của thuật toán nêu trên được mô tả ở dưới đây.

* Thuật toán CBA-CB

R = sort(R); 1

2 For each rule r ∈ R theo tuần tự Do

3 temp = ∅;

4 for each case d ∈ D do

if d thỏa mãn điều kiện của r then 5

lưu trữ d.id trong temp và đánh dấu r nếu nó phân loại đúng 6

d

if r được đánh dấu then 7

chèn r vào cuối của C; 8

xóa tất cả các trường hợp với ids trong temp ra khỏi D; 9

chọn một lớp ngầm định cho cây hiện tại C; 10

tính tổng số sai số của C; 11

end 12

end 13

14 Tìm luật đầu tiên p trong C có tổng số sai số nhỏ nhất và đưa ra tất cả các

luật sau p trong C;

15 Thêm giá trị lớp ngầm định liên kết với p vào cuối của C và trả về C (cây

phân loại của chúng ta)

Giải thích

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Bước 1: (dòng 1): sắp các luật theo thứ tự ưu tiên (>), Điều này giúp ta

34

chọn được luật ưu tiên nhất cho cây của chúng ta.

Bước 2 (dòng 2-13): chọn những luật cho cây quyết định từ R theo thứ tự

đã được xếp. Với mỗi luật r, chúng ta duyệt qua D để tìm những case (trường

hợp) được phủ bởi r (chúng thỏa mãn điều kiện của r) (dòng 5). Chúng ta đánh

dấu r nếu nó phân loại đúng một case d (dòng 6) d.id là chỉ số của d. Nếu r có

thể phân loại chính xác ít nhất ở một case (tức là nếu r được đánh dấu), nó sẽ

là một luật tiềm năng trong cây QĐ của chúng ta (dòng 7-8). Những case mà

được phủ bởi r sẽ được bỏ ra khỏi D (dòng 9). Một lớp ngầm định cũng được

chọn (lớp phổ biến (majority class) trong các dữ liệu còn lại), có nghĩa là nếu

chúng ta dừng việc chọn nhiều hơn các luật cho cây phân loại C thì lớp này sẽ

là lớp ngầm định cho C (dòng 10). Chúng ta tính và ghi lại tổng số các sai số

mà tạo ra cây C hiện tại và lớp ngầm định (dòng 11).

Đây là tổng của các sai số mà được tạo ra bởi việc chọn các luật trong C

và tổng các sai số được tạo ra bởi các lớp ngầm định trong tập mẫu học. Khi

không còn luật nào nữa hoặc không còn mẫu học nữa việc chọn các luật được

dừng lại.

Bước 3: (dòng 14-15): Bỏ ra khỏi C các luật mà không cải thiện được độ

chính xác của cây. Luật đầu tiên mà có số bản ghi sai ít nhất trên D là luật cắt.

Tất cả các luật sau luật này có thể được bỏ ra bởi vì chúng chỉ có thể cho sai số

lớn hơn. Những luật không bị loại bỏ và giá trị lớp ngầm định của luật cuối

cùng trong C tạo nên cây phân loại cần tìm.

2.3. Thuật toán hiện đại

2.3.1. Thuật toán CBA cải tiến

Chúng ta biết rằng, thuật toán xây dựng cây phân lớp dựa trên luật kết hợp

phân lớp CBA-RG và CBA-CB được Liu, Hsu, Ma giới thiệu vào năm 1998.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Thời gian tính toán tập trung vào thuật toán tìm các luật kết hợp phổ biến trong

35

tập mẫu học. Độ phức tạp tính toán của thuật toán này là O(m2 .n) (với m là số

phần tử của tập mẫu, n – là số thuộc tính). Đặc tả thuật toán CBA-RG được

trình bày. Với số phần tử (m) và số thuộc tính (n) của tập mẫu học tăng lên thì

thời gian chạy của thuật toán sẽ tăng khá nhiều. Trong thời gian gần đây, một

thuật toán cải tiến được trinh bày [5] đã tìm được các luật kết hợp phân lớp

trong bảng mẫu học có ý nghĩa đáng kể là giảm một nửa số phép tính.

Thuật toán (tìm các luật kết hợp phân lớp)

Input: tập D là bảng quan hệ có m phần tử trên tập các thuộc tính R =

{A1, A2, …An, CL}, với CL là thuộc tính phân lớp;

Output: Tập SCAR, tập các luật kết hợp phân lớp dạng X → CL với X là

tập con các khoản mục.

Bước 1: Ta tính toán hệ bằng nhau ED của D như sau:

ED = { Ei,j: 1 ≤ i < j ≤ n và Ei,j = {a ∈ R; ti(a)}; ti,tj ∈ D}

Gọi ED là hệ bằng nhau của D.

Đối với mỗi Ei,j mà có CL ∈ Ei,j đặt Mi,j = { Xi,j ∪ y với Xi,j là tập các khoản

mục (Ak, ti(Ak)) với Ak ∈ Ei,j; (CL = y) với CL ∈ Ei,j} là tập các luật kết hợp

phân lớp có 2 phần tử.

(Chú ý là: tập Mi,j có thể được xác định Mi,j = { Xi,j ∪ y với Xi,j là tập các khoản

mục (Ak, tj(Ak)) với Ak ∈ Ei,j; (CL = y) với CL ∈ Ei,j} vì các phần tử ti, tj có

cùng giá trị trên các thuộc tính Ak – theo cách xác định tập Ei,j).

Đặt CLD = {Mi,j} và gọi CLD là hệ luật kết hợp phân lớp 2 phần tử của D.

(Vì mỗi Xi,j đại diện cho một cặp có 2 phần tử)

Số phép toán cần thực hiện là: n(m-1)(m-2)…1 = n.m2/2.

Độ phức tạp tính toán của Bước 1 là O(n.m2).

Bước 2:

Với mỗi phần tử Mz,l ∈ CLD, tính số hỗ trợ dương s+ và số hỗ trợ âm s- của

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Mz,l như sau:

36

- Tính độ hỗ trợ Mzl:

+ Ký hiệu số phần tử chứa Mz,l là s+ và tiến hành;

+ s+ = 1;

+ Nếu Ez,l ⊆ Ei,j và thỏa mãn: (z=i) ∨ (z=j) ∨ (l=j) ∨ (l=i) tăng số đếm s+

lên 1 đơn vị (s+ = s+ + 1);

+ Tính số phần tử theo công thức:

Count(Mz,l) = (1 + √1 + 8s+)/2.

+ Tính độ hỗ trợ cho Mz,l:

supt = count(Mz,l)/m.

- Tính độ chắc chắn cho Mz,l như sau:

+ Ký hiệu số phần tử chưa Xi,j là s- và tiến hành:

s- = 1;

+ Nếu Xz,l ⊆ Ei,j và thỏa mãn: (z=i) ∨ (z=j) ∨ (l=j) ∨ (l=i) tăng số đếm s-

lên 1 đơn vị (s- = s- + 1);

+ Tính số phần tử chứa Xz,l theo công thức:

Count(Xz,l) = (1 + √1 + 8s−)/2.

+ Tính độ chắc chắn cho Mz,l: confd (Mz,l) = s+/s-

- Nếu supt(Mz,l) ≥ Minsup và confd (Mz,l) ≥ Minconfd thì

SCAR = SCAR ∪ Mz,l

- Tỉa các luật: nếu Mz,l ⊆ Mi,j với Mz,l, Mi,j ∈ SCAR thì loại Mz,l ra khỏi tập SCAR.

Như vậy chúng ta sẽ thấy số các phép tính tập trung vào Bước 1, và số phép

tính sẽ là: n.(m-1).(m-2)…1 = n.m2/2.

Chú ý: các công thức tính count(Mz,l) và count(Xz,l) được tính dựa trên căn

cứ sau:

Nếu gọi k là số cặp bằng nhau (tại một tập thuộc tính A) của các bản ghi,

n là số bản ghi có giá trị bằng nhau (tại một tập thuộc tính A), ta có mối quan

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

hệ giữa k và n như sau:

37

k = n(n-1)/2 và ta xác định n theo công thức tính tính nghiệm của phương

trình bậc hai: n2 – n – 2k = 0; giải ra ta có: n = (1 + √1 + 8𝑘)/2)

Tính đúng đắn của thuật toán này đã được khảng định trong [5].

Trong thuật toán CBA-RG ta nhận thấy quy trình để xác định các CAR sẽ

lần lượt được thực hiện lần lượt với các CARk với k = 1, …, m; phải nhiều lần

duyệt tập D với tất cả các phần tử và cần nhiều phép tính so sánh và có độ phức

tạp tính toán là O(m2.n).

Thuật toán cải tiến có số lần duyệt các phần tử trên D sẽ ít hơn và cũng có

độ phức tạp tính toán là O(m2.n) nhưng giảm được một nửa số phép tính.

2.3.2. Ví dụ áp dụng thuật toán cải tiến

Chúng ta sẽ minh họa việc sử dụng thuật toán mới để tính các luật kết hợp

phân lớp thông qua một ví dụ.

Bảng 2.1.Ví dụ tập mẫu học để tìm các luật kết hợp phân lớp theo thuật toán

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

cải tiến

38

C D CL A B

2 1 Y 1 1 0

1 0 Y 2 1 2

2 2 Y 3 2 1

3 3 Y 4 2 2

2 1 N 5 1 0

2 4 N 6 1 1

Tính các Eij như sau:

E1,2 = A.CL; E1,3 = C.CL; E1,4 = CL; E1,5 = ABCD; E1,6 = AC

E2,3 = CL; E2,4 = B.CL; E2,5 = A; E2,6 = A;

E3,4 = A.CL; E3,5 = C; E3,6 = BC;

E4,5 = ∅; E4,6 = ∅;

E5,6 = AC.CL

Tính CLD = { M1,2 = <(A=1), (CL=Y)>; M1,3 = <(C=2), (CL=Y)>;

M2,4 = <(B=2), (CL=Y)>; M3,4 = <(A=2), (CL=Y)>; M5,6 = <(A=1), (CL=N)>}

Để thuận tiện ta ký hiệu:

<(Ai, giá trị)…, nhãn lớp> cho mục luật <(Ai=giá trị)…, Y>;

Với ký hiệu trên ta có:

CLD = {M1,2 = <(A,1),Y>; M1,3 = <(C,2),Y>; M2,4 = <(B,2),Y>;

M3,4 = <(A,2),Y>; M5,6 = <(A,1)(C,2),N>}

Với M1,2 ta có số hỗ trợ dương là 2; số hỗ trợ âm của X1,2 là 1 do vậy với

luật:

(A=1) → Y ta có hệ số hỗ trợ là 2/6 * 100% = 33,3% và hệ số chắc chắn

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

là 50%

39

Tương tự:

Với M1,3 ứng với luật (C=2) → Y ta có: hệ số hỗ trợ là 33,3% và hệ số

chắc chắn là 50%;

Với M2,4 ứng với luật (B=2) → Y ta có: hệ số hỗ trợ là 33,3% và hệ số

chắc chắn là 100%

Với M3,4 ứng với luật (A=2) → Y ta có: hệ số hỗ trợ là 33,3% và hệ số

chắc chắn là 100%

Với M5,6 ứng với luật <(A=1),(C,2)> → N ta có: hệ số hỗ trợ là 33,3% và

hệ số chắc chắn là 67%.

Ta có bảng tổng hợp sau:

Bảng 2.2.Bảng tổng hợp

Mục luật s+ cout supt Condset count confd s-

(A,1),Y 1 2 33% (A,1) 6 4 50%

(A,2),Y 1 2 33% (A,2) 1 2 100%

(C,2),Y 1 2 33% (C,2) 6 4 50%

(C,2),N 1 2 33% (C,2) 6 4 50%

(B,2),Y 1 2 33% (B,2) 1 2 100%

1 2 (A,1),(C,2),N 33% (A,1),(C2) 3 3 67%

Như vậy nếu Minsup = 30% và Minconfd = 60% ta sẽ thấy có các mục

luật sau là vừa phổ biến và chính xác:

(A,1) → N

(C,2) → N

(A,2) → Y

(B,2) → Y

Để đánh giá hiệu quả thực hiện của thuật toán cải tiến so với thuật toán cổ

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

điển, chúng ta ước tính số phép toán:

40

Để tính được tập bằng nhau: chúng ta cần thực hiện:

62 x 4/2 = 72 phép tính

Tính Bảng 4 ta cần: 15 phép tính + 15 phép tính = 30 phép tính

Tổng cộng cần 102 phép tính.

Nếu xét với cùng ví dụ trên, chúng ta có thể tìm luật kết hợp phân lớp theo

CBA-RG:

Với Minsup = 30% và Minconfd = 60%. Ta tìm các khoản mục phổ biến,

bằng cách duyệt trên bảng ta có:

- Bảng 1: liệt kê các khoản mục và các hệ số hỗ trợ của các khoản mục

- Bảng 2: liệt kê các luật phân lớp phổ biến 1 – khoản mục

- Bảng 3: liệt kê các luật phân lớp phổ biến 2 – khoản mục

Các luật phân lớp phổ biến 3 – khoản mục trở nên không có.

Bảng 2.3a – Khoản mục

Bảng 2.3b – Các luật kết hợp phân lớp phổ biến 1 – Khoản mục

Count supt

Mục luật Count (A,1),Y (A,2),Y (B,2),Y (C,2),Y (A,1),N (C,2),N 2 2 2 2 2 2 Supt 33% 33% 33% 33% 33% 33% confd 50% 100% 100% 50% 50% 50%

Bảng 2.3c – Các luật kết hợp phân lớp 2 – khoản mục

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Khoản mục A = 1 A = 2 B = 0 B = 1 B = 2 C = 1 C = 2 C = 3 D = 0 D = 1 D = 2 D = 3 D = 4 4 2 2 2 2 1 4 1 1 2 1 1 1 67% 33% 33% 33% 33% 17% 67% 17% 17% 33% 17% 17% 17% Mục luật (A,1),(B,2),Y (A,1),(C,2),Y (A,1),(C,2),N Count 1 1 2 Supt 17% 17% 33% confd 100% 100% 100%

41

So sánh với điều kiện Minsup = 30% và Minconfd = 60% chúng ta thấy có các

mục luật vừa chính xác vừa phổ biến là:

(A,1) -> N

(C,2) → N

(A,2) → Y

(B,2) → Y

Ước tính số phép toán thực hiện:

Ta chọn phép so sánh giá trị ở 1 khoản mục làm đơn vị.

Để có được kết quả ở Bảng 1 cần thực hiện 62 x 4 =144 phép tính.

Để có được Bảng 2 cần thực hiện: 6 x 6 = 36 phép tính.

Để có được Bảng 3 cần thực hiện: 3 x 6 = 18 phép tính.

Tổng cộng cần là: 198 phép tính (= O(m2.n)) Chưa kể các phép so sánh và

tính supt và confd…

Như vậy, tuy độ phức tạp tính toán của thuật toán cải tiến là O(m2.n) nhưng

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

số lượng phép toán giảm được khoảng 1/2 so với CBA-RG.

42

CHƯƠNG 3.

CHƯƠNG TRÌNH THỬ NGHIỆM TÌM CÁC LUẬT KẾT HỢP PHÂN

LỚP DỰA TRÊN TẬP MẪU HỌC

3.1. Bài toán thử nghiệm

3.1.1. Bài toán và tập mẫu học đầu vào

Mô tả Bài toán chẩn đoán bệnh cúm tại bệnh viện Đa khoa Trung ương

Thái Nguyên và yêu cầu chương trình:

Cúm là một bệnh truyền nhiễm cấp tính lây theo đường hô hấp, do các

vi rút cúm A,B,C gây nên. Bệnh khởi phát đột ngột bằng sốt cao, nhức đầu, đau

mỏi toàn thân và những dấu hiệu hô hấp, dễ dẫn đến viêm phổi, tỷ lệ tử vong

cao.

Trong thế kỷ XX nhiều đại dịch cúm đã xảy ra với số mắc và tỷ lệ tử

vong cao. Tuy nhiên lâm sàng bệnh đã được mô tả nhiều thế kỷ trước (A Hirsd,

1881-1886). Năm 1933 W.Smith, C.Andrews, P.Laidpow xác định được vi rút

cúm A. Năm 1940 T.Francis và T.Magill phát hiện vi rút cúm B, năm 1949

R.Taylor phát hiện vi rút cúm C. Bằng các kỹ thuật sinh học phân tử, các nhà

khoa học đã xác định thủ phạm gây ra vụ đại dịch cúm đầu tiên năm 1918-1919

(cúm Tây Ban Nha) là vi rút cúm A chủng H1N1 gây tử vong 20 triệu người,

đại dịch cúm châu Á năm 1957 - 1958 là do cúm A chủng H2N2 làm khoảng 1

triệu người tử vong. Cúm Hồng Kông năm 1968 - 1969 do cúm A H3N2, cúm

Nga năm 1977 do chủng H1N1…Virút cúm A có khả năng thay đổi cấu trúc

kháng nguyên. Quá trình lai ghép, tái tổ hợp giữa virut cúm A ở người Virut

cúm A ở động vật sẽ tạo thành chủng virut cúm mới. Vì vậy virut cúm A là thủ

phạm gây ra các đại dịch, virut cúm B thường gây các vụ dịch. Khu vực, virut

cúm C thường gây các dịch tản phát. Cứ khoảng 10 - 14 năm lại có một đại

dịch cúm xảy ra. Dịch cúm A(H5N1) lây từ gia cầm sang người xảy ra ở Hồng

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Kông đang có nguy cơ lan rộng thành đại dịch.

43

- Quy trình chuẩn đoán xác định bệnh cúm được dựa vào các thông tin

chính sau:

Bệnh cúm khởi phát đột ngột, sốt cao thời gian sốt 4 - 7 ngày.

- Thời kỳ khởi phát:

Thường đột ngột bằng sốt cao 39 - 400C, kèm theo rét run, nhức đầu

choáng váng, buồn nôn và đau mỏi toàn thân, mệt mỏi không muốn làm việc.

- Thời kỳ toàn phát:

+ Hội chứng nhiễm khuẩn nhiễm độc sốt cao liên tục 39 - 400C, thời gian

sốt 4 - 7 ngày, khi hết sốt nhiệt độ giảm nhanh. Một số bệnh nhân sốt kiểu “V

cúm” đang sốt cao nhiệt độ tụt xuống ngay sau đó lại tăng lên rồi mới hạ xuống

lần thứ 2.

+ Bệnh nhân mệt mỏi nhiều ăn ngủ kém, môi khô lưỡi bẩn, mạch nhanh

huyết áp dao động, nước tiểu vàng.

+ Bạch cầu máu ngoại vi số lượng không tăng, tỷ lệ bạch cầu

Lymphocyte tăng, tốc độ lấy máu không tăng.

+ Hội chứng hô hấp: Các triệu chứng thường gặp là:

 Viêm long đường hô hấp trên: Sổ mũi, hắt hơi, rát họng, ho khan mắt

xung huyết, chảy nước mắt, sợ ánh sáng.

 Viêm phế quản cấp viêm phổi: Đau tức ngực, khó thở, ho khạc đờm

trắng dính. Khám phổi thấy ran ngáy ran rít, hoặc một số ran ẩm nhỏ hạt.

 Viêm thanh hầu và khí quản: Bệnh nhân khàn tiếng, ho khan.

 X quang phổi: Thường không phản ánh được dấu hiệu lâm sàng ở

phổi.

+ Triệu chứng khác:

 Đau đầu liên tục, đau nhiều ở vùng thái dương, vùng trán, đôi khi dội

lên từng cơn kèm theo hoa mắt chóng mặt ù tai.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

 Đau mỏi toàn thân đau cơ bắp và khớp, đau dọc sống lưng, đau ngang

44

thắt lưng, xoa bóp cơ khớp thì đỡ đau.

Dựa vào các triệu chứng bệnh nêu trên. Nếu hết giai đoạn khám lâm sàng

này, bác sĩ không có nghi ngờ gì về bệnh cúm thì sẽ đưa ra câu trả lời phủ định

bệnh cúm, có thể gợi ý khả năng bệnh nhân mắc một bệnh khác. Bệnh nhân sẽ

được khuyên là nên quay lại nếu bệnh nặng hơn mà không rõ căn nguyên.

Thông tin về các thuộc tính được khảo sát như sau [2]

1. Đaudau (Đau đầu): không đau, đau, đau dữ dội

2. Đauco (Đau cơ): Khong đau, rat đau, đau, hơi đau, đau khi van dong

3. Thannhiet (Thân nhiệt): Bình thường, sốt nhẹ, sốt cao

4. Onlanh (Ớn lạnh): khong lạnh, gai ret, ret, ret run

5. Chongmat (Chóng mặt): Có, không

6. Metmoi (Mệt mỏi): Có, không

7. Ho (Ho): Có, không

8. Dauhong (Đau họng): Có, không

9. Chaynuocmui (Chảy nước mũi): Có, không

10. Nghetmui (Nghẹt mũi): Có, không

11. Non (Nôn): Có, không

12. Tieuchay (Tiêu chảy): Có, không

13. Cum (Cúm): Có, không

Để đơn giản chẩn đoán bệnh cúm, chúng ta chỉ nghiên cứu theo 4 nguyên

nhân chính, sau này có điều kiện sẽ mở rộng ra theo cả 13 thuộc tính. Như vậy,

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

chúng ta có dữ liệu về tập mẫu học tương ứng sau:

45

Bảng 3.1. Tập mẫu học

Tap mau hoc

E-Cúm? A-Than B-đau C-ớn D-đau cơ (thuộc tính nhiet đầu lạnh phân lớp)

Không 1. Sốt nhẹ Rét Rất đau Y đau

2. Sốt nhẹ Đau Gai rét Không đau Y

3. Sốt cao Hơi đau Rét Đau Y

4. Sốt cao đau Rét run Hơi đau Y

Không 5. Sốt nhẹ Rét Rất đau N đau

Đau khi vận 6. Sốt nhẹ Hơi đau Rét N động

Y- yes- bị cúm

N-no- không bị

cúm

Để đơn giản tính toán, chúng ta mã hóa chúng để có được tập mẫu học

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

dạng số như sau:

46

Bảng 3.2. Bảng mẫu học được số hóa

Tap mau hoc

A-Thân B-đau C-ớn D-đau cơ E-Cúm? nhiệt đầu lạnh

2 1 1 0 1 Y

1 2 1 2 0 Y

2 3 2 1 2 Y

3 4 2 2 3 Y

2 5 1 0 1 N

2 6 1 1 4 N

0- 0- Không Không 0- Không 0- Không dau lạnh sốt đau 1- Rất đau Y- yes 1- Gai 1- Sốt nhẹ 1- Đau 2- Đau N-no rét 2- Sốt cao 2- Đau 3- Hơi đau 2- Rét dữ dội 4- Đau khi 3- Rét vận động run

3.1.2. Chọn thuật toán thử nghiệm

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Thuật toán được chon để thử nghiệm là thuật toán cải tiến trong mục 2.3.1.

47

3.2. Môi trường thử nghiệm

3.2.1. Chọn môi trường chứa dữ liệu đầu vào

Bảng mẫu học được lưu trong EXCEL: Tuan1.xlsx (dạng chữ và số)

3.2.2. Chọn ngôn ngữ lập trình

Sử dụng ngôn ngữ lập trình C# để xây dựng chương trình thử nghiệm.

3.3. Nội dung và kết quả thử nghiệm

3.3.1. Mô hình thuật toán thử nghiệm

Thuật toán (tìm các luật kết hợp phân lớp) [5]

Input: tập D* là bảng quan hệ có m phần tử trên tập các thuộc tính R

= {A,B,C,D,E}, với E là thuộc tính phân lớp;

Output: Tập SCAR, tập các luật kết hợp phân lớp dạng X={A,B,C,D} → E

với X là tập con các khoản mục.

Bước 1: Ta tính toán hệ bằng nhau ED* của tập mẫu học như sau:

ED* = { Ei,j: 1 ≤ i < j ≤ n và Ei,j = {a ∈ R; ti(a)}; ti,tj ∈ D*}

Gọi ED* là hệ bằng nhau của D*.

Đối với mỗi Ei,j mà có E ∈ Ei,j đặt Mi,j = { Xi,j ∪ y với Xi,j là tập các khoản

mục (Ak, ti(Ak)) với Ak ∈ Ei,j; (E = y) với E ∈ Ei,j} là tập các luật kết hợp phân

lớp có 2 phần tử.

(Chú ý là: tập Mi,j có thể được xác định Mi,j = { Xi,j ∪ y với Xi,j là tập các khoản

mục (Ak, tj(Ak)) với Ak ∈ Ei,j; (E = y) với E ∈ Ei,j} vì các phần tử ti, tj có cùng

giá trị trên các thuộc tính Ak – theo cách xác định tập Ei,j).

Đặt ED = {Mi,j} và gọi ED là hệ luật kết hợp phân lớp 2 phần tử của D.

(Vì mỗi Xi,j đại diện cho một cặp có 2 phần tử)

Số phép toán cần thực hiện là: n(m-1)(m-2)…1 = n.m2/2.

Độ phức tạp tính toán của Bước 1 là O(n.m2).

Bước 2:

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Với mỗi phần tử Mz,l ∈ ED, tính số hỗ trợ dương s+ và số hỗ trợ âm s- của

48

Mz,l như sau:

- Tính độ hỗ trợ Mzl:

+ Ký hiệu số phần tử chứa Mz,l là s+ và tiến hành;

+ s+ = 1;

+ Nếu Ez,l ⊆ Ei,j và thỏa mãn: (z=i) ∨ (z=j) ∨ (l=j) ∨ (l=i) tăng số đếm s+

lên 1 đơn vị (s+ = s+ + 1);

+ Tính số phần tử theo công thức:

Count(Mz,l) = (1 + √1 + 8s+)/2.

+ Tính độ hỗ trợ cho Mz,l:

supt = count(Mz,l)/m.

- Tính độ chắc chắn cho Mz,l như sau:

+ Ký hiệu số phần tử chứa Xi,j là s- và tiến hành:

s- = 1;

+ Nếu Xz,l ⊆ Ei,j và thỏa mãn: (z=i) ∨ (z=j) ∨ (l=j) ∨ (l=i) tăng số đếm s-

lên 1 đơn vị (s- = s- + 1);

+ Tính số phần tử chứa Xz,l theo công thức:

Count(Xz,l) = (1 + √1 + 8s−)/2.

+ Tính độ chắc chắn cho Mz,l: confd (Mz,l) = s+/s-

- Nếu supt(Mz,l) ≥ Minsup và confd (Mz,l) ≥ Minconfd thì

SCAR = SCAR ∪ Mz,l

- Tỉa các luật: nếu Mz,l ⊆ Mi,j với Mz,l, Mi,j ∈ SCAR thì loại Mz,l ra khỏi tập SCAR.

3.3.2. Xác định các luật kết hợp thu được

Sau khi thực hiện các phép tính toán theo thuật toán cải tiến trên, ta thu

được bảng tổng hợp sau:

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Bảng 3.3.Bảng tổng hợp

49

Mục luật s+ count supt Condset s- count confd

(Thannhiet, (Thannhiet,sotnhe),Y 1 2 33% 6 4 50% sotnhe)

(Thannhiet, (Thannhiet,sotcao),Y 1 33% 2 1 2 100% sotcao)

(Ơnlanh,ret),Y 33% (Ơnlanh,ret) 1 2 6 4 50%

(Ơnlanh,ret),N 33% (Ơnlanh,ret) 1 2 6 4 50%

(Đau đầu, 2 (đau đầu,dau dữ dội),Y 1 33% 1 2 100% đaududoi)

(Thannhiet,sotnhe),(Ơn (Thannhiet,sotn 1 2 33% 3 3 67% lanh,ret),N he),(Ơnlanh,ret)

Như vậy nếu Minsup = 30% và Minconfd = 60% ta sẽ thấy có các mục

luật sau là vừa phổ biến và chính xác:

 (Thannhiet, sotnhe) → không bị cúm

 (Ơnlanh, ret) → không bị cúm

 (Thannhiet, sotcao) → bị cúm

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

 (đauđau, đaududoi) → bị cúm

50

3.3.3. Một số giao diện chính của chương trình thử nghiệm

Hình 3.1. Giao diện của chương trình thử nghiệm

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Hình 3.2. Giao diện của chương trình thử nghiệm

51

3.4. Đánh giá chương trình thử nghiệm

Chương trình thử nghiệm với tập mẫu học đưa vào là file Excel:

Tuan1.xlsx với dữ liệu được thu thập từ các bệnh nhân tại bệnh viện đa khoa

TW Thái Nguyên đã cho kết quả tốt, đúng với kết luận của các bác sĩ tại bệnh

viện đa khoa TW Thái Nguyên.

3.5. Mở rộng bài toán

Mẫu học được mở rộng với 50 bệnh nhân và 13 thuộc tính đặc trưng và 1

thuộc tính phân lớp (cúm) [2]

Bảng 3.4. Bảng mẫu học (mở rộng) đầu vào

table1

Be

nh Dau Da Than Onl Chon Met Dau Chaynu Nghe No Tieu Cu Ho nh dau uco nhiet anh gmat moi hong ocmui tmui n chay m

an

B0 Khô Khôn Khôn Kh Khôn Có Cao Có Có Có Có Không Có 1 ng g g ông g

Bình Kh Khôn Kh Khôn Kh Khôn Kh B0 Có thườn Có Có Có Không ông g ông g ông g ông 2 g

Rất Khô Kh Khôn B0 Có Có Có Có Có Có Không Có Có cao ng ông g 3

B0 Khô Kh Khôn Kh Khôn Khôn Kh Cao Có Có Có Không Có 4 ng ông g ông g g ông

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Bình B0 Kh Khô Khô Kh Kh Khôn Kh Có thườn Có Có Không Có 5 ông ng ng ông ông g ông g

52

table1

Be

nh Dau Da Than Onl Chon Met Dau Chaynu Nghe No Tieu Cu Ho nh dau uco nhiet anh gmat moi hong ocmui tmui n chay m

an

Kh Khôn Khô B0 Khô Có Cao Có Có Có Có Có Có Có ông g ng 6 ng

Khô Khôn Khôn B0 Khô Có Cao Có Có Có Có Có Có Có ng g g 7 ng

Kh Kh Kh Khôn Khôn B0 Có Cao Có Có Có Có Có Có ông ông ông g g 8

Khôn Kh Khôn Khô Khôn B0 Khô Có Cao Có Có Có Không Có g ông g ng g 9 ng

Kh Khôn Khô Khôn B1 Có Có Cao Có Có Có Không Có Có ông g ng g 0

Khôn Khô B1 Có Có Cao Có Có Có Có Có Có Có Có g ng 1

Bình Khô B1 Khô Kh Khôn Kh Khôn Kh Có Có Có Có Có thườn ng 2 ng ông g ông g ông g

Bình Khô Khôn Kh Khô Kh Khôn Kh B1 Có Có thườn Có Có Có ng g ông ng ông g ông 3 g

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Khô Khôn Khô Khôn B1 Có Có Cao Có Có Không Có Có Có ng g ng g 4

53

table1

Be

nh Dau Da Than Onl Chon Met Dau Chaynu Nghe No Tieu Cu Ho nh dau uco nhiet anh gmat moi hong ocmui tmui n chay m

an

Khôn B1 Khô Khôn Có Cao Có Có Có Có Có Có Có Có g 5 ng g

Khôn Khôn Rất B1 Có Có Có Có Có Có Có Không Có Có g g cao 6

Bình Kh Kh Khô Khôn Khôn Khôn Kh B1 Có thườn Có Có Không Có ông g ông ng g g ông 7 g

Kh Khôn Kh Khôn B1 Có Có Cao Có Có Có Có Có Có ông g ông g 8

Khôn Khôn B1 Có Có Cao Có Có Có Có Không Có Có Có g g 9

Khôn Kh Khô Khôn Kh Khôn Kh B2 Có Có Cao Có Có Không g ông ng g ông g ông 0

Bình Khô Khôn Kh Kh Khôn Kh Kh B2 Có Có Không Có Có thườn ng g ông ông g ông ông 1 g

Khôn Kh Khôn B2 Khô Kh Rất Có Có Có Có Có Có Có g ông g 2 ng ông cao

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

B2 Kh Khô Khôn Khô Khôn Kh Khôn Kh Có Cao Có Có Không 3 ông ng g ng g ông g ông

54

table1

Be

nh Dau Da Than Onl Chon Met Dau Chaynu Nghe No Tieu Cu Ho nh dau uco nhiet anh gmat moi hong ocmui tmui n chay m

an

B2 Khô Kh Khôn Khôn Cao Có Có Có Có Không Có Có Có 4 ng ông g g

Khô Khôn Kh Khôn B2 Có Có Cao Có Có Có Có Không Có ng g ông g 5

Kh Khô Khôn Khô Kh Khôn B2 Có Cao Có Có Không Có Có ông ng g ng ông g 6

B2 Khô Khôn Khô Khôn Rất Có Có Có Có Không Có Có Có 7 ng g ng g cao

Bình Kh Kh Khô B2 Có Có Có Có Có Có Có Có Có thườn ông ông ng 8 g

Bình Kh Khô Khôn Kh Khô Khôn Kh Khôn Kh B2 Có Có Có thườn ông ng g ông ng g ông g ông 9 g

Khô Khôn Khô Kh Kh Khôn B3 Có Có Cao Có Không Có Có ng g ng ông ông g 0

B3 Khô Kh Rất Khô Kh Khô Kh Khôn Có Có Không Có Có 1 ng ông cao ng ông ng ông g

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

B3 Khô Rất Khôn Kh Khô Khôn Khôn Kh Có Có Có Không Có 2 ng cao g ông ng g ông g

55

table1

Be

nh Dau Da Than Onl Chon Met Dau Chaynu Nghe No Tieu Cu Ho nh dau uco nhiet anh gmat moi hong ocmui tmui n chay m

an

Khôn Kh Khôn Kh Khô Kh B3 Khô Kh Cao Có Có Có Không g ông g ông ng ông 3 ng ông

Kh Khôn Kh B3 Có Có Cao Có Có Có Có Có Có Có ông g ông 4

Bình Kh Khôn B3 Có Có thườn Có Có Có Có Không Có Có Có ông g 5 g

Khôn Kh Khôn Rất Khôn B3 Có Có Có Có Có Có Không Có g ông g cao g 6

Kh Khô Rất B3 Khô Khôn Kh Có Có Có Có Không Có Có ông ng cao 7 ng g ông

B3 Khô Kh Rất Khôn Kh Khô Khôn Kh Có Có Không Có Có 8 ng ông cao g ông ng g ông

Khô Khôn Khô Khôn Kh Khôn B3 Có Có Cao Có Có Có Có ng g ng g ông g 9

Kh Khô Khôn Kh Kh B4 Có Cao Có Có Có Có Không Có ông ng g ông ông 0

B4 Khô Rất Khôn Kh Khôn Có Có Có Có Không Có Có Có 1 ng cao g ông g

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

B4 Có Có Cao Khô Khôn Có Có Khô Có Có Kh Khôn Có

56

table1

Be

nh Dau Da Than Onl Chon Met Dau Chaynu Nghe No Tieu Cu Ho nh dau uco nhiet anh gmat moi hong ocmui tmui n chay m

an

ng g ng ông g 2

Kh Khôn Kh Khôn B4 Có Có Cao Có Có Có Không Có Có ông g ông g 3

Bình Kh Kh Khô Khôn Kh Khôn B4 Có thườn Có Có Không Có Có ông ông ng g ông g 4 g

B4 Khô Kh Rất Kh Khô Khôn Khôn Kh Có Có Có Không Có g 5 ng ông cao ông ng g ông

Bình B4 Khô Kh Khô Khôn Kh Khôn Kh thườn Có Có Có Không Có 6 ng ông ng g ông g ông g

Khô Khôn Khô Khôn Kh Khôn B4 Có Có Cao Có Có Có Có ng g ng g ông g 7

Rất Kh Khôn B4 Có Có Có Có Có Có Không Có Có Có cao ông g 8

Kh Rất Khôn Khô Kh Khôn B4 Có Có Có Có Không Có Có ông cao g ng ông g 9

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

B5 Khô Kh Khôn Khô Kh Khôn Kh Cao Có Có Không Có Có 0 ng ông g ng ông g ông

57

Sau khi mã hóa, chúng ta cũng có:

Bảng 3.5. Bảng mẫu học mở rộng được số hóa

table1

N C Benh Dau Da Than Onl Chon Met H Dau Chaynu Nghe Tieu o u nhan dau uco nhiet anh gmat moi o hong ocmui tmui chay n m

0 1 0 0 0 1 1 1 0 1 1 1 0 B01

0 0 0 0 1 0 0 1 0 1 0 1 0 B02

0 1 0 1 1 1 1 0 1 1 1 1 0 B03

1 0 0 0 0 0 1 1 0 1 0 1 0 B04

0 0 0 1 1 0 0 0 1 0 0 1 0 B05

0 1 0 1 0 1 1 0 1 1 1 1 1 B06

1 1 1 0 0 1 1 1 0 1 1 0 1 B07

0 1 0 1 1 0 1 1 0 1 0 1 1 B08

0 1 0 0 0 1 1 0 0 1 1 1 0 B09

0 1 0 1 1 1 1 0 0 1 1 1 0 B10

1 1 0 1 1 1 1 0 1 1 1 1 1 B11

0 0 0 0 0 0 0 0 1 1 1 1 1 B12

0 0 0 1 1 1 0 0 0 1 0 0 1 B13

1 1 0 1 1 1 1 0 0 0 1 1 0 B14

1 1 1 0 0 1 1 1 0 1 1 1 1 B15

1 1 0 0 1 1 1 1 1 1 1 1 0 B16

1 0 0 0 1 0 0 0 0 1 0 1 0 B17

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

0 1 1 0 1 1 1 1 0 1 0 1 1 B18

58

table1

N C Benh Dau Da Than Onl Chon Met H Dau Chaynu Nghe Tieu o u nhan dau uco nhiet anh gmat moi o hong ocmui tmui chay n m

1 1 0 1 1 1 1 1 0 1 1 1 0 B19

0 0 0 0 1 1 1 1 0 1 0 0 0 B20

0 0 0 1 1 0 0 0 0 1 0 1 0 B21

0 1 0 0 0 0 1 1 1 1 1 1 1 B22

0 0 0 0 1 0 1 0 0 0 1 1 0 B23

1 1 0 1 0 0 1 1 0 1 1 1 0 B24

0 1 0 0 1 1 1 0 1 1 1 1 0 B25

0 1 0 1 1 0 1 0 0 1 1 0 0 B26

1 1 0 1 0 1 1 1 0 1 1 0 0 B27

0 1 1 1 1 0 0 0 1 1 1 1 1 B28

0 0 0 0 1 0 0 0 0 1 0 0 1 B29

1 0 1 0 1 1 1 0 0 0 0 1 0 B30

1 0 1 0 0 0 1 0 1 1 0 0 0 B31

1 0 0 0 0 1 1 1 0 1 0 0 0 B32

0 0 0 0 0 0 1 1 1 0 0 1 0 B33

0 1 0 1 1 0 1 1 1 1 1 1 1 B34

1 1 0 1 1 1 0 1 1 1 0 1 0 B35

0 1 0 0 1 1 1 1 0 1 1 1 0 B36

1 0 1 0 0 1 1 1 1 1 0 0 0 B37

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

1 0 1 0 0 0 1 1 0 1 0 0 0 B38

59

table1

N C Benh Dau Da Than Onl Chon Met H Dau Chaynu Nghe Tieu o u nhan dau uco nhiet anh gmat moi o hong ocmui tmui chay n m

B39 1 1 1 0 0 0 1 1 1 0 1 0 0

B40 1 0 1 0 1 1 1 1 0 0 0 1 0

B41 0 1 1 1 0 1 0 1 0 1 1 0 1

B42 1 1 1 0 0 1 1 0 1 0 1 0 1

B43 1 1 1 1 0 1 0 1 0 0 1 0 1

B44 1 0 0 0 0 1 0 1 0 1 0 1 0

B45 0 0 1 1 1 1 0 0 0 1 0 0 0

B46 0 0 0 0 0 1 1 1 0 0 0 0 1

B47 1 1 1 0 0 0 1 1 1 0 1 0 0

B48 1 1 1 1 1 1 0 1 0 1 1 0 1

B49 1 0 1 1 0 1 1 0 0 0 1 0 1

B50 0 0 1 1 0 0 0 1 0 1 0 1 0

Bảng mẫu học mở rộng được lưu trong EXCEL: Tuan2.xlsx (dạng chữ và

số)

Từ kết quả của phần mềm cho thấy thuật toán cải tiến dựa trên luật kết

hợp phân lớp được trình bày trong [5] đưa ra kết quả đúng và giảm một nửa

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

số phép tính trong quá trình tính toán.

60

KẾT LUẬN

Kết quả đạt được

Luận văn “ Nghiên cứu một số phương pháp tìm các luật kết hợp

phân lớp trên tập mẫu học áp dụng vào chẩn đoán bệnh” đã đạt được những

kết quả sau:

 Chương 1 giới thiệu tổng quan về “ Khai phá dữ liệu” một số vấn đề

như: khái niệm, các phương pháp khai phá dữ liệu, các ứng dụng của khai phá

dữ liệu. Khái niệm về phân lớp dữ liệu, các bước tiến hành phân lớp, các kiểu

phương pháp phân lớp dữ liệu.....

 Chương 2 giới thiệu về một số phương pháp tìm các luật kết hợp phân

lớp dựa trên tập mẫu học, phương pháp phân lớp, các bước tiến hành phân lớp

dựa trên luật kết hợp. Chương này cũng giới thiệu các thuật toán xây dựng cây

phân lớp dựa trên luật kết hợp, các thuật toán cổ điển CBA-RG, CBA-CB và

thuật toán cải tiến giúp giảm một nửa số phép tính khi thực hiện bài toán.

 Chương 3 mô tả bài toán áp dụng thuật toán cải tiến vào chuẩn đoán

bệnh cúm tại bệnh viện đa khoa TW Thái Nguyên, các quy trình chuẩn đoán

xác định bệnh, các thông tin về tình trạng bệnh nhận được thu thập và lưu vào

file Excel làm dữ liệu đầu vào của bài toán. Cuối chương 3 là phần giới thiệu

về kết quả xây dựng phần mềm chuẩn đoán bệnh cúm và kết quả thu được sau

khi nhập dữ liệu.

Vì khai phá dữ liệu dựa trên luật kết hợp nói riêng và khai phá dữ liệu

nói chung là một vấn đề rộng lớn, nên chắc hẳn bài nghiên cứu nhỏ này của e

sẽ còn nhiếu thiếu sót, phần thực nhiệm vẫn còn ở dạng thử nghiệm thuật toán

cần cải thiện thêm mới có thể trở thành sản phẩm thực tiễn. Em rất mong nhận

được sự góp ý của các thầy cô và các bạn để đề tài ngày càng hoàn thiện hơn.

Em xin chân thành cảm ơn!

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Hướng nghiên cứu tiếp theo

61

Tiếp tục hoàn thiện phần mềm để có thể trở thành phần mềm thực tiễn.

Nghiên cứu áp dụng thuật toán, xây dựng những phần mềm chuẩn đoán

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

các bệnh khác.

62

TÀI LIỆU THAM KHẢO

A-Tiếng Việt

[1]. Nguyễn Khắc Giáo (2013), Khai thác luật kết hợp từ cơ sở dữ liệu

giao dịch của siêu thị bán lẻ, Luận văn Thạc sĩ Công nghệ thông tin, Đại học

Công nghệ, Đại học Quốc gia Hà Nội.

[2].Nguyễn Đăng Nguyên (2017), Phương pháp xây dựng cây quyết

định dựa trên tập phụ thuộc hàm xấp xỉ, Luận văn Thạc sĩ Khoa học máy tính,

Đại học Công nghệ thông tin và truyền thông – Đại học Thái Nguyên.

[3]. Lê Văn Phùng (2018), Cơ sở dữ liệu quan hệ và công nghệ phân

tích –thiết kế , Tái bản lần 1, Nhà xuất bản Thông tin và truyền thông.

[4]. Lê Văn Phùng - Quách Xuân Trưởng, Khai phá dữ liệu (2017), tái

bản lần 1, Nhà xuất bản Thông tin và truyền thông.

[5]. Phạm Hạ Thủy (2006), Một số vấn đề liên quan đến tệp dữ liệu trong

hệ thống cơ sở dữ liệu, Luận án tiến sĩ, Viện CNTT, Viện Hàn lâm Khoa học

và công nghệ Việt Nam.

B-Tiếng Anh

[6]. Han J. and M. Kamber (2006), Data Mining-Concepts and

Techniques (Second Edition). Morgan Kaufmann Publishers.

[7]. B.Liu (1998), integrating classification and association mining, in

proc. Conf. Knowledge discover and data mining p 80-86 nework) .

[8]. Kwok wa Lam (2004) building decision trees using functional

dependencies, proceeding of the international conference on information

technology: coding and computing).

[9]. ZijianZheng (1996), Constructing New Attributes for Dacision Tree

Learning, The thesis for the degree of Doctor of Philosophy, The University of

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn

Sydney)