Nghiên cứu kỹ thuật cây quyết định và xây dựng ứng dụng hỗ trợ học sinh trường thpt võ nguyên giáp chọn nghề

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM

ĐÀO THỊ MỸ VÂN

NGHIÊN CỨU KỸ THUẬT CÂY QUYẾT ĐỊNH

VÀ XÂY DỰNG ỨNG DỤNG HỖ TRỢ HỌC SINH

TRƯỜNG THPT VÕ NGUYÊN GIÁP CHỌN NGHỀ

TÓM TẮT

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

Đà Nẵng – Năm 2019

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM

ĐÀO THỊ MỸ VÂN

NGHIÊN CỨU KỸ THUẬT CÂY QUYẾT ĐỊNH

VÀ XÂY DỰNG ỨNG DỤNG HỖ TRỢ HỌC SINH

TRƯỜNG THPT VÕ NGUYÊN GIÁP CHỌN NGHỀ

CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN

MÃ SỐ: 8480104

TÓM TẮT LUẬN VĂN THẠC SĨ

NGƯỜI HƯỚNG DẪN KHOA HỌC

PGS.TSKH. TRẦN QUỐC CHIẾN

Đà Nẵng – Năm 2019

1

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

Chọn nghề là một việc quan trọng đối với mỗi bản thân cá nhân học sinh, gia

đình và ảnh hưởng một phần nào đó đến xã hội. Việc chọn nghề phù hợp sẽ giúp cho

học sinh trong tương lai có công việc ổn đinh, có thu nhập để nuôi sống bản thân và

gia đình, góp phần ổn định xã hội. Chọn nghề không phù hợp sẽ dẫn đến những việc

tiêu cực như thất nghiệp, lãng phí thời gian, tiền bạc. Theo quan điểm của lý thuyết

căng thẳng trong nghiên cứu xã hội học tội phạm, khi con người không tìm thấy

những phương tiện hợp pháp để thỏa mãn nhu cầu của mình (như nhu cầu có thu

nhập để sống) thì họ buộc phải sử dụng đến các phương tiện phi pháp. Đây chính là

một trong những nguy cơ làm gia tăng tội phạm trộm cướp, cờ bạc và các tệ nạn khác

trong xã hội. Làm xói mòn nếp sống văn hóa, lành mạnh, phá vỡ các mối quan hệ.

Vậy làm thế nào để giúp học sinh THPT có để lựa chọn nghề không sai lầm?

Việc ứng dụng công nghệ thông tin để giúp học sinh lựa chọn nghề phù hợp

trong tương lai là điều cần thiết để hạn chế việc lựa chọn nghề sai lầm của học sinh,

hạn chế làm việc trái nghề sau khi ra trường.

KPDL là một tiến trình khai phá tự động tri thức tiềm ẩn trong cơ sở dữ liệu, là

tiến trình khái quát các sự kiện rời rạc trong dữ liệu thành các tri thức mang tính quy

luật, hỗ trợ tích cực cho việc đưa ra các quyết định. Và Kỹ thuật cây quyết định trong

Khai phá dữ liệu là một phương pháp tối ưu trong việc đánh giá rủi ro, hỗ trợ ra quyết

định như: Ngân hàng, bảo hiểm, tài chính, y học, giáo dục và viễn thông, …

Luận văn: “NGHIÊN CỨU KỸ THUẬT CÂY QUYẾT ĐỊNH VÀ XÂY

DỰNG ỨNG DỤNG HỖ TRỢ HỌC SINH TRƯỜNG THPT VÕ NGUYÊN

GIÁP CHỌN NGHỀ” nghiên cứu về kỹ thuật cây quyết định C4.5 và ứng dụng vào

bài toán chọn nghề để hỗ trợ học sinh lựa chọn nghề phù hợp.

2. Mục tiêu nghiên cứu

- Mục tiêu tổng quát: Hướng đến xây dựng ứng dụng hỗ trợ học sinh chọn nghề bằng

kỹ thuật cây quyết định trong khai phá dữ liệu để hạn chế tình trạng chọn sai nghề của

học sinh trong tương lai và giảm tình trạng thất nghiệp hoặc làm trái nghề của sinh

viên sau khi ra trường.

- Mục tiêu cụ thể:

+ Ứng dụng thuật toán cây quyết định để tạo ra ứng dụng hỗ trợ học sinh chọn nghề

phù hợp.

+ Ứng dụng dễ sử dụng đối với người dùng cuối.

3. Đối tượng nghiên cứu

- Kỹ thuật hướng nghiệp chọn nghề.

- Nghiên cứu về phân lớp dữ liệu trong khai phá dữ liệu.

+ Kỹ thuật phân lớp bằng cây dữ liệu.

+ Thuật toán cây quyết định trong khai phá dữ liệu.

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

a) Nghiên cứu lý thuyết

- Nghiên cứu tài liệu, ngôn ngữ và các công nghệ có liên quan.

2

- Tổng hợp và phân tích và tổng hợp các tài liệu để lựa chọn các phương pháp

thích hợp triển khai ứng dụng: Tài liệu về khai phá dữ liệu sử dụng thuật toán về

Decision Tree, phân loại dữ liệu, mô hình dự báo.

b) Nghiên cứu thực nghiệm

- Tiến hành thu thập và tổng hợp các tài liệu liên quan đến hướng nghiệp chọn

nghề, các phương pháp chọn nghề phù hợp.

- Ứng dụng kết hợp kỹ thuật phân loại và mô hình cây quyết định để xây dựng

ứng dụng hỗ trợ học sinh đưa ra kết luận chọn nghề.

- Tiến hành kiểm thử, so sánh đánh giá hiệu suất của ứng dụng.

5. Ý nghĩa khoa học và thực tiễn của luận văn

Áp dụng lý thuyết về khai phá dữ liệu vào việc hỗ trợ ra quyết định chọn nghề

cho học sinh trong tương lai.

Về mặt thực tiễn, ứng dụng có khả năng phân tích dữ liệu nghề nghiệp: đặc điểm

nghề nghiệp, yêu cầu của nghề nghiệp, xu hướng thị trường nghề nghiệp. Phân tích

dữ liệu về cá nhân: tư duy, tính cách, khả năng thích ứng với nghề nghiệp theo xu

hướng thị trường nghề nghiệp trong tương lai.

Giúp cho việc dự đoán nhằm hỗ trợ ra quyết định một cách khoa học, tránh được

các tình huống chọn nghề theo phong trào, theo cảm tính.

6. Cấu trúc luận văn

Luận văn được chia thành 3 chương như sau:

Chương 1: Khái quát phát hiện tri thức và khai phá dữ liệu.

Trình bày tổng quan về phát hiện tri thức từ cơ sở dữ liệu, làm rõ mối liên hệ

giữa phát hiện tri thức từ cơ sở dữ liệu và khai phá dữ liệu (Data Mining) với cơ sở

dữ liệu. Chương này tìm hiểu về các kỹ thuật KPDL, đặc biệt kỹ thuật khai phá dữ

liệu bằng cây quyết định. Ngoài ra chương còn giới thiệu các công cụ được sử dụng

trong KPDL, các lĩnh vực liên quan, …

Chương 2: Cây quyết định trong chọn nghề.

Chương này tìm hiểu về bài toán chọn nghề, phân tích và thiết kế chương trình

cho bài toán chọn nghề. Trong chương mô tả mô hình bài toán chọn nghề, các chức

năng cần có trong hệ thống chọn nghề, xác định mối quan hệ cây quyết định C4.5

trong bài toán chọn nghề,…

Chương 3: Xây dựng hệ thống

Chương này tiến hành xây dựng CSDL cho hệ thống, đồng thời tiến hành áp

dụng quy trình KPDL bằng cây quyết định C4.5 cho bài toán chọn nghề trên CSDL

được xây dựng. Tiến hành áp dụng dữ liệu thực nghiệm cho bài toán, xác định độ

chính xác cây quyết định, xây dựng tập luật và kết quả thực nghiệm khi học sinh thực

hiện chọn nghề trên hệ thống chọn nghề,…

3

Chương 1: KHÁI QUÁT PHÁT HIỆN TRI THỨC VÀ KHAI PHÁ DỮ LIỆU

1.1. Phát hiện tri thức (Knowledge Discovery in Databases – KDD)

1.1.1. Một số khái niệm:

1.1.1.1.Thông tin

1.1.1.2.Tri thức

1.1.2. Tổ chức và khai thác thông tin truyền thống

1.1.3. Phát hiện tri thức

1.1.3.1.Sự cần thiết của phát hiện tri thức

1.1.3.2.Quá trình KDD

a. Khái niệm KDD

Ngoài thuật ngữ phát hiện tri thức - KDD, người ta còn dùng một số thuật ngữ

khác có ý nghĩa tương tự như phân tích dữ liệu/mẫu, khai mỏ dữ liệu, khai phá dữ

liệu… Nhưng tóm lại, về bản chất phát hiện tri thức liên quan đến việc phân tích các

dữ liệu và sử dụng các kỹ thuật đặc biệt để tìm ra các mẫu đặc trưng trong một tập dữ

liệu khổng lồ. Có nhiều định nghĩa về phát hiện tri thức đã được các tác giả khác

nhau đưa ra, theo định nghĩa của Fayyad: “KDD là quá trình không tầm thường của

việc xác định các mẫu tiềm ẩn có tính hợp lệ, mới lạ, có ích và có thể hiểu được trong

dữ liệu” [7].

Tiến trình KDD bao gồm các giai đoạn: Chuẩn bị dữ liệu, tìm kiếm mô hình,

khai phá dữ liệu, đánh giá mẫu và sử dụng tri thức khai phá được. Thuật ngữ “mẫu

tiềm ẩn” được hiểu là mối quan hệ trong dữ liệu chẳng hạn như những sinh viên học

giỏi toán và tiếng anh thì có điểm trung bình cuối khóa cao, “hợp lệ” bởi vì chứng

minh được tính đúng của mô hình. Thuật ngữ “mới lạ” hàm ý rằng những mẫu khai

phá được là không biết trước.

b. Quá trình KDD

Giai đoạn 1: Chọn lọc dữ liệu (Selection):

Đây là giai đoạn tập hợp các dữ liệu được khai thác từ một CSDL, một kho dữ

liệu, thậm chí từ các nguồn ứng dụng web vào một CSDL riêng. Chú ng ta chỉ chọn ra

những dữ liệu cần thiết cho các giai đoạn sau.

Thực hiện giai đoạn này gồm các bước sau:

 Bước 1: Nghiên cứu lĩnh vực

Ta cần phải tìm hiểu lĩnh vực ứng dụng, xác định rõ mục tiêu và nhiệm vụ của

bài toán. Giai đoạn này giúp ta xác định những tri thức cần chắc và lựa chọn kỹ thuật

khai phá dữ liệu thích hợp với mục tiêu của ứng dụng và đặc điểm của dữ liệu.

4

 Bước 2: Thu thập dữ liệu

Sau khi xác định được mục tiêu của bài toán, có các mô tả đầy đủ về mục tiêu

cần đạt tới ta tiến hành thu thập các dữ liệu liên quan (các thông tin cần thiết, phù hợp

với mục tiêu của quá trình khai phá dữ liệu bao gồm cả các thuộc tính sẽ được xem

xét). Công việc này bao gồm thu thập những dữ liệu có sẵn, thu thập dữ liệu cần thiết

bổ sung. Sau đó, ta tích hợp tất cả xây dựng tập tin để lưu trữ các dữ liệu đầu vào để

máy tính có thể lưu trữ và xử lý.

Giai đoạn 2: Tiền l dữ liệu (Preprocessing):

Ở bước này ta tiến hành bỏ bớt những dữ liệu rườm rà, không cần thiết, tinh

chỉnh lại cấu trúc của dữ liệu và mã hóa chúng để tiện cho quá trình xử lý.

Quá trình này đòi hỏi phải có một kỹ thuật phù hợp sao cho dữ liệu sau khi

được rút gọn vẫn có khả năng được khai phá hiệu quả. Việc rút gọn dữ liệu bao gồm

các phương pháp như tổng hợp và tổng quát hóa, giảm chiều dữ liệu, nén dữ liệu,

giảm số lượng các bản ghi, rời rạc hóa.

 Tổng hợp dữ liệu và tổng quát hóa dữ liệu: tổ hợp từ hai thuộc tính trở lên

thành một thuộc tính, tổng quát dữ liệu cấp thấp sang dữ liệu cấp cao chẳng

hạn như các thành phố tổng hợp vào vùng, khu vực, nước…

 Giảm chiều dữ liệu: thực hiện trích chọn đặc trưng, tìm ra tập các thuộc tính

có khả năng khai phá tốt nhất loại bỏ các thuộc tính không liên quan, dư

thừa bằng phương pháp vét cạn, phương pháp heuristic, cây quyết định khi

đó các thuộc tính nằm trong cấu trúc cây quyết định sẽ được lựa chọn để

khai phá dữ liệu. Thuộc tính nào không được đưa vào cây quyết định sẽ bị

loại bỏ, do thuộc tính đó có ảnh hưởng không lớn đến kết quả.

 Cách tiếp cận chính để làm giảm số bản ghi dữ liệu là lấy mẫu ngẫu nhiên.

Thay vì tiến hành khai phá trên tập toàn bộ các trường hợp, các mẫu ngẫu

nhiên được thu thập. Có hai cách để lấy mẫu:

o Mẫu tăng dần: Phương pháp này tiến thử nghiệm với một tập mẫu lấy

từ dữ liệu nguồn, dùng mẫu này để đánh giá hiệu quả. Tiếp theo lấy

các mẫu với số lượng trường hợp tăng dần và so sánh độ hiệu quả với

tập mẫu trước đó. Nếu hiệu quả được cải thiện thì tiếp tục quá trình

lấy mẫu, ngược lại quá trình sẽ dừng.

o Mẫu trung bình: nếu chương trình chỉ có khả năng xử lý N trường

hợp thì lấy k mẫu, mỗi mẫu có N trường hợp để xử lý

Dữ liệu được lấy từ các mẫu trên sẽ có kích thước nhỏ hơn nhiều so với toàn bộ

kho dữ liệu. Ngoài ra, việc tổng hợp các kết quả để thu được kết quả cuối có độ sai

lệch thấp hơn so với chỉ lấy một tập mẫu. Nếu số mẫu lấy đủ lớn, kết quả thu được sẽ

tương đương với kết quả từ việc xử lý cả kho dữ liệu.

5

Nhiệm vụ làm sạch dữ liệu bao gồm các công đoạn: Điền các giá trị còn thiếu;

xác định các sai biệt và khử dữ liệu tạp, nhiễu; sửa chữa các dữ liệu mâu thuẫn.

Đối với việc xử lý dữ liệu bị thiếu có một số giải pháp sau:

 Bỏ qua mẫu dữ liệu đó nếu mẫu dữ liệu chứa nhiều thuộc tính thiếu giá trị.

 Điền vào các giá trị thiếu bằng tay: Phương pháp này thường tốn thời gian và

có thể không khả thi cho một tập dữ liệu nguồn lớn với nhiều giá trị bị thiếu.

 Bổ sung các giá trị thiếu này bằng phương pháp toán học, có thể chọn một

trong ba cách sau:

o Thay thế giá trị thiếu bằng một hằng số chuẩn.

o Thay thế giá trị thiếu bằng giá trị trung bình cùng thuộc tính.

o Thay thế giá trị thiếu bằng giá trị trung bình cùng thuộc tính và lớp

Phương pháp này có ưu điểm là đơn giản, nhưng có hạn chế là giá trị thay thế

không phải giá trị đúng hoàn toàn. Nếu thay thế giá trị thiếu bằng một hằng số hoặc

một vài giá trị định trước sẽ làm cho dữ liệu mất tính khách quan. Ví dụ nếu giá trị

thiếu được thay thế bằng trung bình của thuộc tính cùng lớp sẽ làm cho các giá trị này

hội tụ vào một tập tương ứng với lớp có số trường hợp bị thiếu lớn nhất.

 Bổ sung các giá trị thiếu sử dụng phương pháp logic, thường sử dụng

các kỹ thuật cây quyết định hoặc luật quyết định. Phương pháp này tỏ ra

có ưu thế hơn phương pháp toán học do tập luật được xây dựng trên dữ

liệu thực, vì thế kết quả có độ tin cậy cao hơn.

Đối với việc xử lý dữ liệu nhiễu có một số giải pháp sau:

 Phương pháp chia giỏ: sắp xếp và chia dữ liệu vào các giỏ theo độ rộng

(chia vùng giá trị thành N khoảng cùng kích thước), hoặc theo độ sâu

(chia vùng giá trị thành N khoảng mà mỗi khoảng có chứa gần như cùng

số lượng mẫu). Khử nhiễu bằng giá trị trung bình, trung tuyến, biên

giỏ…

 Hồi quy: Phương pháp thường dùng là hồi quy tuyến tính, để tìm ra

được một mối quan hệ tốt nhất giữa hai thuộc tính (hoặc các biến), từ đó

một thuộc tính có thể dùng để dự đoán thuộc tính khác.

 Phân cụm: Các giá trị tương tự nhau được tổ chức thành các nhóm hay

cụm. Các giá trị rơi ra bên ngoài các nhóm này sẽ được xem xét để làm

mịn.

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

Trong giai đoạn này dữ liệu sẽ được chuyển đổi về dạng thuận tiện để tiến hành

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

Một số kỹ thuật áp dụng cho quá trình chuyển đổi dữ liệu:

6

 Chuyển đổi kiểu dữ liệu: Đây là một kỹ thuật đơn giản nhất. Chẳng hạn

như chuyển các cột dữ liệu kiểu logic sang dạng nguyên và ngược lại.

 Rời rạc hóa: biến đổi miền giá trị thuộc tính liên tục thành từng khoảng,

lưu nhãn của khoảng thay cho giá trị thực. Chẳng hạn như thay thế giá trị tuổi

bằng các nhãn như trẻ, trung niên, già.

 Nhóm: Kỹ thuật này phân loại các giá trị trong một cột thành các nhóm,

sau đó ánh xạ giá trị ban đầu sang các giá trị nhóm tương ứng. Chẳng hạn cột

nghề nghiệp có những giá trị khác nhau như kỹ sư cơ khí, kỹ sư công nghệ

thông tin, kỹ sư xây dựng… thì chúng ta có thể nhóm chúng lại thành nhóm kỹ

sư.

 Tập hợp: những thông tin lưu trữ trong cơ sở dữ liệu là rất chi tiết, chúng

ta có thể tập hợp chúng lại thành vài thuộc tính tổng hợp. Chẳng hạn chúng ta

muốn phân loại khách hàng dựa trên những thông tin sử dụng điện thoại hàng

tháng của khách hàng, chúng ta có thể tập hợp những thông tin này thành một

vài thuộc tính tổng hợp như tổng số cuộc gọi hay thời gian trung bình các cuộc

gọi.

 Tổng quát hóa: Dữ liệu ở mức thấp (dữ liệu nguyên thủy) có thể được

thay thế bằng các khái niệm ở mức cao hơn. Chẳng hạn những loài cây có thể

được tổng quát ở mức cao hơn là thực vật.

 Chuẩn hóa: Một thuộc tính được chuẩn hóa bằng cách ánh xạ một cách

có tỉ lệ dữ liệu về một khoảng xác định ví dụ như 0.0 đến 1.0. Chuẩn hóa là một

phần hữu ích của thuật toán phân lớp trong mạng noron, hoặc thuật toán tính

toán độ lệch sử dụng trong việc phân lớp hay nhóm cụm các phần tử liền kề.

Giai đoạn 4: Khai phá dữ liệu (Data mining):

Trong giai đoạn này ta sử dụng các kỹ thuật nhằm phát hiện ra các tri thức tiềm

ẩn trong dữ liệu.

Giai đoạn này gồm các bước sau:

 Bước 1: Chọn kỹ thuật khai phá dữ liệu:

Tùy thuộc vào yêu cầu của bài toán để chọn kỹ thuật khai phá phù hợp. Bao

gồm các kỹ thuật khai phá như:

 Phân lớp: Là việc xác định một hàm ánh xạ từ một mẫu dữ liệu vào một

trong số các lớp đã được biết trước đó. Mục tiêu của thuật toán phân lớp là tìm ra

mối quan hệ nào đó giữa thuộc tính dự báo và thuộc tính phân lớp. Một điều cần

chú ý là khác với bài toán phân cụm, dữ liệu dùng để xây dựng mô hình

(Training Data) trong bài toán phân lớp phải được xác định lớp trước (pre￾Labeled). Quá trình phân lớp dữ liệu thường gồm các bước: huấn luyện mô hình,

kiểm thử mô hình và tính toán sai số để đánh giá mô hình. Dữ liệu gốc sẽ được

7

chia thành 2 phần là tập dữ liệu huấn luyên để xây dựng mô hình và tập dữ liệu

kiểm thử để kiểm định mô hình tương ứng với hai bước trên. Trong kỹ thuật

phân lớp chúng ta có thể sử dụng các phương pháp như: cây quyết định, K –

láng giềng gần nhất, mạng noron, giải thuật di truyền, mạng Bayesian, tập mờ và

tập thô.

 Hồi qui

 Phân cụm

 Phân tích luật kết hợp

 Bước 2: Chọn thuật toán khai phá:

Trong mỗi kỹ thuật khai phá có thể có nhiều giải thuật khai phá, việc

chọn thuật toán nào để có hiệu quả cao phụ thuộc vào rất nhiều yếu tố như độ

lớn của tập dữ liệu khai phá, cấu trúc của tập dữ liệu, tập dữ liệu có hay không

có thuộc tính bị thiếu nhiều giá trị…

 Bước 3: Khai phá dữ liệu:

Với một tập dữ liệu đã được tiền xử lý ta tiến hành khai phá dữ liệu bằng

kỹ thuật khai phá đã chọn. Trong bước này, chúng ta có thể cần phải thực hiện

các thuật toán nhiều lần cho đến khi thu mô hình với độ chính xác chấp nhận

được.

Giai đoạn 5: á nh giá k t qu m u (Evaluation Interprelation):

Trong giai đoạn này, các mẫu dữ liệu được chiết xuất bởi các phần mềm khai

phá dữ liệu. Không phải bất cứ mẫu nào cũng đều có ích, thậm chí còn bị sai lệch.

Giai đoạn này có thể chia thành các bước sau:

 Bước 1: ánh giá mô hình

 Bước 2: S dụng các tri thức phát hiện được

`Hình 1.1 Quá trình phát hiện tri thức từ dữ liệu

1.1.4. Quá trình KDD và KPDL

1.2. Khai phá dữ liệu

KPDL là một khâu của quá trình KDD.

8

1.2.1. Khái niệm KPDL

KPDL là một tiến trình sử dụng các công cụ phân tích dữ liệu khác nhau để

khám phá ra các mẫu dưới nhiều góc độ khác nhau nhằm phát hiện ra các mối quan

hệ giữa các dữ kiện, đối tượng bên trong CSDL, kết quả của việc khai phá là xác định

các mẫu hay các mô hình đang tồn tại bên trong, nhưng chúng nằm ẩn trong các

CSDL (rất) lớn. Để từ đó trích rút ra được các mẫu quan trọng (không tầm thường,

ẩn, chưa được biết đến, và có thể hữu ích), các thông tin và tri thức từ CSDL [7].

1.2.2. Lịch s KPDL

1.2.2.1.Sự hình thành ngành khoa học thống kê

1.2.2.2.Phân tích thống kê hiện đại: Thế hệ thứ nhất

1.2.2.3.Phân tích thống kê hiện đại: Thế hệ thứ hai

1.2.2.4.Phương pháp học máy: Thế hệ thứ ba

1.2.2.5.Học thuyết thống kê: Tổng quan thứ tư

1.2.2.6.Lịch sử phát triển của KPDL

1.2.3. Quá trình KPDL

Các giải thuật KPDL thường được mô tả như những chương trình hoạt động

trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và thống kê trước đây,

thường thì bước đầu tiên là các giải thuật nạp toàn bộ tệp dữ liệu vào trong bộ nhớ.

Quá trình xử lý KPDL gồm các bước sau:

Bước 1: Xác định chính xác vấn đề cần giải quyết.

Bước 2: Xác định các dữ liệu liên quan dùng để xây dựng giải pháp.

Bước 3: Thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho

giải thuật KPDL có thể hiểu được.

Bước 4: Chọn thuật toán KPDL thích hợp và thực hiện việc KPDL để tìm được

các mẫu (pattern) có ý nghĩa dưới dạng biểu diễn tương ứng với các ý nghĩa đó

(thường được biểu diễn dưới dạng các luật xếp loại, cây quyết định, luật sản xuất,

biểu thức hồi quy,…).

Đặc điểm của mẫu phải là mới (ít nhất là đối với hệ thống đó). Độ mới có thể

đuợc đo tương ứng với độ thay đổi trong dữ liệu (bằng cách so sánh các giá trị hiện

tại với các giá trị trước đó hoặc các giá trị mong muốn), hoặc bằng tri thức (mối liên

hệ giữa phương pháp tìm mới và phương pháp cũ như thế nào). Thường thì độ mới

của mẫu được đánh giá bằng một hàm logic hoặc một hàm đo độ mới, độ bất ngờ của

mẫu. Ngoài ra, mẫu còn phải có khả năng sử dụng tiềm tàng. các mẫu này sau khi

được xử lý và diễn giải phải dẫn đến những hành động có ích nào đó được đánh giá

bằng một hàm lợi ích. mẫu khai thác được phải có giá trị đối với các dữ liệu mới với

độ chính xác nào đó.

9

1.2.4. Khái quát về các kỹ thuật KPDL

1.2.4.1. hai thác t p phổ biến và u t kết h p

1.2.4.2.Phân p d iệu

Phân lớp (classification): là tiến trình khám phá các luật phân loại hay đặc

trưng cho các tập dữ liệu đã được xếp lớp. Tập dữ liệu học bao gồm tập đối tượng đã

được xác định lớp sẽ được dùng để tạo mô hình phân lớp dựa trên đặc trưng của đối

tượng trong tập dữ liệu học. Các luật phân lớp được sử dụng để xây dựng các bộ phân

lớp dữ liệu. Phân lớp dữ liệu có vai trò quan trọng trong tiến trình dự báo các khuynh

hướng quy luật phát triển. Một số kỹ thuật thường được sử dụng trong phân lớp:

- Cây quyết định (Decision tree): Biểu diễn ở dạng cấu trúc hình cây. Các

quyết định này tạo ra các quy tắc để phân lớp và dự đoán tập dữ liệu mới chưa được

phân lớp. Tri thức được rút ra trong kỹ thuật này thường được mô tả dưới dạng tường

minh, đơn giản, trực quan, dễ hiểu đối với người sử dụng.

- Mạng Nơron (Neural Network)

1.2.4.3.Gom cụm

1.3. Kỹ thuật khai phá dữ liệu sử dụng cây quyết định

1.3.1. Cây quy t định:

1.3.1.1.Gi i thiệu cây quyết định:

Cây quyết định là một dạng đặc biệt của cấu trúc cây. Các cây quyết định được

dùng để hỗ trợ quá trình ra quyết định.

Cây quyết định có thể được dùng để phân lớp bằng cách xuất phát từ gốc của

cây và di chuyển theo các nhánh cho đến khi gặp nút lá. Trên cơ sở phân lớp này

chúng ta có thể chuyển đổi về các luật quyết định. Cây quyết định được sử dụng để

dự đoán những thành viên của đối tượng theo những đề mục khác nhau (lớp), đưa

vào các giá trị mà có liên quan đến thuộc tính (biến dự đoán), phương thức cây quyết

định là một trong những kỹ thuật KPDL chính.

1.3.1.2.Cấu trúc cây quyết định:

Cấu trúc của một cây quyết định bao gồm các nút và các nhánh.

Hình 1.3 Mô hình cây quyết định

10

 Nhánh (branch): biễu diễn giá trị có thể có của thuộc tính.

 Nút (node): mỗi nút mạng một thuộc tính bao gồm 3 loại:

 Nút gốc (root node) là đỉnh trên cùng của cây.

 Nút lá (leaf node) là nút ngoài cùng, mang thuộc tính phân lớp.

 Nút trong (internal node) là các nút còn lại, mang thuộc tính phân loại.

1.3.2. Kỹ thuật KPDL s dụng cây quy t định

1.3.2.1.Gi i thiệu kỹ thu t PDL sử dụng cây quyết định:

Quy nạp cây quyết định (decision tree induction) là việc tìm kiếm các cây quyết

định từ những bản ghi huấn luyện đã có nhãn lớp. Mỗi cây quyết định là một cấu trúc

cây kiểu lưu đồ, trong đó mỗi nút trong biểu thị một sự kiểm tra trên một thuộc tính

nào đó, mỗi nhánh biểu diễn một kết quả của sự kiểm tra đó, còn mỗi nút lá chứa một

nhãn lớp. Nút ở trên cùng của cây là nút gốc, chứa tên của thuộc tính cần kiểm tra..

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

Quá trình xây dựng cây quyết định gồm hai giai đoạn:

 Giai đoạn thứ nhất: phát triển cây quyết định: Giai đoạn này phát triển

bắt đầu từ gốc, đến từng nhánh và phát triển quy nạp theo cách thức chia để trị

cho tới khi đạt được cây quyết định với tất cả các lá được gán nhãn lớp.

Khung công việc của giai đoạn này:

- Bước 1: Chọn thuộc tính “tốt” nhất bằng một độ đo đã định trước.

- Bước 2: Phát triển cây bằng việc thêm các nhánh tương ứng với từng

giá trị của thuộc tính đã chọn.

- Bước 3: Sắp xếp, phân chia tập dữ liệu huấn luyện tới node con.

- Bước 4: Nếu các ví dụ được phân lớp rõ ràng thì dừng. Ngược lại: lặp

lại bước 1 tới bước 4 cho từng node con.

 Giai đoạn thứ hai: cắt, tỉa bớt các nhánh trên cây quyết định. Giai đoạn

này nhằm mục đích đơn giản hóa và khái quát hóa từ đó làm tăng độ chính xác

của cây quyết định bằng cách loại bỏ sự phụ thuộc vào mức độ nhiễu, lỗi của dữ

liệu huấn luyện mang tính chất thống kê, hay những sự biến đổi mà có thể là đặc

tính riêng biệt của dữ liệu huấn luyện. Giai đoạn này chỉ truy cập dữ liệu trên cây

quyết định đã được phát triển trong giai đoạn trước.

1.3.2.3.Các vấn đề trong PDL sử dụng cây quyết định

1.3.3. Thuật toán s dụng ây dựng cây quy t định

Tạo cây quyết định chính là quá trình phân tích cơ sở dữ liệu, phân lớp và đưa ra

dự đoán. 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. Lựa chọn thuộc tính để tạo nhánh thông qua Entropy và Gain.