ĐẠI HỌC THÁI NGUYÊN 
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

TRẦN HÀ PHƯƠNG

PHÂN CỤM ĐỒ THỊ DỮ LIỆU VÀ ỨNG DỤNG  
 
 
 

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN - 2016


ĐẠI HỌC THÁI NGUYÊN 
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

TRẦN HÀ PHƯƠNG

PHÂN CỤM ĐỒ THỊ DỮ LIỆU VÀ ỨNG DỤNG  
 

Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: PGS. TS. ĐOÀN VĂN BAN

THÁI NGUYÊN - 2016


 


 

ii

LỜI CẢM ƠN
 

Sau một  thời gian  nghiên  cứu  và làm việc nghiêm  túc,  được  sự  động  viên, 
giúp đỡ và hướng dẫn tận tình của Thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban, 
luận văn với đề tài “Phân cụm đồ thị dữ liệu và ứng dụng”đã hoàn thành. 
Tôi xin bày tỏ lòng biết ơn sâu sắc đến: 
Thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban đã tận tình chỉ dẫn, giúp đỡ 
tôi hoàn thành luận văn này. 
Khoa sau Đại học Trường Đại học công nghệ thông tin và truyền thông đã 
giúp đỡ tôi trong quá trình học tập cũng như thực hiện luận văn. 
Tôi  xin  chân  thành  cảm  ơn  bạn  bè,  đồng  nghiệp  và  gia  đình  đã  động  viên, 
khích lệ, tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập, thực hiện và hoàn 
thành luận văn này. 
Thái Nguyên, ngày 16 tháng 6 năm 2016
Tác giả luận văn

Trần Hà Phương
 
 

 

1.3.2  Phương pháp phân cụm phân cấp .......................................................... 12 
1.3.3  Phương pháp phân cụm dựa trên mật độ ............................................... 13 
1.3.4  Phương pháp phân cụm dựa trên lưới ................................................... 14 
1.3.5  Phương pháp phân cụm dựa trên mô hình ............................................. 15 
1.3.6  Phương pháp phân cụm dữ liệu có liên kết ............................................ 15 
1.4  Các ứng dụng của phân cụm dữ liệu ............................................................ 16 
1.5  Các yêu cầu và những vấn đề còn tồn tại trong phân cụm dữ liệu ................ 18 
1.5.1  Các yêu cầu của phân cụm dữ liệu ........................................................ 18 
1.5.2  Những vấn đề còn tồn tại trong phân cụm dữ liệu ................................. 20 
1.6  Tổng kết chương ......................................................................................... 20 
 


 

iv

CHƯƠNG 2 THUẬT TOÁN PHÂN CỤM ĐỒ THỊ DỮ LIỆU ....................... 22 
2.1  Tổng quan về lý thuyết đồ thị ...................................................................... 22 
2.1.1  Giới thiệu chung ................................................................................... 22 
2.1.2  Biểu diễn đồ thị trên máy tính ............................................................... 23 
2.2  Mô hình đồ thị dữ liệu ................................................................................. 27 
2.3  Độ đo trong phân cụm đồ thị dữ liệu ........................................................... 28 
2.3.1  Độ đo cho phân cụm dữ liệu nói chung ................................................. 28 
2.3.2  Độ đo cho phân cụm đồ thị ................................................................... 30 
2.4  Một số thuật toán phân cụm dữ liệu dựa trên đồ thị ..................................... 31 
2.4.1  Thuật toán CHAMELEON ................................................................... 31 
2.4.2  Thuật toán phân cụm quang phổ ........................................................... 33 
2.4.3  Thuật toán phân cụm phân cấp.............................................................. 35 
2.5  Kết luận chương .......................................................................................... 46 


Từ tiếng Anh 

Từ tiếng Việt 

Binding  data  Clustering  Phương pháp phân cụm dữ liệu 
BDCM
CA

Methods

có liên kết

Continuous Attribute

Thuộc tính liên tục
Cơ sở dữ liệu

CSDL
Discrette Attribute

Thuộc tính rời rạc

DBM

Density-Based Methods 

Phương pháp dựa trên mật độ 

GBM

Cây khung nhỏ nhất 

Partitioning Methods 

Phương pháp phân họach 

Random Walk Algorithm 

Thuật toán bước đi ngẫu nhiên 

Star Clustering 

Phân cụm hình sao 

PM
RWA
SC
SCA

Spectral Clustering Algorithm  Thuật toán phân cụm quang phổ 

SOM 

Self-Organizing Map 

 
 

 


Hình 1.2. Ví dụ phân cụm các đối tượng dựa trên khoảng cách [7] .......................... 5 
Hình 1.3. Ví dụ phân cụm các đối tượng dựa trên kích cỡ [7] .................................. 6 
Hình 1.4. Các bước trong quá trình phân cụm .......................................................... 8 
Hình 1.5. Các chiến lược phân cụm phân cấp [11] ................................................. 13 
Hình 1.6. Cấu trúc phân cụm dữ liệu dựa trên lưới ................................................ 15 
Hình 2.1. Ví dụ về mô hình đồ thị .......................................................................... 22 
Hình 2.2. Phân loại đồ thị ...................................................................................... 23 
Hình 2.3. Ma trận kề vô hướng (trên) và có hướng (dưới) ...................................... 25 
Hình 2.4. Ma trận trọng số vô hướng (trên) và có hướng (dưới) ............................. 26 
Hình 2.5. Ma trận liên thuộc vô hướng (trên) và có hướng (dưới) .......................... 27 
Hình 2.6. Minh họa thuật toán CHAMELEON ...................................................... 32 
Hình 2.7. Nguyên lý chung của AntTree ................................................................ 36 
Hình 2.8. Kiến trúc khác nhau giữa SOM và SOMTree ......................................... 41 
Hình 2.9. Phân việc từ cây  treec cho treec ............................................................ 44 
old

Hình 2.10. Tách subtreex khỏi cây  treec và đưa vào list ........................................ 45 
old

Hình 2.11. Tái liên kết subtreex vào treec .............................................................. 45 
Hình 3.1. Màn hình chính của chương trình ........................................................... 51 
Hình 3.2. Biểu diễn dữ liệu theo đồ thị .................................................................. 52 
Hình 3.3. Phân cụm dữ liệu đồ thị quang phổ với dữ liệu vào là dữ liệu kiểm tra ... 53 
Hình 3.4. Phân cụm dữ liệu đồ thị quang phổ với dữ liệu vào là điểm học sinh ..... 54 
Hình 3.5. Kết quả phân cụm dữ liệu dạng ba cụm Gaussian với 1000 mẫu dữ liệu 55 
Hình 3.6. Kết  quả  phân  cụm  dữ  liệu  dạng  ba  cụm Gaussian với  độ lớn  lần  lượt là 
100, 1000, 3000 mẫu dữ liệu ................................................................................. 55 
Hình 3.7. Kết quả phân cụm dữ liệu dạng hai nửa vầng trăng với kích thước dữ liệu 
là ba cụm Gaussian với độ lớn lần lượt là 7500 mẫu dữ liệu .................................. 56 
Hình 3.8. Kết quả phân cụm dữ liệu dạng hai nửa vầng trăng với hai thuật toán K 

thông tin. Trong phân cụm, sự tương đồng giữa các đối tượng được phân cụm có thể 
được diễn tả như một đồ thị có trọng số. Trong đó, các đối tượng là các đỉnh và sự 
tương đồng là trọng số của các cạnh. Bài toán phân cụm sẽ được đơn giản hóa về 
bài toán phân cụm đồ thị mà nhiệm vụ chính là tách các đồ thị phụ dày đặc và kết 
nối thưa thớt khỏi nhau dựa trên khái niệm của mật độ nội cụm so với khoảng cách 
liên cụm. 
Với những lý do trên, tác giả đã chọn đề tài “Phân cụm đồ thị dữ liệu và
ứng dụng”  làm  đề  tài  nghiên  cứu  luận  văn  tốt  nghiệp  thạc  sĩ  chuyên  ngành 
Khoa học máy tính. 
 


 

2

2. Mục tiêu, đối tượng và phạm vi nghiên cứu của đề tài
Đề tài nhằm thực hiện các mục tiêu sau:
- Nghiên cứu tổng quan và đánh giá các phương pháp phân cụm, nghiên cứu 
sâu về phương pháp phân cụm dữ liệu dựa trên đồ thị.  
- Nghiên cứu một số thuật toán của phương pháp phân cụm dựa trên đồ thị 
như: Chameleon, phân cụm đồ thị quang phổ (Spectral Clustering), phân cụm phân 
cấp theo đồ thị (thuật toán AntTree và SOMTree). Đánh giá các ưu và nhược điểm 
của mỗi thuật toán. 
- Cài  đặt  phần  mềm  thử  nghiệm  mô  phỏng  chương  trình  phân  loại  kết  quả 
học tập của học sinh theo thuật toán phân cụm đồ thị quang phổ, đánh giá hiệu quả 
hoạt động của thuật toán này. 
Chính  vì  vậy,  đối  tượng  của  luận  văn  là:  Các  thuật  toán  phân  cụm  dữ  liệu 
dựa trên đồ thị. Luận văn sẽ khảo sát và đánh giá một số ứng dụng thực tế của một 
số  phương  pháp  phân  cụm  dữ  liệu  dựa  trên  đồ  thị.Tập  trung  sâu  vào  cài  đặt  thử 

toán  như:  Thuật toán  Chameleon, thuật  toán  phân  cụm  quang  phổ, thuật  toán  Ant 
Tree, thuật toán  SOM Tree.
 Chương 3: Ứng dụng thuật toán đồ thị quang phổ trong việc phân loại
kết quả học tập của học sinh.
- Phát biểu bài toán, xây dựng chương trình phân loại kết quả học tập của 
học sinh theo thuật toán phân cụm dữ liệu quang phổ.
 

 

 


 

4

CHƯƠNG 1

TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU

1.1 Khái niệm, mục tiêu và các bước cơ bản của phân cụm dữ liệu
1.1.1 Phân cụm dữ liệu là gì?
Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu (Data mining) nhằm 
tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong 
tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định [6], [14]. 
Phân cụm dữ liệu là sự phân chia một cơ sở dữ liệu lớn thành các nhóm dữ 
liệu trong đó các đối tượng tương tự nhau trong một nhóm. Trong mỗi nhóm, một 
số chi tiết có thể không quan tâm đến để đổi lấy dữ liệu đơn giản hóa. Hay ta có thể 
hiểu “Phân cụm dữ liệu là quá trình tổ chức các đối tượng thành từng nhóm sao cho 


 
Hình 1.1. Ví dụ về phân cụm dữ liệu [7]
1.1.2 Các mục tiêu của phân cụm dữ liệu
Mục tiêu của phân cụm dữ liệu là để xác định các nhóm nội tại bên trong một 
bộ dữ liệu không có nhãn. Nhưng làm thế nào để quyết định cái gì đã tạo nên một 
phân cụm dữ liệu tốt? Ta có thể thấy rằng không có tiêu chuẩn tuyệt đối “tốt nhất” 
mà sẽ phải phụ thuộc vào mục đích cuối cùng của phân cụm dữ liệu. Do đó, người 
sử dụng phải cung cấp tiêu chuẩn. Theo cách như vậy, kết quả của phân cụm dữ liệu 
sẽ phù hợp với nhu cầu của họ cần. 

 
Hình 1.2. Ví dụ phân cụm các đối tượng dựa trên khoảng cách [7]
Ví  dụ,  chúng  ta có  thể  quan  tâm  đến  việc  tìm  kiếm  đối tượng  đại  diện  cho 
các nhóm đồng nhất trong “các cụm tự nhiên” và mô tả thuộc tính không biết của 
chúng trong việc tìm kiếm các nhóm hữu ích và phù hợp hoặc trong việc tìm kiếm 
các đối tượng bất thường trong dữ liệu (cá biệt, ngoại lệ, nhiễu) [1]. 
 


 

6
Một vấn đề thường gặp trong phân cụm là hầu hết các dữ liệu cần cho phân 

cụm đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc thiếu đầy 
đủ.  Vì  vậy,  cần  phải  xây  dựng  chiến  lược  cho  bước  tiền  xử  lí  dữ  liệu  nhằm  khắc 
phục  hoặc  loại  bỏ  nhiễu  trước  khi  chuyển  sang  giai  đoạn  phân  tích  cụm  dữ  liệu. 
Nhiễu ở đây được hiểu là các đối tượng dữ liệu không chính xác, không tường minh 
hoặc  là  các  đối  tượng  dữ  liệu  khuyết  thiếu  thông  tin  về  một  số  thuộc  tính...  Một 

được tiền xử lý trước khi dùng trong các bước sau.  
- Chọn độ đo gần gũi: Đây là một độ đo chỉ ra mức độ tương tự hay không 
tương tự giữa hai vector đặc trưng. Phải đảm bảo rằng tất cả các vector đặc trưng 
góp phần như nhau trong việc tính toán độ đo gần gũi và không có đặc trưng nào át 
hẳn đặc trưng nào. Điều này được đảm nhận bởi quá trình tiền xử lý.  
- Tiêu chuẩn phân cụm: Điều này phụ thuộc vào sự giải thích của chuyên 
gia  cho  thuật ngữ  “dễ nhận thấy”  dựa  vào  loại của  các cụm  được chuyên gia  cho 
rằng đang ẩn dấu dưới tập dữ liệu. Chẳng hạn, một cụm loại chặt (compact) của các 
vector đặc trưng trong không gian ℓ-chiều có thể dễ nhận thấy theo một tiêu chuẩn, 
trong  khi  một  cụm  loại  “dài và mỏng”  lại  có  thể  được  dễ  nhận  thấy  bởi  một  tiêu 
chuẩn khác. Tiêu chuẩn phân loại có thể được diễn đạt bởi hàm chi phí hay một vài 
loại quy tắc khác.  
- Thuật toán phân cụm: Cần lựa chọn một sơ đồ thuật toán riêng biệt nhằm 
làm sáng tỏ cấu trúc cụm của tập dữ liệu.  
- Công nhận kết quả: Khi đã có kết quả phân loại thì ta phải kiểm tra tính đúng 
đắn của nó. Điều này thường được thực hiện bởi việc dùng các kiểm định phù hợp.  
- Giải thích kết quả: Trong nhiều trường hợp, chuyên gia trong lĩnh vực ứng 
dụng phải kết hợp kết quả phân loại với bằng chứng thực nghiệm và phân tích để 
đưa  ra  các  kết  luận  đúng  đắn.  Trong  một  số  trường  hợp,  nên  có  cả  bước  khuynh 
hướng phân cụm; trong bước này có các kiểm định khác nhau để chỉ ra một dữ liệu 
có hay không một cấu trúc phân cụm. Ví dụ như tập dữ liệu của ta có thể hoàn toàn 
ngẫu nhiên vì vậy mọi cố gắng phân cụm đều vô nghĩa.  
Các  lựa  chọn  khác  nhau  của  các  đặc  trưng,  độ  đo  gần gũi,  tiêu  chuẩn phân 
cụm có thể dẫn tới các kết quả phân cụm khác nhau. Do đó, việc lựa chọn một cách 
 


 

8

hạn không đếm được  
- Thuộc tính rời rạc (Discrette
ộc tính rời rạc (Discrette Attribute): Nếu miền giá trị của nó l
ếu miền giá trị của nó là tập hữu 
hạn, đếm được  
- Lớp các thuộc tính nhị phân: l
ớp các thuộc tính nhị phân: là trường hợp đặc biệt của thuộc tính rời rạc 
ờng hợp đặc biệt của thuộc tính rời rạc 
mà miền giá trị của nó chỉ có 2 phần tử đ
ền giá trị của nó chỉ có 2 phần tử được diễn tả như : Yes / No ho
ư : Yes / No hoặc Nam/Nữ, 
False/true,…  

 


 

9

1.2.1.2 Phân loại các kiểu dữ liệu dựa trên hệ đo
Giả sử rằng chúng ta có hai đối tượng x, y và các thuộc tính xi, yi tương ứng 
với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu như sau :  
- Thuộc tính định danh (Nominal Scale): đây là dạng thuộc tính khái quát hoá 
của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có 
nhiều hơn hai phần tử - nghĩa là nếu x và y là hai đối tượng thuộc tính thì chỉ có thể 
xác định là x ≠ y hoặc x = y.  
- Thuộc tính có thứ tự (Ordinal Scale): là thuộc tính định danh có thêm tính 
thứ tự, nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì 
ta có thể xác định là x ≠ y hoặc x = y hoặc x > y hoặc x
đó, một số thực δ(x,y), được gọi là khoảng cách giữa x và y.   
- Quy tắc nói trên thoả mãn hệ tính chất sau : δ(x,y) > 0 nếu x ≠ y ;  (ii) δ(x,
y)=0 nếu x = y;  (iii) δ(x,y) = δ(y,x) với mọi x,y;  (iv) δ(x,y) ≤ δ(x,z)+δ(z,y).   
Hàm δ(x,y) được gọi là một metric của không gian. Các phần tử của X được 
gọi là các điểm của không gian này.  
1.2.2.2Thuộc tính khoảng cách
Sau khi chuẩn hoá, độ đo phi tương tự của hai đối tượng dữ liệu x, y được 
xác định bằng các metric khoảng cách như sau:  
- Khoảng  cách  Minskowski:  Được  thể  hiện  trong  (1.1)  trong  đó  q  là  số  tự 
nhiên dương. 
1/ q

 n
q
d  x, y     xi  yi   
 i 1


(1.1) 

- Khoảng cách Euclide : Được thể hiện bởi (1.2), đây là trường hợp đặc biệt 
của khoảng cách Minskowski trong trường hợp q=2. 
n

d  x, y  

 x y
i

2


pm
 
p

(1.5) 


 

11
Trong đó m là số thuộc tính đối sánh tương ứng trùng nhau, và p là tổng số 

các thuộc tính.  
1.2.2.4 Thuộc tính có thứ tự
Giả sử i là thuộc tính thứ tự có Mi  giá trị (Mi kích thước miền giá trị): Các 
trạng thái Mi được sắp thứ tự như sau : [1…Mi], chúng ta có thể thay thế  mỗi giá trị 
của thuộc tính bằng giá trị cùng loại ri, với ri ∈{1…Mi}.  
Mỗi một thuộc tính có thứ tự có các miền giá trị khác nhau, vì vậy chúng ta 
chuyển đổi chúng về cùng miền giá trị [0,1] bằng cách thực hiện phép biến đổi sau 
cho mỗi thuộc tính :  
ri   1
 
M i 1
j

Zi  
j

(1.6) 

phân loại theo các phương pháp tiếp cận chính như sau : Phương pháp phân hoạch 
(Partitioning  Methods);  Phương  pháp  phân  cấp  (Hierarchical  Methods);  Phương 
pháp dựa trên mật độ (Density-Based Methods); Phương pháp dựa trên lưới (GridBased  Methods);  Phương  pháp  dựa  trên  mô  hình  phân  cụm  (Model-Based 
 


 

12

Clustering  Methods)  và  Phương  pháp  phân  cụm  dữ  liệu  có  liên  kết  (Binding  data 
Clustering Methods) [8]. 
1.3.1 Phương pháp phân cụm phân hoạch
Kỹ thuật này phân hoạch một tập hợp dữ liệu có n phần tử thành k nhóm cho 
đến khi xác định số các cụm được thiết lập. Số các cụm được thiết lập là các đặc 
trưng được lựa chọn trước. Phương pháp này là tốt cho việc tìm các cụm hình cầu 
trong  không  gian  Euclidean.  Ngoài  ra,  phương  pháp  này  cũng  phụ  thuộc  vào 
khoảng cách cơ bản giữa các điểm để lựa chọn các điểm dữ liệu nào có quan hệ là 
gần  nhau  với  mỗi  điểm  khác  và  các  điểm  dữ  liệu  nào  không  có  quan  hệ  hoặc  có 
quan hệ là xa nhau so với mỗi điểm khác. Tuy nhiên, phương pháp này không thể 
xử lí các cụm có hình dạng kỳ quặc hoặc các cụm có mật độ các điểm dầy đặc. Các 
thuật  toán  phân  hoạch  dữ  liệu  có  độ  phức  tạp  rất  lớn  khi  xác  định  nghiệm  tối  ưu 
toàn  cục  cho  vấn đề  phân  cụm  dữ liệu,  do  nó  phải  tìm  kiếm tất cả  các  cách  phân 
hoạch có thể được. Chính vì vậy, trên thực tế thường đi tìm giải pháp tối ưu cục bộ 
cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lượng của 
cụm cũng như để hướng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu. Như vậy, ý 
tưởng  chính  của  thuật  toán  phân  cụm  phân  hoạch  tối  ưu  cục  bộ  là  sử  dụng  chiến 
lược tham lam (Greedy) để tìm kiếm nghiệm.  
Điển hình trong phương pháp tiếp cận theo phân cụm phân họach là các thuật 
toán  như  :  K_means,  K-medoids,  CLARA    (Clustering  Large  Applications), 

toán như : AGNES (Agglomerative Nesting), DIANA (Divisive Analysis), BIRCH 
(1996), CURE (1998), CHAMELEON (1999),… [7]. 
Thực tế áp dụng, có nhiều trường hợp kết hợp cả hai phương pháp phân cụm 
phân hoạch và phân cụm phân cấp, nghĩa là kết quả thu được của phương pháp phân 
cấp có thể cải tiến thông qua bước phân cụm phân hoạch. Phân cụm phân hoạch và 
phân  cụm  phân  cấp  là  hai  phương  pháp  phân  cụm  dữ  liệu  cổ  điển,  hiện  đã  có  rất 
nhiều thuật toán cải tiến dựa trên hai phương pháp này đã được áp dụng phổ biến 
trong khai phá dữ liệu.  
1.3.3 Phương pháp phân cụm dựa trên mật độ
Phương pháp phân cụm dựa trên mật độ nhóm các đối tượng dữ liệu dựa trên 
hàm mật độ xác định, mật độ là số các đối tượng lân cận của một đối tượng dữ liệu 
theo một nghĩa nào đó. Trong cách tiếp cận này, khi một dữ liệu đã xác định thì nó 
 


 

14

tiếp tục được phát triển thêm các đối tượng dữ liệu mới miễn là số các đối tượng lân 
cận này phải lớn hơn một ngưỡng đã được xác định trước. Phương pháp phân cụm 
dựa trên mật độ của các đối tượng để xác định các cụm dữ liệu có thể phát hiện ra 
các cụm dữ liệu với hình thù bất kỳ. Kỹ thuật này có thể khắc phục được các phần 
tử ngoại lai hoặc giá trị nhiễu rất tốt, tuy nhiên việc xác định các tham số mật độ 
của thuật toán là rất khó khăn, trong khi các tham số này lại có tác động rất lớn đến 
kết quả phân cụm.  
Điển hình trong phương pháp tiếp cận theo phân cụm dựa trên mật độ  là các 
thuật  toán  như  :  DBSCAN(KDD’96),  DENCLUE  (KDD’98),  CLIQUE 
(SIGMOD’98)), OPTICS (SIGMOD’99) . . . [7]. 
1.3.4 Phương pháp phân cụm dựa trên lưới

tốt của các tham số mô hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có 
thể sử dụng chiến lược phân cụm phân hoạch hoặc phân cụm phân cấp, dựa trên cấu 
trúc hoặc mô hình mà chúng giả định về tập dữ liệu và cách chúng hiệu chỉnh các 
mô hình này để nhận dạng ra các phân hoạch.   
Phương này cố gắng khám phá các phép xấp xỉ tốt của các tham số mô hình 
sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử dụng chiến lược phân 
cụm phân hoạch hoặc phân cụm phân cấp, dựa trên cấu trúc hoặc mô hình mà chúng 
giả định về tập dữ liệu và cách chúng hiệu chỉnh các mô hình này để nhận dạng ra 
các phân hoạch.   
1.3.6 Phương pháp phân cụm dữ liệu có liên kết
Sự phát triển của phân cụm dữ liệu không gian trên cơ sở dữ liệu lớn đã 
cung cấp nhiều công cụ tiện lợi cho việc phân tích thông tin địa lí, tuy nhiên hầu 
hết các thuật toán này cung cấp rất ít cách thức cho người dùng để xác định các 
ràng buộc trong thế giới thực cần phải được thỏa mãn trong quá trình phân cụm. 
 


 

16

Để phân cụm dữ liệu không gian hiệu quả hơn, các nghiên cứu bổ sung cần được 
thực  hiện  để  cung  cấp  cho  người  dùng  khả  năng  kết  hợp  các  ràng  buộc  trong 
thuật toán phân cụm.  
Hiện nay, các phương pháp phân cụm trên đã và đang được phát triển và áp 
dụng nhiều trong các lĩnh vực khác nhau và đã có một số nhánh nghiên cứu được 
phát triển trên cơ sở của các phương pháp đó như:   
- Phân  cụm  thống  kê:  Dựa  trên  các  khái  niệm  phân  tích  hệ  thống,  nhánh 
nghiên  cứu  này  sử  dụng  các  độ  đo  tương  tự  để  phân  hoạch  các  đối  tượng,  nhưng 
chúng chỉ áp dụng cho các dữ liệu có thuộc tính số.