Mục lục
Lời nói đầu
1

2

iii

Khái quát chung về dạng và nhận dạng
1.1 Khái niệm về dạng và nhận dạng . . . . . . . . . . . . . .
1.1.1 Khái niệm về dạng, lớp dạng . . . . . . . . . . . . .
1.1.2 Khái niệm nhận dạng: . . . . . . . . . . . . . . . .
1.2 Không gian mẫu và cách tiếp cận nhận dạng . . . . . . . .
1.3 Một số ứng dụng của nhận dạng: . . . . . . . . . . . . . .
1.3.1 Nhận dạng giọng nói . . . . . . . . . . . . . . . . .
1.3.2 Nhận dạng chữ viết tay . . . . . . . . . . . . . . .
1.3.3 Dự báo thời tiết . . . . . . . . . . . . . . . . . . . .
1.3.4 Phân tích điện tâm đồ để chẩn đoán hoạt động của
tim . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.5 Phân tích y học bằng chụp tia X-quang . . . . . . .
1.3.6 Làm rõ các bức ảnh chụp từ vệ tinh và khoảng không
1.4 Học có hướng dẫn và không có hướng dẫn . . . . . . . . .
Phân tích phân cụm và các thuật toán phân cụm
2.1 Phân tích phân cụm . . . . . . . . . . . . . . . . . . . . .
2.1.1 Khái niệm phân cụm . . . . . . . . . . . . . . . . .
2.1.2 Ứng dụng của phân cụm . . . . . . . . . . . . . . .
2.1.3 Các yêu cầu của phân tích phân cụm . . . . . . . .
2.2 Các độ đo thường được sử dụng trong phân tích phân cụm
2.2.1 Độ đo sự gần gũi . . . . . . . . . . . . . . . . . . .
2.2.2 Khoảng cách giữa hai cụm (interset) và khoảng cách
nội cụm (intraset) . . . . . . . . . . . . . . . . . . .


2.4

.
.
.
.
.
.
.
.

25
25
34
36
40
41
45
48

Chương trình ứng dụng thuật toán ISODATA
3.1 Nêu lại ví dụ: . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Các trường hợp tính toán . . . . . . . . . . . . . . . . . .

52
52
52

2.5


.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.


60

ii


Lời nói đầu
Cuộc sống ngày càng hiện đại, khoa học công nghệ ngày càng phát
triển và đạt được nhiều thành tựu to lớn, phục vụ thiết thực cho cuộc sống
của con người. Trong những thành tựu đó không thể không nhắc tới công
nghệ nhận dạng. Công nghệ nhận dạng sử dụng khả năng tính toán của
máy tính để xử lý một khối lượng dữ liệu lớn thành các thông tin cần thiết
dựa vào quá trình nhận dạng của con người. Nhờ công nghệ nhận dạng
bạn có thể điều khiển các đồ vật trong nhà mình không cần bằng tay mà
bằng giọng nói, hay bạn không phải tra thìa khóa vào ổ để mở cửa mà chỉ
cần đặt tay vào máy nhận dạng là cửa tự động mở, v.v. Còn vô số các ứng
dụng mà bạn không thể ngờ tới trong tương lai không xa. Công nghệ cuộc
sống, điều đó thật thú vị phải không? Đó là lí do vì sao chúng tôi chọn đề
tài "Các thuật toán phân tích phân cụm và ứng dụng". Không đi sâu vào
nghiên cứu từng ứng dụng cụ thể của nhận dạng ở trên mà luận văn này
tập trung vào ba chương chính:
Chương 1: Nêu khái quát chung về nhận dạng, bao gồm khái niệm
về dạng, lớp dạng và khái niệm nhận dạng, cùng với những ứng dụng của
nhận dạng. Qua đó cung cấp cho chúng ta một cách nhìn tổng quan về
nhận dạng.
Chương 2: Đây là nội dung chính của bản luận văn. Chương này gồm
ba phần:
• Phần đầu là mục "phân tích phân cụm" bao gồm khái niệm phân cụm,
ứng dụng của phân cụm, và một số yêu cầu trong phân cụm.
• Giới thiệu một số độ đo thường được sử dụng trong phân tích phân

Lê Đăng Điển

iv


Chương 1

Khái quát chung về dạng
và nhận dạng
1.1
1.1.1

Khái niệm về dạng và nhận dạng
Khái niệm về dạng, lớp dạng

Khái niệm về dạng: Chúng ta nói về dạng thường là đề cập đến những
đối tượng hoặc những cá thể mà ta có thể quan sát được. Nhưng thực tế
ta có thể hiểu dạng theo nghĩa rộng hơn, dạng không chỉ là một đối tượng
cụ thể mà còn có thể là một hệ thống dữ liệu.
Có rất nhiều ví dụ về dạng như khi ta nghiên cứu tình hình kinh tế
của một quốc gia thì ta đề cập đến dạng của nền kinh tế quốc gia đó, ta
nhận thấy rằng trong suốt quá trình khủng hoảng tài chính thế giới năm
1997-1999 có nhiều quốc gia bị ảnh hưởng nặng nề nhưng một số khác thì
không, lí do là dạng nền kinh tế của họ là khác nhau.
Khái niệm về lớp dạng: Dạng có thể được xác định định lượng hay
được mô tả cấu trúc của đối tượng mà chúng ta quan tâm. Theo đó một
lớp dạng có thể được hiểu là một tập hợp các dạng có một số thuộc tính
chung.
Thông thường, dạng được mô tả như một điểm trong không gian đa
chiều thích hợp nào đó gọi là không gian dạng (mỗi chiều tương ứng với

cảnh, tranh ảnh, biểu tượng, các kí tự (chữ Latinh, chữ Ả rập, chữ
Trung Hoa), các bản đồ thời tiết, điện tâm đồ (ECG), điện não đồ
(EEG), hình ảnh chụp X-quang,...
2. Nhận dạng đối tượng trừu tượng: là nhận dạng khái niệm. Ví dụ, khi
nghe một bản nhạc ta có thể nhận biết được bài đó có giai điệu đàn
guitar hay piano ...

1.2

Không gian mẫu và cách tiếp cận nhận
dạng

Chúng ta cần lựa chọn, đo đạc hay quan sát để thu thập một tập dữ
liệu về một hiện tượng nào đó. Nếu hiện tượng cần phân tích bao gồm
2


Chương 1. Khái quát chung về dạng và nhận dạng

các đối tượng vật lý hoặc hình ảnh, thì thiết bị thu thập dữ liệu có thể là
camera, máy quét đa phổ, hay một thiết bị khác. Đối với những vấn đề
khác như bài toán kinh tế, có thể cần đến một loại hệ thu thập dữ liệu đặc
thù để thu được một tập dữ liệu phù hợp.
Trong quá trình tiền xử lý dữ liệu chúng ta thường sử dụng một phép
biến đổi (hay một hàm) nào đó để chuyển đổi dạng quan sát được thành
một dạng điện tử hoặc chuyển đổi một tập hợp dữ liệu rời rạc thành dạng
toán học sao cho dữ liệu này phù hợp hơn với việc phân tích của máy tính.
Kết quả của quá trình chuyển đổi này sẽ cho một véc tơ dạng, và véc tơ
này được xem như một điểm trong không gian dạng mẫu.
Chẳng hạn nếu ta quét một ảnh bằng một máy quét đa phổ 12 kênh,


 T 

 x2   x21 x22 · · · x2n 
 

S=
 ..  = 

..
 .  

.
  

T
xN
xN 1 xN 2 · · · xN n
trong đó xTi = (xi1 , xi2 , · · · , xin ), i = 1, · · · , N , biểu diễn véc tơ dạng mẫu
thứ i.
3


Chương 1. Khái quát chung về dạng và nhận dạng

Mục đích của việc trích chọn đặc trưng là quá trình làm giảm số chiều.
Nó chuyển đổi dữ liệu gốc thành một dạng phù hợp gọi là véc tơ dạng mẫu
và sẽ được sử dụng như đầu vào cho quá trình xử lý đưa ra quyết định
phân loại. Như vậy kết quả của quá trình trích chọn đặc trưng sẽ cho các
véc tơ đặc trưng:

 .. 
 . 


 l 
l
xi =  xik  ; l = 1, · · · , K; i = 1, · · · , Nl ; k = 1, · · · , n


 .. 
 . 


l
xin
4


Chương 1. Khái quát chung về dạng và nhận dạng

trong đó l là chỉ số của lớp dạng, i là chỉ số véc tơ dạng mẫu thứ i của
lớp thứ l: ωl ; k là thành phần thứ k của vectơ dạng mẫu n chiều. K, Nl , n
tương ứng là số lớp dạng, số véc tơ dạng mẫu của lớp thứ l, và số chiều
của vectơ dạng mẫu.
Các véc tơ dạng mẫu thuộc cùng một lớp dạng do có cùng một số thuộc
tính chung sẽ tạo thành một cụm trong một miền nhất định của không
gian dạng mẫu.
Trong trường hợp không gian dạng mẫu là hai chiều thì bài toán phân
loại thực chất là tìm một mặt phân biệt trong không gian dạng mẫu sao
cho nó có khả năng phân loại đúng tất cả các véc tơ dạng mẫu của tập

5


Chương 1. Khái quát chung về dạng và nhận dạng

1.3.1

Nhận dạng giọng nói

Nhận dạng giọng nói có rất nhiều ứng dụng. Ví dụ như, trong công tác
điều tra tội phạm, việc nhận dạng được chính xác giọng nói của các đối
tượng để phân tích xem họ có phải đối tượng nghi vấn không hay không.
Chúng ta có thể mô tả cơ chế hoạt động của một hệ thống nhận dạng
giọng nói theo sơ đồ sau:

Hình 1.1: Cơ chế của hệ thống nhận dạng giọng nói

Các tín hiệu biến đổi từ các ngôn từ, đầu tiên được lọc và lấy mẫu
6


Chương 1. Khái quát chung về dạng và nhận dạng

thông qua các bộ lọc thông âm điệu với tần số trung tâm từ 200Hz đến
7500Hz. Một vài tham số riêng, chẳng hạn như những đỉnh cục bộ phổ,
năng lượng giọng nói, và những biểu diễn toàn bộ mẫu của phổ, được
chiết xuất cho sự phân mảnh và nhận dạng âm vị. Lỗi xuất hiện trong
quá trình phân mảnh và nhận dạng âm vị được sửa bằng cách cho trước
các quy tắc sửa lỗi âm vị, sau đó các tính toán tương đương được thực
hiện và các tương thích nhất được chọn cho giải pháp.

là phương pháp phân tích tương quan và phương pháp phân tích thành
phần chính (Kahunen-Loeve). Cả hai phương pháp này sẽ tìm ra những
đặc trưng tổng thể. Ứng dụng của phương pháp cú pháp cho bài toán dự
báo thời tiết, chẳng hạn như sử dụng chuỗi hoặc cây biểu diễn cho biểu đồ
đường đẳng áp, cũng đang được nghiên cứu.
7


Chương 1. Khái quát chung về dạng và nhận dạng

1.3.4

Phân tích điện tâm đồ để chẩn đoán hoạt động
của tim

Điện tâm đồ (ECG) ghi chép lại hoạt động của tim thông qua máy đo
nhịp tim. Thông tin về tim và những dẫn giải về thể chất của người bệnh
có thể dễ dàng được ghi lại dưới dạng sóng trong định dạng "file" được
chuyển đến. Các thông số được ghi lại qua máy điện tâm đồ rất hữu ích
cho việc chẩn đoán các hoạt động của tim bệnh nhân từ đó bác sĩ có những
biện pháp điều trị hợp lí.

1.3.5

Phân tích y học bằng chụp tia X-quang

Việc phát hiện, chẩn đoán sớm và chính xác bệnh có thể cứu chữa kịp
thời cho bệnh nhân. Ví dụ về bệnh ho dị ứng do hít phải nhiều bụi của
công nhân mỏ than đá, nguyên nhân do liên tục hít phải khí bụi bẩn và
độc hại. Triệu chứng chính là sự giảm động mạch phổi. Chẩn đoán dựa

Học có hướng dẫn và không có hướng
dẫn

Ta đã thấy ở trên một thủ tục nhận dạng sẽ bao gồm hai công đoạn
là học và phân loại, trong đó công đoạn học (hay còn gọi là luyện) là quá
trình hình thành tri thức phân loại dựa trên các thông tin đã cho trước
ở tập luyện còn công đoạn phân loại là quá trình đưa ra quyết định phân
loại một dạng có véc tơ dạng mẫu bất kỳ vào một trong các lớp hay các
cụm đã được xác định. Tùy theo cấu trúc của tập luyện cho trước ta phân
biệt hai quá trình học sau:
Quá trình học có hướng dẫn là quá trình hình thành tri thức phân loại
thông qua việc xử lý một tập luyện bao gồm các véc tơ dạng mẫu cùng với
chỉ số lớp tương ứng của nó đều đã cho trước. Khi đó, thủ tục nhận dạng
được xây dựng sẽ lần lượt xử lý các véc tơ dạng mẫu của tập luyện và mỗi
khi tri thức phân loại đã hình thành được sử dụng để phân loại cho véc
tơ dạng mẫu mới được xét của tập luyện cho kết quả không đúng với chỉ
số lớp cho trước của nó thì thủ tục phân loại sẽ thực hiện một hiệu chỉnh
các tham số của nó và quá trình học này sẽ chỉ kết thúc khi: với tham số
đã hiệu chỉnh, thủ tục phân loại đã thực hiện phân loại đúng toàn bộ tập
luyện cho trước. Tập luyện bao gồm các véc tơ dạng mẫu cùng với chỉ số
lớp tương ứng của nó đều đã cho trước như xét trên sẽ được gọi là một tập
luyện có hướng dẫn. Rõ ràng là nếu tập luyện có hướng dẫn có kích thước
đủ lớn và có tính đại diện cho lớp dạng của không gian dạng thì có cơ sở
để tin là thủ tục phân loại đã học được các tri thức phân loại cần thiết
và sẽ có khả năng thực hiện phân loại chính xác không chỉ với các véc tơ
dạng mẫu của tập luyện mà đối với cả một véc tơ dạng mới bất kỳ.
Quá trình học không có hướng dẫn là quá trình hình thành tri thức
phân loại cho một thủ tục nhận dạng nhờ kết quả xử lý một tập luyện chỉ
bao gồm các véc tơ dạng mẫu mà không cho trước các chỉ số lớp tương
ứng của chúng. Tập luyện này được gọi là tập luyện không có hướng dẫn


Phân tích phân cụm và
các thuật toán phân cụm
2.1
2.1.1

Phân tích phân cụm
Khái niệm phân cụm

Phân cụm là phương pháp phân loại một tập dữ liệu (hay còn gọi là
tập luyện) trong đó quá trình tạo ra các cụm không sử dụng bất kỳ kiến
thức tiên nghiệm nào về chỉ số lớp của các cá thể thuộc tập luyện.
Khi cho một tập luyện S gồm N phần tử:
S = {xi |xi ∈ Rn , i = 1, · · · , N }
Thì quá trình phân cụm có thể được phát biểu như sau:
Tìm các miền con: S1 , S2 · · · , SK của tập luyện S sao cho mỗi xi , i=1,...,N
sẽ chỉ thuộc vào duy nhất một miền con xác định trên, nghĩa là:
S1 ∪ S2 ∪ · · · ∪ SK = S
Si ∩ Sj = ∅ với ∀i = j
Khi đó ta nói tập luyện có N phần tử trên đã được phân thành K cụm
khác nhau. Đồng thời, các véc tơ thuộc cùng một cụm Si thì "gần nhau"
hơn, còn các véc tơ thuộc các cụm khác nhau thì không "gần nhau", trong
đó tiêu chuẩn độ đo sự gần gũi giữa các véc tơ của các cụm sẽ được lựa
11


Chương 2. Phân tích phân cụm và các thuật toán phân cụm

chọn thích hợp với kiểu dáng hình thành của tập luyện cũng như với các
thành phần được xác định (hay còn gọi là các biến) của các véc tơ dạng

Theo các nghiên cứu gần đây, chưa có một phương pháp phân cụm tổng
quát nào có thể giải quyết trọn vẹn cho tất cả tập dữ liệu. Hơn nữa, mỗi
phương pháp phân cụm cần có cách thức biểu diễn cấu trúc khác nhau, và
với mỗi cách thức biểu diễn khác nhau sẽ tương ứng với một thuật toán
phân cụm phù hợp. Vì vậy, phân cụm vẫn đang là một vấn đề khó và mở,
vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với
nhiều tập dữ liệu khác nhau nhất là đối với các tập dữ liệu dạng hỗn hợp.

12


Chương 2. Phân tích phân cụm và các thuật toán phân cụm

2.1.2

Ứng dụng của phân cụm

Phân cụm có nhiều ứng dụng trong nhiều lĩnh vực như:
• Thương mại: Tìm kiếm nhóm các khách hàng quan trọng có đặc trưng
tương đồng và những đặc tả họ từ những bản ghi mua bán trong các
mẫu dữ liệu
• Sinh học: Phân loại các gen với các chức năng tương đồng và thu được
các cấu trúc trong mẫu
• Thư viện: Phân loại các cụm sách có nội dung và ý nghĩa tương đồng
nhau để cung cấp cho độc giả.
• Bảo hiểm: Nhận dạng các nhóm đối tượng tham gia bảo hiểm có chi
phi bồi thường cao, hoặc ưu tiên đặc biệt.
• Quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa
lí,... nhằm cung cấp thông tin cho quy hoạch đô thị.
• Nghiên cứu trái đất: Phân cụm để theo dõi các tâm động đất nhằm

vậy hướng tới việc tìm kiếm các cụm hình cầu với mật độ và kích cỡ
tương tự nhau. Tuy nhiên, một cụm có thể có bất cứ một hình dạng
nào. Do đó, việc phát triển các thuật toán có thể khám phá ra các cụm
có hình dạng bất kì là việc làm quan trọng.
• Tối thiểu hóa tri thức cần cho xác định các tham số đầu vào:
Nhiều thuật toán phân cụm yêu cầu người dùng đưa vào những tham
số nhất định trong phân tích phân cụm (như số lượng các cụm mong
muốn). Kết quả của phân cụm thường khá nhạy cảm với các tham số
đầu vào. Nhiều tham số rất khó để xác định, nhất là với các tập dữ
liệu có số lượng phần tử lớn. Điều này không những gây trở ngại cho
người dùng mà còn làm cho khó có thể điều chỉnh được chất lượng
phân cụm.
• Khả năng thích nghi với các dữ liệu nhiễu: Hầu hết những tập
dữ liệu đều chứa đựng những phần tử ngoại lai, dữ liệu lỗi, chưa biết
thuộc tính hoặc sai. Một số thuật toán phân cụm nhạy cảm với dữ liệu
như vậy và có thể dẫn đến chất lượng phân cụm thấp.
• Ít nhạy cảm với thứ tự đầu vào của các tập dữ liệu: Một số
thuật toán phân cụm nhạy cảm với thứ tự đầu vào của dữ liệu, ví dụ
như với cùng một tập dữ liệu, khi được đưa vào với các thứ tự khác
nhau thì có thể sinh ra các cụm khác nhau. Do đó, việc quan trọng là
phát triển một thuật toán ít nhạy cảm với thứ tự đầu vào của các mẫu
dữ liệu.
• Số chiều lớn: Một tập dữ liệu có thể chứa các véc tơ dạng mẫu với
số chiều hoặc các thuộc tính lớn. Nhiều thuật toán phân cụm áp dụng
tốt cho các mẫu dạng có số chiều thấp, bao gồm chỉ hai đến ba chiều.
Người ta đánh giá việc phân cụm là có chất lượng nếu nó áp dụng được
cho các mẫu dạng từ ba chiều trở lên. Đây là một sự thách thức với
các đối tượng dữ liệu cụm trong không gian với số chiều lớn, đặc biệt
khi xét những không gian với số chiều lớn nhưng có thể rất thưa.
• Phân cụm ràng buộc: Nhiều ứng dụng thực tế có thể thực hiện

Các độ đo sự gần gũi thường được đưa ra dưới dạng số để chỉ mức độ
gần gũi giữa các mẫu trong một cụm, hoặc giữa một mẫu và một cụm các
mẫu, hoặc giữa hai cụm mẫu.
1. Độ đo không tương tự:
• Độ đo khoảng cách Euclide:
Khoảng cách Euclide là độ đo không tương tự đơn giản nhất
và thường sử dụng nhiều nhất, nó được kí hiệu là d(xi , xj ) và xác
định như sau:
n
2

T

(xik − xjk )2

d (xi , xj ) = (xi − xj ) (xi − xj ) =
k=1

15


Chương 2. Phân tích phân cụm và các thuật toán phân cụm

trong đó: xi , xj ∈ Rn .
Khoảng cách này sẽ trở thành độ đo không tương tự nếu các
biến thành phần của véc tơ xi , xj là có cùng thứ nguyên, nếu không
ta cần sử dụng các hiệu chỉnh là các trọng số tương ứng. Khi đó, ta
có một độ đo không tương tự có trọng số được xác định như sau:
n



• Khoảng cách Mahalanobis
Bình phương khoảng cách Mahalanobis từ xi tới xj cho bởi
công thức:
r2 (xi , xj ) = (xi − xj )T C −1 (xi − xj )
trong đó C −1 là ma trận nghịch đảo của ma trận hiệp phương sai
C. Khoảng cách Mahalanobis được sử dụng khi các biến (hay các
thành phần) của véc tơ dạng mẫu không có cùng thứ nguyên.
2. Độ đo tương tự Tanimoto:
Tanimoto đưa ra một tỉ số được biết như là độ đo Tanimoto:
xTi xj
dT (xi , xj ) = T
xi xi + xTj xj − xTi xj
trong đó xTi xj biểu thị số các thuộc tính chung giữa xi và xj . Còn xTi xi
biểu diễn số các thuộc tính có bởi xi , và xTj xj biểu diễn số thuộc tính
có bởi xj . Mẫu số biểu diễn số thuộc tính cái mà có ở trong xi hoặc
xj nhưng không có ở trong cả hai. Vậy độ đo Tanimoto biểu diễn tỉ số
giữa số thuộc tính thuộc vào cả hai véc tơ xi và xj với số thuộc tính
chỉ có ở xi hoặc xj nhưng không có ở cả hai véc tơ dạng mẫu xi và xj .
16


Chương 2. Phân tích phân cụm và các thuật toán phân cụm

2.2.2

Khoảng cách giữa hai cụm (interset) và khoảng
cách nội cụm (intraset)

Bình phương khoảng cách giữa hai cụm riêng biệt: ω1 và ω2 sẽ được ký

N2

n

(x1ik − x2jk )2 .

(2.2)

i=1 j=1 k=1

Như vậy, bình phương khoảng cách này là trung bình của bình phương
các khoảng cách giữa các điểm thuộc các cụm riêng biệt, với chỉ số trên 1
và 2 trong [x1i ] [x2j ] ký hiệu cho các véctơ dạng mẫu thuộc cụm thứ nhất:
ω1 và cụm thứ hai: ω2 và N1 , N2 tương ứng là số véctơ dạng mẫu của cụm
ω1 và ω2
Khoảng cách nội cụm của cụm thứ s (Ss ) gồm N véc tơ dạng mẫu sẽ
được xây dựng tương tự như sau:
Nếu xi , xj ∈ Ss thì khoảng cách giữa chúng là D(xi , xj ) và được xác định
như sau:
n
2

(xik − xjk )2 .

D (xi , xj ) =

(2.3)

k=1



i=1

1
N −1
17

N

n

(xik − xjk )2
j=1 k=1

(2.5)


Chương 2. Phân tích phân cụm và các thuật toán phân cụm

Hay:
2
Dss

N
=
N −1

n

1


k=1

1
N
1
N

N

j=1

1
N

N

1
(xik ) − 2
N
i=1

N

(xik

N

2


(xjk )2
j=1

N

(xjk )2 .

(2.7)

i=1

Do chúng ta đang làm việc trên tập các véc tơ dạng mẫu của cùng một
cụm nên rõ ràng có:
(xik )2 = (xjk )2
(2.8)
Vì vậy ta có :
2
Dss

=

D2 ([xi ], [xj ])

2N
=
N −1

n

2

N

2

i=1

1
xik xik +
N

N

2

(xik )
i=1

2

= (xik )2 − (xik ) .

(2.10)

Sau khi thực hiện quá trình rút gọn trên thì ta thu được công thức tính
khoảng cách nội cụm Dss xác định như sau:
2
Dss

=


dụng độ đo khoảng cách:
Cụm đầu tiên có thể được chọn bất kỳ, giả sử nó có tâm cụm là z1 . Khi
cụm đầu tiên được chọn, phân loại các véc tơ dạng mẫu vào cụm này nếu
khoảng cách từ véc tơ dạng mẫu đó tới tâm cụm z1 là nhỏ hơn một ngưỡng
τ đã cho trước. Nếu không thì tạo ra một cụm mới. Mỗi khi có các véc tơ
dạng mẫu rơi vào trong một cụm thì giá trị tâm cụm và phương sai của
cụm này sẽ được tính lại. Lặp lại quá trình trên cho đến khi tất cả các véc
tơ dạng mẫu đã được phân hết vào các cụm.
Thuật toán phân cụm sử dụng phương pháp trực quan:
Dựa trên cơ sở lí thuyết đã trình bày ở trên, chúng ta có thuật toán phân
cụm trực quan sẽ được tiến hành theo các bước sau:
• Bước 1: Chọn một véc tơ dạng mẫu đầu tiên làm phần tử đại diện z1
của cụm xuất phát, hay z1 = x1 còn được gọi là tâm cụm đầu tiên.
• Bước 2: Chọn một véc tơ dạng mẫu tiếp theo xi và tính toán khoảng
cách của nó tới tất cả các cụm hiện thời (đầu tiên thì chỉ có một cụm),
khi đó có các trường hợp sau:
a. xi thuộc cụm thứ w là ωw có tâm cụm zw nếu:
d(xi , zw ) ≤ θτ

0≤θ≤1

(2.12)

trong đó τ là tham số xác định độ thuộc của véc tơ dạng vào cụm thứ
i và giá trị của τ được thiết lập từ đầu bởi người thiết kế thủ tục phân
cụm
b. xi không thuộc cụm ωw nếu:
d(xi , zw ) > τ

(2.13)


∀w

(2.16)

• Bước 4: Lặp lại bước 2 và bước 3 cho đến khi tất cả các véc tơ dạng
mẫu của tập luyện được phân vào các cụm. Trong quá trình thực hiện
bước 4, có thể xảy ra các kết quả phân cụm ở bước lặp trước bị thay
đổi hay một số véc tơ dạng mẫu sẽ được sắp xếp lại theo một trật tự
khác.
• Bước 5: Quá trình luyện được coi như hoàn thành nếu tất cả các véc
tơ dạng mẫu xi không còn bị thay đổi về sự liên thuộc cụm trong quá
trình phân cụm theo cách trên.
Thuật toán này là đơn giản và hiệu quả, nó có những tính ưu
việt sau:
• Thuật toán này đòi hỏi nhu cầu tính toán tối thiểu.
• Các véc tơ dạng mẫu được xử lí liên tiếp và không có nhu cầu bộ nhớ
lớn.
• Thuật toán cho phép xác định số cụm dạng mà không cần thông tin
gì đặc biệt về số cụm.
Mặt khác nó cũng có vài hạn chế khi dùng thuật toán như sau:
20


Chương 2. Phân tích phân cụm và các thuật toán phân cụm

• Thuật toán này đòi hỏi các véc tơ dạng nếu thuộc cùng một cụm phải
có liên kết chặt chẽ với nhau và giữa các cụm vẫn có sự tách biệt khá
rõ ràng thì thuật toán mới cho một phân cụm như mong đợi.
• Kết quả phân cụm theo thuật toán sẽ phụ thuộc vào thứ tự xử lí các

tâm cụm mới thì quy về Bước 3, Bước 4, Bước 5 và Bước 6 cho đến
khi dừng hẳn thuật toán. Nếu khoảng cách này lớn hơn một phần xác
định của khoảng cách giữa các tâm cụm thì mẫu đó sẽ tương ứng với
một cụm mới. Nếu không, dừng thuật toán.
21