Bài giảng Khai phá dữ liệu - Chương 5: Phân lớp dữ liệu - Nguyễn Vương Thịnh

TR ƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM 
KHOA CÔNG NGHỆ THÔNG TIN 
BÀI G I ẢNG MÔN HỌC  KHAI PHÁ DỮ LIỆU 
Giảng viên : ThS. Nguyễn V ươ ng Thịnh 
Bộ môn : Hệ thống thông tin 
Hải Phòng, 2013 
CHƯƠNG 5: PHÂN LỚP DỮ LIỆU 
2 
Thông tin về giảng viên 
Họ và tên 
Nguyễn Vương Thịnh 
Đơn vị công tác 
Bộ môn Hệ thống thông tin – Khoa Công nghệ thông tin 
Học vị 
Thạc sỹ 
Chuyên ngành 
Hệ thống thông tin 
Cơ sở đào tạo 
Trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội 
Năm tốt nghiệp 
2012 
Điện thoại 
0983283791 
Email 
thinhnv@vimaru.edu.vn 
Website cá nhân 
3 
Thông tin về học phần 
Tên học phần 
Khai phá dữ liệu 
Tên tiếng Anh 
Data Mining 
Mã học phần 
17409 
Số tín chỉ 
03 tín chỉ 
Số tiết lý thuyết 
39 tiết (13 tuần x 03 tiết/tuần) 
Số tiết thực hành 
10 tiết (05 tuần x 02 tiết/tuần) 
Bộ môn phụ trách 
Hệ thống thông tin 
PHƯƠNG PHÁP HỌC TẬP, NGHIÊN CỨU 
Nghe giảng, t hảo luận, trao đổi với giảng viên trên lớp. 
Tự n ghiên cứu tài liệu và làm bài tập ở nhà. 
PHƯƠNG PHÁP ĐÁNH GIÁ 
SV phải t ham dự ít nhất 75% thời gian . 
Có 02 bài kiểm tra viết giữa học phần (X = X 2 = (L 1 + L 2 )/2). 
Thi kết thúc học phần bằng hình thức trắc nghiệm khách quan trên máy tính (Z = 0.5X + 0.5Y). 
4 
Tài liệu tham khảo 
Jiawei Han and Micheline Kamber, Data Mining Concepts and Techniques , Elsevier Inc, 2006. 
Ian H. Witten, Eibe Frank , Data Mining – Practical Machine Learning Tools and Techniques (the second edition) , Elsevier Inc, 2005 ( sử dụng kèm với công cụ Weka ). 
Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4 th Edition) , Pearson Education Inc, 2004. 
Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú, Giáo trình Khai phá dữ liệu Web , NXB Giáo dục, 2009 
5 
6 
Công cụ phần mềm hỗ trợ 
Phần mềm Weka được phát triển bởi nhóm nghiên cứu của trường Đại học Waikato (New Zealand) từ năm 1999. Có thể download về tại địa chỉ:  
CHƯƠNG 5: PHÂN LỚP DỮ LIỆU 
5 .1. KHÁI NIỆM VỀ PHÂN LỚP DỮ LIỆU 
5 .2. PHÂN LỚP DỰA TRÊN XÁC SUẤT CÓ ĐIỀU KIỆN 
(Phân lớp Bayes – Naive Bayesian Classification) 
5 .3. PHÂN LỚP DỰA TRÊN CÂY QUYẾT ĐỊNH 
5 .4. XÂY DỰNG MÔ HÌNH PHÂN LỚP VỚI WEKA 
7 
8 
5 .1 . KHÁI NIỆM VỀ PHÂN LỚP DỮ LIỆU 
Cho tập các lớp C = {C 1 , C 2 ,, C m } và tập dữ liệu D = {X 1 , X 2 ,, X n } 
Phân lớp dữ liệu là sự phân chia các đối tượng dữ liệu vào các lớp. Về bản chất đây quá trình ánh xạ mỗi đối tượng X j ∈ D tương ứng với một lớp C i ∈ C. 
X 1 
X 2 
X 3 
X n-1 
X n 
C 1 
. 
. 
. 
C 3 
C 2 
C m 
. 
. 
. 
D 
C 
f: D → C hay c = f(X) (với X∈ D và c∈ C) 
9 
Mỗi ánh xạ được gọi là một mô hình phân lớp (Classification Model). 
⟹ Làm sao để xây dựng mô hình phân lớp? 
Thông qua quá trình huấn luyện dựa trên tập dữ liệu học (học có giám sát – supervised learning) 
10 
Xây dựng mô hình 
B1 : Chọn một tập ví dụ mẫu (gồm các đối tượng đã được phân lớp): 
 D exam = D 1 ∪ D 2 ∪  ∪ D m trong đó D i = {X|(X ∈ D )∧( X ⟶ C i )} i=1,..,m 
B2 : Tách D exam thành 02 tập: 
Tập dữ liệu học D train 
Tập dữ liệu kiểm tra D test 
Hiển nhiên D exam = D train ∪ D test và thường thì người ta tách sao cho: 
B3 : Dùng D train để xây dựng mô hình (xác định tham số). Có nhiều loại mô hình phân lớp như: Bayes, cây quyết định, luật phân lớp, 
B4 : Dùng D test để kiểm tra, đánh giá mô hình xây dựng được. 
B5 : Chọn mô hình có chất lượng nhất. 
Sử dụng mô hình 
Cho X ∈ D (là tập dữ liệu chưa phân lớp) ⟹ Xác định lớp của X 
11 
5 .2. PHÂN LỚP DỰA TRÊN XÁC SUẤT CÓ ĐIỀU KIỆN 
(Naive Bayes Classifier) 
5 .2.1. Xác suất có điều kiện và công thức Bayes 
Gọi X là một bộ dữ liệu (data tuple). Theo ngôn ngữ xác suất, X được xem là một biến cố (evidence). 
Gọi H là một giả thuyết (hypothesis): bộ X thuộc về lớp C i . 
⟹ Cần xác định P(H|X) : xác suất xảy ra H khi đã xuất hiện X (hay xác suất để X thuộc về lớp C i nếu như đã biết các thuộc tính của X). 
X được xác định thông qua tập giá trị của các thuộc tính 
Nhãn phân lớp 
12 
P(H|X) là xác suất có điều kiện của H đối với X (xác xuất xảy ra H khi biết X xảy ra). 
	 Ví dụ : 	X = (age=35 years old, income=$40,000), 
	H = (buy_computer=Yes) 
	P(H|X) = P(by_computer=yes | age=35 years old, income=$40,000) 
	 ⟹ Xác suất để một người 35 tuổi có thu nhập $40,000 mua máy tính 
P(X|H) là xác suất có điều kiện của X đối với H (xác suất xảy ra X khi biết H xảy ra). 
	 Ví dụ : 
	 P(X|H) = P(age=35 years old, income=$40,000|buy_computer=yes) 
	 ⟹ Xác suất để một người mua máy tính có độ tuổi là 35 và thu nhập là $40,000. 
P(X) là xác suất tiên nghiệm của X. 
	 Ví dụ : P(X) = P(age=35 years old,income=$40,000) ⟹ Xác suất để tìm thấy trong tập dữ liệu đang xét một người có độ tuổi là 35 và thu nhập là $40,000. 
P(H) là xác suất tiên nghiệm của H. 
	 Ví dụ : P(H) = P(buy_computer=Yes) ⟹ Xác suất mua máy tính của khách hàng nói chung (không quan tâm đến độ tuổi hay thu nhập) 
13 
Thomas Bayes 
(1702 – 1761) 
Công thức Bayes: 
14 
5 .2.2. Phân lớp dữ liệu dựa trên xác suất có điều kiện (phân lớp Bayes) 
Bộ phân lớp Bayes hoạt động như sau: 
Cho D là tập dữ liệu học gồm các bộ và nhãn lớp tương ứng (đã được phân lớp). Mỗi bộ được biểu diễn bởi một vector n chiều X = (x 1 , x 2 ,, x n ) trong đó x i là giá trị tương ứng với thuộc tính A i (i = 1, 2,, n). Tập D i = {X|(X ∈ D )∧( X ⟶ C i )} là tập các bộ trong D thuộc về lớp C i . 
Giả sử có m lớp C 1 , C 2 ,, C m . Bộ X được dự đoán là thuộc về lớp C i khi và chỉ khi: P(C i |X) > P(C j |X) với mọi j ≠ i và 1 ≤ j ≤ m (X thuộc về lớp mà xác suất có điều kiện khi biết X là lớn nhất) ⟹ Đi tìm lớp C i trong số m lớp sao cho P(C i |X) là lớn nhất. 
P(X) là giống nhau với tất cả các lớp nên theo công thức Bayes thì P(C i |X) lớn nhất tương ứng với tích P(X|C i )P(C i ) lớn nhất ⟹ Đi tìm C i sao cho tích P(X|C i )P(C i ) là lớn nhất (i = 1, 2,, m). 
Ta có thể tính: 
	và nếu coi n thuộc tính của X là độc lập thì: 
15 
Chú ý: 
Nếu không tính được P(C i ) thì có thể coi P(C 1 ) = P(C 2 ) =  = P(C m ) và bài toán quy về tìm lớp C i trong số m lớp sao cho P(X|C i ) có giá tri lớn nhất . 
Nếu tồn tại P(x k |C i ) = 0 thì có thể áp dụng hiệu chỉnh Lapace và công thức tính của P(x k |C i ) được hiệu chỉnh như sau: 
q: số giá trị khác nhau của A k 
16 
Ví dụ : 
Cho tập dữ liệu học gồm các bộ dữ liệu đã được phân lớp như sau: 
Áp dụng phân lớp Bayes hãy dự đoán bộ dữ liệu 
thuộc lớp nào? 
17 
Có 02 lớp dữ liệu tương ứng với buys_computer = yes và buys_computer = no 
Suy ra: 
Tương tự: 
⟹ X thuộc lớp dữ liệu tương ứng với buys_computer = yes 
18 
5 .3. PHÂN LỚP DỰA TRÊN CÂY QUYẾT ĐỊNH 
5 .3.1. Mô hình phân lớp cây quyết định 
Cây quyết định (decision tree) là một mô hình phân lớp điển hình. 
Cây quyết định bao gồm: 
Các nút trong : biểu diễn cho một thuộc tính được kiểm thử (test). 
Các nút lá : nhãn/mô tả của một lớp (class label). 
Nhánh : xuất phát từ một nút trong, phản ánh kết quả của một phép thử trên thuộc tính tương ứng. 
Married 
Salary 
Acct Balance 
Age 
yes 
no 
poor risk 
fair risk 
good risk 
poor risk 
fair risk 
good risk 
< 20K 
>= 20K 
< 50K 
>= 50K 
5K < 
>= 5K 
< 25 
>= 25 
19 
Married 
Salary 
Acct Balance 
Age 
yes 
no 
poor risk 
fair risk 
good risk 
poor risk 
fair risk 
good risk 
< 20K 
>= 20K 
< 50K 
>= 50K 
5K < 
>= 5K 
< 25 
>= 25 
If (Married = yes) And (Salary > 20K) Then Class = poor risk 
If (Married = yes) And (50K > Salary >= 20K) Then Class = fair risk 
If (Married = yes) And (Salary >= 50K) Then Class = good risk 
If (Married = no) And (Acct Balance < 5K) Then Class = poor risk 
If (Married = no) And (Acct Balance >= 5K) And (Age < 25) Then Class = fair risk 
If (Married = no) And (Acct Balance >= 5K) And (Age >= 25) Then Class = good risk 
Có thể dễ dàng chuyển đổi từ mô hình cây quyết định sang mô hình luật phân lớp bằng cách: đi từ nút gốc cho tới nút lá, mỗi đường đi tương ứng với một luật phân lớp. 
20 
Married 
Salary 
Acct Balance 
Age 
yes 
no 
poor risk 
fair risk 
good risk 
poor risk 
fair risk 
good risk 
< 20K 
>= 20K 
< 50K 
>= 50K 
5K < 
>= 5K 
< 25 
>= 25 
Name 
Age 
Married 
Salary 
Acct Balance 
Class 
Alice 
19 
yes 
30K 
6K 
? 
Pike 
28 
no 
60K 
7K 
? 
Tom 
35 
yes 
10K 
10K 
? 
Peter 
24 
no 
20K 
8K 
? 
Lucas 
40 
no 
20K 
3K 
? 
Name 
Age 
Married 
Salary 
Acct Balance 
Class 
Alice 
19 
yes 
30K 
6K 
fair risk 
Pike 
28 
no 
60K 
7K 
good risk 
Tom 
35 
yes 
10K 
10K 
poor risk 
Peter 
24 
no 
20K 
8K 
fair risk 
Lucas 
40 
no 
20K 
3K 
poor risk 
21 
5 .3.2. Các độ đo sử dụng trong phân lớp 
A. Entropy của tập dữ liệu 
Là lượng thông tin cần để phân loại một phần tử trong tập dữ liệu D. Ký hiệu là Infor(D). 
Gọi: 
p i : xác suất để một phần tử bất kỳ trong D thuộc về lớp C i (i=1, 2,, m). 
D i : Tập các phần tử trong D thuộc về lớp C i . 
Claude Elwood Shannon 
(1916 – 2001) 
22 
B. Entropy của dữ liệu ứng với một thuộc tính 
Là lượng thông tin cần để phân loại một phần tử trong tập dữ liệu D dựa trên thuộc tính A. Ký hiệu là Infor A (D). 
Thuộc tính A dùng để phân tách D thành v phân hoạch (tập con) là D 1 , D 2 ,, D v . 
Mỗi phân hoạch D j có |D j | phần tử. 
Lượng thông tin này sẽ cho biết mức độ trùng lặp giữa các phân hoạch, nghĩa là một phân hoạchchứa các phần tử từ một hay nhiều lớp khác nhau. 
⟹ Mong đợi: Infor A (D) càng nhỏ càng tốt. 
23 
C. Độ lợi thông tin (Information Gain) 
Mục tiêu: Tối thiểu hóa lượng thông tin cần thiết để phân lớp các các mẫu dữ liệu (tối thiểu hóa số lượng các điều kiện kiểm tra cần thiết để phân lớp một bản ghi mới). 
Độ lợi thông tin ứng với thuộc tính A ( ký hiệu Gain(A) ) chính là độ sai biệt giữa Entropy ban đầu của tập dữ liệu (trước phân hoạch) và Entropy của dữ liệu ứng với thuộc tính A (sau khi phân hoạch bởi A). 
24 
5 .3.3. Giải thuật ID3 xây dựng cây quyết định 
Input: 	 Tập dữ liệu học Records gồm m đối tượng (bản ghi) R 1 , R 2 ,, R m . 
	 Tập thuộc tính Attributes gồm m thuộc tính A 1 , A 2 ,, A n . 
Output: 	 Mô hình cây quyết định. 
procedure Build_tree(Records, Attributes) 
begin 
Tạo nút N; 
if (tất cả các bản ghi thuộc về một lớp C i nào đó) then 
begin 
	N.Label = C i ; 
	return N; 
end ; 
if (Attributes = ⍉) then 
begin 
	Tìm lớp C j mà phần lớn các bản ghi r ∈ Records thuộc về lớp đó. 
	N.Label = C j ; 
	return N; 
end ; 
Chọn A i ∈ Attribute sao cho Gain(A i )→max; 
N.Label = A i ; 
for each giá trị v i đã biết của A i do 
begin 
	Thêm một nhánh mới vào nút N ứng với A i = v j ; 
	S j = Tập con của Records có A i = v j ; 
	 if (S j = ⍉) then 	 
	Thêm một nút lá L với nhãn là lớp mà phần lớn các bản ghi r ∈ Records thuộc về lớp đó; 
	Return L; 
	 else 
	Thêm vào nút được trả về bởi Build_Tree(S j , Attribute \{A i }); 
end ; 
end ; 
25 
Phương pháp lựa chọn thuộc tính 
Dùng heuristic để chọn tiêu chí rẽ nhánh tại một nút: Phân hoạch tập dữ liệu học D thành các phân hoạch con với các nhãn phù hợp: 
Xếp hạng mỗi thuộc tính. 
Thuộc tính được chọn để rẽ nhánh là thuộc tính có trị số điểm (score) là lớn nhất. 
Độ đo để chọn thuộc tính phân tách (splitting attribute) là Information Gain (được xây dựng dựa trên lý thuyết thông tin của Claude Elwood Shannon). 
Cụ thể: Thuộc tính có giá trị Information Gain lớn nhất sẽ được chọn làm thuộc tính phân nhánh cho nút N. 
Nút N là nút hiện tại cần phân hoạch các phần tử trong D. 
Thuộc tính phân hoạch đảm bảo sự trùng lắp ngẫu nhiên ít nhất giữa các phân hoạch tạo được. 
⟹ Giúp tối thiểu số phép thử (test) cần để phân loại một phần tử. 
26 
27 
Tính toán tương tự: 
⟹ Chọn age là thuộc tính phân tách 
Ví dụ : Cho tập dữ liệu học: 
28 
29 
Khởi động phần mềm Weka, chọn Explorer: 
5 .4. XÂY DỰNG MÔ HÌNH PHÂN LỚP VỚI WEKA 
30 
Chọn tập tin dữ liệu sử dụng 
31 
Tập dữ liệu mẫu 
32 
Sử dụng luôn tập dữ liệu học đưa vào để kiểm tra mô hình 
Sử dụng tập dữ liệu khác để kiểm tra mô hình 
Sử dụng một số % dữ liệu đưa vào để học và sử dụng phần còn lại để kiểm tra mô hình 
Lựa chọn Thuật toán phân lớp được sử dụng (chọn thuật toán ID3) 
Chỉ định thuộc tính (nhãn) phân lớp 
Cây quyết định xây dựng được 
33 
Outlook 
Humidity 
Windy 
Sunny 
Overcast 
Rainy 
YES 
High 
Normal 
NO 
YES 
True 
False 
NO 
YES 
Q & A 
34