Luận văn Phân tách cụm danh từ cơ sở tiếng Việt sử dụng mô hình CRFs

i

TRƯỜNG ………………….

KHOA……………………….

----------

Báo cáo tốt nghiệp

Đề tài:

PHÂN TÁCH CỤM DANH TỪ CƠ SỞ TRIẾNG ViỆT SỬ DỤNG MÔ HÌNH CRFs

ii

LỜI CAM ĐOAN

Tôi xin cam đoan, kết quả luận văn hoàn toàn là kết quả của tự bản thân

tôi tìm hiểu, nghiên cứu. Các tài liệu tham khảo được trích dẫn và chú thích đầy

đủ.

Học viên

Nguyễn Thanh Huyền

iii

LỜI CẢM ƠN

Trong suốt thời gian học tập, hoàn thành luận văn tôi đã được các Thầy,

Cô truyền đạt cho các kiến thức cũng như phương pháp nghiên cứu khoa học rất

hữu ích và được gia đình, cơ quan, đồng nghiệp và bạn bè quan tâm, động viên

rất nhiều.

Trước hết, tôi muốn gửi lời cảm đến các Thầy, Cô trong khoa Công nghệ

thông tin- Trường Đại học Công nghệ - Đại học Quốc gia Hà nội đã truyền đạt

các kiến thức quý báu cho tôi trong suốt thời gian học tập tại trường. Đặc biệt,

tôi xin gửi lời cảm ơn sâu sắc tới thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban,

người Thầy đã tận tình chỉ bảo và hướng dẫn về mặt chuyên môn cho tôi trong

suốt quá trình thực hiện luận văn này.

Cũng qua đây, tôi xin gửi lời cảm ơn đến ban giám hiệu trường Trung cấp

kinh tế Hà Nội, nơi tôi đangcông tác đã tạo mọi điều kiện thuận lợi cho tôi trong

thời gian học tập cũng như trong suốt quá trình làm luận văn tốt nghiệp.

Cuối cùng, tôi xin cảm ơn bố mẹ, anh, chị, chồng, con và các bạn bè,

đồng nghiệp đã luôn ủng hộ, động viên tôi rất nhiều để tôi yên tâm nghiên cứu

và hoàn thành luận văn. Trong suốt quá trình làm luận văn, bản thân tôi đã cố

gắng tập trung tìm hiểu, nghiên cứu và tham khảo thêm nhiều tài liệu liên quan.

Tuy nhiên, do thời gian hạn chế và bản thân còn chưa có nhiều kinh nghiệm

trong nghiên cứu khoa học, chắc chắn bản luận văn vẫn còn nhiều thiếu sót. Tôi

rất mong được nhận sự chỉ bảo của các Thầy Cô giáo và các góp ý của bạn bè,

đồng nghiệp để luận văn được hoàn thiện hơn.

Hà Nội, ngày 12 tháng 06 năm 2011

Nguyễn Thanh Huyền

iv

MỤC LỤC

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

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

MỤC LỤC........................................................................................................................ iv

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT....................................... vi

DANH MỤC CÁC BẢNG.........................................................................................vii

DANH MỤC CÁC HÌNH.........................................................................................viii

MỞ ĐẦU............................................................................................................................ 1

Chương 1 - TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ LÝ THUYẾT

TẬP THÔ.......................................................................................................................... 3

1.1. Giới thiệu về khai phá dữ liệu .............................................................. 3

1.1.1 Khám phá tri thức...................................................................................... 3

1.1.2. Khai phá dữ liệu........................................................................................ 4

1.2. Ứng dụng của khai phá dữ liệu ............................................................ 5

1.3. Một số phương pháp khai phá dữ liệu thông dụng................................ 6

1.3.1. Phân lớp (Classification)......................................................................... 6

1.3.2. Phân cụm (Clustering)............................................................................. 8

1.3.3. Luật kết hợp (Association Rules) .......................................................... 9

1.4. Lý thuyết tập thô.................................................................................. 9

1.4.1. Hệ thông tin ............................................................................................. 10

1.4.2. Bảng quyết định...................................................................................... 10

1.4.3. Quan hệ không phân biệt được ........................................................... 12

1.4.4. Xấp xỉ tập hợp......................................................................................... 12

1.5. Kết luận chương 1.............................................................................. 14

Chương 2- CÂY QUYẾT ĐỊNH VÀ CÁC THUẬT TOÁN XÂY DỰNG

CÂY QUYẾT ĐỊNH..................................................................................................... 15

2.1. Tổng quan về cây quyết định ............................................................. 15

2.1.1. Định nghĩa................................................................................................ 15

2.1.2. Thiết kế cây quyết định ......................................................................... 16

2.1.3. Phương pháp tổng quát xây dựng cây quyết định............................. 18

2.1.3. Ứng dụng cây quyết định trong khai phá dữ liệu ............................. 19

2.2. Thuật toán xây dựng cây quyết định dựa vào Entropy........................ 20

2.2.1. Tiêu chí chọn thuộc tính phân lớp....................................................... 20

2.2.2. Thuật toán ID3 ........................................................................................ 21

2.2.3. Ví dụ về thuật toán ID3 ......................................................................... 23

2.3. Thuật toán xây dựng cây quyết định dựa vào độ phụ thuộc của thuộc

tính ........................................................................................................... 28

v

2.3.1. Độ phụ thuộc của thuộc tính theo lý thuyết tập thô ......................... 28

2.3.2. Độ phụ thuộc chính xác  theo lý thuyết tập thô.............................. 28

2.3.3. Tiêu chí chọn thuộc tính để phân lớp.................................................. 28

2.3.4. Thuật toán xây dựng cây quyết định ADTDA.................................. 29

2.3.5. Ví dụ.......................................................................................................... 30

2.4. Thuật toán xây dựng cây quyết định dựa vào Entropy và độ phụ thuộc

của thuộc tính ........................................................................................... 33

2.4.1. Tiêu chí chọn thuộc tính để phân lớp.................................................. 33

2.4.2. Thuật toán FID3 (Fixed Iterative Dichotomiser 3 [5] )................... 34

2.4.3. Ví dụ.......................................................................................................... 35

2.5. Kết luận chương 2.............................................................................. 39

Chương 3 - ỨNG DỤNG KIỂM CHỨNG VÀ ĐÁNH GIÁ.............................. 40

3.1. Giới thiệu bài toán ............................................................................. 40

3.2. Giới thiệu về cơ sở dữ liệu................................................................. 40

3.3. Cài đặt ứng dụng................................................................................ 41

3.4. Kết quả và đánh giá thuật toán........................................................... 42

3.4.1. Mô hình cây quyết định tương ứng với tập dữ liệu Bank_data...... 42

3.4.2. Các luật quyết định tương ứng với tập dữ liệu Bank_data ............. 44

3.4.3. Đánh giá thuật toán ................................................................................ 44

3.4.4. Ứng dụng cây quyết định trong khai phá dữ liệu ............................. 45

3.5. Kết luận chương 3.............................................................................. 46

KẾT LUẬN..................................................................................................................... 47

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

vi

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

CÁC KÝ HIỆU:

S = (U, A)

V_a

Hệ thông tin

Tập các giá trị của thuộc tính a

Quan hệ tương đương của tập thuộc tính B

Lớp tương đương chứa đối tượng u_i

Phân hoạch của U sinh ra bởi quan hệ IND(B)

Bảng quyết định

IND(B)

[u_i]_p

U/B

DT=(U,CD)

B(X )

B-Xấp xỉ dưới của X

B(X )

B-xấp xỉ trên của X

POS_C(d)

Miền C-khẳng định của d

|DT|

|U|

Tổng số các đối tượng trong DT

Lực lượng của tập U

[U]_d

Phân hoạch của U sinh ra bởi quan hệ IND(d)

CÁC CHỮ VIẾT TẮT:

ADTDA

Algorithm for Buiding Decision Tree Based on Dependency

of Attributes

FID3

ID3

IG

Fixed Iterative Dichotomiser 3

Iterative Dichotomiser 3

Information Gain

vii

DANH MỤC CÁC BẢNG

Bảng 1. Hệ thông tin đơn giản......................................................................... 10

Bảng 2. Một bảng quyết định với C={Age, LEMS} và D={Walk}..................... 11

Bảng 3. Dữ liệu huấn luyện.............................................................................. 23

Bảng 4. Bảng các thuộc tính của tập dữ liệu Bank_data................................... 41

Bảng 5. Độ chính xác của các thuật toán ......................................................... 45

viii

DANH MỤC CÁC HÌNH

Hình 1. Quá trình phân lớp dữ liệu – Bước xây dựng mô hình ........................... 7

Hình 2. Quá trình phân lớp dữ liệu – Ước lượng độ chính xác mô hình ............. 8

Hình 3. Quá trình phân lớp dữ liệu –Phân lớp dữ liệu mới ................................ 8

Hình 4. Xấp xỉ tập đối tượng trong Bảng 2 bởi các thuộc tính điều kiện Age và

LEMS ............................................................................................................... 14

Hình 5. Mô tả chung về cây quyết định............................................................. 15

Hình 6. Ví dụ về Cây quyết định....................................................................... 16

Hình 7. Mô hình phân lớp các mẫu mới ........................................................... 19

Hình 8. Cây sau khi chọn thuộc tính Humidity (ID3)........................................ 25

Hình 9. Cây sau khi chọn thuộc tính Outlook (ID3).......................................... 26

Hình 10. Cây kết quả (ID3) .............................................................................. 27

Hình 11. Cây sau khi chọn thuộc tính Humidity (ADTDA) ............................... 31

Hình 12. Cây sau khi chọn thuộc tính Outlook (ADTDA) ................................. 32

Hình 13. Cây kết quả (ADTDA)........................................................................ 33

Hình 14. Cây quyết định sau khi chọn thuộc tính Humidity (FID3) .................. 36

Hình 15. Cây quyết định sau khi chọn thuộc tính Windy (FID3)....................... 38

Hình 16. Cây kết quả (FID3)............................................................................ 39

Hình 17. Dạng cây quyết định ID3................................................................... 42

Hình 18. Dạng cây quyết định ADTDA............................................................. 42

Hình 19. Dạng cây quyết định FID3................................................................. 43

Hình 20. Một số luật của cây quyết định ID3 ................................................... 44

Hình 21. Một số luật của cây quyết định ADTDA............................................. 44

Hình 22. Một số luật của cây quyết định FID3................................................. 44

Hình 23. Giao diện ứng dụng ........................................................................... 46

1

MỞ ĐẦU

 Lý do chọn đề tài

Trong những năm gần đây Công nghệ thông tin phát triển mạnh mẽ và có

những tiến bộ vượt bậc. Cùng với sự phát triển của Công nghệ thông tin là sự

bùng nổ thông tin. Các thông tin tổ chức theo phương thức sử dụng giấy trong

giao dịch đang dần được số hóa, do nhiều tính năng vượt trội mà phương thức

này mang lại như: có thể lưu trữ lâu dài, cập nhật, sửa đổi, tìm kiếm một cách

nhanh chóng. Đó là lý do khiến cho số lượng thông tin số hóa ngày nay đang

tăng dần theo cấp số nhân.

Hiện nay, không một lĩnh vực nào lại không cần đến sự hỗ trợ của công

nghệ thông tin và sự thành công của các lĩnh vực đó phụ thuộc rất nhiều vào

việc nắm bắt thông tin một cách nhạy bén, nhanh chóng và hữu ích. Với nhu cầu

như thế nếu chỉ sử dụng thao tác thủ công truyền thống thì độ chính xác không

cao và mất rất nhiều thời gian. Do vậy việc khai phá tri thức từ dữ liệu trong các

tập tài liệu lớn chứa đựng thông tin phục vụ nhu cầu nắm bắt thông tin có vai trò

hết sức to lớn. Việc khai phá tri thức đã có từ lâu nhưng sự bùng nổ của nó thì

mới chỉ xảy ra trong những năm gần đây. Các công cụ thu thập dữ liệu tự động

và các công nghệ cơ sở dữ liệu được phát triển dẫn đến vấn đề một lượng dữ liệu

khổng lồ được lưu trữ trong cơ sở dữ liệu và trong các kho thông tin của các tổ

chức, cá nhân....Do đó việc khai phá tri thức từ dữ liệu là một trong những vấn

đề đã và đang nhận được nhiều sự quan tâm của các nhà nghiên cứu. Một vấn đề

quan trọng và phổ biến trong kỹ thuật khai phá dữ liệu là phân lớp, nó đã và

đang được ứng dụng rộng rãi trong thương mại, y tế, công nghiệp...

Trong những năm trước đây, phương pháp phân lớp đã được đề xuất,

nhưng không có phương pháp tiếp cận phân loại nào là cao hơn và chính xác

hơn hẳn những phương pháp khác. Tuy nhiên với mỗi phương pháp có một lợi

thế và bất lợi riêng khi sử dụng. Một trong những công cụ khai phá tri thức hiệu

quả hiện nay là sử dụng cây quyết định để tìm ra các luật phân lớp.

Phân lớp sử dụng lý thuyết tập thô, được đề xuất bởi Zdzislaw Pawlak vào

năm 1982, và đã được nghiên cứu rộng rãi trong những năm gần đây. Lý thuyết

tập thô cung cấp cho nhiều nhà nghiên cứu và phân tích dữ liệu với nhiều kỹ

thuật trong khai phá dữ liệu như là các khái niệm đặc trưng bằng cách sử dụng

một số dữ kiện. Nhiều nhà nghiên cứu đã sử dụng lý thuyết tập thô trong các

ứng dụng như phân biệt thuộc tính, giảm số chiều, khám phá tri thức, và phân

2

tích dữ liệu thời gian,... Đây là một công cụ toán học mới được áp dụng trong

khai phá dữ liệu có thể được dùng để lựa chọn thuộc tính để phân nhánh trong

việc xây dựng cấu trúc cây quyết định và có nhiều cách tiếp cận khác nhau để

chọn thuộc tính phân nhánh tối ưu, làm cho cây có chiều cao nhỏ nhất. Chính vì

vậy, trong luận văn này tôi đã tìm hiểu về các phương pháp xây dựng cây quyết

định dựa vào tập thô. Việc ứng dụng cây quyết định để khai phá dữ liệu đã và

đang được tiếp tục tìm hiểu, nghiên cứu. Với mong muốn tìm hiểu và nghiên

cứu về lĩnh vực này, tôi đã chọn đề tài “Ứng dụng cây quyết định trong khai

phá dữ liệu” làm luận văn tốt nghiệp.

 Mục tiêu nghiên cứu

Mục đích của luận văn là nghiên cứu các vấn đề cơ bản của lý thuyết tập

thô, cây quyết định và các thuật toán xây dựng cây quyết định trên hệ thông tin

đầy đủ dựa trên tập thô; cài đặt và đánh giá các thuật toán xây dựng cây quyết

định đã nghiên cứu; bước đầu áp dụng mô hình cây quyết định đã xây dựng vào

trong khai phá dữ liệu (hỗ trợ ra quyết định trong vay vốn).

 Bố cục luận văn

Luận văn gồm 3 chương chính:

Chương 1: Tổng quan về khai phá tri thức và lý thuyết tập thô

Trong chương này trình bày tổng quan về khai phá dữ liệu và lý thuyết tập

thô.

Chương 2: Cây quyết định và các thuật tóan xây dựng cây quyết định.

Trong chương này giới thiệu tổng quan về cây quyết đinh, phương pháp

tổng quát xây dựng cây quyết định và ba thuật toán xây dựng cây quyết định:

ID3, ADTDA, FID3

Chương 3: Thực nghiệm và đánh giá.

Phát biểu bài toán, cài đặt ứng dụng và đánh giá.

3

Chương 1 - TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ

LÝ THUYẾT TẬP THÔ

1.1. Giới thiệu về khai phá dữ liệu

1.1.1 Khám phá tri thức

Trong thời đại bùng nổ công nghệ thông tin, các công nghệ lưu trữ dữ liệu

ngày càng phát triển nhanh chóng tạo điều kiện cho các đơn vị thu thập dữ liệu

nhiều hơn và tốt hơn. Đặc biệt trong lĩnh vực kinh doanh, các doanh nghiệp đã

nhận thức được tầm quan trọng cuả việc nắm bắt và xử lí thông tin. Nó hỗ trợ

các chủ doanh nghiệp trong việc đưa ra các chiến lược kinh doanh kịp thời mang

lại những lợi nhuận to lớn cho doanh nghiệp của mình. Tất cả lí do đó khiến cho

các cơ quan, đơn vị và các doanh nghiệp đã tạo ra một lượng dữ liệu khổng lồ cỡ

Gigabyte thậm chí là Terabyte cho riêng mình. Các kho dữ liệu ngày càng lớn và

tiềm ẩn nhiều thông tin có ích. Sự bùng nổ đó dẫn tới một yêu cầu cấp thiết là

phải có những kĩ thuật và công cụ mới để biến kho dữ liệu khổng lồ kia thành

những thông tin cô đọng và có ích. Khám phá tri thức từ dữ liệu (Knowledge

Discovery from Data - KDD) ra đời như một kết quả tất yếu đáp ứng các nhu

cầu đó.

Quá trình khám phá tri thức từ dữ liệu thông thường gồm các bước chính

sau [2]-[7]:

Bước 1: Xác định vấn đề và lựa chọn nguồn dữ liệu (Problem

Understanding anh Data Understanding)

Trong giai đoạn này các chuyên gia trong lĩnh vực cần phải thảo luận

với các chuyên gia tin học, để xác định được chúng ta mong muốn khám

phá những gì, thống nhất giải pháp cho quá trình khám phá dữ liệu (muốn

có các luật hay muốn phân lớp, phâm cụm dữ liệu…). Đây là một giai đoạn

quan trọng vì nếu xác định sai vấn đề thì toàn bộ quá trình phá sản, nó trở

nên vô ích.

Bước 2: Chuẩn bị dữ liệu (Data preparation)

Bao gồm các quá trình sau:

- Thu thập dữ liệu (data gathering)

4

- Làm sạch dữ liệu (data cleaning)

- Tích hợp dữ liệu ( data integeration)

- Chọn dữ liệu (data selection)

- Biến đổi dữ liệu (data transformation)

Đây cũng là một giai đoạn rất quan trọng vì nếu dữ liệu đầu vào

không chính xác thì hiển nhiên sẽ không thể nào có một kết quả chính xác

được.

Bước 3 : Khai phá dữ liệu (Data Mining)

Đây là bước xác định nhiệm vụ khai phá dữ liệu và lựa chọn kỹ thuật

khai phá dữ liệu. Kết quả của quá trình này sẽ tìm ra các tri thức, mô hình

hay các quy luật tiềm ẩn bên trong dữ liệu.

Bước 4: Đánh giá mẫu (Partern Evalution)

Đánh giá xem tri thức thu được có chính xác và có giá trị hay không,

nếu không có thể quay lại các bước trên. Việc đánh giá này được thực hiện

thông qua các chuyên gia trong lĩnh vực và người dùng là chính chứ không

phải là các chuyên gia tin học.

Bước 5: Biểu diễn tri thức và triển khai (Knowlegde presentation and

Deployment)

Biểu diễn tri thức phát hiện được dưới dạng tường minh, thân thiện và

hữu ích với đa số người dùng và tiến hành đưa tri thức phát hiện được vào

các ứng dụng cụ thể.

1.1.2. Khai phá dữ liệu

Khai phá dữ liệu chỉ là một bước trong quá trình khám phá tri thức từ cơ sở

dữ liệu. Khai phá dữ liệu bao gồm các giai đoạn sau [7]:

Giai đoạn 1: Gom dữ liệu (Gathering)

Đây là bước tập hợp các dữ liệu được khai thác trong một cơ sở dữ liệu,

một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web.

Giai đoạn 2: Trích lọc dữ liệu (Selection)

5

Ở giai đoạn này dữ liệu được lựa chọn hoặc phân chia theo một số tiêu

chuẩn nào đó, ví dụ chọn tất cả những người có tuổi đời từ 25 – 35 và có trình

độ đại học.

Giai đoạn 3: Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu (Cleansing,

Pre-processing and Preparation)

Giai đoan thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là một

bước rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thường mắc phải

trong khi gom dữ liệu là tính không đủ chặt chẽ, logíc. Vì vậy, dữ liệu thường

chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Ví dụ: tuổi =

673. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói

trên. Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị.

Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không được “làm

sạch - tiền xử lý - chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch nghiêm

trọng.

Giai đoạn 4: Chuyển đổi dữ liệu (Transformation)

Dữ liệu sẽ được chuyển đổi phù hợp với mục đích khai thác.

Giai đoạn 5: Phát hiện và trích mẫu dữ liệu (Pattern Extraction and

Discovery)

Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để trích ra các

mẫu từ dữ liệu. Thuật toán thường dùng là nguyên tắc phân loại, nguyên tắc kết

hợp hoặc các mô hình dữ liệu tuần tự,. v.v.

Giai đoạn 6: Đánh giá kết quả mẫu (Evaluation of Result)

Đây là giai đoạn cuối trong quá trình khai phá dữ liệu. Ở giai đoạn này, các

mẫu dữ liệu được chiết xuất ra bởi phần mềm khai phá dữ liệu. Không phải bất

cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì vậy, cần

phải ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức (Knowlege)

cần chiết xuất ra.

1.2. Ứng dụng của khai phá dữ liệu

Hiện nay, kĩ thuật khai phá dữ liệu đang được áp dụng một cách rộng rãi

trong rất nhiều lĩnh vực kinh doanh và đời sống khác nhau như marketing, tài

chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet, …

6

+ Y học và chăm sóc sức khỏe : chẩn đoán bệnh trong y tế dựa trên kết

quả xét nghiệm đã giúp cho bảo hiểm y tế Australia phát hiện ra nhiều trường

hợp xét nghiệm không hợp lí tiết kiệm được 1 triệu $/năm.

+ Marketing: IBM Surf – Aid đã áp dụng khai phá dữ liệu vào phân tích

các lần đăng nhập Web vào các trang có liên quan đến thị trường để phát hiện sở

thích khách hàng, từ đó đánh giá hiệu quả của việc tiếp thị qua Web và cải thiện

hoạt động của các Website; Trang Web mua bán qua mạng Amazon cũng tăng

doanh thu nhờ áp dụng Khai phá dữ liệu trong việc phân tích sở thích mua bán

của khách hàng…

+ Tài chính và thị trường chứng khoán: Áp dụng vào việc phân tích các

thẻ tín dụng tiêu biểu của các khách hàng, phân đoạn tài khoản nhận được, phân

tích đầu tư tài chính như chứng khoán, giấy chứng nhận, và các quỹ tình thương,

đánh giá tài chính, và phát hiện kẻ gian, .... Dự báo giá của các loại cổ phiếu

trong thị trường chứng khoán, ...

+ Bảo hiểm: Áp dụng vào việc phân tích mức độ rủi ro xảy ra đối với từng

loại hàng hoá, dịch vụ hay chiến lược tìm kiếm khách hàng mua bảo hiểm, ...

+ Quá trình sản xuất: Các ứng dụng giải quyết sự tối ưu của các nguồn tài

nguyên như các máy móc, nhân sự, và nguyên vật liệu; thiết kế tối ưu trong quá

trình sản xuất, bố trí phân xưởng và thiết kế sản phẩm, chẳng hạn như quá trình

tự động dựa vào yêu cầu khách hàng...

1.3. Một số phương pháp khai phá dữ liệu thông dụng

Nhiệm vụ chính của khai phá dữ liệu là mô tả và dự đoán. Trong đó mô tả

nhằm biểu thị các đặc điểm chung của dữ liệu có trong CSDL, còn dự đoán

nhằm thực hiện, suy luận trên dữ liệu hiện có để đưa ra các kết luận của dự đoán

đó. Dưới đây giới thiệu 3 phương pháp thông dụng nhất là: phân cụm dữ liệu,

phân lớp dữ liệu và luật kết hợp.

1.3.1. Phân lớp (Classification)

Mục tiêu của phương pháp phân lớp dữ liệu là dự đoán nhãn lớp cho các

mẫu dữ liệu. Quá trình phân lớp dữ liệu thường gồm 2 bước:

Bước 1: Xây dựng mô hình

Trong bước này, một mô hình sẽ được xây dựng dựa trên việc phân tích

các mẫu dữ liệu sẵn có. Đầu vào của quá trình này là một tập dữ liệu có cấu trúc

7

được mô tả bằng các thuộc tính và được tạo ra từ tập các bộ giá trị của các thuộc

tính đó. Mỗi bộ giá trị được gọi chung là một mẫu (sample). Trong tập dữ liệu

này, mỗi mẫu được giả sử thuộc về một lớp định trước, lớp ở đây là giá trị của

một thuộc tính được chọn làm thuộc tính gán nhãn lớp hay thuộc tính quyết

định. Đầu ra của bước này thường là các quy tắc phân lớp dưới dạng luật dạng

if-then, cây quyết định, công thức logic, hay mạng nơron. Quá trình này được

mô tả như trong hình 1

Hình 1. Quá trình phân lớp dữ liệu – Bước xây dựng mô hình

Bước 2: Sử dụng mô hình đã xây dựng để phân lớp dữ liệu

Trong bước này việc đầu tiên là phải làm là tính độ chính xác của mô

hình. Nếu độ chính xác là chấp nhận được mô hình sẽ được sử dụng để dự đoán

nhãn lớp cho các mẫu dữ liệu khác trong tương lai.

Độ chính xác mang tính chất dự đoán của mô hình phân lớp vừa tạo ra

được ước lượng. Holdout là một kỹ thuật đơn giản để ước lượng độ chính xác

đó. Kỹ thuật này sử dụng một tập dữ liệu kiểm tra với các mẫu đã được gán

nhãn lớp. Các mẫu này được chọn ngẫu nhiên và độc lập với các mẫu trong tập

dữ liệu đào tạo. Độ chính xác của mô hình trên tập dữ liệu kiểm tra đã đưa là tỉ

lệ phần trăm các các mẫu trong tập dữ liệu kiểm tra được mô hình phân lớp đúng

(so với thực tế).

8

Hình 2. Quá trình phân lớp dữ liệu – Ước lượng độ chính xác mô hình

Hình 3. Quá trình phân lớp dữ liệu –Phân lớp dữ liệu mới

1.3.2. Phân cụm (Clustering)

Mục tiêu chính phân cụm dữ liệu là nhóm các đối tượng tương tự nhau

trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một lớp là

tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng.

Phân cụm dữ liệu là một ví dụ của phương pháp học không giám sát. Trong

phương pháp này ta sẽ không thể biết kết quả các cụm thu được sẽ như thế nào khi

bắt đầu quá trình. Vì vậy, cần có một chuyên gia về lĩnh vực đó để đánh giá các cụm

thu được.

Phân cụm dữ liệu được sử dụng nhiều trong các ứng dụng về phân loại thị

trường, phân loại khách hàng, nhận dạng mẫu, phân loại trang web,… Ngoài ra

9

phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lý cho các

thuật toán khai phá dữ liệu khác.

1.3.3. Luật kết hợp (Association Rules)

Luật kết hợp là luật mà trong đó phản ánh mối quan hệ kết hợp chặt chẽ

trong một tập các đối tượng trong một CSDL [2].

Mục tiêu của phương pháp này là phát hiện và đưa ra mối liên hệ giữa các

giá trị dữ liệu trong CSDL. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật

kết hợp tìm được. Khai phá luật kết hợp được thực hiện qua 2 bước:

 Bước 1: Tìm tất cả các tập mục phổ biến, một văn bản phổ biến được xác

định qua độ hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu.

 Bước 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải

thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu.

1.4. Lý thuyết tập thô

Lý thuyết tập thô (rough set theory) lần đầu tiên được đề xuất bởi

Z.Pawlak vào những năm đầu thập niên 1980. Phương pháp này đóng vai trò hêt

sức quan trọng trong lĩnh vực trí tuệ nhân tạo và các ngành liên quan đến nhận

thức, đặc biệt là trong lĩnh vực học máy, thu nhận tri thức, phân tích quyết định,

phát hiện và khám phá tri thức từ cơ sở dữ liệu, các hệ chuyên gia, các hệ hỗ trợ

quyết định, lập luận dựa trên quy nạp [1]-[8].

Các lĩnh vực ứng dụng trong tập thô bao gồm:

- Chẩn đoán y học (medical diagnosis)

- Nghiên cứu dược lý ((pharmacology)

- Dự đoán thị trường cổ phiếu và phân tích dữ liệu tài chính

- Kinh doanh tiền tệ (banking)

- Nghiên cứu thị trường

- Các hệ thu nhận và lưu trữ thông tin

- Nhận dạng mẫu, gồm nhận dạng tiếng nói và chữ viết tay

- Thiết kế hệ điều khiển ( control system design)

- Xử lý ảnh (image processing)

10

- Thiết kế logic số(digital logic design)

Sau đây chúng ta sẽ nghiên cứu các khái niệm cơ bản của lý thuyết tập thô.

Đây là những kiến thức quan trọng cho việc áp dụng tập thô để xây dựng cây

quyết định.

1.4.1. Hệ thông tin

Trong hầu hết các hệ quản trị cơ sở dữ liệu thông thường thì thông tin

thường được biểu diễn dưới dạng các bảng, trong đó mỗi bảng biểu diễn thông

tin về một đối tượng, mỗi cột biểu diễn thông tin về một thuộc tính của đối

tượng. Từ đầu những năm 80 Pawlak đã định nghĩa một khái niệm mới là hệ

thông tin (infomation system) dựa trên khái niệm bảng truyền thống như sau

[4]:

Định nghĩa 1.1. [1]-[8] Hệ thông tin là một cặp S = (U, A) trong đó U

là tập hữu hạn khác rỗng các đối tượng (được gọi là tập vũ trụ các đối tượng) và

A là tập hữu hạn khác rỗng các thuộc tính. Với mọi aA ta kí hiệu V_alà tập giá

trị của thuộc tính a. Nếu xU và aA thì ta kí hiệu x(a) là giá trị thuộc tính a

của đối tượng x.

Ví dụ 1.1. [8] Bảng dữ liệu dưới đây là một hệ thông tin với 7 đối tượng

và 2 thuộc tính.

Age

LEMS

50

x₁

x₂

x₃

x₄

x₅

x₆

x₇

16-30

31-45

46-60

16-30

46-60

0

1-25

26-49

Bảng 1. Hệ thông tin đơn giản

1.4.2. Bảng quyết định

Để có thể biểu diễn một dữ liệu thực tế, trong đó có những thuộc tính quyết

đinh, chúng ta xét một trường hợp đặc biệt của hệ thông tin được gọi là bảng

quyết định được định nghĩa như sau:

11

Định nghĩa 1.2: Bảng quyết định (hệ quyết định) là một dạng đặc biệt của

hệ thông tin, trong đó tập các thuộc tính A bao gồm hai tập con rời nhau là tập

thuộc tính điều kiện C và tập các thuộc tính quyết định D. Như vậy bảng quyết

định là một hệ thông tin có dạng DT= (U, C  D) với C  D =  [1].

Ví dụ 1.2. Bảng 2 dưới đây thể hiện một bảng quyết định, trong đó tập

thuộc tính điều kiện như ở Bảng 1 và thuộc tính quyết định {Walk} được thêm

vào nhận hai giá trị là Yes và No [8].

Walk

Yes

No

Age

LEMS

50

x₁

x₂

x₃

x₄

x₅

x₆

x₇

16-30

31-45

46-60

16-30

46-60

0

1-25

26-49

No

Yes

No

Yes

No

Bảng 2. Một bảng quyết định với C={Age, LEMS} và D={Walk}

Định nghĩa 1.3. Miền khẳng định

Cho bảng quyết định DT = {U,CD}. Tập POS_C(D) =

C(X ) được



XU / IND(D)

gọi là C-miền khẳng định của D. Nói cách khác, uPOS_C(D) nếu và chỉ nếu

u(C) = v(C) kéo theo u(D) = v(D) với mọi vU [1].

Một thuộc tính c  C được gọi là không cần thiết trong DT nếu POS_C(D)

= POS_C-{c}(D). Ngược lại, c là cần thiết trong DT.

Ta nói bảng quyết định DT = (U, C  {d}) là độc lập nếu mọi thuộc tính

c  C đều cần thiết trong DT.

Định nghĩa 1.4. Xét bảng quyết định DT = (U, C {d}) và hai đối tượng

x, y  U. Ta nói x và y mâu thuẫn nhau trong DT nếu x(C) = y(C) nhưng x(d) ≠

y(d) [3].

Đối tượng x được gọi là nhất quán trong DT nếu không tồn tại một đối

tượng y khác mâu thuẫn với x. DT được gọi là nhất quán nếu mọi đối tượng

trong xU đều là nhất quán.

12

1.4.3. Quan hệ không phân biệt được

Một trong những đặc điểm cơ bản của lý thuyết tập thô là dùng để lưu giữ

và xử lý các dữ liệu trong đó có sự mập mờ, không phân biệt được. Trong một

hệ thông tin theo định nghĩa trên cũng có thể có những đối tượng không phân

biệt được.

Định nghĩa 6: Cho hệ thông tin S = (U, A). Với mỗi tập thuộc tính B  A

đều tạo ra tương ứng một quan hệ tương đương, kí hiệu IND(B) [1]-[8]:

IND(B) = {(x,x’)  U²|  a B, x(a) = x’(a) }

IND(B) được gọi là quan hệ B-không phân biệt được. Nếu (x,x’)  IND(B) thì

các đối tượng x và x’ là không thể phân biệt được với nhau qua tập thuộc tính B.

Với mọi đối tượng x  U, lớp tương đương của x trong quan hệ IND(B) được kí

hiệu bởi [x]_Blà tập tất cả các đối tượng có quan hệ IND(B) với x.

Quan hệ B- không phân biệt được phân hoạch tập đối tượng U thành các

lớp tương đương, kí hiệu là U/ IND(B) hay U/B, tức là U/B = {[x]_P| x  U}.

Ví dụ 1.3. [8] Xét hệ thông tin cho trong Bảng 1

Xét thuộc tính B = {LEMS}, ta có phân hoạch của tập U sinh bởi quan hệ

tương đương IND(B) là:

U/B = {{x₁}, {x₂}, {x₃, x₄}, {x₅, x₆, x₇}}

Khi đó, ta nói các cặp đối tượng x₃, x₄và x₅, x₆là không phân biệt qua tập

thuộc tính {LEMS} vì chúng thuộc cùng một lớp tương đương định bởi quan hệ

IND(B).

Nếu ta xét B = {Age, LEMS}, ta có:

U/B = {{x₁}, {x₂}, {x₃, x₄}, {x₅, x₇},{ x₆}}

Khi đó x₅và x₆là phân biệt được qua tập thuộc tính {Age, LEMS} vì

chúng không thuộc cùng lớp tương đương định bởi quan hệ IND(B).

1.4.4. Xấp xỉ tập hợp

Ta thấy ở bảng 2 khái niệm Walk không thể định nghĩa rõ ràng qua 2

thuộc tính điều kiện Age và LEMS vì có x₃, x₄thuộc cùng một lớp tương đương

tạo bởi 2 thuộc tính Age và LEMS nhưng lại có giá trị khác nhau tại thuộc tính

13

Walk. Vì vậy, nếu một đối tượng nào đó có (Age,LEMS) = (31-45, 1-25) thì ta

vẫn không thể biết chắc chắn giá trị của nó tại thuộc tính Walk là Yes hay No.

Vì vậy, ta thấy khái niệm Walk không được mô tả rõ ràng. Tuy nhiên, căn cứ

vào tập thuộc tính {Age, LEMS} ta vẫn có thể chỉ ra được chắc chắn một số đối

tượng có Walk là Yes, một số đối tượng có Walk là No, còn lại là các đối tượng

thuộc tính về biên của hai giá trị Yes và No, cụ thể:

. Nếu đối tượng nào có giá trị tại tập thuộc tính {Age,LEMS} thuộc tập

{{16-30, 50}, {16-30, 26-49}} thì có Walk là Yes.

. Nếu đối tượng nào có giá trị tại tập thuộc tính {Age,LEMS} thuộc tập

{{16-30, 0}, {46-60, 26-49}} thì có Walk là No.

. Nếu đối tượng nào có giá trị tại tập thuộc tính {Age,LEMS} = {31-45, 1-

25} thì có Walk là Yes hoặc No.

Chính vì vậy ta có khái niệm xấp xỉ tập hợp như sau:

Định nghĩa 1.3. [10] Cho hệ quyết định DT = (U, C D), tập thuộc tính BC,

tập đối tượng XU. Chúng ta có thể xấp xỉ tập hợp X bằng cách sử dụng các

thuộc tính trong B từ việc xây dựng các tập hợp B-xấp xỉ dưới và B-xấp xỉ trên

được định nghĩa như sau:

B-xấp xỉ dưới của tập X: BX = {x  U | [x]_B X}

B-xấp xỉ trên của tập X: B X = {x  U | [x]_BX ≠ 

Tập hợp BX là tập các đối tượng trong U mà sử dụng các thuộc tính trong

B ta có thể biết chắc chắn được chúng là các phần tử của X.

Tập hợp B X là các đối tượng trong U mà sử dụng các thuộc tính trong B

ta chỉ có nói rằng chúng có thể là các phần tử của X.

Tập BN_B(X) = B X \BX được gọi là B-biên của tập X, nó chứa các đối

tượng mà sử dụng các thuộc tính của B ta không thể xác định được chúng có

thuộc tập X hay không.

Tập U\ B X được gọi là B-ngoài của tập X, gồm những đối tượng mà sử

dụng tập thuộc tính B ta biết chắc chắn chúng không thuộc tập X.

Một tập hợp được gọi là thô nếu đường biên của nó là không rỗng, ngược

lại ta nói tập này là rõ.

Ví dụ 1.4. Xét hệ quyết định cho trong Bảng 2

14

Xét tập đối tượng X = {x U | x(Walk) = Yes} = {x₁, x₄, x₆} và tập thuộc

tính B = {Age, LEMS}. Khi đó ta có [8]:

U/B ={{x₁}, {x₂}, {x₃, x₄}, {x₅, x₇},{ x₆}}

BX = {x U | [x]_B X} = {x₁, x₆}

B X = {x  U | [x]_BX ≠ } = {u₁, u₂, u₅, u₇, u₈}

Hình 4. Xấp xỉ tập đối tượng trong Bảng 2 bởi các thuộc tính điều kiện Age và

LEMS

1.5. Kết luận chương 1

+ Chương này đã giới thiệu tổng quan về khai phá dữ liệu, ứng dụng của

khai phá dữ liệu, và giới thiệu một số phương pháp khai phá dữ liệu thông dụng.

+ Trình bày tổng quan về lý thuyết tập thô bao gồm hệ thống thông tin,

quan hệ không phân biệt được, các tập thô, bảng quyết định,… Và đồng thời

trình bày các ví dụ cụ thể để minh họa các khái niệm này.

15

Chương 2- CÂY QUYẾT ĐỊNH VÀ CÁC THUẬT TOÁN XÂY

DỰNG CÂY QUYẾT ĐỊNH

2.1. Tổng quan về cây quyết định

Cây quyết định là công cụ dùng để phân lớp các dữ liệu, nó có cấu trúc

cây. Mỗi cây quyết định là một sự tượng trưng cho một sự quyết định của một

lớp các dữ kiện nào đó. Mỗi nút trong cây là tên của một lớp hay một phép thử

thuộc tính cụ thể nào đó, phép thử này phân chia không gian trạng thái các dữ

kiện tại nút đó thành các kết quả có thể đạt được của phép thử. Mỗi tập con được

phân chia của phép thử là không gian con của các sự kiện, nó tương ứng với một

vấn đề con của sự phân lớp. Các cây quyết định được dùng để hỗ trợ quá trình ra

quyết định.

2.1.1. Định nghĩa

Cây quyết định là một cây mà mỗi nút của cây là:

- Nút lá hay còn gọi là nút trả lời biểu thị cho một lớp các trường hợp mà

nhãn của nó là tên của lớp.

- Nút không phải là nút lá hay còn gọi là nút trong, nút định phép kiểm tra

các thuộc tính, nhãn của nút này là tên của thuộc tính và có một nhánh nối nút này

đến các cây con ứng với mỗi kết quả có thể có phép thử. Nhãn của nhánh này là

các giá trị của thuộc tính đó. Nút trên cùng gọi là nút gốc.

Nút gốc

Các nhánh

Nút trong

Nút lá

Nút trong

Nút lá

Hình 5. Mô tả chung về cây quyết định

Để phân lớp mẫu dữ liệu chưa biết, giá trị các thuộc tính của mẫu được đưa

vào kiểm tra trên cây quyết định. Mỗi mẫu tương ứng có một đường đi từ gốc đến

lá và lá biểu diễn dự đoán giá trị phân lớp của mẫu đó.

16

Ví dụ 2.1: Cây quyết định

Humidity

high

low

Normal

Temp

Outlook

TRUE

mild

hot

Overcast

Sunn

Rainy

TRUE

FALSE

TRUE

FALSE

Hình 6. Ví dụ về Cây quyết định

2.1.2. Thiết kế cây quyết định

2.1.2.1. Xử lý dữ liệu

Trong thế giới thực, nói chung dữ liệu thô chắc chắn có mức độ nhiễu.

Điều này có các nguyên nhân khác nhau như là dữ liệu lỗi, dữ liệu có đại lượng

không chính xác, .... Do đó, chúng ta thường tiền xử lý (nghĩa là, “làm sạch”) để

cực tiểu hoá hay huỷ bỏ tất cả dữ liệu thô bị nhiễu. Các giai đoạn tiền xử lý này

cũng có thể biến đổi dữ liệu thô hiển thị hữu ích hơn, như hệ thống thông tin.

Khi nhiều bước tiền xử lý ứng dụng hiệu quả, nó sẽ giúp cải tiến hiệu quả phân

lớp.

Các công việc cụ thể của tiền xử lý dữ liệu bao gồm những công việc như:

- Filtering Attributes: Chọn các thuộc tính phù hợp với mô hình.

- Filtering samples: Lọc các mẫu (instances, patterns) dữ liệu cho

mô hình.

- Transformation: Chuyển đổi dữ liệu cho phù hợp với các mô hình

như chuyển đổi dữ liệu từ numeric sang nomial

- Discretization (rời rạc hóa dữ liệu): Nếu bạn có dữ liệu liên tục

nhưng có một số thuật toán chỉ áp dụng cho các dữ liệu rời rạc

(như ID3, ADTDA,…) thì bạn phải thực hiện việc rời rạc hóa dữ

liệu.

17

2.1.2.2. Tạo cây

Cây quyết định được tạo thành bằng cách lần lượt chia (đệ quy) một tập

dữ liệu thành các tập dữ liệu con, mỗi tập con được tạo thành chủ yếu từ các

phần tử của cùng một lớp.

Các nút (không phải là nút lá) là các điểm phân nhánh của cây. Việc phân

nhánh tại các nút có thể dựa trên việc kiểm tra một hay nhiều thuộc tính để xác

định việc phân chia dữ liệu.

2.1.2.3. Tiêu chuẩn tách

Việc lựa chọn chủ yếu trong các thuật toán phân lớp dựa vào cây quyết

định là chọn thuộc tính nào để kiểm tra tại mỗi nút của cây. Chúng ta mong

muốn chọn thuộc tính sao cho việc phân lớp tập mẫu là tốt nhất. Như vậy chúng

ta cần phải có một tiêu chuẩn để đánh giá vấn đề này. Có rất nhiều tiêu chuẩn

được đánh giá được sử dụng đó là:

+ Lượng thông tin thu thêm IG (Information Gain, thuật toán ID3 của

John Ross Quilan [9]).

+ Độ phụ thuộc của thuộc tính quyết định vào thuộc tính điều kiện theo

nghĩa lí thuyết tập thô của Zdzisław Pawlak [3]-[10]

Các tiêu chuẩn trên sẽ được trình bày trong các thuật toán xây dựng cây

quyết định ở các phần dưới đây.

2.1.2.4. Tiêu chuẩn dừng

Đây là phần quan trọng trong cấu trúc phân lớp của cây quyết định nhằm

chia một nút thành các nút con.

Chúng ta tập trung một số tiêu chuẩn dừng chung nhất được sử dụng trong

cây quyết định. Tiêu chuẩn dừng truyền thống sử dụng các tập kiểm tra. Chúng

ta kiểm tra cây quyết định trong suốt qúa trình xây dựng cây với tập kiểm tra và

dừng thuật toán khi xảy ra lỗi. Một phương pháp khác sử dụng giá trị ngưỡng

cho trước để dừng chia nút. Chúng ta có thể thay ngưỡng như là giảm nhiễu, số

các mẫu trong một nút, tỉ lệ các mẫu trong nút, hay chiều sâu của cây, ...

2.1.2.5. Tỉa cây

Trong giai đoạn tạo cây chúng ta có thể giới hạn việc phát triển của cây

bằng số bản tin tối thiểu tại mỗi nút, độ sâu tối đa của cây hay giá trị tối thiểu

của lượng thông tin thu thêm.

Sau giai đoạn tạo cây chúng ta có thể dùng phương pháp “Độ dài mô tả

ngắn nhất” (Minimum Description Length) hay giá trị tối thiểu của IG để tỉa cây

18

(chúng ta có thể chọn giá trị tối thiểu của IG trong giai đoạn tạo cây đủ nhỏ để

cho cây phát triển tương đối sâu, sau đó lại nâng giá trị này lên để tỉa cây).

2.1.3. Phương pháp tổng quát xây dựng cây quyết định

Quá trình xây dựng một cây quyết định cụ thể bắt đầu bằng một nút rỗng

bao gồm toàn bộ các đối tượng huấn luyện và làm như sau [3]:

1. Nếu tại nút hiện thời, tất cả các đối tượng huấn luyện đều thuộc vào

một lớp nào đó thì cho nút này thành nút lá có tên là nhãn lớp chung của các

đối tượng.

2. Trường hợp ngược lại, sử dụng một độ đo, chọn thuộc tính điều kiện

phân chia tốt nhất tập mẫu huấn luyện có tại nút.

3. Tạo một lượng nút con của nút hiện thời bằng số các giá trị khác nhau

của thuộc tính được chọn. Gán cho mỗi nhánh từ nút cha đến nút con một giá trị

của thuộc tính rồi phân chia các các đối tượng huấn luyện vào các nút con tương

ứng.

4. Nút con t được gọi là thuần nhất, trở thành lá, nếu tất cả các đối tượng

mẫu tại đó đều thuộc vào cùng một lớp. Lặp lại các bước 1-3 đối với mỗi nút

chưa thuần nhất.

Trong các thuật toán cơ sở xây dựng cây quyết định chỉ chấp nhận các

thuộc tính tham gia vào quá trình phân lớp có giá trị rời rạc, bao gồm cả thuộc

tính được dùng để dự đoán trong quá trình học cũng như các thuộc tính được sử

dụng để kiểm tra tại mỗi nút của cây. Do đó trong trường hợp các thuộc tính có

giá trị liên tục có thể dễ dàng loại bỏ bằng cách phân mảnh tập giá trị liên tục

của thuộc tính thành một tập rời các khoảng.

Việc xây dựng cây quyết định được tiến hành một cách đệ qui, lần lượt từ

nút gốc xuống tới tận các nút lá. Tại mỗi nút hiện hành đang xét, nếu kiểm tra

thấy thoả điều kiện dừng: thuật toán sẽ tạo nút lá. Nút này được gán một giá trị

của nhãn lớp tùy điều kiện dừng được thoả mãn. Ngược lại, thuật toán tiến hành

chọn điểm chia tốt nhất theo một tiêu chí cho trước, phân chia dữ liệu hiện hành

theo điều kiện chia này.

Sau bước phân chia trên, thuật toán sẽ lặp qua tất cả các tập con (đã được

chia) và tiến hành gọi đệ qui như bước đầu tiên với dữ liệu chính là các tập con

này.

19

Trong bước 3, tiêu chuẩn sử dụng lựa chọn thuộc tính được hiểu là một số

đo độ phù hợp, một số đo đánh giá độ thuần nhất, hay một quy tắc phân chia tập

mẫu huấn luyện.

2.1.3. Ứng dụng cây quyết định trong khai phá dữ liệu

Sau khi đã xây dựng thành công cây quyết định ta sử dụng kết quả từ mô

hình cây quyết định đó. Đây là bước sử dụng mô hình để phân lớp dữ liệu hoặc

rút ra các tri thức trong phương pháp khai phá dữ liệu bằng phương pháp phân

lớp.

2.1.3.1. Xác định lớp của các mẫu mới

Trên cơ sở đã biết giá trị của các thuộc tính của các mẫu X₁, X₂, …, X_nta

xác định thuộc tính quyết định (hay phân lớp) Y của đối tượng đó (có thể dùng

kỹ thuật này để nhận dạng mẫu, dự báo, …)

Cây quyết

định

Dữ liệu

huấn luyện

Dữ liệu

cụ thể

Kết quả ?

(Sunny, True, Cool, High)

Hình 7. Mô hình phân lớp các mẫu mới

2.1.3.2. Rút ra các tri thức hay luật từ cây

Với mục đích và nhiệm vụ chính của việc khai phá dữ liệu là phát hiện ra

các quy luật, các mô hình từ trong CSDL. Từ mô hình thu được ta rút ra các tri

thức hay các quy luật dưới dạng cây hoặc các luật dưới dạng “If … Then…”.

Hai mô hình trên là tương đương, chúng có thể được chuyển đổi qua lại giữa các

mô hình đó với nhau.

20

Ví dụ 2.2:

Một trong các luật rút ra từ cây trong ví dụ 2.1 là

+Luật 1:

IF(Humidity: high) AND (Outlook: rainy) THEM (=> Quyết định: False)

+Luật 2:

IF(Humidity: high) AND (Outlook: sunny) THEM (=> Quyết định: False)

+Luật 3:

IF(Humidity: high) AND (Outlook: Overcast) THEN (=> Quyết định: True)

…

Từ đây ta sử dụng các luật này để hỗ trợ quá trình ra các quyết định, dự

đoán, …

2.2. Thuật toán xây dựng cây quyết định dựa vào Entropy

2.2.1. Tiêu chí chọn thuộc tính phân lớp

Tiêu chí để đánh giá tìm điểm chia là rất quan trọng, chúng được xem là

một tiêu chuẩn “heuristic” để phân chia dữ liệu. Ý tưởng chính trong việc đưa ra

các tiêu chí trên là làm sao cho các tập con được phân chia càng trở nên “trong

suốt” (tất cả các bộ thuộc về cùng một nhãn) càng tốt.

Thuật toán dùng độ đo lượng thông tin thu thêm (information IG - IG) để

xác định điểm chia [9]. Độ đo này dựa trên cơ sở lý thuyết thông tin của nhà

toán học Claude Shannon, độ đo này được xác như sau:

Xét bảng quyết định DT = (U, C  {d} ), số giá trị (nhãn lớp) có thể của d

là k. Khi đó Entropy của tập các đối tượng trong DT được định nghĩa bởi:

k

Entropy(U)   p log p



i

2

i

i1

trong đó p_ilà tỉ lệ các đối tượng trong DT mang nhãn lớp i.

Lượng thông tin thu thêm (Information Gain - IG) là lượng Entropy còn

lại khi tập các đối tượng trong DT được phân hoạch theo một thuộc tính điều

kiện c nào đó. IG xác định theo công thức sau:

|U_v|

IG(U,c)  Entropy(U) 

Entropy(U_v)

 _{|U |}

vV_c

21

trong đó V_clà tập các giá trị của thuộc tính c, U_vlà tập các đối tượng trong DT

có giá trị thuộc tính c bằng v. IG(U, c) được John Ross Quinlan [9] sử dụng làm

độ đo lựa chọn thuộc tính phân chia dữ liệu tại mỗi nút trong thuật toán xây

dựng cây quyết định ID3. Thuộc tính được chọn là thuộc tính cho lượng thông

tin thu thêm lớn nhất.

2.2.2. Thuật toán ID3

Thuật toán ID3 – Iterative Dichotomiser 3 [9] là thuật toán dùng để xây

dựng cây quyết định được John Ross Quinlan trình bày. Ý tưởng chính của thuật

toán ID3 là để xây dựng cây quyết định bằng cách ứng dụng từ trên xuống (Top-

Down), bắt đầu từ một tập các đối tượng và các thuộc tính của nó. Tại mỗi nút

của cây một thuộc tính được kiểm tra, kết quả của phép kiểm tra này được sử

dụng để phân chia tập đối tượng theo kết quả kiểm tra trên. Quá trình này được

thực hiện một cách đệ quy cho tới khi tập đối tượng trong cây con được sinh ra

thuần nhất theo một tiêu chí phân lớp nào đó, hay các đối tượng đó thuộc cùng

một dạng giống nhau nào đó. Các lớp hay các dạng này được gọi là nhãn của nút

lá của cây, còn tại mỗi nút không phải là nút lá thì nhãn của nó là tên thuộc tính

được chọn trong số các thuộc tính được dùng để kiểm tra có giá trị IG lớn nhất.

Đại lượng IG được tính thông qua hàm Entropy. Như vậy, IG là đại lượng được

dùng để đưa ra độ ưu tiên cho thuộc tính nào được chọn trong quá trình xây

dựng cây quyết định.

Giả mã của thuật toán ID3 như sau:

Dữ liệu vào: Bảng quyết định DT = (U, C  {d})

Dữ liệu ra: Mô hình cây quyết định

Function Create_tree (U, C, {d})

Begin

If tất cả các mẫu thuộc cùng nhãn lớp d_ithen

return một nút lá được gán nhãn d_i

else if C = null then

return nút lá có nhãn d_jlà lớp phổ biến nhất trong DT

else begin

bestAttribute:= getBestAttribute(U, C);

// Chọn thuộc tính tốt nhất để chia

22

C := C- {bestAttribute};

//xóa bestAttribute khỏi tập thuộc tính

Với mỗi giá trị v in bestAttribute

begin

U_v:= [U]_v;

//U_vlà phân hoạch của U theo thuộc tính

//bestAttribute có giá trị là v

ChildNode:=Create_tree(U_V, C, {d});

//Tạo 1 nút con

Gắn nút ChildNode vào nhánh v;

end

End

Giả mã của hàm getBestAttribute như sau:

Dữ liệu vào: Bảng quyết định DT = (U, C{d})

Dữ liệu ra: Thuộc tính điều kiện tốt nhất

Function getBestAttribute (U, C);

Begin

maxIG := 0;

Với mỗi c in C

begin

tg : = IG(U, c);

// Tính lượng thông tin thu thêm IG(U,c)

If (tg > max IG) then

begin

maxIG := tg;

kq := c;

end

return kq;

//Hàm trả về thuộc tính có lượng thông tin thu thêm IG là lớn nhất

End