DAI hQc QUOc GIA hÀ HỘI TTŒ|ỜITG ĐẠI hỌc cÔIIG IIGhỆ HGUVÈH SƠN PhG|ONG PhAP PhATI cUM DU LIEU KhÔNG GIAN VÀ ỨIG DỤNG TT0IG VIỆc XAc DIIh VI TTi TOI GJU BAT MAY ATM LUẬN VĂN ThẠc SỸ hÀ HỘI -2011 DAI hQc QUOc GIA hÀ HỘI TTŒ|ỜITG ĐẠI hỌc cÔIIG IIGhỆ HGUVÈH SƠN PhG|ONG PhAP PhATI cUM DU LIEU KhÔNG GIAN VÀ ỨIG DỤNG TT0IG VIỆc XAc DIIh VI TTi TOI GJU BAT MAY ATM Iganh: công nghệ thông tin chuyên ngành:hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN ThẠc SỸ IGGIỜI hd|ÓIG DÃII Kh0A hỌc: PGS. TS Đặng Văn Đức hÀ HỘI -2011 3:19)191/008i9E7. TOIG QUATI hE ThOMG TI DIA LY VA KhAI PhA DU LIEU €:195/e16. Tổng quan về hệ thông lin địa lý 3 2.
Một số định nghĩa về hệ thong tim địa lý.----2- 2 2<+2sz+cxe+zxzerxee 3 2. các hành phần của hệ †hông lin địa lý.----2-©-s¿©sz+2xz+cxz+rxecrxeerxee 4 2. biểu diễn đữ liệu địa lý. Phân lích và xử ly đữ liệu không gian.
Ứng dụng của hệ thông tin địa lý. Tống quan về khai phá dữ liệu 21 2. Tiến trình khai phá dữ liệu. các mô hình khai phá dữ liệu.- ¿22 ©¿©2+2EE+2EEt2EECEEECEEErrrkrrrkeee 23 2.
các hojớng liếp cận và kỹ thuật! sử dụng trOng khai phá dữ liệu. các đạng dữ liệu có thê khai phá. các ứng dụng của khai phá dữ liệu. Khai phá dữ liệu không gian 26 2.
các đặc lroIng của khai phá dữ liệu không g1a. Kh0 dữ liệu không gian và các chiều đữ liệu. Một số ứng dụng của khai phá đữ liệu không gian. PhÂ1TI cỤM DỮ LIỆU KhÔIIG GIAIIH.
Khái quát về phân cụm dữ liệu 32 3. Phân cụm phân h0Oạch.--- 2-2 2£++£+2E££EEE£EEE£EEEEEEEeEEEEkrrrkrrrkeee 32 3. Phân cụm phân CẤp.----:-2¿©+++22+++2EE+tEEE+tEEEvEEEEEEExrrrkrrrrkrrrrkre 35 3. Phân cụm dựa lrên mật đỘ.
Phân cụm dựaÌrÊII ÏƠJỚII.- -- + SE *tE#EEEEEeEekEekrekreeeeerkrrkrerere 49 3. Phân cụm dữ liệu không gian 50 3. các đặc troing của dữ liệu không g1aI1. các quan hé/thudc lính không gian của dữ liệu không g1an.
các độ đ0 tojong dong trOng phan cum dit ligu không gian. UIIG DUNG PhAII cUM KhONG GIAITI TTOlG BAI TOATI XAc DITTh VI TTi TOI GU LAP DAT MAY ATM oon. Phân lích bài Hán 62 4. Iguồn dữ liệu đầu và0 và phạm vi sài lÖán.
Phojong pháp kỹ thuật giải quyết sài †Öán. Xây dung chojong trình ứng dụng 64 4. Phân lích thiết kế hệ thống. cài đặi chơiơng lrìnhh.----s-©2s22xc2Ekt2212211211121112111211211211 21121 re.
Thử nghiệm và đánh giá các thuật l0án phân cụm. KET LUATD ooo ecccececsssesssssssesssssssssssssssssssusssssssssssssssssssusssesssesssesssesssessseeesess 75 TÀI LIỆU ThAM KhhẢU.-- 5-5256 kSEE9EE£EEEEEESEEEEEEEEE2E1117111711111E 11111 1X. 76 DANh MỤc hìïñhh VE hình 1: 5 thành lố của GIS.ctkrrrrir 4 hình 2: Mối quan hệ giữa các thành phần của GIS. Ví dụ siểu diễn vị lrí nơiớc bi ô nhiễm .--2- 2 £©£+E£+£x£+xz+rxz+rxee 8 hình 4.
Ví dụ siểu diỄn đơ|Ờng.---2- 22 ©2S+22S++2EEE2EEE2EEEEEEEEEEkrerrkrerrrrerkrrrrex § hình 5. Ví dụ siểu diễn khu vực hành chínhh. --- - -¿- 5 + + + + + E+vE+eseereereeeesee 9 hình 6. biểu diễn vectOr của đối †ojợng địa lý.
biểu diễn thế giới sằng mô hình rasler.-:-©22©2522c+zeccxeerzxrerreee 13 hình 8: Tìm đơiờng đi ngắn nhất giữa 2 địa điểm trên sản đồ hà Hội. 15 Hirth 9: Chémg phti da gid. Tiến trình phủ đa giác .----¿- 2+ 5++22©++22EEt2EEEtSEEErEEExrrrkrerrkrerrrrerrvee 18 hình 11: Tiến trình khám phá tri thức từ cơ sở dữ liệu.-¿---c-cc5s+2 22 hình 12: Kiến trúc điển hình của một hệ khai phá dữ liệu.-------2- 5+: 23 hình 13: Phân cụm p0Iyg0n đề phân lích xu thế giảm giá trung sình nhà ch0 †huê xung quanh mội khu vực ở ['egenseurg [ESK. ¿555 c<cccscsexrersee 29 hình 14: Khái quát hóa mô hình 3D của vật †hê.---2¿©2¿©2z+ccxceczxrerreee 29 hình 15: Phân cụm đữ liệu ảnh viễn thám thu đơjợc the0 sự 16 hop tin hiéu cua 5 kênh màu của 5 ảnh viễn thám vòng ven siên calif0rnia [ESKS01].
30 hình 16: Phân lích thủy hệ lại vòng Ilesraska, h0a Kỳ [J0S 1].- 30 hình 17: các địa phojơng có lỷ lệ ngojời nghỉ hdøqu ca0 [ESKS0I]. -- 31 hình 18: Minh họa thuật l0án k-mea1.-- ¿c2 3323321 E*E**EE*EEEeExekeereeeeereee 34 hình 19: Phân cụm phân CẤp.----¿- + 22+©++2E+++2EE++2EEESEEEvEEEEerrxrerrxrerrrrerrree 35 hình 20: Kề mật độ trực liếp, q là đối toJợng lõi (c0re), p là đối toJợng siên. 37 hình 21: Kể mật độ,.----- -- ® k+x+Ex£EkEEEE2E1EE1E711211111112111111E11111E 11111. 37 hình 22: Kết nối †he0 mật độ,.--- - 2 2° +kSEE+EESEEEEEE2EEEEE211221117151111.
38 hình 23: Minh họa đồ lhị kh0ảng cách 4-dis† đã đơjợc sắp xếp của một cSDL. 4I hình 24: Đồ thi k-dis† và mội phoJơng pháp oiớc lojợng tham số Eps.- 42 hình 25: Đồ thị 4-disi của dữ liệu sản đồ “hệ thống siêu †hị”.------5-+- 42 hình 26: Đồ thị 4-dist cua dit liu sản đồ “IIgân hàng”.-- 2 5z2csz2zxz2zsz+e 43 hình 27: các cụm phái hiện dojo sởi CLATATIS (a) và DbScAII (š). 43 hình 28: các cụm đơ3ợc phái hiện bởi DBIS(a), DBScAlIlœ), K-Means(c), 90. 49 hình 29: Phân cụm dựa †he0 lơJới VÙHg .---- - 6 + SE SE, 49 hình 30: Quan hệ về hoJớng của các đối loJợng không gian [ESKS01].
52 hình 31: Mô hình 9-inlerseciOn [EGFT A94].--22:-©55c22szc2cxevccxrerrxrerrrrerrree 53 hình 32: Quan hệ về lô pô của các đối lojợng không gian [ESKS0I].- 53 hình 33: Kh0ảng cận điỂm. 55 hình 34: Kh0ảng cách cận-viỄn.-:- 22 22¿©22t2CEE2EEEtSEEEEEEErEEkrerrrrerrrrerrree 56 hình 35: S0 sánh kh0ảng cách hausd0rff với kh0ảng cách ‡âm.- 56 hình 36: Mối quan hệ lô pô giữa hai đa giác dựa trên đối loJợng tham chiếu luyến "0 .ÔỎ 60 hình 37: hình ảnh chồng phủ (vòng màu vàng) của các cụm “Ilgân hàng” (màu xanh) và “Siêu †hj” (mầu đỏ).--¿-©22+©22++22S++22EE2EEESEEECEEEErEEkrerrkrerrrrerrrrerrvee 68 hình 3§: Kết quả phân cụm DBTS đối với dữ liệu thử nghiệm lự †a0.- 69 hình 39: Kết quả phân cụm DBI'S đối với dữ liệu thực “IIút mạng đojờng bộ” của Tỉnh Thừa Thiên- huUẾ. 2-2 + k£SEE+EE£EEEEEESEEEEEEEEEEEEEEEEEEEEEE117111111. 69 hình 40: Kết quả phân cụm và chồng phủ các cụm điểm liện ích “Siêu thị” và “Khách sạn” tr0ng nội thành hà Hội.
Vùng màu vàng có thể cũi là vị trí lỗi ơiu ch0 việc lắp đặ! các máy A'TTM.11 70 hình 41: Khả năng phát hiện nhiễu và cụm có hình dạng sấi kỳ của K-means (trái) c8 37. 71 hình 42: Khả năng phân cụm the0 thu6c tinh cua DbScATI (trai) và DBTS (phải) 72 hình 43: Đồ thị s0 thời gian thực hiện phân cụm của các thuật l0án K-measn, DbScAII và DBTS với còng mội lập đữ liệu đầu và0.---¿---¿©cce+cxccscee 72 hình 44: Đồ thị thời gian thực hiện phân cụm của các thuật l0án K-measn, DbScAII và DBIS lrên các tập dữ liệu khác 1rhau.-- 6 + SE *EEvE+vEeeEetreeeeerrsvreeree 73 KY hIEU VIET TAT cSDL cơ sở đữ liệu GIS hệ thông tin dia ly KDD Khám phá lri thức lừ cơ sở dữ liệu KPDL Khai phá dữ liệu 0LAP Xử lý phân tích dữ liệu trực tuyên SDbS hệ cơ sở dữ liệu không gian SDW K0 dữ liệu không gian 1 chữ|OïIG 1. MỞ ĐÀU Khai phá dữ liệu không gian hay còn gọi là khai phá tri thức lừ dữ liệu không gian là một lĩnh vực có nhu cầu rất ca0. bởi lẽ dữ liệu đầu và0 ở đây sa0 gồm một khối lojợng dữ liệu không gian khổng lồ đã đojợc thu thập lừ nhiều ứng dụng khác nhau, từ thiết sị viễn thám đến hệ thống thông lin địa lý, lừ sản đồ số, từ các hệ thống quản lý và đánh giá môi trojờng,.
Việc phân lích và khai thác lojong thong tin không lồ này ngày càng lạ0 ra các thách thức và khó khăn, đòi hỏi phải có các nghiên cứu sâu hơn đề †ìm ra các kỹ thuật khai phá dữ liệu hiệu quả hơn. Tr0ng những năm gần đây, việc nghiên cứu về khai phá dữ liệu đã có xu hơiớng chuyển lừ cơ sở đữ liệu quan hệ và cơ sở dữ liệu gia0 dịch sang cơ sở dữ liệu không gian. Sự lhay đổi này không những giúp hiểu đojợc dữ liệu không gian mà còn giúp khám phá đojợc mối quan hệ giữa dữ liệu không gian và phi không gian, các mô hình dựa trên tri thức không gian, phoJơng pháp lối qu cau truy vấn, tô chức dữ liệu lr0ng cơ sở dữ liệu không gian,. Khai phá dữ liệu không gian đơjợc sử dụng nhiều tr0ng các hệ thống thông lin địa lý (GIS), viễn thám, khai phá dữ liệu ảnh, ảnh y học, rô sốt dẫn đojờng,.
Khám phá tri thức lừ dữ liệu không gian có thê đojợc thực hiện dotới nhiều hình thức khác nhau nhọ sử dụng các quy lắc đặc lroing và quyết định, trích rúi và mô lá các cầu trúc hOặc cụm nỗi sật, kết hợp không gian, các sài l0án truyền thống của một hệ thông lin địa lý có thể trả lời các câu hỏi kiểu nhơi: - _ Ihững c0n phố nà0 dẫn đến Ihà hát lớn hà Hội ? - Ihững căn nhà nà0 nằm †r0ng vòng quy h0ạch mở rộng phố? Khai phá dữ liệu không gian có thê giúp trả lời ch0 các câu hỏi dạng: - _ Xu hơlớng của các dòng chảy, các dirt gay địa tang ? - _ Tên số lrí các trạm liếp sóng điện th0ại di động nhơi thế nà0? - [hing vj tri mA0 146i oyu dé dat cic may ATM ? Một tr0ng những sài l0án liên quan đến dữ liệu không gian, cụ thể là dữ liệu địa lý có ý nghĩa thực lế ca0 là sài l0án xác định vị krí lối oịu ch0 việc đặi các máy ATM của các ngân hàng. hiện nay, còng với chủ lrolơng xây dựng chính phủ điện tử và thúc đây gia0 dịch điện lử ở Việt Ilam, việc thanh l0án đang chuyên dần lừ sử dụng liền mặt sang thanh 104m qua lài kh0ản, đồng thời với nhu cầu sử dung thé tin dụng ngày càng lăng, các ngân hàng lr0ng nojớc sử dụng lối đa mọi lợi thế để cạnh 2 tranh, thu hút khách hàng. Một tr0ng các cách dé cạnh lranh hiệu quả là thông qua việc thiết lập các trạm ATM dé khách hàng có thể lự thực hiện các gia0 dịch của mình mội cách thuận liện. 3 Tính đến cuối năm 2010, số loợng trạm ATM đã đại gần 8000 máy, số thẻ ATM đgjợc phái hành là hơn 12 triệu thé sởi hơn 40 tô chức ngân hàng.
Tuy nhiên, việc phái triển hệ thống các trạm ATM choja đơjợc quy h0ạch †he0 chiến lojợc sài bản, vị lrí đặt các lạm ATM vẫn còn nhiều sất cập nho| tình trạng thừa hOặc thiếu ATM ở nội số khu vực, d0 đó choỊa khai thác đojợc hết iềm năng của hình thức gia0 dịch này. Xuất phái lừ nhu cầu thực lễ đó, luận văn giới thiệu mội số phơ|ơng pháp phân cụm dữ liệu tr0ng khai phá cơ sở dữ liệu không gian đojợc sử dụng hiện nay. Trên cơ sở đó cải đặt thử nghiệm mội ứng dụng sử dụng kỹ thuật phân cụm dữ liệu địa lý, tr0ng đó khai thác thông tin địa lý của các đối lojợng địa lý có lầm ảnh hojởng quan trọng đến vị tri đặt các máy ATM nhơi: các siêu thị, trung lâm †hoJơng mại, khách sạn, nhà hàng, khu đông dân coi, đojờng gia0 thông. để hỗ trợ giải quyết sài 104n tìm vị trí lối ơtu đặ! các máy ATM tr0ng thành phố hà Hội.