..

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP

KHỔNG MINH TỰ

NGHIÊN CỨU, TÌM HIỂU MỘT SỐ
THUẬT TỐN CƠ BẢN VỀ PHÂN NHĨM DỮ LIỆU
TRÊN CƠ SỞ DỮ LIỆU KHƠNG GIAN

LUẬN VĂN THẠC SĨ KỸ THUẬT ĐIỆN TỬ

THÁI NGUYÊN - 2014
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP
........................................

KHỔNG MINH TỰ

NGHIÊN CỨU, TÌM HIỂU MỘT SỐ
THUẬT TỐN CƠ BẢN VỀ PHÂN NHĨM DỮ LIỆU
TRÊN CƠ SỞ DỮ LIỆU KHƠNG GIAN
Chuyên ngành: KỸ THUẬT ĐIỆN TỬ
Mã số: 60. 52. 02. 03
LUẬN VĂN THẠC SĨ KỸ THUẬT
PHÕNG QUẢN LÝ ĐÀO TẠO

NGƢỜI HƢỚNG DẪN KHOA HỌC

SAU ĐẠI HỌC

PGS.TS. LƢƠNG CHI MAI

KHOA ĐIỆN TỬ
TRƢỞNG KHOA

THÁI NGUYÊN - 2014
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

i

LỜI CAM ĐOAN
Tơi xin cam đoan đây là cơng trình nghiên cứu của riêng tôi, các số liệu, kết quả nêu
trong luận văn này là trung thực và là công trình nghiên cứu của riêng tơi, luận văn này
khơng giống hồn tồn bất cứ luận văn hoặc các cơng trình đã có trƣớc đó.
Thái Nguyên, ngày 24 tháng 02 năm 2014
Tác giả luận văn

Khổng Minh Tự

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>


ii

LỜI CẢM ƠN
Trong suốt quá trình học tập và tốt nghiệp, tơi đã nhận đƣợc sự giúp đỡ tận
tình của các thầy cô trong Khoa Điện tử - Trƣờng Đại học Kỹ thuật Công nghiệp Đại học Thái Nguyên. Tôi xin bày tỏ lòng biết ơn đối với các thầy cơ giáo và
Phịng Đào tạo sau đại học vì sự giúp đỡ tận tình này. Tơi đặc biệt muốn cảm ơn
PGS.TS. Lƣơng Chi Mai đã tận tình giúp đỡ, hƣớng dẫn tôi trong thời gian thực
hiện đề tài, cảm ơn sự giúp đỡ của gia đình, bạn bè và các đồng nghiệp trong thời
gian qua.
Mặc dù đã cố gắng, song do điều kiện thời gian và kinh nghiệm thực tế cịn
nhiều hạn chế nên khơng thể tránh khỏi thiếu sót. Vì vậy, tơi rất mong nhận đƣợc
sự đóng góp ý kiến của các thầy cô cũng nhƣ của các bạn bè, đồng nghiệp.
Tôi xin chân thành cảm ơn!
Tác giả luận văn

Khổng Minh Tự

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

iii

LỜI NĨI ĐẦU
Trong thời đại bùng nổ Cơng nghệ thơng tin, các công nghệ lƣu trữ dữ liệu
ngày càng phát triển nhanh chóng tạo điều kiện cho các đơn vị thu thập dữ liệu
nhiều hơn và tốt hơn. Đặc biệt trong lĩnh vực quản lý, kinh doanh, các doanh nghiệp
đã nhận thức đƣợc tầm quan trọng của việc nắm bắt và xử lí thơng tin. Tất cả lí do
đó khiến cho các cơ quan, đơn vị và các doanh nghiệp đã tạo ra một lƣợng dữ liệu
khổng lồ cỡ Gigabyte thậm chí là Terabyte cho riêng mình. Các kho dữ liệu ngày

càng lớn và tiềm ẩn nhiều thơng tin có ích. Sự bùng nổ đó dẫn tới một yêu cầu cấp
thiết là phải có những kĩ thuật và cơng cụ mới để biến kho dữ liệu khổng lồ kia
thành những thơng tin (tri thức) cơ đọng và có ích.
Tuy nhiên ngay cả khi đã có những cơng cụ phù hợp để lƣu trữ và quản lý các
dạng thơng tin nói trên, thì để nhận đƣợc những thơng tin có ích đối với dạng CSDL
loại này, các biện pháp phân tích dữ liệu thơng thƣờng cũng gặp rất nhiều khó khăn,
đơi khi là khơng thể giải quyết đƣợc. Đó chính là cơ sở cho sự xuất hiện của kỹ
thuật khai phá dữ liệu.
Tác giả xin bày tỏ lòng biết ơn chân thành đến các thầy cô giáo, đặc biệt là cô
giáo hƣớng dẫn: PGS.TS. Lƣơng Chi Mai đã tận tình giúp đỡ để hồn thành luận
văn này.
Trong khn khổ giới hạn của luận văn cùng khả năng kiến thức và thời gian
nghiên cứu cịn hạn chế, nên mặc dù đã có nhiều cố gắng song luận văn chắc chắn
không tránh khỏi những thiếu sót. Tác giả mong nhận đƣợc sự đóng góp ý kiến của
các thầy giáo, cơ giáo để đề tài đƣợc hoàn thiện hơn.
Xin trân trọng cảm ơn!

HỌC VIÊN

Khổng Minh Tự

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

iv

MỤC LỤC
LỜI CAM ĐOAN ....................................................................................................... i
LỜI CẢM ƠN ............................................................................................................ ii

LỜI NÓI ĐẦU .......................................................................................................... iii
MỤC LỤC ................................................................................................................. iv
BẢNG THUẬT NGỮ VIẾT TẮT ........................................................................... vii
DANH MỤC CÁC HÌNH ....................................................................................... viii
MỞ ĐẦU ....................................................................................................................1
Chƣơng 1. TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ CƠ SỞ
DỮ LIỆU KHÔNG GIAN ..................................................................6
1.1. Khai phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in
Databases - DD) ......................................................................................... 6
1.1.1. Sự ra đời của khai phá tri thức trong cơ sở dữ liệu ....................................... 6
1.1.2. Khái niệm khai phá dữ liệu ..................................................................................... 7
1.1.3. Quá trình khai phá tri thức trong cơ sở dữ liệu ..................................................... 7
1.1.4. Các nhiệm vụ của khai phá dữ liệu ........................................................................ 8
1.2. Phân nhóm (Clustering) và các cách tiếp cận chính.................................... 9
1.2.1. Phân nhóm và các ứng dụng ................................................................................... 9
1.2.2. Các cách tiếp cận chính ......................................................................................... 11
1.3. Hệ quản trị cơ sở dữ liệu không gian .........................................................16
1.3.1. Cơ sở dữ liệu không gian ....................................................................................... 16
1.3.2. Hệ quản trị cơ sở dữ liệu không gian ................................................................... 17
1.3.3. Phƣơng pháp truy nhập không gian...................................................................... 18
1.4. Kết luận ...................................................................................................................... 20
Chƣơng 2. CÁC CÁCH TIẾP CẬN CỦA KỸ THUẬT PHÂN NHĨM ............21
2.1. Thuật tốn DBSCAN .................................................................................21
2.1.1. Các định nghĩa và bổ đề đƣợc sử dụng trong thuật toán DBSCAN ................. 22
2.1.2. Thuật tốn DBSCAN ............................................................................................. 25
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

v


2.2. Thuật toán DBCLASD ...............................................................................27
2.2.1. Một số định nghĩa ................................................................................................... 27
2.2.2. Thuật toán DBCLASD........................................................................................... 30
2.3. Thuật toán DENCLUE...............................................................................34
2.3.1. Một số định nghĩa ................................................................................................... 35
2.3.2. Những tính chất của phƣơng pháp DENCLUE .................................................. 37
2.3.3. Thuật toán DENCLUE........................................................................................... 38
2.4. Kết luận ...................................................................................................................... 43
Chƣơng 3. CÁC GIẢI THUẬT PHÂN NHÓM TRÊN CƠ SỞ
DỮ LIỆU KHÔNG GIAN LỚN .......................................................44
3.1. Một số khái niệm cần thiết khi tiếp cận phân nhóm dữ liệu ......................44
3.1.1. Phân loại các kiểu dữ liệu ...................................................................................... 44
3.1.2. Độ đo tƣơng tự và phi tƣơng tự ............................................................................ 45
3.2. Thuật toán K-MEANS ...............................................................................49
3.3. Giải thuật DBSCAN ...................................................................................53
3.4. Kết luận ......................................................................................................55
Chƣơng 4. XÁC ĐỊNH THAM SỐ, CÀI ĐẶT THỬ NGHIỆM
VÀ ĐÁNH GIÁ KẾT QUẢ ...............................................................56
4.1. Môi trƣờng thử nghiệm ..............................................................................56
4.2. Công cụ thử nghiệm ...................................................................................56
4.3. Xác định tham số........................................................................................56
4.3.1. Xác định tham số cho thuật toán DBSCAN ........................................................ 56
4.3.2. Tối ƣu hoá việc lựa chọn các tham số

và cho thuật toán DENCLUE ...........62

4.4. Cài đặt thử nghiệm và đánh giá kết quả ....................................................63
4.4.1. Xây dựng chƣơng trình cài đặt thuật tốn phân nhóm ....................................... 63
4.4.2. Tạo lập dữ liệu ........................................................................................................ 64

4.4.3. Cài đặt thuật tốn phân nhóm ............................................................................... 65
4.4.4. Lƣu trữ và hiển thị kết quả .................................................................................... 73
4.5. Đánh giá kết quả trên một số tập dữ liệu ...................................................74
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

vi

4.5.1. Tập dữ liệu ............................................................................................................... 74
4.5.2. Đánh giá kết quả ..................................................................................................... 75
4.5.3. Nhận xét ................................................................................................................... 79
4.6. Kết luận ......................................................................................................81
KẾT LUẬN ..............................................................................................................82
TÀI LIỆU THAM KHẢO ......................................................................................84

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

vii

BẢNG THUẬT NGỮ VIẾT TẮT

Từ hoặc nhóm từ

Từ viết tắt

Từ tiếng anh


Cơ sở dữ liệu

CSDL

DataBase

Khai phá dữ liệu

KPDL

Data Mining

Khai phá tri thức

KPTT

Knowledge Discovery

Khai phá tri thức trong cơ sở dữ liệu

KDD

Knowledge Discovery in Databases

Phân nhóm dữ liệu

PNDL

Data Clustering


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

viii

DANH MỤC CÁC HÌNH
Hình 1.1:

Các bƣớc trong q trình khám phá tri thức KDD .................................8

Hình 1.2:

Biểu đồ Hertzsprung-Russell ............................................................... 10

Hình 1.3:

Mơ tả cách phân nhóm theo phƣơng pháp từ dƣới lên và từ trên
xuống .................................................................................................... 14

Hình 1.4:

Những điểm nằm trong miền tơ sẫm mới đƣợc xét đến khi tìm
điểm gần nhất cho điểm x. Những điểm ngồi miền khơng cần
xét đến .................................................................................................. 17

Hình 1.5:

Một cách chia lƣới. Những ơ mầu sẫm là những ô chứa dữ liệu và
đƣợc lƣu trữ. Những ô màu trắng là những ô không chứa dữ liệu....... 19


Hình 1.6:

Mơ phỏng một R*-tree gồm 3 mức ...................................................... 20

Hình 2.1:

Lân cận của P với ngƣỡng Eps ............................................................. 22

Hình 2.2:

Mật độ - đến đƣợc trực tiếp .................................................................. 23

Hình 2.3:

Mật độ đến đƣợc................................................................................... 23

Hình 2.4:

Mật độ liên thơng ................................................................................. 24

Hình 2.5:

Nhóm và nhiễu ..................................................................................... 24

Hình 2.6:

Mơ phỏng thuật tốn DBSCAN ........................................................... 25

Hình 2.7:


Thủ tục ExpandCluster ......................................................................... 26

Hình 2.8:

Ví dụ dữ liệu tập các điểm đƣợc chia thành 2 lớp ............................... 27

Hình 2.9:

Ảnh hƣởng của độ rộng ơ lƣới đến việc xác định vùng xấp xỉ ............ 29

Hình 2.11: Ví dụ một cách chia và đánh số trong không gian hai chiều ............... 40
Hình 3.1:

Minh họa số đo chiều rộng, chiều cao một đối tƣợng ......................... 46

Hình 3.2:

Khoảng cách Euclidean ........................................................................ 48

Hình 3.3:

Các thiết lập để xác định ranh giới các nhóm ban đầu......................... 49

Hình 3.4:

Tính tốn trọng tâm của các nhóm mới................................................ 50

Hình 3.5:


Ví dụ các bƣớc của thuật tốn K-means .............................................. 52

Hình 3.6:

Một số hình dạng khám phá bởi phân nhóm dƣa trên mật độ.............. 54

Hình 3.7:

Thuật tốn DBSCAN ........................................................................... 54

Hình 4.1:

Mơi trƣờng thử nghiệm ........................................................................ 56

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

ix

Hình 4.2:

Đồ thị khoảng cách với k = 4. Dựa vào đồ thị khoảng cách đó ta có
thể đƣa ra đƣợc khoảng cách Eps một cách chính xác............................ 57

Hình 4.3:

Tập các dữ liệu đƣợc biểu diễn trong toạ độ 2 chiều ........................... 59

Hình 4.4:


Đồ thị k-dist (k = 3) .............................................................................. 59

Hình 4.5

.............................................................................................................. 60

Hình 4.6

.............................................................................................................. 60

Hình 4.7

.............................................................................................................. 60

Hình 4.8

.............................................................................................................. 61

Hình 4.9.

Các tập dữ liệu với mật độ phân bố khác nhau giữa các lớp .............. 61

Hình 4.10: Đồ thị mơ tả sự phụ thuộc m( ) vào

............................................... 62

Hình 4.11: Sơ đồ thực hiện chƣơng trình ............................................................... 63
Hình 4.12: Tập dữ liệu lấy từ nguồn tài liệu .......................................................... 74
Hình 4.13: Tập dữ liệu lấy từ nguồn tài liệu .......................................................... 75

Hình 4.14: Tập dữ liệu lấy từ nguồn tài liệu .......................................................... 75
Hình 4.15: Tập dữ liệu ban đầu .............................................................................. 75
Hình 4.16a .............................................................................................................. 76
Hình 4.16 b .............................................................................................................. 76
Hình 4.16 c .............................................................................................................. 76
Hình 4.17 a .............................................................................................................. 77

Hình 4. 17 b ......................................................................................................77
Hình 4.17 c .............................................................................................................. 78
Hình 4.18 a .............................................................................................................. 78
Hình 4.18 b .............................................................................................................. 79

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

1

MỞ ĐẦU
Trong vài thập kỷ gần đây, công nghệ thông tin có nhiều bƣớc phát triển
nhanh chóng và đã đƣợc ứng dụng rộng rãi trong mọi lĩnh vực, ngành nghề xã hội,
đặc biệt là lĩnh vực quản lý – một lĩnh vực mà yếu tố công nghệ xử lý thông tin có
tính chất quyết định. Từ đó, theo q trình hoạt động của các hệ thống quản lý dẫn
đến sự bùng nổ thơng tin, kích thƣớc của các kho dữ liệu có kích thƣớc tăng nhanh
chóng theo từng năm, từng thời kỳ, làm cho những nhà (lãnh đạo) quản lý rơi vào
tình trạng “ngập lụt thơng tin”. Kích thƣớc dữ liệu tăng quá nhanh dẫn tới các
phƣơng pháp phân tích dữ liệu truyền thống khơng cịn có thể đáp ứng đƣợc nữa. Vì
vậy, các chun gia cơng nghệ thơng tin cho rằng hiện nay chúng ta đang sống
trong một xã hội mà “rất giàu thông tin nhƣng nghèo tri thức”. Trƣớc hiện trạng đó,
địi hỏi phải phát triển các phƣơng pháp khai phá, phát hiện ra những tri thức có ích

tiềm ẩn trong các kho dữ liệu khổng lồ kia để phục vụ tốt hơn cho công việc quyết
định của các nhà quản lý.
Sự ra đời của lĩnh vực khai phá dữ liệu đã mở ra nhiều hƣớng nghiên cứu
mới thu hút sự quan tâm chú ý của nhiều nhà nghiên cứu thuộc nhiều lĩnh vực khác
nhau. Đồng thời, dựa trên các kỹ thuật đƣa ra trong lĩnh vực này rất nhiều các ứng
dụng đã đƣợc xây dựng tạo ra đƣợc nhiều hệ thống trợ giúp đắc lực cho cuộc sống
con ngƣời.
Khai phá dữ liệu (Data Mining) là một lĩnh vực khoa học liên ngành mới
xuất hiện gần đây nhằm đáp ứng nhu cầu này. Các kết quả nghiên cứu cùng với
những ứng dụng thành công trong khai phá dữ liệu, khám phá tri thức cho thấy khai
phá dữ liệu là một lĩnh vực khoa học tiềm năng, mang lại nhiều lợi ích, đồng thời có
ƣu thế hơn hẳn so với các cơng cụ phân tích dữ liệu truyền thống.
Một trong các kỹ thuật khai phá dữ liệu đang đƣợc quan tâm nghiên cứu đó
là kỹ thuật phân nhóm (clustering). Thật vậy, trong một vài thập kỷ qua, phân nhóm
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

2

đƣợc sử dụng rộng rãi trong các lĩnh vực nhƣ nhận dạng (pattern recognition), phân
tích dữ liệu (data analysis) và xử lý ảnh (image processing). Hiện nay, phân nhóm
dữ liệu là một hƣớng đƣợc nghiên cứu rất nhiều trong Tin học. Tuy nhiên, các giải
thuật phân nhóm đƣợc biết trƣớc đây có một số hạn chế khi áp dụng vào các cơ sở
dữ liệu khơng gian lớn [10].
1. Tính cấp thiết của đề tài
Dữ liệu khơng gian?
Với lý do, ngồi nhu cầu lƣu trữ và xử lý các kiểu dữ liệu thông thƣờng nhƣ
kiểu chuỗi, kiểu số, kiểu ngày tháng, … ngƣời sử dụng cịn có thêm nhu cầu lƣu trữ
và xử lý dữ liệu không gian để lƣu trữ các đối tƣợng nhƣ Point, Line, Polugon, …

Và từ đó, một mơ hình cơ sở dữ liệu đƣợc quan tâm nhất hiện nay chính là mơ hình
cơ sở dữ liệu không gian (SDB – Spatial Database) đƣợc sử dụng cho xử lý và lƣu
trữ dữ liệu không gian, chẳng hạn nhƣ dữ liệu bản đồ, dữ liệu, dữ liệu của lĩnh vực
khí tƣợng thuỷ văn, quân sự, multimedia, … và đặc biệt là trong lĩnh vực viễn
thông. Thuật ngữ dữ liệu không gian (spatial data) đƣợc sử dụng theo nghĩa rộng,
bao gồm các phần tử dữ liệu (bản ghi) mô tả cho mỗi đối tƣợng mà trong đó bao
hàm 2 thành phần: thành phần thông tin về không gian (vị trí địa lý, vùng, toạ độ,
… ) và thành phần cịn lại là các thuộc tính khác của đối tƣợng. Mối quan hệ giữa
thuộc tính khơng gian và thuộc tính phi khơng gian liên kết rất chặt chẽ và có thể
dựa vào thuộc tính chất khơng gian để đƣa ra đƣợc thuộc tính phi khơng gian và
ngƣợc lại. Ví dụ nhƣ dựa vào tính chất về tỷ lệ ngƣời thất nghiệp của một điểm dữ
liệu, chúng ta có thể đƣa ra đƣợc dự đốn về vị trí của điểm đó (trung tâm thành
phố, nông thôn, miền núi, …). Hoặc dựa vào vị trí của điểm đó với các điểm trung
tâm thành phố, chúng ta có thể đƣa ra đƣợc tỷ lệ thất nghiệp với một mức độ chính
xác nhất định. Một ví dụ khác là mức độ mƣa giữa các vùng, miền trên lãnh thổ
(lĩnh vực khí tƣợng) cũng đƣợc lƣu trữ trong cơ sở dữ liệu sau nhiều năm nhƣ một
kho dữ liệu khơng gian.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

3

Dữ liệu không gian trong lĩnh vực điện tử, truyền thông?
Trong hoạt động quản lý của các nhà cung cấp dịch vụ viễn thơng, kích
thƣớc kho dữ liệu lƣu trữ về các cuộc thoại di động tăng nhanh đáng kể. Dữ liệu mô
tả cho các cuộc đàm thoại này cũng mang tính chất của dữ liệu khơng gian. Thuộc
tính khơng gian của nó có thể là tỉnh, vùng, cell, … và thuộc tính phi khơng gian có
thể bao gồm: thời điểm của cuộc thoại, thời gian đàm thoại, thuê bao, … Với kho
dữ liệu khổng lồ đƣợc lƣu trữ về các cuộc thoại, một vấn đề đặt ra là liệu có tri thức

nào để trả lời cho những câu hỏi dạng nhƣ:
-

Mối quan hệ giữa vùng và thời gian của các cuộc thoại?

-

Mối quan hệ của các cuộc đàm thoại giờ thấp điểm và thời gian đàm thoại?

-

Vùng của các cuộc thoại có tỉ lệ diễn ra nhiều?

-

…

Khai phá dữ liệu khơng gian
Để có thể trích rút các tri thức có ích nhƣ trình bày ở trên là một vấn đề quan
trọng đƣợc nhiều nhà lãnh đạo quản lý quan tâm. Nó có thể giúp cho các nhà lãnh đạo
ra các quyết định đúng đắn hơn trong chiến lƣợc đầu tƣ, phát triển và điều phối hay
vận hành hệ thống mạng viễn thơng một cách hiệu quả.
Chính vì lý do đó mà em chọn đề tài “Nghiên cứu, tìm hiểu một số thuật tốn
cơ bản về phân nhóm dữ liệu trên Cơ sở dữ liệu không gian” làm hƣớng nghiên cứu
chính cho luận văn của mình.
2. Mục tiêu đề tài
Mục tiêu trọng tâm của đề tài là:
-

Nghiên cứu một số thuật tốn phân nhóm dữ liệu trên cơ sở dữ liệu không gian.


-

Cài đặt thử nghiệm trên một số mẫu dữ liệu không gian (dựa trên tập dữ
liệu trong các tài liệu tham khảo).

-

Đƣa ra bảng so sánh giữa các thuật tốn.

-

Tìm cách xây dựng các tham số cho các thuật tốn.

3. Đối tƣợng và phạm vi nghiên cứu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

4

-

Các kỹ thuật thu thập và lƣu trữ dữ liệu;

-

Các phƣơng pháp phân nhóm dữ liệu;

-


Tập trung nghiên cứu một số thuật tốn phân nhóm cơ bản dựa vào mật độ
phân bố của các đối tƣợng dữ liệu không gian.

4. Ý nghĩa khoa học và thực tiễn của đề tài
a. Ý nghĩa khoa học
Vào cuối thập kỷ 90, kỹ thuật khám phá tri thức trong cơ sở dữ liệu
(Knowledge Discovery in Database -KDD) đƣợc đƣa ra nhằm tìm kiếm các thơng tin,
tri thức cần thiết, có giá trị tiềm ẩn trong một khối dữ liệu lớn và phức tạp nhƣ dữ liệu
không gian, dữ liệu đa phƣơng tiện, … Trong đó, giai đoạn khai phá dữ liệu là giai
đoạn chính trong quá trình khai phá tri thức trong cơ sở dữ liệu. Có rất nhiều phƣơng
pháp khai phá dữ liệu nhƣ phân lớp, phân nhóm, phát hiện luật kết hợp, … Mỗi
phƣơng pháp có những đặc điểm riêng phù hợp với một lớp các bài toán, các dạng dữ
liệu và miền dữ liệu nhất định.
Đối với dữ liệu không gian, phƣơng pháp đang đƣợc quan tâm nghiên cứu là
phƣơng pháp phân nhóm (clustering). Đây là một bài tốn quan trọng của lĩnh vực tìm
kiếm tri thức trong cơ sở dữ liệu không gian lớn và phải đƣợc giải quyết trƣớc tiên.
Hiện nay nhiều nhà khoa học đã đƣa ra nhiều giải thuật phân nhóm, tuy nhiên
khơng cho ra kết quả tốt trong trƣờng hợp kích thƣớc dữ liệu lớn, có hình dạng phức
tạp và có cả nhiễu.
b. Ý nghĩa thực tiễn
Kết quả nghiên cứu là tìm hiểu và đƣa ra một số thuật tốn phân nhóm có hiệu
quả trên dữ liệu không gian, đặc biệt trong trƣờng hợp dữ liệu lớn, bị nhiễu, đa chiều.
Kết quả so sánh giữa các thuật tốn cho thấy tính hiệu quả của mỗi thuật toán trên
những đối tƣợng dữ liệu khác nhau. Trong lĩnh vực viễn thông, là lĩnh vực phát triển
mạnh mẽ và lƣợng thông tin trao đổi cực lớn, dữ liệu lƣu trữ đồ sộ. Giải quyết đƣợc
bài tốn phân nhóm dữ liệu khơng gian là giải quyết đƣợc bài tốn lớn trong việc hỗ
trợ quyết định của nhiều lĩnh vực quản lý, đặc biệt là trong lĩnh vực viễn thông. Cho
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên


/>

5

phép các nhà lãnh đạo quản lý có những chiến lƣợc đúng đắn, kịp thời trong việc điều
hành các hoạt động của hệ thống nhƣ đầu tƣ, vận hành, cũng cấp các dịch vụ, nâng
cấp, biến đổi đơn vị mang tính cạnh tranh, …
5. Phƣơng pháp nghiên cứu
Phƣơng pháp tài liệu: Nghiên cứu các tài liệu (sách, báo, tạp chí khoa học,
Internet, …) liên quan đến kỹ thuật phân nhóm dữ liệu trên CSDL không gian.
Phƣơng pháp thực nghiệm: Cài đặt thử nghiệm trên một số mẫu dữ liệu, từ
đó đƣa ra đánh giá về tính hiệu quả của các thuật tốn đó.
6. Bố cục của luận văn
Ngồi các phần Mở đầu, Mục lục, Danh mục hình, Kết luận, Tài liệu tham
khảo. Nội dung chính của luận văn đƣợc trình bày trong 04 chƣơng nhƣ sau:
Chƣơng 1: Tổng quan về khai phá tri thức trong cơ sở dữ liệu không gian.
Chƣơng 2: Các cách tiếp cận của kỹ thuật phân nhóm.
Chƣơng 3: Các giải thuật phân nhóm trên cơ sở dữ liệu không gian lớn.
Chƣơng 4: Xác định tham số, cài đặt thử nghiệm và đánh giá kết quả.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

6

Chƣơng 1

TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ CƠ SỞ
DỮ LIỆU KHÔNG GIAN

1.1. Khai phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD)
1.1.1. Sự ra đời của khai phá tri thức trong cơ sở dữ liệu
Trong những năm gần đây, cùng với sự thay đổi và phát triển không ngừng
của ngành công nghệ thông tin nói chung và trong các ngành cơng nghệ phần cứng,
phần mềm, truyền thông và hệ thống các dữ liệu phục vụ trong các lĩnh vực kinh tế
xã hội nói riêng đã làm cho khả năng thu thập và lƣu trữ thông tin của các hệ thống
thông tin tăng nhanh một cách chóng mặt. Bên cạnh đó việc tin học hóa một cách ồ
ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng nhƣ nhiều lĩnh vực hoạt
động khác đã tạo ra cho chúng ta một lƣợng dữ liệu lƣu trữ khổng lồ. 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 trí 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 các tri thức có ích.
Sự phát triển nhanh chóng của một lƣợng lớn dữ liệu đƣợc thu thập và lƣu
trữ trong các cơ sở dữ liệu lớn đã vƣợt ra ngoài khả năng của con ngƣời để có thể
hiểu hết đƣợc chúng nếu khơng có những công cụ hỗ trợ tốt. Kết quả là, dữ liệu thu
thập đƣợc trong một lƣợng lớn cơ sở dữ liệu đã trở thành những đống dữ liệu mà ít
khi đƣợc xem xét đến. Do vậy, việc đƣa ra những quyết định thƣờng không dựa vào
những thông tin hoặc dữ liệu thu thập đƣợc mà chỉ dựa vào nhận thức, suy đoán của
ngƣời đƣa ra quyết định, đơn giản là vì họ khơng có những cơng cụ giúp cho việc
lấy ra những tri thức từ lƣợng lớn dữ liệu. Tình huống này đã đặt chúng ta trong
hoàn cảnh nhiều dữ liệu nhƣng thiếu thông tin, thiếu tri thức. Với một khối lƣợng
lớn dữ liệu nhƣ vậy rõ ràng là các phƣơng pháp thủ cơng truyền thống áp dụng để
phân tích dữ liệu nhƣ chia bảng hoặc ngôn ngữ truy vấn ad-hoc đã không thể áp
dụng đƣợc nữa. Dẫn đến nhu cầu về một kỹ thuật mới có các đặc tính thơng minh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

7


và khả năng tự động để hỗ trợ con ngƣời tìm kiếm thơng tin hữu ích trong một núi
dữ liệu lộn xộn. Kỹ thuật đó đƣợc gọi là khai phá tri thức trong cơ sở dữ liệu
(Knowledge Discovery in Database - KDD).
Khai phá tri thức trong cơ sở dữ liệu đƣợc định nghĩa bởi Fayyad nhƣ sau:
“Knowledge discovery in databases is the non-trivial process of identifying valid,
novel, potentially, and ultimately understandable patterns in data”. (Khai phá tri thức
trong cơ sở dữ liệu là một q trình khơng tầm thƣờng của việc xác định các mẫu mới
lạ, có giá trị, có hiệu quả sử dụng và cơ bản hiểu đƣợc trong cơ sở dữ liệu). [4], [11]
1.1.2. Khái niệm khai phá dữ liệu
Khai phá dữ liệu (Data Mining) là một khái niệm ra đời vào những năm cuối
của thập kỷ 1980. Nó là q trình trích xuất các thơng tin có giá trị tiềm ẩn bên
trong lƣợng lớn dữ liệu đƣợc lƣu trữ trong các CSDL, kho dữ liệu….Hiện nay,
ngoài thuật ngữ khai phá dữ liệu, ngƣời ta còn dùng một số thuật ngữ khác có ý
nghĩa tƣơng tự nhƣ: Khai phá tri thức từ CSDL, trích lọc dữ liệu, phân tích dữ liệu
mẫu, khảo cổ dữ liệu, nạo vét dữ liệu. Nhiều ngƣời coi Khai phá dữ liệu và một
thuật ngữ thông dụng khác là Phát hiện tri thức trong CSDL (Knowledge Discovery
in Databases - KDD) là nhƣ nhau. Tuy nhiên trên thực tế, khai phá dữ liệu chỉ là
một bƣớc thiết yếu trong quá trình Phát hiện tri thức trong CSDL. Có thể nói Data
Mining là giai đoạn quan trọng nhất trong tiến trình Phát hiện tri thức từ cơ sở dữ
liệu, các tri thức này hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh.
1.1.3. Quá trình khai phá tri thức trong cơ sở dữ liệu
Quá trình khai phá tri thức trong cơ sở dữ liệu bao gồm các giai đoạn sau:
1. Trƣớc tiên cần xác định và hiểu rõ đƣợc lĩnh vực ứng dụng và nhiệm vụ
đặt ra là xác định các tri thức đã có và mục đích của ngƣời sử dụng.
2. Tạo lập đƣợc một tập dữ liệu đích: Chọn lựa từ cơ sở dữ liệu một tập con
dữ liệu với các giá trị biến và các mẫu đƣợc quan tâm mà trên đó ta có thể thực hiện
việc tìm kiếm, phát hiện tri thức.
3. Làm sạch và tiền xử lý dữ liệu: Thực hiện các thao tác cơ bản nhƣ loại bỏ
nhiễu hoặc loại bỏ các phần không cần thiết, bổ sung thêm các thơng tin cần thiết

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

8

4. Thực hiện các phƣơng pháp chuyển đổi để làm giảm bớt số chiều của dữ
liệu để tập trung vào những thuộc tính chủ chốt đối với việc phát hiện tri thức.
5. Khai phá dữ liệu: Quá trình áp dụng các giải thuật về tìm kiếm tri thức để
đƣa ra đƣợc những thông tin cần thiết và tiềm ẩn trong tập dữ liệu.
6. Đánh giá, giải thích, thử lại các mẫu đã đƣợc khai phá, có thể lặp lại một
hoặc nhiều bƣớc kể trên để thu đƣợc các kết quả tốt hơn.
7. Sử dụng các tri thức phát hiện đƣợc: Hợp nhất các tri thức thu đƣợc vào một
hệ thống làm việc, hoặc đƣa ra các tài liệu về tri thức thu đƣợc từ dữ liệu về một vấn
đề quan tâm. Giải quyết các xung đột tiềm tàng trong tri thức khai thác đƣợc.

Hình 1.1: Các bƣớc trong quá trình khám phá tri thức KDD
Khai phá dữ liệu (Data mining) chỉ là một bƣớc trong quá trình khai phá tri
thức trong cơ sở dữ liệu. Tuy nhiên đây là giai đoạn đóng vai trị quan trọng nhất,
có ảnh hƣởng rất lớn đến chất lƣợng cũng nhƣ hiệu quả của toàn bộ quá trình khai
phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD).
1.1.4. Các nhiệm vụ của khai phá dữ liệu
Nhìn chung, mục đích chính của khai phá dữ liệu là dự đốn (prediction) và
mơ tả (description). Dự đoán là việc sử dụng các biến hoặc các trƣờng trong cơ sở
dữ liệu để đƣa ra dự đoán về những giá trị chƣa biết hoặc những giá trị chờ đợi
trong tƣơng lai. Mô tả tập trung vào việc tìm kiếm các mẫu mơ tả dữ liệu mà con
ngƣời có thể hiểu đƣợc.
Để đạt đƣợc hai mục đích này, nhiệm vụ chính của khai phá dữ liệu gồm:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên


/>

9

Phân lớp (Classification), hồi quy (Regression), phân nhóm (Clustering), tóm
tắt (Summarization), mơ hình hố phụ thuộc (Dependency modeling), phát hiện sự
thay đổi và lạc hƣớng (Change and deviation detection).
Phân lớp là phân loại một mẫu dữ liệu vào một trong số các lớp đã xác định.
Hồi quy là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đốn có
giá trị thực (real -valued prediction variable). Phân nhóm là việc mơ tả chung để tìm
ra tập xác định các nhóm hay các loại để mơ tả dữ liệu. Tổng kết liên quan đến các
phƣơng pháp tìm kiếm mơ tả tóm tắt cho một tập con dữ liệu. Mơ hình hố phụ
thuộc bao gồm việc tìm kiếm một mơ hình mơ tả sự phụ thuộc đáng kể giữa các
biến. Phát hiện sự thay đổi và lạc hƣớng bao gồm khai thác những thay đổi đáng kể
trong dữ liệu từ các giá trị chuẩn hoặc đƣợc đo trƣớc đó.[3]
Trong các phƣơng pháp trên, phân nhóm đƣợc sử dụng rộng rãi nhất và đôi
khi đƣợc coi là tiền xử lý dữ liệu cho những phƣơng pháp khác. Vì thế khi cần xây
dựng một ứng dụng cho KDD vào thực tế vấn đề đầu tiên ngƣời ta phải quan tâm
tới là chia dữ liệu thành từng nhóm. Việc phân nhóm giúp cho chúng ta có cái nhìn
tổng quan hơn về từng khối dữ liệu. Đặc biệt khi việc phân nhóm tốt, thời gian xem
xét cơ sở dữ liệu đƣợc giảm xuống bởi vì chúng ta khơng nhất thiết phải tìm kiếm
trong tồn bộ cơ sở dữ liệu mà chỉ phải tìm kiếm ở một lớp (nhóm) các dữ liệu
trong cơ sở dữ liệu lớn.
1.2. Phân nhóm (Clustering) và các cách tiếp cận chính
1.2.1. Phân nhóm và các ứng dụng
a. Khái niệm
Phân nhóm (clustering) là q trình nhóm một tập các đối tƣợng vật lý hoặc
trừu tƣợng thành các nhóm hay các lớp đối tƣợng tƣơng tự nhau. Một lớp (cluster)
là một tập các đối tƣợng dữ liệu trong đó các đối tƣợng trong cùng một lớp có sự
tƣơng tự hoặc giống nhau và ít tƣơng tự hoặc khác nhau so với các đối tƣợng thuộc

lớp khác. độ tƣơng tự đƣợc xác định theo một tiêu chuẩn nào đó, tuỳ thuộc vào từng
ứng dụng cụ thể và đƣợc xác định trƣớc.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

10

Khơng giống nhƣ trong q trình phân loại (classification), ta thƣờng biết
trƣớc tính chất hay đặc điểm của các đối tƣợng trong cùng một lớp và dựa vào đó để
ấn định một đối tƣợng mới vào lớp của nó. Thay vào đó, trong q trình phân nhóm
ta khơng hề biết trƣớc tính chất của các lớp mà phải dựa vào mối quan hệ giữa các
đối tƣợng để tìm ra sự giống nhau giữa các đối tƣợng theo một độ đo nào đó đặc
trƣng cho mỗi lớp.
Một ví dụ cho việc phân nhóm để tìm hiểu về các vì sao và nhiệt độ của nó.
Biểu đồ trên hình 1.2 đƣợc gọi là biểu đồ Hertzsprung-Russell với trục tung là độ
sáng và trục hồnh là nhiệt độ (theo độ K).

Hình 1.2: Biểu đồ Hertzsprung-Russell
Có thể thấy đƣợc rằng những ngơi sao trong biểu đồ thuộc vào một trong 3
lớp và trong mỗi lớp mối quan hệ giữa nhiệt độ và độ sáng là nhƣ nhau. Giữa các
lớp khác nhau mối quan hệ đó cũng khác nhau. [4]
b. Các ứng dụng của phân nhóm
Đây là một hoạt động quan trọng của con ngƣời. Khi còn bé, con ngƣời học
cách phân biệt giữa các đồ vật, giữa động vật và thực vật bằng cách liên tục thay đổi
nhận thức trong quan niệm phân chia các đối tƣợng dựa vào mối tƣơng quan giữa
chúng. Việc phân tích lớp đã đƣợc sử dụng rộng rãi trong các ứng dụng của nhiều
lĩnh vực, bao gồm nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh và phân tích thị
trƣờng. Trong kinh doanh, phân nhóm có thể giúp các nhà nghiên cứu thị trƣờng

phát hiện đƣợc các nhóm khách hàng khác nhau và đặc tính của từng nhóm khách
hàng dựa vào dữ liệu mua bán. Trong sinh học, phân nhóm đƣợc dùng để chia nhóm
các lồi thực vật và động vật, phân loại gen có chức năng tƣơng tự nhau và có đƣợc
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

11

những thông tin chi tiết hơn về cấu trúc các vùng dân cƣ. Phân nhóm cũng giúp cho
việc nhận dạng các mẫu đất giống nhau dựa trên cơ sở dữ liệu quan sát trái đất,
phân chia các nhóm nhà trong thành phố theo các tiêu chí nhƣ giá trị, vị trí địa lý
của ngơi nhà. Đồng thời phân nhóm cịn sử dụng để phân chia các nhóm tài liệu trên
Web dựa vào nội dung thơng tin.
Với vai trị là chức năng trong khai phá dữ liệu, phân tích lớp có thể sử dụng
nhƣ là một công cụ độc lập để thu thập thông tin về sự phân bố dữ liệu, để quan sát
các đặc tính của một lớp nhờ đó tập trung đƣợc vào từng lớp cụ thể cho các bƣớc
phân tích sau. Ngồi ra, phân nhóm cũng là một bƣớc tiền xử lý dữ liệu cho nhiều
thuật toán nhƣ là phát hiện các đặc tính và phân loại dữ liệu trong đó các thuật tốn
này thƣờng địi hỏi thực hiện trên các lớp đã đƣợc phát hiện.
Phân nhóm khơng bao giờ đƣợc sử dụng độc lập mà nó thƣờng đƣợc sử dụng
kèm với các phƣơng pháp khác. Khi một cách phân nhóm đƣợc đƣa ra cũng phải có
một phƣơng pháp áp dụng trên các lớp đó để đƣa ra đƣợc ý nghĩa của lớp đó.[4]
1.2.2. Các cách tiếp cận chính
Có rất nhiều các thuật tốn phân nhóm khác nhau, việc chọn lựa một thuật
tốn thích hợp phụ thuộc vào kiểu dữ liệu cần thực hiện cũng nhƣ là mục đích của
ứng dụng. Tuy nhiên các kỹ thuật phân nhóm đƣợc chia thành các cách tiếp cận
chính sau: Phƣơng pháp phân hoạch, phƣơng pháp phân cấp, phƣơng pháp dựa vào
mật độ, phƣơng pháp chia lƣới, phƣơng pháp dựa vào mô hình.
a. Phƣơng pháp phân hoạch (Partioning methods)

Ý tƣởng chính của kỹ thuật này phƣơng pháp phân hoạch là xác định số
nhóm (lớp) trƣớc và xác định ln tính chất của từng lớp. Sau đó với mỗi một điểm
dữ liệu tìm cách đƣa điểm dữ liệu đó vào lớp thích hợp nhất. Các thuật tốn điển
hình là: K-MEANS, K-MEDOID, CLARANS,...
Thuật tốn phân hoạch K-MEANS [11]
Thuật tốn phân nhóm K-MEANS là một phƣơng pháp đƣợc sử dụng rất
rộng rãi trong thực tế và nó có thể đƣợc biến đổi để thích hợp cho từng bài toán cụ
thể. Phƣơng pháp này đƣợc J. B. MacQueen đƣa ra vào năm 1967.
Thuật toán K-MEANS bao gồm các bước sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

12

Bƣớc 1: Chọn k điểm dữ liệu làm điểm tâm (center) hay nhân (seed) (ví dụ
nhƣ thuật tốn MacQueen là lấy k điểm dữ liệu đầu tiên). Trong những trƣờng hợp
tổng quát, việc chọn nhân là những điểm có khoảng cách khơng gian giữa chúng lớn
có thể đáp ứng đƣợc việc phân nhóm tốt hơn.
Bƣớc 2: Xác định các điểm dữ liệu còn lại vào các lớp sao cho việc chia đó
là thích hợp nhất. Điều đó có thể thực hiện một cách đơn giản bằng cách chia điểm
dữ liệu đó vào lớp nào gần với nó nhất. Khoảng cách đó đƣợc đo bằng chính
khoảng cách từ điểm đó tới nhân của lớp.
Bƣớc 3: Tính lại điểm tâm của các lớp. Một cách đơn giản để tính lại điểm
tâm của lớp là xác định trung bình cộng của tất cả các điểm trong lớp.
Lặp lại quá trình trên bắt đầu từ bƣớc 2 cho đến khi khơng có sự thay đổi về lớp
của các điểm dữ liệu (nghĩa là điểm tâm sẽ không thay đổi trong một sai số cho phép).
Có thể mơ tả thuật tốn K-means nhƣ sau:
Đầu vào:
Tập X = {x1, x2, . . ., xn} Rm

số lƣợng các nhóm k cần phân chia
Đầu ra: c1, c2, . . ., ck là các lớp.
Thuật toán:
Chọn k điểm nhân s1, s2, . . ., sk.
While khơng có thay đổi do
For all xi do
Đƣa xi vào lớp cj nếu sl d(xi, sj)

d(xi, sl).// d: hàm khoảng cách

end
for all si do// cập nhật lại các điểm tâm
si = (ci)// : hàm tính độ trung bình
end
end
Thuật tốn phân hoạch CLARANS [4]
Thuật tốn CLARANS (Clustering Large Applications based on Randomized
Search) là sự cải tiến của thuật tốn K-MEANS với việc tìm k điểm nhân đƣợc xác
định một cách ngẫu nhiên và thuật toán tìm biên đã làm tăng hiệu quả của việc phân
nhóm và do vậy thuật toán này thƣờng đƣợc sử dụng khi xử lý dữ liệu lớn. Để có
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

13

đƣợc một chƣơng trình hiệu quả về thời gian thực hiện thuật tốn CLARANS đã có
những sửa đổi sau:
1. Một lớp chỉ cần tính lại tâm nếu nhƣ có sự thêm hoặc bớt điểm vào lớp và
cách tính tâm đó có thể đƣợc xác định nhƣ sau:

 Khi thêm một điểm (xp, yp) vào lớp
x New

(n * x oldt

x p ) /(n 1)

y New

(n * y oldt

y p ) /(n 1)

 Khi bớt một điểm (xp, yp) trong lớp
x New

(n * x oldt

x p ) /(n 1)

y New

(n * y oldt

y p ) /(n 1)

với n là số điểm trong lớp, (xold, yold) là tâm cũ và (xNew, yNew) là tâm mới.
2. Khi có một tâm của một lớp thay đổi
 Đối với những điểm trong lớp nếu khoảng cách từ điểm đó tới tâm mới
lớn hơn khoảng cách đến tâm cũ thì kiểm tra xem có thể chuyển điểm đó sang lớp

khác hay khơng. Nếu có thể, thực hiện việc chuyển.
 Đối với những điểm ngoài lớp, nếu khoảng cách từ điểm đó tới tâm mới ngắn
hơn khoảng cách đến tâm hiện tại thì thực hiện việc chuyển điểm đó tới lớp mới.
Ƣu điểm của thuật tốn K-MEANS (hoặc thuật toán CLARANS) là rất đơn
giản, dễ hiểu và dễ áp dụng. Tuy nhiên, nhƣợc điểm của K-MEANS (hay
CLARANS) là tốc độ khi áp dụng với cơ sở dữ liệu lớn. Thêm vào nữa, những thuật
tốn trên khơng thể làm việc với cơ sở dữ liệu có tồn tại dữ liệu nhiễu.
b. Phƣơng pháp phân cấp (Hierarchical methods)
Phƣơng pháp phân cấp thực hiện bằng cách nhóm các đối tƣợng dữ liệu trên
cây phân cấp. Phƣơng pháp phân nhóm theo phân cấp đƣợc chia làm hai loại đó là
phƣơng pháp phân nhóm theo kiểu từ dƣới lên (bottom up) và phƣơng pháp phân
nhóm từ trên xuống (top down). Chất lƣợng và hiệu quả của phƣơng pháp tùy thuộc
vào quyết định ghép hoặc chia lớp.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

14

 Phân nhóm theo phƣơng pháp từ dƣới lên
Phân nhóm theo phƣơng pháp từ dƣới lên dựa vào độ đo khoảng cách giữa hai
lớp ở mỗi bƣớc để quyết định ghép hai lớp đó hay khơng. Khởi tạo số lớp bằng số
điểm dữ liệu, mỗi một lớp chỉ có duy nhất một điểm dữ liệu (nếu cơ sở dữ liệu có N
điểm dữ liệu thì ban đầu sẽ có N lớp). Sau đó, tại một bƣớc ghép hai lớp có khoảng
cách nhỏ nhất (hay mức độ tƣơng tự giữa chúng là lớn nhất). Thực hiện nhƣ vậy
N-1 bƣớc, chúng ta đƣợc duy nhất một lớp.
Lớp sau khi thực hiện N-1 bƣớc đƣợc tạo thành gọi là lớp gốc. Cùng với cây
mới tạo đƣợc chúng ta có thể chọn k lớp thích hợp nhất cho bài tốn bằng cách cho
vào một tham số để kết thúc việc ghép lớp. Cách làm này đƣa đến một bài tốn nhỏ

hơn đó là phải đo đƣợc khoảng cách giữa hai lớp. Hình 1.3 mơ tả việc phân nhóm
có thứ bậc theo kiểu bottom-up có hình dạng nhƣ một cây đƣợc xây dựng dần từ
dƣới lên gốc.
 Phân nhóm theo phƣơng pháp trên xuống
Phân nhóm theo phƣơng pháp trên xuống thực hiện quá trình ngƣợc lại với
phƣơng pháp trƣớc, tại mỗi bƣớc sẽ quyết định chia một lớp hay khơng. Khởi tạo
ban đầu chỉ có một lớp gồm tất cả các điểm dữ liệu trong cơ sở dữ liệu, quá trình
thực hiện tƣơng tự nhƣ việc xây dựng một cây bắt đầu từ gốc. Chúng ta tìm cách
chia mỗi nút gốc (nút cha) thành hai nút con (trong các thuật toán mở rộng, số nút
con tách ra của một nút có thể lớn hơn hai). Quá trình chia đƣợc thực hiện cho đến
khi thoả mãn điều kiện về lớp đƣa vào hoặc đến khi mỗi lớp chỉ gồm 1 đối tƣợng.

Hình 1.3: Mơ tả cách phân nhóm theo phƣơng pháp từ dƣới lên
và từ trên xuống
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>