ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

TRẦN XUÂN LỢI ỨNG DỤNG KHAI PHÁ DỮ LIỆU ĐỂ GIẢM THIỂU
RỦI RO TÍN DỤNG LUẬN VĂN THẠC SĨ

ỨNG DỤNG KHAI PHÁ DỮ LIỆU ĐỂ GIẢM THIỂU
RỦI RO TÍN DỤNG

Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 05

LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. NGUYỄN TRỌNG DŨNG
Hà Nội - 2010 I



7
Minsup
Minimum Support

8
Confidence


9
Mincof
Minimum Confidence

10
Training set


11
Test set


12
Information gain


13
Coverage


14

20
Mining Structure


II
21
Mining Model


22
Discretized

hóa

hóa
22
Discrete


23
Key
Khóa chính
Khóa chính
24


29
MINIMUM
PROBABILITY



30
MINIMUM
SUPPORT

 III

DANH MỤC CÁC HÌNH VẼ

STT

Hình 1
 T
Hình 1.1

Hình 1.3.1


Hình 1.3.3.1

Hình 1.3.3.2







Quan 


hàng ScoringF1

Trình  ScoringF1

Trình  ScoringF1 theo %

 ScoringF1

 ScoringF1 theo %

Phng t ScoringF1

PhScoringF1 theo %

 ScoringF1

 ScoringF1 theo %

 ScoringF1

b

theo % 

   
ScoringF1

b
 



 

b
, tính





  

  
F2


vay

 





 VII

LỜI CAM ĐOAN
y là công 



m 2010



VIII

LỜI CẢM ƠN









 , 


 .














 , 
 , 





 , 











T

.

  IX

MỤC LỤC

 
1
:  .
2
1.1  
2
1.1.1 S 

2
1.1.2  .

27
2.1.2  
27
2.2  
28
2.2.1  
29
2.2.2  
30
2.2.3 
31
2.2.3  
32
2.3  
33
2.3.1  
33
2.3.2 Phân nhóm khách hàng 
33 X
2.3.3  
34
2.3  
38
2.3.1  
38
2.3.2  
39

80
3.3.2  
80
3.3.3  
81
3.3.4  
86
IV 
91
 
93

- 1 - MỞ ĐẦU

Khai phá dữ liệu là một quá trình phát hiện những mẫu có giá trị, mới, hữu ích
tiềm năng và hiểu được trong dữ liệu. Kho dữ liệu của một ngân hàng hay một tập
đoàn bán lẻ không ngừng tăng trưởng theo thời gian với tốc độ cao, nhưng chỉ một số
ít trong đó là thực sự có giá trị, có lợi hay hỗ trợ cho việc ra quyết định. Ngày nay khai
phá dữ liệu đã được ứng dụng trong nhiều lĩnh vực của đời sống như bán lẻ, ngân
hàng, tài chính…Khai phá dữ liệu trong lĩnh vực tài chính bao gồm các nhiệm vụ sau:
dự đoán xu hướng thị trường chứng khoán, lãi suất tiền tệ, đo lường xác suất phá sản
của ngân hàng, quản trị rủi ro tài chính, giao dịch hàng hóa tương lai, xếp hạng tín
dụng, chống rửa tiền…
Rủi ro tín dụng là khả năng mất vốn khi khách hàng không thực hiện đầy đủ
nghĩa vụ nợ, theo nghĩa đó khách hàng không trả được nợ khi các khoản nợ đến hạn
bao gồm gốc và lãi dẫn đến chất lượng các khoản nợ suy giảm. Việc ứng dụng khai
phá dữ liệu vào lĩnh vực quản lý rủi ro nói chung và rủi ro tín dụng nói riêng có một ý

lợi cho quá trình ra quyết định.
Hình vẽ dưới đây trình bày một tập dữ liệu giả định về vay nợ ngân hàng gồm
23 trường hợp được biểu diễn trong không gian hai chiều. Mỗi điểm trên đồ thị
biểu diễn một trường hợp vay nợ ở ngân hàng trong quá khứ. Trục hoành biểu
diễn thu nhập còn trục tung biểu diễn tổng nợ cá nhân của người đi vay (tiền
thế chấp, tiền chi trả ô tô ). Dữ liệu được phân thành hai lớp: lớp

gồm
những người thiếu khả năng trả nợ ngân hàng và lớp o gồm những người có
tình trạng tốt. Như vậy để hạn chế rủi ro các loại nợ (3-5) dẫn đến khả năng
mất vốn ngân hàng chỉ cấp tín dụng cho những khách hàng có mức thu nhập từ
ngưỡng T trở lên.

Việc phát hiện ra những thông tin “có giá trị” là không dễ dàng, đối với nguồn dữ liệu
có kích thước lớn chúng ta không thể phân tích bằng tay mà cần đến những công cụ hỗ
trợ đặc biệt. Usama Fayyad đã chỉ ra những nhược điểm sau đây:
- Con người cần hàng tuần lễ hoặc lâu hơn để phát hiện ra những thông tin có
ích.
- Phần lớn dữ liệu chưa bao giờ được phân tích cả.
- 3 - - Có một hố sâu giữa khả năng sinh ra dữ liệu và khả năng sử dụng dữ liệu.
Chính vì những điều đó đã dẫn đến sự ra đời của khai phá dữ hiệu hay còn gọi là phát
hiện trị thức, nhằm giải quyết tình trạng “giàu dữ liệu nhưng nghèo tri thức”.
Khai phá dữ liệu là giải pháp phân tích tự động các kho dữ liệu, phát hiện ra các thông
tin hữu ích, có lợi cho quá trình ra quyết định. Cùng với thời gian, với sự tăng cường
năng lực tính toán, hoàn thiện các thuật toán thống kê, học máy và các phương pháp
thu thập, quản lý dữ liệu là tiền đề cho sự ra đời của khai phá dữ liệu.



1.1.3 Quy trình khám phá tri thức trong CSDL
Khám phá tri thức trong CSDL bao gồm nhiều bước là: Chuẩn bị dữ liệu, tìm kiếm
mẫu, ước lượng tri thức, tinh chế sự tương tác nội tại sau khi chuyển dạng dữ liệu.
Quá trình được thừa nhận là không tầm thường theo nghĩa là quá trình đó bao hàm một
mức độ tìm kiếm tự động. Khai phá dữ liệu chỉ là một bước thiết yếu trong quy trình
này.

Quy trình này gồm các bước:

1) Làm sạch dữ liệu: Loại bỏ nhiễu hoặc các dữ liệu không thích hợp.
2) Tích hợp dữ liệu: Tích hợp dữ liệu từ các nguồn khác nhau như: CSDL, kho dữ
liệu, file text…
3) Chọn dữ liệu: Ở bước này, những dữ liệu liên quan trực tiếp đến nhiệm vụ sẽ được
thu thập từ các nguồn dữ liệu ban đầu.
4) Chuyển đổi dữ liệu: Trong bước này, 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.
5) Khai phá dữ liệu: Là giai đoạn thiết yếu, trong đó các phương pháp thông minh sẽ
được áp dụng để trích xuất ra các mẫu dữ liệu.
6) Đánh giá mẫu: Đánh giá sự hữu ích của các mẫu biểu diễn tri thức dựa vào một số
phép đo. 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 bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì
- 5 - vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức cần
chiết xuất ra.
7) Trình diễn dữ liệu: Sử dụng các kỹ thuật trình diễn vàtrực quan hoá dữ liệu để biểu
diễn tri thức khai phá được cho người sử dụng.


, … t
n
} là tập gồm n giao dịch (transaction), mỗi giao dịch được định danh
bởi TID (transaction identification).

Định nghĩa 1:Luật là một quy tắc chung nhất trên một tập các đối tượng. Khái niệm
“chung nhất” được hiểu là một sự kiện xẩy ra thường xuyên hoặc có tính chất dị
thường (những giao dịch gian lận thẻ tín dụng thường có tính chất dị thường).
Định nghĩa 2: Một luật kết hợp là một quan hệ có dạng X

Y, trong đó X, Y

I là
các tập mục gọi là itemsets, và

YX 
. Ở đây, X được gọi là tiền đề, Y là mệnh đề
kết quả.
Hai thông số quan trọng của luật kết hợp là độ hỗ trợ (s)và độ tin cậy (c).
Định nghĩa 3: Độ hỗ trợ (support) của luật kết hợp X

Y là tỷ lệ phần trăm các bản
ghi
YX 
với tổng số các giao dịch có trong cơ sở dữ liệu.
Định nghĩa 4: Đối với một số giao dịch được đưa ra, độ tin cậy (confidence) là tỷ lệ
của số giao dịch có chứa
YX 
với số giao dịch có chứa X. Đơn vị tính %.Về mặt xác
- 6 -

Bánh mì, Đậu phụng
T3
Bánh mì, Sữa, Đậu phụng
T4
Bia, Bánh mì
T5
Bia, Sữa

I = { Bia, Bánh mì, Trái cây, Sữa, Đậu phụng}
S= {Bánh mì, Đậu phụng}; count(S) = 3 và |D| = 5 → sup(S) = 60% → S- tập phổ
biến
S2 = {Bánh mì} → sup(S2) = 80%→ S2 - tập phổ biến
- 7 - S3 = {Đậu phụng} → sup(S3) = 60% → S3 - tập phổ biến
S4 = {Sữa}→ sup(S4) = 2/5 = 40% → S4 –không là tập phổ biến
S5={Sữa, Bánh mì} → sup(S5) = 1/5 = 20% → S5 –không là tập phổ biến

Từ ví dụ này chúng ra rút ra các luật kết hợp với support và confidence như sau:
X→Y
Support
Confidence
Bánh mì → Đậu phụng
60%
75%
Đậu phụng → Bánh mì
60%
100%
Bia → Bánh mì

cof(A

(S - A)) = sup(S) / sup(A) >= mincof

Từ bài toán khai thác luật kết hợp chuyển thành bài toán khai thác tập phổ biến: Độ
phức tạp tính toán cao vì số lượng các tập ứng cử viên là rất lớn.

Tiến trình khai thác luật kết hợp
Xác định các tập phổ biến:Việc xác định các tập phổ biến gồm có hai bước chính sau
đây:
- 8 - • Xác định các tập ứng cử viên (C
k
).
• Xác định các tập phổ biến (L) dựa vào tập ứng cử viên
Để xác định tập ứng cử viên, ta thực hiện các bước sau đây:
• Tìm các tập ứng cử viên một mục.
• Quét CSDL D để xác định độ hỗ trợ của các tập ứng cử viên. Trong vòng đầu
tiên, các tập ứng cử viên cũng chính là tất cả các mục có trong CSDL. Tại vòng
thứ k (k>1), các tập ứng cử viên được xác định dựa vào các tập phổ biến đã xác
định tại vòng k – 1, sử dụng hàm Apriori-gen(). Sau khi đã xác định được các
tập ứng cử viên, thuật toán quét từng giao dịch trong CSDL để tính độ hỗ trợ
của các tập ứng cử viên. Quá trình xác định các tập mục sẽ kết thúc khi không
xác định được thêm tập phổ biến nào nữa.
Nội dung hàm Apriori-gen().
Hàm Apriori-gen() thực hiện hai bước
[1]:


k
, k>=2 do
Call Genrules(L
k
, L
k
);
Procedure Genrules(L
k
: large k-itemset, a
m
: large m-itemset)
Begin
A={(m-1)-itemset a
m-1
| a
m-1

a
m
}
Forall a
m-1

A do begin
Conf = Suport(L
k
)/Suport(a
m-1
)

Nội dung kỹ thuật:
Forall itesets c

C
k
do
Forall (k – 1)–subsets s of c do
If (s

L
k – 1
) then
Delete c from C
k
- 10 - Dựa vào đây, ta có thể tỉa được các tập ứng viên, từ đó có thể giới hạn miền tìm kiếm
của nó trên tất cả các tập mục.

1.3Phân lớp
Phân lớp là bài toán mà chúng ta thường gặp trong thực tế: Phân loại học sinh vào các
lớp A, B, C, ngân hàng thực hiện phân lớp khách hàng để cấp tín dụng hay từ chối,
phân loại giao dịch thẻ tín dụng là gian lận hay hợp pháp, phân loại tin tức thuộc các
lĩnh vực như tài chính, y học, giải trí, thể thao, thời tiết…Có thể nói phân lớp có trong
hầu hết các lĩnh vực của cuộc sống, nhưng tại sao phải phân lớp và phân lớp để làm
gì?. Việc phân lớp đối tượng sẽ giúp hiểu rõ hơn về các đối tượng có chung một đặc
điểm nào đó, đồng thời giúp chúng ta những ứng xử tốt hơn với các đối tượng đó.
Ngân hàng thực hiện phân loại tình trạng tín dụng của khác hàng thành các lớp AAA
(tốt nhất), AA (rất tốt), A (tốt), BBB (khá), BB (trung bình khá), B (trung bình), C

tập kiểm thử (test set). Tập huấn luyện được dùng để xây dựng các mô hình và tập
kiểm thử để kiểm tra tính hợp lệ và đúng đắn của các môt hình đó.

Quy trình phân lớp: Gồm 2 bƣớc
- 11 - Bƣớc 1: Xây dựng mô hình – Mô tả tập các lớp đƣợc xác định trƣớc
• Tập huấn luyện: Các mẫu/bộ dùng cho việc xây dựng mô hình
• Mỗi mẫu/bộ thuộc về một lớp đã được định nghĩa trước
• Tìm luật phân lớp, cây quyết định hoặc công thức toán để mô tả lớp

Bƣớc 2 - Sử dụng mô hình: Phân lớp các đối tƣợng chƣa biết
Xác định độ chính xác của mô hình dựa vào các tiêu chí sau:
• So sánh nhãn của mẫu kiểm tra với kết quả phân lớp từ mô hình
• Độ chính xác là tỷ lệ (%) của tập mẫu kiểm tra được phân loại đúng bởi mô
hình
• Sử dụng tập dữ liệu để kiểm tra độc lập với tập huấn luyện

1.3.1 Phân lớp bằng phƣơng pháp dựa trên cây quyết định
Cây quyết định là một sơ đồ luồng giống với cấu trúc cây, là một cấu trúc phân cấp của
các nút và các nhánh:
• Mỗi nút trong ứng với một phép kiểm tra trên một thuộc tính
• Mỗi nhánh biểu diễn kết quả phép kiểm tra
• Các nút lá biểu diễn các lớp hay các phân bố lớp
• Nút cao nhất trong cây là nút gốc.

Xây dựng cây quyết định gồm 2 bước:
Bƣớc 1: Thiết lập cây quyết định
• Bắt đầu từ gốc

fair
yes

>40
medium
no

fair
yes

>40
low
yes
fair
yes

>40
low
yes
excellent
no

31…40
low
yes
excellent
yes

<=30
medium

31…40
high
yes
fair
Yes

>40
medium
no

excellent
NoBảng 1: Thông tin thuộc tính mua máy tính cá nhân khách hàng
Hình 1.3.1: Xây dựng cây quyết định về việc mua máy tính cá nhân của khách
hàng, mỗi nút trong ứng với một phép kiểm tra trên một thuộc tính. Mỗi nút lá biểu
thị một lớp (buys_computer = yes hoặc buys_computer = no)
- 13 -
Thuật toán xây dựng cây quyết định
Chiến lƣợc cơ bản
1) Bắt đầu từ nút đơn biểu diễn tất cả các mẫu.
2) Nếu các mẫu thuộc về cùng một lớp, nút trở thành nút lá và được gán nhãn bằng
lớp đó.