ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Doãn Hiền
ỨNG DỤNG MỘT SỐ THUẬT TOÁN PHÂN CỤM
PHÂN TÍCH DỮ LIỆU NGÂN HÀNG
LUẬN VĂN THẠC SỸ
Hà Nội – 2006
Hà Nội – 2006 2
Lêi c¶m ¬n
Sau một thời gian nghiên cứu và nỗ lực thực hiện, luận văn “Ứng dụng một số
thuật toán phân cụm phân tích dữ liệu Ngân hàng” đã cơ bản hoàn thành.
Ngoài sự cố gắng của bản thân, tôi đã nhận đƣợc sự giúp đỡ từ nhà trƣờng,
thầy cô giáo, gia đình và bạn bè.
Trƣớc hết, tôi xin đƣợc cảm ơn mẹ, ngƣời đã động viên và chăm sóc tôi trong
quá trình học tập và hoàn thành luận văn.
Tôi xin cảm ơn các thầy cô giáo trƣờng Đại học Công nghệ - Đại học Quốc
gia Hà Nội đã truyền đạt những kiến thức quí báu cho tôi cũng nhƣ các học
viên lớp Cao học Công nghệ K10T3.
Đặc biệt, tôi xin cảm ơn sâu sắc tới thầy giáo Bùi Công Cƣờng, ngƣời đã trực
tiếp tận tình giúp đỡ, hƣớng dẫn tôi trong quá trình thực hiện luận văn này.
Nhân đây, tôi cũng gửi lời cảm ơn tới các bạn bè cùng lớp K10T3 đã cùng sát
cánh và động viên tôi trong những ngày cùng nhau học tập tại trƣờng Đại học
Công nghệ - Đại học Quốc Gia Hà Nội.
3
MỤC LỤC
MỞ ĐẦU 6
CHƢƠNG 1. TỔNG QUAN 7
3.3.2 Các bƣớc thực hiện thuật toán K-means 47
3.3.3 Ví dụ về áp dụng thuật toán K-means 49
3.3.4 Một số vấn đề và ƣu, nhƣợc điểm của K-means 52
3.3.5 Độ phức tạp của thuật toán K-means 53
3.4 THUẬT TOÁN PHÂN CỤM MỜ K-MEANS (FKM) 53
3.4.1 Khái niệm về tập mờ và phân cụm mờ 53 4
3.4.2 Thuật toán phân cụm mờ K-means 55
3.4.3 Mô tả thuật toán 57
3.4.4 Độ phức tạp thuật toán 58
3.5 THUẬT TOÁN PHÂN CỤM HIERACHICAL 59
3.5.1 Nguyên lý thực hiện 59
3.5.2 Mô tả thuật toán 60
3.5.3 Ví dụ về thuật toán phân cấp 61
3.5.4 Ƣu, nhƣợc điểm của thuật toán 65
3.6 THUẬT TOÁN PHÂN CỤM K-LÁNG GIỀNG GẦN 66
3.6.1 Thuật toán K-láng giềng gần 66
3.6.2. Cách thức thực hiện thuật toán KNN 66
3.6.3. Một ví dụ áp dụng thuật toán KNN 69
3.6.4. Ƣu, nhƣợc điểm của thuật toán KNN 71
CHƢƠNG 4. XÂY DỰNG CHƢƠNG TRÌNH PHÂN CỤM 72
4.1 PHÂN TÍCH CÁC MODULE 72
4.1.1 Module chuẩn bị dữ liệu 72
4.1.2 Tinh chỉnh dữ liệu 72
4.1.3 Hàm tính khoảng cách 73
4.2 CHƢƠNG TRÌNH MÔ PHỎNG CÁC THUẬT TOÁN 75
4.2.1 Giới thiệu chƣơng trình 75
4.2.2 Chuyển đổi và tinh chỉnh dữ liệu 75
7. Định dạng cây phân cấp 105
6
MỞ ĐẦU
Đối với các Ngân hàng hiện nay, nắm đƣợc khách hàng là một trong những
điểm mấu chốt tạo nên thành công trong kinh doanh. Để đạt đƣợc điều này,
việc cần thiết đó là thiết lập đƣợc chiến lƣợc khách hàng đúng đắn để sao cho
giành đƣợc các khách hàng mới và giữ đƣợc các khách hàng có chất lƣợng
cao. Để đạt đƣợc những mục tiêu đó, các Ngân hàng đã xây dựng các hệ
thống dữ liệu về khách hàng, từ đó có thể phân tích và xây dựng các chiến
lƣợc kinh doanh cho mình.
Thực tế cho thấy rằng, thay vì nhắm vào tất cả các khách hàng để đối xử,
khuyến khích, Ngân hàng có thể lựa chọn các khách hàng đáp ứng một tiêu
chuẩn nào đó về lợi nhuận dựa trên các thuộc tính giao dịch hay những thuộc
tính khác của khách hàng [7].
Trong những năm gần đây, hệ thống máy giao dịch tự động (ATM –
Automatic Teller Machine) đƣợc các Ngân hàng tại Việt Nam triển khai và
phát triển khá mạnh mẽ. Hệ thống này cho phép khách hàng thực hiện giao
dịch một cách tiện lợi về thời gian (online 24/7) cũng nhƣ cung cấp các dịch
vụ (vấn tin, chuyển khoản, rút tiền, thanh toán hoá đơn, cách dịch vụ tín dụng
). Vì vậy, có thể nói hệ thống ATM trở thành một trong những kênh quan
trọng trong các kênh giao dịch của Ngân hàng cung cấp cho khách hàng.
Tuy nhiên, để phát huy hiệu quả của hệ thống này, ngoài các thông tin cố định
nhƣ lƣợng thẻ, lƣợng giao dịch, số máy ATM… Ngân hàng cần biết đƣợc các
thuộc tính ẩn của khách hàng để đề ra chiến lƣợc phát triển đúng đắn cho loại
hình dịch vụ này. Đó chính là lý do cần đến khoa học khai phá dữ liệu mà ở
đây cụ thể hơn, chúng ta sẽ nghiên cứu về các thuật toán phân cụm dữ liệu để
8
1.2. TÓM TẮT NỘI DUNG CÁC CHƢƠNG
Luận văn có 4 chƣơng và phần mở đầu, kết luận:
Phần mở đầu
Phần này nêu lên sự cần thiết của vấn đề phân cụm dữ liệu nói chung và nhất
là việc áp dụng vào phân tích dữ liệu trong Ngân hàng để từ đó định hƣớng
cho việc mở rộng các dịch vụ với các dối tƣợng khách hàng hợp lý.
Chƣơng một: Tổng quan
Chƣơng này nêu lên mục tiêu, nội dung và phƣơng pháp nghiên cứu để hoàn
thành bản luận văn này.
Chƣơng hai: Phân cụm dữ liệu
Chƣơng này nêu lên khái niệm cơ bản về phân cụm dữ liệu, các bƣớc cơ bản
để thực hiện một thuật toán phân cụm, các loại đặc trƣng của phân cụm và các
định nghĩa liên quan đến phân cụm.
Chƣơng hai có đề cập đến một số ứng dụng của việc phân cụm và một nội
dung quan trọng nhất của các thuật toán phân cụm là các độ đo.
Chƣơng ba: Một số thuật toán phân cụm dữ liệu
Chƣơng ba giới thiệu chi tiết về một số thuật toán phân cụm hiện đang đƣợc
áp dụng phổ biến, đó là các thuật toán phân cụm tuần tự (Sequence), thuật
toán phân cụm phân cấp (Hierachical), thuật toán K-trung bình (K-Means), K-
trung bình mờ (Fuzzy K-Means) và thuật toán K láng giềng gần (K-Nearest
Neighbour).
Chƣơng bốn: Xây dựng chƣơng trình phân cụm 9
Chƣơng bốn giới thiệu chƣơng trình thực hiện một số thuật toán nêu tại
Chƣơng ba bao gồm phần phân tích các module thực hiện và phần chƣơng
trình thực hiện.
Chƣơng năm: Ứng dụng phân cụm dữ liệu giao dịch ATM
vì nó phải đi giải quyết vấn đề tìm một cấu trúc trong tập hợp các dữ liệu chƣa
biết trƣớc các thông tin về lớp hay các thông tin về tập ví dụ huấn luyện. 11
Trong nhiều trƣờng hợp, khi phân lớp đƣợc xem là vấn đề học có giám sát thì
phân cụm dữ liệu là một bƣớc trong phân lớp dữ liệu, trong đó phân cụm dữ
liệu sẽ khởi tạo các lớp cho phân lớp bằng các xác định các nhãn cho các
nhóm dữ liệu.
Một vấn đề thƣờng gặp trong phân cụm dữ liệu là hầu hết các dữ liệu cần cho
phân cụm đều có chứa nhiễu do quá trình thu thập thiếu chính xác hoặc thiếu
đầy đủ, vì vậy cần phải xây dựng chiến lƣợc cho bƣớc tiền xử lý dữ liệu nhặm
khắc phục và loại bỏ nhiễu trƣớc khi bƣớc vào giai đoạn phân tích phân cụm
dữ liệu. “Nhiễu” ở đây có thể là các đối tƣợng dữ liệu không chính xác, hoặc
là các đối tƣợng khuyết thiếu thông tin về một số thuộc tính. Một trong các kỹ
thuật xử lý nhiễu phổ biến là việc thay thế giá trị của các thuộc tính của đối
tƣợng nhiễu bằng giá trị thuộc tính tƣơng ứng của đối tƣợng dữ liệu gần nhất.
2.2 CÁC BƢỚC CƠ BẢN ĐỂ PHÂN CỤM
- Chọn lựa đặc trƣng: các đặc trƣng phải đƣợc chọn lựa một cách hợp lý để
có thể mã hoá nhiều nhất thông tin liên quan đến công việc quan tâm. Mục
tiêu chính là phải giảm thiểu sự dƣ thừa thông tin giữa các đặc trƣng. Các đặc
trƣng cần đƣợc tiền xử lý trƣớc khi dùng chúng trong các bƣớc sau.
- Chọn độ đo gần gũi: đây là một độ đo chỉ ra mức độ tƣơng tự hay không
tƣơng tự giữa hai vectơ đặc trƣng. Phải đảm bảo rằng tất cả các vectơ đặc
trƣng góp phần nhƣ nhau trong việc tính toán độ đo gần gũi và không có đặc
trƣng nào át hẳn đặc trƣng nào, điều này đƣợc đảm bảo bởi quá trình tiền xử
lý.
- Tiêu chuẩn phân cụm: điều này phụ thuộc vào sự giải thích của chuyên gia
cho thuật ngữ “dễ nhận thấy” dựa vào loại của các cụm đƣợc chuyên gia cho
rằng đang ẩn giấu dƣới tập dữ liệu. Chẳng hạn, một cụm loại chặt của véctơ
trong tập dữ liệu thoả mãn các giả thiết đã cho hay không.
- Dự đoán dựa trên các cụm: Trƣớc hết ta phải phân cụm một tập dữ liệu
thành các cụm mang đặc điểm của các dạng mà nó chứa. Sau đó, khi có một 13
dạng mới chƣa biết xác định xem nó có khả năng thuộc về cụm nào nhất và
dự đoán đƣợc một số đặc điểm của dạng này nhờ các đặc trƣng chung của cả
cụm.
Trong thực tế, phân cụm đƣợc áp dụng vào nhiều lĩnh vực khác nhau nhƣ:
- Tìm kiếm dữ liệu trên mạng: kết quả đƣợc phân thành các cụm tuỳ theo độ
tƣơng tự với dữ liệu cần tìm.
- Marketing: trợ giúp cán bộ thị trƣờng phát hiện đƣợc những phân đoạn thị
trƣờng để có chiến lƣợc, sản phẩm hợp lý đối với các phân đoạn đó.
- Phân loại khách hàng sử dụng các sản phẩm của Ngân hàng và các ngành
tài chính, bảo hiểm
- Lập bản đồ thành phố theo nhóm các loại nhà ở, giá trị tài sản hay vị trí địa
lý.
2.4 CÁC LOẠI ĐẶC TRƢNG
Có 4 loại đặc trƣng đó là:
- Các đặc trƣng danh nghĩa (nominal): gồm các đặc trƣng mà các giá trị của
nó mã hoá các trạng thá1. Chẳng hạn cho một đặc trƣng là giới tính của một
ngƣời thì các giá trị có thể của nó là 1 ứng với nam và 0 ứng với nữ. Rõ ràng
là bất kỳ sự so sánh về lƣợng nào giữ các giá trị loại này đều vô nghĩa.
- Các đặc trƣng thứ tự (ordinal): là các đặc trƣng mà các giá trị của nó có thể
đƣợc sắp một cách có ý nghĩa.
Ví dụ về một đặc trƣng thể hiện sự hoàn thành khoá học của một sinh viên.
Giả sử các giá trị có thể là 4, 3, 2, 1 tƣơng ứng với với việc xếp loại kết quả
học tập của sinh viên là: “xuất sắc”, “giỏi”, “khá”, trung bình khá”, “trung
bình”. Các giá trị này đƣợc sắp xếp theo một thứ tự có ý nghĩa nhƣng sự so
, ,C
m
sao cho thoả mãn 3 điều kiện:
i) C
i
, i=1, ,m
ii)
m
i
i
XC
1
iii) C
i
C
j
=; i j; i,j =1, ,m
Thêm vào đó, các véctơ trong một cụm là tƣơng tự nhau hơn so với các véctơ
thuộc một cụm khác. Lƣợng hoá thuật ngữ tƣơng tự và không tƣơng tự phụ
thuộc rất nhiều vào loại của cụm. Chẳng hạn, loại cụm chặt thì có một số độ
đo phù hợp, trong khi loại cụm có hình dáng dài và mỏng lại phù hợp hơn với
các loại độ đo khác (xem hình vẽ). 15
m
j
ij
xU
i = 1,2, , N
0 <
m
j
ij
xU
1
)(
< N-1 j = 1,2, m (2.3)
Mỗi cụm trong trƣờng hợp này có thể không đƣợc định nghĩa chính xác.
Nghĩa là mỗi véctơ x thuộc về nhiều hơn một cụm, với mỗi cụm nó lại thuộc
về với độ thuộc u
j
:
- Khi u
j
gần 1: mức độ thuộc của x vào cụm thứ j cao.
- Khi u
j
gần 0: mức độ thuộc của x vào cụm thứ j thấp.
Nếu một hàm thuộc có giá trị gần 1 với hai véctơ thì hai véctơ này đƣợc coi là
tƣơng tự nhau.
nhất.
Dễ dàng nhận thấy khoảng cách Euclid là một độ đo không tƣơng tự metric.
2.6.2 Độ đo tƣơng tự
Một độ đo tƣơng tự s trên X là một hàm: s : X x X R
trong đó R là tập số thực sao cho:
s
0
R: - < s(x,y) s
o
< +, x,yX (2.9)
s(x,x) = s
0
, xX (2.10) 17
Và:
s(x,y) = s(y,x), x,yX (2.11)
Ngoài ra:
s(x,y) = s
0
khi và chỉ khi: x = y (2.12)
và
s(x,y)s(y,z) [s(x,y) +s(y,z)]s(x,z), x,y,zX (2.13)
thì d đƣợc gọi là một SM metric
2.6.3 Độ đo gần gũi giữa các tập con của X
Cho U là một lớp các tập con của X,
Nghĩa là các D
i
X, i=1, ,k và U= {D
,x
4
},{x
3
,x
4
,x
5
},{x
1
,x
2
,x
3
,x
4
,x
5
}}
Và hàm không tƣơng tự sau đây:
ji
DyDx
ji
ss
yxdDDd
,
2min
),(min),(
i
,
D
j
có phần tử chung, chẳng hạn: {x
1
,x
2
} và {x
1
,x
4
} thì:
0,,,
4121min
xxxxd
ss
Trong khi chúng là 2 tập khác nhau.
Một cách trực giác thì các định nghĩa trên cho thấy các DM là ngƣợc với các
SM.
Chẳng hạn, nếu d là một DM (metric) với d(x,y)>0,
x,y
X thì s = a/d với
a>0 là một SM (metric): s = d
max
+ k – d cũng là một SM (metric), với d
(2.14)
w
i
0,
i = 1, ,l; p > 0
w
i
là hệ số trọng số thứ i, chúng đƣợc sử dụng chủ yếu với các vectơ giá trị
thực.
Nếu w
i
= 1,
i = 1, ,l ta có các DM metric không trọng số.
Nếu p = 2 ta có khoảng cách Euclid.
Các DM metric có trọng số l
2
đƣợc tổng quát hoá nhƣ sau: 19
),()(),( yxByxyxd
t
max),(
(2.17)
Chuẩn l
1
và l
có thể đƣợc xem nhƣ ƣớc lƣợng trên và ƣớc lƣợng dƣới của
chuẩn l
2
, thật vậy:
d
(x,y)
d
2
(x,y)
d
1
(x,y)
Khi l = 1 thì tất cả l
p
trùng nhau.
Dựa vào các DM trên ta có thể định nghĩa các SM tƣơng ứng là:
s
p
(x,y) = b
max
(2.18)
trong đó: b
j
và a
j
là các giá trị lớn nhất và nhỏ nhất của đặc trƣng thứ j
Dễ dàng thấy đây là một DM metric và nó không chỉ dựa trên x và y mà còn
dựa vào toàn bộ tập X. Vì thế nếu d
G
(x,y) là khoảng cách giữa hai vectơ x, y
và d‟
G
(x,y) là khoảng cách giữa hai vectơ trên nhƣng là khi chúng thuộc X*
thì nói chung:
d
G
(x,y) d‟
G
(x,y)
Một độ đo không tƣơng tự nữa là: 20
ii
t
inner
yxyxyxs
1
),(
Trong phần lớn trƣờng hợp, tích nội đƣợc dùng khi các véctơ đƣợc chuẩn
hoá sao cho chúng có cùng độ dài a. Vì vậy, cận trên và cận dƣới của tích
nội là +a
2
và -a
2
, và nó chỉ phụ thuộc vào góc giữa x và y. Một độ đo
không tƣơng tự tƣơng ứng với tích nội là:
D
inner
(x,y) = b
max
- s
inner
(x,y)
+ Độ đo Tanimoto:
Đƣợc dùng cho cả các véctơ có giá trị thực cũng nhƣ rời rạc:
yxyx
yx
yxs
t
t
t
2
21
1
),(
(2.21) 21
Trong trƣờng hợp này, độ đo Tanimoto tỷ lệ nghich với a
2
/x
t
y. Vì thế nếu
coi tích nội giữa hai véctơ biểu thị mức độ liên quan giữa chúng thì nếu hai
véctơ càng liên quan đến nhau, độ đo Tanimoto giữa chúng càng lớn.
+ Một độ đo khác cũng hay đƣợc dùng đƣợc định nghĩa là:
yx
yxd
yxs
c
),(
1),(
2
Dễ thấy, độ đo này đạt max = 1 khi x = y
và đạt min = 0 khi x = -y
Hình 2.3: (a) Lƣới 2 chiều với k = 4. (b) Lƣới siêu lập phƣơng H
2
(Hình vuông)
Xét x, y
F
-1
và đặt: A(x,y) = [a
ij
] , i,j = 0,1, ,k-1 (2.22)
Là ma trận k x k. Các phần tử a
ij
là số vị trí mà véctơ đầu tiên có ký hiệu là i
và phần tử tƣơng ứng của véctơ thứ hai có ký hiệu là j trong đó: i, j
F. Ma
trận này đƣợc gọi là bảng ngẫu nhiên. Hầu hết các độ đo gần gũi giữa hai 22
véctơ có giá trị rời rạc có thể biểu diễn qua sự kết hợp các phần tử của ma trận
A(x,y).
Các độ đo không tương tự:
+ Khoảng cách Hamming: là số vị trí hai véctơ khác nhau.
Sử dụng ma trận A, ta có thể định nghĩa khoảng cách Hamming nhƣ sau:
(2.23)Nghĩa là ta chỉ ra việc tính tổng các vị trí không phải đƣờng chéo của A.
Khi k = 2, véctơ x
l
i
iiH
yxlyxd
1
5,0),(
(2.25)
Độ đo tƣơng tự tƣơng ứng là:
),(),(
max
yxddyxs
HH
Khoảng cách l
1
đƣợc định nghĩa trong trƣờng hợp các véctơ có giá trị liên tục:
l
i
ii
23
và y trừ những cặp mà cả hai toạ độ đều bằng 0. Điều này rất dễ hiểu nếu ta
coi giá trị toạ độ thứ i của x nhƣ là độ sở hữu của x đối với đặc trƣng thứ i, vì
vậy cặp (0,0) là kém quan trọng hơn tất cả các cặp còn lạ1.
Ta định nghĩa:
1
0
1
1
k
j
ij
k
i
x
an
và:
1
1
1
1
1
1
),(
k
j
ij
k
i
yx
k
i
ii
T
ann
a
yxs
(2.27)
Các hàm tƣơng tự khác giữa x và y đƣợc định nghĩa thông qua ma trận A.
Một số hàm thì quan tâm đến số vị trí mà hai véctơ giống nhau nhƣng khác 0.
Trong khi các hàm khác tính tất cả các vị trí của hai véctơ giống nhau.
Hàm tƣơng tự trong trƣờng hợp đầu là:
l
a
k
i
1
0
24
2.6.4.3. Các véctơ với giá trị hỗn hợp
Trong thực tế, ta cũng hay gặp các trƣờng hợp khi không phải tất cả các đặc
trƣng của véctơ đặc trƣng đều có cùng giá trị thực hoặc rời rạc. Có 3 cách
khắc phục:
- Cách 1: Dùng các độ đo gần gũi cho véctơ thực vì các véctơ rời rạc có thể
đƣợc so sánh một cách chính xác theo nghĩa các độ đo gần gũi cho véctơ
thực, trong khi điều ngƣợc lại nói chung không cho kết quả hợp lý. Độ đo
đƣợc đề xuất tốt cho trƣờng hợp này là khoảng cách l
1
.
- Cách 2: Cách này chuyển các đặc trƣng giá trị thực thành rời rạc. Nếu một
đặc trƣng x
i
lấy giá trị trong khoảng [a,b] ta chia đoạn này thành k đoạn
con. Nếu giá trị x
i
nằm trong đoạn con thứ r thì x
i
= r-1. Kết quả là ta có
véc tơ rời rạc và có thể dùng bất kỳ độ đo rời rạc nào đã nói ở trên.
- Cách 3: Cho x, y là hai véctơ l-chiều có giá trị hỗn hợp. Khi đó hàm tƣơng
tự giữa hai véctơ đƣợc định nghĩa là:
q
= 0
- Nếu đặc trƣng thứ q của x, y là giá trị nhị phân và cả hai dều bằng 0
thì w
q
= 0
- Các trƣờng hợp còn lại: w
q
= 1
- Nếu tất cả các w
q
= 0 thì s(x,y) là không xác định
+ s
q
(x,y):
Copyright: Tài liệu đại học ©