Bài giảng Khai phá dữ liệu

thuật toán: 
1. Tạo nút N 
2. If các bộ trong D đều có nhãn lớp C then 
3. Trả về N thành một nút lá với nhãn lớp C 
4. If danh sách thuộc tính attribute_list là rỗng then 
 71 
5. Trả về N thành một nút là với nhãn là lớp chiếm đa số trong D (Việc này thực hiện 
qua gọi hàm Attribute_selection_method(D, attribute_list) để tìm ra tiêu chí phân chia tốt 
nhất splitting_criterion và gán nhãn cho N tiêu chí đó) 
6. If splitting_attribute là một giá trị rời rạc và có nhiều cách chia then 
7. Attribute_list = attribute_list – splitting_attribute // Loại bỏ thuộc tính 
splitting_attribute 
8. Foreach j in splitting_criterion 
// Phân chia các bộ xây dựng cây cho các phân chia đó 
9. Đặt Dj là tập các bộ trong D phù hợp với tiêu chí j 
10. If Dj là rỗng then 
11. Gắn nhãn cho nút N với nhãn phổ biến trong D 
12. Else Gắn nút được trả về bởi hàm Generate_decision_tree(Dj, attribute_list) cho nút N 
13. Endfor 
14. Return N 
5.2.2. Lựa chọn thuộc tính 
Việc lựa chọn thuộc tính thực hiện nhờ việc lựa chọn các tiêu chí phân chia sao cho việc 
phân nguồn dữ liệu D đã cho một cách tốt nhất thành các lớp phân biệt. Nếu chúng ta chia D thành 
các vùng nhỏ hơn dựa trên các kết quả tìm được của tiêu chí phân chia, thì mỗi vùng sẽ khá là thuần 
chủng (Nghĩa là các tập các vùng đã phân chia có thể hoàn toàn thuộc về cùng một lớp). Điều này 
giúp xác định cách các bộ giá trị tại một nút xác định sẽ được chia thế nào. Cây được tạo cho phân 
vùng D được gán nhãn với tiêu chí phân chia, các nhánh của nó được hình thành căn cứ vào các kết 
quả phân chia của các bộ. 
Giả sử D là một phân vùng dữ liệu chứa các bộ huấn luyện được gán nhãn. Các nhãn có m 
giá trị phân biệt xác định m lớp, Ci (với i = 1,..,m). Gọi Ci,D là tập các bộ của lớp Ci trong D 
Thông tin cần thiết để phân lớp một bộ trong D cho bởi 
Trong đó pi là khả năng một bộ trong D thuộc về lớp Ci được xác định bởi |Ci,D| /|D|. 
Giờ giả sử chúng ta phân chia các bộ D dựa trên một số thuộc tính A có v giá trị phân biệt 
{a1, .., av}. Thuộc tính A có thể dùng để chia D thành v phân vùng hoặc tập con {D1, D2, …, Dv} 
trong đó Dj chứa các bộ trong D có kết quả đầu ra aj. Các phân vùng đó sẽ tương đương với các 
nhánh của nút N. 
Thông tin xác định xem việc phân chia đã gần tiếp cận đến một phân lớp được cho như sau 
 72 
 là trọng lượng của phân vùng thứ j. InfoA(D) thể hiện thông tin cần thiết để phân lớp 
một bộ của D dựa trên phân lớp theo A. Giá trị thông tin nhỏ nhất sẽ cho ra phân vùng thuần túy 
tương ứng. 
Độ đo thông tin thu được được cho 
Gain(A) sẽ cho chúng ta biết bao nhiêu nhánh có thể thu nhận được từ A. Thuộc tính A với 
độ đo thông tin thu được lớn nhất sẽ được dùng làm thuộc tính phân chia của nút N.
 73 
MỘT SỐ ĐỀ THI MẪU 
 74 
Trƣờng Đại Học Hàng Hải Việt Nam 
Khoa Công nghệ Thông tin 
BỘ MÔN HỆ THỐNG THÔNG TIN 
-----***----- 
THI KẾT THÚC HỌC PHẦN 
Tên học phần: KHAI PHÁ DỮ LIỆU 
Năm học: x 
Đề thi số: Ký duyệt đề: 
x x 
Thời gian: 60 phút 
Câu 1: (2 điểm) 
Trình bày khái niệm khai phá dữ liệu? 
Câu 2: (4 điểm) 
 Cho bảng tổng hợp sau biểu diễn dữ liệu tổng hợp kết quả bán hàng của một siêu thị, 
trong đó hot-dogs thể hiện số giao dịch có chứa hot-dog trong danh sách mặt hàng, 
 thể hiện số giao dịch không có chứa hot-dog trong danh sách, tương tự như vậy 
đối với hamburgers. 
 Hot-dogs 
Hamburgers 2.000 500 2.500 
 1.000 1.500 2.500 
 3.000 2.000 5.000 
a. Giả sử luật kết hợp đã được khai phá. Cho min_sup = 
25% và min_conf = 50%. Luật trên có phải là luật kết hợp mạnh hay không? Giải 
thích? 
b. Dựa trên các dữ liệu đã cho, hãy cho biết việc mua hot-dog có độc lập với việc mua 
humbergers hay không? Nếu không hãy cho biết mối quan hệ tương quan giữa hai 
mặt hàng trên? 
Câu 3: (2 điểm) 
Hãy trình bày ý nghĩa của tiền xử lý dữ liệu trong kỹ thuật khai phá dữ liệu? 
Câu 4: (2 điểm) 
Cho tập dữ liệu dùng để phân tích về độ tuổi được sắp xếp tăng dần như sau: {13, 
15, 16, 16, 19, 20, 20, 21, 22, 22, 25, 25, 25, 25, 30, 33, 33, 35, 35, 35, 35, 36, 40, 45, 46, 
52, 70} 
a. Sử dụng phương pháp làm mịn biên với độ rộng bin là 5. Minh họa các bước thực 
hiện? 
b. Sử dụng phương phương pháp chuẩn hóa min-mã để biến đổi giá trị tuổi 35 về 
khoảng [0.0, 1.0]. 
----------------------------***HẾT***---------------------------- 
Lưu ý: - Không sửa, xóa đề thi, nộp lại đề sau khi thi 
 75 
Trƣờng Đại Học Hàng Hải Việt Nam 
Khoa Công nghệ Thông tin 
BỘ MÔN HỆ THỐNG THÔNG TIN 
-----***----- 
THI KẾT THÚC HỌC PHẦN 
Tên học phần: KHAI PHÁ DỮ LIỆU 
Năm học: x 
Đề thi số: Ký duyệt đề: 
x x 
Thời gian: 60 phút 
Câu 1: (2 điểm) 
Trình bày thuật toán Apriori? 
Câu 2: (4 điểm) 
Cho một cơ sở dữ liệu với 5 giao dịch, giả sử độ min_sup = 60% và min_conf= 80% 
TID Mặt hàng 
T100 {M, O, N, K, E, Y} 
T200 {D, O, N, K, E, Y} 
T300 {M, A, K, E} 
T400 {M, U, C, K, Y} 
T500 {C, O, O, K, I, E} 
a. Tìm tất cả tất cả các tập phổ biến Itemsets sử dụng thuật toán Apriori ? 
b. Liệt kê tất cả các luật kết hợp mạnh (với độ support s, và confidence c) đáp ứng tân 
từ sau, trong đó X là biến biểu diễn khách hàng và itemi là các biến biểu diễn các mặt 
hàng (ví dụ A, B, …) 
Câu 3: (2 điểm) 
Trình bày các điểm khác biệt giữa kho dữ liệu và một cơ sở dữ liệu thông thường? 
Câu 4: (2 điểm) 
Cho tập dữ liệu dùng để phân tích về độ tuổi được sắp xếp tăng dần như sau: {13, 
15, 16, 16, 19, 20, 20, 21, 22, 22, 25, 25, 25, 25, 30, 33, 33, 35, 35, 35, 35, 36, 40, 45, 46, 
52, 70} 
a. Sử dụng phương pháp làm mịn trung vị với độ rộng bin là 3. Minh họa các bước 
thực hiện? 
b. Sử dụng phương phương pháp chuẩn hóa decimal-scale để biến đổi giá trị tuổi 35. 
----------------------------***HẾT***---------------------------- 
Lưu ý: - Không sửa, xóa đề thi, nộp lại đề sau khi thi 
 76 
Trƣờng Đại Học Hàng Hải Việt Nam 
Khoa Công nghệ Thông tin 
BỘ MÔN HỆ THỐNG THÔNG TIN 
-----***----- 
THI KẾT THÚC HỌC PHẦN 
Tên học phần: KHAI PHÁ DỮ LIỆU 
Năm học: x 
Đề thi số: Ký duyệt đề: 
x x 
Thời gian: 60 phút 
Câu 1: (2 điểm) 
Cho ví dụ về một nguồn dữ liệu lưu trữ có cấu trúc bảng, cấu trúc semi-structured, 
hoặc không cấu trúc? 
Câu 2: (4 điểm) 
Cho một cơ sở dữ liệu với 5 giao dịch, giả sử độ min_sup = 60% và min_conf= 80% 
TID Mặt hàng 
T100 {M, O, N, K, E, Y} 
T200 {D, O, N, K, E, Y} 
T300 {M, A, K, E} 
T400 {M, U, C, K, Y} 
T500 {C, O, O, K, I, E} 
a. Tìm tất cả tất cả các tập phổ biến Itemsets sử dụng thuật toán Apriori ? 
b. Liệt kê tất cả các luật kết hợp mạnh (với độ support s, và confidence c) đáp ứng tân 
từ sau, trong đó X là biến biểu diễn khách hàng và itemi là các biến biểu diễn các mặt 
hàng (ví dụ A, B, …) 
Câu 3: (2 điểm) 
Các bước của quá trình khai phá dữ liệu? 
Câu 4: (2 điểm) 
Làm mịn dữ liệu sử dụng kỹ thuật làm tròn cho tập sau: 
Y = {1.17, 2.59, 3.38, 4.23, 2.67, 1.73, 2.53, 3.28, 3.44} 
Sau đó biểu diễn tập thu được với các độ chính xác: 
a. 0.1 
b. 1. 
----------------------------***HẾT***---------------------------- 
Lưu ý: - Không sửa, xóa đề thi, nộp lại đề sau khi thi 
 77 
Trƣờng Đại Học Hàng Hải Việt Nam 
Khoa Công nghệ Thông tin 
BỘ MÔN HỆ THỐNG THÔNG TIN 
-----***----- 
THI KẾT THÚC HỌC PHẦN 
Tên học phần: KHAI PHÁ DỮ LIỆU 
Năm học: x 
Đề thi số: Ký duyệt đề: 
x x 
Thời gian: 60 phút 
Câu 1: (2 điểm) 
Nhiệm vụ chính của quá trình khai phá dữ liệu? 
Câu 2: (4 điểm) 
 Cho bảng tổng hợp sau biểu diễn dữ liệu tổng hợp kết quả bán hàng của một siêu thị, 
trong đó hot-dogs thể hiện số giao dịch có chứa hot-dog trong danh sách mặt hàng, 
 thể hiện số giao dịch không có chứa hot-dog trong danh sách, tương tự như vậy 
đối với hamburgers. 
 Hot-dogs 
Hamburgers 2.000 500 2.500 
 1.000 1.500 2.500 
 3.000 2.000 5.000 
a. Giả sử luật kết hợp đã được khai phá. Cho min_sup = 
30% và min_conf = 70%. Luật trên có phải là luật kết hợp mạnh hay không? Giải 
thích? 
b. Dựa trên các dữ liệu đã cho, hãy cho biết việc mua hot-dog có độc lập với việc mua 
humbergers hay không? Nếu không hãy cho biết mối quan hệ giữa hai mặt hàng trên? 
Câu 3: (2 điểm) 
Trình bày các điểm khác biệt giữa hai phương pháp phân lớp và phân cụm dữ liệu? 
Câu 4: (2 điểm) 
Cho tập mẫu với các giá trị bị thiếu 
o X1 = {0, 1, 1, 2} 
o X2 = {2, 1, −, 1} 
o X3 = {1, −, −, 0} 
o X4 = {−, 2, 1, −} 
Nếu miền xác định của tất cả các thuộc tính là [0, 1, 2], hãy xác định các giá trị bị thiếu biết 
rằng các giá trị đó có thể là một trong số các xác trị của miền xác định? Hãy giải thích 
những cái được và mất nếu rút gọn chiều của kho dữ liệu lớn? 
----------------------------***HẾT***---------------------------- 
Lưu ý: - Không sửa, xóa đề thi, nộp lại đề sau khi thi 
 78 
Trƣờng Đại Học Hàng Hải Việt Nam 
Khoa Công nghệ Thông tin 
BỘ MÔN HỆ THỐNG THÔNG TIN 
-----***----- 
THI KẾT THÚC HỌC PHẦN 
Tên học phần: KHAI PHÁ DỮ LIỆU 
Năm học: x 
Đề thi số: Ký duyệt đề: 
x x 
Thời gian: 60 phút 
Câu 1: (2 điểm) 
Kỹ thuật khai phá dữ liệu bao gồm những điểm cơ bản nào? 
Câu 2: (4 điểm) 
Cho một cơ sở dữ liệu với 5 giao dịch, giả sử độ min_sup = 60% và min_conf= 80% 
TID Mặt hàng 
T100 {M, O, N, K, E, Y} 
T200 {D, O, N, K, E, Y} 
T300 {M, A, K, E} 
T400 {M, U, C, K, Y} 
T500 {C, O, O, K, I, E} 
a. Tìm tất cả tất cả các tập phổ biến Itemsets sử dụng thuật toán Apriori ? 
b. Liệt kê tất cả các luật kết hợp mạnh (với độ support s, và confidence c) đáp ứng tân 
từ sau, trong đó X là biến biểu diễn khách hàng và itemi là các biến biểu diễn các mặt 
hàng (ví dụ A, B, …) 
Câu 3: (2 điểm) 
Trình bày khái niệm dự đoán, cho ví dụ và phân tích? 
Câu 4: (2 điểm) 
Nếu các tập itemset được cấu trúc sao cho A + {A1, A2, A3}, B= {B1, B2}, C = {C1, C2, C3}, 
D = {D1, D2} và E = {E1, E2} 
a. Hãy tìm các tập itemset được định nghĩa trên mức độ khái niệm? 
b. Tìm các luật kết hợp đáng tin cậy cho các tập itemset ở câu trên. 
----------------------------***HẾT***---------------------------- 
Lưu ý: - Không sửa, xóa đề thi, nộp lại đề sau khi thi