Luận văn Thạc sĩ Khoa học máy tính: Kỹ thuật phân cụm dữ liệu không gian có ràng buộc

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

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG CHU THỊ HẢO

KỸ THUẬT PHÂN CỤM DỮ LIỆU KHÔNG GIAN CÓ RÀNG BUỘC

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

THÁI NGUYÊN, 2017

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

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG CHU THỊ HẢO

KỸ THUẬT PHÂN CỤM DỮ LIỆU KHÔNG GIAN CÓ RÀNG BUỘC 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. ĐẶNG VĂN ĐỨC THÁI NGUYÊN, 2017

i

MỤC LỤC

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

Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ DỮ LIỆU

KHÔNG GIAN ................................................................................................ 4

1.1. Khai phá dữ liệu ......................................................................................... 4

1.1.1. Một số khái niệm ..................................................................................... 4

1.1.2. Quá trình khai phá dữ liệu ....................................................................... 4

1.1.3. Các kỹ thuật khai phá dữ liệu .................................................................. 7

1.2. Dữ liệu không gian địa lý ........................................................................... 9

1.3. Hệ thống thông tin địa lý và ứng dụng ..................................................... 10

1.3.1. Một số định nghĩa về hệ thông tin địa lý .............................................. 11

1.3.2. Mô hình biểu diễn dữ liệu địa lý không gian ........................................ 14

1.3.3. Quan hệ không gian giữa các đối tượng địa lý ..................................... 20

1.4. Khái niệm và mục tiêu của Phân cụm dữ liệu ......................................... 20

1.5. Kết luận .................................................................................................... 23

Chương 2. MỘT SỐ KỸ THUẬT PHÂN CỤM DỮ LIỆU KHÔNG GIAN... 24

2.1. Phương pháp phân cụm theo phân hoạch ............................................... 24

2.2. Phương pháp phân cụm dựa trên mật độ ................................................. 26

2.3. Phương pháp phân cụm dựa trên lưới ...................................................... 32

2.4. Phương pháp phân cụm dữ liệu ràng buộc ............................................... 35

2.4.1. Thuật toán phân cụm dữ liệu không gian .............................................. 37

2.4.2. Thuật toán .............................................................................................. 45

2.5. Kết luận .................................................................................................... 48

Chương 3. CÀI ĐẶT VÀ THỬ NGHIỆM .................................................. 49

3.1. Phân tích bài toán ..................................................................................... 49

3.1.1. Nguồn dữ liệu đầu vào và phạm vi bài toán ......................................... 49

3.1.2. Phương pháp kỹ thuật giải quyết bài toán ............................................. 50

ii

3.2. Xây dựng chương trình ứng dụng ............................................................ 51

3.2.1. Phân tích thiết kế hệ thống .................................................................... 51

3.2.2. Cài đặt chương trình .............................................................................. 52

3.3. Thử nghiệm và đánh giá các thuật toán phân cụm ................................... 54

KẾT LUẬN VÀ KIẾN NGHỊ ...................................................................... 61

TÀI LIỆU THAM KHẢO ............................................................................ 62

iii

DANH MỤC CÁC BẢNG

Bảng 3.1: So sánh tổng quan các thuật toán K-means, DBSCAN và DBRS ...... 54

Bảng 3.2: Kết quả so sánh thời gian thực hiện phân cụm của các thuật toán

K-means, DBSCAN và DBRS với cùng một tập dữ liệu đầu vào ...... 56

Bảng 3.3: Kết quả so sánh thời gian thực hiện phân cụm của các thuật toán

K-means, DBSCAN và DBRS trên các tập dữ liệu khác nhau ........... 57

iv

DANH MỤC CÁC HÌNH

Hình 1.1: Khai phá dữ liệu trong tập dữ liệu ....................................................... 4

Hình 1.2: Tiến trình khám phá tri thức từ cơ sở dữ liệu ..................................... 5

Hình 1.3: Kiến trúc điển hình của một hệ khai phá dữ liệu ............................... 6

Hình 1.4. Ví dụ biểu diễn vị trí trước bị ô nhiễm .............................................. 13

Hình 1.5. Ví dụ biểu diễn đường xác định bởi ranh giới các đường, có

điểm đầu trùng với điểm cuối.............................................................. 13

Hình 1.6: Ví dụ biểu diễn khu vực hành chính .................................................. 14

Hình 1.7: Biểu diễn vector của đối tượng địa lý ................................................ 18

Hình 1.8: Biểu diễn thế giới bằng mô hình raster .............................................. 19

Hình 1.9: Mô tả tập dữ liệu được phân thành 3 cụm ........................................ 21

Hình 2.1: Minh họa thuật toán k-means .............................................................. 25

Hình 2.2: Kề mật độ ................................................................................................ 27

Hình 2.3: Kết nối theo mật độ ............................................................................... 27

Hình 2.4: Hình dạng các cụm được khám phá bởi thuật toán DBSCAN ...... 28

Hình 2.5: Cấu trúc phân cấp .................................................................................. 32

Hình 2.3: Các cách mà các cụm có thể đưa ra ................................................... 36

Hình 2.6: Phân cụm các đối tượng dữ liệu ràng buộc. ..................................... 37

Hình 2.7: Phân cụm các đối tượng dữ liệu ràng buộc ....................................... 40

Hình 2.8: Các đa giác đơn giản và tạo ra các đường cản trở ........................... 44

Hình 2.9: Thuật toán 1: phân cụm có các ràng buộc ......................................... 47

Hình 2.10: Thuật toán 2: Mở rộng một cụm ......................................................... 47

Hình 2.11: Tìm các điểm láng giềng ...................................................................... 47

Hình 3.1: Phân cu ̣m lớ p dữ liê ̣u "Khách sa ̣n-Trường học trong nô ̣i

thành Hà Nô ̣i, các vù ng màu vàng là các cu ̣m tìm đươ ̣c. ............... 53

v

Hình 3.2: Hình ảnh chồng phủ (vùng màu vàng) của các cụm “Siêu thi ̣”

(màu xanh) và các cu ̣m “Khách sa ̣n- Trường học” (màu đỏ).

Vùng màu vàng có thể coi là vị trí tối ưu cho việc đă ̣t địa

điểm Nhà hàng. ...................................................................................... 53

Hình 3.3: Kết quả phân cụm DBSCAN đối với dữ liệu thử nghiệm tự tạo ...... 54

Hình 3.4: Khả năng phát hiện nhiễu và cụm có hình dạng bất kỳ của K-

means (trái) và DBSCAN (phải), đường bao màu xanh là

đường biên cụm ..................................................................................... 55

Hình 3.5: Khả năng phân cụm theo thuộc tính của DBSCAN (trái) và

DBRS (phải) ........................................................................................... 55

Hình 3.5: Đồ thị so thời gian thực hiện phân cụm của các thuật toán K-

measn, DBSCAN và DBRS với cùng một tập dữ liệu đầu vào. ........ 57

Hình 3.6: Phân cụm tập dữ liệu DS1 ................................................................... 59

Hình 3.7: Phân cụm DS2 ........................................................................................ 60

1

MỞ ĐẦU

Hệ thống thông tin địa lý (GIS) được ứng dụng ngày càng phổ biến,

không chỉ trong lĩnh vực giám sát, quản lý, lập kế hoạch về tài nguyên môi

trường mà còn trong nhiều bài toán kinh tế xã hội khác. Kết quả là, khối

lượng dữ liệu liên quan đến địa lý, còn gọi là dữ liệu không gian thu thập

được tăng lên nhanh chóng. Một câu hỏi đặt ra là làm thế nào để tận dụng,

khai thác, khám phá, phát hiện những tri thức hữu ích từ kho dữ liệu này?

Khai phá dữ liệu là áp dụng các kỹ thuật và công cụ để trích rút các tri

thức có ích từ nguồn dữ liệu về một lĩnh vực nào đó mà ta quan tâm. Khai phá

dữ liệu với GIS hay còn gọi là khai phá dữ liệu không gian, mở rộng khai phá

dữ liệu trong các CSDL quan hệ, xét thêm các thuộc tính của dữ liệu không

gian được phản ánh trong hệ thông tin địa lý, ví dụ khoảng cách (gần kề hay

cách xa), điều kiện môi trường tự nhiên hay kinh tế xã hội (rừng núi, đồng

bằng, ven biển, đô thị, v.v…).

Các bài toán truyền thống của một hệ thông tin địa lý có thể trả lời các

câu hỏi kiểu như:

- Những con phố nào dẫn đến sân bay Tân Sân Nhất ?

- Những căn nhà nào nằm trong vùng quy hoạch mở rộng phố?

Khai phá dữ liệu không gian có thể giúp trả lời cho các câu hỏi dạng:

- Xu hướng của các dòng chảy, các đứt gãy địa tầng ?

- Nên bố trí các trạm tiếp sóng điện thoại di động như thế nào?

- Những vị trí nào là tối ưu để đặt các máy ATM, xăng dầu, nhà hàng,…?

Một trong những bài toán liên quan đến dữ liệu không gian, cụ thể là

dữ liệu địa lý có ý nghĩa thực tế cao là bài toán xác định vị trí tối ưu cho việc

đặt các cây xăng. Cả nước hiện có 374 tổng đại lý và hơn 14.000 cửa hàng

bản lẻ xăng dầu. Để xác định được vị trí đặt các trạm bán lẻ xăng dầu cần

2

phải tuân theo các quy định của Bộ Công thương, nhất là các quy định về an

toàn, phòng chống cháy nổ. Ngoài ra, cây xăng cũng phải đặt ở vị trí thuận

lợi cho việc kinh doanh đạt doanh số cao. Hoặc một bài toán khác cũng có ý

nghĩa thực tiễn rất lớn đó là xác định vị trí tối ưu để mở một nhà hàng. Hiện

nay trên địa bàn thành phố Hà Nội cũng đã có rất nhiều nhà hàng, quán ăn

đã được mở ra. Nhưng không phải tất cả các nhà hàng, quán ăn đó đều có

thể cho doanh thu tốt. Có khi có nhà hàng mới mở ra được một thời gian

ngắn đã phải đóng cửa vì không có khách dẫn đến chủ đầu tư phải chịu thua

lỗ nặng. Một trong những nguyên nhân chính dẫn đến thất bại đó là địa điểm

kinh doanh chưa hợp lý. Một vị trí tối ưu cho việc mở nhà hàng, quán ăn thì

vị trí đó phải thỏa mãn một số yếu tố sau: nằm trong khu vực đông dân cư,

gần nhiều cơ quan công sở hay trường học, có khu vực để xe, có quang cảnh

xung quanh thoáng mát...các vấn đề này đã được rất nhiều các đề tài nghiên

cứu tuy nhiên với những vị trí phức tạp có các ngăn cách con sông hay cây

cầu v.v… thì cần phải có những đánh giá chính xác hơn nữa.

Xuất phát từ nhu cầu thực tế đó và do đặc thù, khả năng ứng dụng rất

phong phú của kỹ thuật phân cụm dữ liệu trong không gian nên em đã chọn

nghiên cứu đề tài kỹ thuật phân cụm dữ liệu không gian có ràng buộc làm

luận văn tốt nghiệp cao học.

Trên cơ sở đó cài đặt thử nghiệm một ứng dụng sử dụng kỹ thuật phân

cụm dữ liệu không gian, trong đó khai thác thông tin địa lý của các đối tượng

để hỗ trợ giải quyết bài toán ví dụ như tìm vị trí tối ưu đặt nhà hàng.

Luận văn được chia thành các chương mục sau

- Chương 1: Tổng quan về khai phá dữ liệu và dữ liệu không gian

- Chương 2: Một số kỹ thuật phân cụm dữ liệu không gian

- Chương 3: Xây dựng chương trình thử nghiệm, kết luận, đánh giá

3

Luận văn này được hoàn thành dưới sự hướng dẫn tận tình của PGS.TS

Đặng Văn Đức, em xin bày tỏ lòng biết ơn chân thành của mình đối với thầy.

Em xin chân thành cảm ơn các thầy, cô giáo Viện Công nghệ thông tin,

Trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái

Nguyên đã tham gia giảng dạy, giúp đỡ em trong suốt qúa trình học tập nâng

cao trình độ kiến thức. Tuy nhiên vì điều kiện thời gian và khả năng có hạn

nên luận văn không thể tránh khỏi những thiếu sót. Em kính mong các thầy cô

giáo và các bạn đóng góp ý kiến để đề tài được hoàn thiện hơn

4

Chương 1

TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ DỮ LIỆU KHÔNG GIAN

1.1. Khai phá dữ liệu

1.1.1. Một số khái niệm

Khai phá dữ liệu được dùng để mô tả quá trình phát hiện ra tri thức trong CSDL. Khai phá dữ liệu làm giảm chi phí về thời gian so với phương pháp truyền thống trước kia (ví dụ như phương pháp thống kê).

Hình 1.1 minh họa đơn giản và trực quan cho khái niệm này.

Hình 1.1: Khai phá dữ liệu trong tập dữ liệu [5]

Khám phá tri thức trong CSDL là lĩnh vực liên quan đến nhiều ngành như:

Tổ chức dữ liệu, xác suất, thống kê, lý thuyết thông tin, học máy, CSDL, thuật

toán, trí tuệ nhân tạo, tính toán song song và hiệu năng cao. Các kỹ thuật chính

áp dụng trong khám phá tri thức phần lớn được thừa kế từ các ngành này.

1.1.2. Quá trình khai phá dữ liệu

Một số nhà khoa học xem khai phá dữ liệu là một cách gọi khác của

một thuật ngữ rất thông dụng: Khám phá tri thức từ cơ sở dữ liệu (Knowledge

Discovery in Database- KDD). Mặt khác, khi chia các bước trong quá trình

khám phá tri thức, một số nhà nghiên cứu lại cho rằng, KPDL chỉ là một bước

trong quá trình khám phá tri thức [5].

5

Như vậy, khi xét ở mức tổng quan thì hai thuật ngữ này là tương đương

nhau, nhưng khi xét cụ thể thì KPDL được xem là một bước trong quá trình

khám phá tri thức.

Nhìn chung, khai phá dữ liệu hay khám phá tri thức từ cơ sở dữ liệu

bao gồm các bước sau [4]:

Hình 1.2: Tiến trình khám phá tri thức từ cơ sở dữ liệu

Trích chọn dữ liệu: Là quá trình trích lọc một lượng dữ liệu phù hợp,

cần thiết từ tập dữ liệu lớn (cơ sở dữ liệu tác nghiệp, kho dữ liệu)…

Tiền xử lý dữ liệu: Là bước làm sạch dữ liệu (xử lý dữ liệu không đầy

đủ, dữ liệu nhiễu, ngoại lai, dữ liệu không nhất quán…), rút gọn dữ liệu (lấy

mẫu dữ liệu, lượng tử hóa…), rời rạc hóa dữ liệu. Kết quả sau bước này là dữ

liệu có tính nhất quán, đầy đủ, được rút gọn và được rời rạc hóa.

Chuyển đổi dữ liệu: Là bước chuẩn hóa khuôn dạng và làm mịn dữ

liệu, nhằm đưa dữ liệu về dạng thuận lợi nhất để phục vụ cho việc áp dụng

các giải thuật khai phá dữ liệu ở bước sau.

Khai phá dữ liệu: Sử dụng các phương pháp, kỹ thuật, các thuật toán để

trích lọc ra mẫu có ý nghĩa cùng với các tri thức, quy luật, biểu thức mô tả

mối quan hệ của dữ liệu trong một khía cạnh nào đó. Đây là bước quan trọng

và tốn nhiều thời gian nhất của toàn bộ tiến trình KDD.

6

Đánh giá và biểu diễn tri thức: Trình bày các tri thức, quy luật, biểu thức

có ý nghĩa đã tìm được ở bước trước dưới các dạng thức gần gũi, dễ hiểu đối với

người sử dụng như đồ thị, biểu đồ, cây, bảng biểu, luật…Đồng thời đưa ra những

đánh giá về tri thức khám phá được theo những tiêu chí nhất định.

Trong giai đoạn khai phá dữ liệu, có thể cần sự tương tác của con người

để điều chỉnh cách thức và kỹ thuật sử dụng trong khai phá, nhằm thu được tri

thức phù hợp nhất.

Dựa trên các bước của quá trình khai phá dữ liệu như trên, kiến trúc điển

hình của một hệ khai phá dữ liệu có thể bao gồm các thành phần như sau:

Hình 1.3: Kiến trúc điển hình của một hệ khai phá dữ liệu

7

1.1.3. Các kỹ thuật khai phá dữ liệu

Trong thực tế có nhiều kỹ thuật khai phá dữ liệu khác nhau nhằm thực

hiện hai chức năng mô tả và dự đoán.

Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả các tính chất hoặc

các đặc tính chung của dữ liệu trong CSDL hiện có. Một số kỹ thuật khai

phá trong nhóm này là: phân cụm dữ liệu (Clustering), tổng hợp

(Summarisation), trực quan hoá (Visualization), phân tích sự tiến hóa

(Evolution and deviation analyst),….

Kỹ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đưa ra các dự đoán

dựa vào các suy diễn trên cơ sở dữ liệu hiện thời. Một số kỹ thuật khai phá

trong nhóm này là: phân lớp (Classification), hồi quy (Regression), cây

quyết định (Decision tree), thống kê (statictics), mạng nơron (neural

network), luật kết hợp,….

Một số kỹ thuật phổ biến [1],[3],[5] thường được sử dụng để khai phá

dữ liệu hiện nay là:

1.1.3.1. Phân lớp dữ liệu

Mục tiêu của phân lớp dữ liệu đó là dự đoán nhãn lớp cho các mẫu dữ

liệu. Quá trình gồm hai bước: xây dựng mô hình, sử dụng mô hình để phân

lớp dữ liệu (mỗi mẫu 1 lớp). Mô hình được sử dụng để dự đoán nhãn lớp khi

mà độ chính xác của mô hình chấp nhận được.

1.1.3.2. Phân cụm dữ liệu

Mục tiêu của phân cụm dữ liệu là nhóm các đối tượng tương tự nhau

trong tập dữ liệu vào các cụm, sao cho các đối tượng thuộc cùng một cụm là

tương đồng.

Trong luận này tác giả đã sử dụng kỹ thuật phân cụm và thuật toán

DBSCAN DBCLUC tìm vị trí thích hợp để đặt nhà hàng. Vì vậy kỹ thuật

này và các thuật toán có liên quan sẽ được trình bày trong chương II.

8

1.1.3.3. Khai phá luật kết hợp

Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ

giữa các giá trị dữ liệu trong cơ sở dữ liệu. Đầu ra của giải thuật luật kết

hợp là tập luật kết hợp tìm được. Phương pháp khai phá luật kết hợp gồm

có hai bước:

Bước 1: Tìm ra tất cả các tập mục phổ biến. Một tập mục phổ biến

được xác định thông qua tính độ hỗ trợ và thoả mãn độ hỗ trợ cực tiểu.

Bước 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật

phải thoả mãn độ hỗ trợ và độ tin cậy cực tiểu.

1.1.3.4. Hồi quy

Phương pháp hồi quy tương tự như là phân lớp dữ liệu. Nhưng khác ở

chỗ nó dùng để dự đoán các giá trị liên tục còn phân lớp dữ liệu dùng để dự

đoán các giá trị rời rạc.

1.1.3.5. Mạng nơ-ron (neural network)

Đây là một trong những kỹ thuật KPDL được ứng dụng phổ biến hiện

nay. Kỹ thuật này phát triển dựa trên một nền tảng toán học vững vàng, khả

năng huấn luyện trong kỹ thuật này dựa trên mô hình thần kinh trung ương

của con người.

Kết quả mà mạng nơ-ron học được có khả năng tạo ra các mô hình dự

báo, dự đoán với độ chính xác và độ tin cậy cao. Nó có khả năng phát hiện ra

được các xu hướng phức tạp mà kỹ thuật thông thường khác khó có thể phát

hiện ra được. Tuy nhiên phương pháp neural network rất phức tạp và quá trình

tiến hành nó gặp rất nhiều khó khăn: đòi hỏi mất nhiều thời gian, nhiều DL,

nhiều lần kiểm tra thử nghiệm.

1.1.3.6. Cây quyết định

Kỹ thuật cây quyết định là một công cụ mạnh và hiệu quả trong việc

phân lớp và dự báo. Các đối tượng DL được phân thành các lớp. Các giá trị

của đối tượng DL chưa biết sẽ được dự đoán, dự báo. Tri thức được rút ra

9

trong kỹ thuật này thường được mô tả dưới dạng tường minh, đơn giản, trực

quan, dễ hiểu đối với người sử dụng. Trong những năm qua, nhiều mô hình

phân lớp DL đã được các nhà khoa học trong nhiều lĩnh vực khác nhau đề

xuất, nhưng kỹ thuật cây quyết định với những ưu điểm của mình được đánh

giá là một công cụ mạnh, phổ biến và đặc biệt thích hợp cho DM nói chung

và phân lớp dữ liệu nói riêng.

1.2. Dữ liệu không gian địa lý

Khái niệm

- Đối tượng địa lý: Trên bản đồ, các đối tượng như trạm xe bus, bến tàu,

trạm xăng là các thực thể dữ liệu quản lý, còn được gọi là đối tượng địa lý. Một

trạm xăng trên bản đồ là một thể hiện cụ thể của đối tượng địa lý trạm xăng.

- Dữ liệu địa lý và cơ sở dữ liệu địa lý: Dữ liệu địa lý là thông tin về các đối

tượng địa lý được mã hóa trong máy tính. Cơ sở dữ liệu địa lý là một tập hợp các

dữ liệu địa lý có chuẩn cấu trúc được lưu trữ trên máy tính và các thiết bị lưu

trữ thông tin khác, có thể thỏa mãn yêu cầu khai thác thông tin đồng thời của

nhiều người sử dụng hay nhiều chương trình ứng dụng với nhiều mục đích

khác nhau.

- Dữ liệu không gian và dữ liệu phi không gian: Một đối tượng địa lý

chứa các thông tin dữ liệu không gian và dữ liệu phi không gian.

+ Dữ liệu không gian: Dữ liệu không gian được sử dụng theo nghĩa

rộng bao gồm các điểm đa chiều, các đường thẳng, hình khối,...và các đối

tượng hình học nói chung. Mỗi đối tượng này chiếm một vùng không gian

được đặc trưng bởi hai thuộc tính vị trí và biên. Trong luận văn, khái niệm dữ

liệu không gian được hiểu đơn giản hơn, dữ liệu không gian mô tả các đối

tượng địa lý được thể hiện dưới dạng hình học, được quản lý bằng hình thể và

được biểu diễn dưới ba dạng đối tượng cơ bản là điểm, đường, vùng.

+ Dữ liệu phi không gian: Một đối tượng địa lý ngoài các thuộc tính

không gian còn có các thông tin thuộc tính khác. Ví dụ con đường có thể có

10

các thông tin như tên đường, độ rộng, chất liệu làm đường, đơn vị quản lý,

thời gian đưa vào sử dụng, ... Các thuộc tính này gọi là các thông tin thuộc

tính phi không gian (dữ liệu phi không gian). Dữ liệu phi không gian đôi khi

gọi tắt là dữ liệu thuộc tính.

- Hệ thống GIS: Khi đề cập đến dữ liệu địa lý, hệ thống thông tin địa lý

(Geographic Information System - gọi tắt là GIS) thường được nhắc đến bởi

GIS sử dụng dữ liệu địa lý. GIS được hình thành vào những năm 1960 và phát

triển mạnh trong 10 năm lại đây. Xét dưới góc độ hệ thống, GIS có thể được

hiểu như một hệ thống gồm các thành phần: phần cứng, phần mềm, dữ liệu và

con người (người dùng và các quy định, chính sách liên quan đến duy trì, phát

triển hệ thống).

Một cách đơn giản, có thể hiểu GIS như một sự kết hợp giữa bản đồ

(map) và cơ sở dữ liệu (database).

GIS = Bản đồ + Cơ sở dữ liệu

Bản đồ trong GIS là một công cụ hữu ích cho phép chỉ ra vị trí của từng

địa điểm. Với sự kết hợp giữa bản đồ và cơ sở dữ liệu, người dùng có thể xem

thông tin chi tiết về từng đối tượng/thành phần tương ứng với địa điểm trên

bản đồ thông qua các dữ liệu đã được lưu trữ trong cơ sở dữ liệu. Ví dụ, khi

xem bản đồ về các thành phố, người dùng có thể chọn một thành phố để xem

thông tin về thành phố đó như diện tích, số dân, thu nhập bình quân, số

quận/huyện của thành phố,

1.3. Hệ thống thông tin địa lý và ứng dụng

Khái niệm Địa lý (Geography) đề cập lĩnh vực nghiên cứu mô tả Trái

đất (Geo-Earth). Ngày nay, khái niệm này và khái niệm Không gian (Space)

được sử dụng thay thế nhau trong một số trường hợp. Tuy nhiên, về mặt bản

chất thì Địa lý là tập các mô tả về không gian (hai chiều), khí quyển (ba

chiều), … của Trái đất. Còn không gian cho phép mô tả bất kỳ cấu trúc đa

chiều nào, không quan tâm đến vị trí địa lý của nó. Như vậy có thể coi Địa lý

như là một phần cấu trúc nhỏ trong tập cấu trúc Không gian.

11

Khi mô tả Trái đất, các nhà địa lý luôn đề cập đến quan hệ không gian

(spatial relationship) của các đối tượng trong thế giới thực. Mối quan hệ này

được thể hiện thông qua các bản đồ (map) trong đó biểu diễn đồ họa của tập

các đặc trưng trừu tượng và quan hệ không gian tương ứng trên bề mặt trái

đất, ví dụ: bản đồ dân số biểu diễn dân số tại từng vùng địa lý.

Dữ liệu bản đồ còn là loại dữ liệu có thể được số hóa. Để lưu trữ và

phân tích các số liệu thu thập được, cần có sự trợ giúp của hệ thông tin địa lý

(Geographic Information System-GIS).

1.3.1. Một số định nghĩa về hệ thông tin địa lý

Có nhiều cách diễn giải khác nhau cho từ viết tắt GIS, tuy nhiên các

cách diễn giải đó đều mô tả việc nghiên cứu các thông tin địa lý và các khía

cạnh khác liên quan.

GIS cũng giống như các hệ thống thông tin khác, có khả năng nhập, tìm

kiếm và quản lý các dữ liệu lưu trữ, để từ đó đưa ra các thông tin cần thiết cho

người sử dụng. Ngoài ra, GIS còn cho phép lập bản đồ với sự trợ giúp của

máy tính, giúp cho việc biểu diễn dữ liệu bản đồ tốt hơn so với cách truyền

thống. Dưới đây là một số định nghĩa GIS hay dùng [1]:

Định nghĩa của dự án The Geographer's Craft, Khoa Địa lý, Trường

Đại học Texas: GIS là cơ sở dữ liệu số chuyên dụng trong đó hệ trục tọa độ

không gian là phương tiện tham chiếu chính. GIS bao gồm các công cụ để

thực hiện những công việc sau:

- Nhập dữ liệu từ bản đồ giấy, ảnh vệ tinh, ảnh máy bay, số liệu điều tra

và các nguồn khác.

- Lưu trữ dữ liệu, khai thác, truy vấn cơ sở dữ liệu.

- Biến đổi dữ liệu, phân tích, mô hình hóa, bao gồm cả dữ liệu thống kê

và dữ liệu không gian.

- Lập báo cáo, bao gồm bản đồ chuyên đề, bảng biểu, biểu đồ và kế hoạch.

Từ định nghĩa trên, ta thấy: Thứ nhất, GIS có quan hệ với ứng dụng cơ

sở dữ liệu. Thông tin trong GIS đều liên kết với tham chiếu không gian và

GIS sử dụng tham chiếu không gian như phương tiện chính để lưu trữ và truy

nhập thông tin. Thứ hai, GIS là công nghệ tích hợp, cung cấp các khả năng

12

phân tích như phân tích ảnh máy bay, ảnh vệ tinh hay tạo lập mô hình thống

kê, vẽ bản đồ... Cuối cùng, GIS có thể được xem như một hệ thống cho phép

trợ giúp quyết định. Cách thức nhập, lưu trữ, phân tích dữ liệu trong GIS phải

phản ánh đúng cách thức thông tin sẽ được sử dụng trong công việc lập quyết

định hay nghiên cứu cụ thể.

Định nghĩa của David Cowen, NCGIA, Mỹ

GIS là hệ thống phần cứng, phần mềm và các thủ tục được thiết kế để

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 qui

chiếu không gian để giải quyết các vấn đề quản lý và lập kế hoạch phức tạp.

Một cách đơn giản, có thể hiểu GIS như một sự kết hợp giữa bản đồ

(map) và cơ sở dữ liệu (database).

GIS = Bản đồ + Cơ sở dữ liệu

Bản đồ trong GIS là một công cụ hữu ích cho phép chỉ ra vị trí của từng

địa điểm. Với sự kết hợp giữa bản đồ và cơ sở dữ liệu, người dùng có thể xem

thông tin chi tiết về từng đối tượng/thành phần tương ứng với địa điểm trên

bản đồ thông qua các dữ liệu đã được lưu trữ trong cơ sở dữ liệu. Ví dụ, khi

xem bản đồ về các thành phố, người dùng có thể chọn một thành phố để xem

thông tin về thành phố đó như diện tích, số dân, thu nhập bình quân, số

quận/huyện của thành phố,

* Ðiểm (Point)

Điểm được xác định bởi cặp giá trị tọa độ (x, y). Các đối tượng đơn với

thông tin về địa lý chỉ bao gồm vị trí thường được mô tả bằng đối tượng điểm.

Các đối tượng biểu diễn bằng kiểu điểm thường mang đặc tính chỉ có

tọa độ đơn (x, y) và không cần thể hiện chiều dài và diện tích. Ví dụ, trên bản

đồ, các vị trícủa bệnh viện, các trạm rút tiền tự động ATM, các cây xăng,

… có thể được biểu diễn bởi các điểm.

Hình 1.1 là ví dụ về vị trí nước bị ô nhiễm. Mỗi vị trí được biểu

diễn bởi 1 điểm gồm cặp tọa độ (x, y) và tương ứng với mỗi vị trí đó có

thuộc tính độ sâu và tổng số nước bị nhiễm bẩn. Các vị trí này được biểu

diễn trên bản đồ và lưu trữ trong các bảng dữ liệu.

13

Hình 1.4. Ví dụ biểu diễn vị trí trước bị ô nhiễm

Ðường - Cung (Line - Arc)

Đường được xác định bởi dãy các điểm hoặc bởi 2 điểm đầu và điểm

cuối. Đường dùng để mô tả các đối tượng địa lý dạng tuyến như đường giao

thông, sông ngòi, tuyến cấp điện, cấp nước…

Các đối tượng được biểu diễn bằng kiểu đường thường mang đặc điểm là

có dãy các cặp tọa độ, các đường bắt đầu và kết thúc hoặc cắt nhau bởi điểm, độ

dài đường bằng chính khoảng cách của các điểm. Ví dụ, bản đồ hệ thống đường

bộ, sông, đường biên giới hành chính, … thường được biểu diễn bởi đường và

trên đường có các điểm (vertex) để xác định vị trí và hình dáng của đường.

● Vùng (Polygon)

Hình 1.5: Ví dụ biểu diễn đường xác định bởi ranh giới các đường,

có điểm đầu trùng với điểm cuối

14

Các đối tượng địa lý có diện tích và được bao quanh bởi đường thường

được biểu diễn bởi vùng.

Các đối tượng biểu diễn bởi vùng có đặc điểm là được mô tả bằng tập

các đường bao quanh vùng và điểm nhãn (label point) thuộc vùng để mô tả,

xác định cho mỗi vùng. Ví dụ, các khu vực hành chính, hình dạng các công

viên,… được mô tả bởi kiểu dữ liệu vùng. Hình 1.3 mô tả ví dụ cách lưu trữ

một đối tượng vùng.

Hình 1.6: Ví dụ biểu diễn khu vực hành chính

Một đối tượng có thể biểu diễn bởi các kiểu khác nhau tùy thuộc vào tỷ

lệ của bản đồ đó. Ví dụ, đối tượng công viên có thể được biểu diễn bởi điểm

trong bản đồ có tỷ lệ nhỏ, và bởi vùng trong bản đồ có tỷ lệ lớn.

1.3.2. Mô hình biểu diễn dữ liệu địa lý không gian

Như đã đề cập ở trên, dữ liệu địa lý bao gồm thành phần dữ liệu không

gian và thành phần dữ liệu thuộc tính. Ở phần này, chúng ta sẽ xem xét cách

thức biểu diễn thành phần dữ liệu không gian trong hệ thông tin địa lý.

- Mô hình khái niệm

Đây là mức trừu tượng đầu tiên trong tiến trình biểu diễn các thực thể

địa lý. Là tập các thành phần và các quan hệ giữa chúng liên quan đến hiện

tượng tự nhiên nào đó. Mô hình này độc lập lập với hệ thống, độc lập với cấu

trúc, tổ chức và quản lý dữ liệu. Một số mô hình quan niệm thường được sử

dụng trong GIS là:

15

- Mô hình không gian trên cơ sở đối tượng:

Mô hình này tập trung vào các hiện tượng, thực thể riêng rẽ được xem

xét độc lập hay cùng với quan hệ của chúng với thực thể khác. Bất kỳ thực thể

lớn hay nhỏ đều được xem như một đối tượng và có thể độc lập với các thực

thể láng giềng. Đối tượng này lại có thể bao gồm các đối tượng khác và chúng

cũng có thể có quan hệ với các đối tượng khác. Ví dụ các đối tượng kiểu thửa

đất và hồ sơ là tách biệt với các đối tượng khác về không gian và thuộc tính.

Mô hình hướng đối tượng phù hợp với các thực thể do con người tạo ra

như nhà cửa, đường quốc lộ, các điểm tiện ích hay các vùng hành chính. Một

số thực thể tự nhiên như sông hồ, đảo… cũng thường được biểu diễn bằng mô

hình đối tượng do chúng cần được xử lý như các đối tượng rời rạc. Mô hình

dữ liệu kiểu vector (sẽ đề cập đến ở phần sau) là một ví dụ của mô hình không

gian trên cơ sở đối tượng.

- Mô hình không gian trên cơ sở mạng:

Mô hình này có một vài khía cạnh tương đồng với mô hình hướng đối

tượng, nhưng mở rộng xem xét cả mối quan hệ tương tác giữa các đối tượng

không gian. Mô hình này thường quan tâm đến tính liên thông, hay đường đi

giữa các đối tượng không gian, ví dụ mô hình mạng lưới giao thông, mạng

lưới cấp điện, cấp thoát nước…Trong mô hình này, hình dạng chính xác của

đối tượng thường không được quan tâm nhiều. Mô hình topo là một ví dụ về

mô hình không gian trên cơ sở mạng.

- Mô hình quan sát trên cơ sở nền:

Mô hình này quan tâm đến tính liên tục, trải dài về mặt không gian của

thực thể địa lý, ví dụ các thực thể như thảm thực vật, vùng mây bao phủ, vùng

ô nhiễm khí quyển, nhiệt độ bề mặt đại dương…thích hợp khi sử dụng mô

hình này. Mô hình dữ liệu kiểu raster (sẽ đề cập ở phần sau) là một ví dụ về

mô hình quan sát trên cơ sở nền.

16

- Mô hình logic

Sau khi biểu diễn các thực thể ở mức mô hình quan niệm, bước tiếp

theo là cụ thể hóa mô hình quan niệm của các thực thể địa lý thành các cách

thức tổ chức hay còn gọi là cấu trúc dữ liệu cụ thể để có thể được xử lý bởi hệ

thông tin địa lý. Ở mô hình logic, các thành phần biểu diễn thực thể và quan

hệ giữa chúng được chỉ rõ dưới dạng các cấu trúc dữ liệu. Một số cấu trúc dữ

liệu được sử dụng trong GIS là:

- Cấu trúc dữ liệu toàn đa giác:

Mỗi tầng trong cơ sở dữ liệu của cấu trúc này được chia thành tập

các đa giác. Mỗi đa giác được mã hóa thành trật tự các vị trí hình thành

đường biên của vùng khép kín theo hệ trục tọa độ nào đó. Mỗi đa giác

được lưu trữ như một đặc trưng độc lập, do vậy không thể biết được đối

tượng kề của một đối tượng địa lý. Như vậy quan hệ topo (thể hiện mối

quan hệ không gian giữa các đối tượng địa lý như quan hệ kề nhau, bao

hàm nhau, giao cắt nhau…) không thể hiện được trong cấu trúc dữ liệu

này. Nhược điểm của cấu trúc dữ liệu này là một số đường biên chung

giữa hai đa giác kề nhau sẽ được lưu hai lần, và như vậy, việc cập nhật,

sửa đổi dữ liệu thường gặp nhiều khó khăn.

- Cấu trúc dữ liệu cung nút:

Cấu trúc dữ liệu cung nút mô tả các thực thể địa lý dưới dạng các

điểm (nút) và các đường (cung). Như vậy, có thể biểu diễn được quan hệ

topo giữa các đối tượng địa lý. Trong cấu trúc dữ liệu này, các phần đối

tượng không gian kề nhau sẽ được lưu trữ một lần, ngoài ra, các đối tượng

lân cận của một đối tượng địa lý cũng được chỉ rõ, điều này giúp dễ dàng

thực hiện các phép phân tích không gian, đồng thời cũng tối ưu được dung

lượng lưu trữ dữ liệu.

17

- Cấu trúc dữ liệu dạng cây:

Trong một số mô hình dữ liệu như mô hình raster, dữ liệu có thể được

phân hoạch thành các đối tượng nhỏ hơn với nhiều mức khác nhau để giảm

thiểu dung lượng lưu trữ và tăng tốc độ truy vấn. Ví dụ cấu trúc cây tứ phân

chia một vùng dữ liệu làm 4 phần, trong mỗi phần này lại có thể được chia

tiếp thành 4 phần con.

- Mô hình dữ liệu vật lý

Dữ liệu địa lý cần được lưu trữ vật lý trên máy tính theo một cách thức

nhất định, tùy theo các hệ thống thông tin địa lý cụ thể mà cách thức lưu trữ, cài

đặt dữ liệu khác nhau. Mô hình dữ liệu vật lý thường khá khác nhau đối với từng

hệ thống GIS cụ thể. Một số hệ GIS thương mại có thể kể đến như: Arc/Info,

ERDAS, Geovision, Grass, Caris, Intergres, Oracle, Postgres…

Như vậy, từ một thực thể địa lý, thông qua 3 mức mô hình biểu diễn mà

được cụ thể hóa thành dữ liệu trên máy tính sẽ có dạng thể hiện rất khác nhau

đối với từng hệ GIS cụ thể. Mỗi hệ thông tin địa lý đều sử dụng mô hình dữ

liệu quan niệm riêng để biểu diễn mô hình dữ liệu vật lý duy nhất. Hệ thông

tin địa lý cung cấp các phương pháp để người sử dụng làm theo các mô hình

quan niệm tương tự ba lớp mô hình mô tả trên.

Hai nhóm mô hình dữ liệu không gian thường gặp trong các hệ GIS

thương mại là mô hình dữ liệu vector và mô hình dữ liệu raster.

- Mô hình vector

Mô hình vector sử dụng tọa độ 2 chiều (x, y) để lưu trữ hình khối của

các thực thể không gian trên bản đồ 2D. Mô hình này sử dụng các đặc tính rời

rạc như điểm, đường, vùng để mô tả không gian, đồng thời cấu trúc topo của

các đối tượng cũng cần được mô tả chính xác và lưu trữ trong hệ thống.

18

Hình 1.7: Biểu diễn vector của đối tượng địa lý

Theo Hình 1.7 các đối tượng không gian được lưu trữ dưới dạng vertor,

đồng thời các thuộc tính liên quan đến lĩnh vực cần quản lý (dữ liệu chuyên

đề - thematic data) của đối tượng đó cũng cần kết hợp với dữ liệu trên. Các

nhân tố chỉ ra sự tác động qua lại lẫn nhau giữa các đối tượng cũng được quản

lý, các nhân tố đó có thể là quan hệ topo (giao/ không giao nhau, phủ, tiếp

xúc, bằng nhau, chứa, …), khoảng cách và hướng (láng giềng về hướng nào).

- Mô hình raster

Mô hình raster hay còn gọi mô hình dạng ảnh (image) biểu diễn các đặc tính

dữ liệu bởi ma trận các ô (cell) trong không gian liên tục. Mỗi ô có chỉ số tọa độ

(coordinate) và các thuộc tính liên quan. Mỗi vùng được chia thành các hàng và cột,

mỗi ô có thể là hình vuông hoặc hình chữ nhật và chỉ có duy nhất một giá trị.

19

Hình 1.8: Biểu diễn thế giới bằng mô hình raster

Trên thực tế, chọn kiểu mô hình nào để biểu diễn bản đồ là câu hỏi luôn

đặt ra với người sử dụng. Việc lưu trữ kiểu đối tượng nào sẽ quyết định mô

hình sử dụng. Ví dụ nếu lưu vị trí của các khách hàng, các trạm rút tiền hoặc

dữ liệu cần tổng hợp theo từng vùng như vùng theo mã bưu điện, các hồ chứa

nước, … thì sử dụng mô hình vector. Nếu đối tượng quản lý được phân loại

liên tục như loại đất, mức nước hay độ cao của núi, … thì thường dùng mô

hình raster. Đồng thời, nếu dữ liệu thu thập từ các nguồn khác nhau được

dùng một mô hình nào đó thì có thể chuyển đổi từ mô hình này sang mô hình

khác để phục vụ tốt cho việc xử lý của người dùng.

Mỗi mô hình có ưu điểm và nhược điểm khác nhau. Về mặt lưu trữ,

việc lưu trữ giá trị của tất cả các ô/điểm ảnh trong mô hình raster đòi hỏi

không gian nhớ lớn hơn so với việc chỉ lưu các giá trị khi cần trong mô hình

vector. Cấu trúc dữ liệu lưu trữ của raster đơn giản, trong khi vector dùng các

cấu trúc phức tạp hơn. Dung lượng lưu trữ trong mô hình raster có thể lớn hơn

gấp 10 đến 100 lần so với mô hình vector. Đối với thao tác chồng phủ (xem

mục 1.3.4), mô hình raster cho phép thực hiện một cách dễ dàng, trong khi

mô hình vector lại phức tạp và khó khăn hơn.

Về mặt hiển thị, mô hình vector có thể hiển thị đồ họa vector giống như

bản đồ truyền thống, còn mô hình raster chỉ hiển thị ảnh nên có thể xuất hiện

hình răng cưa tại đường biên của các đối tượng tùy theo độ phân giải của tệp

20

raster. Với dữ liệu vector, người dùng có thể bổ sung, co dãn hoặc chiếu bản

đồ, thậm chí có thể kết hợp với các tầng bản đồ khác thuộc các nguồn khác

nhau. Hiện nay, mô hình vector được sử dụng nhiều trong các hệ thống GIS

bởi các lý do trên, ngoài ra mô hình này cho phép cập nhật và duy trì đơn

giản, dễ truy vấn dữ liệu.

1.3.3. Quan hệ không gian giữa các đối tượng địa lý

Có ba kiểu quan hệ không gian chính là: quan hệ khoảng cách, quan hệ

hướng và quan hệ Topo.

Quan hệ khoảng cách dựa trên khoảng cách Euclid giữa 2 đối tượng địa lý.

Quan hệ hướng thể hiện vị trí của đối tượng này so với các đối tượng

khác trong quan hệ không gian.

Quan hệ Topo có kiểu đặc trưng điển hình là giao giữa hai đối tượng

địa lý và chúng bất biến trên các phép biến đổi hình học như quay và co giãn.

Có nhiều phương pháp để xác định các quan hệ Topo giữa các điểm, đường,

vùng. Hầu như, chúng đều dựa trên mô hình giao nhau như: bên trong và

đường bao hoặc bên trong, bên ngoài và đường bao. Phép giao là sự phối hợp

của các toán tử logic và( ) và hoặc( ). Các mô hình giao nhau xác định 8

quan hệ Topo nhị phân là: cắt(crosses), chứa(contains), trong(within),

bao(covers), bao bở(-coveredBy), trùng(equals), không nối(disjoint),

chồng(overlaps).

1.4. Khái niệm và mục tiêu của Phân cụm dữ liệu

1.4.1. Một số Khái niệm

- Phân cụm dữ liệu là quá trình nhóm một tập các đối tượng tương tự

nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một

cụm là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không

tương đồng. Phân cụm dữ liệu là một ví dụ của phương pháp học không có

thầy. Không giống như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải

định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ

21

liệu là một cách học bằng quan sát, trong khi phân lớp dữ liệu là học bằng ví

dụ... Ngoài ra phân cụm dữ liệu còn có thể được sử dụng như một bước tiền

xử lí cho các thuật toán khai phá dữ liệu khác như là phân loại và mô tả đặc

điểm, có tác dụng trong việc phát hiện ra các cụm.

Hình 1.9: Mô tả tập dữ liệu được phân thành 3 cụm

- Ràng buộc cản trở: Một ràng buộc cản trở là một đa giác được biểu

thị bởi P(V, E) ở đây V là tập k điểm từ ràng buộc cản trở V  v1, v2, v3,, vk 

và E là tập k đoạn đường thẳng E  e1, e2, e3,, ek  ở đây ei là một đoạn

đường thẳng kết nối vi và vi+1, 1  i  k, i 1  1 nếu i+1 > k.

Có hai loại đa giác biểu diễn ràng buộc cản trở: đa gác lồi và đa giác lõm.

- Tầm nhìn: Tầm nhìn thể hiện sự kết nối giữa hai điểm dữ liệu, nếu

đoạn đường thẳng nối từ một điểm tới điểm khác không cắt với đa giác P(V,

d3,, dn , đoạn l nối di và dj, đây di, d j  D, i  j, 1  i, j  n, và đoạn ek  E,

E) biểu diễn ràng buộc cản trở. Cho tập D gồm n điểm dữ liệu D  d1, d2,

không tồn tại một điểm cắt p giữa hai đoạn đường thẳng l và ek thì khi đó di

nhìn thấy dj.

- Không gian tầm nhìn

Cho tập D gồm n điểm dữ liệu D  d1, d2, d3,, dn , không gian tầm

nhìn là tập S gồm k điểm S  s1, s2, s3,, sk d  S, si và sj nhìn thấy nhau,

S  D, i  j và 1  i, j  n. S ={  d| si và sj nhìn thấy nhau}.

22

- Cụm

Cho tập D gồm n điểm dữ liệu D  d1, d2, d3, , dn , cụm là một tập

C gồm c điểm C  c1, c2, c3, , cc  thỏa mãn các điều kiện dưới đây, ở đây

C  D, i  j, và 1  i, j  n.

- Tối đa hóa: di, d j, nếu di C và dj là mật độ có thể đạt được từ di

với Eps và MinPts, khi đó d j C.

- Sự kết nối: ci, c j C, ci là mật độ kết nối với cj theo Eps và MinPts

- ci, c j C, ci và cj nhìn thấy nhau.

- Điểm đi vào – Entry point: Entry point là điểm nằm trên chu vi của

đa giác miêu tả ràng buộc cắt ngang, nghĩa là khi mật đo có thể đạt được từ

điểm p với Eps thi p trở thành có thể đạt được bởi điểm x bất kỳ từ entry point

khác trong cùng đa giác biểu diễn ràng buộc cắt ngang với Eps. Nói cách

khác, hai entry point khác nhau p1 và p2, tại hai đầu của ràng buộc cắt ngang,

nếu a là mật độ có thể đạt được tới p1 với Eps và b là mật độ có thể đạt với p2

với Eps, khi đó a và b có thể đến được với nhau.

- Cạnh đi vào – Entry edge: là cạnh của đa giác miêu tả ràng buộc cắt

ngang với tập các entry point bắt đầu từ một entry point cuối của entry edge

tới entry point khác được tách biệt bởi một giá trị khoảng ie , ( ie  Eps)

- Ràng buộc cắt ngang: Ràng buộc cắt ngang (hoặc cây cầu) là tập B

gồm m điểm dữ liệu B  b1, b2, b3,, bn  đã sinh ra từ tất cả các entry edge.

Bằng cách định nghĩa một điểm bất kỳ ba  B có thể đạt được bởi tất cả các

điểm khác trong B. Cây cầu B được biểu thị bởi B(P,E), ở đây P là tập các entry

point được tạo sinh ra từ tập entry edge E. Do vậy một cây cầu “kết nối” tập các

điểm dữ liệu tối đa cũng như là tạo ra các cụm, nếu các điểm dữ liệu hoặc các

cụm có thể bị phân cụm bởi tất cả các entry point từ cây cầu.

23

1.5. Kết luận

Trong chương này, đầu tiên tôi trình bày khái quát chung về lĩnh vực

Khai phá tri thức và Khai phá dữ liệu. Sau đó, tôi tập trung trình bày chi tiết

về Khai phá dữ liệu như: Định nghĩa, mục tiêu,... và một số thách thức đặt ra

cho việc Khai phá dữ liệu.

Như vậy, Khai phá dữ liệu là một trong giai đoạn quan trọng của Khai

phá tri thức. Sự chính xác của Khai phá tri thức phụ thuộc chủ yếu vào giai

đoạn Khai phá dữ liệu. Do vậy, Khai phá dữ liệu đã và đang trở thành một

trong những hướng nghiên cứu thu hút được sự quan tâm của nhiều nhà

nghiên cứu và được ứng dụng trong nhiều lĩnh vực khác nhau. Do phạm vi

nghiên cứu, trong chương tới chúng tôi sẽ tập trung vào nghiên cứu một

hướng tiếp cận của Khai phá dữ liệu, đó là Phân cụm dữ

24

Chương 2

MỘT SỐ KỸ THUẬT PHÂN CỤM DỮ LIỆU KHÔNG GIAN

Các kỹ thuật Phân cụm dữ liệu có rất nhiều cách tiếp cận và ứng dụng

trong thực tế, nó hướng tới hai mục tiêu chung đó là chất lượng của các cụm

khám phá được và tốc độ thực hiện của thuật toán. Hiện nay, các kỹ thuật

Phân cụm dữ liệu có thể phân loại theo các cách tiếp cận chính sau.

2.1. Phương pháp phân cụm theo 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 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 đề PCDL, 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 ăn tham (Greedy) để tìm kiếm

nghiệm [1]. Dưới đây chúng tôi trình bày chi tiết một thuật toán đại diện cho kỹ

thuật phân cụm dữ liệu phân hoạch là thuật toán K- means.

Thuật toán k-means

Thuật toán k-means được mô tả cụ thể như sau:

Input: K, và dữ liệu về n mẫu của 1 CSDL.

Output: Một tập gồm K cluster sao cho cực tiểu về tổng sai-số vuông.

Thuật toán:

25

Bước 1: Chọn ngẫu nhiên K mẫu vào K cluster. Coi tâm của cluster

chính là mẫu có trong cluster.

Bước 2: Tìm tâm mới của cluster.

Bước 3: Gán (gán lại) các mẫu vào từng cluster sao cho khoảng cách từ

mẫu đó đến tâm của cluster đó là nhỏ nhất.

Bước 4: Nếu các cluster không có sự thay đổi nào sau khi thực hiện

bước 3 thì chuyển sang bước 5, ngược lại sang bước 2.

Bước 5: Dừng thuật toán.

Ví dụ: Giả sử trong không gian hai chiều, cho 12 điểm (n = 12) cần

phân 12 điểm này thành hai cluster (k=2).Đầu tiên chọn hai điểm ngẫu nhiên

vào hai cluster, giả sử chọn điểm (1,3) và điểm (9,4) (điểm có màu đỏ trên

hình 2.3a). Coi điểm (1,3) là tâm của cluster 1 và điểm (9,4) là tâm của

cluster hai. Tính toán khoảng cách từ các điểm khác đến hai điểm này và ta

gán được các điểm còn lại này vào một trong hai cluster, những điểm có màu

xanh lơ vào cluster 1, những điểm có màu xanh đậm vào cluster 2 (hình

2.3b). Hiệu chỉnh lại tâm của hai cluster, điểm màu đỏ trên hình 2.3c là tâm

mới của hai cluster. Tính lại các khoảng cách các điểm đến tâm mới và gán

lại các điểm này, hình 2.3d. Tiếp tục hiệu chỉnh lại tâm của hai cluster. Cứ

như thế lặp lại cho đến khi không còn sự thay đổi nữa thì dừng. Khi đó ta

thu được output của bài toán.

Hình 2.1: Minh họa thuật toán k-means

26

Đánh giá ưu nhược điểm của Thuật toán K-means

Ưu điểm:

Do K-means đơn giản nên có thể áp dụng đối với tập dữ liệu lớn Bảo

đảm hội tụ sau 1 số bước lặp hữu hạn.

Luôn có k cụm dữ liệu

Luôn có ít nhất 1 điểm dữ liệu trong 1 cụm dữ liệu.

Các cụm không phân cấp và không bị chồng chéo dữ liệu lên nhau.

Nhược điểm:

Chất lượng của thuật toán K-means phụ thuộc nhiều vào các tham số

đầu vào như: số cụm k và k trọng tâm khởi tạo ban đầu. Trong trường hợp các

trọng tâm khởi tạo ban đầu mà quá lệch so với các trọng tâm cụm tự nhiên thì

kết quả phân cụm của k-means là rất thấp

Khó để chọn ra được số lượng cụm tối ưu ngay từ đầu, mà phải qua

nhiều lần thử để tìm ra được số lượng cụm tối ưu

Không có khả năng tìm ra các cụm không lồi hoặc các cụm có hình

dạng phức tạp.

Rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu

2.2. Phương pháp phân cụm dựa trên mật độ

Kỹ thuật này 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ó 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. Dưới đây tôi sẽ trình bày

thuật toán đại diện cho kỹ thuật phân cụm dựa trên mật đó, đó là thuật toán

DBSCAN [5].

27

Thuật toán DBSCAN

DBSCAN là một phương pháp dựa trên mật độ điển hình, nó tăng

trưởng các cụm theo một ngưỡng mật độ.Thuật toán DBSCAN được Ester

giới thiệu vào năm 1996, khi nghiên cứu các thuật toán phân cụm dữ liệu

không gian. DBSCAN được khẳng định qua thực nghiệm là tốt hơn các

thuật toán khác.

Định nghĩa 1: Đối tượng p là “kề mật độ” (density-reachable) từ đối

tượng q nếu tồn tại một dãy p1, p2, ..., pn (p1 =q, pn= p) sao cho pi+1 là kề

mật độ trực tiếp từ pi.

Hình 2.2: Kề mật độ

Định nghĩa 2: Đối tượng p là “kết nối theo mật độ” (density-connected)

với đối tượng q nếu tồn tại đối tượng o sao cho cả p và q đều kề mật độ từ o.

Hình 2.3: Kết nối theo mật độ

Định nghĩa 3 (cụm): Cho cơ sở dữ liệu D, cụm C thỏa Eps và MinPts là

tập con khác rỗng của D thỏa 2 điều kiện sau:

1. p,q: nếu pЄC và q là kề mật độ từ p thì pЄC

2. p,qЄC: nếu pЄC và p kết nối theo mật độ với q

Trong phần này chúng ta mô tả giải thuật DBSCAN để phát hiện ra các

cụm và nhiễu theo định nghĩa 2 và 3. Như đã biết, các thuật toán theo hướng

mật độ đều có hai tham số là Eps và MinPts, việc xác định giá trị của hai tham

28

số này có ảnh hưởng lớn đến các cụm được phát hiện. Thực tế cho thấy là

không có cách nào xác định được giá trị của hai tham số này một cách chính

xác, tất cả các thuật toán đều xác định dựa trên một hàm xấp xỉ. Lý tưởng nhất

là xác định được cho mỗi cụm một cặp giá trị Eps và MinPts. Nhưng điều đó là

khó thực hiện vì trước khi phân cụm thì chúng ta không thu nhận được thông

tin về các cụm trong CSDL. DBSCAN đưa ra một heuristic hiệu quả và khá

đơn giản để xác định các tham số Eps và MinPts của cụm "mỏng nhất"

(thinnest) trong CSDL [4]. Vì thế DBSCAN sử dụng giá trị toàn cục Eps và

MinPts đối với tất cả các cụm.

Hình 2.4: Hình dạng các cụm được khám phá bởi thuật toán DBSCAN

Thuật toán

Để xác định các cụm, DBSCAN bắt đầu với một điểm p bất kỳ và tìm

tất cả các điểm lân cận mật độ với p. Nếu p là điểm nhân, thủ tục này sẽ tạo ra

một cụm (xem bổ đề 2). Nếu p là điểm biên, thì không có điểm nào kề mật độ

với p và DBSCAN thăm điểm kế tiếp trong CSDL.

29

Khi chúng ta sử dụng các giá trị toàn cục cho Eps và MinPts, DBSCAN

có thể trộn 2 cụm theo định nghĩa 5 thành một cụm, nếu hai cụm này "gần"

với nhau. Khoảng cách giữa hai tập điểm S1 và S2 được định nghĩa là

dist(S1, S2) = min

{dist(p,q) | p S1, q S2}. Hai tập điêm có các điểm tối thiểu của một cụm

mỏng sẽ tách rời nhau chỉ nếu khoảng cách giữa hai tập lớn hơn Eps. Do đó, lời

gọi đệ quy của DBSCAN có thể là cần thiết đối với các cụm được phát hiện với

giá trị cao hơn MinPts. Tuy nhiên, đây không phải là một nhược điểm vì ứng

dụng đệ quy của DBSCAN tạo ra một thuật toán cơ bản, khá hiệu quả.

Hơn nữa, phân cụm đệ quy các điểm của một cụm chỉ cần thiết trong

trường hợp có thể được phát hiện dễ dàng.

[4]Giới thiệu phiên bản cơ bản của DBSCAN bỏ qua các chi tiết về

kiểu dữ liệu và việc tạo ra các thông tin bổ sung về các cụm như sau:

DBSCAN (SetOfPoints, Eps, MinPts)

// SetOfPoints là tập chưa phân lớp.

ClusterId := nextId(NOISE);

FOR i FROM 1 TO SetOfPoints.size DO

Point := SetOfPoints.get(i);

IF Point.ClId = UNCLASSIFIED THEN

IF ExpandCluster(SetOfPoints, Point,ClusterId, Eps, MinPts)

THEN

ClusterId := nextId(ClusterId) END IF

END IF END

FOR

END; // DBSCAN

Trong đó, SetOfPoints là toàn bộ CSDL hoặc cụm được phát hiện từ

lần chạy trước. Eps và MinPts là các tham số mật độ toàn cục được xác định

bằng tay hoặc dựa trên heuristic. Hàm SetOfPoints.get(i) trả về phần tử thứ i

30

của SetOfPoints. Hàm quan trọng nhất được sử dụng bởi DBSCAN là

ExpandCluster được minh hoạ như sau:

ExpandCluster(SetOfPoints, Point, ClId, Eps,MinPts) : Boolean;

seeds:=SetOfPoints.regionQuery(Point,Eps);

IF seeds.size

SetOfPoint.changeClId(Point,NOISE);

RETURN False;

ELSE // tất cả các điểm trong seeds là kề mật độ với Point

SetOfPoints.changeClIds(seeds,ClId);

seeds.delete(Point);

WHILE seeds <> Empty DO

currentP := seeds.first();

result := SetOfPoints.regionQuery(currentP,Eps); IF

result.size >= MinPts THEN

FOR i FROM 1 TO result.size DO

resultP := result.get(i); IF

resultP.ClId

IN {UNCLASSIFIED, NOISE} THEN

IF resultP.ClId = UNCLASSIFIED

THEN

seeds.append(resultP); END

IF;

SetOfPoints.changeClId(resultP,ClId);

END IF; // UNCLASSIFIED hoặc NOISE

END FOR;

END IF; // result.size >= MinPts

seeds.delete(currentP);

END WHILE; // seeds <> Empty

31

RETURN True; END

IF

END; // ExpandCluster

Lời gọi hàm SetOfPoints.regionQuery(Point,Eps) trả về Eps-Neighborhood

của Point trong SetOfPoints như một danh sách các điểm. Các truy vấn vùng

có thể được hỗ trợ một cách hiệu quả bởi các phương thức truy nhập không

gian như cây R* được cho trong hệ thống CSDL không gian (SDBS) để xử lý

một cách hiệu quả cho một số kiểu truy vấn không gian.Chiều cao của cây R*

là O(logn) với CSDL có n điểm trong trường hợp tồi nhất và một truy vấn với

vùng truy vấn nhỏ phải duyệt trên một số giới hạn các đường đi trên cây R*.

Khi lân cận Epsilon được trông đợi là nhỏ khi so sánh với kích thước của toàn

bộ không gian dữ liệu, độ phức tạp thời gian tính trung bình của một truy vấn

vùng đơn giản là O(log n). Với mỗi n điểm của CSDL, chúng ta có nhiều

nhất một truy cấn vùng. Do đó, độ phức về thời gian tính trung bình của

DBSCAN là O(n * logn). ClId (ID của cụm) của các điểm mà được đánh dấu

là NOISE có thể bị thay đổi, nếu chúng là điểm tới được từ một số điểm khác

trong CSDL. Điều này xảy ra đối với một số điểm biên của cụm. Các điểm

này không được bổ sung vào seeds-list vì chúng ta biết rằng một điểm với

ClId của NOISE thì không phải là điểm hạt nhân. Bổ sung các điểm này vào

seeds sẽ chỉ có kết quả trong các truy vấn vùng bổ sung mà không mang lại câu

trả lời mới. Khi hai cụm C1 và C2 gần nhau, có thể xảy ra trường hợp có một

số điểm p thuộc về cả hai cụm C1 và C2. Khi đó, p phải là điểm biên của cả hai

cụm vì nếu không C1 và C2 sẽ bằng nhau khi chúng ta sử dụng các tham số

toàn cục. Trong trường hợp này, điểm p sẽ được gán với cụm được phát hiện ra

trước. Như vậy, DBSCAN hiệu quả hơn trong việc phát hiện ra các cụm với hình

dạng bất kì, kể cả hình không lồi. Và khử nhiễu tốt hơn CLARANS. Tuy nhiên

vẫn có một số trường hợp mà DBSCAN không phù hợp:

32

* Nếu các cụm có mật độ khác nhau nhiều thì DBSCAN sẽ không giữ được

tính hiệu quả. Trên những dữ liệu như thế ta phải áp dụng mật độ của cụm có mật

độ thấp nhất cho tất cả các cụm khác. Với các cụm có mật độ rất cao thì DBSCAN

tốn nhiều thời gian để xác định lân cận của các điểm một cách không cần thiết.

2.3. Phương pháp phân cụm dựa trên lưới

Kỹ thuật phân cụm dựa trên lưới thích hợp với dữ liệu nhiều chiều, dựa

trên cấu trúc dữ liệu lưới để phân cụm, phương pháp này chủ yếu tập trung áp

dụng cho lớp dữ liệu không gian. Mục tiêu của phương pháp này là lượng hóa dữ

liệu thành các ô tạo thành cấu trúc dữ liệu lưới. Sau đó, các thao tác phân cụm chỉ

cần làm việc với các đối tượng trong từng ô trên lưới chứ không phải các đối

tượng dữ liệu. Cách tiếp cận dựa trên lưới này không di chuyển các đối tượng

trong các ô mà xây dựng nhiều mức phân cấp của nhóm các đối tượng trong một

ô. Phương pháp này gần giống với phương pháp phân cụm phân cấp nhưng

chúng không trộn các ô, đồng thời giải quyết khắc phục yêu cầu đối với dữ liệu

nhiều chiều mà phương pháp phân phân cụm dựa trên mật độ không giải quyết

được. Ưu điểm của phương pháp phân cụm dựa trên lưới là thời gian xử lí nhanh

và độc lập với số đối tượng dữ liệu trong tập dữ liệu ban đầu, thay vào đó là

chúng phụ thuộc vào số ô trong mỗi chiều của không gian lưới

Hình 2.5: Cấu trúc phân cấp

33

Thuật toán đại diện cho kỹ thuật này

Thuật toán DBRS

Thuật toán DBRS (A Density-Based Spatial Clustering Method with

Random Sampling) được tác giả Xin Wang và Howard J.Hamilton đưa ra năm

2003. Thuật toán này cũng phân cụm dữ liệu dựa trên mật độ của các điểm

trong CSDL không gian. DBRS khắc phục được một số hạn chế mà thuật toán

DBSCAN còn mắc phải. Như đã nói trong mục trước, thuật toán DBSCAN

bị hạn chế khi mà cụm được phát hiện có mật độ khác nhau nhiều hoặc dữ

liệu có đặc tính phi không gian. DBRS được giới thiệu là thuật toán phân cụm

dữ liệu có các đặc trưng sau đây.

Thứ nhất: Các cụm được phát hiện có nhiều hình dạng khác nhau.

Chẳng hạn như dữ liệu về địa chỉ của sinh viên của một trường đại học. Khi

phân cụm sinh viên theo địa chỉ thì có thể có các cụm sinh viên tại các nhà

chung cư (cụm có dạng hình chữ nhật), cụm sinh viên dọc theo các tuyến xe

bus (cụm có dạng tuyến),...

Thứ hai: Các cụm có mật độ khác nhau nhiều. Một ví dụ như CSDL

nghiên cứu về sự phân bố khách hàng của một công ty, ở các thành phố lớn thì

khách hàng của công ty rất nhiều, còn ở các vùng hẻo lánh thì lượng khách hàng

thưa thớt. Vì các thành phố lớn dân số tập trung đông hơn nhiều các vùng hẻo

lánh. Như vậy các cụm được phát hiện sẽ có mật độ khác nhau khá lớn.

Thứ ba: Dữ liệu có những đặc tính phi không gian (non-spatial).

Thứ tư: CSDL có kích thước lớn với hàng trăm nghìn điểm.

DBRS là sự mở rộng của thuật toán DBSCAN, các định nghĩa của thuật

toán DBSCAN vẫn được dùng bình thường, ngoài ra còn có thêm một số định

nghĩa sau đây, nhằm định nghĩa tính chất của các thuộc tính phi không gian.

Cho CSDL D, hàm khoảng cách đối xứng dist, các tham số MinPts, Eps

và thuộc tính prop (định nghĩa cho khía cạnh thuộc tính phi không gian).

34

Thuật toán DBRS có thể được mô tả ngắn gọn như sau: DBRS xuất

phát với điểm bất kì q và tìm lân cận ghép qseeds có số điểm MinPts và độ

thuần nhất MinPur thì q là điểm nhân, ngược lại coi q là điểm nhiễu hoặc

điểm biên. Nếu q là điểm nhân thì kiểm tra lân cận của q có giao với một cụm

đã có không, danh sách các cụm đã có được lưu trong ListCluster, nếu có giao

với một cụm thì trộn qseeds với cụm đó, nếu giao với nhiều cụm thì hợp các

cụm đó với qseeds. Ngược lại thì tạo ra một cụm mới. Quá trình lặp lại cho

đến khi tòan bộ các điểm của D đã được đưa vào một cụm nào đó hoặc là

được gán là nhiễu. Có thể mô tả thuật toán bằng đoạn mã giả Pascal như sau:

Algorithm DBRS(D, Eps, MinPts, MinPur)

ClusterList := Empty;

WHILE (D.isClassified = False) DO

Select one unclassified point q from D;

qseeds := D.matchingNeighbors(q, Eps);

IF ((|qseeds| < MinPts) or (qseeds.pur <

MinPur)) THEN

q.clusterID := -1;/* q là điểm nhiễu hoặc điểm biên */

ELSE

isFirstMerge := True;

Ci := ClusterList.firstCluster;

/* so sánh qseeds với tất cả các cụm đã có */

WHILE (Ci<> Empty) DO

IF (hasIntersection(qSeeds, Ci)) THEN

IF (isFirstMerge) THEN

newCi := Ci.merge(qseeds);

isFirstMerge := False;

ELSE

newCi := Ci.merge(Ci) ClusterList.deleteCluster(C);

END IF

35

Ci := ClusterList.NextCluster; END WHILE;

/* không giao với một cụm nào đã tồn tại */

IF (isFirstMerge) THEN

Create a new cluster Cj từ qseeds;

ClusterList := ClusterList.addCluste(Cj); END IF; //

isFirstMerge

END IF;

END WHILE; //D.isClassified = False

Trong thuật toán DBRS thì truy vấn miền D.matchingNeighbors(q,Eps)

là tốn nhiều thời gian nhất. Nếu sử dụng các cấu trúc không gian như cây R*

hoặc cây SR thì độ phức tạp của thủ tục này là O(logn). Trường hợp tồi tệ

nhất là n điểm trong CSDL đều là nhiễu thì mất n lần truy vấn nên độ phức

tạp là O(n logn). Tuy nhiên nếu tìm thấy một điểm nhân thì số lần truy vấn

giảm đi rất nhiều vì các điểm thuộc lân cận ghép thì không cần truy vấn

miền nữa. Để giảm thời gian thực hiện thì DBRS sử dụng một kỹ thuật

heurictis gọi là DBS-H.

* Hiệu quả của thuật toán DBRS

Ưu điểm nổi bật của DBRS so với các thuật toán khác là tốc độ nhanh

hơn rất nhiều, vì DBRS thực hiện ít truy vấn miền hơn. So với K- Means và

DBRS phát hiện nhiễu tốt hơn.

2.4. Phương pháp phân cụm dữ liệu ràng buộc

Sự phát triển của PCDL không gian trên CSDL 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. Để

PCDL 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.

36

Hình 2.3: Các cách mà các cụm có thể đưa ra

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ố.

Phân cụm khái niệm: Kỹ thuật này được phát triển áp dụng cho dữ liệu

hạng mục, chúng phân cụm các đối tượng theo các khái niệm mà chúng xử lí.

Phân cụm mờ: Sử đụng kỹ thuật mờ để PCDL. Các thuật toán thuộc

loại này chỉ ra lược đồ phân cụm thích hợp với tất cả các hoạt động đời sống

hàng ngày, chúng chỉ xử lí các dữ liệu thực không chắc chắn.

Phân cụm mạng Kohonen: Loại phân cụm này dựa trên khái niệm của

các mạng nơron. Mạng Kohonen có tầng nơron vào và các tầng nơron ra. Mỗi

nơron của tầng vào tương ứng với mỗi thuộc tính của bản ghi, mỗi một nơron

vào kết nối với tất cả các nơron của tầng ra. Mỗi liên kết được gắn liền với

một trọng số nhằm xác định vị trí của nơron ra tương ứng. Các thuật toán

37

thuộc kỹ thuật phân cụm dữ liệu ràng buộc này gồm có: Thuật toán COD-

CLARANS, thuật toán DBCluC.

2.4.1. Thuật toán phân cụm dữ liệu không gian

Trong các thuật toán được trình bày ở các phần trên đều chỉ tập trung vào

tính hiệu quả của phân cụm dữ liệu. Tuy nhiên, không thuật toán nào xem xét các

ràng buộc có thể có trong quá trình phân cụm dữ liệu.

Trong dữ liệu không gian thì phân cụm ràng buộc có nhiều ứng dụng,

đặc biệt trong các hệ thống thông tin địa lý vì dữ liệu của hệ thống này như

ảnh,… có các ràng buộc vật lý (có các đối tượng cản trở như dòng sông,

đường cao tốc, dãy núi,.... và có các đối tượng cắt ngang như cây cầu) và các

ràng buộc này có thể làm thay đổi quá trình phân cụm trong hệ thống thông

tin địa lý. Hơn nữa, các các ràng buộc cản trở (dòng sông, đường cao tốc,…)

có chức năng biểu diễn cho việc “không kết nối” để không kết nối các đối

tượng dữ liệu gần nhau, trong khi các ràng buộc cắt ngang (cây cầu) có chức

năng biểu diễn cho việc “Kết nối” để kết nối các đối tượng dữ liệu với nhau.

Do vậy, chúng ta cần có các thuật toán xem xét các đối tượng cản trở và các

đối tượng cắt ngang (cây cầu) để tăng tính hiệu quả và độ chính xác của cụm.

Hình 2.6 trình bày phân cụm các đối tượng dữ liệu liên các xét đến các ràng

buộc vật lý. Loại bỏ các ràng buộc dẫn đến không chính xác trong việc giải

thích của sự tương quan giữa các đối tượng dữ liệu. Hình 2.6(b) trình bày ba

cụm. Hình 2.6(c) phân cụm chính xác, tạo ra bốn cụm, ba cụm có các ràng

buộc cao tốc và sông, và một cụm được nhóm bởi ràng buộc cây cầu).

Hình 2.6: Phân cụm các đối tượng dữ liệu ràng buộc.

(a) các đối tượng dữ liệu và các ràng buộc; (b) các cụm loại bỏ các rang

buộc; (c) các cụm với các ràng buộc

38

Trong phần này, tôi sẽ trình bày khái quát các thuật toán phân cụm dữ

liệu không gian có các ràng buộc vật lý: CLARANS[3], COD-CLARANS [4]

và DBCluC [5].

2.4.1.1. Giới thiệu thuật toán CLARANS

CLARANS phân cụm dựa trên việc tìm kiếm ngẫu nhiên các tập gồm k

đối tượng để làm tâm của k cụm. Tại mỗi bước tìm kiếm sẽ xác định được độ

tốt của nó và giữ lại kết quả tìm kiếm tốt nhất.

Ý tưởng cơ bản của CLARANS là không xem xét tất cả các khả năng

có thể thay thế các đối tượng tâm medoids bởi một đối tượng khác, nó ngay

lập tức thay thế các đối tượng medoid này nếu việc thay thế có tác động tốt

đến chất lượng phân cụm chứ không cần xác định cách thay thế tối ưu nhất.

Một phân hoạch cụm phát hiện được sau khi thay thế đối tượng trung

tâm được gọi là một láng giềng của phân hoạch cụm trước đó. Số các láng

giềng được hạn chế bởi tham số do người dùng đưa vào là Maxneighbor, quá

trình lựa chọn các láng giềng này là hoàn toàn ngẫu nhiên. Tham số Numlocal

cho phép người dùng xác định số vòng lặp tối ưu cục bộ được tìm kiếm.

Không phải tất các láng giềng được duyệt mà chỉ có Maxneighbor số

láng giềng được duyệt.

2.4.1.2. Mô tả thuật toán CLARANS

Các tác giả đã thực hiện việc tìm kiếm và đánh giá độ tốt của phép tìm

kiếm bằng cách xây dựng một đồ thị tìm kiếm như sau. Với n đối tượng cần

chia làm k cụm thì đồ thị được đặt tên là Gn,k. Mỗi đỉnh của Gn,k là một tập

gồm k đối tượng.

Thuật toán CLARANS cần có hai tham số đầu vào là numlocal (số cục

địa phương cần tìm) và maxneighbor (số đỉnh kề cần xét). Quá trình thực hiện

của thuật toán như sau: Đầu tiên chọn ngẫu nhiên một đỉnh làm đỉnh hiện

thời, lấy ngẫu nhiên một đỉnh kề với đỉnh hiện thời, so sánh trọng số của đỉnh

hiện thời và đỉnh vừa chọn, nếu đỉnh vừa chọn có trọng số nhỏ hơn thì đặt

đỉnh đó làm đỉnh hiện thời, lặp lại quá trình đó maxneighbor lần, tìm được

39

một đỉnh có trọng số thấp nhất, trọng số này gọi là cực tiểu địa phương. So

sánh cực tiểu địa phương với một số mincost, nếu nhỏ hơn thì gán mincost

bằng cực tiểu địa phương đó và lưu lại đỉnh hiện thời vào bestnode. Lặp lại

quá trình trên đủ numlocal lần. Kết quả được chứa trong bestnode.

Thuật toán CLARANS được mô tả cụ thể như sau:

Bước 1: Đặt i = 1, mincost = + .

Bước 2: Chọn một đỉnh ngẫu nhiên của Gn,k gọi là đỉnh hiện thời current.

Bước 3: Đặt j = 1.

Bước 4: Chọn ngẫu nhiên 1 đỉnh S kề với current. Tính trọng số của S.

Bước 5: Nếu S có trọng số nhỏ hơn current thì đặt S là đỉnh hiện thời

và trở lại bước 3.

Bước 6: Ngược lại, j = j + 1. Nếu j maxneighbor thì quay về bước 4.

Bước 7: Ngược lại, khi j > maxneighbor thì so sánh trọng số của

current với mincost, nếu nhỏ hơn mincost thì đặt mincost bằng trọng số của

current và đặt bestnode = current.

Bước 8: i = i + 1, nếu i > numlocal thì đưa ra bestnode và dừng, ngược

lại thì quay về bước 2.

Như vậy, quá trình hoạt động của CLARANS tương tự với quá trình hoạt

động của thuật toán CLARA. Tuy nhiên, ở giai đoạn lựa chọn các trung tâm

medoid cụm dữ liệu, CLARANS lựa chọn một giải pháp tốt hơn bằng cách lấy

ngẫu nhiên một đối tượng của k đối tượng trung tâm medoid của cụm và cố gắng

thay thế nó với một đối tượng được chọn ngẫu nhiên trong (n-k) đối tượng còn

lại, nếu không có giải pháp nào tốt hơn sau một số cố gắng lựa chọn ngẫu nhiên

xác định, thuật toán dừng và cho kết quả phân cụm tối ưu cục bộ.

CLARANS có ưu điểm là không gian tìm kiếm không bị giới hạn như

đối với CLARA và trong cùng một lượng thời gian thì chất lượng của các

cụm phân được là lớn hơn so với CLARA. Thuật toán CLARANS được

đánh giá là hiệu quả trên CSDL lớn, vấn đề xác định tham số numlocal và

maxneighbor không phức tạp. Có thể chọn các giá trị khác nhau sao cho phù

hợp với CSDL cần nghiên cứu.

40

Tuy nhiên, CLARANS cũng bộc lộ một số hạn chế. Thứ nhất, CLARANS

cần đưa cả CSDL vào bộ nhớ trong. Thứ hai thời gian thực thi có nhiều trường

hợp rất xấu, trường hợp tốt nhất là O(kn2) và trường hợp xấu nhất là O(nk).

Trong các thuật toán được trình bày ở các phần trên đều chỉ tập trung

vào tính hiệu quả của phân cụm dữ liệu. Tuy nhiên, không thuật toán nào xem

xét các ràng buộc có thể có trong quá trình phân cụm dữ liệu.

Trong dữ liệu không gian thì phân cụm ràng buộc có nhiều ứng dụng, đặc biệt

trong các hệ thống thông tin địa lý vì dữ liệu của hệ thống này như ảnh,… có

các ràng buộc vật lý (có các đối tượng cản trở như dòng sông, đường cao tốc,

dãy núi,.... và có các đối tượng cắt ngang như cây cầu) và các ràng buộc này

có thể làm thay đổi quá trình phân cụm trong hệ thống thông tin địa lý.

Hơn nữa, các các ràng buộc cản trở (dòng sông, đường cao tốc,…) có

chức năng biểu diễn cho việc “không kết nối” để không kết nối các đối tượng

dữ liệu gần nhau, trong khi các ràng buộc cắt ngang (cây cầu) có chức năng

biểu diễn cho việc “Kết nối” để kết nối các đối tượng dữ liệu với nhau. Do

vậy, chúng ta cần có các thuật toán xem xét các đối tượng cản trở và các đối

tượng cắt ngang (cây cầu) để tăng tính hiệu quả và độ chính xác của cụm.

Hình 2.7 trình bày phân cụm các đối tượng dữ liệu liên các xét đến các

ràng buộc vật lý. Loại bỏ các ràng buộc dẫn đến không chính xác trong việc

giải thích của sự tương quan giữa các đối tượng dữ liệu. Hình 2.7(b) trình bày

ba cụm. Hình 2.7(c) phân cụm chính xác, tạo ra bốn cụm, ba cụm có các ràng

buộc cao tốc và sông, và một cụm được nhóm bởi ràng buộc cây cầu).

Hình 2.7: Phân cụm các đối tượng dữ liệu ràng buộc

(a) các đối tượng dữ liệu và các ràng buộc; (b) các cụm loại bỏ các ràng

buộc; (c) các cụm với các ràng buộc

41

Trong phần này, tôi sẽ trình bày khái quát hai thuật toán phân cụm dữ

liệu không gian có các ràng buộc vật lý: COD-CLARANS [4] và trình bày chi

tiết thuật toán DBCluC [3].

2.4.1.3. Thuật toán COD-CLARANS

COD-CLARANS được phát triển từ thuật toán CLARANS [4]. Đây là

thuật toán được thay đổi của phương pháp k-medoids. COD-CLARANS xem

xét các ràng buộc cản trở bằng cách tích hợp một lược đồ tối ưu vào trong

hàm khoảng cách lỗi trong thuật toán CLARANS. Các ràng buộc cản trở được

mô hình hóa bằng một đồ thị tầm nhìn (visibility graph) VG=(V, E) thỏa mãn

mỗi đỉnh của ràng buộc cản trở có nút tương ứng trong V, và hai nút v1 và v2

trong V được kết nối bằng một cạnh trong E nếu và chỉ nếu chúng thể hiện là

nhìn thấy nhau. Đồ thị tầm nhìn là quá trình tiền xử lý để tính toán khoảng

cách cản trở giữa hai đối tượng dữ liệu trong một không gian mặt phẳng.

Khoảng cách cản trở là một khoảng cách khúc ngoặt giữa hai đối tượng

dữ liệu khi xem xét đồ thị tầm nhìn. Mỗi khi đồ thị tầm nhìn được xây dựng,

Micro-clustering được áp dụng là quá trình tiền xử lý nhóm các đối

tượng dữ liệu từ cùng một cụm để tối thiểu hóa số lượng các đối tượng dữ

liệu được xét trong phân cụm COD-CLARANS và làm vừa tập dữ liệu

trong bộ nhớ chính. Song song với việc sử dụng thuật toán phân cụm

CLARANS, COD-

CLARANS sử dụng một hàm tỉa để giảm không gian tìm kiếm bằng

cách tối thiểu hóa các lỗi khoảng cách khi lựa chọn cách miêu tả các cụm.

Không may, COD-CLARANS kế thừa các bài toán từ CLARANS, một

phương phâp phân cụm phân hoạch nên COD-CLARANS nhạy cảm với

nhiễu và chấp nhận quá trình tiền xử lý trong không gian dữ liệu có ảnh

hưởng lớn khi xét các ràng buộc cản trở.

42

2.4.1.4. Thuật toán DBCluC

Như đã đề cập ở các phần trên, phần này tôi sẽ tập trung nghiên cứu và

trình bày chi tiết thuật toán DBCluC. Trước khi đi vào nội dung của thuật toán

này, tôi đã trình bày các khái niệm liên quan đến thuật toán DBCluC ở phần

chương 1.

2.4.1.5. Mô hình hóa các ràng buộc

Chúng ta đã định nghĩa bài toán phân cụm dữ liệu ràng buộc trong phần

trên. Xét về tính hiệu quả của quá trình phân cụm thì yếu tố quan trọng đó là mô

hình hóa các ràng buộc một cách hiệu quả hiệu quả thì sẽ hạn chế tác động lên

các cụm của thuật toán DBCluC. Như đã đề cập trong các phần trước, chúng ta

mô hình hóa các ràng buộc vật lý bằng các đa giác. Tuy nhiên, với số lượng các

ràng buộc cản trở nhiều thì chúng ta sẽ có một số lượng lớn các cạnh để kiểm tra

cho việc phân chia các không gian tầm nhìn Trong phần này, tôi sẽ trình bày một

mô hình hóa các đa giác mà giảm tối thiểu số lượng các cạnh xem xét.

* Mô hình hóa ràng buộc cản trở

Nhiều lĩnh vực nghiên cứu như khai phá dữ liệu không gian, hình học

tính toán, đồ họa máy tính,… đã xem xét các ràng buộc cản trở là các đa giác.

Hiệu quả cả các thuật toán đã sử dụng đa giác để miêu tả các ràng buộc cản

trở là phụ thuộc vào kích thước đầu vào, tức là số lượng các cạnh đa giác. Cụ

thể đối với việc tìm một đường ngắn nhất giữa điểm bắt đầu và điểm kết thúc

có các ràng buộc cản trở thì yêu cầu phải đánh giá các ràng buộc cản trở để tối

thiểu hóa khoảng cách. Hiểu kết nối giữa các điểm dữ liệu cũng cần thiết để

đánh giá các ràng buộc cản trở. [1] và [4] thảo luận bài toán phân cụm có các

ràng buộc cản trở, nhưng [4] không trình bày rõ ràng cách để mô hình hóa các

ràng buộc cản trở. Mặc dù [1] mô hình hóa các ràng buộc cản trỏ sử dụng một

đồ thị tầm nhìn nhưng các tác giả không trình bày các loại ràng buộc cản trở

cụ thể, tuy nhiên đồ thị tầm nhìn không đưa vào để đánh giá độ phức tạp hoặc

thời gian thực hiện.

43

Trong [5] đưa mô hình hóa các ràng buộc cản trở bằng các đa giác,

một đa giác được biểu diễn bằng tập nhỏ nhất các đoạn đường thẳng, được

gọi là các đường cản trở, không thỏa mãn Định nghĩa 2.1 về ràng buộc cản

trỏ. Tập các đường cản trỏ này nhỏ hơn số lượng các cạnh trong đa giác.

Điều này dẫn đến giảm kích thước đầu vào. Các đường cản trở trong một đa

giác phụ thuộc vào loại đa giác: đa giác lồi hoặc đa giác lõm. Chú ý rằng

một ràng buộc cản trở tạo ra số lượng các không gian tầm nhìn cùng với số

lượng các điểm lồi. Trước khi trình bày ý tưởng chuyển đổi một đa giác biểu

diễn ràng buộc cản trở thành một đa giác có số lượng các đoạn đường thẳng

nhỏ hơn (các đường cản trở), chúng ta cần kiểm tra đa giác đó là lồi hoặc

lõm. Nếu một điểm bất kỳ của đa giác biểu diễn ràng buộc cản trở được

phân loại thành lõm thì đa giác này được nói là đa giác lõm. Ngược lại nói là

đa giác lồi. Kiểm tra tính lồi của đa giác là yếu tố cơ bản trong xác định các

đường cản trở. Khi đó bài toán kiểm tra tính lồi hoặc lõm thành xác định các

điểm đa giác là lồi hoặc lõm. Quá trình kiểm tra kiểm tra điểm lồi để xác

định các đường cản trở (biểu diễn đa giác nhỏ hơn của đa giác miêu tả các

ràng buộc cản trở) được đưa ra chi tiết trong [4]. Với phạm vi của báo cáo

nên trong phần này tôi chỉ trình bày ý tưởng cơ bản.

* Giảm đa giác biểu diễn ràng buộc cản trở

Để tạo ra các đường cản trở cho đa giác miêu tả ràng buộc cản trở, đầu

tiên chúng ta cần xác định loại của đa giác, đa giác lồi hoặc đa giác lõm vì số

lượng các đường cản trở phụ thuộc vào loại của của đa giác miêu tả ràng buộc

cản trở. Kiểm tra điểm lồi cho một điểm của đa giác miêu tả ràng buộc cản trở

dựa trên việc kiểm tra có hay không một đoạn đường kéo dài mà cắt các cạnh

còn lại của đa giác miêu tả ràng buộc cản trở. Mỗi khi chúng ta xác định được

loại đa giác là lỗi hoặc lõm, chúng ta tìm các đường cản trở để thay thế các

đoạn thẳng ban đầu của đa giác miêu tả ràng buộc cản trở bằng cách đảm bảo

các không gian tầm nhìn không bị phân chia hoặc bị chộn. Rõ ràng với một đa

44

giac lồi có số điểm của không gian tầm nhìn (Định nghĩa 2) bằng số lượng các

điểm lồi của đa giác miêu tả ràng buộc cản trở do mỗi đoạn đường thẳng từ các

khối điểm lồi nhìn các không gian tầm nhìn láng giềng của nó. Ngược lại, một

điểm lõm không tạo ra hai không gian tầm nhìn. Nó thực hiện có một không

gian tầm nhìn. Một điểm lồi tạo ra hai không gian tầm nhìn liền kề nhau.

Chúng ta quan sát thực tế rằng với hai đoạn liền kề nhau dùng một

điểm lồi trong một đa giác miêu tả ràng buộc cản trở, một trong chúng là đủ

để cản trở tầm nhìn giữa hai không gian tầm nhìn láng giềng mà được tạo ra

bởi điểm lồi. Do vậy đủ để tìm một tập các đường cản trở mà cản trở các

không gian tầm nhìn liền kề nhau của mỗi điểm lồi từ một đa giác miêu tả

ràng buộc cản trở, trong khi các đường cản trở là ở trong và không tương tác

với đa giác miêu tả ràng buộc cản trở. Bây giờ, rõ ràng rằng chúng ta có thể

giảm số lượng các đoạn đường thẳng ban đầu từ một đa giác lồi miêu tả ràng

buộc cản trở tới [N/2] đoạn, ở đây N là số lượng các điểm trong đa giác lồi.

Tuy nhiên, đối với đa giác lõm không như vậy. Yêu cầu trong một đa giác

lõm cần kiểm tra nếu một đường cản trở được tương tác với một đoạn đường

thẳng từ đa giác lõm và ngoài đa giác lõm. Nếu một đường cản trở có thể được

tương tác với đoạn từ hoặc ngoài tới một đa giác lõm miêu tả ràng buộc cản trở,

khi đó đa giác này được thay thế với tập các đường cản trở mà có thể là các đoạn

đường thẳng từ đa giác lõm hoặc là trong và không tương tác với đa giác lõm

miêu tả ràng buộc cản trở. Các độ đo này sẽ đảm bảo rằng số lượng các đường cản

trở tạo ra nhỏ hơn số lượng các cạnh đa giác bau đầu miêu tả ràng buộc cản trở.

Hình 2.8: Các đa giác đơn giản và tạo ra các đường cản trở

45

2.4.1.6. Mô hình hóa ràng buộc cắt ngang (cây cầu)

Ràng buộc cắt ngang cũng được mô hình hóa bằng một đa giác. Tuy

nhiên, đa giác miêu tả ràng buộc cắt ngang này có vài điểm và các cạnh đặc

biệt được gọi là các entry point và entry edge (Định nghĩa 2.5). Các entry

point này tương ứng cho việc liên kết các điểm dữ liệu gần từ các cụm khác

nhau. Một điểm hoặc cạnh từ đa giác cây cầu mà không là entry point hoặc

entry edge, được định nghĩa bởi người sử dụng hoặc ứng dụng, không đóng

vai cắt ngang. Một entry edge bất kỳ được thay thể bởi tập entry point dọc

theo cạnh bắt đầu từ một điểm cuối của cạnh tới điểm khác, thỏa mãn các

entry point này được tách biệt bởi một giá trị khoảng cách de ở đây de  Eps.

Do vậy, một cây cầu được biểu diễn bằng một tập các entry point mà mở

rộng có thể đạt được sự gần bởi các cụm. Chú ý rằng hướng của ràng buộc cắt

ngang không được mô hình hóa và là một chủ đề của nghiên cứu tương lai.

2.4.2. Thuật toán

Mỗi khi chúng ta cô đọng lại các ràng buộc cản trở sử dụng thuật

toán giảm đa giác và mô hình hóa các ràng buộc cắt ngang, DBCluC bắt

đầu thủ tục phân cụm từ một điểm dữ liệu tùy ý. Để lựa chọn tùy ý một

điểm khởi đầu, DBCluC có thể xét các ràng buộc cắt ngang sau khi hoặc

trong khi phân cụm các điểm dữ liệu. Sự mềm dẻo này tạo ra DBCluC

xem xét lại các cụm được khám phá. Thủ tục phân cụm trong DBCluC là

khá giống với DBSCAN

[4]. Như đã minh họa trong [4], khoảng cách giữa các cụm C1 và C2 được

định nghĩa là khoảng cách nhỏ nhất giữa các điểm dữ liệu trong C1 và C2.

Thông thường các cụm được định nghĩa rằng không thỏa mãn với Định

nghĩa 2.6 hoặc khoảng cách của chúng giữa các cụm là lớn hơn Eps được

riêng biệt. Trong thuật toán DBCluC dưới đây (Thuật toán 1), các ràng buộc

46

cắt ngang được xem xét trong khi phân cụm các đối tượng dữ liệu. Một CSDL

là tập các điểm dữ liệu được phân cụm trong thuật toán. Dòng 1 thủ tục khởi

tạo phân cụm từ một tập các entry point mà được mô hình hóa từ các ràng

buộc cắt ngang. Do vậy tập các điểm dữ liệu được nhóm lại liên quan tới kết

nối cắt ngang từ một các entry point trong các ràng buộc cắt ngang. Mỗi khi

tập các cụm tối đa được định nghĩa sau dòng 1, dòng 3 xây dựng một cụm từ

các đối tượng dữ liệu mà không thỏa mãn với kết nối cắt ngang trong CSDL.

Dòng 4 gán một id cho cụm mới.

ExpandCluster có thể tương đương với hàm trong [4]. Tuy nhiên, sự khác

biệt đó là các ràng buộc cản trở được xem xét trong RetrieveNeighbours (Point,

Eps, Obstacles). Có một điểm truy vấn, các láng giềng của điểm truy vấn được

tìm sử dụng SR-tree. Trong DBCluC, chúng ta đã theo phương pháp truy vấn

khoảng láng giềng thay vì phương pháp truy vấn láng giềng gần nhất từ SR-tree,

do vậy chúng ta vô cùng khó cho việc mở rộng một tập các cụm, nếu mật độ của

các điểm dữ liệu cao. Thời gian chạy trung bình của một truy vấn láng giềng là

O(logN), ở đây N là số lượng các đối tượng dữ liệu. Mỗi khi tìm các láng giềng

của một điểm truy vấn, để đánh giá các tầm nhìn giữa một điểm truy vấn và các

láng giềng của nó. Tầm nhìn giữa hai đối tượng dữ liệu ràng buộc cản trở được

tính toán sử dụng một đoạn đường thẳng các điểm cuối của nó là hai đối tượng

dữ liệu. Nếu một đoạn đường thẳng bất kỳ biểu diễn một ràng buộc cản trở được

tương tác với đoạn đường thẳng trên, khi đó hai điểm dữ liệu không được nhóm

cùng nhau, do vậy chúng không nhìn thấy nhau theo Định nghĩa 2.2.

Các láng giềng được chấp nhận trên được định nghĩa là SEED mà được

tìm từ RetrieveNeighbours(Point, Eps, Obstacles) duy trì mở rộng một cụm từ

các phần tử của SEED, nếu số lượng các phần tử trong SEED không nhỏ hơn

MinPts. Chú ý rằng Dòng 7 trong Thuật toán 2 không có Nhiễu từ một phần

tử của SEED để cải thiện hiệu quả truy vấn.

47

Hình 2.9: Thuật toán 1: phân cụm có các ràng buộc

Hình 2.10: Thuật toán 2: Mở rộng một cụm

Hình 2.11: Tìm các điểm láng giềng

48

2.5. Kết luận

Trong chương này, đầu tiên tôi trình bày những kiến thức cơ bản liên

quan đến Phân cụm dữ liệu. Sau đó, tôi trình bày các kỹ thuật tiếp cận trong

Phân cụm dữ liệu và trong mỗi kỹ thuật tôi trình bày một thuật toán đại diện.

Đặc biệt, tôi trình bày thuật toán phân cụm dữ liệu ràng buộc và đi sâu vào

thuật toán DBCluC. Như vậy, chúng ta thấy trong phân cụm dữ liệu không

gian khi phân cụm không xét đến các ràng buộc thì kết quả sẽ không được

chính xác. Để giải quyết vấn đề này, trong chương tôi trình bày hai thuật

toán (Thuật toán COD-CLARANS, Thuật toán DBCluC và đi sâu vào thuật

toán DBCluC. Để có thể biết được hiệu quả của thuật toán phân cụm ràng

buộc này, trong chương tới tôi sẽ tiến hành xây dựng thử nghiệm. Từ đó đưa

ra kết quả và đánh giá.

49

Chương 3

CÀI ĐẶT VÀ THỬ NGHIỆM

3.1. Phân tích bài toán

Chương 1 đã phát biểu sơ bộ mục đích, ý nghĩa của bài toán tìm vị trí

tối ưu đă ̣t điểm tâ ̣p kết Nhà hàng trong nội thành Hà Nội. Yêu cầu của bài

toán là: tìm ra các vị trí nằm càng gần các khu vực tâ ̣p trung đông ngườ i như

cơ quan, công ty, khách sạn, siêu thị, bê ̣nh viê ̣n…càng tốt. Trong khuôn khổ

của luận văn, cơ sở để giải quyết bài toán này là dựa trên việc khai phá dữ

liệu không gian, cụ thể là thực hiện phân cụm các điểm tiện ích để tìm ra phân

bố không gian của chúng một cách tự động, từ đó hỗ trợ việc ra quyết định

lựa chọn các vị trí gần nhất tới các cụm điểm tiện ích.

Phần này làm rõ bài toán cũng như tính khả thi của nó thông qua việc xem

xét các yếu tố quyết định đến kết quả của bài toán, các yếu tố này bao gồm:

- Dữ liệu đầu vào.

- Phạm vi bài toán.

- Phương pháp kỹ thuật sử dụng để giải quyết bài toán.

3.1.1. Nguồn dữ liệu đầu vào và phạm vi bài toán

Dữ liệu bản đồ số các tỉnh thành của Việt Nam nhìn chung còn hạn chế

về số lượng, chất lượng và thường không đồng bộ về tỷ lệ bản đồ, nội dung

hiển thị. Đa phần bản đồ số chỉ bao gồm các lớp về ranh giới hành chính, địa

hình. Các thông tin về các điểm tiện ích như khu du lịch, khách sạn, nhà hàng,

siêu thị, đền chùa, khu vui chơi giải trí, vân vân, đều rất hạn chế. Đặc điểm

của bài toán khai phá dữ liệu nói chung và phân cụm dữ liệu nói riêng là tính

hiệu quả phụ thuộc nhiều vào khối lượng dữ liệu đầu vào.

Trong số các nguồn dữ liệu bản đồ số mà học viên tiếp cận được, dữ liệu

bản đồ thành phố Hà Nội là phong phú nhất, trong đó bao gồm 21 lớp thông tin

bản đồ, được chia thành 9 nhóm thông tin như: nhóm lớp thông tin bản đồ nền,

nhóm Văn hóa, giáo dục, Y tế, Kinh doanh và dịch vụ, Du lịch, hành chính…

50

Trong các lớp thông tin trên, lượng thông tin chủ yếu tập trung ở khu

vực nội thành và các lớp thông tin có ý nghĩa đối với yêu cầu đặt ra của bài

toán chủ yếu là các lớp thông tin dạng điểm tiện ích như:

- Khách sạn, nhà khách

- Siêu thị

- Ngân hàng

- Nhà hàng, quán bia, cà phê

Như vậy, dữ liệu đầu vào sử dụng được cho bài toán chủ yếu là các lớp

thông tin dạng điểm, phạm vi chủ yếu trong nội thành Hà Nội.

3.1.2. Phương pháp kỹ thuật giải quyết bài toán

Để giải quyết bài toán, cần thực hiện phân cụm các lớp dữ liệu điểm

tiện ích, có hai cách tiếp cận:

- Sử dụng phân cụm đa chiều.

- Phân cụm đơn chiều trên các lớp dữ liệu và thực hiện tổng hợp các

kết quả phân cụm.

Học viên lựa chọn tiếp cận thứ hai với lý do mong muốn áp dụng một bài

toán quan trọng của hệ thông tin địa lý là bài toán chồng phủ bản đồ. Theo cách

tiếp cận này, từng lớp dữ liệu điểm tiện ích sau khi phân cụm sẽ thực hiện xây

dựng đường bao của các cụm, tạo thành một lớp bản đồ dạng vùng bao phủ của

các cụm. Tiến hành chồng phủ các lớp bản đồ dạng vùng này sẽ thu được vùng

giao cắt là vùng thỏa mãn tiêu chí: khoảng cách địa lý tới các cụm điểm tiện ích

là nhỏ nhất, là vị trí có thể coi là tối ưu để đặt các điểm tiện ích Nhà hàng.

Lựa chọn phương pháp phân cụm

Với đặc điểm của dữ liệu đầu vào như đã đề cập ở trên, chúng ta lựa

chọn phương pháp phân cụm theo mật độ bởi:

Thứ nhất: đối tượng phân cụm chủ yếu là các điểm tiện ích, tức là các

đối tượng dạng điểm. Kiểu đối tượng này khá phù hợp với phương pháp phân

cụm theo mật độ.

51

Thứ hai: không cần thiết phải biết trước số cụm điểm tiện ích phân

hoạch được, do đó không sử dụng tiếp cận phân hoạch.

Thứ ba: Không cần lưu trữ thông tin các mức trung gian trong quá trình

phân cụm, do đó không sử dụng tiếp cận theo lưới.

Lựa chọn độ đo sử dụng trong phân cụm

Chúng ta quan tâm đến tính liên tục về mặt không gian của các điểm

tiện ích trong cụm và khoảng cách giữa các điểm này chứ không quan tâm

đến hướng của chúng. Hơn nữa với các đối tượng dạng điểm, quan hệ về

topology mang ít ý nghĩa ngoại trừ các đối tượng này mang thông tin về mạng

lưới liên thông như: mạng lưới cột điện, mạng lưới cấp nước…Do vậy ta sử

dụng độ đo khoảng cách trong bài toán phân cụm đã đề ra.

3.2. Xây dựng chương trình ứng dụng

3.2.1. Phân tích thiết kế hệ thống

Hệ thống phải đảm bảo cung cấp các chức năng tối thiểu của một hệ

thông tin địa lý như:

- Duyệt bản đồ

- Phóng to

- Thu nhỏ

- Trượt bản đồ

- Xem thông tin bản đồ

Ngoài ra, phục vụ yêu cầu của bài toán đã đề ra, hệ thống cần có thêm

các chức năng:

- Phân cụm dữ liệu

- Chồng phủ bản đồ

- Lưu kết quả chồng phủ

Trên cơ sở phân tích các chức năng của hệ thống như trên, chúng ta

xây dựng được biểu đồ Use case thể hiện các chức năng chính của hệ

thống như sau:

52

Biểu đồ ca sử dụng

3.2.2. Cài đặt chương trình

Chương trình thử nghiệm được cài đặt bằng ngôn ngữ C#, trong đó có

sử dụng thư viện mã nguồn mở SharpMap do tác giả Morten Nielsen

(www.iter.dk) và cộng đồng mã nguồn mở phát triển để hỗ trợ hiển thị bản đồ.

Một số chức năng chính đã được cài đặt trong chương trình:

- Duyệt bản đồ: hiển thị bản đồ, phóng to, thu nhỏ, trượt bản đồ

- Phân cụm dữ liệu bản đồ

- Chồng phủ bản đồ

- Lưu bản đồ

Học viên đã tiến hành cài đặt thử nghiệm 2 thuật toán phân cụm dựa trên

mật độ là thuật toán DBSCAN và DBRS, DBCLUC ngoài ra cũng cài đặt thêm

thuật toán phân cụm dựa trên phân hoạch K-means để so sánh và đánh giá.

53

Một số hình ảnh của chương trình

Hình 3.1: Phân cụm lớ p dữ liê ̣u "Khá ch sa ̣n-Trường học trong nội thà nh Hà Nội, cá c vùng màu và ng là cá c cụm tìm được.

Hình 3.2: Hình ảnh chồng phủ (vùng màu vàng) của các cụm “Siêu thi ̣” (màu xanh) và cá c cụm “Khá ch sa ̣n- Trường học” (màu đỏ). Vùng màu vàng có thể coi là vị trí tối ưu cho việc đă ̣t địa điểm Nhà hàng.

54

Hình 3.3: Kết quả phân cụm DBSCAN đối với dữ liệu thử nghiệm tự tạo

3.3. Thử nghiệm và đánh giá các thuật toán phân cụm

Học viên tiến hành thử nghiệm, so sánh và đánh giá 3 thuật toán đã cài

đặt trên hệ thống như sau:

Đánh giá tổng quan 3 thuật toán

Bảng 3.1: So sánh tổng quan các thuật toán K-means,

DBSCAN và DBRS

K-means DBSCAN DBRS

Độ phức tạp O(tKN) O(NlogN) O(NlogN)

Khả năng phát hiện nhiễu kém Tốt Tốt

không có có

không không có Khả năng phát hiện cụm có hình dạng bất kỳ Khả năng phân cụm theo thuộc tính phi không gian

Kết quả phân cụm Giống nhau Khác nhau ở mỗi lần chạy Khá giống nhau

55

Hình 3.4: Khả năng phát hiện nhiễu và cụm có hình dạng bất kỳ của K-

means (trái) và DBSCAN (phải), đường bao màu xanh là đường biên cụm

Hình 3.5: Khả năng phân cụm theo thuộc tính của DBSCAN (trái) và DBRS (phải)

Đánh giá độ phức tạp thuật toán

Thử nghiệm thứ nhất: Thực hiện phân cụm với cùng một tập dữ liệu

đầu vào: tệp Cosohatang_KTXH bao gồm 4235 mẫu dữ liệu, thực hiện trên

máy tính với CPU 1.6GHz Celeron Mobile đơn lõi, 2GB Ram. Kết quả thu

được như sau:

56

Bảng 3.2: Kết quả so sánh thời gian thực hiện phân cụm của các thuật toán

K-means, DBSCAN và DBRS với cùng một tập dữ liệu đầu vào

Bảng so sánh thời gian thực hiện phân cụm với cùng một tập dữ liệu đầu vào

(với cùng một tập dữ liệu đầu vào: tệp Cosohatang_KTXH với 4235 mẫu dữ liệu

thực hiện trên máy tính với CPU 1.6GHz Celeron Mobile đơn lõi, RAM 2GB)

Thời gian (ms)

Các tham

Thuật

lần

số phân

toán

lần 1 lần 2 lần 3 lần 4 lần 5 lần 6 lần 7 lần 8 lần 9

10

cụm

412 356 449 611

266 577 192 311 621 số cụm = 6

K-means 382

epsilon =

1301.1470,

DBSCAN 1340 1347 1389 1445 1347 1323 1382 1331 1340 1395

MinPts=4

epsilon =

1301.1470,,

MinPts=4

minPur

=0.8,

random

815

727 831 957 909 935 917 856 723 946

DBRS

samplin,

alpha max

=0.01,

thuộc tính

phân cụm:

"tenGoi"

57

Kết quả thể hiện dưới dạng đồ thị như sau:

Hình 3.5: Đồ thị so thời gian thực hiện phân cụm của các thuật toán

K-measn, DBSCAN và DBRS với cùng một tập dữ liệu đầu vào.

Kết quả cho thấy: với cùng số lượng dữ liệu đầu vào, thời gian thực

hiện trung bình của thuật toán K-means thấp nhất, DBSCAN thực hiện lâu

nhất. Đồ thị cũng cho thấy sự biến thiên thời gian thực hiện của K-means với

mỗi bộ tâm cụm ngẫu nhiên ở mỗi lần chạy.

Thử nghiệm thứ 2: Sử dụng các tập dữ liệu đầu vào khác nhau, với số

lượng dữ liệu tăng dần, kết quả thu được như bảng sau:

Bảng 3.3: Kết quả so sánh thời gian thực hiện phân cụm của các thuật

toán K-means, DBSCAN và DBRS trên các tập dữ liệu khác nhau

Bảng so sánh thời gian thực hiện phân cụm với số lượng mẫu dữ liệu khác nhau (với các tập dữ liệu đầu vào khác nhau, thực hiện trên máy tính với CPU 1.6GHz Celeron Mobile đơn lõi, RAM 2GB)

Số mẫu dữ liệu

Các tham số phân cụm

64 mẫu 2

130 mẫu 5

Thời gian (ms) 514 mẫu 19

1153 mẫu 65

270 mẫu 12

2155 mẫu 127

4235 mẫu 238

số cụm = 6

K-means

8

14

19

35

117

717

1298

MinPts=4

DBSCAN

6

7

6

25

93

244

816

DBRS

MinPts=4, minPur =0.8, random sampling, alpha max =0.01

58

Kết quả cho thấy, độ phức tạp thuật toán O(tKn), độ phức tạp thuật

toán O(NlogN). Đồ thị cũng cho thấy thuật toán DBCLUC có thời gian

thực hiện thấp hơn DBSCAN do chỉ duyệt một số hữu hạn điểm ngẫu nhiên

trong cơ sở dữ liệu.

. Độ phức tạp của thuật toán DBCluC

Như đã trình bày ở trên, thuật toán giảm đa giác mô hình hóa các cản

trở và các cắt ngang được phân thành các đa giác cản trở lồi hoặc lõm. Cho

n số lượng các điểm của đa giác p, và ncc và ncv tương ứng là số lượng các

điểm đa giác lồi và số lượng các điểm đa giác lõm với n  ncc  ncv . Kiểm

tra tính chất lồi cho đa giác p yêu cầu (n * ncc * ncv ) trong trường hợp xấu

nhất, nhỏ hơn (n2) . Do vậy, tôi đánh giá với tập các đa giác, độ phức tạp

của giảm đa giác xấp xỉ (n2), ở đây n là số lượng các điểm của đa giác lớn

nhất (tính về cạnh). Giảm đa giác là một giai đoạn tiền xử lý trước khi phân

cụm. Độ phức tạp đối với thuật toán phân cụm xấp xỉ (N * log N * L), ở

đây L là số lượng các đường cản trở được tạo ra bởi thuật toán giảm đa

giác, và N là số lượng các điểm trong cơ sở dữ liệu. Tuy nhiên, độ phức tạp

có thể được giảm tới (N * log N ), nếu chúng ta làm theo phương pháp chỉ

mục cho các cản trở.

Tính hiệu quả

Để có thể so sánh, tôi phải sử dụng các tập dữ liệu đúng đắn với cùng

các ràng buộc. Tuy nhiên, chúng ta không truy cập tới các tập dữ liệu. Xét về

tính hiệu quả, chúng ta chưa biết phân cụm dựa trên mật độ làm tốt hơn các

thuật toán phân cụm sử dụng kỹ thuật phân hoạch như COD-CLARANS. Tôi

đã đánh giá DBCluC bằng cách tạo ra các tập dữ liệu với các hình dạng cụm

phức tạp và biến đổi kích thước dữ liệu cũng như số lượng và tính phức tạp

của các ràng buộc vật lý. Đối với mục đích thử nghiệm, tôi đã tạo ra các tập

dữ liệu tổ hợp.Trong báo cáo này, tôi báo cáo ba thử nghiệm DS1, DS2, và

DS3. Các cây cầu và các cản trở (các dòng sông, các hồ, và đường cao tốc)

59

cũng được đưa vào trong các tập dữ liệu trên. DS1 chứa 434 điểm dữ liệu với

bốn cản trở. Hình 3.6 trình bày 16 đoạn đường thẳng đa giác đã giảm tới 8

đường. Do vậy DS1 là thưa thớt vì vậy được nhóm thành một cụm. Thêm các

cản trở tạo ra bốn cụm khác nhau (Hình 3.6(c)).

Hình 3.6: Phân cụm tập dữ liệu DS1

Hình 3.7 minh họa tính hiệu quả của DBCluC khi xuất hiện các cản trở

và các cắt ngang. Với việc so sánh các kết quả phân cụm, Hình 3.7 minh họa

các điểm dữ liệu, các cản trở, và các cắt ngang liên tục trước khi phân cụm

(a); các kết quả phân cụm khi không xét các ràng buộc (b); các cụm khi xét

các cắt ngang (c); các cụm khi xét các cản trở (d); và các kết quả phân cụm

khi xét các loại ràng buộc: các cản trở và các cắt ngang. Các đường đỏ từ các

cản trở trong tất cả các tập dữ liệu là các đường cản trở để thay thết các đa

giác ban đầu mà được vẽ lại màu blue. Các cắt ngang từ DS2 và DS3 được vẽ

lại bằng các đường red và black tương ứng là các cạnh entry và non-entry.

DS2 có khoảng 1063 điểm dữ liệu, 4 đối tượng cản trở và hai đối tượng

cắt ngang. Có 6 cụm nếu không xét các ràng buộc (cản trở và cắt ngang), trình

bày trong Hình 3.6(b). DS2 trình bày trực giác bài toán mà tôi nghiên cứu

trong báo cáo này. Phân cụm chính xác là 8 cụm. Mặc dù một cụm là đủ nhỏ

để truy cập một cắt ngang từ (c) trong Hình 3.7. DS3 có 11775 điểm dữ liệu

với 6 cản trở (gồm có 29 đoạn đường thẳng) và 2 cây cầu. Hai 29 đoạn đường

thẳng ban đầu mô tổ các cản trở được thay thế với 15 đường cản trở.

60

Hình 3.7: Phân cụm DS2

Tôi cũng xây dựng các thử nghiệm thay đổi kích thước của các tập dữ

liệu và số lượng các cản trở để mô phỏng tính co giãn của DBCluC. Hình

3.7(a) trình bày thời gian thực hiện trong hai giây đối với tám tập dữ liệu có

kích thước thay đổi từ 25K đến 200K với sự tăng 25K điểm dữ liệu. Hình 3.7

trình bày một sự co giãn tốt. Thời gian thực hiện phần lớn là tuyến tính theo

số lượng các đối tượng dữ liệu. Hình 3.7(b) trình bày thời gian thực hiện

trong hai giấy cho việc phân cụm 40K đối tượng dữ liệu nhưng bằng cách

thay đổi số lượng các cản trở. Số lượng theo trục X miêu tả số lượng tổng các

cạnh đa giác và các đường cản trở tương ứng. Chú ý rằng, thuật toán giảm đa

giác ở trên đã thành công trong việc giảm số lượng các đường xấp xỉ một nửa

thời gian. Sự chênh lệch trong việc tăng các cạnh đa giác không là hằng số.

Tuy nhiên, trong phần tăng của các đa giác, thời gian thực hiện tuyến tính. Do

vậy, DBCluC là co giãn với các cơ sở dữ liệu lớn với sự kết hợp các cản trở

và các cây cầu theo hướng kích thước của cơ sở dữ liệu và theo hướng số

lượng các ràng buộc.

61

KẾT LUẬN VÀ KIẾN NGHỊ

Từ việc nghiên cứu Tổng quan về Khai phá tri thức và Khai phá dữ liệu

dẫn đến có cái nhìn khái quát về Khai phá dữ liệu như: Khái niệm, ứng dụng

và các kỹ thuật trong KPDL. Sau đó, tôi nghiên cứu Khái quát về Phân cụm

dữ liệu và đi sâu vào các phương pháp phân cụm dữ liệu không gian và có

ràng buộc như Thuật toán DBSCAN, DBRS và DBCluC. Cuối cùng, tôi tiến

hành xây dựng chương trình demo sử dụng thuật toán DBCSAN và đánh giá

kết quả, nhận xét.

Như vậy, với thời gian ngắn ngủi, về mặt cơ bản tôi đã đáp ứng được

yêu cầu của luận văn đề ra và đã giành được một số kết quả như sau:

- Quyển báo cáo có thể làm tài liệu tham khảo về Khai phá dữ liệu nói

chung và Phân cụm dữ liệu và phn cụm có rang buộc nói riêng.

- Xây dựng được chương trình demo thử nghiệm.

Trong thời gian tới, tôi sẽ tiếp tục nghiên cứu những vấn đề sau:

- Tiếp tục ứng dụng thuật toán DBCluC trong không gian dữ liệu 3 chiều,...

- Tiếp tục hoàn thiện và phát triển chương trình demo có thể ứng dụng

với các tập dữ liệu lớn.

Trong quá trình làm luận văn, tôi đã cố gắng rất nhiều, tuy nhiên không

tránh khỏi những thiếu sót, tôi mong rằng sẽ nhận được các ý kiến đóng góp

của các Thầy giáo, Cô giáo, các bạn bè, đồng nghiệp để bản luận văn ngày

càng hoàn thiện hơn.

62

TÀI LIỆU THAM KHẢO

Tài liệu tiếng việt

[1] Đặng Văn Đức (2001), Hệ thống thông tin địa lý, NXB Khoa học và Kỹ

Thuật, Hà Nội.

Tài liệu tiếng Anh

[2] Han J. and M. Kamber (2000), Data Mining: Concepts and Techniques, Morgan

Kaufman.

[3] Osmar R. Zaїane and Chi-Hoon Lee, Clustering Spatial Data in the

Presence of Obstacles and Crossings: a Density-Based Approach,

Database Laboratory, Deparment of Computing Science, University of

Alberta, Canada

[4] Tung A. K. H., Ng R., Lakshmanan L. V. S. and Han J. (2001), Constranint-

based clustering in large database, In Proc. ICDT, pp 405-419

[5] Wang, X., & Hamilton, H.J. (2003), “DBRS- A Density-Based Spatial

Clustering Method with Random Sampling”, 7thPAKDD, Seoul, Korea,

pp. 563-575.