Bài giảng Khai phá dữ liệu: Bài 5

Bài 5: Gom cụm (clustering)

PhânPhân ttííchch bbằằngng gomgom ccụụmm

không tương

tương ttựự

tương ttựự vvàà không

trong phânphân ttííchch bbằằngng gomgom ccụụmm

phương phpháápp gomgom ccụụmm chchíínhnh phương phpháápp phânphân hohoạạchch phương phpháápp phânphân ccấấpp

(cid:1)(cid:1) PhânPhân ttííchch bbằằngng gomgom ccụụmm llàà ggìì ?? (cid:1)(cid:1) ĐĐốốii tưtượợngng tương (cid:1)(cid:1) CCáácc loloạạii ddữữ liliệệuu trong (cid:1)(cid:1) CCáácc phương (cid:1)(cid:1) CCáácc phương (cid:1)(cid:1) CCáácc phương (cid:1)(cid:1) PhânPhân ttííchch Outlier Outlier (cid:1)(cid:1) TTóómm ttắắtt

PhânPhân ttííchch bbằằngng gomgom ccụụmm llàà ggìì ??

(cid:1)(cid:1) GomGom ccụụmm:: gom các đối tượng dữ liệu

o Tương tự với một đối tượng khác trong

o Không tương tự với các đối tượng trong

cùng cụm

oo MMụụcc tiêutiêu ccủủaa gomgom ccụụmm:: để gom tập

các đối tượng thành các nhóm

các cụm khác

a gom ng tiêu biểểu cu củủa gom

CCáác c ứứng dng dụụng tiêu bi ccụụmm

(cid:1)(cid:1) MMộột công c phân bốố ddữữ liliệệu u phân b

(cid:1)(cid:1) LLààm bưm bướớc tic tiềền xn xửử lý cho c

t công cụụ đ độộc lc lậập đp đểể xem x xem xéét t

CCáácc ứứngng ddụụngng ccủủaa gomgom ccụụmm

(cid:1)(cid:1) TiTiếếpp ththịị:: khám phá các nhóm khác hàng

phân biệt trong CSDL mua hàng

(cid:1)(cid:1) SSửử ddụụngng đđấấtt:: nhận dạng các vùng đất sử dụng giống nhau khi khảo sát CSDL quả đất (cid:1)(cid:1) BBảảoo hihiểểmm:: nhận dạng các nhóm công ty có

chính sách bảo hiểm mô tô với chi phí đền bù trung bình cao

(cid:1)(cid:1) HoHoạạchch đđịịnhnh ththàànhnh phphốố:: nhận dạng các

nhóm nhà cửa theo loại nhà, giá trị và vị trí địa lý.

ThThếế nnààoo llàà gomgom ccụụmm ttốốtt

(cid:1) Một phương pháp tốt sẽ tạo ra các cụm có chất

lượng cao với: o Tương tự cao cho trong lớp (intra o Tương tự thấp giữa các lớp (inter

intra--class) class) class) inter--class)

(cid:1) Chất lượng của kết quả gom cụm phụ thuộc vào:

o độ đo tương tự sử dụng o Cài đặt độ đo tương tự

hidden patterns)

(cid:1) Chất lượng của phương pháp gom cụm cũng được đo bởi khả năng phát hiện vài hay tất cả các mẫu bị che ( hidden

lý cho cáác c thuthuậật tot toáán khn kháác c

CCáácc yêuyêu ccầầuu ccủủaa gomgom ccụụmm trong trong KPDL (1) KPDL (1)

(scalability) thay đđổổii quyquy mômô (scalability)

(cid:1)(cid:1) CCóó ththểể thay (cid:1)(cid:1) KhKhảả năngnăng llààmm viviệệcc ccáácc loloạạii thuthuộộcc ttíínhnh khkháácc

nhaunhau..

(cid:1)(cid:1) KhKháámm phpháá ccáácc ccụụmm ccóó hhììnhnh ddáángng bbấấtt kkỳỳ

(cid:1)(cid:1) CCáácc yêuyêu ccầầuu ttốốii thithiềềuu chocho tri tri ththứứcc llĩĩnhnh vvựựcc

nhnhằằmm xxáácc đđịịnhnh ccáácc thamtham bibiếếnn nhnhậậpp

KPDL trong KPDL

CCáácc nhunhu ccầầuu gomgom ccụụmm trong (2)(2)

(cid:1)(cid:1) Không

(cid:1)(cid:1) KhKhảả năng outliers outliers Không nhnhạạyy ccảảmm vvớớii thưthư ttựự ccáácc bbảảnn ghighi nhnhậậpp vvààoo

(cid:1)(cid:1) CCóó ssốố chichiềềuu caocao (cid:1)(cid:1) HHợợpp ttáácc vvớớii ccáácc rrààngng bubuộộcc do do

năng llààmm viviệệcc vvớớii nhinhiềềuu vvàà

(cid:1)(cid:1) CCóó ththểể didiễễnn ddịịchch vvàà khkhảả ddụụngng

tương ttựự

ngưngườờii ddùùngng chchỉỉ đđịịnhnh

(cid:1) Không có định nghĩa duy nhất về sự tương tự và

bất tương tự giữa các đối tượng dữ liệu

(cid:1) Định nghĩa về tương tự và bất tượng tự giữa các

đối tượng tùy thuộc vào o Loại dữ liệu khảo sát o Loại tương tự cần thiết

TTươngương ttựự vvàà bbấấtt tương gigiữữaa haihai đđốốii tưtượợngng (1)(1)

(cid:1) Tương tự /Bất tượng tự giữa đối tượng thường được

biểu diễn qua độ đo khoảng cách d(x,y)

(cid:1) Lý tưởng, mọi độ đo khoảng cách phải là một và phải

thỏa các điều kiện sau:

SSựự tương tương ttựự vvàà bbấấtt tương tương ttựự (2)(2)

= =

‡

1. 2. 3. 4.

) ) ) )

) )

)

( , yxd , ( yxd ( , yxd ( , zxd

0 iff 0 x ( , xyd , ( yxd

( zyd

trong phânphân ttííchch

LoLoạạii ddữữ liliệệuu trong ccụụmm

(cid:1)(cid:1) CCáácc bibiếếnn khokhoảảngng ttỉỉ llệệ (cid:1)(cid:1) BiBiếếnn nhnhịị phân phân (cid:1)(cid:1) CCáácc bibiếếnn đđịịnhnh danh (cid:1)(cid:1) CCáácc bibiếếnn ccóó kikiểểuu hhổổnn hhợợpp (cid:1)(cid:1) CCáácc kikiểểuu ddữữ liliệệuu phphứứcc ttạạpp

danh, , ththứứ ttựự, , ttỉỉ llệệ

CCáácc bibiếếnn trtrịị khokhoảảngng (1)(1)

(cid:1)(cid:1) CCáácc đđộộ đođo liênliên ttụụcc ccủủaa ccáácc thang

(cid:1) Ví dụ: trọng lượng, chiều cao, tuổi (cid:1) Đơn vị đo có thể ảnh hưởng đến phân

thang đođo tuytuyếếnn ttíínhnh, , thôthô

(cid:1) Để tránh sự phụ thuộc vào đơn vị đo,

tích cụm

cần chuẩn hoá dữ liệu

CCáácc bibiếếnn thang

thang đođo theo

theo khokhoảảngng (2)(2)

Chuẩn hoá các độ đo :

• Tính sai biệt tuyệt đối trung bình

++ ...

x 2

mx nf

(|1 mxn

++ ...

x 2

x nf

với

và

= (xn m

- - -

z if

• Tính độ đo chuẩn ((zz--score score)) mx if s

CCáácc bibiếếnn thang

thang đoo khokhoảảngng (3)(3)

(cid:1) Một nhóm các độ đo khoảng cách phổ

q )|

q |

),( jid

x i 1

j 1

x i

x i p

j p

i = (xi1, xi2, …, xip) vvàà j = (xj1, xj2, …, xjp) llàà với ccáácc đđốốii tưtượợngng ddữữ liliệệuu p-chiều và q llàà ssốố nguên nguên dương dương

CCáácc bibiếếnn thang

thang đođo khokhoảảngng (4)(4)

(cid:1) Nếu q = 1, đđộộ đođo khokhoảảngng ccááchch llàà

- - - biến cho biến tỉ lệ theo khoảng là Minkowski.. khoảng cách Minkowski + ++ ...

++ ...

i 1

j (cid:1) Nếu q = 2, đđộộ đođo khokhoảảngng ccááchch llàà khokhoảảngng

Euclidean ccááchch Euclidean

- - - Manhattan Manhattan id j ),( x |

jid ),(

2 |

++ ...

2 )|

x i 1

j 1

x i 2

j 2

x i p

j p

- - -

CCáácc bibiếếnn nhnhịị phânphân (1)(1)

(cid:1) Biến nhị phân chỉ có hai trạng thái là 0 hay 1

(cid:1) Bảng contingency table

contingency table cho dữ liệu nhị phân:

Object j 0 b

1 a

sum + ba + dc

Object i

d +

c +

sum

dbca

CCáácc bibiếếnn nhnhịị phânphân (2)(2)

(cid:1)(cid:1) HHệệ ssốố Jaccard

coefficient (tương tự Jaccard coefficient

=),( jid

,( id

+ cb +++ dcba + b c ++ b a

không bất biến, nếu biến nhị phân là bất đối xứng):

CCáácc bibiếếnn nhnhịị phânphân (3)(3)

VVíí ddụụ: sự bất tương tự giữa các biến nhị

Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4 P Jack M P Mary F N Jim M

N N N

Y Y Y

N P N

(cid:1) Tám thuộc tính trong đó

o gender là thuộc tính đối xứng o Các thuộc tính còn lại là bất đối xứng nhị

phân

phân: • Bảng record bệnh nhân N N P

CCáácc bibiếếnn nhnhịị phânphân (4)(4)

(cid:1) Gọi các trị YY và PP được gán trị 1, và trị NN

được gán trị 0

(cid:1) Tính khoảng cách giữa các bệnh nhân dựa vào

các bất đối xứng dùng hệ số Jaccard:

(

jack

mary

)

33.0

67.0

(

jack

jim

)

75.0

jimd (

mary

)

+ 10 ++ 102 + 11 ++ 111 + 21 ++ 211

(cid:1) Mở rộng biến nhị phân để biến có thể nhận nhiều hơn hai trạng thái chẳng hạn đỏ, vàng, xanh, lục

(cid:1) Phương pháp 1: đđốốii ssáánhnh đơnđơn gigiảảnn

oo m: m: # lần đối sáng,, p: p: ttổổngng ssốố bibiếếnn

CCáácc bibiếếnn đđịịnhnh danh (nominal variables) danh (nominal variables)

,( id

mp p

(cid:1) Phương pháp 2: ddùùngng mmộộtt ssốố lưlượợngng llớớnn ccáácc bibiếếnn nhnhịị phânphân

o Tạo biến nhị phân mới cho từng trang thái định danh của

CCáácc bibiếếnn ththứứ ttựự

(cid:1) Các biến thứ tự có thể là liên tục hay rời rạc (cid:1) Thứ tự của các trị là quan trọng, ví dụ hạng (cid:1) Có thể xử lý như tỷ lệ khoảng

(cid:1) Thay thế xif bởi hạng của chúng o Ánh xạ phạm vi của từng biến vào đoạn [0, 1] bằng cách thay

thế đối tượng thứ i trong biến thứ f bởi

r ˛

,1 {

...,

}

o Tính sự khác nhau dùng các phương pháp cho biến tỉ lệ

theo khoảng

r M

- -

CCáácc bibiếếnn ttỉỉ llệệ

(cid:1)(cid:1) ĐĐộộ đođo dương

dương trêntrên thang thang phi phi tuytuyếếnn,

(cid:1)(cid:1) CCáácc phương

(cid:1) xử lý chúng như các biến thang đo khoảng

— không phải là lựa chọn tốt ! (why?)

(cid:1) áp dụng biến đổi logarithmic yifyif = = log(xif log(xif)) (cid:1) xử lý chúng như dữ liệu thứ tự liên tục và xử lý chúng theo hạng như thang đo khoảng

CCáácc bibiếếnn ccóó kikiểểuu hhỗỗnn hhợợpp (1)(1)

(cid:1) CSDL Có thể chứa cả sáu loại biến (cid:1) Có thể dùng công thức được gán trọng để kết hợp các

hiệu quả:

)

xấp xỉ thang đo mũ (cid:1) Ví dụ AeAeBtBt hay AeAe--BtBt phương phpháápp::

p f

id ,(

)

( ij )

d = 1 p f

( ij d 1

d ( f ij

S S

)

(

missing,

d or

otherwise

= δ (f)

CCáácc bibiếếnn ccóó kikiểểuu hhỗỗnn hhợợpp (2)(2)

với

(cid:1) Nếu f là nhị phân hay định danh:

(

)

(

)

if 0

x jf

;

otherwise

(cid:1) Nếu f dựa trên khoảng: dùng khoảng cách được chuẩn hoá

ĐĐóóngng ggóópp ccủủaa bibiếếnn f vvààoo khokhoảảngng ccááchch d(i,j)::

zif

(cid:1) Nếu f là thứ tự hay tỉ số được tỉ lệ theo: (cid:1) Tính hạng rif và o xử lý zif theo tỉ lệ khoảng

r M

- -

CCáácc kikiểểuu ddữữ liliệệuu phphứứcc ttạạpp

(cid:1) Tất cả các đối tượng được xem xét a trong KPDL là không quan hệ => Loại dữ liệu phức tạp o Ví dụ về loại dữ liệu như vậy là dữ liệu không

gian, dữ liệu đa phương tiện, dữ liệu di truyền, dữ liệu văn bản, dữ liệu chuỗi thời gian, dữ liệu văn bản và dữ liệu được thu gom từ World-Wide Web

(cid:1) Các độ đo tương tự và bất tương tự thường

hoàn toàn khác nhau ứng với các loại dữ liệu trên

phương phpháápp gomgom ccụụmm

CCáácc phương (clustering) chchíínhnh yyếếuu (clustering)

(cid:1) Các phương pháp dựa trên phân hoạch (cid:1) Các phương pháp phân cấp (cid:1)(cid:1) CCáácc phương

(cid:1)(cid:1) CCáácc phương

CCáácc phương

phương phpháápp phânphân hohoạạchch

(cid:1)(cid:1) Phương

phương phpháápp ddựựaa trêntrên mmậậtt đđộộ based methods GridGrid--based methods phương phpháápp ddựựaa trêntrên mômô hhììnhnh (gom cụm khái niệm, mạng neural )

phân hohoạạchch:: tạo một phân

Phương phpháápp phân hoạch của CSDL D chứa nn đối tượng thành tập gồm k cụm sao cho: o Mỗi cụm chứa ít nhất là một đối tượng o Mỗi đối tượng thuộc về đúng một cụm (cid:1) Cho k, tìm một phân hoạch có kk ccụụmm nhằm tối ưu tiểu chuẩn phân hoạch được chọn

TiêuTiêu chuchuẩẩnn suysuy đođoáánn chchấấtt lưlượợngng phânphân hohoạạchch

(cid:1)(cid:1) TTốốii ưuưu totoàànn ccụụcc: liệt kê theo lối vét cạn tất

(cid:1)(cid:1) CCáácc phương

oo kk--meansmeans (MacQueen’67): mỗi cụm được centroid) đại diện bằng tâm của cụm (centroid

oo kk--medoids

cả các phân hoạch phương phpháápp:

Phương phpháápp gomgom ccụụmm kk-- Phương means(1) means(1)

(cid:1)(cid:1)

ĐĐầầuu vvààoo ccủủaa thuthuậậtt totoáánn: số k cụm k, và CSDL có n đối tượng ThuThuậậtt totoáánn ggồồmm 4 4 bưbướớcc:

centroid (trung

Phân hoạch đối tượng thành k tập con/cụm khác rỗng Tính các điểm hạt giống làm centroid bình của các đối tượng của cụm) cho từng cụm trong cụm hiện hành

3. Gán từng đối tượng vào cụm có centroid gần

nhất

4. Quay về bước 2, chất dứt khi không còn phép

gán mới

Phương phpháápp gomgom ccụụmm kk-- Phương means(2) means(2)

medoids (Kaufman & Rousseeuw’87): mỗi cụm được đại diện bằng một trong các medoid) đối tượng của cụm (medoid

2. Gán hoặc gán lại từng đối tượng vào

ThuThuậậtt totoáánn khkháácc ccũũngng ggồồmm 4 4 bưbướớcc : 1. Chọn bất kỳ k đối tượng làm các tâm (centroids) ban đầu

3. Cập nhật centroids 4. Quay về bước 2, dừng khi không còn

cụm với khoảng cách gần nhất

phép gán mới

phương phpháápp gomgom

ĐiĐiểểmm mmạạnhnh ccủủaa phương ccụụmm kk--meansmeans

Ví dụ: phương pháp gom cụm k- means

(cid:1)(cid:1) Scalable

tương đđốốii: : trong trong khikhi xxửử lýlý ccáácc

Scalable tương ttậậpp ddữữ liliệệuu llớớnn (cid:1)(cid:1) HiHiệệuu susuấấtt tương

(cid:1) Thường kết thúc ở điểm tối ưu cục bộ; có thể tìm được tối ưu toàn cục dùng các kỹ thuật như thuật toán di truyền

phương phpháápp gomgom

ĐiĐiểểmm yyếếuu ccủủaa phương ccụụmm kk--meansmeans

(cid:1)(cid:1) CCóó ththểể áápp ddụụngng chchỉỉ khikhi xxáácc đđịịnhnh đưđượợcc trtrịị

tương đđốốii: O(tkn), với n là số đối tượng, k là số cụm, và t là số lần lặp. Thông thường k, t << n.

trung bbììnhnh ccủủaa ccáácc đđốốii tưtượợngng trung (cid:1)(cid:1) CCầầnn chchỉỉ đđịịnhnh trtrứứcc k, số các cụm (cid:1)(cid:1) Không (cid:1)(cid:1) Không

Không ththểể xxửử lýlý ddữữ liliệệuu chuchuỗỗii vvàà ooutliers Không phphùù hhợợpp để khám phá các cụm với dạng khong lồi hay cụm có kích thước khác nhau.

phương phpháápp

CCáácc bibiếếnn đđổổii ccủủaa phương means(1) gomgom ccụụmm kk--means(1)

means khkháácc nhaunhau ởở: :

(cid:1)(cid:1) VVààii bibiếếnn ththểể ccủủaa kk--means (cid:1) Chọn k centroids ban đầu o Tính toán sự bất tương tự o Các chiến lược tính centroids cụm

(cid:1) Xử lý dữ liệu phân nhóm: kk--modesmodes (Huang’98) o Thay trị trung bình của cluster bằng modesmodes o Dùng các độ đo bất tương tự mới cho các đối tượng phân

nhóm

o Dùng phương pháo dựa trên tần số để cập nhật modes

của các cụm

(cid:1) Một sự kết hợp giữa dữ liệu phân lớp và dữ liệu số :

phương pháp kk--prototype. prototype.

Phương phpháápp gomgom ccụụmm KK-- Phương medoids medoids

(cid:1)(cid:1) ĐĐầầuu vvààoo ccủủaa thuthuậậtt totoáánn: số cụm k và

(cid:1)(cid:1)

ban medoids ban

đđầầuu (các đối tượng đại diện)

2. Gán từng đối tượng còn lại vào cụm có medoid

gần nhất

3. Chọn nonmedoid và thay một trong các

medoids bằng nó nếu nó cải thiện chất lượng cụm

4. Quay về bước 2, dừng khi không còn phép gán

mới.

PhPhươngương phpháápp phânphân ccấấpp

(cid:1)(cid:1) PhPhươngương phpháápp phânphân ccấấpp:: tạo phân cấp cụm, chứ không phải là một phân hoạch đơn thuần các đối tượng

(cid:1) Không cần dữ liệu nhập là số cụm kk

(cid:1) Dùng ma ma trtrậậnn làm tiêu chuẩn gom cụm

(cid:1)(cid:1) CCóó ththểể ccóó điđiềềuu kikiệệnn kkếếtt ththúúcc (ví dụ số cụm)

CSDL có n đối tượng ThuThuậậtt totoáánn ggồồmm 4 4 bưbướớcc : 1. Chọn bất kỳ k đối tượng làm medoids

CCâyây ccáácc ccụụmm

(cid:1) Phân cấp cụm thường tạo cây các cụm

hay còn được gọi là dendrogram dendrogram

o Các lá của cây biểu diễn các đối tượng

o Các nút trong của cây biểu diễn các cụm

phương phpháápp ttạạoo kikiếếnn trtrúúcc

HaiHai loloạạii phương ccụụmm (1)(1)

Hai loHai loạại ki kỹỹ thuthuậật gom c

t gom cụụm phân l

m phân lớớp :p : agglomerative (từ dưới lên):

•• GGộộpp--agglomerative

o Đưa từng đối tượng vào cluster riêng của nó (a

singleton)

o Trộn ở mỗi bước hai cụm tương tự nhất cho

đến khi chỉ còn một cụm hay thỏa điều kiện kết thúc

divisive (từ trên xuống):

oo PhânPhân chiachia --divisive

o Bắt đầu bằng một cụm lớn chứa tất cả đối

tượng.

o Phân chia cụm phân biệt nhất thành các cụm nhỏ hơn và xử lý cho đến khi co n cụm hay thỏa điều kiện kết thúc

i phương phááp tp tạạo kio kiếến n

c phân cấấp cp cụụm (2)m (2)

Hai loạại phương ph Hai lo trtrúúc phân c

Step 1

Step 2 Step 3 Step 4

Step 0

riêng lẻ

GGộộpp--agglomerative agglomerative

a b

a b c d e

c d e

d e

a b c d e

PhPhânân chiachia-- divisive divisive

Step 3

Step 2 Step 1 Step 0

Step 4

trong CCáácc khokhoảảngng ccááchch trong

(cid:1) Thường có 3 cách được dùng để định nghĩa khoảng cách

giữa các cụm

oo Phương

Phương phpháápp liênliên kkếếtt đơnđơn(làng giềng gần nhất):

jid ),(

min

{ yxd ,(

} )

CyCx , i j

Phương phpháápp liênliên kkếếtt hohoàànn totoàànn(láng giềng xa oo Phương nhất ): { yxd ,(

jid ),(

max

} )

˛ ˛

CyCx , i

oo Phương

trung bbììnhnh (trung bình

Phương phpháápp liênliên kkếếtt trung cặp nhóm không có trọng ):

j ),(

avg

{ yxd ,(

} )

˛ ˛

CyCx , i

˛ ˛

SSứứcc mmạạnhnh ccủủaa ccáácc phương phương phpháápp phânphân ccấấpp

(cid:1)(cid:1) KhKhááii niniệệmm đơnđơn gigiảảnn (cid:1)(cid:1) LýLý thuy thuyếếtt ttốốtt (cid:1)(cid:1) KhiKhi ccụụmm đưđượợcc trtrộộnn/tácht, quyết

định là vĩnh cửu => => ssốố ccáácc phưong áánn khkháácc nhaunhau ccầầnn đưđượợcc phưong xemxem xxéétt bbịị rrúútt gigiảảmm

ĐiĐiểểmm yyếếuu ccủủaa phương

phương phpháápp phânphân ccấấpp

(cid:1)(cid:1) TrTrộộn/tn/tááchch ccáácc ccụụmm llàà vvĩĩnhnh ccửửuu => => không ththểể khkhắắcc

(cid:1)(cid:1) CCáácc phương

ccáácc quyquyếếtt đđịịnhnh saisai llàà không phphụụcc vvềề sausau (cid:1)(cid:1) CCáácc phương phương phpháápp phânphân chiachia llàà ccầầnn ththờờii giangian ttíínhnh totoáánn phương phpháápp llàà không scalable không scalable chocho ccáácc ttậậpp ddữữ liliệệuu llớớnn

Outlier (1) PhânPhân ttííchch Outlier (1)

Outliers (cid:1)(cid:1) Outliers o Là các đối tương bất tương tự với phần dữ liệu

còn lại

o Có thể gây ra việc đo đạc hay lỗi thực hiện, hay o Là kết quả của biến đổi dữ liệu kế thừa Rất nhiều

thuật toán KTDL cố gắng o Giảm ảnh hưởng của outliers o Giảm outliers

Outlier (2) PhânPhân ttííchch Outlier (2) (cid:1) Cực tiểu hóa ảnh hưởng của outliers

(cid:1)(cid:1) CCáácc ứứngng ddụụngng ccủủaa khai

o Phát hiện phạm tội (Fraud detection) o Tiếp thị o Xử lý y khoa

và/hay khử đi các the outliers có thể gây ra mất mát thông tin outlier (cid:1) Có thể quan tâm đến khai thác outlier miningmining outlier khai ththáácc outlier

TTổổngng kkếếtt (1)(1)

(cid:1)(cid:1) PhPhânân ttííchch gomgom ccụụmm ccáácc đôiđôi tưtượợngng ddựựaa

(cid:1)(cid:1) PhPhânân ttííchch gomgom ccụụmm ccóó phphạạmm vi vi ứứngng ddụụngng

trêntrên ssựự tương tương ttựự

(cid:1)(cid:1) CCóó ththểể ttíínhnh đđộộ đođo tương

(cid:1)(cid:1) ViViệệcc llựựaa chchọọnn đđộộ đođo tương

to to llớớnn tương ttựự chocho nhinhiềềuu loloạạii ddữữ liliệệuu khkháácc nhau nhau. .

tương ttựự ttùùyy thuthuộộcc tương ttựự vvààoo ddữữ liliệệuu đưđượợcc ddùùngng vvàà loloạạii tương ccầầnn ttììmm

TTổổngng kkếếtt (2)(2)

(cid:1)(cid:1) CCóó ththểể chiachia ccáácc thuthuậậtt totoáánn gomgom ccụụmm ththàànhnh

(cid:1)(cid:1) CCóó nhinhiềềuu vvấấnn đđềề nghiên

ccáácc loloạạii partitioning methods, partitioning methods, phương phpháápp phânphân ccấấpp oo CCáácc phương phương phpháápp ddựựaa trêntrên mmậậtt đđộộ, , oo CCáácc phương phương phpháápp ddựựaa trêntrên lưlướớii oo CCáácc phương phương phpháápp ddựựaa trêntrên mômô hhììnhnh oo CCáácc phương nghiên ccứứuu vvềề phânphân ttííchch gomgom ccụụmm