ĐẠ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 Chun ngành: Cơng Nghệ Thông tin Mã số: 010110 LUẬN VÁN THẠC s ỉ Ịf h 'IA HÁ NÓI t s u ; Ì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 Mục lục L)ị giới thiệu Chương (ỉỉói thiệu vể khám phá tri thức co sớ liệu không gian / / Giới thiệu 1.1.1 G iới thiệu c h u n g 1.1.2 N hữ ng phư ơng pháp khai thác dĩr liệu không g ia n 1.1.3 Khái n iệm c khám phá liệu không g i a n .9 1.1 Cấu trúc liệ u , c c phép toán truy vấn k h ôn e g ia n i 12 Những phương pháp khám phá tri thức sở liệu không giun ¡3 1.2 Khám phá tri thức dựa tổn g quát h o 14 1.2 Phương pháp phái luật kết họp không g ia n 16 1.2.3 Phương pháp ch ia lớp (clusterìng) .17 1.2.4 Khám phá (ri thức c sớ liệu ảnh c sở dĩr liệu r a s te r .17 13 Cấu trúc (lữ liệu dùng sở liệu không ỊỊÌan 19 Cấu trúc d ữ liệu c h o phân h oạch không gian v ec to r 19 1.3 Cấu trúc liệu c h o k hôn g gian m e t r ic 23 1.3 N hữ ng cấu trúc d ữ liệu k hác khai thác liệu k h ô n g g ia n 26 / Cúc hướnsị phát triển khám phá tri thức (lữ liệu không gian 27 Cttơng Chia lớp sớ liệu không gian .30 Giới thiệu chung 30 22 Các u cầu vê thuật tốn chia ìớp sở liệu kliông gian .32 23 Các hướng tiếp cận toán chia lớp sờ liệu không gian 33 Phương pháp c h ia iớp phân h o ch .33 Phương pháp c h ia lớp c ó cấu trú c 34 3 Phương pháp c h ia lớp dựa v o vị trí đ ịa phư ng 2.3.4 Đ n h g iá tổ n g q u t 37 2.4 Một sơ thuật tốn chia lớp thơng (lụng 39 C L A R A N S D B S C A N .4 2 D B C L A S D 4 4 S T I N G B IR C H W A V E C lu s te r D E N C L U E 2 C L I Q U E .5 2.4.9 C U R E .5 2.5 Tịng kết thuật tốn chia lóp 61 C huong T h u ậ t t o n c h i a ló p đ a t a n g v ứ n g d ụ n g 63 3.1 Thuật toán chia lóp da tầng 63 3.1.1 G iớ i thiệu v ề thuật toán c h ia lớp đa tầ n g .6 3 1.2 Khái niệm c sờ liệu đa tẩng phương pháp ch ia lớp đa tầng 1.3 Thuật toán ch ia lớp đa tầng M D B S C A N 66 3.2 Bài toán chia IỚỊ) đồ Việt N am 72 3.2.1 G iới ih iệti 72 2.2 Phát biểu t o n 73 3.2.3 N hững kĩ thuật xử lý liệ u 75 3.2.4 ứ n g dụng c ù a M D B S C A N 80 3.2.5 Kết ứng dụ n g M D B S C A N 81 ĩ.ĩ Kết luận 84 T i liệ u T h a m k h ả o 86 L Ờ I G IỚ I T H IỆ U Cách mạng khoa học kỹ thuật giúp COI1 người thu thập lưu trữ lượng cữ liệu khổng lổ Đặc biệt với kích tlurớc sờ liệu khơng gian sở liệu ảnh vệ tinh, ảnh y học, thiên tai, bệnh viện tăng nhanh Trong rhững sở liệu tìm ẩn nhiều tri thức có ích mà người chưa biết Do đó, có nhu cầu tìm kiếm tri thức núi liệu Nhu cầu rgày cấp thiết dẫn tới hình thành lĩnh vực — lĩnh vực Uiám phá liệu sở liệu không gian (data milling in spatial databases) hay khám phá tri thức sở liệu khơng gian (Knowledge Discovery in bìatiưì DatabaseS-KDSD) Glia lớp sở liệu không gian phương pháp quan t ong trình tìm kiếm tri thức Chia lớp phương pháp học từ quan sát (learning t'ơn obversation) hay gọi học không (háy (unsupervisecl learning or aromatic classfication) tronc trí tuệ nhân lạo Chia lớp đặc biệt hiệu ta Uvìng biết thơng tin lớp, ta quan tâm tới thuộc tính 1Vị inà ta chưa biết biết thơng tin Hièn có nhiều thuật toán chia lớp đưa Những thuật toán thường ciực chia vào loại thuật toán chia lớp chia lớp phân hoạch, chia lớp có cấu trúc 'à chia lớp dựa vị trí địa phương kết hợp loại chia lớp Ngoài ra, số kĩ thuật chia lưới, thống kè sử dụng dể nàng cao chít lượng thuật toán chia lớp Những thuật toán chia lóp áp dụng cho sờ Lệ khơng gian phải đáp ứng yêu cầu thời gian chạy, nhớ yêu cầu, Hrh dạng lớp đỏi tượng Ỉ/Iíc dù có nhiều thuật tốn chia lớp đáp ứng yêu cầu thời gian, yêu cầu nhớ, yêu cầu vể hình dạng lớp hầu hết thuật tốn khơng áp dụig lên sở liệu không gian gồm nhiều loại lớp đối tượng liệu Điều là/ uiàt phát từ thực tế lớp đưa áp dụng thuật toán chia lớp lên 5Ởdĩ liệu khơng gian phải thỗ mãn số điều kiện thuật toán Điều Trang !91 khiến cho thuật lốn chia lớp có tìm nhũng lớp đối tượng liệu mà lớp đối tượng có số tính chất chung Đé khắc phục điểm yếu thuật tốn chia lớp tại, tơi đưa khái niệm thuật toán chia lớp đa tầng Dựa khái niệm này, xây ding lên thuât toán chia lớp đáp ứng cho sở liệu gồm nhiều loại lớ[ đối tượng với tính chất khác Trong phạm vi luận văn cao học này, tơi trình bày tìm kiếm tri thức sở liệu khơng gian, toán chia lớp sở liệu khơng gian thuật tốn chia lớp đa tầng ứng dụng Toàn nội dung luận văn gồm: Chương Giới thiệu chung khám phá tri thức liệu khơng gian Clương trình bày phần là: Giới thiệu chung khám phá tri thức, plương pháp khám phá tri thức sở liệu không gian, cấu trúc liệu sử dụng hướng phát triển khám phá tri thức sở liệu khòng gian Chương 2: Giới thiệu chia lóp sở liệu khơng gian Chương trình bày phần trình bày tốn chia lớp, hướng giải toán (phân hoạch, chia lớp có cấu trúc chia lớp dựa vào mật độ địa phíơng), thuật tốn sử dụng đánh giá tổng quan thuật tốn Chương Thuật toán chia lớp đa tầng ứng dụng Chương trình bày thuật tốn chia lớp đa tầng ứng dụng thuật toán chia lớf đa tầng Trong chương vào hai phần : 1) Thuật tốn chia lớ[ đa tầng 2) ứig dụng cụ thể thuật toán chia lớp đa tầng lên toán chia lớp đồ Việt Nam dựa mức độ chăm sóc y tế vùng Cuối cùng, xin chân ihành cảm Ư I1 th ầy cô khoa Công nghệ- Đại học Quốc gic, Hà Nội tạo điều kiện giúp đỡ tỏi q trình làm khố luận Cuối cùng, em xin cảm ơn hướng dẫn tận tình tiến sĩ Lương Chi Mai-Viện Cóng ngiệ Thơng tin giáo sư Hồ Tú Bảo-Viện Công nghệ tiên tiến Nhật Bản- JAIST, T r a n g / 91 En xin chân thành chị Huỳnh Thanh Bình -Đại học bách khoa Hà Nội giúp đỡ cùig làm việc toán chia lớp đổ Việt Nam dựa mức độ chăm sóc sứ( khoẻ Xii cám ơn giúp đỡ bạn lớp 7KT - Khoa Cơng Nghệ suốt q trình họ: tập làm khoá luận Hà Nội, ngày 20 tháng 08 năm 2002 Học viên Lê Sĩ Quang Trang 6/91 CHƯƠNG GIỚI THIỆU VỂ KHÁM PHÁ TRI THỨC TRONG c SỞ D ữ LIỆU KHÒNG GIAN l.L G iớ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ứ tạo bước nhảy vọt tất ;ác lĩnh vực Một nhũng thành công cách mạng lần bùng rổ thơng tin phát triển đến chóng mặt cư sở liệu phạm vi toàn cầu Cìng với q trình đó, tiến kĩ thuật thu thập liệu mã vạch Ụưcode reading), cảm biến từ xa, ảnh vệ tinh giúp người thu thập mờ lượng lớn liệu tạo nên sở liệu khổng lổ Đứng trước “núi” lệt thu thập được, việc khám phá tri thức thông tin trở nên khó khăn Nhu cầu thác tri thức sở liệu ngày lớn dãn tới hình thành I'll ì vực —lĩnh vực khám phá liệu {data mining) hay khám phá tri thức CJ ;ở liệu {Knowledge Discovery in databases-KDD) Khám phá tri thức Sĩ iữ liệu có thè coi q trình tìm tri thức cán có ích cán thiết, tiểm ấn cua biết trước sở liệu lớn {discovery o f interesting, implicit, and ptviously unknown knowledge from large databases) [WGÇ92, CPG93Ị Tuy n ¿ời khám phá tri thức lĩnh vực riêng rẽ hồn tồn độc Up mà có kết hợp nhiều lĩnh vực khác bao gồm học máy (machine learning), liỉ ;ơ sở liệu (database systems), hiển thị liệu (data visualization), thống kê (.'tctistics) 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 sở liệu quan hệ c 1;ờ liệu giao dịch (relational and transaction databases) ÍRR94 JYKGWQ95I ming khám phá tri thức CÒI1 vấn để mờ áp dụne vào sờ liệi ứng dụng sờ liệu không gian (spatial databases), sờ liệu thời Clươriĩị I Giới thiệu vê Khám phá tri thức sở liệu không gian Trang 7/91 gai ( te m p o l d a tư b a se s), sờ liệu hướng đối tượng (O b je ct-O rie n te d d/t/bases), sở liệu đa phương tiện (m u ltim é d ia d a ta bases) Eểtìm hiểu sờ liệu khơng gian, trước hết phải có khái niệm liệu knng gian Dữ liệu không gian liệu mà đối tượng liệu mang tkinc tính khơng gian Như vậy, sở liệu không gian tập đối tượng khơng gai, mỏi đối tượng biểu diễn kiểu liệu không gian nn mối quan hệ đối tượng Dữ liệu không gian thường liệu hm dạng (topological) thông tin khoảng cách (distance) Cơ;ờ liệu khơng gian có đặc thù riêng thường tổ chức theo cấu trúc đánh ciisố không gian (spatial index structures) truy cập phương pháp Í1U' cập khơng gian [PK| Sự đặc biệt thuộc tính liệu khơng gian đưa đínnhững thách thức hội cho việc tìm kiếm tri thức liệu Người ta dĩ; định nghĩa tìm kiếm tri thức sờ liệu không gian: Khan phú (lữ liệu không giun, hay cịn 1ịỌ Ì klúun phú tri thức sở liệu kiịìg gian coi nlìi/ việc trích lọc thơng tin tiềm ẩn, quan lù ¡hơng lỊÌan mẫu met khơng lưu trữ sỏ (lữ liệu Nhing phương pháp khai thác liệu khơng gian dùng để tìm kiếm tri thí! mà người sử dụng quan tâm sở liệu không gian tạo nẻn nũng hệ tri Ihức không gian Hệ sờ tri thức giúp người sử dụng hiểu liìi khống gian mà họ có phát mối quan lìệ liệu khống gian liịtphi khơng gian (nơn-spati data) Những phương pháp sử dụng niitu hệ thông hệ thống thông tin địa lý (GỈS-Geographic Information S'sem.s), hệ thống cảm nhận từ xa, hệ thống khám phá sở liệu ánh, hệ thống kián pha sở liệu ảnh y tế, hệ thống điều khiên robot rình vực khác co dung sở liệu khơng gian T i hức nhận q trình khám phá tri thức sở liệu không gian co tiê nhiều dạng khác Ví dụ dạng luật liên quan tới thuộc tính liệu, chrụ cấu trúc mô tả lớp (clnsters) liên quan đến đối tượng Những Chtơnạ ì Giới thiệu Khám phá tri thức sở liệu không gian Trang (*?/91 tr thức sử dụng ứng dụng cụ thể dược tìm piương pháp khác 1.2 Những phương pháp khai thác liệu không gian c» nhiều phương pháp khai thác 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, phương pháp đtu có điểm mạnh điểm yếu chi' thích ứng với ứng dụng cụ thể 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 hirớns; chủ đạo tnng phương pháp phàn tích liệu không gian Các nhà khoa học tiến hành njhiên cứu phương pháp tương đối kỹ đưa nhiều thuật toán nlững giải pháp tối ưu hoá cho khám phá tri thức sở liệu không gian Tiy vậy, phương pháp thống kê số hạn chế sau: Phương pháp thống kê chì thực tốt liệu số, đưa kết hoàn toàn độc lập với phân bố khổng gian điểm liệu Yêu cầu thứ hai phương pháp thống kế khiến cho phương pháp không áp dụng lên sở liệu khơng gian lớn thực tế điểm liệu khơng gian có quan hệ ánh hưởng lẫn theo vị trí khơng gian chúng Phương pháp thống kê khơng thê mơ hình hố luật phi tuyến không giải 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 sờ liệu không đủ khơng liên lục Độ phức tạp tính tốn phương pháp thống kê lớn Do đó, phương pháp thống kê không áp dụng lên sở liệu khơng gian lớn 2.Píiương pháp Kriging phương pháp hồi quy Đ: khắc phục điểm yếu phương pháp thống kê, người ta đưa phương pláp Kriging phuơng pháp hổi quy Tuy nhiên, hai phương pháp lại làm Cnưinị I Giới thiện Khám phá tri thức sỏ liệu khôn ^ gian Trang 9/91 trnh khám phá tri thức trờ nên phức tạp chúng chi thực bời nhũng chuyển gia lĩnh vực thống kê lĩnh vực dược khám phá Nói cich khác, khơng phải kĩ thuật phương pháp mà người sử dụng irong muốn để đánh giá liệu không gian cách hiệu Những phương pháp Những plurơng pháp truyền thống tị khơng hiệu áp dụng đê tìm kem tri thức sờ liệu có quy mơ lớn Để khắc phục hạn chế này, nlũng năm gần đây, nhà nghiên cứu đưa nhiều phương pháp Háu hết C1C phương pháp xuất phái từ phương pháp cũ học máy, sở litu thống kê [JYKGWQ95I lại dựa sở liệu quan hệ (1 'liitionưl databases) cư sở liệu giao dịch (transaction databases) Những nịhiên cứu nhu khám phá tri thức sờ liệu quan hệ lớn 1JYN93 MJP94] đưa tảng cho khám phá liệu không gian Những kĩ thuật Ikc máy học từ ví dụ mẫu (learning from examples) lổng quan hố đặc biìt hố (generalization and specialization) sử đụng rộng rãi khám phí liệu khơng gian 1.1.3 Khái niệm khám phá liệu không gian Tiong khám phá tri thức sờ liệu không gian thường hay gập nlững khái niệm sau: - Luật (rules): Có nhiều kiểu luật phát từ sờ liệu nói dung Ví dụ luật đặc chưng (characteristic rule), luật biệt số (discriminant nies), luật kết hợp (association rules), luật lệch hướng phát triển (dniaíion and evolution rules) o Luật dật trưng luật mô tả đặc trưng chung liệu khơng gian Ví dụ luật biểu diễn giá nhà miền thành phố luật đặc trưng Cnưiiií I Giới thiệu Khám phá tri thức nong sở liệu không gian ... lớp đa tầng ứng dụng thuật toán chia lớf đa tầng Trong chương vào hai phần : 1) Thuật toán chia lớ[ đa tầng 2) ứig dụng cụ thể thuật toán chia lớp đa tầng lên toán chia lớp đồ Việt Nam dựa mức... kiếm tri thức sở liệu không gian, tốn chia lớp sở liệu khơng gian thuật toán chia lớp đa tầng ứng dụng Toàn nội dung luận văn gồm: Chương Giới thiệu chung khám phá tri thức liệu khơng gian Clương... (lữ liệu không gian 27 Cttơng Chia lớp sớ liệu không gian .30 Giới thiệu chung 30 22 Các u cầu vê thuật tốn chia ìớp sở liệu kliông gian .32 23 Các hướng tiếp cận toán chia lớp