0

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Hà Nội – 2014
NGUYỄN THỊ KHÁNH LINH

PHÂN CỤM DỮ LIỆU ĐỊA LÝ VÀ ÁP DỤNG TRONG
PHÂN TÍCH MỘT SỐ CHỈ SỐ KINH TẾ XÃ HỘI CỦA
CÁC ĐỊA PHƯƠNG Ở VIỆT NAM

Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60480101
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Nguyễn Đình Hóa

Hà Nội - 2015


1

LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của tôi và không sao chép của bất
kỳ ai. Những kiến thức trình bày trong luận văn là do tôi tìm hiểu, nghiên cứu và trình
bày lại theo cách hiểu. Trong quá trình làm luận văn, tôi có tham khảo các tài liệu có
liên quan và đã ghi rõ nguồn tài liệu tham khảo.
Hà Nội, ngày

tháng năm 2015

Học viên

Nguyễn Thị Khánh Linh


2

LỜI CẢM ƠN
Lời đầu tiên, em xin trân trọng gửi lời cảm ơn sâu sắc đến thầy giáo PGS.TS.
Nguyễn Đình Hóa – Viện CNTT – Trường Đại học Quốc gia Hà Nội và thầy giáo TS.
Lê Hoàng Sơn – ĐH Khoa học Tự nhiên đã trực tiếp hướng dẫn và tận tình giúp đỡ em
trong suốt thời gian thực hiện luận văn.
Thứ hai, em xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong
khoa Công nghệ thông tin, trường Đại học Công nghệ Hà Nội, Đại học Quốc gia Hà Nội
đã dạy bảo tận tình em trong suốt quá trình em học tập tại khoa.
Trong quá trình thực hiện luận văn, em cũng nhận được sự giúp đỡ rất nhiều từ
các thầy cô, các anh chị và các bạn tại Trung tâm Tính toán Hiệu năng cao, trường Đại
học Khoa học tự nhiên. Luận văn này được thực hiện dưới sự tài trợ của đề tài cấp
ĐHQG, mã số: QG.14.60.
Cuối cùng, em xin gửi lời cảm ơn tới gia đình, bạn bè, đồng nghiệp, những người
đã luôn bên cạnh em để động viên, giúp đỡ và tạo điều kiện tốt nhất để em có thể hoàn
thành luận văn.
Hà Nội, ngày

tháng năm 2015

Học viên


Nguyễn Thị Khánh Linh


3

MỤC LỤC
LỜI CAM ĐOAN ..............................................................................................

1

LỜI CẢM ƠN....................................................................................................

2

MỤC LỤC .........................................................................................................

3

DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT......................................

5

DANH MỤC CÁC HÌNH VẼ............................................................................

7

DANH MỤC CÁC BẢNG BIẾU.......................................................................

8


MỞ ĐẦU ...........................................................................................................

9

CHƯƠNG 1: DỮ LIỆU ĐỊA LÝ VÀ PHÂN CỤM DỮ LIỆU ĐỊA LÝ ........

10

1.1 GIS và dữ liệu địa lý .....................................................................................10
1.1.1 GIS ........................................................................................................10
1.1.2 Dữ liệu địa lý ......................................................................................... 11
1.1.2.1 Dữ liệu không gian............................................................................... 11
1.1.2.2 Dữ liệu thuộc tính ................................................................................12
1.2 Tổng quan về phân cụm dữ liệu địa lý .......................................................... 14
1.2.1 Khái niệm về phân cụm dữ liệu ..............................................................14
1.2.2 Ứng dụng của phân cụm dữ liệu địa lý ................................................... 15
1.2.3 Các thuật toán phân cụm dữ liệu địa lý ................................................... 15
1.2.3.1 Thuật toán FCM ...................................................................................16
1.2.3.2 Thuật toán NE ......................................................................................18
1.2.3.3 Thuật toán FGWC ................................................................................19
1.2.3.4 Thuật toán CFGWC .............................................................................21
1.2.3.5 Thuật toán CFGWC 2 ..........................................................................22
1.2.3.6 Thuật toán IPFGWC ............................................................................26
1.2.3.7 Thuật toán MIPFGWC .........................................................................27
1.3 Kết luận ........................................................................................................29

CHƯƠNG 2: XÂY DỰNG ỨNG DỤNG PHÂN CỤM DỮ LIỆU ĐỊA LÝ
VỚI PHẦN MỀM MÃ NGUỒN MỞ MAPWINDOW................................................. 30
2.1


MapWindow và các plug-in để mở rộng chức năng................................................. 30


4
2.1.1

Các phần mềm GIS ................................................................................ 30

2.1.2

Phần mềm GIS MapWindow.................................................................. 31

2.1.3

Xây dựng và sử dụng plug-in với MapWindow ...................................... 32

2.1.3.1 Quy tắc chung ......................................................................................32
2.1.3.2 Các bước cụ thể ...................................................................................33
2.2

Phân tích thiết kế plug-in để thực hiện các thuật toán phân cụm ................... 34

2.2.1

Mô hình ca sử dụng ................................................................................ 35

2.2.1.1 Mô hình ca sử dụng tổng thể của plug-in ..............................................35
2.2.1.2 Mô hình ca sử dụng chức năng phân cụm dữ liệu ................................. 35
2.2.2


Mô tả ca sử dụng .................................................................................... 36

2.2.3

Biểu đồ lớp phân tích ............................................................................. 37

2.2.4

Thiết kế lớp ............................................................................................ 37

2.2.4.1 Lớp giao diện .......................................................................................37
2.2.4.2 Lớp điều khiển .....................................................................................39
2.3

Kết luận ........................................................................................................40

CHƯƠNG 3: THỰC NGHIỆM VÀ ĐÁNH GIÁ .......................................... 41
3.1

Dữ liệu thực nghiệm .....................................................................................41

3.1.1

Chuẩn bị dữ liệu không gian .................................................................. 41

3.1.2

Chuẩn bị bộ dữ liệu phân cụm ................................................................ 41

3.2


Các kịch bản chạy thử...................................................................................44

3.3

Một số kết quả khi chạy chương trình ........................................................... 45

3.3.1

Kết quả khi chạy các thuật toán phân cụm khác nhau cho cùng một tập dữ

liệu chuyên đề ....................................................................................................

46

3.3.2

Kết quả khi chạy nhiều chuyên đề với một thuật toán ............................. 52

3.3.3

Kết quả khi chạy phân cụm đồng thời nhiều thuộc tính .......................... 56

3.4

Kết luận ........................................................................................................59

KẾT LUẬN...................................................................................................... 61
TÀI LIỆU THAM KHẢO................................................................................ 62



5

DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT
STT

Từ viết tắt/thuật

Từ tiếng Anh

Ý nghĩa
Trí tuệ nhân tạo

ngữ
1

AI

Artifical Intelligence

3

GIS

Geographical

4

NE


Information Hệ thống thông tin địa

System

lý

Neighbourhood Effects

Thuật toán hiệu

ứng

vùng lân cận
5

FCM

Fuzzy C-means

Thuật toán phân

cụm

mờ
6

FGWC

Fuzzy


Geographically Thuật toán phân

Weight Clustering

cụm

dữ liệu theo trọng số
địa lý

7

CFGWC

Context

Fuzzy Thuật toán phân

Geographically

cụm

Weight địa lý kết hợp ngữ cảnh

Clustering
8

IPFGWC

Intuitionistic
Fuzzy


9

MIPFGWC

Possiblistic Thuật toán phân

cụm

Geographically địa lý trên tập mờ trực

Weighted Clustering

cảm

Modification Intuitionistic

Thuật toán phân

Possiblistic

cụm

Fuzzy địa lý hiệu chỉnh trên

Geographically

Weighted tập mờ trực cảm

Clustering

10

KMIPFGWC

Kernel-based Modification
Intuitionistic
Fuzzy

CSDL

12

UC

Geographically tập mờ trực cảm sử
dụng hàm nhân
Cơ sở dữ liệu

Usecase

cụm

Possiblistic địa lý hiệu chỉnh trên

Weighted Clustering
11

Thuật toán phân

Ca sử dụng



6

13

SIM

Spatial Interaction Model

Mô

hình

tương

tác

không gian
14

SIM

2

Spatial
Interaction
Modification Model

- Mô hình tương tác hiệu chỉnh không gian



7

DANH MỤC CÁC HÌNH VẼ
Hình 1.1. Ví dụ về dữ liệu thuộc tính ..............................................................

13

Hình 1.2. Dữ liệu địa lý ...................................................................................

14

Hình 2.1. Mô hình ca sử dụng tổng quan của plug-in ...................................... 35
Hình 2.2. Mô hình usecase chức năng phân cụm ............................................. 35
Hình 2.3: Biểu đồ lớp của plug-in ...................................................................

37

Hình 2.4. Lớp giao diện chính của plug-in ......................................................

38

Hình 2.5. Lớp giao diện của chức năng phân cụm ........................................... 38
Hình 2.6. Lớp giao diện tải chuyên đề .............................................................

38

Hình 2.7. Lớp giao diện nhập tham số thuật toán ............................................


39

Hình 2.8. Lớp điều khiển tính toán phân cụm .................................................. 39
Hình 2.9. Lớp điều khiển cập nhật dữ liệu vào bảng thuộc tính ....................... 40
Hình 2.10. Lớp điều khiển Reset bảng thuộc tính ............................................ 40
Hình 3.1. Dữ liệu chuyên đề ở dạng file .csv ................................................... 42
Hình 3.2. Dữ liệu chuyên đề ở dạng file .txt .................................................... 42
Hình 3.3. Giao diện chương trình khi tải layer và bật plug-in .......................... 45
Hình 3.4. Giao diện in bản đồ .........................................................................

46

Hình 3.5. Kết quả khi chạy thuật toán MIPFGWC trên dữ liệu “Tổng mức bán
lẻ hàng hóa và dịch vụ” với số cụm bằng 4. ...............................................................

52


8

DANH MỤC CÁC BẢNG BIẾU
Bảng 3.1: Kết quả chạy phân cụm với các thuật toán trên dữ liệu “Tổng mức
bán lẻ hàng hóa và dịch vụ”........................................................................................................... 49
Bảng 3.2: Thời gian chạy các thuật toán trên các bộ dữ liệu với tham
số

............................................................................................ 50
Bảng 3.3:Thời gian chạy các thuật toán trên các bộ dữ liệu với tham

số


............................................................................................ 51
Bảng 3.4:Thời gian chạy các thuật toán trên các bộ dữ liệu với tham

số

............................................................................................ 51
Bảng 3.5: Kết quả phân cụm thuật toán MIPFGWC chạy trên 3 chuyên đề:

“Tổng mức bán lẻ hàng hóa và dịch vụ”, “Giá trị sản xuất xây dựng”, “Giá trị sản xuất
công nghiệp” giai đoạn 2005-2013.............................................................................................. 55
Bảng 3.6: Kết quả phân cụm đồng thời nhiều thuộc tính khi thay đổi tỉ lệ giữa
các trọng số........................................................................................................................................ 59


9

MỞ ĐẦU
Hệ thống thông tin địa lý (GIS) là một ứng dụng rất có giá trị và là công cụ trợ
giúp quyết định trong nhiều hoạt động kinh tế - xã hội, quốc phòng của nhiều quốc gia
trên thế giới. Hiện nay, GIS được phát triển và ứng dụng ngày càng nhiều tại Việt Nam.
Trong sự phát triển của đất nước ta hiện nay, việc tổ chức quản lý thông tin địa lý một
cách tổng thể có có vai trò rất quan trọng trong việc sử dụng có hiệu quả hơn nguồn tài
nguyên của đất nước. GIS giúp các cơ quan chính phủ có cái nhìn khách quan hơn về
hiện trạng các thực thể tự nhiên, kinh tế xã hội thông qua việc xử lý các dữ liệu không
gian và dữ liệu thuộc tính.
Các dữ liệu về kinh tế, xã hội, môi trường… đều gắn với các địa phương, tức là
các dữ liệu địa lý, và nhiều bài toán thực tế đòi hỏi phải khai phá những dữ liệu này. Có
nhiều phương pháp khai phá dữ liệu, trong đó phân cụm là một phương pháp được sử
dụng khá nhiều. Hiện nay đã có nhiều cách tiếp cận thuật toán phân cụm khác nhau như:

dựa trên phân hoạch, phân cấp, dựa trên lưới, dựa trên mật độ, dựa trên mô hình, dựa
trên đồ thị… Phân cụm dữ liệu địa lý là một hướng nghiên cứu nhiều triển vọng.
Đề tài nghiên cứu hướng tới các thuật toán phân cụm dữ liệu không gian. Trên cơ
sở tìm hiểu nắm vững kỹ thuật xử lý dữ liệu không gian và vận dụng được vào chương
trình thực hiện thuật toán phân cụm dữ liệu không gian, chúng tôi sẽ thử áp dụng với
các dữ liệu thực tế, phân tích diễn giải ý nghĩa kết quả phân cụm.
Bố cục của luận văn gồm 3 chương:
Chương 1: Trình bày các khái niệm chung về GIS và dữ liệu địa lý, các thuật
toán sử dụng trong phân cụm dữ liệu địa lý.
Chương 2: Trình bày cách thức xây dựng ứng dụng phân cụm dữ liệu và thể hiện
một số chỉ tiêu kinh tế xã hội của các địa phương ở Việt Nam dựa trên phần mềm mã
nguồn mở MapWindow
Chương 3: Chạy chương trình trên số liệu thực tế thu thập được với từng thuật
toán, so sánh kết quả từng thuật toán. Đánh giá, phân tích một số kết quả đầu ra của các
thuật toán phân cụm.


10

CHƯƠNG 1:

DỮ LIỆU ĐỊA LÝ VÀ PHÂN CỤM DỮ LIỆU
ĐỊA LÝ

1.1 GIS và dữ liệu địa lý
1.1.1 GIS
Từ lâu bản đồ luôn là một công cụ thông tin quen thuộc đối với loài người. Trong
quá trình phát triển kinh tế kĩ thuật, bản đồ luôn được cải tiến sao cho ngày càng đầy đủ
thông tin và chính xác hơn. Với sự đa dạng của các loại bản đồ trong việc thể hiện các
đối tượng khác nhau trên bề mặt trái đất, các nhà quy hoạch nhận thức được sự cần thiết

trong xử lý đồng thời nhiều hơn một bản đồ. Các mô hình đồ họa cổ điển xử lý thông tin
bản đồ gặp rất nhiều khó khăn trong xử lý đồng thời dữ liệu không gian và dữ liệu thuộc
tính. Điều này đã dẫn đến sự phát triển các phương pháp và kỹ thuật xử lý tổng hợp
thông tin nhằm phục vụ tốt hơn cho công tác quy hoạch và ra quyết định. [1]
Trong những năm đầu thập kỉ 60 (1963-1964) các nhà khoa học ở Canada đã cho
ra đời hệ thông tin địa lý. Hệ thống thông tin địa lý kế thừa mọi thành tựu trong ngành
bản đồ cả về ý tưởng lẫn thành tựu của kỹ thuật bản đồ. Hệ thông tin địa lý bắt đầu hoạt
động bằng việc thu thập dữ liệu theo định hướng tuỳ thuộc vào mục tiêu đặt ra.
Cùng với Canada, các trường đại học tại Mỹ cũng tiến hành nghiên cứu và xây
dựng hệ thống thông tin địa lý và càng ngày nhu cầu sử dụng, nghiên cứu hệ thống
thông tin địa lý càng được quan tâm nhiều hơn.
Hệ thông tin địa lý (Geographical Information System – GIS) là tập hợp các công
cụ để thu thập, lưu trữ, chỉnh sửa, truy cập, phân tích và cập nhật các thông tin địa lý
cho một mục đích chuyên biệt.
Ngoài ra cũng có nhiều định nghĩa khác về GIS [1]:
GIS là công cụ trên cơ sở nền máy tính để lập bản đồ và phân tích những hiện
tượng đang tồn tại và các sự kiện xảy ra trên trái đất (Environmental System Research
Institute ESRI – Mỹ).
GIS là hệ thống phần cứng, phần mềm và các thủ tục được thiết kế nhằm thu
thập, quản lý, xử lý, phân tích, mô hình hóa và hiển thị các dữ liệu quy chiếu không gian
để giải quyết các vấn đề quản lý và lập kế hoạch (National Center for Geography
Information and Analysis NCGIA – Mỹ).


11
GIS là một tập hợp các nguyên lý, phương pháp, dụng cụ và dữ liệu quy chiếu
không gian được sử dụng để nhập, lưu trữ, chuyển đổi, phân tích, lập mô hình, mô
phỏng và lập bản đồ các hiện tượng, sự kiện trên trái đất, nhằm sản sinh các thông tin
thiết thực hổ trợ cho việc ra quyết định (Thériault – Canada).
Hệ thống thông tin địa lý bao gồm các phần chính sau:

1. Hệ thống thiết bị phần cứng bao gồm máy tính hoặc hệ mạng máy tính, các
thiết bị đầu vào, các thiết bị đầu ra.
2. Hệ thống phần mềm bao gồm phần mềm vẽ bản đồ, phần mềm quản trị, phần
mềm ứng dụng.
3. Hệ thống thông tin đầu vào và hệ thống cập nhật thông tin.
4. Hệ thống cơ sở dữ liệu bao gồm các dữ liệu địa lý và các dữ liệu thuộc tính
(các dữ liệu chữ - số, dữ liệu multimedia, v.v.) và mối quan hệ giữa hai loại dữ liệu này.
5. Hệ thống hiển thị thông tin và giao diện với người sử dụng đòi hỏi những đặc
thù riêng về độ chính xác (hệ tọa độ, quy chiếu không gian).
1.1.2 Dữ liệu địa lý
Dữ liệu địa lý là dữ liệu bao gồm dữ liệu không gian và dữ liệu thuộc tính (còn
gọi là dữ liệu phi không gian) được kết hợp với nhau một cách tương ứng. Dữ liệu địa lý
có thể là các bản đồ số trên máy vi tính, các mô hình mô phỏng hình dáng bề mặt trái
đất, các cơ sở dữ liệu ảnh bề mặt trái đất.
1.1.2.1 Dữ liệu không gian
Dữ liệu không gian là những mô tả số của các đối tượng thực tế được thể hiện
hình ảnh bản đồ. Đó có thể là thửa đất, con đường, sông ngòi, hồ ao, rừng núi, tòa nhà,
sân bay, bến cảng ….. Chúng bao gồm toạ độ, quy luật và các ký hiệu dùng để thể
hiện thành một hình ảnh cụ thể trên bản đồ. Hệ thống thông tin địa lý dùng các dữ liệu
không gian để tạo ra một bản đồ hay hình ảnh bản đồ trên màn hình hoặc trên giấy
thông qua thiết bị ngoại vi, v.v.
Có hai mô hình dữ liệu không gian được sử dụng đồng thời trong hệ thống thông
tin địa lý, là mô hình vector và mô hình raster. Mỗi mô hình có những ưu điểm và nhược
điểm riêng.
Mô hình raster: Có thể hiểu đơn giản là một “ảnh” chứa các thông tin về một
chuyên đề. Nó mô hình hóa bề mặt trái đất và các đối tượng trên đó bằng một lưới (đều
hoặc không đều) gồm các hàng và cột. Những phần tử nhỏ này gọi là những pixel


12

hay cell. Giá trị của pixel là thuộc tính của đối tượng. Kích thước pixel càng nhỏ thì đối
tượng càng được mô tả chính xác. Một mặt phẳng chứa đầy các pixel tạo thành raster.
Mô hình này thường được áp dụng để mô tả các sự vật, hiện tượng phân bố liên tục
trong không gian, dùng để lưu giữ thông tin dạng ảnh (ảnh mặt đất, hàng không, vũ
trụ...). Một số dạng mô hình biểu diễn bề mặt như DEM (Digital Elevation Model),
DTM (Digital Terrain Model), TIN (Triangulated Irregular Network) trong CSDL cũng
thuộc dạng raster .
Ưu điểm của dữ liệu dạng raster là dễ thực hiện các chức năng xử lý và phân
tích. Tốc độ tính toán nhanh, thực hiện các phép toán bản đồ dễ dàng. Dễ dàng liên kết
với dữ liệu viễn thám. Mô hình raster có nhược điểm là kém chính xác về vị trí không
gian của đối tượng. Khi độ phân giải càng thấp (kích thước pixel lớn) thì sự sai lệch này
càng tăng
Mô hình vector: mô tả vị trí và phạm vi của các đối tượng không gian bằng tọa
độ cùng các kết hợp hình học gồm các điểm nút, các cung trên đường biên, các vùng
mặt phẳng và quan hệ giữa chúng. Về mặt hình học, các đối tượng được phân biệt thành
3 dạng: đối tượng dạng điểm (point), đối tượng dạng đường (line) và đối tượng dạng
vùng (region hay polygon). Điểm được xác định bằng một cặp tọa độ X,Y. Đường là
một chuỗi các cặp tọa độ X,Y liên tục. Vùng là khoảng không gian được giới hạn bởi
một tập hợp các cặp tọa độ X,Y trong đó điểm đầu và điểm cuối trùng nhau. Với đối
tượng vùng, mô hình vector phản ảnh đường bao.
Dữ liệu vector có ưu điểm là vị trí của các đối tượng được định vị chính xác
(nhất là các đối tượng điểm, đường và đường bao). Điều này giúp cho người sử dụng dễ
dàng biên tập bản đồ, chỉnh sửa, in ấn. Tuy nhiên mô hình dữ liệu vector có nhược điểm
là phức tạp khi thực hiện các phép chồng xếp bản đồ.
Dữ liệu vector có thể được lưu trữ trong máy tính theo các khuôn dạng tệp khác
nhau và các hệ thông tin địa lý có thể hỗ trợ/ không hỗ trợ một số khuôn dạng dữ liệu
không gian nhất định. Tuy nhiên, khuôn dạng shape (*.shp) được coi như chuẩn thực tế
và mọi hệ thông tin địa lý đều hỗ trợ khuôn dạng này.
1.1.2.2 Dữ liệu thuộc tính
Dữ liệu thuộc tính diễn tả các đặc tính của các đối tượng thực tế được thể hiện

trên bản đồ. Dữ liệu thuộc tính có thể là định tính - mô tả chất lượng (qualitative) hay là
định lượng (quantative). Dữ liệu định lượng ví dụ như chiều dài đoạn đường, diện


13
tích thửa đất, độ sâu hồ nước, dân số của một đơn vị hành chính (xã, huyện, tỉnh..) cụ
thể. Dữ liệu định tính ví dụ như xếp hạng độ màu mỡ của thửa đất, mức độ phát triển
kinh tế một tỉnh...
Về nguyên tắc, số lượng các thuộc tính của một đối tượng là không có giới hạn.
Để quản lý dữ liệu thuộc tính của các đối tượng địa lý trong CSDL, GIS đã sử dụng
phương pháp gán các giá trị thuộc tính cho các đối tượng thông qua các bảng số liệu.
Mỗi bản ghi (record) đặc trưng cho một đối tượng địa lý, mỗi cột của bảng tương ứng
với một kiểu thuộc tính của đối tượng đó.
Thông thường hệ thống thông tin địa lý có 4 loại số liệu thuộc tính:
Đặc tính của đối tượng: liên kết chặt chẽ với các thông tin không gian có thể
thực hiện câu lệnh truy vẫn và phân tích.
Số liệu hiện tượng, tham khảo địa lý: miêu tả những thông tin, các hoạt động
thuộc vị trí xác định.
Chỉ số địa lý: tên, địa chỉ, khối, phương hướng định vị, …liên quan đến các
đối tượng địa lý.
Quan hệ giữa các đối tượng trong không gian, có thể đơn giản hoặc phức tạp
(sự liên kết, khoảng tương thích, mối quan hệ đồ hình giữa các đối tượng).

Hình 1.1. Ví dụ về dữ liệu thuộc tính
Hình 1.2 là ví dụ về một số tệp dữ liệu địa lý gồm 4 tệp chính:
VNM_adm2.dbf: Dữ liệu thuộc tính lưu trong cơ sở dữ liệu dạng bdf, có thể
mở file này bằng excel
VNM_adm2.prj: File mô tả về lưới chiếu sử dụng cho bộ dữ liệu này



14
VNM_adm2.shp: File dữ liệu không gian dạng shape.
VNM_adm2.shx: Đây là dữ liệu để ánh xạ mỗi vùng không gian trong file
.shp tương ứng với từng bản ghi trong file .shx.

Hình 1.2. Dữ liệu địa lý

1.2 Tổng quan về phân cụm dữ liệu địa lý
1.2.1 Khái niệm về phân cụm dữ liệu
Phân cụm dữ liệu là một kỹ thuật 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.
Phân cụm dữ liệu là sự phân chia một tập dữ liệu lớn thành các nhóm dữ liệu mà
các đối tượng trong cùng nhóm là tương tự nhau. “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 mà các đối tượng ở mỗi nhóm đều tương tự nhau theo
một tính chất nào đó, những đối tượng có tính chất không tương tự sẽ ở nhóm khác.” [2]
Dữ liệu địa lý ngày một phát triển với lượng dữ liệu ngày càng lớn và phức tạp
hơn, đòi hỏi các nhà nghiên cứu cần có những phương pháp, kỹ thuật để phân tích và
khai phá dữ liệu hiệu quả hơn.
Trong những năm gần đây, việc nghiên cứu và khai phá dữ liệu đã có xu hướng
chuyển từ cơ sở dữ liệu quan hệ và cơ sở dữ liệu giao dịch sang cơ sở dữ liệu không
gian. Khám phá tri thức từ dữ liệu không gian có thể được thực hiện dưới nhiều hình


15
thức khác nhau như sử dụng các quy tắc đặc trưng và quyết định, trích rút và mô tả các
cấu trúc hoặc cụm nổi bật, kết hợp không gian.
1.2.2 Ứng dụng của phân cụm dữ liệu địa lý
Phân cụm dữ liệu địa lý được ứng dụng trong nhiều lĩnh vực khác nhau như:
Y tế: Xác định và khoanh vùng các ổ dịch giúp cho việc điều trị, quản lý,

phòng chống lây lan sang các khu vực khác.
Nông – lâm nghiệp: Nhận dạng các vùng đất, điều kiện địa lý phù hợp với
loại cây trồng tương ứng.
Sinh học: Phân loại động – thực vật thông qua các Gen tương đồng của
chúng.
Kinh tế: Phân cụm các nhóm khách hàng quan trọng theo từng vùng miềm.
Xã hội – phòng chống tội phạm: Khoanh vùng các khu vực là điểm nóng về
tội phạm.
1.2.3 Các thuật toán phân cụm dữ liệu địa lý
Bài toán phân cụm dữ liệu địa lý được định nghĩa như sau:
Định nghĩa 1.Cho tập dữ liệu thuộc tính X gồm N điểm dữ liệu trong không gian
r chiều. Mỗi điểm dữ liệu tương ứng với một kiểu đối tượng điểm của hệ thống Vector.

Hãy phân chia tập dữ liệu thuộc tính này thành C cụm sao cho thỏa mãn hàm mục tiêu
[2]:
N

(1)

C

ukj || X k V j ||2

J

min,

k 1 j 1

Với các ràng buộc:

ukj

[0,1]

C
u 1

kj

u

kj

V
j

(2)

.

j1

ukj (W j

V

)

(W )


j

j

Trong đó:
ukj

0,1 là độ thuộc của điểm dữ liệu thứ k vào cụm j , j

1,C ,


16

X k là điểm dữ liệu thứ k ( k 1, N ),
Vj là tâm cụm không gian thứ j ( j 1,C ),
W j là trọng số không gian của cụm j (

j 1,C ).

Khoảng cách giữa hai đối tượng x và y được tính thông qua các độ đo khoảng cách
sau:
1
q

n

Khoảng cách Minskowski:

d (x, y) | xi yi


|q

, trong đó q là số tự nhiên

i1

dương.
n

Khoảng cách Euclidean: d (x, y)(xi yi )2

, đây là trường hợp đặc biệt của

i1

khoảng cách Minskowski trong trường hợp q

2.

n

Khoảng cách Manhattan: d (x, y)

| xi

yi | , đây là trường hợp đặc biệt của

i1


khoảng cách Minskowski trong trường hợp q
d(x, y) maxn

Khoảng cách Chenbysev:

1.

| X Y |,
i1

i

của khoảng cách Minskowski trong trường hợp q

đây là trường hợp đặc biệt

i

.

1.2.3.1 Thuật toán FCM
FCM [3] là thuật toán phân cụm cho phép một phần dữ liệu có thể nằm ở một
hoặc nhiều cụm khác nhau. Phương pháp phân cụm này được Dunn xây dựng vào năm
1973 và được Bezdek cải tiến vào năm 1981, thường được sử dụng trong việc nhận dạng
mẫu.
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 .
Đầu vào:
-


J
c
Số cụm và tham số mũ m cho hàm mục tiêu :
Jukjm X k V jmin

N

C

(a)

2

k1 j1

17


Đầu ra:
-

c cụm dữ

liệu sao cho hàm mục tiêu trong (a) đạt giá trị cực tiểu.

Các bước thực hiện thuật toán:
Bước 1: Khởi tạo ma trận U (t) với t 0
Bước 2: Tính ma trận tâm V (t) bởi công thức:
N


ukim X k

V

Bước 3: Tính U (t

1)

;i 1,C

k 1

i

N

u

(1)

m

ki

bởi công thức:
1

uki
C


|| X k V

2

i

|| X V
j 1

k

|| m

; i 1, C; k 1, N

(2)

||
j

Bước 4: Nếu ||U (t 1) U (t) || thì dừng thuật toán, ngược lại thì quay lại bước 2.

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 hiệu quả,

thông thường chọn m 2 .
Độ phức tạp của thuật toán FCM tương đương với độ phức tạp của thuật toán Kmeans 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, FCM vẫn chứa đựng các nhược điểm của thuật
toán K-means trong việc xử lý đối với các phần tử ngoại lai và nhiễu trong dữ liệu.
Ưu điểm [3] của thuật toán này là đơn giản, dễ thực hiện. Nhược điểm [3] của
thuật toán là nhạy cảm với các nhiễu và phần tử ngoại lai trong dữ liệu, chưa sử dụng
đến các yếu tố địa lý.


18
1.2.3.2 Thuật toán NE
Thuật toán NE [10] là thuật toán phân cụm dữ liệu có tính đến yếu tố địa lý đầu
tiên, được đưa ra bởi Feng và Flowerdew vào năm 1998. Thuật toán này sẽ tích hợp
thêm các đặc trưng địa lý thông qua mô hình tương tác không gian (SIM). Mô tả của
thuật toán:
Đầu vào:
-

X

m

Tập dữ liệu đầu vào , số mờ
N
C
r
Số điểm dữ liệu , số cụm , số chiều
Các tham số địa lý
.
Ngưỡng
Đầu ra:


a,b, ,

C cụm dữ liệu sao cho thỏa mãn hàm mục tiêu:
Jukjm X k V jmin
N

C

(3)

2

k1 j1

Các bước thực hiện thuật toán:
Bước 1: Khởi tạo ma trận U (t) với t 0
Bước 2: Tính ma trận tâm V (t) bởi công thức:
N

V

ukim X k

;i

k1

N


i

1,C

(4)
.

ukim
k1

Bước 3: Tính U (t 1) bởi công thức:
1

uki
C

j1

|| X k

V ||

2

;i 1,C,k 1, N.

m

i


|| X k V j ||

Bước 4: Nếu ||U (t 1) U (t) || thì dừng thuật toán, ngược lại thì quay lại bước 2.

Bước 5: Hiệu chỉnh bởi các đặc trưng địa lý:

(5)


19

1

uki'uki wij

uki ;i 1,C,k 1, N
C

A

(6)

j 1

(7)

1
( pij )b

w

ij

dij

(8)

a

Trong đó, pij là khoảng cách lớn nhất giữa các điểm trong phần biên chung giữa
cụm i và cụm j , dij là khoảng cách tâm cụm i và cụm j , A là hệ số để đảm bảo tổng độ
thuộc của một phần tử vào tất cả các cụm luôn bằng 1.
Do có kết hợp các yếu tố địa lý nên chất lượng phân cụm của thuật toán NE tốt
hơn so với thuật toán FCM. Tuy nhiên, thuật toán vẫn còn một số nhược điểm [10] như:
-

Thuật toán bỏ qua các tác động của các khu vực mà không có biên chung.

-

Thuật toán loại trừ ảnh hưởng của yếu tố dân số - là một yếu tố quan trọng trong
bài toán phân cụm dữ liệu địa lý.

-

Việc hiệu chỉnh địa lý được thực hiện ở bước cuối cùng (ngoài vòng lặp) nên các
cụm không gắn chặt với yếu tố không gian.

1.2.3.3 Thuật toán FGWC
Thuật toán FGWC [4] do Mason và Jacobson xây dựng vào năm 2007 nhằm
khắc phục những hạn chế của thuật toán NE. Ý tưởng của thuật toán là tích hợp thêm

yếu tố dân cư và đưa việc cập nhật địa lý bằng mô hình SIM vào trong vòng lặp thuật
toán.
Đầu vào:
-

Số cụm c và các tham số m, cho hàm mục tiêu J ;

-

Tập dữ liệu đầu vào X , số mờ m

-

Số điểm dữ liệu N , số cụm C , số chiều r

-

Các tham số địa lý

-

Ngưỡng
Đầu ra:

-

C cụm dữ liệu sao cho thỏa mãn hàm mục tiêu:

a,b, ,


.

20


N

Jukjm

C

2

Xk Vj

min

k1 j1

(9)

Các bước thực hiện thuật toán:
Bước 1: Khởi tạo ma trận U (t) với t 0
Bước 2: Tính ma trận tâm V (t) bởi công thức:
N

ukim X k

V


;i 1,C.

k1

i

N

(10)

um

ki

Bước 3: Tính U (t 1) bởi công thức:
1

uki

|| X k

C

V ||

2

;i 1,C,k 1, N.

(11)


m

i

|| X k V j ||

j1

Bước 4: Hiệu chỉnh bởi các đặc trưng địa lý:

1

uki'uki wij

uki ;i 1,C, k 1, N.
C

A

j1

1

w

ij

(12)


(mi m j )b
dija

(13)
(14)

Trong đó, mi là dân số hay số lượng phần tử thuộc của cụm i, dij là khoảng cách
tâm cụm i và cụm j , A là hệ số để giới hạn tổng độ thuộc của một phần tử vào tất cả các
cụm luôn bằng 1.
Bước 5: Nếu U ' (t 1) U (t) thì dừng thuật toán, ngược lại thì quay lại bước 2.


21
FGWC [4] là thuật toán được sử dụng rộng rãi nhất hiện nay do nó khắc phục
được nhược điểm của thuật toán NE như xem xét các tác động của những khu vực
không có biên chung, kết hợp dân cư vào các bước thực hiện của nó và các cụm được
gắn chặt với quan hệ không gian.
Nhược điểm của thuật toán này là [4]:
-

Thời gian thực hiện thuật toán chậm.

-

Chất lượng phân cụm thu được là không cao

1.2.3.4 Thuật toán CFGWC
Thuật toán CFGWC do nhóm nghiên cứu của Tiến sỹ Lê Hoàng Sơn cùng cộng
sự đưa ra để khắc phục nhược điểm về tốc độ tính toán của thuật toán FGWC (Mason và
Jacobson).

Ý tưởng của thuật toán [7]:
Thuật toán sẽ đưa thêm một biến ngữ cảnh để thu hẹp dữ liệu gốc theo một số
điều kiện cho trước. Biến ngữ cảnh sẽ tăng tốc độ tính toán đưa ra kết quả chính xác
hơn.
Đầu vào:
-

X

m

-

Tập dữ liệu đầu vào , số mờ
N
C
r
Số điểm dữ liệu , số cụm , số chiều

-

Các tham số địa lý

-

Ngưỡng , ngữ cảnh .
Đầu ra:

-


a,b, ,
f

C

cụm dữ liệu sao cho thỏa mãn hàm mục tiêu:
Jukjm X k V jmin

N

C

(15)

2

k1 j1

Các bước thực hiện thuật toán:
Bước 1: Khởi tạo ma trận U (t) với t 0
Bước 2: Tính ma trận tâm V (t) bởi công thức:


22

N

ukim X k

V


;i

k1

N

i

1,C.

(16)

ukim
k1

Bước 3: Tính U (t 1) bởi công thức:

f
k

uki
C

|| X V
k

2

|| m


i

|| X V
j1

k

; i 1, C, k 1, N.

(17)

||
j

Bước 4: Hiệu chỉnh bởi các đặc trưng địa lý:

1

uki'uki wij

uki ;i 1,C, k 1, N.
C

A

j1

1


w

ij

(18)

(mi m j )b
dija

(19)
(20)

Trong đó, mi là số lượng phần tử thuộc của cụm i , dij là khoảng cách tâm cụm
i và cụm j , A

là hệ số để giới hạn tổng độ thuộc của một phần tử thứ i vào tất cả các

cụm luôn bằng fi .
Bước 5: Nếu U ' (t 1) U (t) thì dừng thuật toán, ngược lại thì quay lại bước 2.

Ưu điểm của thuật toán là cải tiến tốc độ tính toán so với thuật toán FGWC.
Nhược điểm của thuật toán này là chất lượng phân cụm không cao.
1.2.3.5 Thuật toán CFGWC 2
Thuật toán này được đưa ra để nâng cao chất lượng phân cụm cho thuật toán
FGWC dựa trên ý tưởng về tập mờ loại 2, biến ngữ cảnh, tối ưu bầy đàn và tính toán
song song. Thuật toán được Tiến sỹ Lê Hoàng Sơn đưa ra năm 2014 [5]. Mô tả thuật
toán:
Đầu vào:



23

X

-

Tâm khởi tạo V(0), tập mẫu

-

Số phần tử (số cụm) –

-

Các tham số địa lý
Ngưỡng , số bước lặp MaxStep

N

, khoảng mờ

m ,m
1

2

, số chiều của tập dữ liệu

r


a,b, ,

Đầu ra:
-

Ma trận tâm kết quả V 3
Các bước thực hiện thuật toán:

Bước 1: Tính khoảng ma trận độ thuộc U (x) [U (x),U (x)]

từ ma trận tâm cụm

khởi tạo V (0) và tập mẫu X bởi các công thức:
C

U (x) {U kj (0,1) | k 1, N ; j

1,C ;

U kj 1}

(21)

j1

(22)

C

U (x) {U kj (0,1) | k 1, N; j 1,C;


Ukj

1}

j1

(23)

1
2

C

Nếum11
|| X k V
||
,
|| X k V i (0) || 1
|| X k Vj(0) ||
C
(0)

1

j

i1

U =

kj

1

C

|| X k Vj(0)
|| X V

i1

k

2

m 1

|| 2
(0) , Ngược lại
||

i

1
C

(0)
|| X k

U


kj

=

i

|| X

1

C

Vj

V

k

i1

||

i

m

1

1


1

|| Xk Vj

1
(0)
(0)

V
k

||

i

|| m
||

(24)

2Nếu

(0)C

|| X k Vj

|| X

C


,

1
(0)

||

C

,2 Ngược lại
2

1


24
Bước 2: Gán V ( A)

V (0) và thực hiện phương pháp hiệu chỉnh Kanik [9] để tính

tâm phải VR và tâm trái VL từ V ( A) và U(x) . Sắp xếp X theo các đặc trưng l(l 1, r)
theo thứ tự tăng dần.
Bước 3: Tìm chỉ số k0 thỏa mãn công thức:
C

X

k0l


v

/ CX

( A)
jl

(25)
(k0

1)l

j1

Nếu không chỉ số nào được tìm thấy, gán k0

N 1

Bước 4: Tính U (1)(l ) bởi công thức:
U
U

kj

, Nếu k

kj

(1)(l)


U

(26)

k

,

0

, ngược lại

j 1,C, k 1, N

kj

Bước 5: Tính ma trận tâm mới V (1) bởi công thức:
(27)

(1)(l )

N

m1

m2

U

X

kj

ki

2

(1)
ji

V

k1
N

U

kj

Ukj(1)(s)

U
kj

,j

1, C , i 1, r

2

k1


Bước 6: Nếu V (1)

,j

m1 m2
(1)(l )

V ( A) thì dừng việc tìm VR

V (1) . Với mỗi

s l 1, r, gán

1,
1,C , k N . Sau đó, tính U (1) bởi:
r

U

(1)

(28)

(1)(l )
r

U
l1


Ngược lại, gán V ( A) V (1) và quay lại bước 3 và bước 6 là ma trận tâm phải VR và
ma trận độ thuộc U (1)
Bước 7: Tính ma trân tâm trái VL và ma trận độ thuộc U (2) giống như ở Bước 2
đến Bước 6 với hai thay đổi ở bước 4 và bước 6 là:
U

U kj

(2 )( l )

kj

U

Nếu

(29)

k k

kj

, ngược lại

0

, j 1,C, k 1, N