ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC KINH TẾ
KHOA THỐNG KÊ - TIN HỌC

ĐỀ ÁN MÔN HỌC
Đề tài:
ỨNG DỤNG THUẬT TOÁN CÂY QUYẾT ĐỊNH CHO BÀI
TOÁN PHÂN LỚP TRONG XÁC ĐỊNH KHẢ NĂNG HUY
ĐỘNG VỐN CỦA NGÂN HÀNG THÔNG QUA TIỀN GỬI
CÓ KỲ HẠN CỦA KHÁCH HÀNG
Giáo viên hướng dẫn : TH.S NGUYỄN VĂN CHỨC
Sinh viên thực hiện : Lê Thị Tường Vi
Hà Thị Sau
Lớp : 35K14
Đà Nẵng, tháng 8 năm 2012
LỜI CAM ĐOAN
Em xin cam đoan nội dung trong đề tài này là do em thực hiện dưới sự hướng dẫn trực
tiếp của thầy Nguyễn Văn Chức.
Mọi tham khảo dùng trong đề tài này đều được trích dẫn rõ ràng tên tác giả .
Mọi sao chép không hợp lệ vi phạm quy chế đào tạo em xin chịu hoàn toàn trách nhiệm.
Sinh viên thực hiện.
Lê Thị Tường Vi
Hà Thị Sau
-Trang 1-
LỜI MỞ ĐẦU
Trong những năm gần đây, việc nắm bắt được thông tin được coi là chìa khóa của
kinh doanh. Ai thu thập, phân tích và hiểu được thông tin và hành động được nhờ vào những
thông tin đó là kẻ thắng cuộc trong thời đại thông tin này. Chính vì vậy, việc tạo ra thông tin
và mức tiêu thụ thông tin ngày nay ngày càng gia tăng.
Cùng với chức năng khai thác có tính chất tác nghiệp, việc khai thác các cơ sở dữ liệu
(CSDL) phục vụ các yêu cầu trợ giúp quyết định ngày càng có ý nghĩa quan trọng và là nhu

khai phá dữ liệu còn mới mẻ, khối lượng kiến thức trong lĩnh vực khai phá dữ liệu còn nhiều và
liên tục được cập nhật nên chắc chắn không tránh khỏi những sai sót. Kính mong sự đóng góp ý
kiến của thầy giáo để chúng em cố gắng hoàn thiện tốt hơn.
-Trang 3-
CHƯƠNG 1
Tổng quan về khai phá dữ liệu
I. Khai phá dữ liệu (Data Mining)
Khai phá dữ liệu (Data mining) là một khái niệm ra đời vào những năm cuối của thập kỷ
80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các
tập dữ liệu lớn trong thực tế. Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ
liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy (regularities) từ các tập dữ
liệu lớn nhằm mục đích dự đoán các xu thế, các hành vi trong tương lai, hoặc tìm kiếm những
tập thông tin hữu ích mà bình thường không thể nhận diện được. Năm 1989, Fayyad, Piatestsky-
Shapiro và Smyth đã dùng khái niệm Phát hiện tri thức trong cơ sở dữ liệu (Knowledge
Discovery in Database-KDD) để chỉ toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ
liệu lớn. Trong đó, khai phá dữ liệu là một bước đặc biệt trong toàn bộ quá trình, sử dụng các
giải thuật đặc biệt để chiết xuất ra các mẫu (pattern) hay các mô hình từ dữ liệu.
" Khai phá dữ liệu là một quá trình khám phá các thông tin hữu ích từ các tập dữ liệu lớn,
sử dụng phân tích toán học để lấy được các mẫu và các xu hướng tồn tại trong dữ liệu mà
thông thường những mẫu này không thể có được bằng khai thác dữ liệu truyền thống bởi vì
các mối quan hệ quá phức tạp và lượng dữ liệu quá lớn. "
Khai phá dữ liệu nhấn mạnh hai khía cạnh chính đó là khả năng trích xuất thông tin có ích
tự động (Automated) và bán tự động (Semi - Automated) mang tính dự đoán (Predictive). Khai
phá dữ liệu là một lĩnh vực liên ngành, liên quan chặt chẽ đến các lĩnh vực sau:
Statistics (Thống kê) : là một số đo cho một thuộc tính nào đó của một tập mẫu. Mỗi giá trị
thống kê được tính bằng một hàm nào đó và thông tin của môt thống kê mang tính đại diện
cho thông tin của tập mẫu mang lại.
Machine Learning (Máy học): là một phương pháp để tạo ra các chương trình máy tính bằng
việc phân tích các tập dữ liệu. Máy học có liên quan lớn đến thống kê, vì cả hai lĩnh vực đều
nghiên cứu việc phân tích dữ liệu, nhưng khác với thống kê, học máy tập trung vào sự phức

Việc thực hiện một DMM với đầy đủ 4 bước công việc chính của quá trình khai phá dữ liệu là :
 Bước 1: Chuẩn bị dữ liệu (Data Preparation); Trong bước này chúng ta thực hiện các công
việc tiền xử lý dữ liệu theo yêu cầu của mô hình như trích chọn thuộc tính, rời rạc hóa dữ
liệu và cuối cùng là chia dữ liệu nguồn (Data Source) thành 2 tập dữ liệu dùng để huấn
luyện mô hình (Training Data) và kiểm tra mô hình (Testing data).
 Bước 2: Xây dựng mô hình (Data Modeling); ta sử dụng Training Data vừa tạo ra để xây
dựng mô hình.
 Bước 3: Đánh giá mô hình (Validation); Sau khi sử dụng Training Data để xây dựng mô
hình, bây giờ ta sử dụng Testing Data để kiểm tra xem mô hình có đủ tốt để sử dụng hay
không? (Nếu chưa đủ tốt thì phải sử dụng Training Data khác để huấn luyện lại). Có 3 kỹ
thuật chính để kiểm tra mô hình đó là sử dụng Accuracy Chart (Lift Chart), Classification
Matrix và Profit Chart.
 Bước 4: Sử dụng mô hình để dự đoán dự liệu trong tương lai (Model Usage); Sau khi mô
hình được kiểm tra (Testing) nếu độ chính xác đáp ứng yêu cầu thì có thể sử dụng model đã
xây dựng vào dự đoán các dữ liệu chưa biết.
Hình 1.4 Quy trình xây dựng mô hình khai phá dữ liệu.
-Trang 6-
CHƯƠNG 2
Giới thiệu kỹ thuật phân lớp trong khai phá dữ liệu
I.Giới thiệu bài toán phân lớp
Phân lớp (Classification) là tập các phương pháp tìm cách xếp các đối tượng vào các lớp đã biết
trước.
Dữ liệu của bài toán phân lớp có dạng:
(x,y) = (x1,x2,x3 ,xk,y)
Trong đó:
- x1,x2,x3 ,xk là các thuộc tính đầu vào của đối tượng ( hay gọi là biến độc lập)
- y là lớp các đối tượng (biến phụ thuộc)
Ví dụ mô hình phân lớp dự báo thời tiết có thể cho biết thời tiết ngày mai là mưa hay nắng (biến
phụ thuộc) dựa vào các thông số hay các biến độc lập như độ ẩm, sức gió, nhiệt độ Hay
trong lĩnh vực ngân hàng, để biết khách hàng có kế hoạch trả nợ hay không, ngân hàng sẽ

Cheap
Medium
Bus
Female
1
Cheap
Medium
Train
Female
0
Cheap
Low
Bus
Male
1
Cheap
Medium
Bus
Male
0
Standard
Medium
Train
Female
1
Standard
Medium
Train
Female
1

Dựa vào các luật này, việc dự đoán lớp cho các dữ liệu chưa biết (unseen data hay Testing data)
rất đơn giản. Trong ví dụ này, Alex có giá trị của thuộc tính Travel Cost/Km là Standard
nên sẽ chọn phương tiện là Train (Rule 2) mà không cần quan tâm đến các thuộc tính khác
của Alex. Buddy có giá trị của thuộc tính Travel Cost/Km là Cheap và Gender của anh ta
là Male nên anh ta sẽ chọn Bus (Rule 3). Cheery cũng có giá trị thuộc tính Travel Cost/Km
là Cheap nhưng Gender là Female và sở hữu 1 xe hơi cho nên theo cây quyết định trên
(Rule 5) cô ta sẽ chọn phương tiện là Train.
Có rất nhiều thuật toán phân lớp như ID3, J48, C4.5, CART (Classification and Regression
Tree),…Việc chọn thuật toán nào để có hiệu quả phân lớp cao tùy thuộc vào rất nhiều yếu
tố, trong đó cấu trúc dữ liệu ảnh hưởng rất lớn đến kết quả của các thuật toán. Chẳn hạn như
thuật toán ID3 và CART cho hiệu quả phân lớp rất cao đối với các trường dữ liệu số
(quantitative value) trong khi đó các thuật toán như J48, C4.5 có hiệu quả hơn đối với các
dữ liệu Qualititive value (ordinal, Binary, nominal)
III.Thuật toán xây dựng cây quyết định ID3
Thuật toán ID3 là thuật toán phân lớp dữ liệu dựa trên cây quyết định hiệu quả và phổ biến trong
những ứng dụng khai phá cơ sở dữ liệu có kích thước nhỏ được phát minh bởi
J.RossQuinlanvào năm 1979.Thuật toán ID3 sử dụng thông tin lý thuyết phát minh bởi
Shannon trong năm 1948, xây dựng cây quyết định từ trên xuống dưới. Gain Infomation
được sử dụng để chọn các thuộc tính hữu ích nhất để phân loại.
-Trang 9-
Nếu có n thông điệp có thể xảy ra, thì xác suất p của 1/n và thông tin chuyển tải của một thông
điệp là
-log2 (p) = log2 (n)
Ví dụ, nếu có 16 tin nhắn, thì ta có log2(16)=4 và chúng ta cần 4 bit để xác định mỗi thông điệp
Nói chung, chúng ta đưa ra một phân bố xác suất P=(p1, p2, , pn) thì các thông tin chuyển tải
bởi phân phối , còn được gọi là Entropy của P là:
I(P) = -(p1*log2(p1) + p2*log2(p2) + + pn*log2(pn))
Ví dụ, nếu P là (0.5, 0.5) thì
I(P)= -(0.5*log2(0.5)+ 0.5*log2(0.5)) =1
Nếu P là (0.67, 0.33) thì I(P) là 0.92, nếu P là (1, 0) thì I(P) là 0.

đường dẫn từ gốc.
 Tư tưởng thuật toán ID3
Các thuật toán ID3 được sử dụng để xây dựng một cây quyết định, cho một tập hợp của các
thuộc tính không phân loại C1,C2, , Cn, C thuộc tính phân loại,và một training set T của
các bản ghi
Function ID3(R, C, S):
Input:
R: một tập hợp các thuộc tính không-phân loại.
C: thuộc tính phân loại.
S: một training set.
Output:
Quay lại cây quyết định.
Begin
Nếu S rỗng, quay lại một nút đơn với giá trị Failure;
Nếu S bao gồm tất cả các giá trị tương tự cho các thuộc tính không phân loại, quay lại 1 nút duy
nhất có giá trị đó ;
Nếu R rỗng, thì trả về nút đơn như giá trị thường gặp nhất của các giá trị của các thuộc tính phân
loại được tìm thấy trong bản ghi của S; [Lưu ý rằng sau đó sẽ có lỗi, có nghĩa là, bản ghi sẽ
không đúng phân loại];
-Trang 11-
Cho D là các thuộc tính với Gain(D,S) lớn nhất trong số các thuộc tính của R;
Cho {dj| j=1,2, , m} là giá trị của thuộc tính D;
Cho {Sj| j=1,2, , m} là tập hợp con của S bao gồm bản ghi tương ứng với dj cho thuộc tính D;
Returns Cây với gốc có nhãn D và nhãn vòng cung d1, d2, , dm sẽ tương ứng với các cây.
ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), , ID3(R-{D}, C, Sm);
end ID3;
 Ví dụ minh họa
Chúng ta có dữ liệu mẫu sau: bao gồm 4 thuộc tính là Outlook, Temperature, Humidity, Windy
và 1 thuộc tính phân lớp có chơi hay không chơi tennis (Play?)
Hình 2.2Dữ liệu cho ví dụ minh họa

Cây quyết định hoàn chỉnh cuối cùng:
-Trang 14-
Hình 2.5 Cây quyết định cuối cùng
-Trang 15-
Chương 3
Triển khai ứng dụng phân lớp dữ liệu
I.Mô tả bài toán
Khai phá tri thức(các luật) có ý nghĩa trong hoạt động tín dụng của Ngân Hàng,nhằm hạn
chế rủi ro, dự đoán khả năng trả lãi của khách hàng và nâng cao phát hiện khách hàng tiềm năng.
Mục đích của việc xây dựng mô hình phân lớp là để phân ra các lớp đối tượng khác nhau. Thông
qua kết quả đạt được là chúng ta có thể dự đoán xem một khách hàng có đăng kí gửi tiền có kì
hạn hay không dựa vào các thuộc tính đầu vào như:
+Những khách hàng nào sẽ có khả năng nhất sử dụng dịch vụ gửi hàng có kì hạn của Ngân
Hàng,họ có những đặc điểm như thế nào, để sau này công tác tư vấn thẩm định và đưa ra chiến
lược đối với khách hàng được dễ dàng hơn.
+Khách hàng có loại công việc mang lại nguồn thu thập ổn định và cao thì khả năng gửi
tiền có kì hạn sẽ cao.
+Khách hàng có nhà ở cũng như các khoản cho vay(loan)thường có nhu cầu gửi tiền nhiều
hơn so với khách hàng không có các khoản cho vay,nhà ở.
+Khách hàng nhận được chiến dịch tiếp thị trước đó do Ngân hàng cung cấp mà thành
công sẽ có khả năng gửi tiền có kì hạn vào Ngân Hàng sẽ cao hơn.
+ Khách hàng ở độ tuổi bao nhiêu hay trình độ học vấn,có tín dụng mặc định hay không
cũng ảnh hưởng đến số lượng khách hàng sử dụng dịch vụ.
Do vậy trong môi trường cạnh tranh khốc liệt hiện nay, việc sử dụng phương pháp khai
phá tri thức từ dữ liệu là một phương pháp tiếp cận mới, góp phần giúp Ngân hàng đưa quyết
định kịp thời, tăng cường khả năng cạnh tranh và nâng cao hiệu quả kinh doanh.
II.Thu thập dữ liệu
 Dữ liệu gồm 17 thuộc tính:
STT
Tên Thuộc

Yes,no
6
balance
Nominal
Bình quân hàng năm
bằng đồng Euro
4789,1350,
7
housing
Nominal
Nhà ở
Yes,No
8
loan
Nominal
Cho vay
Yes,No
9
Contact
Nominal
Liên hệ
Cellular,unknown,
10
day
Nominal
Ngày liên lạc cuối cùng của
tháng
12,20,
11
month

Failure,unknown
-Trang 17-
17
y
Nominal
Khách hàng đăng kí gửi tiền
có kì hạn
Yes,No
 Mô tả dữ liệu
Dữ liệu có liên quan với các chiến dịch tiếp thị trực tiếp của một tổ chức ngân hàng Bồ
Đào Nha. Các chiến dịch tiếp thị dựa trên các cuộc gọi điện thoại. Thông thường,nếu có
nhiều hơn một hợp đồng được yêu cầu bởi một khách hàng để truy cập nếu sản phẩm (kỳ
hạn gửi tiền ngân hàng) sẽ là đăng ký(hoặc không).
Ví dụ (4521), lựa chọn ngẫu nhiên từ ngân hàng-full.csv tập dữ liệu nhỏ nhất được
cung cấp để kiểm tra các thuật toán máy tính đòi hỏi hơn học (ví dụ: SVM).
Mục tiêu phân loại là để dự đoán xem các khách hàng có đăng ký tiền gửi có kỳ hạn hay
không (biến y).
Ta sẽ thực hiện công việc này thông qua 4 giai đoạn: Data Preparation; Data Modeling;
Validation; Model Usage.
III. Công cụ xây dựng mô hình
1. Chuẩn bị dữ liệu cho mô hình (Data Preparation)
Công cụ sử dụng là SQL Server Business Intelligent Development Studio (add-ins trong
Excel 2007)
Trong bước này chúng ta thực hiện các công việc tiền xử lý dữ liệu theo yêu cầu của mô
hình như trích chọn thuộc tính, rời rạc hóa dữ liệu (các vấn đề này đã đề cập ở các bài viết trước)
và cuối cùng là chia dữ liệu nguồn (Data Source) thành 2 tập dữ liệu dùng để huấn luyện mô hình
(Training Data) và kiểm tra mô hình (Testing data).
-Trang 18-
Kết quả là Sau bước chuẩn bị dữ liệu ta có 2 sheet chứa dữ liệu để huấn luyện DMM là ra
training Set (70%) và Testing Set (30%).

-Trang 23-
Hình 3.5 Bảng kết quả Lift Chart.
4. Sử dụng mô hình (Model Usage)
Sau khi mô hình được kiểm tra (Testing) nếu độ chính xác đáp ứng yêu cầu thì có thể sử
dụng model đã xây dựng vào dự đoán các dữ liệu chưa biết. Bây giờ ta sẽ sử dụng mô hình