LỜI CẢM ƠN
Lời đầu tiên xin được gửi lời cảm ơn chân thành nhất đến Tiến sĩ Võ Văn
Tài, Thầy đã tận tình hướng dẫn, dìu dắt em trong mỗi bước đi, giúp em hoàn thành
luận văn này.
Em xin gửi lời cảm ơn đến cô Phạm Bích Như, cố vấn học tập lớp Toán
Ứng Dụng K33, một người Cô, một người Chị luôn quan tâm giúp đỡ em và các
bạn trong những lúc khó khăn.
Em xin gửi lời cảm ơn sâu sắc đến quý Thầy Cô trong Khoa Khoa học Tự
nhiên, đặc biệt là quý Thầy Cô trong bộ môn Toán đã truyền đạt cho em những kiến
thức quý báu cũng như những kỹ năng trong cuộc sống.
Tôi xin gửi lời cảm ơn đến tập thể lớp Toán Ứng Dụng K33 thân yêu, những
người đã cùng tôi vượt qua bao khó khăn, chia sẻ bao vui buồn trong học tập cũng
như trong cuộc sống.
Xin gửi lời cảm ơn đến gia đình, đặc biệt là mẹ tôi, chỗ dựa tinh thần, nguồn
động lực giúp tôi cố gắng học tốt, ngày càng cố gắng hoàn thiện mình hơn.
i
DANH MỤC CÁC BẢNG
Trang
Bảng 2.1 Một số hàm hạt nhân thông dụng 18
Bảng 3.1 Các bước tính toán chùm kết quả học tập-phương pháp thứ bậc 34
Bảng 3.2 Các bước tính toán chùm kết quả học tập-phương pháp không
thứ bậc 35
Bảng 3.3 Kết quả chi tiết chùm kết quả học tập ở vòng lặp thứ 13 36
Bảng 3.4 Các bước tính toán chùm điểm rèn luyện-phương pháp
thứ bậc 37
Bảng 3.5 Các bước tính toán chùm điểm rèn luyện-phương pháp không
thứ bậc 39
Bảng 3.6 Kết quả chi tiết chùm điểm rèn luyện ở vòng lặp thứ 10 40
Bảng 3.7 Các bước tính toán chùm điểm học tập và rèn luyện-phương
pháp thứ bậc 42
Bảng 3.8 Các bước tính toán chùm điểm học tập và rèn luyện-phương

pháp không thứ bậc 43
Bảng 3.9 Kết quả chi tiết chùm điểm học tập và rèn luyện ở vòng
lặp thứ 12 44
ii
DANH MỤC CÁC HÌNH
Trang
Hình 1.1 Khoảng cách giữa hai phần tử x và y 5
Hình 1.2 Khoảng cách giữa các nhóm 8
Hình 2.1 Đồ thị hàm mật độ xác suất đã ước lượng 21
Hình 2.2 Đồ thị hàm mật độ xác suất trong không gian 3 chiều 25
Hình 3.1 Đồ thị 15 hàm mật độ xác suất của kết quả học tập
các lớp Khoa Khoa học Tự nhiên 33
Hình 3.2 Cây phân loại kết quả học tập học kỳ 1, năm học 2010-2011
các lớp Khoa Khoa học Tự nhiên 34
Hình 3.3 Đồ thị 15 hàm mật độ xác suất của điểm rèn luyện
các lớp Khoa Khoa học Tự nhiên 37
Hình 3.4 Cây phân loại điểm rèn luyện học kỳ 1, năm học 2010-2011
các lớp Khoa Khoa học Tự nhiên 38
Hình 3.5 Đồ thị phân tán điểm rèn luyện và học tập
các lớp Khoa Khoa Học Tự Nhiên 41
Hình 3.6 Đồ thị các hàm mật độ xác suất được ước lượng từ điểm học tập
và rèn luyện các lớp Khoa Khoa học Tự nhiên 41
Hình 3.7 Cây phân loại điểm rèn luyện và học tập
các lớp Khoa Khoa Học Tự Nhiên 42
iii
MỤC LỤC
iv
PHẦN MỞ ĐẦU
1. GIỚI THIỆU
Khi có nhiều dữ liệu, người ta có nhu cầu phân chia dữ liệu thành những nhóm

với những phần tử “gần” nhau theo một dấu hiệu nào đó, từ đó bài toán phân tích
chùm ra đời. Phân tích chùm là việc nhóm các phần tử trong tập hợp đã cho thành
các chùm sao cho các phần tử trong cùng chùm tương tự nhau theo những dấu hiệu
nào đó. Khi chùm được xây dựng, những phần tử trong cùng một chùm sẽ có sự
tương tự nhiều hơn so với những phần tử của chùm khác. Có rất nhiều ứng dụng
trong những lĩnh vực khác nhau của bài toán phân tích chùm: y học, kinh tế, kỹ
thuật, xã hội, … và trong bất kỳ lĩnh vực nào, nơi mà việc nhóm những phần tử lại
với nhau được đòi hỏi. Nhiều tác giả đã phát triển một số phương pháp liên quan
đến phân tích chùm với những thuật toán cụ thể, nhưng chỉ cho những dữ liệu rời
rạc. Các thuật toán này dựa trên định nghĩa khoảng cách hay sự tương tự của hai
phần tử cũng như của hai chùm gồm các phần tử rời rạc.
Có nhiều định nghĩa khoảng cách giữa hai phần tử rời rạc cũng như khoảng
cách giữa hai nhóm dữ liệu. Khoảng cách giữa hai phần tử trong bài toán phân tích
chùm thông thường là khoảng cách Euclide, khoảng cách city–block, khoảng cách
Chebyshev, khoảng cách Minkowski,…, trong khi khoảng cách giữa hai chùm được
định nghĩa là khoảng cách min, khoảng cách max và khoảng cách trung bình của
những phần tử trong hai chùm. Hiện tại có hai phương pháp chủ yếu để xây dựng
chùm cho các phần tử rời rạc: Phương pháp thứ bậc và phương pháp không thứ bậc.
Một hạn chế chung của hai phương pháp này đánh giá sự tương tự của các chùm
không dựa vào sự phân bố của dữ liệu của chùm nên đôi khi nó tạo ra nghịch lý cho
kết quả phân tích chùm: Phần tử đúng phải xếp vào chùm này nhưng lại xếp vào
chùm kia.
Chùm của các hàm mật độ xác suất, nơi mỗi hàm mật độ xác suất mô tả một
tổng thể là một chủ đề chưa được nghiên cứu nhiều. Năm 2010 nhóm tác giả Võ
Văn Tài, Phạm Gia Thụ đã đưa ra khái niệm độ rộng chùm làm tiêu chuẩn xây dựng
chùm các hàm mật độ xác suất. Độ rộng chùm được định nghĩa qua tích phân hàm
cực đại của các hàm mật độ xác suất, vì vậy khi đánh giá sự tương tự của các phần
tử, yếu tố phương sai đã được xem xét. Điều này thể hiện sự hợp lý hơn trong phân
tích chùm. Tuy nhiên trong việc giải quyết bài toán chùm các hàm mật độ xác suất,
vấn đề ước lượng hàm mật độ xác suất từ số liệu rời rạc, tính độ rộng chùm vẫn còn

gặp nhiều khó khăn. Trong luận văn này, tôi tổng kết những kết quả lý thuyết liên
quan đến độ rộng chùm và tiếp tục giải quyết vấn đề khó khăn trong tính toán qua
các chương trình được viết trên phần mềm Matlab. Một ví dụ với số liệu thực về
điểm rèn luyện và học tập của sinh viên Khoa Khoa học Tự nhiên, Trường Đại học
Cần Thơ được đưa ra để kiểm chứng các thuật toán, các chương trình đã viết và
cũng để minh họa cho tính ứng dụng của bài toán phân tich chùm. Kết quả của ứng
dụng cụ thể này cũng nhằm xem xét mức độ tương đồng về điểm số của sinh viên
trong Khoa để có những nhận xét về tình hình học tập và rèn luyện của sinh viên
cũng như mức độ đánh giá các ngành học của Thầy Cô trong Khoa.
2. BỐ CỤC CỦA LUẬN VĂN
Luân văn này gồm phần mở đầu, phần nội dung, phần kết luận và danh mục
các tài liệu tham khảo.
Phần nội dung gồm 3 chương:
Chương 1: Sự tương tự giữa các phần tử
Tổng kết lại một cách có hệ thống các kết quả đã có liên quan đến sự tương
tự của các phần tử, đặc biệt là độ rộng chùm, thang đo chính được sử dụng trong
phân tích chùm các hàm mật độ xác suất.
Chương 2: Xây dựng chùm các hàm mật độ xác suất
Xây dựng các chương trình ước lượng hàm mật độ xác suất từ các phần tử
rời rạc, ước lượng giá trị tích phân hàm cực đại. Từ đó, luận văn trình bày hai
phương pháp xây dựng chùm các hàm mật độ xác suất: phương pháp thứ bậc và
phương pháp không thứ bậc.
Chương 3: Chùm các lớp về điểm rèn luyện và kết quả học tập của sinh viên
Khoa Khoa học Tự nhiên học kỳ 1 năm học 2010-2011
2
Sử dụng các thuật toán cùng các chương trình đã viết trong các chương 1 và
chương 2, áp dụng vào dữ liệu thực tế “Điểm rèn luyện và kết quả học tập của sinh
viên Khoa Khoa học Tự nhiên học kỳ 1, năm học 2010-2011”.
3
Chương 1

SỰ TƯƠNG TỰ CỦA CÁC PHẦN TỬ
Khi thực hiện bài toán phân tích chùm, vấn đề quan trọng là xác định mức độ
gần và xa của các phần tử. Có nhiều tiêu chuẩn với nhiều tên gọi được đưa ra để
đánh giá mức độ này, trong luận văn này ta gọi chung là sự tương tự của các phần
tử. Khi các phần tử rời rạc, tiêu chuẩn để đánh giá sự tương tự thông thường là
khoảng cách. Khi các phần tử là hàm mật độ xác suất, có nhiều khái niệm được đưa
ra như: độ đo tách rời, affinity, độ rộng chùm.
1.1 SỰ TƯƠNG TỰ CỦA CÁC PHẦN TỬ RỜI RẠC
1.1.1 Khoảng cách của hai phần tử
Định nghĩa 1.1: Khoảng cách giũa hai phần tử d(x,y) là một metric, nghĩa là nó
thỏa mãn 3 điều kiện sau với mọi x, y, z.
i) d(x,y)
≥
0
, .x y∀
Dấu bằng xảy ra khi
yx =
,
ii) d(x,y) = d(y,x),
iii) d(x,y) + d(y,z)
≥
d(x,z).
Theo 3 điều kiện trên, ta có thể định nghĩa khoảng cách giữa 2 phần tử x và y
(x,y
∈
R
n
) theo nhiều cách khác nhau. Thông thường các loại khoảng cách sau được
sử dụng phổ biến:
Khoảng cách Euclide:

1
2
2
1
( , ) ( )
n
e i i
i
d x y x y
=
 
= −
 
 
∑
(1.1)
Khoảng cách city- block:
( )
1
,
n
cb i i
i
d x y x y
=
= −
∑
(1.2)
Khoảng cách Chebyshev:
( )

, max
ch i i
i
d x y x y= −
(1.3)
-2 -1 0 1 2 3 4 5 6
-2
-1
0
1
2
3
4
5
6
x(1;2)
y(2;4)
Khoang cach Euclide
mo ta do dai doan thang nay
Khoang cach city-block
mo ta do dai 2 doan gap khuc
Khoang cach
Chebyshev mo
ta do dai duongt
gap khuc lon nha
Khoảng cách Minkowski với bậc m:
( )
1
1
,

n
m
m
m i i
i
d x y x y
=
 
= −
 
 
∑
(1.4)
Nhận xét:
i) Khoảng cách Euclide là khoảng cách thường được sử dụng nhất trong
trong toán học, nó mô tả độ dài của đoạn thẳng nối hai điểm x và y.
ii) Khoảng cách city-block mô tả tổng độ dài (tổng các khoảng cách
Euclide) của n đoạn gấp khúc nối hai điểm x, y thuộc không gian n chiều. Mỗi đoạn
trong n đoạn này sẽ song song với 1 trục tương ứng trong n trục chúng ta chọn làm
hệ quy chiếu.
iii) Khoảng cách Chebyshev mô tả đoạn thẳng có độ dài lớn nhất trong n
đoạn gấp khúc đã được đề cập trong khoảng cách city- block.
iv) Với những m khác nhau, khoảng cách Minkowski bậc m sẽ tương ứng với
một loại khoảng cách khác nhau. Với m =1,
( ) ( )
, ,
m cb
d x y d x y=
, với m = 2,
( ) ( )

, ,
m e
d x y d x y=
, độ lớn của khoảng cách càng giảm khi m càng tăng, khi m
→ ∞
,
( ) ( )
, ,
m ch
d x y d x y=
.
Hình vẽ sau minh họa 3 khoảng cách phổ biến của hai điểm x(1;2) và y(2;4).
Hình 1.1 Các loại khoảng cách giữa hai phần tử x và y
5
Như đã thấy, khoảng cách Euclide mô tả đoạn thẳng nối 2 điểm x và y trong
khi khoảng cách city-block mô tả 2 đoạn gấp khúc nối x và y, chúng lần lượt song
song với trục hoành và trục tung của hệ tọa độ. Tương tự như vậy, nếu x, y thuộc
không gian R
3
thì khoảng cách city-block sẽ mô tả 3 đoạn thẳng lần lượt song song
với Ox, Oy, Oz. Hình trên cũng chỉ ra khoảng cách Chebyshev mô tả đoạn thẳng dài
nhất trong hai đường gấp khúc.
1.1.2 Khoảng cách giữa hai nhóm phần tử
Cho A, B là hai nhóm, mỗi nhóm gồm nhiều phần tử rời rạc khác nhau. Gọi
D(A;B) là khoảng cách giữa hai nhóm A và B, d(x,y) là khoảng cách giữa phần tử x
và phần tử y (
;x A y B∈ ∈
). Thông thường ta sử dụng các định nghĩa sau cho
D(A;B):
Khoảng cách min

( ) ( )
min
; min ,
x A
y B
D A B d x y
∈
∈
=
(1.5)
Khoảng cách max:
( ) ( )
max
; max ,
x A
y B
D A B d x y
∈
∈
=
(1.6)
Khoảng cách trung bình
( ) ( )
1
; ,
avg
x A
A B
y B
D A B d x y

n n
∈
∈
=
∑
(1.7)
Với
,
A B
n n
lần lượt là số phần tử của nhóm A và nhóm B.
Nhận xét:
i) Việc tính khoảng cách giữa hai nhóm dữ liệu không chỉ phụ thuộc vào việc
chọn loại khoảng cách giũa hai nhóm mà còn phụ thuộc vào loại khoảng cách giữa
hai phần tử, do đó sẽ có nhiều kết quả khác nhau tùy vào loại khoảng cách được
chọn. Cho đến nay, người ta chưa chứng minh được sử dụng khoảng cách nào là tối
ưu. Trong thực tế các loại khoảng cách phổ biến đã được nêu ở trên thường được sử
dụng nhiều nhất.
ii) Khi hai nhóm A và B được nhập lại thành một nhóm (A+B) thì việc tính
khoảng cách từ nhóm (A+B) đến một nhóm C bất kỳ cũng có thể thực hiện theo
những công thức trên. Tuy nhiên, ta có thể áp dụng những công thức sau đây để cho
việc tính toán được thuận tiện hơn:
6
( ) ( ) ( )
( ) ( )
( )
1 2 3 4
1 2 3
1 2
5

4;2 , 2;2 , 3; , 3;3
2
1
3; 1 , 2; , 1; 1
2
3
1;2 , 1;
2
A a a a a
B b b b
C c c
 
 
= = − = − = − = −
 
 ÷
 
 
 
 
= = − − = − − = − −
 
 ÷
 
 
 
 
= = =
 
 ÷

 
 
( ) ( ) ( )
, , ,
A B
avg ave ave
A B A B
n n
D A B C D A C D B C
n n n n
+ = +
+ +
( ) ( ) ( )
{ }
( ) ( )
min min min
, min , , , min min , ,min ,
x A y B
z C z C
D A B C D A C D B C d x z d y z
∈ ∈
∈ ∈
 
 
+ = =
 
 
 
(1.8)
( ) ( ) ( )

{ }
( ) ( )
max max max
, max , , , max max , , max ,
x A y B
z C z C
D A B C D A C D B C d x z d y z
∈ ∈
∈ ∈
 
 
+ = =
 
 
 
(1.9)
(1.10)
Ngoài các khoảng cách thông dụng trên, Ward (1963) đã đưa ra công thức
tính khoảng cách trường hợp này bằng biểu thức:
( ) ( ) ( ) ( )
, , , ,
A C B C C
Ward
A B C A B C A B C
n n n n n
D A B C D A C D B C D A B
n n n n n n n n n
+ +
+ = + −
+ + + + + +

(1.11)
Trong đó,
A
n
,
B
n
,và
C
n
lần lượt là số phần tử của nhóm A, B và C.
Ví dụ 1.1: Cho
Tính a)
min max
, ,
avg
D D D
giữa A và B.
b)
min max
, ,
avg
D D D
giữa A+C và B
Giải
Trước tiên ta chọn khoảng cách Euclide làm khoảng cách giữa hai phần tử.
Ta tiến hành tính khoảng cách giữa các nhóm như sau:
a)
( ) ( ) ( ) ( )
{ }

min 1 1 1 2 4 3
, min , , , ,
e e e
D A B d a b d a b d a b=
=
( )
2 2
5
,
2
e
d a b =
= 2.5
Tương tự
( ) ( ) ( ) ( )
{ }
max 1 1 1 2 4 3
, max , , , ,
e e e
D A B d a b d a b d a b=
=
( )
4 3
, 2 5 4.4721
e
d a b = ≈
( ) ( )
1
, , 3.5197
avg

x A
A B
y B
D A B d x y
n n
∈
∈
= ≈
∑
b)
( ) ( ) ( )
{ }
min min min
, min , , ,d A C B D A B D C B+ =
7
-6 -5 -4 -3 -2 -1 0 1 2 3
-3
-2
-1
0
1
2
3
4
5
O
X
Y
Nhom A
Nhom B

Nhom
C
-6 -5 -4 -3 -2 -1 0 1 2 3
-3
-2
-1
0
1
2
3
4
5
O
X
Y
Nhom A
Nhom B
Nhom
C
Nhom A+C
Dmax(A+C,B)
Dmax(A,B)
Dmin(A,B)
Dmin(A+C,B)
=
5 41 5
min ,
2 2 2
 
 

=
 
 
 
( )
2 2
,d a b=
( ) ( ) ( )
{ }
max max max
, max , , ,d A C B D A B D C B+ =
=
{ }
( )
1 1
max 2 5,5 5 ,d c b= =
( ) ( ) ( )
, , ,
C
A
avg avg avg
A C A C
n
n
D A C B D A B D C B
n n n n
+ = +
+ +
=
4 2

3.5197 4.0058 3.6817
6 6
+ ≈
Ta có thể mô tả hình học ví dụ trên như sau:
Hình 1.2 Khoảng cách giữa các nhóm
8
( )
,
avg
D A B
bằng trung bình các khoảng cách được thể hiện bởi các đoạn
thẳng liền nét.
( )
,
avg
D A C B+
bằng trung bình các khoảng cách được thể hiện bởi các đoạn
thẳng liền nét và không liền nét.
1.2 SỰ TƯƠNG TỰ CỦA HAI HÀM MẬT ĐỘ XÁC SUẤT
1.2.1 Khoảng cách
Xét hai tổng thể
1
w
và
2
w
với hàm mật độ xác suất n chiều lần lượt là
)(
1
xf

và
)(
2
xf
, theo Webb (2002),
),(
21
ffD
được gọi là khoảng cách của hai hàm mật độ
xác suất
)(
1
xf
và
)(
2
xf
nếu thỏa mãn ba điều kiện sau:
0),(
21
≥ffD
,
0),(
21
=ffD
nếu hai hàm mật độ xác suất bằng nhau.
),(
21
ffD
đạt giá trị lớn nhất khi

1
w
và
2
w
rời nhau.
Nhiều định nghĩa khoảng cách đã được đưa ra thỏa ba điều kiện trên, có thể kể
ra một số định nghĩa phổ biến sau:
Khoảng cách Chernoff
( ) ( )






−=
∫
−
xxx dffffD
n
R
sss
C
1
2121
ln),(
,
)1,0(∈s
(1.12)

Khoảng cách Bhattacharyya

( ) ( )
[ ]






−=
∫
xxx dffffD
n
R
B
2
1
2121
ln),(
(1.13)
Khoảng cách Divergence

( ) ( )( )
( )
( )
x
x
x
xx d

f
f
ffffD
n
R
D








−=
∫
2
1
2121
ln),(
(1.14)
Khoảng cách
P
L

( ) ( )
1
1 2 1 2
,
n

p
p
p
R
f f f f d
 
= −
 ÷
 ÷
 
∫
x x x
(1.15)
Khoảng cách
1
L
1 2
1 2
1
( ) ( ),
n
R
f x f x dxf f −=
∫
(1.16)
9
Khoảng cách L
2
là khoảng cách được sử dụng phổ biến nhất. Khoảng cách L
1

là một trường hợp đặc biệt của khoảng cách city-block và nó cũng được xem là
khoảng cách tự nhiên nhất.
Trong trường hợp đặc biệt
)(
1
xf
và
)(
2
xf
là hai hàm mật độ xác suất có
phân phối chuẩn n chiều

( )
( ) ( )






−−−=
−
ii
T
i
n
i
i
x

π
f
µµ
1
2
2
1
2
1
exp
2
1
)( Σ
Σ
xx
, i = 1, 2 (1.17)
Ta có

( )( ) ( )








+−−−=
−
−

ss
s
s
T
s
C
ssffD
ΣΣ
Σ
Σ
1
12
1
1221
ln
2
1
1
2
1
),( µµµµ
(1.18)
Trong đó
21
)1( ΣΣΣ ss
s
+−=
, s ∈ (0,1).
( )
( )

( )
{ }
ITrffD
T
D
2
2
1
),(
1
1
22
1
112
1
2
1
11221
−++−−−=
−−−−
ΣΣΣΣΣΣ
µµµµ
(1.19)
Khi s = 0.5 thì
),(
21
ffD
C
trở thành
),(

21
ffD
B
. Cụ thể:

( ) ( ) ( )
( )










+
+−+−=
−
2
1
21
21
12
1
211221
2
ln
2

1
4
1
),(
ΣΣ
ΣΣ
ΣΣ
µµµµ
T
B
ffD
(1.20)
Khi hai ma trận phương sai bằng nhau
ΣΣΣ ==
21
thì D
D
= 8D
B
và trở
thành bình phương khoảng cách Mahalanobis:

)()(),(8),(),(
12
1
12212121
µµµµ
−−===
−
Σ

T
BDM
ffDffDffD
(1.21)
1.2.2 Một số khái niệm khác
Ngoài khái niệm khoảng cách, một số khái niệm khác cũng được đưa ra để
đánh mức độ gần gũi của hai hàm mật độ xác suất.
a) Affinity
i) Hellinger

( )
.)()(),(
2
1
2121
∫
=
n
R
H
dffffD xxx
(1.22)
Matusita cũng đã đề nghị affinity của k hàm mật độ xác suất mà xét khi
2
=
k
nó trở thành affinity của Hellinger.
10
ii) Toussaint


dxffffD
n
R
α
T
21
2121
),(
αα
∫
=
(1.23)
Trong đó
),(
21
α,α=
α
1),1,0(,
2121
=+∈
αααα
.
Trong trường hợp đặc biệt
2
1
21
==
αα
thì affinity của Toussaint trở thành
affinity của Matusita cũng như của Hellinger.

b) Độ rộng chùm
Năm 2008 nhóm tác giả trong [4] trong phân tích chùm các hàm mật độ xác
suất đã đưa ra khái niệm độ rộng chùm của hai hàm mật độ xác suất chính bằng
phân nửa khoảng cách L
1
giữa chúng:
(1.24)
1.3 SỰ TƯƠNG TỰ CỦA
NHIỀU HƠN HAI HÀM MẬT ĐỘ XÁC SUẤT
1.3.1 Một số khái niệm
a) Độ đo phân biệt
Năm 1973, Glick lần đầu tiên đã đưa ra khái niệm độ đo phân biệt. Nó được
xem là nền tảng để xây dựng chùm các hàm mật độ xác suất:
Định nghĩa 1.2: Một hàm đối xứng s sẽ được gọi là độ đo k
)2( ≥k
điểm tách rời
cho tập S trong không gian véc tơ với chuẩn
.
nếu với mọi phần tử
Saaa
k
∈ ,,,
21
nếu hàm s thỏa mãn điều kiện sau:

( )
∑∑
<
<
−≤≤−

ji
jikji
ji
aaaaasaa , ,,max
21
(1.25)
b) Afinity
Định nghĩa 1.3: Cho k hàm mật độ xác suất
k
fff , ,,
21
, (
2
≥
k
) ta có các định nghĩa
affinity như sau:
i) Matusita (1967):

( ) ( )
∫
=
n
R
k
kkM
dffffffD x
/1
2121
, ,,

(1.26)
ii) Toussaint (1972):
( )
1 2 1 2 max
1
( , ) ( ) ( ) 1
2
n n
R R
w f f f x f x dx f x dx
= − = −
∫ ∫
11
∫
∏
=
=
n
j
R
k
j
j
α
kT
dxffffD
1
21
)]([), ,,( x
α

(1.27)
Trong đó
),(
k21
α, ,α,α=
α
∑
=
=∈
k
j
jj
1
1),1,0(
αα
.
Trong trường hợp đặc biệt
k
k
1
21
====
ααα

thì affinity của Toussaint trở
thành affinity của Matusita và khi
2=k
thì nó trở thành của Hellinger.
c) Độ rộng chùm
Định nghĩa 1.4: Cho k hàm mật độ xác suất trên R

n
:
{ }
k
fff , ,,
21
,
3≥k
chúng ta
định nghĩa độ rộng của chùm
{ }
k
fff , ,,
21
như sau:

( )
∫
−==
n
R
kk
dfffffffw 1)(, ,,, ,,
max
1
2121
xx
(1.28)
Như vậy chúng ta đã có định nghĩa giống nhau về độ rộng của chùm các hàm
mật độ xác suất

{ }
k
fff , ,,
21
với mọi
2k ≥
. Lúc này độ rộng của một chùm là hợp
của một tập con chứa một phần tử với một tập con chứa nhiều hơn một phần tử
hoặc hợp hai tập con chứa nhiều hơn một phần tử được định nghĩa giống nhau.
Định nghĩa 1.5: Cho
), ,,(),, ,,(,
2121 mn
fffgggg
là các hàm mật độ xác suất,
chúng ta định nghĩa độ rộng của chùm
( ){ }
m
fffg , ,,,
21
là
{ }
[ ]
m
fffgw , ,,
21
∪
và độ
rộng của chùm
( ) ( ){ }
nm

gggfff , ,,,, ,,
2121
là
{ } { }
[ ]
nm
gggfffw , ,, ,
2121
∪
.
1.3.2. Một số kết quả về độ rộng chùm
Sau đây ta xét mối quan hệ giữa độ rộng của hai chùm chỉ khác nhau một
phần tử, độ rộng của hai chùm và phần hợp của chúng.
Định lý 1.1:Cho k hàm mật độ xác suất
)(x
i
f
, i = 1, 2, …, k,
3≥k
. Khi đó ta có
mối quan hệ giữa độ rộng chùm và afinity của Toussaint như sau:

( )
1), ,,(1
1
, ,,
1
)(
2121
−









−
−
≥
∏
=
k
j
kTk
fffD
k
k
fffw
α
(1.29)
Trong đó
)(
21
), ,,(
α
kT
fffD
được xác định bởi (1.27).

Chứng minh
12
Với mỗi
kj ,,2,1=
, ta có
( )
i
i
i
k
j
j
ff
α
α
≥








∑
=1
,
ki , ,2,1=
Do đó
( ) ( )

∏
∑
∏
∑
=
=
=
+++
=
≥⇔≥








k
j
j
k
j
j
k
j
j
k
j
j

jj
k
ffff
1
1
1

1
21
αα
ααα

Mặt khác
{ }
( )
{ }
( )
k
k
kj
kj
j
kj
ffff
α
α
α
α
≤







≤






≤≤≤≤ 1
1
1
min, ,min
1
1

Do vậy
{ } ( )
∏
=
++
≤≤
≤







k
j
jj
kj
j
k
ff
1
1
1
min
α
αα

hay
{ } ( )
∏
=
≤≤
≤
k
j
jj
kj
j
ff
1
1

min
α

Như vậy
( ) { }
∑∑
∏
=
≤≤
=
=
−≤−≤
k
j
j
kj
j
k
j
k
j
jj
ffff
j
1
1
1
1
min0
α


Vì
{ }
∑
=
≤≤
−
k
j
j
kj
j
ff
1
1
min
có k – 1 số hạng
j
f
nên
{ } { }
j
kj
k
j
j
kj
j
fkff
≤≤

=
≤≤
−≤−
∑
1
1
1
max)1(min

Do đó
( ) { }
j
kj
k
j
k
j
jj
fkff
j
≤≤
=
=
−≤−≤
∑
∏
1
1
1
max)1(0

α

Lấy tích phân trên
n
R
hai vế bất đẳng thức trên được kết quả:

xx
∏
∫
=
−≤−
k
j
R
kT
n
dfkfffD
1
max21
)()1(), ,,(1
α
Thế
( )
1, ,,)(
21max
+=
∫
n
R

k
fffwf x
vào bất đẳng thức trên ta có kết quả (1.29). ■
Định lý 1.2: Cho
121
,, ,,
+kk
ffff
là hàm mật độ xác suất của
1+k
tổng thể.
Chúng ta có các kết quả:
a)
( ) ( )
=−
+ kk
fffwfffw , ,,, ,,
21121

{ }
∫
+
−
n
R
k
dfh xxx )(),(min1
11
(1.30)
Trong đó

{ }
)(), ,(),(max)(
211
xxxx
k
fffh =
,
3≥k
.
b)
( ) ( ) ( )
Afffwfffwfffw
knnnk
−++=
++
1, ,,, ,,, ,,
212121
(1.31)
Trong đó
knkn
<≥
,3,
và
∫
=
n
R
dkkA xxx )}(),(min{
21
với


)}(), ,(),(max{)(
211
xxxx
n
fffk =


)}(), ,(),(max{)(
212
xxxx
knn
fffk
++
=
.
Chứng minh
a) Đặt
∫
−=
n
R
k
k
dh
k
Pe xx)(
1
1
1

)/1(
, ,2,1
và
∫
+
−=
+
+
n
R
k
k
dh
k
Pe xx)(
1
1
1
2
)1/1(
1, ,2,1
,
13
Trong đó

)}(), ,(),(max{)(
211
xxxx
k
fffh =


)}(), ,(),(max{)(
1212
xxxx
+
=
k
fffh
Bởi vì
{ }
)(),(min)()()(
11112
xxxxx
++
−+=
kk
fhfhh

nên
)1/1(
1, ,2,1
+
+
k
k
Pe

[ ]
∫
++

−+
+
−=
n
R
k
f)hfh
k
)}(,({min)()(
1
1
1
1k111
xxxx
dx

Bdf
k
dh
kk
k
k
nn
R
k
R
+
+
−









−
+
+
+
=
∫∫
+
xxxx )(
1
1
)(
1
1
11
1
11


BPe
k
k
k
k

+
+
=
)/1(
, ,2,1
1

(1.32)
Với
{ }
∫
+
+
=
n
R
k
dfh
k
B x.xx )( ),(min
1
1
11
Mặt khác
( )
)1/1(
1, ,2,1121
)1(, ,,
+
++

+−=
k
kk
Pekkfffw
(1.33)
Kết hợp (1.32) và (1.33) ta có

( )






+
+
+−=
+
B Pe
k
k
kkfffw
k
k,1,2, ,k
)/1(
121
1
)1(, ,,



BkkPek
k
k1,2, ,
)1(
)/1(
+−−=

Thế
( )
[ ]
k
k
k
fffk
k
Pe , ,,1
1
21
)/1(
, ,2,1
−−=
vào kết quả trên ta có (1.30).
■
b) Ta có
( )
)/1(
, ,2,121
1, ,,
n
nn

nPenfffw −−=
( )
)/1(
, ,2,121
1, ,,
m
mknn
mPemfffw −−=
++
với
nkm −=
Vì vậy

( ) ( )
knnn
fffwfffw , ,,, ,,
2121 ++
+

[ ]
)/1(
, ,2,1
)/1(
, ,2,1
2
m
m
n
n
mPenPek +−−=

(1.34)
Mặt khác

)/1(
, ,2,1
k
k
Pe
=
{ }
∫
−
n
R
dkk
k
xxx )(),(max
1
1
21

=
{ }
∫
−+−
n
R
dkkkk
k
xxxxx ])(),(min)()([

1
1
2121
14
=






+−+−
∫ ∫ ∫
n n n
R R R
dkkdkndkm
k
xxxxxxx )}(),(min{)()(
1
2121
=
[ ]
AnPemPe
k
n
n
m
m
++
)/1(

, 2,1
)/1(
, ,2,1
1
Hay

(1/ ) (1/ )
1,2, , 1,2,
m n
m n
mPe nPe
 
+ =
 
( )
AfffwkAkPe
k
k
k
−−−=− , ,,1
21
)/1(
, ,2,1,
(1.25)
Thế kết quả (1.35) vào (1.34) ta có (1.31).
Chúng ta vẫn gọi w
*
(k) là độ rộng của chùm gồm k hàm mật độ xác suất
{ }
k

fff , ,,
21
, nhưng xem w
*
(k) là hàm của số những hàm mật độ xác suất (hàm số
với biến số k). Hàm số này có tính đơn điệu và có giá trị được xác định bởi
hệ quả sau:
Hệ quả 1.1: Đặt w
*
(k) =
1
21
, ,,
k
fff
, khi đó với
2
≥
k
thì w
*
(k) là hàm không
giảm và
1 )(*0 −≤≤ kkw
. Dấu bằng ở vế trái xảy ra khi tất cả các
)(x
i
f
trùng nhau
và ở vế phải khi các

)(x
i
f
rời nhau.
Chứng minh
Khi k = 2 dễ dàng ta có hệ quả.
Khi
,3≥k
đặt
{ }
,)(), ,(),(max)(
211
xxxx
k
fffh =
theo (1.30) ta có
w
*
(k+1) – w
*
(k)
{ }
∫
+
−=
n
R
k
dfh xxx )(),(min1
11


0)(1
1
=−≥
∫
+
n
R
k
df xx

nghĩa là w
*
(k) là hàm không giảm với biến số k.
Mặt khác

{ }
∑
=
≤≤
k
i
iki
fffff
1
21
)()(), ,(),(max)( xxxxx

∫
=

n
R
i
df 1)( xx
Thế hai kết quả trên vào đẳng thức
1
21
, ,,
k
fff
=
{ }
1)(), ,(),(xma
21
−
∫
xxxx dfff
k
R
n
ta có cận trên của w
*
(k).
15
Khi
)(x
i
f
giống nhau, theo (1.25) hiển nhiên ta có cận dưới của w
*

(k).
Nhận xét:
Từ (1.31) ta có mối quan hệ giữa độ rộng của 2 chùm và hội của chúng là
( ) ( ) ( )
Affwfffwfffffw
kiikii
−++=
++
1, ,, ,,, ,,, ,,
121121
.
Chúng ta có thể hiểu mối quan hệ này như sau:
( ) ( )
kii
ffwfffw , ,, ,,
121 +
+
là tổng độ rộng của hai chùm trước khi ghép.
1 – A là khoảng cách ngoài hay khoảng cách giữa hai chùm.
Độ rộng chùm phản ánh sự gần nhau của những phần tử trong chùm, trong
khi khoảng cách ngoài phản ánh sự xa nhau giữa hai chùm. Bởi vì
( )
1 2 1
, , , , ,
i i k
w f f f f f
+
là hằng số, nên độ rộng chùm và khoảng cách ngoài biến
thiên theo hướng trái ngược nhau. Khi ghép hai chùm thành một chùm, chúng ta cố
gắng cực tiểu tổng độ rộng và vì vậy cũng có nghĩa là cực đại khoảng cách giữa hai

chùm. Tuy nhiên vấn đề trở nên rất phức tạp khi có nhiều chùm được ghép vào
trong một chùm. Nó có nghĩa khoảng cách giữa các chùm cũng ít rõ ràng, nhưng
tổng độ rộng chùm tăng dần lên với mỗi bước của phân tích chùm hướng đến độ
rộng của chùm cuối cùng.
Chúng ta vừa trình bày một số vấn đề liên quan đến sự tương tự của hai hay
nhiều hàm mật độ xác suất cũng như đưa ra các công thức tính khoảng cách, tính độ
rộng chùm của các hàm mật độ xác suất. Tuy nhiên, để sử dụng được các công thức
trên, chúng ta cần giải quyết các vần đề sau:
i) Ước lượng được các hàm mật độ xác suất của các tổng thể. Vì phần lớn
dữ liệu thu được trên thực tế thường là rời rạc nên chúng ta phải có phương pháp tốt
ước lượng hàm mật độ xác suất của chúng, có như thế thì việc phân tích mới có ý
nghĩa.
ii) Phải tính được các hàm cực đại
( )
max
f x
khi tính khoảng cách của nhiều
hơn hai hàm mật độ xác suất.
iii) Phải có phương pháp tính gần đúng tích phân nhiều chiều của những
hàm mật độ xác suất khá phức tạp.
Các phần được trình bày trong chương 2 sẽ giải quyết các vấn đề trên.
16
17
Chương 2
XÂY DỰNG CHÙM CÁC HÀM MẬT ĐỘ XÁC SUẤT
2.1 GIỚI THIỆU
Khi có nhiều dữ liệu, người ta có nhu cầu phân chia dữ liệu thành những
nhóm với những phần tử “gần” nhau theo một dấu hiệu nào đó, từ đó bài toán phân
tích chùm ra đời. Phân tích chùm là một dạng tổng quát hơn của bài toán phân loại
và phân biệt. Nó cũng được gọi là việc học không được giám sát, vì ở đây ta không

có dự kiến trước việc phân chia các phần tử vào tổng thể nào. Phân tích chùm là
việc nhóm các phần tử trong tập hợp đã cho thành các chùm sao cho các phần tử
trong cùng chùm tương tự nhau theo những dấu hiệu nào đó. Khi chùm được xây
dựng, những phần tử trong cùng một chùm sẽ có sự tương tự nhiều hơn so với
những phần tử của chùm khác.Có rất nhiều ứng dụng trong những lĩnh vực khác
nhau của bài toán phân tích chùm: y học, kinh tế, kỹ thuật, xã hội, … và trong bất
kỳ lĩnh vực nào, nơi mà việc nhóm những phần tử lại với nhau được đòi hỏi.
Xây dựng chùm cho các phần tử rời rạc đã được rất nhiều nhà toán học quan
tâm về mặt lý thuyết cũng như tính ứng dụng của nó. Tiêu chuẩn dùng để đánh giá
mức độ gần xa của các phần tử cũng như các chùm trong trường hợp này là khoảng
cách. Tuy nhiên, khi phân tích nhiều tổng thể, trong đó mỗi tổng thể có rất nhiều
phần tử, các phương pháp phân tích chùm rời rạc chỉ tính đến khoảng cách giữa
trung bình các tổng thể chứ không xét đến dạng phân bố của tổng thể và điều này
đôi khi sẽ dẫn đến kết quả phân tích không được hợp lý: Phần tử đúng phải xếp vào
chùm này nhưng lại xếp vào chùm kia. Đây là một hạn chế của việc phân tích chùm
chỉ dựa vào khoảng cách đơn thuần. Trong chương này luận văn sẽ trình bày một
phương pháp phân tích chùm khác, phức tạp hơn nhưng khắc phục được những hạn
chế của việc phân tích chùm rời rạc. Đó là phương pháp phân tích chùm các hàm
mật độ xác suất.
2.2 ƯỚC LƯỢNG HÀM MẬT ĐỘ XÁC SUẤT
2.2.1 Ước lượng hàm mật độ xác suất
Phần lớn các dữ liệu thu được trong thực tế đều là rời rạc. Do đó, trước khi
tiến hành phân tích chùm các hàm mật độ xác suất từ dữ liệu rời rạc ta phải ước
lượng các hàm mật độ xác suất của các tổng thể chứa dữ liệu. Chính việc ước lượng
này làm tăng tính ứng dụng thực tế của bài toán phân tích chùm các hàm mật độ xác
suất. Có nhiều cách ước lượng hàm mật độ xác suất bằng phương pháp tham số và
phi tham số. Trong luận văn này, chúng ta sẽ tiến hành ước lượng bằng phương
pháp hàm hạt nhân, một phương pháp phi tham số được đánh giá là có nhiều ưu
điểm hiện nay.
Gọi

{ }
1 2
, , ,
N
x x x
là các dữ liệu rời rạc n chiều cần ước hàm mật độ xác
suất. Hàm mật độ xác suất cần ước lượng theo phương pháp hạt nhân có dạng

( )
1
1
1 2
1 1
ˆ

n
N
ij
j
i
j
N j
x x
f x K
N h h h h
=
=
 
−
=

 ÷
 ÷
 
∑
∏
(2.1)
Trong đó
j
h
là tham số trơn cho biến thứ j,
j
K
là hàm hạt nhân của biến thứ j, thỏa hai điều kiện:
( )
( )
0
1
K x
K x dx

≥


=


∫
Thông thường, ta chọn K là một trong các hàm được cho bởi bảng sau:
Bảng 2.1 Một số hàm hạt nhân thông dụng
Hàm hạt nhân Biểu thức

Tam giác
( )
1 1
0 1
x khi x
f x
khi x
 − <

=

≥


Chữ nhật
( )
1
1
2
0 1
khi x
f x
khi x

<

=


≥


18
Chuẩn
( )
2
1
exp
2
2
x
f x
π
 
= −
 ÷
 
Epanechnikov
( )
( )
2
3
1 1
4
0 1
x khi x
f x
khi x

− ≤


=


>

Song lượng
( )
( )
2
2
15
1 1
16
0 1
x khi x
f x
khi x

− ≤

=


>

Chú ý :
i) Khi tham số trơn h nhỏ thì hàm số ước lượng sẽ kém trơn, khi h càng lớn
thì tính trơn sẽ tăng lên nhưng sẽ kém chính xác trong ước lượng. Các nhà toán học
khẳng định việc chọn tham số trơn quan trọng hơn việc chọn hàm hạt nhân. Trong
luận văn này chúng ta chọn tham số trơn theo Scott (1992):


( )
1
4
4
2
n
j j
h
N n
σ
+
 
=
 ÷
 ÷
+
 
,
j
σ
là độ lệch chuẩn mẫu của biến thứ j.
Khi
1n =
,
( )
1
5
1.06h N
σ

−
≈
,
( )
1
1
ˆ
N
i
i
x x
f x K
Nh h
=
−
 
=
 ÷
 
∑
(2.2)
Khi
2n
=
,
( )
1
6
h N
σ

−
=
,
( )
1 2
1 2
1
1 2
1
ˆ
N
i i
i
x x x x
f x K K
Nh h h h
=
 
− −
   
=
 ÷  ÷
 
   
 
∑
(2.3)
ii) Trong luận văn này hàm hạt nhân được chọn có dạng chuẩn.
2.2.2 Chương trình ước lượng hàm mật độ xác suất
Việc tính toán tường minh các công thức trên thực sự rất phức tạp. Vì vậy

trong thực tế, người ta chỉ có thể sử dụng các phần mềm toán học để viết các
chương trình ước lượng các hàm mật độ. Phần sau đây xin trình bày hai chương
trình ước lượng hàm mật độ xác suất một chiều và hai chiều được tôi viết trên phần
mềm Matlab. Việc ước lượng các hàm nhiều chiều hơn được viết một cách tương tự
như ước lượng hàm hai chiều.
a) Chương trình 2.1: Ước lượng hàm mật độ xác suất một chiều
Trước hết, ta tạo hàm uocluong dùng để ước lượng hàm mật độ xác suất
một chiều như sau:
function fa=uocluong(dla);
syms x;
19
fa=sym('x');
sa=sym('x');
ha=1.06*std(dla)*(length(dla)^-0.2);
sa=0;
for i=1:length(dla)
sa=sa+1/(2*pi)^.5*exp(-(((x-dla(1,i))/ha)^2/2));
end;
sa;
fa=(1/ha/length(dla)*sa);
Lưu file vừa tạo với tên “uocluong.m” trong thư mục “work” của Matlab.
Khi cần ước lượng hàm mật độ xác suất của một tổng thể nào đó ta chỉ cần
nhập như sau:
syms x
uocluong([dữ liệu cần ước lượng])
Ví dụ 2.1 Giả sử ta có số liệu về chiều cao (cm) của 30 nhân viên nam công ty X
được cho như sau :
173 174 161 159 167 170 169 171 169 173
168 169 169 171 160 170 167 158 164 178
158 161 159 168 164 180 174 170 172 163.

Ta viết thực hiện ước lượng hàm mật độ xác suất của chiều cao các nhân
viên công ty X bằng Matlab 7.0.4 như sau:
syms x
f=uocluong([173 174 161 159 167 170 169 171 169 173 168 169 169,…
171 160 170 167 158 164 178 158 161 159 168 164 180 174 170 172,
163])
Ta có kết quả:
f = 21956415689413010567052911461721/2596148429267413814265248164610048*exp(-
1/2*(140737488355328/442584986134111*x-24347585485471744/442584986134111)^2)
+21956415689413010567052911461721/2596148429267413814265248164610048*exp(-
1/2*(140737488355328/442584986134111*x-24488322973827072/442584986134111)^2)
+21956415689413010567052911461721/2596148429267413814265248164610048*exp(-
1/2*(140737488355328/442584986134111*x-22658735625207808/442584986134111)^2)
+21956415689413010567052911461721/2596148429267413814265248164610048*exp(-
1/2*(140737488355328/442584986134111*x-22377260648497152/442584986134111)^2)
+21956415689413010567052911461721/2596148429267413814265248164610048*exp(-
1/2*(140737488355328/442584986134111*x-23503160555339776/442584986134111)^2)
+65869247068239031701158734385163/5192296858534827628530496329220096*exp(-
1/2*(140737488355328/442584986134111*x-23925373020405760/442584986134111)^2)
+21956415689413010567052911461721/1298074214633706907132624082305024*exp(-
1/2*(140737488355328/442584986134111*x-23784635532050432/442584986134111)^2)
+21956415689413010567052911461721/2596148429267413814265248164610048*exp(-
1/2*(140737488355328/442584986134111*x-24066110508761088/442584986134111)^2)
+21956415689413010567052911461721/2596148429267413814265248164610048*exp(-
1/2*(140737488355328/442584986134111*x-23643898043695104/442584986134111)^2)
+21956415689413010567052911461721/5192296858534827628530496329220096*exp(-
20