ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
 & 
Bài tập lớn Cơ sở dữ liệu nâng cao
Đề tài: Phương pháp phân tích cụm trong khai phá dữ liệu
không gian
Giảng viên : PGS.TS Nguyễn Hà Nam
Nhóm thực hiện : Nhóm 19
Sinh viên thực hiện : Khúc Ngọc Hiệp
Nguyễn Quang Minh
Hà Nội – 3/2012
1
Mục lục
Mục lục 2
Danh sách hình vẽ 3
Giới thiệu 4
1.Cơ sở dữ liệu không gian 5
1.1 Định nghĩa 5
1.2 Các đặc điểm của cơ sở dữ liệu không gian 5
2.Khai phá dữ liệu không gian 8
2.1 Định nghĩa 8
2.2 Đặc điểm của khai phá dữ liệu không gian 8
3.Phân tích phân cụm 11
3.1 Giới thiệu về phân tích phân cụm 11
3.2 Các thuật toán phân cụm 12
3.3 Phân cụm theo phân bố 12
4.Kết luận 15
5.Tài liệu tham khảo 16
2
Danh sách hình vẽ
Hình 1: Kiểu dữ liệu không gian trong Oracle Spatial 6

tính sau:
• Là một cơ sở dữ liệu
• Có các kiểu dữ liệu không gian trong mô hình dữ liệu và ngôn ngữ truy vấn của nó
• Hỗ trợ các kiểu dữ liệu không gian và cung cấp ít nhất là chỉ số không gian (spatial
indexing) và một thuật toán hiệu quả cho phép kết không gian (spatial joins).
1.2 Các đặc điểm của cơ sở dữ liệu không gian
Cơ sở dữ liệu không gian cho phép quản lý và xử lý các dữ liệu liên quan đến bản đồ. Phần sau
đây sẽ nói về các đặc điểm của nó, bao gồm các kiểu dữ liệu không gian, đánh chỉ số không gian
(spatial indexing) và phép kết không gian.
Các kiểu dữ liệu không gian
Các cơ sở dữ liệu truyền thống được thiết kế để quản lý và xử lý dữ liệu chữ-số thể hiện bởi
chuỗi các ký tự, giá trị số, ngày tháng và giá trị đúng sai. Nó không có sự chuẩn bị để hỗ trợ để
lưu trữ và xử lý dữ liệu không gian mà được thể hiện bởi các điểm, đường, đa giác và bề mặt.
Các cơ sở dữ liệu hướng đối tượng và cơ sở dữ liệu quan hệ cho phép người dùng định nghĩa các
kiểu dữ liệu trừu tượng mô tả cấu trúc cột phức tạp trong cơ sở dữ liệu. Một vài nhà cung cấp
phần mềm cơ sở dữ liệu đã sử dụng khả năng này để định nghĩa các kiểu dữ liệu không gian cho
phép sản phẩm của họ quản lý và xử lý tốt các dữ liệu không gian.
Mỗi nhà cung cấp phần mềm cơ sở dữ liệu cài đặt một cách khác nhau, ví dụ Oracle Spatial có
chín kiểu dữ liệu không gian cơ bản bao gồm điểm, đường thẳng, đường cong, đường phức hợp,
đa giác, đa giác cong, đa giác phức hợp, hình tròn và hình chữ nhật. Trong khi đó, DB2 Spatial
Extender của IBM lại sử dụng thuật ngữ hình học để mô tả các kiểu dữ liệu không gian của nó
với điểm, đa điểm, đường, đa đường, đa giác, hợp đa giác và ellipse.
5
Trong khi các thuật ngữ được sử dụng khác nhau, các mô hình dữ liệu cơ bản và các hàm và
phép toán lại khá là nhất quán.
Hình 1: Kiểu dữ liệu không gian trong Oracle Spatial
Hình 2: Kiểu dữ liệu không gian trong DB2 Spatial Extender
Đánh chỉ số dữ liệu không gian
Đánh chỉ số dữ liệu không gian cũng có mục đích tương tự như trong các cơ sở dữ liệu truyền
thống, là để nhanh chóng tìm kiếm được giá trị mong muốn từ cơ sở dữ liệu không gian, tuy

Khai phá dữ liệu không gian là một lĩnh vực ứng dụng đặc biệt của khai phá dữ liệu. Nó được đặt
nền móng từ khai phá dữ liệu truyền thống và dựa chủ yếu vào các công nghệ khai phá dữ liệu
tổng quát để điều khiển các thuộc tính của dữ liệu không gian.
Khai phá dữ liệu không gian là quá trình khám phá các mẫu đáng chú ý, có ích tiềm tàng, chưa
biết trước từ các tập dữ liệu không gian lớn. Phân tích các mẫu đáng chú ý và có ích từ các tập
dữ liệu không gian khó hơn rất nhiều so với việc phân tích các mẫu tương ứng từ các dữ liệu
chữ-số truyền thống bởi vì sự phức tạp của các kiểu dữ liệu không gian và các mối quan hệ
không gian.
Để sử dụng các kỹ thuật và khái niệm của khai phá dữ liệu trong lĩnh vực không gian, chúng ta
phải cải tiến chúng về cả lý thuyết và kỹ thuật để phù hợp với các tính chất của dữ liệu không
gian và đáp ứng được yêu cầu của người sử dụng trong ra quyết định không gian.
2.2 Đặc điểm của khai phá dữ liệu không gian
Khai phá dữ liệu không gian phức tạp hơn khai phá dữ liệu truyền thống rất nhiều do đặc thù của
dữ liệu không gian:
• Cấu trúc dữ liệu không gian. Dữ liệu không gian thường mang thông tin về vị trí và địa
hình, thường được tổ chức bằng các cấu trúc đánh chỉ số phức tạp và được truy xuất bởi
các phương pháp truy xuất không gian.
8
• Tập dữ liệu không gian. Các cơ sở dữ liệu không gian luôn chứa một lượng lớn dữ liệu
thật sự và nó thường có định dạng và chất lượng hỗn tạp và đòi hỏi một lượng tính toán
đáng kể để làm sạch và lựa chọn chúng để sử dụng trong khai phá dữ liệu.
• Thu thập dữ liệu không gian. Rất nhiều dữ liệu không gian được sử dụng ngày nay đã
được thu thập bằng cách lấy mẫu và được cung cấp tạm thời dưới dạng tập hợp. Đặc tính
này có nghĩa là những thông tin hay thay đổi có thể bị mất bởi vì thiết kế lấy mẫu và
phiên dịch trong thu thập dữ liệu, tính toán và các quá trình biên dịch.
• Phụ thuộc không gian. Các đặc điểm của không gian thường liên hệ với nhau về bản
chất, vì vậy thường là khó hoặc không thể khám phá ra các kiến thức ẩn trong dữ liệu nếu
không có kiến thức trước về các đặc tính của tập dữ liệu cần phân tích. Kiến thức đó
thường không dễ để tìm thấy.
• Tính tạm thời của dữ liệu không gian. Đặc điểm của không gian là liên hệ và kết nối

3. Phân tích phân cụm
Ở phần trước chúng ta đã tìm hiểu về khai phá dữ liệu không gian. Để khai phá thành công một
cơ sở dữ liệu không gian được thu thập với số lượng vô cùng lớn đòi hỏi phải có các kỹ thuật bổ
trợ cho thao tác và làm sạch dữ liệu để chuẩn bị cho phân tích chúng. Có ba phương pháp được
đưa ra và phát triển để hỗ trợ chuẩn bị dữ liệu bao gồm phân lớp dữ liệu không gian, phân tích xu
hướng không gian và phân cụm dữ liệu không gian.
Các thuật toán phân lớp dữ liệu không gian và phân tích xu hướng không gian được phát triển và
kiểm thử, tuy nhiên nó đòi hỏi tính toán rất lớn đặc biệt là với tập lớn dữ liệu. Phương pháp thú
vị nhất và được phát triển rất tốt để thao tác và làm sạch dữ liệu không gian để chuẩn bị cho phân
tích khai phá dữ liệu không gian được chỉ ra là sử dụng phân tích phân cụm. Phần sau đây sẽ tìm
hiểu chi tiết về phương pháp phân cụm dữ liệu không gian.
3.1 Giới thiệu về phân tích phân cụm
Phân tích cụm hay phân cụm là công việc gán một tập các đối tượng lại thành các nhóm (cụm)
sao cho các đối tượng trong cùng một cụm là giống nhau (theo một tiêu chí nào đó) hơn so với
các đối tượng nằm trong các cụm khác.
Phân cụm là một trong những nhiệm vụ chính của khai phá dữ liệu, và là một kỹ thuật chung cho
phân tích dữ liệu thống kê được sử dụng trong nhiều lĩnh vực, bao gồm học máy (machine
learning), nhận dạng mẫu, phân tích ảnh, phục hồi thông tin, và thông tinh sinh học.
Phân tích cụm bản thân nó không phải là một thuật toán riêng, mà là một nhiệm vụ chung cần
được giải quyết. Nó có thể đạt được bằng rất nhiều các thuật toán khác nhau, khác nhau từ trong
khái niệm về cái gì tạo thành một cụm và làm thế nào để tìm được nó một cách hiệu quả.
Các khái niệm chính về cụm bao gồm một nhóm với các khoảng cách ngắn giữa các thành viên
trong nhóm, là các vùng dày đặc của không gian dữ liệu hoặc các phân bố thống kê nhất định.
Phân cụm vì vậy mà được phát biểu một cách hệ thống là một bài toán tối ưu với nhiều mục tiêu.
Thuật toán phân cụm phù hợp và các bố trí tham số (bao gồm các giá trị như là khoảng cách, mật
độ hay số lượng cụm mong muốn) phụ thuộc vào các tập dữ liệu riêng và mục tiêu sử dụng của
kết quả. Phân tích phân cụm vì vậy mà không phải là một công việc tự động, trong quá trình lặp
của quá trình khai phá kiến thức hoặc quá trình lặp của tối ưu hóa với nhiều mục tiêu mà liên
quan đến các phép thử (trial and error), nó thường cần phải thay đổi các tiền xử lý và các tham số
cho đến khi đạt được kết quả mong đợi.

tính đồng nhất của mỗi cụm đã được phát hiện và và tính đồng nhất giữa các cụm đã được phát
hiện. Quá trình lặp để phát hiện các cụm sẽ dừng lại sau khi một hoặc nhiều lần quét qua dữ liệu
đầu vào nếu không có thêm thời gian để quét lần nữa hoặc nếu sự cải thiện của các cụm theo tiêu
chuẩn gà chọi không biện minh cho một lần quét mới.
Thông thường, dữ liệu nhân khẩu học bao gồm số lượng lớn của các biến chủng loại, vì vậy rất
phù hợp với phương pháp phân cụm theo phân bố.
Mô hình phân cụm này liên hệ chặt chẽ với các thống kê dựa trên dựa trên các mô hình phân bố.
Các cụm có thể được định nghĩa thành các đối tượng thuộc về cùng một phân bố một cách dễ
dàng. Một thuộc tính rất đẹp của cách tiếp cận này là nó rất giống với cách các tập dữ liệu nhân
tạo được tạo ra: bằng cách lấy mẫu ngẫu nhiên các đối tượng từ một phân bố.
Trong khi nền móng lý thuyết của phương pháp này là tuyệt vời, chúng lại có một vấn đề chính
được biết đến như là overfitting, nếu không có các ràng buộc được đưa ra cho độ phức tạp mô
hình.
Phương pháp đáng chú ý nhất được biết đến là thuật toán tối ưu hóa mong muốn (expectation-
maximization hay ngắn gọn là EM-clustering). Ở đây, tập dữ liệu thường được mô hình hóa là
một số cố định (để loại trừ overfitting) của các phân phối Gauss, được khởi tạo ngẫu nhiên và
các tham số của nó được tối ưu hóa qua các bước lặp để phù hợp hơn với tập dữ liệu. Điều này sẽ
hội tụ về một tối ưu hóa cục bộ, vì vậy nhiều lần chạy khác nhau sẽ cho các kết quả khác nhau.
13
Hình 6: Phương pháp phân cụm EM-clustering
Phân cụm theo phân bố cung cấp một phương pháp phân cụm nhanh và tự nhiên cho các cơ sở
dữ liệu lớn. Nó tự động quyết định được số lượng cụm cần phải tạo ra. Tuy nhiên, sử dụng thuật
toán này sẽ đẩy thêm gánh nặng cho người sử dụng: phải chọn một mô hình dữ liệu phù hợp để
tối ưu.
14
4. Kết luận
Trong khuôn khổ của bài tập lớn, nhóm đã tìm hiểu về cơ sở dữ liệu không gian, các kỹ thuật
trong khai phá dữ liệu không gian và đã đi sâu vào tìm hiểu các phương pháp phân cụm ứng
dụng trong khai phá dữ liệu không gian.
Có rất nhiều thuật toán khác nhau để phân cụm dữ liệu không gian, tuy nhiên do thời gian có hạn