TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
********

NGUYỄN ĐĂNG ĐỨC

PHÂN TÍCH LỚP VÀ ỨNG DỤNG

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Toán ứng dụng

HÀ NỘI – 2019


TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
********

NGUYỄN ĐĂNG ĐỨC

PHÂN TÍCH LỚP VÀ ỨNG DỤNG

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Toán ứng dụng

Người hướng dẫn khoa học

PGS.TS. TRẦN TRỌNG NGUYÊN

HÀ NỘI – 2019

LỜI CẢM ƠN

Để hoàn thành khóa luận này, em xin được bày tỏ lòng biết ơn sâu sắc
đến thầy PGS.TS. Trần Trọng Nguyên – Người trực tiếp tận tình hướng
dẫn, chỉ bảo và định hướng cho em trong suốt quá trình em nghiên cứu khóa
luận của mình. Đồng thời em cũng xin chân thành cảm ơn Ban chủ nhiệm
khoa Toán, các thầy cô trong tổ Toán ứng dụng và các thầy cô trong khoa
Toán – Trường Đại học Sư phạm Hà Nội 2 đã tạo điều kiện cho em hoàn
thành tốt khóa luận này để có kết quả như ngày hôm nay.
Mặc dù đã có rất nhiều cố gắng, song thời gian nghiên cứu và kinh
nghiệm bản thân còn nhiều hạn chế nên khóa luận không thể tránh khỏi những
thiếu sót rất mong nhận được sự đóng góp ý kiến của các thầy cô, các bạn
sinh viên và bạn đọc.
Em xin chân thành cảm ơn!

Hà Nội, 20 tháng 5 năm 2019
Sinh viên thực hiện

Nguyễn Đăng Đức


LỜI CAM ĐOAN

Em xin cam đoan khóa luận này là kết quả của việc nghiên cứu và nỗ
lực học tập của bản thân dưới sự hướng dẫn của thầy PGS.TS. Trần Trọng
Nguyên, nội dung khóa luận không trùng lặp với kết quả của đề tài khác.
Trong khi nghiên cứu, hoàn thành bản khóa luận này em đã tham khảo một số
tài liệu đã ghi trong phần tài liệu tham khảo.
Em xin chịu hoàn toàn trách nhiệm về lời cam đoan này!


Hà Nội, 20 tháng 5 năm 2019
Sinh viên thực hiện

Nguyễn Đăng Đức


MỤC LỤC
LỜI MỞ ĐẦU .................................................................................................. 1
1. Lí do chọn đề tài.......................................................................................... 1
2. Mục đích nghiên cứu................................................................................... 2
3. Đối tượng và phạm vi nghiên cứu............................................................... 2
4. Phương pháp và công cụ nghiên cứu ........................................................... 2
5. Cấu trúc khóa luận ...................................................................................... 2
Chương 1: ĐỘ ĐO KHOẢNG CÁCH............................................................. 3
1.1. Khoảng cách .............................................................................................. 3
1.1.1. Độ đo khác biệt ...................................................................................... 3
1.1.2. Độ đo tương tự (với các biến tần số) ..................................................... 4
1.1.3. Độ đo tương tự (cho các biến nhị phân) ................................................ 5
1.1.4. Độ đo hỗn hợp ........................................................................................ 6
1.2. Khoảng cách giữa các nhóm ..................................................................... 9
1.2.1. Liên kết trung bình ................................................................................. 9
1.2.2. Liên kết đơn ........................................................................................... 9
1.2.3. Liên kết đầy đủ ...................................................................................... 10
1.3. Một số vấn đề tổ hợp trong phân lớp ....................................................... 10
1.3.1. Số cách phân chia tập n cá thể thành các lớp k các thể ......................... 10
1.3.2. Tổng số cách chia n cá thể .................................................................... 11
1.3.3. Lựa chọn số lớp tối ưu .......................................................................... 11
Chương 2: PHƯƠNG PHÁP PHÂN LỚP ......................................................13
2.1. Phân lớp không thứ bậc ............................................................................13

2.1.1. Các phương pháp kiểu đám mây động trong không gian Ơ cơ lit ........13


2.1.1.1. Quán tính giữa các lớp và trong từng lớp ..........................................14
2.1.1.2. Thuật toán K-means cluster ...............................................................15
2.1.1.3. Lựa chọn k tâm nhóm.........................................................................16
2.1.1.4. Khắc phục suy biến ............................................................................17
2.1.2. Phân lớp với các biến nhị phân .............................................................19
2.1.2.1. Phương pháp tuần tự ..........................................................................20
2.1.2.2. Phương pháp Ward .............................................................................20
2.2. Phân lớp thứ bậc .......................................................................................23
2.2.1. Tiêu chuẩn quán tính và phương pháp Ward ........................................25
2.1.1.1. Mức giảm quán tính khi ghép lớp và khoảng cách giữa hai lớp ........25
2.1.1.2. Chọn số lớp ........................................................................................26
2.3. Phương pháp phân lớp hai bước ..............................................................28
2.3.1. Phương pháp two-step cluster ...............................................................28
2.3.2. Thí dụ và phân tích kết quả ...................................................................29
2.3.2.1. Dữ liệu – mô hình và thủ tục..............................................................29
2.3.2.2. Kết quả chính .....................................................................................32
Chương 3: BÀI TOÁN PHÂN LỚP TRÊN SPSS ..........................................36
3.1. Thủ tục K – Means Cluster .....................................................................36
3.2. Phân lớp có thứ bậc các các thể ..............................................................39
KẾT LUẬN ....................................................................................................45
TÀI LIỆU THAM KHẢO ..............................................................................46


LỜI MỞ ĐẦU
1. Lí do chọn đề tài
Phân lớp (hay phân nhóm) là một trong những bài toán được quan tâm
từ rất sớm trong lịch sử. Từ xa xưa người ta đã tiến hành phân lớp trong mọi

lĩnh vực. Trong trường hợp tổng thể chỉ có một đặc trưng việc phân lớp hoàn
toàn hình thành tự động hay theo một quan điểm chủ quan nào đó. Ngay trong
trường hợp chỉ dùng một đặc trưng, ý tưởng phân lớp đã rõ ràng và nó cũng
mặc nhiên vượt khỏi giới hạn tổng thể 1 đặc trưng. Chẳng hạn, khi quan sát,
nghiên cứu thu thập của cư dân. Cho dù các điều kiện xã hội, kinh tế, chính trị
cũng như các điều kiện khác là thuần nhất thì người nghiên cứu thu thập với
mục đích tìm thị trường cho một loại hàng (kể cả hàng thiết yếu như lương
thực, thực phẩm, may mặc,…) cũng thường trực một ý niệm là mức hay tỷ lệ
chi cho tiêu dùng mặt hàng mà họ quan tâm có thể khác nhau theo giới. Tổng
thể mặc nhiên được phân lớp: Nam và Nữ. Có rất nhiều bài toán phân lớp tự
bộc lộ lời giải ngay trong quá trình vận động của tổng thể. Sẽ không ai thắc
mắc giới tính của cư dân lại chia 2 lớp, hàng hóa lại chia thành thiết yếu,
thông thường và xa xỉ cũng như cách phân chia chúng trong mọi thời đại. Tuy
nhiên, khi mỗi cá thể của tổng thể có quá nhiều đặc trưng nhất là có nhiều đặc
trưng mới mà ta không thể hiểu cặn kẽ: khi chính các đặc trưng này lại vận
động trong mối quan hệ tác động qua lại đồng thời thì việc phân lớp trở thành
vấn đề phức tạp. Có thể thấy vấn đề không chỉ giới hạn ở việc có quá nhiều
đặc trưng cho mỗi cá thể mà chính trong điều kiện này không thể áp đặt một
quan niệm hay mục đích chủ quan trong việc phân lớp. Vì vậy việc nghiên
cứu những cơ sở của các phương pháp khác nhau để giải quyết bài toán phân
lớp khách quan, không phụ thuộc vào các quan điểm chủ quan, mà chỉ phụ
thuộc vào chính sự biểu hiện của các cá thể trong quá trình vận động của
chúng.

1


Hơn nữa tiêu chuẩn cao nhất trong phân lớp một tổng thể là tạo ra các
lớp (tập con) với sự thuần nhất tối đa có thể trong từng lớp cũng như sự khác
biệt tối đa của các cá thể khác lớp.

Thấy được ý nghĩa quan trọng của sự phân tích lớp kinh tế và trên thực
tế chưa có nhiều đề tài nghiên cứu vấn đề này nên dưới sự hướng dẫn của
thầy PGS.TS. Trần Trọng Nguyên em lựa chọn đề nghiên cứu cho khóa
luận tốt nghiệp của mình là:
“PHÂN TÍCH LỚP VÀ ỨNG DỤNG”
2. Mục đích nghiên cứu
✓ Cơ sở lý thuyết về độ đo khoảng cách.
✓ Cơ sở lý thuyết về phân tích lớp.
✓ Ứng dụng phần mềm thống kê SPSS để giải các bài toán về phân tích
lớp.
3. Đối tượng và phạm vi nghiên cứu
✓ Đối tượng nghiên cứu: Các khái niệm cơ bản được sử dụng trong các
bài toán phân lớp với sự trợ giúp của SPSS.
✓ Phạm vi nghiên cứu: Các dạng toán phân lớp và ứng dụng và một số
bài toán.
4. Phương pháp và công cụ nghiên cứu
✓ Phần mềm SPSS.
✓ Nghiên cứu tổng hợp, thống kê, liệt kê, so sánh.
✓ Phân tích dữ liệu.
5. Cấu trúc khóa luận
✓ Ngoài phần mở đầu khóa luận và tài liệu tham khảo. Nội dung nghiên
cứu của khóa luận dự kiến gồm 3 chương:
Chương 1: Độ đo khoảng cách.
Chương 2: Phương pháp phân lớp.
Chương 3: Bài toán toán phân lớp trên SPSS.
2


CHƯƠNG 1: ĐỘ ĐO KHOẢNG CÁCH
Chương này chủ yếu trình bày về các khái niệm, tính chất và các kiến

thức liên quan để phục vụ cho nội dung chính ở chương 2 và chương 3.
1.1. Khoảng cách
Dữ liệu cho phân lớp một tập hợn n các thể có thể được cho dưới dạng
một bảng số (số liệu thô) hay một bảng quan hệ n x n. Để thực hiện phân
nhóm các cá thể một trong những yếu tố quan trọng nhất là xác định khoảng
cách giữa các các thể và khoảng cách giữa các nhóm. Các khoảng cách thông
thường được thể hiện dưới hai dạng: Chỉ số tương tự hoặc chỉ số khác biệt (độ
phát tán) của các cặp cá thể. Sau đây chúng ta xem xét sơ lược các loại
khoảng cách thường sử dụng.
1.1.1. Độ đo khác biệt
Xét tập n các thể, mỗi các thể có thể đặc trưng bởi p đặc trưng (biến).
Gọi E là tập các cá thể cần phân lớp.
Khoảng cách đo bằng độ khác biệt giữa cá thể i và cá thể j là một số
thực d (i, j ) thỏa mãn các điều kiện
+ d (i, j ) = d ( j, i) ;
+ d (i, j )  0 ;
+ d (i, j ) = 0 nếu và chỉ nếu i = j ;
+ d (i, j )  d (i, k ) + d (k , j ) .
Có thể mở rộng định nghĩa trên đối với việc bỏ đi điều kiện thứ tự ta
được một khoảng cách phi Ơcơlit.
Một số độ đo khoảng cách (Với các biến có thang đo khoảng)

3


m

(

Euclidean: d 2 (i, k ) =  xij − xkj

j =1

2

)

1/2

Squared Euclidean: d (i, k ) =  ( xij − xkj )
m

2
2

2

j =1

Mahanobis: d (i, k ) = ( X i − X k )  −1 ( X i − X k )

T

m

Block: d (i, k ) =  xij − xkj
j =1






(

p

Chebychev: d (i, k ) = max xij − xkj
m

Minkowski: d p (i, k ) =  xij − xkj
j =1

)

1/ p

p 1

Pearson correlation*: d (i, k ) = 1 − r (i, k )
Cosine*: d (i, k ) = 1 −

i, k
i k

Có thể thấy rằng khoảng cách thông thường trong không gian tuyến tính là
khoảng cách Ơ cơ lit. (* các khoảng cách đo độ tương tự).
1.1.2. Độ đo tương tự (với các biến tần số)
Với các biến tần số hay số đếm, người ta sử dụng các khoảng cách
tương đối đặc biệt. Đó là khoảng cách Khi-bình phương và Phi
Khi bình phương:  2 = 
i, j


Phi:  =

(O

ij

− Eij )

2

Eij

2
n

4


1.1.3. Độ đo tương tự (cho tập các biến nhị phân)
Độ tương tự (chỉ số tương tự) của i và j là số thực s (i, j ) được xác
định thỏa mãn các điều kiện sau
+ s(i, j ) = s( j, i) ;
+ s(i, j )  0 ;
+ s(i, i)  s(i, j ) ;
Độ đo này tương tự độ đo nhận được từ ma trận hiệp phương sai. Các
biến nhị phân có thể sử dụng độ đo khác biệt như các biến thang đo khoảng.
Tuy nhiên, thuận lợi hơn người ta sử dụng một số chỉ số phản ánh độ tương tự
của các cá thể.
Một số chỉ số được tính như sau

Nếu ta có n các thể được thể hiện bởi p (đặc trưng) biến định tính, ta
có thể xem xét độ tương tự của hai các thể i, j nhờ thông tin các đặc trưng có
xuất hiện ở các cá thể này hay không. Gọi
a là số lần đặc trưng A ở cả i và j ;
b là số lần đặc trưng A có ở i và không có ở j ;
c là số lần đặc trưng A có ở j và không có ở i ;
d là số lần đặc trưng A không có ở cả i và j ;
Một số độ đo phát tán lấy phần bù đơn vị được sử dụng như sau (gọi là
chỉ số tương tự):
Jaccard

Czekanowski (Dice)

a
a+b+c

(J)

2a
2a + b + c

(C-D)

5


a
(a + b)(a + c)

Ochiai


(O)

Russel – Rao

a
a+b+c+d

(R-R)

Rogers – Tanismoto

a+d
a + d + 2(b + c)

(R-T)

1.1.4. Độ đo hỗn hợp
Với số liệu hỗn hợp là số liệu có các biến thang đo khác nhau
(thang đo khoảng, nhị phân hay thứ bậc).
Có 3 giải pháp thường sử dụng.
+ Chuyển các biến thang đo khoảng cách thành các biến định tính và mã hóa
các biến này theo thang đo định danh.
+ Mã hóa các biến thang đo định danh thành các biến thang đo khoảng.
+ Sử dụng độ đo hỗn hợp.

Nguyên tắc cơ bản thiết lập độ đô hỗn hợp là
Cho bảng dữ liệu X nxp ( p biến), khoảng cách giữa hai các nhân I và k
xác định theo công thức


1 p
d (i, k ) =  j (i, k )
p j =1
2

 j (i, k ) được xác định như sau

6


Với các biến thang đo khoảng (biến số)
2

 xij − xkj 


s
j


 j (i, k ) =

xij
xij 
 max − min 
sj
s j 


Với các biến thang đo định danh

1 xij = xkj
0 xij  xkj

 j (i, k ) = 

Thí dụ 1.1: Thống kê biến động giá cổ phiếu 10 phiên liên tiếp của 6
công ty cho ở bảng dưới đây (1 = tăng hơn 6,2%, 0 = tăng không quá 6,2%).
Số lần tối đa xảy ra đặc trưng “tăng hơn 6,2%” là 10.
Phiên

1

2

3

4

5

6

7

8

9

10


PREE

1

0

1

1

1

1

1

1

1

0

PSAM

0

1

1


1

1

1

1

1

1

0

PHAP

1

0

1

0

1

1

1


1

1

0

PTMS

0

0

1

1

1

1

1

1

1

0

PLAF


0

0

1

1

1

1

1

1

1

1

PSHG

0

0

0

0


0

0

0

0

0

0

Có thể dùng các độ đo trên xem xét quan hệ về hiện tượng “tăng giá
hơn 6,2%/phiên” của các cổ phiếu. Kết quả tính toán cho ở bảng dưới đây.

7


PREE

PSAM

PHAP

PTMS

PLAF

PSGH


Jaccard Measure
PREE

1,000

,778

,875

,875

,778

,000

PSAM

,778

1,000

,667

,875

,778

,000

PHAP


,875

,667

1,000

,750

,667

,000

PTMS

,875

,875

,750

1,000

,875

,000

PLAF

,778


,778

,667

,875

1,000

,000

PSGH

,000

,000

,000

,000

,000

1,000

Có thể lựa chọn các độ đo khác trên SPSS.
Với số liệu trên có thể sử dụng ma trận hiệp phương sai để đo độ tương
tự. Kết quả tính toán là

PREE


PSAM

PHAP

PTMS

PLAF

PREE

0,400

PSAM

0,245

0,400

PHAP

0,374

0,200

0,458

PTMS

0,374


0,374

0,332

0,458

PLAF

0,245

0,245

0,200

0,374

0,400

PSGH

0,000

0,000

0,000

0,000

0,000


8

PSGH

0,000


1.2. Khoảng cách giữa các nhóm
Với các cá thể khoảng cách được lựa chọn tương đối đơn giản vì nếu
xem mỗi cá thể là 1 nhóm thì có thể sử dụng các khoảng cách trong (1.1.1.).
Trong các thủ tục ghép nhóm người ta gặp vấn đề khoảng cách giữa các
nhóm, khi ít nhất một trong các cặp nhóm có hơn 1 các thể. Có nhiều lựa chọn
khác nhau để giải quyết vấn đề này, tùy thuộc vào tính chất của tổng thể
nghiên cứu và mục tiêu phân nhóm mà chọn cách xác định khoảng cách giữa
các nhóm cho phù hợp. Sau đây là một số cách xác định khoảng cách nhóm.
Để mô tả dễ dàng hơn chúng ta gọi S = ( sij ) là ma trận các chỉ số khác
biệt hoặc tương tự tính cho các cá thể. Với 1 trong các lựa chọn theo cách nói
ở trên chúng ta có sẵn ma trận S nxn .
Xuất phát từ n cá thể tương ứng n nhóm (mỗi nhóm 1 cá thể). Số các
thể của nhóm N i = 1 (i = 1,2,...n) .
Khoảng cách giữa nhóm A và nhóm B được xác định theo một trong
các liên kết sau:
1.2.1. Liên kết trung bình
Tính s AB theo công thức (Sokal and Michener)
s AB =

1
 sxy
N A N B xA yB


1.2.2. Liên kết đơn
Tính s AB : s AB = Min sxy 

Nếu S có độ đo khác biệt

s AB = Max s xy 

Nếu S có độ đo tương tự

9


1.2.3. Liên kết đầy đủ
Tính sAB: s AB = Max {sxy : x  A, y  B} Nếu S có độ đo khác biệt
s AB = Min {sxy : x  A, y  B} Nếu S có độ đo tương tự

1.3. Một số vấn đề tổ hợp trong phân lớp
Về mặt lý thuyết khi tập E là hữu hạn chúng ta có thể cung cấp mọi
cách phân nhóm, sau đó dùng một tiêu chuẩn nào đó để chọn cách phân nhóm
tối ưu. Tuy nhiên ngay điều này cũng không dễ dàng gì, hơn thế nếu có sẵn
một tiêu thức có vai trò hàm mục tiêu thì tiêu thức này cũng chỉ cung cấp một
cách phân nhóm chủ quan. Số cách tổ hợp khác nhau từ n phần tử quá lớn,
chưa nói đến mỗi cách tổ hợp sinh ra một số lớn các tổ hợp. Hãy xét tình
trạng về số tổ hợp và mối quan hệ của chúng.
1.3.1. Số cách phân chia tập n cá thể thành các lớp k cá thể
Ký hiệu Pn,k là số cách chia n cá thể thành các lớp có k cá thể ta thấy

Pn,1 = Pn,n = 1
Pn,n−1 = n(n − 1) / 2

......
Pn,2 = 2n−1 − 1

Có thể chứng minh rằng: Pn,k = Pn−1,k −1 + kPn−1,k
Và:

Pn ,k =

1 k i
Ck (−1) k −i i n

n! i =1

10

(1.1)


1.3.2. Tổng số cách chia n cá thể
Gọi Pn là tổng số cách chia n các thể ta có thể xác định Pn theo công
thức sau
n

Pn =  Cni −−11Pn−i

với P0 = 0

(1.2)

i =1


1.3.3. Lựa chọn số lớp tối ưu
Cho n cá thể ( n điểm: X i (i = 1,, n) ) chúng ta có tối đa n − 2 cách
chọn số lớp (k = 2, n − 1) có ý nghĩa. Với mỗi k chúng ta chia n cá thể
thành k lớp ( E1 , E2 , Ek ) . Mỗi lớp chúng ta có một tâm lớp g j ( j = 1...k ) .
Gọi tâm n cá thể là g lúc đó có thể tính.
+ Quán tính của đám mây n điểm
n

IT=  pi (Xi -g)T M(Xi -g)

(1.3)

i=1

+ Quán tính của đám mây điểm thứ j
IWj =



xij E j

pij ( X ij − g j )T M (X ij − g j )

(1.4)

k

+ Quán tính giữa các lớp


I B =  n j ( g j − g )T M ( g j − g )
j =1

k

I W =  p j I wj

(1.5)

j =1

Từ đó có thể tính

Fk =

I B / (k − 1)
I W / (n − k )

Fk phân phối Fisher với các bậc tự do (k − 1) và (n − k )

11

(1.6)


Đặt P( Fk  F ( k – 1, n – k ) = ak

(1.7)

ak chính là mức sai lầm loại 1 (mức ý nghĩa) của việc phân lớp n cá


thể thành k lớp. Nếu cách phân chia thành k lớp được tiến hành theo một tiêu
chuẩn tốt nhất thì chúng ta có thể tìm được một số lớp tốt nhất k * .
Số lớp tốt nhất k * thỏa mãn điều kiện: ak* = minak

(1.8)

Để tìm k theo (1.8) cần tính toán tất cả các trường hợp, thực tế với số
cá thể lớn thủ tục này không đơn giản. Vì lý do đó người ta sử dụng biến động
giảm khoảng cách lớp khi ghép lớp để chọn k . Thông thường mỗi phương
pháp cụ thể đều tính được sau mỗi bước ghép lớp thì lượng thông tin về sự
khác biệt giữa các cá thể giảm bao nhiêu. Một tín hiệu giảm nhanh đột ngột
thường cho thấy không nên tiếp tục ghép lớp.
Cũng cần chú ý là số lớp cần thiết đôi khi còn phụ thuộc vào người sử
dụng kết quả, các kỹ thuật phân tích chỉ có vai trò cung cấp thông tin. Người
sử dụng sẽ là người quyết định chọn bao nhiêu lớp.

12


CHƯƠNG 2 CÁC PHƯƠNG PHÁP PHÂN LỚP
Thông thường các phương pháp phân lớp được chia thành hai nhóm:
- Phương pháp thứ bậc là phương pháp tạo nên một cây ghép lớp trong đó
các số lớp được giảm dần (hay tăng đần) mà kết quả phân chia k lớp nhận
được từ việc ghép 2 lớp nào đó từ k + 1 lớp.
- Phương pháp không thứ bậc là phương pháp xác định trước số lớp k . Từ
n cá thể cần tạo ra k nhóm sao cho các cá thể cùng nhóm khác nhau ít

hơn các cá thể khác nhóm.
- Việc đánh giá chất lượng phân lớp thường được thực hiện bở tỷ lệ khác

biệt trong các lớp với tỷ lệ khác biệt giữa các lớp.
2.1. Phân lớp không thứ bậc
Phân lớp các cá thể bằng phương pháp không thứ bậc được thức hiện
khi số lớp đã lựa chọn trước (hay có thể xem k là một tham số của bài toán).
Có thể có nhiều cách khác nhau khi sử dụng các phương pháp như hai
cách phổ biến là giảm dần số lớp và ngược lại là tăng dần số lớp. Ở đây chúng
ta xem xét các phương pháp phân lớp theo cách giảm dần số lớp. Tức là n cá
thể chúng ta xuất phát từ trạng thái có n lớp (mỗi lớp 1 cá thể). Độ đo tương
tự (hoặc khác biệt) được mô tả qua ma trận khoảng cách và khoảng cách lớp.

2.1.1. Các phương pháp kiểu đám mây động trong không gian Ơ cơ lit
Các phương pháp loại này cho phép giải quyết nhanh bài toán phân lớp,
đối với các tập hợp, theo một tiêu chuẩn tối ưu địa phương được sử dụng như
một độ đo quán tính. Chúng ta giả sử rằng các cá thể của tập hợp được mô tả
bởi các điểm trong R p xác định một khoảng cách ơcơlít.

13


2.1.1.1. Quán tính giữa các lớp và trong từng lớp
Cho đám mây n điểm với tâm g , giả sử rằng đám mây này được chia
thành k lớp. Gọi g1 , g 2 ,, g k là các tâm của các lớp ( g j = ( g j1, g j 2 ,, g jk ))
và I1 , I 2 ,, I k là quán tính của các lớp, chúng ta sẽ gọi là quán tính trong của
các lớp để phân biệt với quán tính chung của đám mây. Các quán tính này
được tính theo các tâm lớp.
Đặt aij = 1 nếu cá thể i thuộc lớp j, aij = 0 nếu cá thể i không thuộc
lớp j . Với M = E ta có
n

I j =  aij d

i =1

( x , g ) =  a ( x
p

n

2

i

j

i =1

ij

h =1

ih

− gj)

2

Tổng các quán tính các lớp gọi là quán tính trong của các lớp ký hiệu IW .
k

Iw =  I j


(2.1)

j =1

Tổng quán tính giữa các lớp, ký hiệu I B , xác định như sau

I B =  Pj d 2 ( g j , g )
k

(2.2)

j =1

Trong đó Pj là trọng số của lớp j; xih mô tả cá thể i của biến. Nếu mọi
cá thể có trọng số 1 thì có thể tính Pj = n j .
Nhờ công thức Huygens ta có thể nhận được công thức tính tổng quán
tính chung như sau
I = I B + IW

(2.3)

Tiêu chuẩn sử dụng phân lớp cực tiểu hóa IW hoặc tương đương là cực
đại hóa I B .
Chú ý rằng tiêu chuẩn này dựa trên giả thiết k xác định, nếu k không
xác định có thể dẫn đến việc chia tập n điểm thành n lớp ( IW = 0 ).
14


2.1.1.2. Thuật toán K-means cluster
Phương pháp này lựa chọn khoảng cách phù hợp với thuộc tính của các

biến với tâm các nhóm được tính qua trung bình của các biến trong nhóm.
Không mất tính tổng quát có thể mô tả thuật toán này với M = E .
Giả sử n cá thể được chia thành k nhóm với các tâm c = ( c1, c2 ,, ck )
với số cá thể tương ứng ( n1 , n2 ,, nk ). Tổng sai số bình phương của các cá
thể so với tâm LW được xác định qua công thức sau
k

L =  xi − c j

2

j =1 i j

k

n

j =1

i

=  xi − c j

2

(2.4)

Trong đó aij = 1 nếu cá thể I thuộc nhóm j và aij = 0 nếu cá thể i
không thuộc nhóm j .
Bài toán cực tiểu LW dẫn đến bài toán a = aij và c . Như vậy có thể xác

định hai bài toán lồng như sau
Bài toán 1: Tìm a khi c đã biết.
Bài toán 2: Tìm c khi a đã biết.
Có thể viết lại hàm LW tường minh như sau
T

LW =  aij ( xi − c j ) ( xi − c j )
k

j =1

n

(2.5)

i

Bài toán 1 tìm a cực tiểu LW .
Bài toán 2 có thể giải như sau
Điều kiện cần
T
cj LW =  aij  ( xi − c j ) ( xi − c j ) =  aij ( −2 xi + 2c j ) = 0

 i
i
n

n

Giải nhận được


15

(2.6)


a x
=
a

ij i

cj

i

(2.7)

ij

i

Điều kiện đủ: Nếu cho mọi j tồn tại aij = 1 (nhóm j có ít nhất 1 cá thể) thì:
n

cj LW = 2 aij  0
c j (k )
i

(2.8)


Lặp lại thuật toán này cho đến khi tâm các nhóm không thay đổi và các
cá thể tương ứng được xác định. Chú ý là thuật toán trên có thể thực hiện theo
2 cách: thực hiện bài toán thứ 2 khi có sự thay đổi đầu tiên xác nhận được từ
bài toán thứ nhất; hoặc giải bài toán thứ nhất cho k nhóm sau đó mới giải bài
toán thứ 2.
2.1.1.3. Lựa chọn k tâm nhóm
Người ta cải tiến thuật toán trên thành quá trình lặp tìm tâm các nhóm
(từ đó tìm được các nhóm) như sau
Giả sử có k tâm nhóm g1 , g 2 ,, g k , gọi d min là khoảng cách nhỏ nhất
giữa các tâm.
Giả sử dmin = Mind ( gu , gv ) , việc hiệu chỉnh các tâm nhóm có thể
tiến hành như sau:
Xét điểm X k (cá thể thứ k ) của E





Nếu Min d ( X k , g j )  d min ;
Nếu d ( X k , gu )  d ( X k , gv ) thì thay g v bởi X k ;
Nếu d ( X k , gu )  d ( X k , gv ) thì thay gu bởi X k ;
Thuật toán này sẽ cho phép xác định các tâm xa nhau nhất có thể.
Người ta hy vọng giảm được số bước lặp trong quá trình tính toán.

16


2.1.1.4. Khắc phục suy biến
Theo cách thức trên chúng ta nhận thấy khi một nhóm chỉ có 1 cá thể,

nó có thể bị ghép vào một nhóm khác hoặc trở thành tâm của một nhóm thì
bài toán tìm aij không có lời giải duy nhất (bài toán suy biến). Để khắc phục
tình trạng này người ta đưa thêm điều kiện lựa chọn với từng cá thể khi
khoảng cách của nó đến tâm nhóm gần nhất thứ hai lớn hơn khoảng cách nhỏ
nhất của tâm nhóm gần nhất đến các tâm nhóm khác.
Với X k không phải tâm nhóm, thực hiện thủ tục sau
Gọi gu là tâm nhóm gần X k nhất, g v là tâm nhóm gần X k thứ hai.





Nếu d ( X k , gv )  Min d ( gu , g j ) .
Thì thay gu bằng X k để tiếp tục quá trình giải bài toán.
Trường hợp người lại quá trình giải kết thúc.

17


Thí dụ 2.1: Với số liệu giá XMHT và FE6 theo tháng, ta muốn phân
theo thánh 4 nhóm, chọn ngẫu nhiên ban đầu các tâm là các tháng 1, 4, 7, 10.
Kết quả phân lớp cho ở bảng sau.

Khoảng cách

Tháng

XMHT

FE6


Lớp

1

42000

3800

4

28,675

2

41955,08

3745,989

4

47,892

3

41919,21

3742,787

4


81,576

4

41916,23

3792,421

4

81,936

5

42868,43

3888,067

2

51,435

6

52831,85

38884,749

2


26,148

7

42816,63

3833,582

2

27,311

8

42786,22

3830,859

2

48,733

9

42665,01

3820,007

1


0

10

42186,97

3777,206

4

191,552

11

41748,44

3737,942

3

93,979

12

41561,23

3721,18

3


93,979

18

đến tâm lớp


Tâm các lớp và số cá thể:
Số cá thể

Lớp

XMHT

FE6

của lớp

1

42665,01

3820,01

1

2

42825,78


3859,31

4

3

41654,84

3729,56

2

4

41995,5

3771,68

5

Tổng quán tính của đám mây E là: I = 2630849,738
Quán tính của đám mây các tâm nhóm là: I B = 2553556,108
Tổng quán tính của các nhóm là: IW = 77290,63
Fqs = 88,102; F-value = 0,000
2.1.2. Phân lớp với các biến nhị phân
Vể nguyên tắc, các biến định tính có thể xem như các biến định lượng
để mã hóa và sử dụng độ đo tương tự hỗn hợp khi chúng cùng trong một bài
toán với các biến định lượng hoặc được thiết kế riêng biệt. Tuy vậy nếu cần
phân lớp với dữ liệu gồm tất cả các biến định tính thì người ta có thể sử dụng

công cụ tốt hơn, phù hợp với tính chất của số liệu.
Các phương pháp phân lớp một tập hợp E với n cá thể được mô tả qua
các chỉ tiêu định tính đã được P . Michaud và F. Marcotorchino xây dựng.
Người ta gọi các phương pháp này là các phương pháp mô tả số liệu dưới
dạng quan hệ nhị phân.
Độ đo tương tự (hay độ đo khoảng cách) rất phù hợp cho việc phân lớp
các biến nhị phân.

19