TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2
• • • •
KHOA CÔNG NGHỆ THÔNG TIN
■
NGUYỄN VIỆT DŨNG
ỨNG DỤNG CÂY QUYẾT ĐỊNH ĐỂ PHÂN LOẠI
KHÁCH HÀNG VAY VỐN CỦA NGÂN HÀNG TMCP
NGOẠI THƯƠNG CHI NHÁNH VIỆT TRÌ
KHÓA LUẬN TÓT NGHIỆP ĐẠI HỌC
• • • •
Chuyên ngành: Khoa học máy tính
HÀ NỘI - 2015
TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2
• • • •
KHOA CÔNG NGHÊ THÔNG TIN NGUYỄN VIỆT DŨNG
ỨNG DỤNG CÂY QUYẾT ĐỊNH ĐẺ PHÂN LOẠI
KHÁCH HÀNG VAY VỐN CỦA NGÂN HÀNG TMCP
NGOẠI THƯƠNG CHI NHÁNH VIỆT TRÌ
KHÓA LUÂN TÓT NGHIÊP ĐAI HOC • • • •
Chuyên ngành: Khoa học máy tính
Người hướng dẫn khoa học TS. LƯU THI
BÍCH HƯƠNG
HÀ NỘI – 2015
■
LỜI CẢM ƠN
Để hoàn thành được khóa luận này, trước hết em xin gửi lòi cảm ơn sâu sắc nhất tới
TS. Lưu Thị Bích Hương đã tận tình hướng dẫn, chỉ bảo, định hướng, đóng góp những ý
kiến quý báu cho em trong suốt quá trình thực hiện.
Em xin chân thành cảm ơn các thầy, cô giáo trong khoa Công nghệ Thông tin, trường
Đại học Sư phạm Hà Nội 2 đã quan tâm giảng dạy và giúp đõ em trong suốt bốn năm học
vừa qua cũng như trong thòi gian em làm bài khóa luận này. Là sinh viên khoa Công nghệ
thể làm gì với những dữ liệu này, nhưng họ vẫn tiếp tục thu thập và lưu trữ vì
hy yọng những dữ liệu này sẽ cung cấp cho họ những thông tin quý giá một
cách nhanh chóng để đưa ra những quyết định kịp thời vào một lúc nào đó.
Chính vì vậy, các phương pháp quản tri và khai thác cơ sở dữ liệu truyền thống
ngày càng không đáp ứng được thực tế. Từ đó đã làm phát triển một khuynh
hướng kỹ thuật mới đó là kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD -
Knowledge Discovery and Data Mining).
Cho đến nay, khai phá dữ liệu ngày càng được nghiên cứu, phát triển và
đã đạt được những thành tựu đáng kể trong các lĩnh vực: kinh doanh, y tế,
công nghệ sinh học, quân sự, bưu chính viễn thông, xây dựng, Rất nhiều tổ
chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các
hoạt động sản xuất kinh doanh của mình và thu được những lợi ích to lớn.
Ngành công nghiệp ngân hàng đã bắt đầu nhận ra sự cần thiết của các kỹ thuật
khai phá dữ liệu, các kỹ thuật đó có thể giúp họ cạnh tranh trên thị trường. Các
ngân hàng đã và đang sử dụng các công cụ khai phá dữ liệu cho việc phân
khúc khách hàng và lọi nhuận, chấm điểm tín dụng, phê duyệt, quảng bá và
bán sản phẩm, phát hiện các giao dịch gian lận, Việc sử dụng phương pháp
khai phá tri thức từ dữ liệu để phân loại khách hàng vay vốn là một phương
pháp mới nhằm giảm nguy cơ trong rủi ro tín dụng.
Với mong muốn nghiên cứu về việc ứng dụng cây quyết định để phân
loại khách hàng của ngân hàng thương mại cổ phần Ngoại thương, em đã chọn
đề tài “ủng dụng cây quyết định để phân lom khách hàng vay vốn của Ngân
5
hàng thương mại cổ phần Ngoại thương, chi nhánh Việt Trì” làm khóa luận
tốt nghiệp.
2. Mục đích, nhiệm vụ nghiên cứu
+ lìm hiểu khai phá dữ liệu, các ứng dụng khai phá dữ liệu trong lĩnh vực
ngân hàng.
+ Cây quyết định, thuật toán ID3.
+ Xây dựng ứng dụng cây quyết định để phân loại khách hàng vay vốn của
nghiên cứu và kết quả đạt được qua những phương pháp trên.
ứng dụng kết họp kỹ thuật phân loại và mô hình cây quyết định để
phân loại khách hàng vay vốn của Ngân hàng thương mại.
6. Cấu trúc khóa luân
Ngoài lời cảm ơn, mở đàu, kết luận và hướng phát triển, tài liệu tham
khảo, khóa luận có những nội dung sau:
Chương 1: Cơ sở lý thuyết - Chương này nghiên cứu tổng quan về thuật
toán cây quyết định. Phát biểu bài toán xây dựng cây quyết định trong việc
phân loại khách hàng vay vốn của ngân hàng.
Chương 2: Khai phá dữ liệu - Tìm hiểu về khám phá tri thức, khai phá dữ
liệu và một số phương pháp khai phá dữ liệu thông dụng. Chương này đưa ra
những ứng dụng cụ thể của khai phá dữ liệu trong ngân hàng.
Chương 3: ửng dụng khai phá dữ liệu để phân loại khách hàng -
Chương này tìm hiểu về thuật toán ID3 để xây dựng cây
quyết định; nghiên cứu tổng quan về quy trình tín dụng từ
đó xây dựng chương trình mô phỏng cây quyết định trong
việc phân loại khách hàng vay vốn.
CHƯƠNG 1: Cơ SỞ LÝ THUYẾT
7
1.1. Giới thiệu
Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo
(predictive model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện
tượng tới các kết luận về giá trị mục tiêu của sự vật/hiện tượng. Mỗi một nút
trong (internal node) tương ứng với một biến; đường nối giữa nó vói nút con
của nó thể hiện một giá tri cụ thể cho biến đó. Mỗi nút là đại diện cho giá ữị dự
đoán của biến mục tiêu, cho trước các giá tri của các biến được biểu diễn bởi
đường đi từ nút gốc tới nút lá đó. Kỹ thuật học máy dùng trong cây quyết định
được gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây
quyết định.
Học bằng cây quyết định cũng là một phương pháp thông dụng trong
, là các biến sẽ giúp thực hiện công việc phân lớp
dữ liệu.
8
Cây quyết định là một cấu trúc phân cấp của các nút và các nhánh (mang
giá trị của thuộc tính). CÓ3 loại nút trên cây:
+ Nút gốc
+ Nút nội bộ: mang tên thuộc tính của CSDL +
Nút lá: mang tên lớp Cị
Cây quyết định được sử dụng trong phân lớp bằng cách duyệt từ nút gốc
của cây cho đến khi đụng đến nút lá, từ đó rút ra lớp của đối tượng cần xét.
Ví dụ: Cây quyết định phân lớp mức lương.
Hình 1.1: Cây quyết định phân lớp mức lương
1.2. Các kiểu cây quyết định
Cây quyết định còn có hai tên khác là cây hồi quy và cây phân loại.
+ Cây hồi quy (Regression tree) ước lượng các hàm 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 giá một ngôi
nhà hoặc khoảng thòi gian một bệnh nhân nằm viện.
+ Đây là một phương pháp thống kê mà giá trị kỳ vọng của một hay
nhiều biến ngẫu nhiên được dự đoán dựa vào điều kiện của các biến ngẫu nhiên
(đã tính toán) khác. Cụ thể, có hồi qui tuyến tính, hồi qui lôgic, hồi qui Poisson
và học có giám sát. Phân tích hồi qui không chỉ là trùng khớp đường cong (lựa
chọn một đường cong mà vừa khớp nhất với một tậpđiểm dữ liệu); nó còn phải
trùng khớp vói một mô hình, vói các thành phần ngẫu nhiên và xác định
{deterministic and stochastic components). Thành phần xác định được gọi là bộ
9
dự đoán (predictor) và thành phần ngẫu nhiên được gọi là phần sai số {error
term).
+Phân loại (Classification): Là phương pháp dự báo, cho phép phân loại
một đối tượng vào một hoặc một số lớp cho trước. Phân loại bằng thống kê là
một thủ tục thống kê ừong đó các cá thể riêng biệt sẽ được sắp vào từng nhóm
+ Cây quyết định có thể xử lý tốt một lượng dữ liệu lớn trong thời gian
ngắn. Có thể dùng máy tính cá nhân để phân tích các lượng dữ liệu lớn trong
một thời gian đủ ngắn để cho phép các nhà chiến lược đưa ra quyết định dựa
trên phân tích của cây quyết định.
+ 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 được
sang dạng tiếng Anh, hoặc các câu lệnh SQL. Đây là ưu điểm nổi bật của kỹ
thuật này. Thậm chí vói những tập dữ liệu lớn khiến cho hình dáng cây quyết
định lớn và phức tạp, việc đi theo bất cứ đường nào trên cây là dễ dàng theo
nghĩa phổ biến và rõ ràng. Do yậy sự 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 minh bạch.
+ Khả năng thực thi trong những lĩnh vực hướng quy tắc
Điều này nghe có vẻ hiển nhiên, nhưng 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. Rất nhiều lĩnh vực từ di truyền tói 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 (underlying rules) do khá phức tạp và tối
nghĩa bởi những dữ liệu lỗi (noisy). Cây quyết định là một sự lựa chọn tự nhiên
khi nghi ngờ sự tồn tại của các quy tắc ẩn, không rõ ràng.
+ Dễ dàng tính toán trong khi phân lớp
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 nút. 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 hàm logic và số nguyên là
những toán hạng thực thi nhanh và đơn giản. Đây là một ưu điểm quan trọng
bởi trong môi trường thương mại, các mô hình dự đoán thường được sử dụng
để phân lớp hàng triệu thậm trí hàng tỉ bản ghi.
1
+ Khả năng xử lý với cả thuộc tính liên tục và thuộc tính ròi rạc
Cây quyết định xử lý “tốt” như nhau với thuộc tính liên tục và thuộc tính
Win
Temp
Pla
Hig
Weak
Sunn
Ho
N
Hig
Sunn
Ho
Stron
N
Overcast
Hig
Weak
Ho
Ye
Rai
Mil
Hig
Weak
Ye
Rai
Coo
Normal
Weak
N
Rai
Coo
Overcast
Stron
Ye
Normal
Weak
Overcast
Ho
Ye
Rai
Mil
Hig
Stron
N
Hình 1.2: Cây quyết định có chơi golf hay không
1.5. Thuật toán cây quyết định
Cây quyết định có các tính chất sau:
+ Mỗi nút trong (internal node) biểu diễn một thuộc tính càn kiểm tra
giá tri (anattribute to be tested) đối vói các tập thuộc tính.
+ Nút lá (leaf node) hay còn gọi là nút trả lòi biểu thị cho một lớp các
trường hợp mà nhãn của nó là tên của lớp, nó biểu diễn một lớp.
+ Nút nhánh (branch) từ một nút sẽ tương ứng với một giá tri có thể
của thuộc tính gắn với nút đó.
+ Nhãn (lable) của nút này là tên của thuộc tính và có một nhánh nối
nút này đến các cây con ứng vói mỗi kết quả có thể có phép thử. Nhãn của
nhánh này là các giá ưị của thuộc tính đó. Nút trên cùng gọi là nút gốc.
Đây là cây quyết định kiểm tra khi nào chơi golf, khi nào không chơi.
1.5.1. Xử lý dữ liệu
Trong bước này dữ liệu được thu nhậ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 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
một tiêu chuẩn để đánh giá vấn đề này. Có rất nhiều tiêu chuẩn được đánh giá được sử
dụng đó là: Lượng thông tin thu thêm IG (Information Gain), thuật toán ID3 của John
Ross Quilan.
Tiêu chuẩn tách 1 chiều (Univariate Splitting Criteria) :Nghĩa là tách chỉ dựa trên
1 thuộc tính.
Xét theo cấu trúc của mẫu dữ liệu thì có 3 tiêu chuẩn:
+ Impurity-base Criteria: Khi tất cả các mẫu dữ liệu thuộc về 1 phân lớp, ta
gọi đó là Purity. Ngược lại, khi các mẫu dữ liệu tạo ra nhiều phân lớp thì đó gọi là
Impurity.
+ Binary criteria Dùng để tạo cây quyết định nhị phân. Các tiêu chuẩn thường
được sử dụng đối với tiêu chuẩn này là:
- Twoing Criterion
- Orthogonal (ORT) Criterion
- Kolmogorov-Smimov Criterion
- AUC-Splitting Criteria
+ Normalized impurity based criteria: Dùng tiêu chuẩn này khi thuộc tính có
nhiều giá tri hiện hành (dĩ nhiên các giá trị này phải thuộc miền giá trị, ví dụ với 100
mẫu tín có 80 giá trị khác nhau của thuộc tính khi sử dụng phép chiếu lên thuộc tính).
Tiêu chuẩn tách đa chiều: Khác với tách 1 chiều nghĩa là tách theo 1 thuộc tính,
tiêu chuẩn tách đa chiều sử dụng kết hợp nhiều thuộc tính cùng lúc để phân tách. Tuy
nhiên, điều này sẽ ảnh hưởng tới performance nên ít được sử dụng.
1.5.4. Tiêu chuẩn dừng
Tập trung một số tiêu chuẩn dừng chung nhất được sử dụng trong cây quyết
định. Tiêu chuẩn dừng truyền thống sử dụng các tập kiểm tra, có thể thay ngưỡng như
là giảm nhiễu, số các mẫu trong một nút, tỉ lệ các mẫu trong nút, hay chiều sâu của cây.
Dưới đây là một số tiêu chuẩn dừng thường được sử dụng:
+ Từng thuộc tính đã được đưa vào dọc theo con đường trên cây.
+ Các mẫu huấn luyện ứng với nút lá có cùng giá ữị thuộc tính đích (chẳng
hạn, chúng có entropy bằng 0).
+ Tất cả các mẫu dữ liệu E thuộc về cùng một lớp duy nhất.
Ngày 22/09/2011, đã khai trương hoạt động chi nhánh Vietcombank Việt Trì, tỉnh
Phú Thọ. Đây là chi nhánh thứ 76 trong hệ thống và là chi nhánh đầu tiên của
Vietcombank trên quê hương đất Tổ cũng như các tỉnh trung du vùng núi phía Bắc.
Từ một ngân hàng chuyên doanh phục vụ kinh tế đối ngoại, Vietcombank ngày
nay đã trở thành một ngân hàng đa năng, hoạt động đa lĩnh vực, cung cấp cho khách
hàng đầy đủ các dịch vụ tài chính hàng đầu trong lĩnh vực thương mại quốc tế; ữong
các hoạt động truyền thống như kinh doanh vốn, huy động vốn, tín dụng, tài ữợ dự án
cũng như mảng dịch vụ ngân hàng hiện đại, kinh doanh ngoại tệ, các công vụ phái sinh,
dịch vụ thẻ, ngân hàng điện tử
Trong một vài năm gần đây nền kinh tế của các nước cũng như ở Việt Nam đang
bị suy thoái, đặc biệt là ngành ngân hàng, khách hàng luôn luôn là nhân tố quan trọng
quyết định sự tồn tài và phát triển của họ. Dựa vào hệ thống quản lý quan hệ khách
hàng, ngân hàng có thể thu thập được các thông tin của khách hàng như thông tin về tài
khoản, nhu cầu, liên lạc và các vấn đề khác. Quan hệ khách hàng không những là một
công nghệ mà còn là một chiến lược kinh doanh, trong đó bao gồm cả quản lý phòng
ngừa rủi ro tín dụng.
Tại ngân hàng thương mại cổ phần Ngoại thương chi nhánh Việt Trì, có bài toán
đặt ra là: Để phòng ngừa rủi ro cho vay tín dụng, các chuyên gia ngân hàng thu thập
các thông tin của khách hàng vay vốn, phân tích và đánh giá các thông tin này để quyết
định xem khách hàng nào được vay vốn hay không.
Bảng dưới đây đưa ra một số thông tin của khách hàng:
CHƯƠNG 2: KHAI PHÁ DỮ LIỆU
2.1. Khám phá tri thức
Khai phá dữ liệu {data mining) là quá trình khám phá các tri thức mới và các tri
thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có.
Yếu tố thành công trong mọi hoạt động kinh doanh ngày nay là việc biết sử dụng
thông tin một cách có hiệu quả. Điều đó có nghĩa là từ các dữ liệu sẵn có, phải tìm ra
thông tin tiềm ẩn có giá trị mà trước đó chưa được phát hiện, tìm ra những xu hướng
phát triển và những yếu tố tác động lên chúng. Nói một cách khác, mục đích của khai
Bảng 1.2: Bảng các thuộc tính của tập dữ liệu Dulieunganhang
8
TaikhoaTietkiein Co, Klione Có,khône
9
TaikboaiiHieutai Co, Klionẹ Có
?
khônẹ
10
TaisaiiThecliap Co, Klionẹ Có
?
khône
11
RESƯLT(Chovay) True, false
Cỏ (True),
Không (False)
phá tri thức và khai phá dữ liệu chính là tìm ra các mẫu hoặc mô hình đang tồn tại ừong
các cơ sở dữ liệu nhưng vẫn còn bị che khuất bởi lượng dữ liệu quá lớn.
Khai phá tri thức có thể hiểu theo nhiều khía cạnh khác nhau, nhưng tựu chung
lại có thể phát biểu khái niệm khai phá tri thức như sau:
Khai phá tri thức trong cơ sở dữ liệu là một quá trình của việc xác định giá trị,
cái mới lạ, tri thức tiềm ẩn và tri thức cuối cùng của các khuôn mẫu/ mô hình ữong dữ
liệu.
Quá trình khai phá tri thức từ cơ sở dữ liệu là một quá trình có sử dụng nhiều
phương pháp và công cụ tin học nhưng vẫn là một quá trình mà trong đó con người là
trung tâm. Do đó, nó không phải là một hệ thống phân tích tự động mà là một hệ thống
bao gồm nhiều hoạt động tương tác thường xuyên giữa con người và cơ sở dữ liệu, tất
nhiên là với sự hỗ trợ của các công cụ tín học. Người sử dụng hệ thống ở đây phải là
người có kiến thức cơ bản về lĩnh vực cần phát hiện tri thức để có thể chọn được đúng
các tập con dữ liệu, các lớp mẫu phù hợp và đạt tiêu chuẩn quan tâm so với mục đích.
Tri thức ở đây là các tri thức rút ra từ các cơ sở dữ liệu, thường để phục vụ cho việc giải
quyết một loạt nhiệm vụ nhất định ữong một lĩnh vực nhất định. Do đó, quá trình phát
Giai đoạn 1: Gom dữ liệu
Gom dữ liệu: Tập hợp dữ liệu là bước đàu tiên trong quá trình khai phá
dữ liệu. Đây là bước được khai thác ưong một cơ sở dữ liệu, một kho dữ liệu
và thậm chí các dữ liệu từ các nguồn ứng dụng Web.
Giai đoạn 2: Trích lọc dữ liệu
Trích lọc dữ liệu: Ở giai đọan này dữ liệu được lựa chọn hoặc phân chia
theo một số tiêu chuẩn nào đó phục vụ mục đích khai thác, ví dụ chọn tất cả
những em học sinh có điểm Trung bình học kỳ lớn hơn 8.0 và có giói tính nữ.
Giai đoạn 3: Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu
Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu: Giai đoạn thứ ba này là
giai đoạn hay bị sao lãng, 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à tính không đủ chặt chẽ, logic. Vì vậy, dữ liệu thường chứa các giá tri vô
nghĩa và không có khả năng kết nối dữ liệu.
Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói
trên. Những dữ liệu dạng này được xem như 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 vì dữ liệu này nếu không được
“làm sạch - tiền xử lý - chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch
nghiêm ttọng.
Giai đoạn 4: Chuyển đổi dữ liệu
Chuyển đổi dữ liệu: Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu
đưa ra có thể sử dụng và điều khiển được bỏi việc tổ chức lại nó, tức là dữ liệu
sẽ được chuyển đổi về dạng phù hợp cho việc khai phá bằng cách thực hiện
các thao tác nhóm hoặc tập hợp.
Giai đoạn 5: Khai phá dữ liệu
Khai phá dữ liệu: Đây là bước mang tính tư duy ừong khai phá dữ liệu.
Ở 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 là nguyên tắc phân loại, nguyên tắc
kết,
Giai đoạn 6: Đánh giá các luật và biểu diễn tri thức
mô hình dự đoán có thể dự đoán được lượng tiền tiêu dùng của các khách hàng
tiềm năng dựa trên những thông tín về thu nhập và nghề nghiệp của khách
hàng. Trong những năm qua, phân lớp dữ liệu đã thu hút sự quan tâm các nhà
nghiên cứu trong nhiều lĩnh vực khác nhau như học máy (machine learning),
hệ chuyên gia (expert system), thống kê (statistics) Công nghệ này cũng ứng
|C^
CL
Cơ sở dữ liệu Kho dữ liệu
World Wide Web
Các kiểu kho chứa
thông tin khác
Hình 2.2: Kiến trúc điển hình của hệ thống khai phá dữ liệu
Copyright: Tài liệu đại học ©