ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG
NGUYỄN VĂN SỰ
KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH
VÀ ỨNG DỤNG TRONG HỆ HỖ TRỢ QUYẾT ĐỊNH
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Thái Nguyên - 2012
1Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1
MỤC LỤC
2.2.4. Thuật toán SLIQ 41
2.3. Kỹ thuật cắt tỉa cây quyết định 50
2.4. Tổng kết 61
Chương 3. CÂY QUYẾT ĐỊNH VÀ ỨNG DỤNG TRONG HỆ HỖ TRỢ
QUYẾT ĐỊNH 64
3.1. Tổng quan về công tác thi đua khen thưởng trong ngành giáo dục 65
3.1.1. Các tiêu chuẩn và danh hiệu thi đua trong ngành giáo dục 66
3.1.2. Quy trình đề nghị xét duyệt và ra quyết định khen thưởng 67
3.2. Phần mềm hỗ trợ ra quyết định khen thưởng 70
3.2.1. Cấu trúc kho dữ liệu 70
3.2.2. Kết quả cài đặt phần mềm 72
3.2. 3. Đánh giá kết quả đạt được của chương trình 75
3.3. Kết luận và hướng phát triển 77
TÀI LIỆU THAM KHẢO 79 ii
3Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3
LỜI NÓI ĐẦU
Song song với sự phát triển không ngừng của ngành Công nghệ thông tin nói
chung và các lĩnh vực ngành công nghệ phần mềm nói riêng, hệ thống các kho dữ
liệu phục vụ trong công tác hỗ trợ ra quyết định và việc phân loại các thông tin
cũng như nhu cầu lưu trữ thông tin ngày càng cần thiết. Bên cạnh đó việc tin học
hóa trong các công tác quản lý cũng như nhiều lĩnh vực, hoạt động khác đã tạo ra
cho nhân loại một thư viện dữ liệu khổng lồ, sẵn sàng phục vụ bất cứ ai quan tâm.
Đối với chúng ta nó là một trong những nguồn tài nguyên thông tin vô cùng giá trị,
việc tận dụng kho dữ liệu này để làm cơ sở cho việc hỗ trợ ra quyết định trong
công tác quản lý mang lại hiệu quả đáng kể. Nhưng vấn đề là chúng ta cần phải
dục, các quy trình xét duyệt và ra quyết định khen thưởng, xác định yêu cầu bài
toán, lựa chọn thuật toán để cài đặt xây dựng công cụ hỗ trợ ra quyết định khen
thưởng trong công tác quản lý thi đua khen thưởng của Bộ Giáo dục và Đào tạo.
5Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5
Chương 1
KHAI PHÁ DỮ LIỆU
1.1. Khám phá tri thức và khai phá dữ liệu
Khám phá tri thức (Knowledge Discovery) trong các cơ sở dữ liệu, kho dữ
liệu là một quy trình gồm nhiều công đoạn để nhận biết các mẫu hoặc các mô hình
trong dữ liệu với các tính năng: hợp thức, mới, khả ích, và có thể hiểu được [18].
Khai phá dữ liệu là việc sử dụng dữ liệu lịch sử để khám phá những qui tắc và
cải thiện những quyết định trong tương lai.
Khai phá dữ liệu như là một quá trình phân tích được thiết kế thăm dò một
lượng cực lớn các dữ liệu nhằm phát hiện ra các mẫu thích hợp 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 hoá 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. Mục đích của khai phá dữ liệu là:
o Rút trích thông tin hữu ích, chưa biết, các mẫu hoặc các mô hình tiềm
ẩn trong khối dữ liệu lớn dưới dạng các quy luật, ràng buột, quy tắc
trong cơ sở dữ liệu.
o Phân tích dữ liệu bán tự động.
o Giải thích dữ liệu trên các tập dữ liệu lớn.
Khai phá dữ liệu là một bước trong quy trình khám phá tri thức để hỗ trợ ra
quyết định, dự báo và khái quát dữ liệu.
1.2. Tại sao phải khai phá dữ liệu
Ước tính cứ mỗi năm lượng thông tin trên thế giới lại tăng lên khoảng 2 lần.
Chính vì vậy, hiện nay dữ liệu mà con người thu thập và lưu trữ trong các kho dữ
pháp khai phá dữ liệu thích hợp với mục đích của ứng dụng và bản chất của dữ
liệu.
- Bước 2: Thu thập và tiền xử lý dữ liệu
Trong bước này dữ liệu được thu thập ở dạng thô (nguồn dữ liệu thu thập có
thể là từ các kho dữ liệu hay nguồn thông tin khác từ internet). Trong giai đoạn này
dữ liệu cũng được tiền xử lý để biến đổi và cải thiện chất lượng dữ liệu cho phù
hợp với phương pháp khai phá dữ liệu được chọn lựa trong bước trên.
Bước này thường chiếm nhiều thời gian nhất trong quá trình khám phá tri
thức.
Các giải thuật tiền xử lý dữ liệu bao gồm:
1. Xử lý dữ liệu bị mất/thiếu: các dạng dữ liệu bị thiếu sẽ được thay thế bởi
các giá trị thích hợp.
2. Khử sự trùng lặp: các đối tượng dữ liệu trùng lặp sẽ bị loại bỏ đi.
3. Giảm nhiễu: nhiễu và các đối tượng tách rời khỏi phân bố chung sẽ bị loại
đi khỏi dữ liệu.
4. Chuẩn hoá: miền giá trị của dữ liệu sẽ được chuẩn hoá.
5. Rời rạc hoá: các dạng dữ liệu số sẽ được biến đổi ra các giá trị rời rạc.
6. Rút trích và xây dựng đặc trưng mới từ các thuộc tính đã có.
7. Giảm chiều: các thuộc tính chứa ít thông tin sẽ được loại bỏ bớt.
- Bước 3: Khai phá dữ liệu và rút ra các tri thức
Đây là bước quan trọng nhất trong tiến trình khám phá tri thức. Kết quả của
bước này là trích ra được các mẫu và (hoặc) các mô hình ẩn dưới các dữ liệu. Một
mô hình có thể là một biểu diễn cấu trúc tổng thể một thành phần của hệ thống hay
8Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
8
cả hệ thống trong cơ sở dữ liệu, hay miêu tả cách dữ liệu được nảy sinh. Còn một
mẫu là một cấu trúc cục bộ có liên quan đến vài biến và vài trường hợp trong cơ sở
dữ liệu.
- Bước 4: Phân tích và kiểm định kết quả
- Trích lọc dữ liệu (selection)
Ở giai đoạn này dữ liệu được lựa chọn và phân chia theo một số tiêu chuẩn
nào đó.
- Làm sạch và tiền xử lý dữ liệu (cleansing preprocessing)
Giai đoạn thứ ba này là giai đoạn thường bị bỏ quên, 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à dữ liệu không đầy đủ hoặc không thống nhất, thiếu chặt
chẽ, vô nghĩa (ví dụ như: con người có chiều cao = 4 mét điều này là vô lý), do
vậy ở giai đoạn thứ ba này nhằm xử lý các dữ liệu như trên (dữ liệu vô nghĩa, dữ
10Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
10
liệu không có khả năng kết nối). Những dữ liệu dạng này thường được xem là
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.
Nếu dữ liệu không được làm sạch - tiền xử lý - chuẩn bị trước thì sẽ tạo ra những
kết quả sai lệch nghiêm trọng về sau.
- Chuyển đổi dữ liệu (transformation)
Trong giai đoạn này, dữ liệu có thể được tổ chức và sử dụng lại. Mục đích của
việc chuyển đổi dữ liệu là làm cho dữ liệu phù hợp hơn với mục đích khai phá dữ
liệu.
- Phát hiện và trích chọn mẫu dữ liệu (pattern extraction and discovery)
Đây là bước tư duy trong khai phá dữ liệu. Ở trong 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 để trích mẫu dữ liệu là thuật toán phân loại dữ liệu, kết hợp dữ liệu, thuật
toán mô hình hoá dữ liệu tuần tự.
- Đánh giá kết quả mẫu (evaluation of result)
Đây là giai đoạn cuối cùng 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
mẫu dữ liệu nào cũng hữu ích, đôi khi nó còn bị sai lệch. Vì vậy cần phải đưa ra
những tiêu chuẩn đánh giá độ ưu tiên cho các mẫu dữ liệu để rút ra được những tri
của mô hình chấp nhận được.
2) Phân cụm dữ liệu
Mục tiêu của 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 cụm là tương đồng
với nhau. 12Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
12
3) Khai phá luật kết hợp
Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các
giá trị dữ liệu trong cơ sở dữ liệu. Phương pháp khai phá luật kết hợp gồm có hai
bước:
Bước 1: Tìm ra tất cả các tập mục phổ biến, một tập mục phổ biến được xác
định thông qua độ hỗ trợ và thoả 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 thoả
mãn độ hỗ trợ và độ tin cậy cực tiểu.
4) Hồi quy
Phương pháp hồi quy tương tự như là phân lớp dữ liệu. Nhưng khác ở chỗ nó
dùng để dự đoán các giá trị liên tục còn phân lớp dữ liệu dùng để dự đoán các giá
trị rời rạc.
5) Giải thuật di truyền
Là quá trình mô phỏng theo tiến hoá của tự nhiên. Ý tưởng chính của giải
thuật là dựa vào quy luật di truyền trong biến đổi, chọn lọc tự nhiên và tiến hoá
trong sinh học.
6) Mạng nơron
Đây là một trong những kỹ thuật khai phá dữ liệu được ứng dụng phổ biến
hiện nay. Kỹ thuật này phát triển dựa trên một nền tảng toán học vững vàng, khả
năng huấn luyện trong kỹ thuật này dựa trên mô hình thần kinh trung ương của con
Khai phá dữ liệu tuy không phải là một cách tiếp cận mới, song nó lại thu hút
rất nhiều sự quan tâm của các nhà nghiên cứu và phát triển nhờ vào những ứng
dụng thực tiến của nó. Dưới đây là một số ứng dụng điển hình được sử dụng phổ
biến trong từng lĩnh vực cụ thể:
- Nhận dạng (Pattern recognition)
- Tin - sinh (Bio-informatics)
- Khai phá dữ liệu văn bản, dữ liệu web (Textmining & Webmining)
- Trong tài chính và thị trường chứng khoán (Finace & Stock market)
14Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
14
- Trong điều trị y học (Medical treatment)
- Trong bảo hiểm (Insurance)
- Phát hiện gian lận (Fraud detection)
- Các ứng dụng phát hiện và cô lập lỗi trên hệ thống mạng viễn thông
(Network fault isolation)
.v.v.
1.9. Tổng kết
Khai phá dữ liệu là một môn khoa học liên ngành: Cơ sở dữ liệu, học máy và
thống kê toán học, nghiên cứu các kỹ thuật nhằm phát hiện những thông tin có giá
trị, tiềm ẩn trong các cơ sở dữ liệu lớn.
Khai phá dữ liệu bằng cây quyết định là một kỹ thuật trong số các kỹ thuật
thường được sử dụng để khai phá dữ liệu nhằm tìm kiếm các tri thức có ích và hỗ
trợ ra quyết định trong các công tác quản lý của các nhà lãnh đạo các cơ quan, tổ
chức doanh nghiệp,
15Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
15
Chương 2
KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH
- Cây hồi quy (Regression tree) ước lượng các hàm giá có giá trị là số thực
thay vì được sử dụng cho các nhiệm vụ phân loại (ví dụ: ước tính khoảng thời gian
một bệnh nhân nằm viện hoặc giá của một ngôi nhà).
- Cây phân loại (Classification tree) nếu y là một biết phân loại như giới tính
(nam hay nữ), kết quả của một kỳ thi đại học (đỗ hay trượt).
2.1.2. Một số vấn đề trong khai phá dữ liệu bằng cây quyết định
Các vấn đề đặc thù trong khi học hay phân lớp dữ liệu bằng cây quyết định
gồm: xác định độ sâu để phát triển cây quyết định, xử lý với những thuộc tính liên
tục, chọn phép đo lựa chọn thuộc tính thích hợp, sử dụng tập dữ liệu đào tạo với
những giá trị thuộc tính bị thiếu, sử dụng các thuộc tính với những chi phí khác
nhau, và cải thiện hiệu năng tính toán. Sau đây luận văn sẽ đề cập đến những vấn
đề chính đã được giải quyết trong các thuật toán phân lớp dựa trên cây quyết định.
17Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
17
+ Tránh “quá vừa” dữ liệu
Có thể hiểu “quá vừa” là hiện tượng cây quyết định chứa một số đặc trưng
riêng của tập dữ liệu đào tạo, nếu lấy chính tập dữ liệu đào tạo để kiểm tra lại mô
hình phân lớp thì độ chính xác sẽ rất cao, trong khi đối với những dữ liệu tương lai
khác nếu sử dụng cây đó lại không đạt được độ chính xác như vậy.
“Quá vừa” dữ liệu là một khó khăn đáng kể đối với học bằng cây quyết định
và những phương pháp học khác. Đặc biệt khi số lượng ví dụ trong tập dữ liệu đào
tạo quá ít, hay có “nhiễu” trong dữ liệu.
Có hai phương pháp tránh “quá vừa” dữ liệu trong cây quyết định:
1) Dừng phát triển cây sớm, trước khi đạt tới điểm phân lớp hoàn hảo tập dữ
liệu đào tạo. Với phương pháp này, một thách thức đặt ra là phải ước
lượng chính xác thời điểm dừng phát triển cây.
2) Cho phép cây có thể “quá vừa” dữ liệu, sau đó sẽ cắt, tỉa cây.
Mặc dù phương pháp thứ nhất có vẻ trực tiếp hơn, nhưng với phương pháp
best
tốt nhất tùy vào chiến lược của từng thuật
toán [8].
2.1.3. Ưu nhược điểm của cây quyết định trong khai phá dữ liệu
So với các phương pháp khai phá dữ liệu khác, kỹ thuật khai phá dữ liệu bằng
cây quyết định có một số ưu nhược điểm sau:
+ Ưu điểm:
1) Khả năng sinh ra các quy tắc hiểu được: Cây quyết định có khả năng sinh
ra các quy tắc có thể chuyển đổi sang mô hình dạng quy tắc (hay còn gọi
là mô hình dạng luật IF THEN ) đây là ưu điểm nổi bật của kỹ thuật
này, cho dù hình dáng cây quyết định có thể lớn và phức tạp do những tập
dữ liệu lớn nhưng việc đi theo bất cứ đường nào trên cây đều dễ dàng theo
nghĩa phổ biến và rõ ràng. Do vậy việc giải thích cho bất cứ một sự phân
lớp hay dự đoán nào đều tương đối rõ ràng và trực quan.
2) Khả năng thực thi những lĩnh vực hướng quy tắc: Quy tắc quy nạp nói
chung và cây quyết định nói riêng là lựa chọn hoàn hảo cho những lĩnh
vực thực sự là các quy tắc. Ta thấy, trong các lĩnh vực từ di truyền đến các
quá trình công nghiệp thực sự chứa các quy tắc ẩn, không rõ ràng do khá
phức tạp và tối nghĩa bởi những dữ liệu nhiễu. Cây quyết định sẽ là một sự
19Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
19
lựa chọn tự nhiên khi chúng ta nghi nghờ sự tồn tại của các quy tắc ẩn,
không minh bạch.
3) Dễ tính toán trong khi phân lớp: Như chúng ta đã biết, cây quyết định có
thể chứa nhiều định dạng, nhưng trong thực tế, các thuật toán sử dụng để
tạo ra cây quyết định thường tạo ra những cây với số phân nhánh thấp và
các test đơn giản tại từng node. Những test điển hình là: so sánh số, xem
xét phần tử của một tập hợp, và các phép nối đơn giản. Khi thực thi trên
máy tính, những test này chuyển thành các toán hàm logic và số nguyên là
2) Dễ gây ra lỗi khi có quá nhiều lớp, một số cây quyết định chỉ thao tác với
những lớp giá trị nhị phân dạng “yes/no”. Số khác lại có thể chỉ định các
bản ghi vào một số lớp bất kỳ, nhưng dễ xảy ra lỗi khi số mẫu huấn luyện
ứng với một lớp là nhỏ. Điều này thể hiện càng nhanh, rõ hơn với cây mà
có nhiều tầng hay có nhiều nhánh trên một node.
3) Chi phí tính toán “đắt” để đào tạo, nghe có vẻ mâu thuẫn với ưu điểm thứ
3 được nên trên. Tuy nhiên, quá trình phát triển cây quyết định “đắt” về
mặt tính toán là vì cây quyết định có rất nhiều node trong trước khi đi đến
lá cuối cùng. Tại từng node, cần tính một độ đo (hoặc tiêu chuẩn phân
chia) trên từng thuộc tính, với thuộc tính liên tục phải thêm thao tác xắp
xếp lại tập dữ liệu theo thứ tự giá trị ủa thuộc tính đó, sau đó mới có thể
chọn một thuộc tính phát triển và tương ứng là một phân chia tốt nhất. Một
vài thuật toán sử dụng tổ hợp các thuộc tính kết hợp với nhau có trọng số
để phát triển cây quyết định. Quá tình cắt tỉa cây cũng “đắt” bởi nhiều cây
con ứng cử phải được tạo ra và so sánh.
2.1.4. Xây dựng cây quyết định
Xây dựng cây quyết định là công đoạn quan trọng nhất trong việc sử dụng cây
quyết định để khai phá dữ liệu. Quá trình xây dựng cây quyết định gồm ba bước cơ
bản sau:
21Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
21
Bước 1: Tạo cây quyết định
Tại bước này việc tạo cây quyết định 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.
Các công việc của bước này gồm:
1) Chọn thuộc tính “tốt” nhất bằng một độ đo định trước;
2) Phát triển cây bằng việc sinh các nhánh tương ứng với từng giá trị của
1. Tạo một nút T, nút này gồm tất cả các mẫu của tập huấn luyện;
2. Nếu tất cả các mẫu trong T có thuộc tính quyết định mang giá trị "YES"
(hay thuộc cùng một lớp), thì gán nhãn cho nút T là "YES" và dừng lại. T
lúc này là nút lá;
3. Nếu tất cả các mẫu trong T có thuộc tính quyết định mang giá trị "NO"
(hay thuộc cùng một lớp), thì gán nhãn cho nút T là "NO" và dừng lại. T
lúc này là nút lá;
4. Trường hợp ngược lại các mẫu của tập huấn luyện thuộc cả hai lớp "yes"
và "no" thì:
i. Chọn một thuộc tính X trong tập thuộc tính của tập mẫu dữ liệu, X
có các giá trị v
1
,v
2
, …v
n
;
ii. Chia tập mẫu trong T thành các tập con T
1
, T
2
,….,T
n
. chia theo giá
trị của X;
iii. Tạo n nút con T
i
(i=1,2…n) với nút cha là nút T;
iv. Tạo các nhánh nối từ nút T đến các nút T
i
11 Nắng Bình thường Trung bình Mạnh Có
12 U ám Bình thường Cao Mạnh Có
13 U ám Nóng Trung bình Yếu Có
14 Mưa Bình thường Cao Mạnh Không
Bảng 2.1. Tập dữ liệu huấn luyện quyết định chơi thể thao
Bảng dữ liệu trên là một tập các mẫu mô tả quyết định đi chơi tennis. Trong
bảng, thuộc tính Day được dùng để định danh (chỉ số). Các thuộc tính outlook
(quang cảnh bầu trời), temperature (nhiệt độ), humidity (độ ẩm), wind (gió) là các
thuộc tính ứng cử viên được dùng để xét. Còn thuộc tính play tennis là thuộc tính
khẳng định được dùng để phân lớp các mẫu dữ liệu. Khi đó cây quyết định được
xây dựng theo thuật toán CLS đối với tập dữ liệu trong bảng 11.1 được xây dựng
như sau:
1) Chọn thuộc tính Bầu trời = {Nắng, U ám, Mưa} ta có cây như hình 2.2
dưới đây:
24Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
24
Hình 2.2. Cây được tạo khi thuộc tính “Bầu trời” được chọn
Với giá trị thuộc tính Bầu trời = "U ám" các giá trị thuộc tính “Chơi thể thao”
của các ngày {3,7,12,13} đếu có giá trị là “Có”, chúng thuộc cùng một lớp "Có",
đây là nút lá có nhãn là "Có".
2) Tiếp theo chọn thuộc tính Độ ẩm = {Cao, Trung bình} để mở rộng cho
nhánh bên trái của cây, chúng ta được cây như hình 2.3 bên dưới.
Hình 2.3. Cây được mở rộng khi thuộc tính “Độ ẩm” được chọn
Bầu trời
[1,2,3,4,5,6,7,8,9,10,11,12,13,14]
U ám
25Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Copyright: Tài liệu đại học ©