ĐẠI HỌC THÁI NGUYÊN

ĐẠI HỌC THÁI NGUYÊN

KHOA CÔNG NGHỆ THÔNG TIN

KHOA CÔNG NGHỆ THÔNG TIN





Nguyễn Trung Sơn

Nguyễn Trung Sơn

PHƢƠNG PHÁP PHÂN CỤM VÀ ỨNG DỤNG

PHƢƠNG PHÁP PHÂN CỤM VÀ ỨNG DỤNG

Chuyên ngành :
Mã số :

KHOA HỌC MÁY TÍNH
60.48.01

Chuyên ngành :
Mã số :

KHOA HỌC MÁY TÍNH
60.48.01


35

TRANG

2.1 Thuật toán FCM

36

LỜI CẢM ƠN

5

2.2 Thuật toán εFCM

37

LỜI MỞ ĐẦU

6

3. Thuật toán phân cụm dữ liệu dựa vào cụm trung tâm

37

CHƢƠNG I : TỔNG QUAN THUYẾT VỀ PHÂN CỤM DỮ LIỆU

7

3.1 . Thuật toán K – MEANS


4. Thuật toán phân cụm dữ liệu dựa vào tìm kiếm

46

2.1 Dữ liệu Categorical

10

4.1 Thuật toán di truyền (GAS)

46

2.2 Dữ liệu nhị phân

13

4.2 J- Means

48

2.3 Dữ liệu giao dịch

14

5. Thuật toán phân cụm dữ liệu dựa vào lƣới

49

2.4 Dữ liệu Symbolic


3.2 Biến đổi dữ liệu

21

6.1 Thuật toán DBSCAN

53

3.2.1 Phân tích thành phần chính

21

6.2. Thuật toán OPTICS

57

3.2.2 SVD

23

6.3. Thuật toán DENCLUDE

58

3.2.3 Phép biến đổi Karhunen-Loève

24

7. Thuật toán phân cụm dữ liệu dựa trên mẫu


1. Phân đoạn ảnh

62

1.3 Thuật toán ANGNES

32

1.1. Định nghĩa Phân đoạn ảnh

63

1.4 Thuật toán DIANA

33

1.2 Phân đoạn ảnh dựa vào phân cụm dữ liệu

65

1.5 Thuật toán ROCK

33

2. Nhận dạng đối tƣợng và ký tự

71

1.6 Thuật toán Chameleon

80

4. Khai phá dữ liệu

81

4.1 Khai phá dữ liệu bằng Phương pháp tiếp cận.

82

4.2 Khai phá dữ liệu có cấu trúc lớn.

83

4.3 Khai phá dữ liệu trong Cơ sở dữ liệu địa chất.

84

4.4 Tóm tắt

86

KẾT LUẬN ,HƢỚNG PHÁT TRIỂN CỦA ĐỀ TÀI

90

PHỤ LỤC

91


Hàng triệu CSDL đã được sử dụng trong các hoạt động sản xuất, kinh doanh,
quản lý..., trong đó có nhiều CSDL cực lớn cỡ Gigabyte, thậm chí là Terabyte.
Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là cần có những kỹ
thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ kia thành

một tập các đối tượng thực thể hay trừu tượng thành lớp các đối tượng tương

các tri thức có ích. Từ đó, các kỹ thuật khai phá dữ liệu đã trở thành một lĩnh

trong nhiều ứng dụng.

vực thời sự của nền CNTT thế giới hiện nay nói chung và Việt Nam nói riêng.
Khai phá dữ liệu đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực

1.2 Một số ví dụ về phân cụm dữ liệu

kinh doanh và đời sống khác nhau: marketing, tài chính, ngân hàng và bảo
hiểm, khoa học, y tế, an ninh, internet… Rất nhiều tổ chức và công ty lớn trên
thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh
doanh của mình và thu được những lợi ích to lớn.
Các kỹ thuật khai phá dữ liệu thường được chia thành 2 nhóm chính:
- Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả về các tính
chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có.
- Kỹ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đưa ra các dự đoán
dựa vào các suy diễn trên dữ liệu hiện thời.
Bản luận văn này trình bày một số vấn đề về Phân cụm dữ liệu, một
trong những kỹ thuật cơ bản để Khai phá dữ liệu. Đây là hướng nghiên cứu
có triển vọng chỉ ra những sơ lược trong việc hiểu và khai thác CSDL khổng
lồ, khám phá thông tin hữu ích ẩn trong dữ liệu; hiểu được ý nghĩa thực tế của dữ liệu.
Luận văn đƣợc trình bày trong 3 chƣơng và phần phụ lục :

x
 n1

x12  x1d 

x 22  x 2 d 
,
   

x n 2  x nd 

Trong đó :
- n là số lượng các gen
- d là số lượng mẫu hay điều kiện thử
- xij là thước đo biểu diễn mức gen i trong mẫu j


-8-

-9-

Bởi vì các biểu ma trận gốc chứa nhiễu, giá trị sai lệch, hệ thống biến thể,
do đó tiền xử lý là đòi hỏi cần thiết trước khi thực hiện phân cụm.

điều kiện những người có nguy cơ nghèo.
1.2.3 Phân cụm dữ liệu đối với hoạt đông nghiên cứu thị trường
Trong nghiên cứu thị trường, phân cụm dữ liệu được sử dụng để phân
đoạn thị trường và xác định mục tiêu thị trường (Chrisoppher, 1969;
Saunders, 1980, Frank and Green, 1968). Trong phân đoạn thị trường, phân



Dữ liệu biểu diễn gen có thể được phân cụm theo hai cách. Cách thứ nhất
là nhóm các các mẫu gen giống nhau, ví dụ như gom các dòng của ma trận D.
Cách khác là nhóm các mẫu khác nhau trên các hồ sơ tương ứng, ví dụ như

1.1 đưa ra một danh sách giản lược các tác vụ đa dạng của khai phá dữ liệu và

gom các cột của ma trận D.

lượng lớn dữ liệu thông qua phương tiện tự động hay bán tự động (Berry and

1.2.2 Phân cụm dữ liệu phục trong sức khỏe tâm lý
Phân cụm dữ liệu áp dụng trong nhiều lĩnh vực sức khỏe tâm lý, bao
gồm cả việc thúc đẩy và duy trì sức khỏe, cải thiện cho hệ thống chăm sóc sức
khỏe, và công tác phòng chống bệnh tật và người khuyết tật (Clatworthy et

Linoff, 2000). Trong khai phá dữ liệu gián tiếp, không có biến nào được chọn
ra như một biến đích, và mục tiêu là để khám phá ra một vài mối quan hệ
giữa tất cả các biến. Trong khi đó đối với khai phá dữ liệu gián tiếp một vài
biến lại được chọn ra như các biến đích. Phân cụm dữ liệu là khai phá dữ liệu

al., 2005). Trong sự phát triển hệ thống chăm sóc sức khỏe, phân cụm dữ liệu
được sử dụng để xác định các nhóm của người dân mà có thể được hưởng lợi

gián tiếp, bởi vì trong khai phá dữ liệu, ta không đảm bảo chắc chắn chính xác
cụm dữ liệu mà chúng ta đang tìm kiếm, đóng vai trò gì trong việc hình thành
các cụm dữ liệu đó, và nó làm như thế nào.
Vấn đề phân cụm dữ liệu đã được quan tâm một cách rộng rãi, mặc dù

từ các dịch vụ cụ thể (Hodges và Wotring, 2000). Trong thúc đẩy y tế, nhóm


Nhị phân

2. Một số kiểu dữ liệu
Thuật toán phân cụm dữ liệu có nhất rất nhiều liên kết với các loại dữ
liệu. Vì vậy, sự hiểu biết về quy mô, bình thường hoá, và gần nhau là rất quan
trọng trong việc giải thích các kết quả của thuật toán phân cụm dữ liệu. Kiểu
dữ liệu nói đến mức độ lượng tử hóa trong dữ liệu (Jain và Dubes, 1988;

Đối xứng

Bất đối xứng

Hình 2. Biểu đồ các dạng dữ liệu

Anderberg, 1973) - một thuộc tính duy nhất có thể được gõ như nhị phân, rời

Quy mô dữ liệu

rạc, hoặc liên tục. thuộc tính nhị phân có chính xác hai giá trị, như là đúng
hoặc sai. Thuộc tính rời rạc có một số hữu hạn các giá trị có thể, vì thế các
loại nhị phân là một trường hợp đặc biệt của các loại rời rạc (xem hình 2).
Dữ liệu quy mô, mà chỉ ra tầm quan trọng tương đối của các con số,
cũng là một vấn đề quan trọng trong phân cụm dữ liệu. Vậy liệu có thể được
chia thành quy mô định lượng và quy mô định tính. quy mô định lượng bao
gồm quy mô danh nghĩa và quy mô giới hạn; quy mô định tính bao gồm quy

Định lượng

Danh nghĩa

x2

(A, A, A, A, C, D)

x3

(A, A, A, A, D, C)

x4

(B, B, C, C, D, C)

x5

(B, B, D, D, C, D)

loại danh nghĩa cũng là một trường hợp đặc biệt của kiểu rời rạc.

Khoảng

Giá trị

Cho D  x1 , x 2  , x n  là một tập dữ liệu tuyệt đối với khoảng cách
n, được mô tả bởi d thuộc tính Categorical v1, v2,…vd. Đặt DOM(vj) thuộc


-12-

-13-


rằng

DOM v j   A j1 , A j 2 ,  , A jn j với j = 1, 2, … ,d. Gọi Ajl 1  l  n j là trạng
thái thuộc tính Categorical vj đã cho trong tập dữ liệu D. Một bảng Ts của tập
dữ liệu được định nghĩa
Ts = (s1, s2, … , sd),



(2.1)

Nơi sj (1  l  d ) là vecto định nghĩa là s j  A j1 , A j 2 ,, A jn j

.
T

Vì có nhiều trạng thái có thể là các giá trị (hoặc) cho một biến, một
bảng biểu tượng của một tập dữ liệu thường là không duy nhất. Ví dụ, đối với

mỗi cụm là duy nhất lên đến rằng bảng biểu tượng. Ví dụ, đối với bộ dữ liệu
trong bảng 2.1, cho C được một cụm, trong đó C = (x1, x2, x3). Sau đó, nếu sử
dụng các biểu tượng trình bày trong bảng 2 bảng tần số tương ứng cho các
nhóm C được cho trong bảng 2.4. Nhưng nếu sử dụng bảng biểu tượng trình
bày trong Bảng 2.3, sau đó là bảng tần số cho các nhóm C được cho trong
bảng 2.5.
Để có được bộ dữ liệu Categorical D, chúng ta thấy rằng Tf(D) là một
bảng tính toán tần số trên cơ sở dữ liệu toàn bộ thiết lập. Giả sử D là phân
vùng không chồng chéo vào k cụm C1, C2,..., Ck. Sau đó chúng ta có

bộ dữ liệu trong bảng 1, cả hai bảng 2 và Bảng 3 là bảng biểu tượng của nó.


k

f jr D    f jr Ci 

Bảng 2. Một trong những bảng biểu tượng của bộ dữ liệu trong bảng 1

AA A A B B


BBC C C C

D D D D 


xứng. Trong một biến nhị phân đối xứng, hai giá trị có quan trọng không kém
nhau. Một ví dụ là "nam-nữ". Biến nhị phân đối xứng là một biến danh nghĩa.
Trong một biến không đối xứng, một trong những giá trị của nó mang tầm
quan trọng hơn biến khác . Ví dụ, "có" là viết tắt của sự hiện diện của một
thuộc tính nhất định và "không" nghĩa là sự vắng mặt của một thuộc tính nhất
định.
Một vecto nhị phân x với kích thước d được định nghĩa là (x1, x2,…,

Bảng 3 : Bảng biểu tượng của bộ dữ liệu trong bảng 1.

 AB D A B C 


 B AC C C B 


Sau đó, rõ ràng chúng ta có đẳng thức sau :

một trường hợp đặc biệt của dữ liệu nhị phân. Ví dụ phổ biến nhất của dữ liệu
giao dịch là thị trường dữ liệu trong giỏ hàng. Trong một thị trường

d

S11 x, y   x. y   xi yi ,
i 1

_

_

(2.7a)

thiết lập dữ liệu trong giỏ hàng, giao dịch có chứa một tập hợp con của tập

(2.7b)

tổng số mặt hàng mà có thể được mua. Ví dụ, sau đây là hai giao dịch: (táo,
bánh), (táo, món ăn, trứng, cá,). Nói chung, nhiều giao dịch được thực hiện
các mục thưa thớt phân phối. Ví dụ, một khách hàng chỉ có thể mua một số

d

S00 x, y   x . y   1  xi 1  yi ,
i 1

d


 3 3 3 311


0
0
0
0
1
1


 0 011


Bảng5: Bảng tính toán tần số từ bảng biểu tượng trong bảng 3

 3 0 0 311


 0 3 0 011
 3 011


2.3 Dữ liệu giao dịch
Cho một tập hợp các phần tử I = (I1, I2,. . . , Im), một giao dịch là một
tập hợp con của I (Yang et al, 2002b.; Wang et al, 1999a.; Xiao và Dunham,
2001). Một tập dữ liệu giao dịch là một tập hợp các giao dịch, ví dụ
D  t i : t i  I , i  1,2,  n. . Giao dịch có thể được đại diện bởi vector nhị phân,


-17Để thuận tiện hãy cho D*  x1* , x2* ,, xn*  biểu thị tập dữ liệu thô d-chiều.

• Các mô tả của một đối tượng tượng trưng có thể phụ thuộc vào mối
quan hệ hiện tại giữa các đối tượng khác.

Từ đó ma trận dữ liệu là một ma trân n x d được cho bởi

• Các giá trị các biến mất có thể cho thấy tần suất xuất hiện, khả năng
tương đối, mức độ quan trọng của các giá trị, vv.
Dữ liệu Symbolic có thể được tổng hợp từ các dữ liệu khác thường vì
lý do đó là riêng tư. Trong số liệu điều tra dân số, ví dụ, các dữ liệu được tạo
sẵn ở dạng tổng hợp để đảm bảo rằng các nhà phân tích dữ liệu không thể xác
định một cá nhân hay một doanh nghiệp duy nhất thành lập.
2.5 Chuỗi thời gian(Time Series)
Chuỗi thời gian là những hình thức đơn giản nhất của dữ liệu tạm thời.
Chính xác, một chuỗi thời gian là một chuỗi của số thực đại diện cho các phép
đo của một biến thực tế tại các khoảng thời gian bằng (Gunopulos và Das,
2000). Ví dụ, giá cổ phiếu các phong trào, nhiệt độ tại một điểm nào đó, và
khối lượng bán hàng theo thời gian tất cả đo là các chuỗi thời gian.
Một chuỗi thời gian là rời rạc nếu biến được xác định trên một tập hữu
hạn các điểm thời gian. Nhiều nhất của chuỗi thời gian gặp phải trong phân
tích cụm là thời gian rời rạc. Khi một biến được định nghĩa ở tất cả các điểm
trong thời gian, sau đó là chuỗi thời gian là liên tục.
Nói chung, một chuỗi thời gian có thể được coi là một hỗn hợp của bốn
thành phần sau (Kendall và Ord, 1990):
1. Một xu hướng, ví dụ., các phong trào lâu dài;
2. Biến động về xu hướng đều đặn hơn hoặc ít hơn;
3. Một thành phần theo mùa;
4. Một hiệu ứng dư hoặc ngẫu nhiên.
3. Phép biến đổi và chuẩn hóa dữ liệu

xn* 2

 x1*d 

 x2*d 
  
* 
 xnd


(4.1)

3.1 Phép chuẩn hóa dữ liệu
Chuẩn hoá làm cho dữ liệu giảm kích thước đi. Nó có ích để xác định
tiêu chuẩn hoá chỉ số. Sau chuẩn hóa, tất cả các kiến thức về vị trí và quy mô
của các dữ liệu gốc có thể bị mất. Nó là cần thiết để chuẩn hóa các biến trong
trường hợp các biện pháp không giống nhau, chẳng hạn như khoảng cách
Euclide, là nhạy cảm với những khác biệt trong độ lớn hoặc quy mô của các
biến đầu vào (Milligan và Cooper, 1988). Các phương pháp tiếp cận các
chuẩn hoá của các biến bản chất của hai loại: Chuẩn hóa toàn cục và chuẩn
hoá trong cụm.
Chuẩn hóa hóa toàn cục làm chuẩn các biến trên tất cả các yếu tố trong
các tập dữ liệu. Trong vòng-cụm tiêu chuẩn hoá dùng để chỉ tiêu chuẩn hóa
xảy ra trong các cụm biến mỗi ngày. Một số hình thức tiêu chuẩn hoá có thể
được sử dụng trong các chuẩn hóa toàn cục và chuẩn hóa trong phạm vi rất
tốt, nhưng một số hình thức chuẩn hoá chỉ có thể được sử dụng trong chuẩn
hoá toàn cục.
Không thể trực tiếp chuẩn hóa các biến trong các cụm trong phân cụm,
bởi vì các cụm không được biết trước khi chuẩn hóa. Để khắc phục khó khăn
này, khác phương pháp phải được thực hiện. Tổng thể và Klett (1972) đề xuất

trong biểu thức 4.3

toán, dự toán biweight Tukey's, và Andrew ước tính của sóng.

Tên

Lj

Lj

z-score

x *j

 *j

USTD

0

 *j

Maxium

0

max xij*

Mean


(4.3b)

1
2

(4.3c)

Bây giờ chúng ta thảo luận về một số chi tiết các hình thức chung của
tiêu chuẩn hoá và thuộc tính .z-score là một hình thức của tiêu chuẩn hoá
được sử dụng để chuyển biến thể bình thường để tạo điểm chuẩn. Cho một tập
hợp các dữ liệu thô D*, các Z-score công thức chuẩn được định nghĩa là

 

xij  Z1 xij* 

(4.4)

Nơi x ,  có nghĩa là các mẫu và độ lệch chuẩn của các thuộc tính thứ
*
j

nếu n là lẻ


1 *
 xn  x*n  2  nếu n là chẵn
j
2  2 j
2

 *j

x

*
n 1
j
2

1 i  n

*
j

j, tương ứng.
Biến đổi sẽ có một ý nghĩa của 0 và phương sai một trong số 1. Vị trí
quy mô và thông tin của biến gốc đã bị mất. Chuyển đổi này cũng là trình bày
trong (Jain và Dubes, 1988, trang 24). Một điều quan trọng hạn chế của chuẩn
hóa Z1 là nó phải được áp dụng trong tiêu chuẩn toàn cầu và không ở trong
phạm vi-cụm tiêu chuẩn hoá (Milligan và Cooper, 1988). Trong thực tế, hãy
xem xét trường hợp hai cụm tách ra cũng tồn tại trong các dữ liệu. Nếu một
mẫu có vị trí mỗi hai cụm trung tâm, sau đó trong vòng-cụm chuẩn sẽ chuẩn
hóa các mẫu nằm tại cụm trung tâm về không vectơ. Bất kỳ thuật toán
clustering sẽ nhóm hai số không vectơ với nhau, có nghĩa là hai nguyên mẫu

 

xij  Z 2 xij* 

xij*

max( X )

X
và độ lệch chuẩn
max( X )

, nơi X và  X là trung bình và độ lệch chuẩn của biến gốc. Z3 là nhạy

cảm với sự hiện diện của Outliers (Milligan và Cooper, 1988). Nếu một đơn
lớn quan sát trên một biến được trình bày, Z3 sẽ chuẩn hóa các giá trị còn lại
để gần 0. Z3 có vẻ là có ý nghĩa chỉ khi biến này là một biện pháp trong một
phạm vi tỷ lệ (Milligan và Cooper, 1988).
Hai quy chuẩn có liên quan đến việc sử dụng phạm vi của biến đã được
trình bày trong (Milligan và Cooper, 1988):

 

xij  Z 4 xij* 

 

xij  Z 5 xij* 

xij*

(4.7a)

R*j
xij*  min xij*
1i  n


xij  Z 6 xij* 

xij*
n

x

,

(4.8)

*
ij

Một cách tiếp cận rất khác nhau của chuẩn hoá mà bao gồm việc
chuyển đổi các điểm đến đánh giá cao được trình bày trong (Milligan và
Cooper, 1988) và được định nghĩa là

 

 

xij  Z 7 xij*  Rank xij* ,

(4.9)

Nơi Rank(X) là cấp chỉ định cho X
Một biến chuyển bởi Z7 sẽ có một ý nghĩa của
của n  1

Các Z6 chuyển đổi sẽ bình thường hóa tổng giá trị chuyển thành sự

mới được không tương quan và ra lệnh như vậy là người đầu tiên giữ lại vài
phần lớn các biến thể hiện diện trong tất cả các bản gốc biến.

1
. Như vậy, có nghĩa là sẽ được
n

Các PC được định nghĩa như sau. Cho v  v1 , v 2 ,, v d  là một vectơ của

i 1

thống nhất và các chuyển có nghĩa là sẽ có
liên tục trên tất cả các biến.

d ngẫu nhiên biến, nơi ’ là hoạt động transpose. Bước đầu tiên là tìm một
hàm tuyến tính một a1v của các yếu tố của v có tối đa các phương sai, mà a1 là
một vectơ d-chiều a11 , a12 ,  , a1d  do đó,


-22-

-23a1 là vecto đặc trưng đồng vị với giá trị riêng lớn nhất của

d

a1 ' v   a1i vi
i 1


dữ liệu. ORCLUS sử dụng SVD (Kanth et al, 1998) kỹ thuật. Để tìm hiểu tùy
tiện theo định hướng không gian con với phân cụm dữ liệu tốt.

tương ứng với

3.2.2 SVD
SVD là một kỹ thuật mạnh mẽ trong tính toán ma trận và phân tích,

Trong thực tế, ở bước đầu tiên, z1 = aj v có thể tìm thấy bằng cách giải

chẳng hạn như việc giải quyết các hệ thống phương trình tuyến tính và xấp xỉ
ma trận. SVD cũng là một kỹ thuật nổi tiếng chiếu tuyến tính và đã được sử
dụng rộng rãi trong nén dữ liệu và ảo (Andrews và Patterson, 1976a, b). trong
mục này, phương pháp SVD là phương pháp tóm tắt.

các thứ giá trị j lớn nhất λj.
quyết tối ưu hoá vấn đề sau đây:
Maximize var a1v  a1a  1 ,
Nơi var a1v  được tính như sau

Cho D  x1 , x2 ,, xn  là một số dữ liệu được đặt trong một không

 

var a1' v  a1'  a1

Để giải quyết vấn đề tối ưu hóa ở trên, các kỹ thuật của nhân đấu
Lagrange có thể được sử dụng. Cho λ là một số nhân Lagrange. Ta muốn tối
đa hóa


gian d-chiều. Sau đó, D có thể được đại diện bởi một n x n ma trận X là

và a1 là vecto đặc trưng đồng vị.
a1'  a1  a1' a1   ,

Cho   1 , 2 ,, d  là cột của X,
j 

1 n
 xij ,
n  1 i 1

j  1,2,, d ,

và để cho en là một vectơ cột của n chiều dài với tất cả các yếu tố tương
đương với nó. Sau đó, SVD thể hiện X  en  là,
X  en   USV T

(4.11)

trong đó U là một ma trận n × n trực giao, ví dụ, nghĩa là, UTU = I là
ma trận đơn vị. S là một ma trận chéo chứa các giá trị số ít, và V là một ma
trận unita d × d , ví dụ, VHV = I, nơi VH là ma trận chuyển vị liên hợp của V.


-24-

-25Cho D  x1 , x2 ,, xn  là một tập dữ liệu không gian d chiều, và X là

Các cột của ma trận V là vecto đặc trưng của ma trận hiệp phương sai

n
 i 1


j 



 y1 
 
y 
Y   2 ,  1 ,2 ,,d 

 
y 
 d

của C là bất biến theo luân phiên, nghĩa là,



d

d

j 1

j 1

   2j   j


 X T X   T enT X  X T en    T enT en 

Nơi I d d là ma trận đơn vị I d d

 X T X  n T 

nVV T .

Sau đó , từ phương trình (4.14), bộ phận của yj có thể được tính toán

(4.13)

Kể từ khi V là một ma trận trực giao, từ phương trình (4,13), các giá trị
từ có liên quan đến các giá trị riêng bởi
s  n j ,
2
j

for i  j,
for i  j,

j  1,2,d .

Các vecto đặc trưng chiếm các máy tính của X, và các tính năng không
tương quan sẽ được thu được do chuyển đổi Y   X  en  V . PCA chọn các
tính năng với giá trị riêng cao nhất.
3.2.3 Phép biến đổi Karhunen-Loève
Các phép biến đổi Karhunen-Loève (KL) có liên quan với các giải thích
cấu trúc dữ liệu thông qua một số tuyến tính kết hợp của các biến. Giống như

T
j

,


-26-

-27-

 1T   mT 1 
  


Cho

hoặc xˆi (m)  Y (1, m)      ,

x

 x1   Ex1
 

T
T 
 ( x1T , , xnT )  EX  ,  EX n  )       
 xn   Exn 





ij



(4.15)

Với mỗi lựa chọn điều kiện hằng số bij, Ta nhận được giá trị  2 ( m ) . Lựa
chọn tối ưu cho bij là một trong  ( m ) nhỏ nhất. Từ phương trình (4.15) Lựa
2

chọn tối ưu cho bij, là



 2
 (m)  2 Eyij  bij  0,
bij

Mà đã cho

T

T
j



i



n

j  m 1


T

2

d



    x  Ex  x  Ex 

j  m 1



 bij 

2

ij

X

i


X

 j   j j .

Do đó  j là vecto đặc trưng của

 E Tr (X (m)X T (m))

n

( xi  Exi ).

 Ey

i 1 j  m 1

cột của Y

Chú ý rằng X và X là các ma trận ngẫu nhiên, bởi vậy lỗi vuông xấp



T

i

Do đó  2 ( m ) có thể được viết lại như sau :

Nơi Y (m  1), d ) là ma trận n  (m  d ) được hình thành bởi cột cuối m-d


d

 là ma trận hiệp phương sai của X, do đó chúng ta có
 ( X  EX ) ( X  EX )



.Do đó phương trình (4.16) trở

x

thành
 2 ( m) 

d



j  M 1

Từ ma trận hiệp phương sai của X,



x

j

là semidefinite đối diện, nó có


và nút lá thì không có con. Nút trong lưu trữ các tổng đặc trưng cụm(CF) của
các nút con của nó. Một cây (CF) được đặc trưng bởi hai tham số :
- Yếu tố nhánh (Braching Factor – B) : Nhằm xác định tối đa các nút
con của một nút lá trong của cây
- Ngưỡng(Threshold – T) : khoảng cách tối đa giữa bất kỳ một cặp đối
tượng trong nút lá của cây, khoảng cách này còn gọi là đường kính của các
cụm con được lưu tại các nút lá.

Hình 4.10 : Cây CF sử dụng trong BIRCH
Thuật toán BIRCH thực hiện qua các bƣớc cơ bản nhƣ sau :
1. Các đối tượng dữ liệu lần lượt được chèn vào cây C, sau khi chèn hết các
đối tượng thì thu được cây CF khởi tạo. Một đối tượng được chèn vào nút
là gần nhất tạo thành cụm con. Nếu đường kính của cụm con này lớn hơn T
thì nút lá được tách ra. Khi một đối tượng thích hợp được chèn vào nút lá,
tất cả các nút trỏ tới gốc của cây được cập nhật với thông tin cần thiết

Hai tham số này có ảnh hưởng đến kích thước của cây CF. thuật toán BIRCH
thực hiện gồm hai giai đoạn:
Giai đoạn 1 : BIRCH quét tất cả các đối tượng trong CSDL để xây
dựng cây CF khởi tọa, mà được lưu trữ trong bộ nhớ. Trong giai đoạn này ,

2. Nếu cây CF hiện thời không có đủ bộ nhớ trong khi tiến hành xây dựng
một cây CF nhỏ hơn: Kích thước của cây CF được điều khiển bởi tham số

các đối tượng lần lượt được chèn vào nút lá gần nhất của cây CF(nút lá của

cần yêu cầu đọc dữ liệu lại từ đầu nhưng vẫn đảm bảo hiệu chỉnh cây dữ

cây đóng vai trò là cụm con), sau khi chèn xong thì tất cả các nút trong cây
CF được cập nhật thông tin. Nếu đường kính của cụm con sau khi chèn là lớn

Như vậy, có nhiều hơn một điểm đại diện mỗi cụm cho phép CURE

tâm gần nhất. Bước này nhằm để gán nhãn cho các dữ liệu khởi tạo và loại
bỏ các đối tượng ngoại lai

khám phá được các cụm có hình dạng không phải là hình cầu. Việc co lại các
cụm có tác dụng làm giảm tác động của các phần tử ngoại lai. Như vậy, thuật
toán này có khả năng xử lý tốt trong trường hợp có các phần tử ngoại lại và
làm cho hiệu quả với những hình dạng không phải là hình cầu và kích thước

Với cấu trúc cây CF được sử dụng, BIRCH có tốc độ thực hiện PCDL
nhanh và có thể áp dụng đối với tập CDSL lớn, BIRCH cũng có hiệu quả khi
áp dụng với tập dữ liệu tăng trưởng theo thời gian. BIRCH thực hiện tính toán
khá tốt, độ phức tạp tính toán của BIRCH là tuyến tính tỷ lệ với số các đối
tượng, do BIRCH chỉ duyệt toàn bộ dữ liệu một lần với một lần quét thêm tùy

độ rộng biến đổi. Hơn nữa, nó tỷ lệ tốt với CSDL lớn mà không làm giảm
chất lượng phân cụm. Hình 3.14 dưới đây là ví dụ về quá trình xử lý của
CURE

chọn( thực hiện phân cụm lại các nút lá cây của CF), có thể được đo trong
thời gian O(n) với n là số đối tượng dữ liệu. thuật toán này kết hợp các cụm
gần nhau và xây dựng lại cây CF, tuy nhiên mỗi nút trong cây CF có thể chỉ
lưu trữ một số hữu hạn bởi kích thước của nó. BIRCH vẫn có một hạn chê :
thuật toán này có thể không xử lý tốt nếu các cụm không có hình dạng cầu,
bởi vì nó sử dụng khái niệm bán kính hoặc đường kính để kiểm soát ranh giới
các cụm và chất lượng của các cụm được khám phá không được tốt. Nếu
BIRCH sử dụng khoảng cách Eucle, nó thực hiện tốt chỉ với các dữ liệu số,
mặt khác tham số vào T có ảnh hưởng rất lớn tới kích thước tự nhiên của
cụm. Việc ép các đối tượng dữ lieeujlamf cho các đối tượng của cụm có thể là


đối tượng dữ liệu được chứa trong một cụm lớn và chia tách lặp lại, theo phân

bằng nhau : ý tưởng ở đây là phân hoạch mẫu thành p nhóm dữ
liệu bằng nhau, kích thước của mỗi phân hoạch là n’/p(n’ là kích
thước mẫu).

loại giống nhau dựa trên luật, cho đến khi mỗi đối tượng dữ liệu của cụm lớn
được chia tách hết. Hình dang của cụm phân cấp cùng liên quan đế tiếp cận
top-down bắt đầu tại mức đỉnh nút gốc, với tất cả các đối tượng dữ liệu, trong

3. Phân cụm các điểm của mỗi nhóm : Thực hiện PCDL cho các
nhóm cho đến khi mỗi nhóm được phân thành n’/pq(với q>1).
4. Loại bỏ các phần tử ngoại lai : Trước hết, khi các cụm được hình
thành cho đến khi số các cụm giảm xuống một phần so với số các

một cụm, và duyệt xuống các nút lá dưới cùng nơi tất cả các đối tượng dữ
liệu từng cái được chứa trong cụm của chính mình.
Trong mỗi phương pháp của hai phương pháp, có thể số các cụm dẫn
tới các mức khác nhau trong phân cấp bằng cách duyệt lên hoặc xuống cây.

cụm ban đầu. Sau đó, trong trường hợp các phần tử ngoại lai được

Mỗi mức có thể khác nhau số các cụm và tất nhiên kết quả cũng khác nhau.

lấy mẫu cùng với quá trình pha khởi tạo mẫu dữ liệu, thuật toán
sẽ tự động loại bỏ các nhóm nhỏ
5. Phân cụm các cụm không gian : các đối tượng đại diện cho các

Một hạn chế lớn của cách tiếp cận này là các cụm được hòa nhập hoặc phân

1.3 Thuật toán ANGNES
Phương pháp phân hoạch ANGNES là kỹ thuật kiểu tích tụ. ANGNES
bắt đầu ở ngoài với mỗi đối tượng dữ liệu trong các cụm riêng lẻ. Các cụm
được hòa nhập theo một số loại của cơ sở luật, cho đến khi chỉ có một cụm ở
đỉnh của phân cấp, hoặc gặp điều kiện dừng. Hình dạng này của phân cụm

7.
8.

v:= max(q[u])
delete(Q, v)

phân cấp cũng liên quan đến tiếp cận bottom-up bắt đầu ở dưới với các nút lá
trong mỗi cụm riêng lẻ và duyệt lên trên phân cấp tới nút gốc, nơi tìm thấy

9.
w:= merge(u,v)
10. for each x  q[u]  q[v] do {
11.
link[x, w]:=link[x, u]+ link[x, v]
12.
delete(q[x], u); delete(q[x], v)

cụm đơn cuối cùng với tất cả các đối tượng dữ liệu được chứa trong cụm đó.

13.

insert(q[x], w, g(x, w); insert(q[x], w, g(x, w)

14.

4.
5.
6.
7.

N:= nbrlist[i]
for j:=1 to [N]-1 do
for 1:= j+1 to [N]-1 do
link[N[j], N[l]:=link[N[j], N[l]+1

8. }
End
1.6 Thuật toán Chameleon
Phương pháp Chameleon một cách tiếp cận khác trong việc sử dụng mô

Chameleon sử dụng thuật toán phân cụm phân cấp để tìm các cụm xác thực
bằng cách lặp nhiều lần kết hợp hoặc hòa nhập các cụm con. Để xác định các
cặp của nhiều cụm con tương tự, phải tính toán cả hai liên kết và gần nhau của
các cụm, đặc biệt các đặc trưng bên trong của các cụm đang được hòa nhập.
Như vậy, nó không phụ thuộc vào mô hình tĩnh và có thể từ động thích
nghi với đặc trưng bên trong của các cụm đang được hòa nhập. Nó có khả
năng hơn để khám phá các cụm có hình thù bất kỳ có chất lượng cao hơn
CURE và DBSCAN nhưng chi phí xử lý dữ liệu đa chiều phụ thuộc vào O(n2)
thời gian cho n các đối tượng trong trường hợp xấu nhất.
2. Thuật toán phân cụm dữ liệu mờ
Phân cụm dữ liệu mờ (FCM) là phương pháp phân cụm dữ liệu cho
phép mỗi điểm dữ liệu thuộc về hai hoặc nhiều cụm thông qua bậc thành viên.
Ruspini(1969) giới thiệu khái quát khái niệm phân hoạch mờ để mô tả cấu

hình động để xác định các cụm nào được hình thành. Bước đầu tiên của

của thuật toán FCM bao gồm : phân cụm dựa trên xác suất (Kellet, 1993),


-36-

-37-

phân cụm nhiễu mờ ( Dave, 1991), phân cụm dựa trên toán tử Lp,

Chưa có quy tắc nào nhằm lựa chọn tham số m đảm bảo việc phân cụm

Norm(Kerten, 1999) và thuật toán Insensitive Fuzzy C-means( PCM ).

hiệu quả, thông thường chọn m = 2

2.1 Thuật toán FCM
Thuật toán FCM gồm một chuỗi các phép lặp qua lại giữa phương trình
(5) và (6). Như vậy FCM sử dụng phép lặp để tối ưu hàm mục tiêu, dựa trên
đo đạc độ tương tự có trọng số giưa xk và cụm trung tâm Vi, sau mỗi vòng

thuật toán K-means trong trường hợp số đối tượng của tập dữ liệu cần phân
cụm là rất lớn. Tóm lại, thuật toán phân cụm mờ FCM là một mở rộng của
thuật toán K-means nhằm để khám phá ra các cụm chồng lên nhau, tuy nhiên,

lặp, thuật toán tính toán và cập nhật phân tử ujk trong ma trân phân hoạch U.
Phép lặp sẽ dừng khi max ij u

k 1
ij


Các bƣớc thực hiện của thuật toán FCM nhƣ sau:
Input : Số cụm c và tham số mũ m cho hàm mục tiêu J;

 

V(0), thiết lập j = 0;

V  vij ,V ( 0)  R sxc , j  0;

2. Repeat
j:=j+1;
Tính ma trận phân hoạch mờ U(j)

2. Repeat
j:=j+1
Tính ma trận phân hoạch mờ U(j) theo công thức (5)

Cập nhật các trung tâm V ( j )  v1( j ) , v2( j ) ,..., vc( j ) 

Cập nhật các trung tâm V ( j )  v1( j ) , v2( j ) ,..., vc( j ) dựa vào (6) và U(j)



Until u ( j 1)  U ( j )

4.

Trình diễn các cụm kết quả;

F

1
c

3.1 . Thuật toán K – means
K- means là thuật toán phân cụm mà định nghĩa các cụm bởi trung tâm
của các phương tử. Phương pháp này dựa trên độ đo khoảng cách của các đối
tượng dữ liệu trong cụm. Nó được xem như là trung tâm của cụm. Như vậy,
nó cần khởi tạo một tập trung tâm các trung tâm cụm ban đầu, và thông qua
đó nó lặp lại các bước gồm gán mỗi đối tượng tới cụm mà trung tầm gần, và
tính toán tại trung tâm của mỗi cụm trên cơ sở gán mới cho các đối tượng.
Quá trình này dừng khi các trung tâm hội tụ


-38-

-39-

Hình 3.2 : Các thiết lập để xác định danh giới các cụm ban đầu
Trong phương pháp K-means, chọn một giá trị k và sau đó chọn ngẫu
nhiên k trung tâm của các đối tượng dữ liệu. Tính toán khoảng cách giữa đối
tượng dữ liệu trung bình mỗi cùm để tìm kiếm phần tử nào là tương tự và
thêm vào cụm đó. Từ khoảng cách này có thể tính toán trung bình mới của
cụm và lặp lại quá trình cho đến khi mỗi các đối tượng dữ liệu là một bộ phận
của các cụm k

Hình 3.3 Tính toán trọng tâm của các cụm mới
Các bƣớc cơ bản của thuật toán K – means
Input : Số cụm k và các trọng tâm cụm m j  j 1
k


cách D giữa các đối tượng dữ liệu thường được sử dụng là khoảng cách
Euclide vì đây là mô hình khoảng cách nên dễ lấy đạo hàm và xác định các

định trung bình cộng các vecto đối tượng dữ liệu.

cực trị tối thiểu. Hàm tiêu chuẩn và độ đo khoảng cách có thể được xác định
cụ thể hơn tùy ý vào ứng dụng hoặc quan điểm của người dùng.

thay đổi.

Điều kiện dừng :
Lặp lại các bước 2 và 3 cho đến khi các trọng tâm của cụm không
End.


-40-

-41-

K- means biểu diễn các cụm bởi các trọng tâm của các đối tượng trong
cụm đó Thuật toán K-means chi tiết được trình bày :
BEGIN
1. Nhập n đối tượng dữ liệu
2. Nhập k cụm dữ liệu
3. MSE = 
4. For I = 1 to k do mi  X i(i1)*n/k  ; // khởi tạo k trọng tâm
5. Do {
6.

OldMSE = MSE


có khả năng xử lý hiệu quả đối với dữ liệu nhiễu hoặc phần tử ngoại lai,

18. Endfor
19. n[j] = max(n’[j], 1); m[j] = m’[j]/n[j];
20. MSE’=MSE’
21. } while (MSE’
nhất khi hàm tiêu chuẩn đạt giá trị tối thiểu.
PAM tính giá trị Cjmp cho tất cả các đối tượng Oj để làm căn cứ cho

giá thông qua độ phi tương tự trung bình của toàn bộ các đối tượng dữ liệu
trong tập đối tượng dữ liệu ban đầu. Kết quả thực nghiệm chỉ ra rằng, 5 mẫu
dữ liệu có kích thước 40 +2k cho kết quả tốt. Các bước thực hiện của thuật
toán CLARA :

việc hoán chuyển giữa Om và Op.

CLARA (5);

Om : là đối tượng medoid hiện thời cần được thay thế :
Op : là đối tượng medoid mới thay thế cho Om;
Oj : Là đối tượng dữ liệu ( Không phải medoid) có thể được di chuyển

BEGIN
1. For i = 1 to 5 do
2. Lấy một mẫu có 40 + 2k đối tượng dữ liệu ngẫu nhiên từ tập dữ liệu
và áp dụng thuật toán PAM cho mẫu dữ liệu này nhằm để tìm các đối

sang cụm khác;
Oj,2 : Là đối tượng medoid hiện thời gần đối tượng Oj nhất
Các bước thực hiện thuật toán PAM
Input : Tập dữ liệu có n phần tử, số cụm k.
Output : k cụm dữ liệu sao cho chất lượng phân hoạch là tốt nhất.
BEGIN
1. Chọn k đối tượng medoid bất kỳ;

tượng medoid đại diện cho các cụm.



-44-

-45-

mỗi mẫu, và trả lại cụm tốt nhất ở đầu ra, như vậy, CLARA có thể xử lý với

Giả sử P  R3 là một tập tất cả các điểm . Nói chung, các đối tượng ở đây là

tập dữ liệu lớn hơn PAM.

các đối tượng dữ liệu không gian và chúng ta định nghĩa tâm của một đối

3.4 Thuật toán CLARANS
CLARANS cũng sử dụng kiểu k-medoids , nó kết hợp thuật toán PAM
với chiến lược tìm kiếm kinh nghiệm mới. Ý tưởng cơ bản của CLARANS là
không xem xét tất cả các khả năng có thể thay thế các đối tượng tâm medoids

tượng chính là trung bình cộng toán học của tất cả các đỉnh hay còn gọi là

bới một đối tượng khác, nó ngay lập tức thay thế các đối tượng tâm này nếu
việc thay thế này có tác động tốt đến chất lượng phân cụm chứ không cần xác
định cách thay thế tối ưu nhất.
CLARANS lấy ngẫu nhiên một đối tượng của k đối tượng medoid

đây là khoảng cách Eucliean : dist : PxP  R0

trong tâm cụm và cố gắng thay thế nó với một đối tượng chọn ngẫu nhiên
trong (n-k) đối tượng còn lại. Cụm thu được sau khi thay thế đối tượng trung


tâm

medoid

như

sau

:

medoid

: OM

chất lượng một phân hoạch được định nghĩa như sau : total_distance : C0  R0

Input : O,k, dist, numlocal và maxneighbor;’

CLARANS không thích hợp với tập dữ liệu lớn bởi vì nó lấy phần nhỏ
của toàn bộ tập dữ liệu và phần này được chọn để đại diện toàn bộ tập dữ liệu
và thực hiện sau đó. CLARANS không bị giới hạn không gian tìm kiếm như
đối với CLARA, và trong cùng một lượng thời gian thì chất lượng của các

Output : k cụm dữ liệu;
CLARANS(int k, function dist, int numlocal, int maxneighbor)

liệu sử dụng trong thuật toán CLARANS là các khối đa diện. Mỗi đối tượng
được diễn tả bằng một tập các cạnh, mỗi cạnh được xác định bằng hai điểm.



Thuật toán chi tiết CLARANS :

BEGIN
For (i = 1 ; 1

thuộc: các vấn đề mã hóa và chức năng đánh giá (ví dụ, khách quan chức

clustering đến tự động phân nhóm vấn đề. Clustering là phù hợp với phân
nhóm dữ liệu với nhỏ gọn cụm hình cầu, và số cụm có thể được kiểm soát

năng). Ngay cả đối với cùng một vấn đề, có thể sử dụng mã hóa khác nhau.

gián tiếp bởi một tham số w. Thuật toán sẽ sản xuất một số lượng lớn các cụm

Ví dụ, trong các k-có nghĩa là thuật toán di truyền, Krishna và Narasimha
(1999) làm việc string-of-group-số mã hóa, trong khi Maulik và
Bandyopadhyay (2000) được mã hóa các chuỗi sao cho mỗi chuỗi là một

nhỏ gọn với một giá trị nhỏ của w và nó sẽ sản xuất một số lượng nhỏ hơn của
cụm lỏng hơn với một giá trị lớn của w. A di truyền phân nhóm dựa trên thuật
toán nhằm tìm ra các cụm nonspherical đã được đề xuất bởi Tseng và Yang
(2000).

Thông thường, chỉ có hai thành phần chính của GAS được vấn đề phụ

chuỗi các thực số đại diện cho các trung tâm cụm.
Trong GAS, các tham số của không gian tìm kiếm được mã hoá trong
các hình thức gọi là chuỗi nhiễm sắc thể. AGA maintains dân (set) của N
chuỗi mã hoá cho một số dân số cố định kích thước N và tiến hóa qua các thế
hệ. Trong mỗi thế hệ, ba nhà khai thác di truyền, nghĩa là, tự nhiên, lựa chọn,
xuyên chéo , và đột biến, được áp dụng cho dân số hiện nay để sản xuất một
số dân mới. Mỗi chuỗi trong dân số liên kết với một giá trị thể dục tùy thuộc
vào giá trị của hàm mục tiêu. Dựa trên nguyên tắc sống còn của các lắp rắp ,


min   x  zi

PDS D

2

i 1 xCi

Nơi k là số lượng cụm , . được hiểu là Euclidean chuẩn tắc, và zi là
tâm của cụm Ci
Zi 

1
Ci

x

xCi

Với i = 1, 2,…k

Thuật toán J-mean :
Bước 1 (khởi) Hãy để PD = (C1, C2,. . . , Ck) là một phân vùng ban đầu của
D, zi là trọng tâm của cụm Ci, và fopt được mục tiêu hiện chức năng giá trị;
S2 (điểm chiếm đóng) Tìm điểm trống, nghĩa là, điểm trong D không trùng
với một cụm trọng tâm trong một dung sai nhỏ;

S3 (Bước khu phố) Tìm phân vùng tốt nhất PD và mục tiêu tương ứngchức
năng giá trị f  trong các khu phố nhảy của giải pháp hiện tại PD:
S31 (khai phá láng giềng) Đối với mỗi j (j = 1, 2,..., N), lặp lại sau bước