ĐẠI HỌC QUỐC GIA HÀ NỘI
KHOA CỒNG NGHỆ
LÊ Sỉ QUANG
THUẬT TOÁN CHIA LỚP TRONG c ơ SỞ
Dữ LIỆU KHÔNG GIAN ĐA TANG
Chuyên ngành: Công Nghệ Thông tin
Mã số: 010110
LUẬN VÁN THẠC s ỉ
Ị f h 'IA HÁ NÓI 1
tsu;. . ÌHTIIUm iị
Ị
___
N' I U>Ị
Người hướng dẫn:
TS: Lương Chi Mai
Hà Nội năm 2002
MỤC LỤC
L)ị giới thiệu 3
Chương 1. (ỉỉói thiệu vể khám phá tri thức trong co sớ dữ liệu không gian
.
6
/ /. Giới thiệu
6
1.1.1. Giới thiệu c h un g 6
1.1.2. Những phương pháp khai thác của dĩr liệu không gia n 8
1.1.3. Khái niệm cơ bản trong khám phá dữ liệu không g ia n 9
1.1.4 . Cấu trúc dữ liệu, các phép toán và truy vấn k hône g ia n
1 i
12. Những phương pháp khám phá tri thức trong cơ sở dữ liệu không giun ¡3
.4 8
.5 0
.5 2
.5 5
.5 7
61
63
63
.6 3
.6 4
66
72
72
73
75
8 0
81
84
86
2.4. Một sô thuật toán chia lớp thông (lụng
2.4.1. C L A R A N S
2.4.2. D B S C A N
2.4.3. D B C LA SD
2.4.4. S T IN G
2.4.5. BIRCH
2.4.6. W A V E C lu ster
2.4.7. D E N C L U E
2.4.8. C L IQ U E
2.4.9. C U R E
2.5. Tòng kết các thuật toán chia lóp
1 Vị inà ta chưa biết hoặc biết rất ít về những thông tin đó.
Hièn tại có nhiều thuật toán chia lớp đã được đưa ra. Những thuật toán này thường
ciực chia vào 3 loại thuật toán chia lớp là chia lớp phân hoạch, chia lớp có cấu trúc
'à chia lớp dựa trên vị trí địa phương hoặc là sự kết hợp của các loại chia lớp trên.
Ngoài ra, một số kĩ thuật như chia lưới, thống kè cũng được sử dụng dể nàng cao
chít lượng của thuật toán chia lớp. Những thuật toán chia lóp áp dụng cho cơ sờ dữ
Lệ 1 không gian phải đáp ứng được các yêu cầu về thời gian chạy, bộ nhớ yêu cầu,
Hrh dạng các lớp đỏi tượng
Ỉ/Iíc dù có nhiều thuật toán chia lớp đáp ứng được yêu cầu về thời gian, yêu cầu về
bộ nhớ, yêu cầu vể hình dạng của lớp nhưng hầu hết các thuật toán đều không áp
dụig được lên cơ sở dữ liệu không gian gồm nhiều loại lớp đối tượng dữ liệu. Điều
là/ uiàt phát từ thực tế là các lớp đưa ra khi áp dụng một thuật toán chia lớp lên cơ
5Ởdĩ liệu không gian đều phải thoã mãn một số điều kiện của thuật toán. Điều này
Trang 4!91
đã khiến cho những thuật loán chia lớp hiện có chỉ có thể tìm ra nhũng lớp đối tượng
dữ liệu khi mà các lớp đối t ượng đó có một số tính chất chung.
Đé khắc phục được điểm yếu của các thuật toán chia lớp hiện tại, tôi đưa ra một khái
niệm về thuật toán chia lớp đa tầng. Dựa trên khái niệm này, chúng ta có thể xây
ding lên những thuât toán chia lớp đáp ứng được cho cơ sở dữ liệu gồm nhiều loại
lớ[ đối tượng với tính chất khác nhau.
Trong phạm vi luận văn cao học này, tôi sẽ đi trình bày về tìm kiếm tri thức trong cơ
sở dữ liệu không gian, bài toán chia lớp trong cơ sở dữ liệu không gian và thuật toán
chia lớp đa tầng và ứng dụng. Toàn bộ nội dung của luận văn gồm:
Chương 1. Giới thiệu chung về khám phá tri thức trong dữ liệu không gian.
Clương này trình bày 4 phần cơ bản là: Giới thiệu chung về khám phá tri thức, các
plương pháp khám phá tri thức trong cơ sở dữ liệu không gian, những cấu trúc dữ
liệu sử dụng và hướng phát triển kế tiếp của khám phá tri thức trong cơ sở dữ liệu
khòng gian.
Chương 2: Giới thiệu về chia lóp trong cơ sở dữ liệu không gian
Chương này trình bày 3 phần cơ bản trình bày về bài toán chia lớp, những hướng giải
CHƯƠNG 1. GIỚI THIỆU VỂ KHÁM PHÁ TRI THỨC TRONG c ơ
SỞ Dữ LIỆU KHÒNG GIAN.
l.L Giới thiệu
1.1.1. Giới thiệu chung
CiDc cách mạng khoa học kỹ thuật lần thứ 3 đã tạo ra những bước nhảy vọt trong tất
cả ;ác lĩnh vực. Một trong nhũng thành công của cuộc cách mạng lần này là sự bùng
rổ thông tin và sự phát triển đến chóng mặt của cư sở dữ liệu trên phạm vi toàn cầu.
Cìng với quá trình đó, những tiến bộ của kĩ thuật thu thập dữ liệu như mã vạch
Ụưcode reading), bộ cảm biến từ xa, ảnh vệ tinh đã giúp con người thu thập được
mờ lượng lớn dữ liệu và tạo nên những cơ sở dữ liệu khổng lổ. Đứng trước “núi” dữ
lệt thu thập được, việc khám phá tri thức và thông tin trở nên rất khó khăn. Nhu cầu
khá thác tri thức trong cơ sở dữ liệu ngày càng lớn đã dãn tới sự hình thành của một
I'l l ì vực mới — lĩnh vực khám phá dữ liệu {data mining) hay khám phá tri thức trong
CJ ;ở dữ liệu {Knowledge Discovery in databases-KDD). Khám phá tri thức trong cơ
Sĩ iữ liệu có thè được coi như quá trình tìm tri thức cán có ích cán thiết, tiểm ấn và
cua được biết trước trong cơ sở dữ liệu lớn {discovery of interesting, implicit, and
ptviously unknown knowledge from large databases) [WGÇ92, CPG93Ị. Tuy mới
n ¿ời nhưng khám phá tri thức không phải là một lĩnh vực riêng rẽ và hoàn toàn độc
Up mà có sự kết hợp của nhiều lĩnh vực khác bao gồm học máy (machine learning),
liỉ ;ơ sở dữ liệu (database systems), hiển thị dữ liệu (data visualization), thống kê
(.'tctistics) và lý thuyết thông tin (information theory).
Mịc dù đã có nhiều nghiên cứu vể khám phá tri thức trong cơ sở dữ liệu quan hệ và
c 1 ;ờ dữ liệu giao dịch (relational and transaction databases) ÍRR94. JYKGWQ95I
ming khám phá tri thức vẫn CÒI1 là một vấn để mờ khi áp dụne vào những cơ sờ dữ
liệi ứng dụng như cơ sờ dữ liệu không gian (spatial databases), cơ sờ dữ liệu thời
Clươriĩị I . Giới thiệu vê Khám phá tri thức trong cơ sở dữ liệu không gian
Trang 7/91
gai (tem p o ra l d a tư ba ses), cơ sờ dữ liệu hướng đối tượng (O bject-O riented
d/t/bases), cơ sở dữ liệu đa phương tiện (m u ltim éd ia data bases)
Eểtìm hiểu cơ sờ dữ liệu không gian, trước hết phải có khái niệm cơ bản về dữ liệu
c» rất nhiều phương pháp khai thác dữ liệu nhu phương pháp phân tích thống kê
kiông gian, phương pháp đường hồi quy, học máy Tuy nhiên, mỗi phương pháp
đtu có điểm mạnh điểm yếu và chi' thích ứng với từng ứng dụng cụ thể.
1 Phương pháp phàn tích thống kê không gian:
Piương pháp phân tích thống kê không gian |KJ961 đã từng là một hirớns; chủ đạo
tnng các phương pháp phàn tích dữ liệu không gian. Các nhà khoa học đã tiến hành
njhiên cứu phương pháp này tương đối kỹ và đưa ra được nhiều thuật toán cũng như
nlững giải pháp tối ưu hoá cho khám phá tri thức trong cơ sở dữ liệu không gian.
Tiy vậy, những phương pháp thống kê vẫn còn một số hạn chế như sau:
Phương pháp thống kê chì được thực hiện tốt trên dữ liệu số, và chỉ có thể đưa
ra được kết quả hoàn toàn độc lập với phân bố khổng gian của các điểm dữ
liệu. Yêu cầu thứ hai của phương pháp thống kế đã khiến cho phương pháp
này không áp dụng lên được cơ sở dữ liệu không gian lớn trong thực tế vì
những điểm dữ liệu không gian có quan hệ và ánh hưởng lẫn nhau theo vị trí
không gian của chúng.
Phương pháp thống kê không thê mô hình hoá được những luật phi tuyến và
không giải quyết được những thuộc tính dạng phi số.
Phương pháp thống kê còn không thể áp dụng lên cơ sờ dữ liệu không đủ
hoặc không liên lục.
Độ phức tạp tính toán của phương pháp thống kê là lớn. Do đó, phương pháp
thống kê không áp dụng được lên những cơ sở dữ liệu không gian lớn.
2.Píiương pháp Kriging và phương pháp hồi quy
Đ: khắc phục những điểm yếu của phương pháp thống kê, người ta đã đưa ra phương
pláp Kriging và phuơng pháp hổi quy. Tuy nhiên, hai phương pháp này lại làm quá
Cnưinị I . Giới thiện về Khám phá tri thức trong cơ sỏ dữ liệu khôn ^ gian
Trang 9/91
trnh khám phá tri thức trờ nên phức tạp vì chúng chi có thể được thực hiện bời
nhũng chuyển gia trong cả lĩnh vực thống kê và lĩnh vực đang dược khám phá. Nói
cich khác, đây không phải là những kĩ thuật hoặc phương pháp mà người sử dụng
irong muốn để đánh giá dữ liệu không gian một cách hiệu quả.
thuôc giữa giá nhà và vị trí địa lý của nhà so với bãi biển, trung tâm thành
phô' là luật kếl hợp không gian.
o Luật vể sự lệch lurớng và phát triển là luật dự đoán sự phát triển của và
hướng phát triển trong cơ sở dữ liệu. Ví dụ, luật dự đoán sự táng dàn sô trong
một vùng dựa trên những trục đường, trung tàm thành phố của vùng dó có
thê được xem như luật về sự lệch hướng và phát triển.
- Bán đổ chuyên dê (thematic maps): Bản đồ chuyên đé là bản đổ thê hiện những
phân bô không gian cùa một hoặc một vài thuộc tính. Mục đích của bản dổ chuyên
đề thể là thê hiện mối quan hệ giữa các đối tượng hoặc sự thê hiện một vài thuộc tính
củi các đối tirợng trên bản đổ đó. Bản đồ chuyên để có thể được sử dụng đc phát
hitn các luật. Ví dụ, để đánh giá kiểu thời tiết của một vùng chúng ta có thể theo dõi
bin đồ chuyên (lổ nhiệt độ dể đưa ra được một sô' luật liên quan giữa vị trí địa lý và
nhệt độ.
C( hai cách để thể hiện bản đổ chuyên đề là kiểu raster và kiểu vector.
- Trong ảnh raster, bản đồ đặc trưng là một tập các điểm được liên kết với các
thuộc tính của từng điểm. Ví dụ trong một bản đồ, độ cao của các điểm so với
mặt nước biển có thể được biểu diễn bời mầu sắc.
- Trong biểu diễn vector, mỏi đối tượng không gian được thể hiện bằng cấu
trúc hình học và giá trị các tình chất chủ đề cần biểu diễn. Để biểu diễn cấu
trúc hình học của một đối tượng dữ liệu, người ta thường biểu diễn bằng
đường biên của đối tượng đó. Ví dụ: một vùng điều tra dân số có thể được thê
hiện bởi biên của vùng và dân số của vùng đó.
ChưniỊ I . Giới tliiệu về Khám phá tri thức trong cơ sở dữ liệu không gian
Trang ///91
2ơ sở dữ liệu ảnh {Image databases): Có rất nhiều cơ sờ dữ liệu không gian mà
dữ iệu thòng thường chỉ là ảnh. Cơ sở dữ liệu ảnh đirợc sử dụng trong cảm biến từ
xa, iữ liệu y học Những cơ sở dữ liệu này được lưu trữ dưới nhiều loại hình thức
khá: nhau như ma trận lưới, ma trận mật độ
1.14. Cấu trúc dữ liệu, các phép toán và truy vấn không gian:
I. Cấu trúc dữ liệu
gitn tính toán và đơn giản hoá quá trình xử lý đối tượng không gian, thông thường ta
x;p xỉ đối tượng về một dạng đối tượnc; đơn giản hơn. Ví dụ như xấp xỉ một đa giác
lổ bằng một hình tròn, xấp xi một đa giác bất kì bằng một đa giác có các đường
bin song song với các trục,
- Phép kết hợp không gian (spatiaì join) là một trong những phép toán không gian
vá độ phức tạp lớn nhất. Thông thường các truy vấn trên cơ sở dữ liệu không gian
thrc hiện dựa trên phép kết hợp không gian. Do đó, các truy vấn không gian chi có
thi có hiệu quả nếu phép kết hợp không gian được thực hiện hiệu quả. Brinkhoff đã
duì ra một quá trình nhiều bước để tăng sự hiệu quả của phép toán kết hợp dựa trên
CcV R*-Tree và nhiều phép xấp xí đối tượng không gian.
- Một phép toán quan thường được dùng trong hệ thống thông tin địa lý G1S là phép
tan phú bản đồ.
c. Truy vấn không gian.
Tuy vấn không gian chính là quá trình tìm kiếm các đối lượng dữ liệu không gian
th>ả mãn nhu cầu của người dùng. Khác với phép truy vàn cơ sờ dữ liệu quan hệ,
tny vấn không gian phức tạp hơn do tính chất phức tạp đặc thù của các đối tượng
klàng gian. Thóng thường các phép truy vấn không gian gắn liền với các phép toán
triy câp cơ sờ dữ liệu khỏng gian, tìm kiếm dôi tượng không gian, ghép các đối
tưnig không gian (phép kết hợp không gian),
Đi truy vấn không gian hiệu quả, Aref và Samet đã đưa ra một cấu trúc cho cơ sở dữ
liei không gian gọi là SAND (spatiưl aml nonspatiaI databưses) và chiến lược tối ưu
Ctươììg /. Giới thiệu vé Khảm phá tri thức trong cơ sà dữ liệu kliôtHỊ lỊÌaiì
Trang 13/91
ch) quá trình truy vân không gian trên câu trúc cơ sờ dữ liệu đó. Cấu trúc này là mở
rộig của cấu trúc cơ sở dữ liệu quan hệ bằng cách thêm vào các cấu trúc cho thuộc
tím không gian và với các phép toán không gian trên những thuộc tính đó.
12. Những phương pháp khám phá tri thức trong cơ sở dữ liệu
không gian.
ĨYmg thời đại bùng nổ thông tin như hiện nay, thông tin không chỉ được biểu hiện
bằig các hình thức thông tlnrờng mà được lưu trữ da dạng hơn với nhiều loại hình cơ
lunhững hệ thông cấp bậc khái niệm, ta đi xây dựng cây khái niệm sao cho những
<h.i niệm tổng quát hơn ờ lớp trên và phù hợp với các khái niệm ở lớp dưới.
Tnng khám phá tri thức trong cơ sở dữ liệu không gian dựa trên tổng quát hoá dựa
và« hệ thống cấp bậc khái niệm tlurờng sử dụng phương pháp đệ quy hướng thuộc
ÍI1I đi theo hệ thống cấp bậc tổng quan đế đưa ra được mối quan hộ giữa dữ liệu
dung gian và dữ liệu phi khổng gian ở mức khái niệm cao hơn.
Oệquy hirớng thuộc lính có thể được thực hiện bằng cách: 1) di ngược lèn hệ thống
•ấ| bậc khái niệm cho đến khi những giá trị thuộc tính trong đường đi {tuple) đó đến
n<t giá trị tổng quát, 2) loại bỏ những thuộc tính mà nếu giữ lại những thuộc tính đó
hìkhông thể đưa đến được các tổng quát hơn. Quá trình trên dược thực hiện quy nạp
111 đến khi giá trị của mọi thuộc tính được tổng quát hoá ở một mức độ yêu cầu.
Mic độ này thông thường thoả được khi mà số giá trị khác cho những thuộc tính
lư<c tổng quát hoá trong bảng dữ liệu nhò hơn một ngưỡng tống quát hoá cho thuộc
ím đó.
5híơng pháp tổng quái hoá thường được áp dụng cùng với phương pháp học từ ví dụ
nải (learning from example) IWJB931. Tuy nhiên, phương pháp học từ ví dụ mẫu cổ
liéi khó có thể áp dụng trực tiếp cho cơ sở dữ liệu không gian vì: 1) thuật toán yêu
;ầi sô' ví dụ mẫu lớn (thường là yêu cầu đến một hàm số mũ các ví dụ mẫu), 2)
Chrơiig ỉ . Giới thiệu về Khám phá tri thức trong cơ sở (lữ liệu khôniỊ gian
Trang 15/91
khỏg đưa ra được kết quả chính xác khi dữ liệu có nhiễu hoặc dữ liệu không chắc
chá. Để khác phục hai điểu trên Han et al. đã đưa ra phươtig pháp quy nạp hướng
thuc tính (Attribitte-oriented induction algorithms) đê khám phá tri thức trong cơ sờ
dữ ệu quan hệ lớn. Kế tiếp, Lu et al |WJB931 mở rộng kĩ thuật trên cho cơ sờ dữ
liệiKhông gian.
1. Ting quát hoá dựa trên dữ liệu không gian.
Tốn quát hoá dựa trên dữ liệu không gian bắt đầu bằng việc thu thập toàn bộ dữ liệu
mà gười sử đụng quan tâm. Từ một hệ thống cấp bậc không gian, tổng quát hoá có
thể ược thực hiện bằng cách ghép các miền đã thu thập được dựa vào mô tả thuộc
tínlcúa các miền và mô tả trong hệ thống cấp bậc khái niệm không gian. Quá trình
lốivới một hoặc nhiều thuộc tính không gian hoặc phi không gian khác.
Chú niệm về luật kết hợp lần đầu tiên được đưa ra bởi Agrawal et al ỊRTA93Ị trong
hì nhóm của Agrawal tiên hành nghiên cứu khám phá tri thức trong cơ sờ dữ liêu
;ia> dịch lớn. Sau đó, Koperski và Han ỊK.I95I đã mở lông khái niệm này cho cơ sớ
lữ iệu không gian. Khái niệm về luật kết hợp được phát biểu như sau: một luật có
lạig X-> Y(c%) với X và Y là tập các thuộc tính không gian hoặc phi không gian
ớiđộ tin cậy là c% được coi là luật kết hợp không gian nếu có ít nhất c% đối tượng
Jioig gian trong trong cơ sờ dữ liệu không gian đang xét thoả mãn: nếu điều kiện X
ỉưc thoà mãn thì điểu kiện Y cũng thoá mãn.
/í lụ luật sau là luật kết hợp không gian: is_a(x, scho ol) - ỳ close (x , park) (80%).
Al t trên thể hiện là: 80% trư ờng học gần với công viên.
'ỉhr vậy, có rất nhiều kiểu thuộc tính không gian có thể tạo thành những luật kết hợp
h<ng gian. Điều này khiến cho trong nhiều trường hợp sổ luật kết hợp tìm được
ưc quá nhu cầu. Đê’ hạn chế số luật kết hợp tìm được, người ta sử dụng khái niệm
iỗ rợ tối thiểu a (minimum support) và độ tin cậy tối thiểu ỗ (minimum confidence).
ỉa tham số sẽ giúp loại bớt các luật tìm thấy và chí để lại những luật thực sự có ích
h< người sử dụng:
7rong I . Giới thiệu vé Khúm phá tri thức trong cơ sở dữ liệu không gian
Trang /7/91
i Fỗ trọ tối thiểu:
Yoig cơ sở dữ liệu lớn, có thể có rất nhiều luật giữa các đối tượng nhưng phần lớn
ủaluật đó chỉ có thể áp dụng vào một số nhỏ các đối tượng hoặc độ tin cậy của luật
i nt thấp. Chính vì thế mà phẩn lớn các luật không có ích với người sử dụng. Ví dụ
giơi sử dụng có thể khóng quan tâm nhiều tới mối quan hệ giữa nhà ờ và trường
bcnếu luật đó chỉ áp dụng cho 5% số nhà ở trong khi người ta muốn ít nhất luật đó
ùn; phải được áp dụng cho trên 50% các ngôi nhà. Do đó, chúng ta có thể lọc bỏ
hũig luật kết họp mà chỉ có thể áp dụng được cho một số nhỏ các đối tượng mà chỉ
,iữ ại những luật có thể áp dụng cho a% đối tượng trong cơ sở dữ liệu.
. ỉộ tin cậy tối thiểu:
ỉếi một luật được đưa ra với mức độ tin cậy (độ tin cậy là tỉ lệ số đối tượng dữ liệu
này dược thực hiện bằng cách so sánh mật độ của điểm trung tâm của một m iền với
mật đô dự đoán của các điểm lân cận. Thành phần thứ hai đưa ra những lính chất có
ích từ dữ liệu bằng những phương pháp thường được sử dụng trong nhận dạng nhơ
tách cạnh chu ẩn hoặc biến đổi Hough. Tuy nhiên những phương pháp đó đểu đưa ra
kết quá không mấy hiệu quả khi áp dụng với cơ sở d ữ liệu thực tế có dữ liệu nhiễu
hoặc dữ liệu không chác chắn. Do rất khó có thể xác định được tính chất hoặc thuộc
tính của các núi lửa một cách chính xác nên ma trận chứa ảnh núi lửa được nén
thành một vector. Giá trị của các thành phần trong vector đó được xem như m ột tính
chất của núi lửa. Nhiệm vụ cuối cùng của hệ thống là phân biệt núi lửa và những đối
tượng khác giống núi lửa. Thành phần cuối cùng dựa vào những ví dụ m ẫu của nhà
chuyên m ôn để đưa được ra lớp phân biệt giữa núi lửa và các đối tượng không phải
núi lửa. Góc chụp của các bức ảnh cũng ảnh hưởng rất lớn đến chất lượng của hệ
thống. Theo thống kế, độ chính xác của những bức ảnh chụp hiện có lên tới 80%.
Những nghiên cứu khác trong lĩnh vực này phải kể đến như POSS-II (the second
palomar obvervatory sky survey) sử dụng cây quyết định dể phân loại
{classification) giải thiên hà, các ngôi sao và các vật thể không gian khác với độ
chính xác khoảng 75%. Khám phá tri thức trong cơ sờ dữ liệu raster của Stolorz et aỉ
ChươtHỊ I . Giới thiệu về Khám phá tri thức trong cơ sà (lữ liệu klìôntị ỊỊÍCIII
Trang 79/91
IP 95 1 và Shek et al IE R E K 961 cũng được áp dụng cho cơ sở dữ liệu địa lý thời gian
llụrc C O N ỌUEST (Content-bưsed Querying in space and Time).
1.3. Cấu trúc dữ liệu dùng trong cơ sở dữ liệu không gian.
Mỗi đối tượng dữ liệu không gian trong cơ sở dĩr liệu không gian được biểu diễn
bằng các thuộc tính không gian và các thuộc tính phi không gian. N hững thuộc tính
không gian biểu diễn vị trí và hình dạng của đối tượng đó trong khổng gian: toạ độ,
hình dạng Những thuộc tính phi không gian biểu diễn những tính chất m à đối
tượng đó có như tên của đối tượng, dân số
Đối tượng dữ liệu không gian dưới dạng hoặc vector hoặc raster. Dạng raster biểu
diễn đối tượng dưới một lưới các điểm trong khi dạng vector biểu diễn các đối tượng
bời cấu trúc cùa chúng. Dữ liệu dùng cho dạng vector đơn giàn chỉ là toạ độ của đôi
ẳ
6
•
7
•
Hình i . Ví dụ về cây tứ phân
Cây tứ phân là m ột cây không càn bằng và thứ tự của các đối tượng dữ liệu sẽ sự cân
bằng của cây.
2. Cây k-d (k-d tree)
k-d tree ID E M 9 81 là phương pháp sử dụng cây nhị phán để phân chia không gian k
chiểu. Tại một bước, k-d-tree sẽ chia không gian thành hai không gian con dựa vào
một trục toạ độ bất kì và phân bố của những dữ liệu.
M ức của một nút chính ỉà độ dài đường đi từ gốc đến nút đó và được đánh số từ 0
k-1. Tại một m ức, m ỗi nút trong không gian được chia phụ thuộc vào số: level mod
k.
Phép chèn và tìm kiếm trên cây k-d tree giống như cây nhị phân. Tuy nhiên, thứ tự
các điểm vào ảnh hưởng rất nhiều đến cấu trúc của cây.
Chương I . Giới thiệu về Khám phá tri thức trong cơ sở dữ liệu không gian
Trang 21 m
4
,
:
2
31
1'
&
A i
5<
ị
,
R*-Tree là m ột cấu trúc khá phức tạp nhưng là một trong những phương pháp hiệu
quả trong cơ sờ dữ liệu không gian.
5. R+-Tree
R+-Tree ỊT N C 8 7Ị là m ột m ở rộng khác của R-tree. K hác với R-Tree, R+-Tree cho
phép chia một đối lượng thành nhiều phần và được lưu trữ tại nhiều nút trên cây, ví
dụ:
A
B
c
3
5
Hình 4. R+Tree
Nếu m ột hình chữ nhật phù chung một m iền với m ột hình khác, ta sẽ phán tích hai
hình chữ nhật đó thành m ột nhóm các hình chữ nhật tách rời nhau. Các hình chữ
nhật đó có thể cùng phủ chung đối tượng. Đ iều này làm cây lớn lên nhung tránh
Chương I . Giới thiệu vé Khám phá tri thức trong cơ sở ilữ /iện không gian
Trang 23/91
được hiện tượng các nút Irong cây có phần phù chung. N hờ đó thời gian tìm kiếm
trên cây giảm di đáng kể.
1.3.2. Cấu trúc dữ liệu cho không gian metric
6. Vp-Tree (vantưge point tree)
Vp-Tree Ị APYY(X), T M 97 1 chia không gian dữ liệu thành hai phần xung quanh một
điểm dữ liệu đã dược chọn. Điểm dữ liệu đã được chọn gọi là vantage points, ví dụ:
Hình 5. Vp-tree
Mỗi một điểm trong của cây được tạo từ bộ 4 số (Pv, M, R, L) với
- p v là vantage points.
- M là khoang giá trị trung bình trong tập khoảng cách của các điểm trong tập
thuộc vào lớp pv đến p v.
- R, L là con của P y Điểm L là con chứa những đối tượng dữ liệu mà khoảng
cách đến p v nhò hơn hoặc bằng M. R là con chứa những điểm mà khoảng
9. M -tree
CliươiiíỊ ì . Giới thiệu về Khám phú tri thức trong cơ sở (lữ liệu không gian
Copyright: Tài liệu đại học ©