Luận văn Thạc sĩ Công nghệ thông tin: Phân cụm mờ trọng số địa lý

Chia sẻ: Tomjerry001 | Ngày: | Loại File: PDF | Số trang:73

Thêm vào BST

Báo xấu

35
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung của luận văn bao gồm: Chương 1: Trình bày các kiến thức cơ bản về bài toán phân cụm dữ liệu địa lý, bao gồm các định nghĩa, độ đo và ứng dụng của nó trong 8 các lĩnh vực ý tế, an ninh, xã hội, .v.v. đồng thời trình bày sơ lược về các thuật toán phân cụm mờ trọng số địa lý FCM, NE, FGWC, CFGWC, CFGWC2, IPFGWC, MIPFGWC cùng các ưu nhược điểm của chúng, từ đó đề xuất thuật toán KMIPFGWC. Chương 2: Trình bày thuật toán phân cụm mờ trọng số địa lý KMIPFGWC, với hàm mục tiêu sử dụng độ đo khoảng cách là hàm nhân Gaussian thay vì sử dụng hàm Euclidean truyền thống và sử dụng mô hình SIM2 để nâng cao chất lượng phân cụm cho bài toán. Chương 3: Trình bày một số kết quả thực nghiệm thuật toán KMIPFGWC trên bộ dữ liệu thực tế là bộ dữ liệu địa lý về kinh tế - xã hội từ tổ chức Liên Hợp Quốc – UNO và so sánh nó với các thuật toán MIPFGWC, FGWC để đánh giá hiệu quả của thuật toán đề xuất.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Phân cụm mờ trọng số địa lý

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ THU HOÀN PHÂN CỤM MỜ TRỌNG SỐ ĐỊA LÝ LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ THU HOÀN PHÂN CỤM MỜ TRỌNG SỐ ĐỊA LÝ Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS Nguyễn Đình Hóa TS. Lê Hoàng Sơn HÀ NỘI - 2014
1 LỜI CAM ĐOAN Tôi xin cam đoan kết quả đạt đƣợc trong luận văn là sản phẩm nghiên cứu, tìm hiểu của riêng cá nhân tôi. Trong toàn bộ nội dung của luận văn, những điều đƣợc trình bày hoặc là của cá nhân tôi hoặc là đƣợc tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và đƣợc trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, ngày tháng 7 năm 2014 Ngƣời cam đoan Nguyễn Thị Thu Hoàn
2 LỜI CẢM ƠN Trƣớc khi trình bày nội dung chính của luận văn, em xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS Nguyễn Đình Hóa và Tiến sĩ Lê Hoàng Sơn, ngƣời đã tận tình hƣớng dẫn và tạo điều kiện để em có thể hoàn thành luận văn này. Thứ hai, em xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong khoa Công nghệ thông tin, trƣờng Đại học Công nghệ Hà Nội, Đại học Quốc gia Hà Nội đã dạy bảo tận tình em trong suốt quá trình em học tập tại khoa. Thứ ba, em xin đƣợc gửi lời cảm ơn tới các thầy cô, các anh chị và các bạn trong Trung tâm Tính toán Hiệu năng cao, trƣờng Đại học Khoa học tự nhiên đã giúp đỡ em trong suốt thời gian làm luận văn này. Cuối cùng em xin chân thành cảm ơn tới gia đình, bạn bè, đồng nghiệp đã luôn bên em cổ vũ, động viên, giúp đỡ em trong suốt quá trình học tập và thực hiện luận văn này. Luận văn này đƣợc thực hiện dƣới sự tài trợ của đề tài NAFOSTED, mã số: 102.05-2014.01. Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng cho phép nhƣng chắc chắn sẽ không tránh khỏi những thiếu sót. Em rất mong đƣợc sự góp ý chân thành của thầy cô và các bạn để em hoàn thiện luận văn của mình. Xin chân thành cảm ơn! Hà Nội, ngày tháng 7 năm 2014 Học viên Nguyễn Thị Thu Hoàn
3 MỤC LỤC LỜI CAM ĐOAN.................................................................................................. 1 LỜI CẢM ƠN ....................................................................................................... 2 MỤC LỤC ............................................................................................................. 3 DANH MỤC CÁC CHỮ KÝ HIỆU VÀ VIẾT TẮT ........................................... 5 DANH MỤC CÁC HÌNH VẼ............................................................................... 6 DANH MỤC CÁC BẢNG BIỂU ......................................................................... 6 MỞ ĐẦU ............................................................................................................... 7 CHƢƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU ĐỊA LÝ .................... 9 1.1. Phân cụm dữ liệu địa lý ........................................................................... 9 1.1.1. Định nghĩa bài toán ............................................................................. 10 1.1.2. Độ đo khoảng cách.............................................................................. 10 1.1.3. Ứng dụng............................................................................................. 11 1.1.4. Ví dụ thực tế........................................................................................ 12 1.2. Tổng quan về các thuật toán phân cụm dữ liệu địa lý .............................. 13 1.2.1. Một số khái niệm cơ bản ..................................................................... 13 1.2.2. Thuật toán FCM .................................................................................. 16 1.2.3. Thuật toán NE ..................................................................................... 17 1.2.4. Thuật toán FGWC ............................................................................... 18 1.2.5. Thuật toán CFGWC ............................................................................ 20 1.2.6. Thuật toán CFGWC2 .......................................................................... 22 1.2.7. Thuật toán IPFGWC ........................................................................... 25 1.2.8. Thuật toán MIPFGWC ........................................................................ 27 1.2.9. Ví dụ minh họa.................................................................................... 29
4 1.3. Kết luận chƣơng ........................................................................................ 33 CHƢƠNG 2: THUẬT TOÁN KMIPFGWC ...................................................... 34 2.1. Nhƣợc điểm của thuật toán MIPFGWC ................................................... 34 2.2. Tổng quan về nhóm thuật toán phân cụm sử dụng hàm nhân .................. 35 2.3. Mô hình và nghiệm của bài toán phân cụm dữ liệu địa lý sử dụng hàm nhân .................................................................................................................. 37 2.4. Một số tính chất......................................................................................... 49 2.5. Đánh giá chất lƣợng phân cụm ................................................................. 51 2.6. Thuật toán KMIPFGWC ........................................................................... 59 2.7. Độ phức tạp thuật toán .............................................................................. 60 2.8. Kết luận chƣơng ........................................................................................ 60 CHƢƠNG 3: MỘT SỐ KẾT QUẢ THỬ NGHIỆM .......................................... 61 3.1. Môi trƣờng thực nghiệm ........................................................................... 61 3.2. So sánh chất lƣợng phân cụm ................................................................... 61 3.3. Khảo sát các đặc trƣng của thuật toán KMIPFGWC ................................ 65 3.4. Kết luận chƣơng ........................................................................................ 67 KẾT LUẬN ......................................................................................................... 68 TÀI LIỆU THAM KHẢO ................................................................................... 69
5 DANH MỤC CÁC CHỮ KÝ HIỆU VÀ VIẾT TẮT Từ viết tắt Từ Tiếng Anh Từ hoặc cụm từ FCM Fuzzy C-means, Thuật toán phân cụm mờ NE Neighbourhood Effects, Thuật toán hiệu ứng vùng lân cận FGWC Fuzzy Geographically Weight Thuật toán phân cụm dữ Clustering, liệu theo trọng số địa lý CFGWC Context Fuzzy Geographically Thuật toán phân cụm địa Weight Clustering, lý kết hợp ngữ cảnh IPFGWC Intuitionistic Possiblistic Fuzzy Thuật toán phân cụm địa Geographically Weighted Clustering, lý trên tập mờ trực cảm MIPFGWC Modification Intuitionistic Thuật toán phân cụm địa Possiblistic Fuzzy Geographically lý hiệu chỉnh trên tập mờ Weighted Clustering, trực cảm KMIPFGWC Kernel-based Modification Thuật toán phân cụm địa Intuitionistic Possiblistic Fuzzy lý hiệu chỉnh trên tập mờ Geographically Weighted Clustering trực cảm sử dụng hàm nhân SIM Spatial Interaction Model Mô hình tƣơng tác không gian SIM2 Spatial Interaction - Modification Mô hình tƣơng tác - hiệu Model chỉnh không gian WF Weighting function Hàm trọng số
6 DANH MỤC CÁC HÌNH VẼ Hình 1.1: Phân bố những trƣờng hợp mắc bệnh sốt xuất huyết tại Việt Nam năm 2011 ..................................................................................................................... 12 Hình 1.2: Bộ dữ liệu trƣớc khi phân cụm ........................................................... 29 Hình 1.3: Kết quả phân cụm khi sử dụng thuật toán FCM ................................. 30 Hình 1.4: Kết quả phân cụm khi sử dụng thuật toán NE .................................... 30 Hình 1.5: Kết quả phân cụm khi sử dụng thuật toán FGWC .............................. 31 Hình 1.6: Kết quả phân cụm khi sử dụng thuật toán CFGWC ........................... 31 Hình 1.7: Kết quả phân cụm khi sử dụng thuật toán IPFGWC .......................... 32 Hình 1.8: Kết quả phân cụm khi sử dụng thuật toán MIPFGWC ....................... 32 DANH MỤC CÁC BẢNG BIỂU Bảng 3.1: Giá trị IFV của các thuật toán theo số lƣợng cụm C và các tham số . 62 Bảng 3.2: Thời gian tính toán của các thuật toán theo số lƣợng cụm C và các tham số ................................................................................................................ 64 Bảng 3.3: Giá trị IFV của MIPFGWC trong các trƣờng hợp ............................. 66 Bảng 3.4: Giá trị IFV trong KMIPFGWC bởi tham số  trong hàm Gaussian. 66
7 MỞ ĐẦU Ngày nay, các công cụ tính toán mềm đang dần trở nên phổ biến trong các lĩnh vực của khoa học tính toán, do tính hữu hiệu của nó trong việc giải quyết các bài toán thực tế hiện tại của kinh tế - xã hội mà các công cụ phân tích cổ điển nhƣ các mô hình thống kê và lớp các phƣơng pháp giải chính xác không thực hiện đƣợc [13]. Một trong những hƣớng đƣợc quan tâm hiện nay trong tính toán mềm là ứng dụng các phƣơng pháp này vào các bài toán thực tế có tham chiếu không gian và các phƣơng pháp nhƣ vậy đƣợc gọi là lớp các phƣơng pháp tính toán mềm ảnh hƣởng bởi đặc trƣng địa lý trong các mô hình tƣơng tác không gian. Trong lớp các phƣơng pháp tính toán mềm ảnh hƣởng bởi đặc trƣng địa lý trong các mô hình tƣơng tác không gian, phƣơng pháp phân cụm mờ trọng số địa lý là một phƣơng pháp đã đƣợc ứng dụng cho nhiều bài toán quan trọng của kinh tế - xã hội. Phƣơng pháp này ra đời bắt nguồn từ nhu cầu của bài toán phân cụm dữ liệu địa lý, đƣợc định nghĩa theo Sleight (1993) [19] là sự phân chia dữ liệu có đặc trƣng không gian vào các nhóm khác nhau theo một số tiêu chí nhất định để từ đó đƣa ra các chính sách hợp lý nhằm phân phối sản phẩm và dịch vụ cho các vùng miền. Kết quả của phân cụm dữ liệu địa lý thƣờng đƣợc thể hiện dƣới dạng bản đồ phân bố của các đặc trƣng. Cho đến nay, thuật toán phân cụm mờ trọng số địa lý tốt nhất cho bài toán này là thuật toán MIPFGWC [10]. Thuật toán này đƣợc xây dựng dựa trên các lý thuyết về tập mờ trực cảm, phân cụm mờ xác suất và mô hình SIM2 và đã đƣợc kiểm chứng về chất lƣợng phân cụm khi so sánh với một số thuật toán khác nhƣ NE [24], FGWC [12] và IPFGWC [8]. Mục tiêu và động cơ nghiên cứu của luận văn là cải tiến thuật toán MIPFGWC sử dụng ý tƣởng về lý thuyết hàm nhân [23] nhằm nâng cao chất lƣợng phân cụm của thuật toán. Thuật toán thu đƣợc sẽ đƣợc kiểm chứng so sánh đánh giá với MIPFGWC và một số thuật toán khác về chất lƣợng phân cụm. Bố cục của luận văn bao gồm 3 chƣơng:  Chƣơng 1: Trình bày các kiến thức cơ bản về bài toán phân cụm dữ liệu địa lý, bao gồm các định nghĩa, độ đo và ứng dụng của nó trong
8 các lĩnh vực ý tế, an ninh, xã hội, .v.v. đồng thời trình bày sơ lƣợc về các thuật toán phân cụm mờ trọng số địa lý FCM, NE, FGWC, CFGWC, CFGWC2, IPFGWC, MIPFGWC cùng các ƣu nhƣợc điểm của chúng, từ đó đề xuất thuật toán KMIPFGWC.  Chƣơng 2: Trình bày thuật toán phân cụm mờ trọng số địa lý KMIPFGWC, với hàm mục tiêu sử dụng độ đo khoảng cách là hàm nhân Gaussian thay vì sử dụng hàm Euclidean truyền thống và sử dụng mô hình SIM2 để nâng cao chất lƣợng phân cụm cho bài toán.  Chƣơng 3: Trình bày một số kết quả thực nghiệm thuật toán KMIPFGWC trên bộ dữ liệu thực tế là bộ dữ liệu địa lý về kinh tế - xã hội từ tổ chức Liên Hợp Quốc – UNO và so sánh nó với các thuật toán MIPFGWC, FGWC để đánh giá hiệu quả của thuật toán đề xuất.
9 CHƢƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU ĐỊA LÝ 1.1. Phân cụm dữ liệu địa lý Chúng ta luôn có nhu cầu cần có thông tin về những đối tƣợng mà chúng ta quan tâm. Ví dụ chúng ta đang tìm hiểu thông tin về các ngôi trƣờng trung học trong khu vực chúng ta đang sinh sống. Khi thu thập thông tin, ta sẽ có đƣợc những mẫu tin cho các trƣờng. Với mỗi trƣờng, các thông tin có thể có là tên trƣờng, loại hình đào tạo, số lƣợng giáo viên, số lƣợng cử nhân, thạc sĩ, tiến sĩ đang công tác tại trƣờng, số lƣợng học sinh, số lƣợng nam, số lƣợng nữ, ngày thành lập, địa chỉ .v.v. Nhƣ vậy là có rất nhiều thông tin về trƣờng đó nhƣng còn thiếu một loại thông tin rất quan trọng: Ngôi trƣờng đó ở vị trí nào trong không gian, ở độ cao bao nhiêu, xung quang ngôi trƣờng đó có những đối tƣợng nào không, khuôn viên của trƣờng có hình dáng nhƣ thế nào, rộng bao nhiêu, kích thƣớc các chiều nhƣ thế nào, từ ngôi trƣờng đó đến nhà bạn thì khoảng cách bao nhiêu, đi qua các con đƣờng nào là ngắn nhất, v.v. Tất nhiên là chúng ta có thể mô tả những thông tin bị thiếu trên đây bằng lời mà vẫn hiểu đƣợc. Nhƣng rõ ràng là khó hình dung một cách cụ thể. Để giải quyết bài toán này, ngƣời ta xây dựng một loại dữ liệu gọi là dữ liệu địa lý để tái hiện hình dáng các đối tƣợng trong không gian bằng hình học, các thông tin không tái hiện ở dạng hình học đƣợc thì sẽ đƣợc đính kèm vào các hình vẽ đó một cách tƣơng ứng. Các thông tin đính kèm này đƣợc gọi là dữ liệu thuộc tính. Phần hình học đƣợc gọi là dữ liệu không gian. Nhƣ vậy, dữ liệu địa lý là dữ liệu bao gồm dữ liệu không gian và dữ liệu thuộc tính đƣợc kết hợp với nhau một cách tƣơng ứng. Dữ liệu địa lý có thể là các bản đồ số trên máy vi tính, các mô hình mô phỏng hình dáng bề mặt trái đất, các cơ sở dữ liệu ảnh bề mặt trái đất. Dữ liệu địa lý hay còn gọi là dữ liệu không gian ngày một phát triển với lƣợng dữ liệu ngày càng lớn và phức tạp hơn, đòi hỏi các nhà nghiên cứu cần có những phƣơng pháp, kỹ thuật để phân tích và khai phá dữ liệu hiệu quả hơn. Trong những năm gần đây, việc nghiên cứu và khai phá dữ liệu đã có xu hƣớng chuyển từ cơ sở dữ liệu quan hệ và cơ sở dữ liệu giao dịch sang cơ sở dữ liệu không gian. Sự thay đổi này không những giúp hiểu đƣợc dữ liệu không gian mà còn giúp khám phá đƣợc mối quan hệ giữa dữ liệu không gian và
10 phi không gian, các mô hình dựa trên tri thức không gian, phƣơng pháp tối ƣu câu truy vấn, tổ chức dữ liệu trong cơ sở dữ liệu không gian. Khai phá dữ liệu không gian đƣợc sử dụng nhiều trong các hệ thống thông tin địa lý (GIS), viễn thám, khai phá dữ liệu ảnh, ảnh y học, rô bốt dẫn đƣờng, v.v. Khám phá tri thức từ dữ liệu không gian có thể đƣợc thực hiện dƣới nhiều hình thức khác nhau nhƣ sử dụng các quy tắc đặc trƣng và quyết định, trích rút và mô tả các cấu trúc hoặc cụm nổi bật, kết hợp không gian, v.v. 1.1.1. Định nghĩa bài toán Định nghĩa 1-1. Bài toán phân cụm dữ liệu địa lý [9] đƣợc định nghĩa nhƣ sau: N C (1.1) J   u kj || X k  V j || 2  min , k 1 j 1 Với các điều kiện: ukj  [0,1] (1.2) C  u 1 j 1 kj   C   ukj  N 0   k 1 ukj  ukj (W j )  V j  V j (W j )   Trong đó:  u kj là độ thuộc của điểm dữ liệu thứ k vào cụm j , j  1, C ,  X k là điểm dữ liệu thứ k , k  1, N ,  V j là tâm cụm không gian thứ j , j  1, C ,  W j là trọng số của cụm j , j  1, C . 1.1.2. Độ đo khoảng cách Cho x, y là hai đối tƣợng, x  ( x1 , x2 ,..., xn ), y  ( y1 , y2 ,..., yn ) với n là số chiều. Khoảng cách giữa hai đối tƣợng x và y đƣợc tính thông qua các độ đo khoảng cách sau:
11 1  n q  Khoảng cách Minskowski: d ( x, y)    | xi  yi |q  , trong đó q là số tự  i 1  nhiên dƣơng. n  Khoảng cách Euclidean: d ( x, y)  (x i 1 i  yi ) 2 , đây là trƣờng hợp đặc biệt của khoảng cách Minskowski trong trƣờng hợp q  2 . n  Khoảng cách Manhattan: d ( x, y)  | xi  yi | , đây là trƣờng hợp đặc biệt i 1 của khoảng cách Minskowski trong trƣờng hợp q  1 .  Khoảng cách Chenbysev: d(x, y)  max in1 | X i  Yi |, đây là trƣờng hợp đặc biệt của khoảng cách Minskowski trong trƣờng hợp q   . 1.1.3. Ứng dụng Phân cụm dữ liệu địa lý đƣợc ứng dụng trong các lĩnh vực khác nhau nhƣ:  Hoạch định chính sách: Xác định các khu vực có tỷ lệ thất nghiệp cao để đƣa ra các chính sách hỗ trợ cụ thể.  Thƣơng mại: Với từng vùng khác nhau nhu cầu khách hàng sẽ khác nhau. Chính vì thế phân cụm dữ liệu địa lý sẽ giúp các nhà kinh doanh có đƣợc tầm nhìn bao quát và đƣa ra đƣợc mục tiêu tiếp thị hợp lý.  Sinh học: Việc xác định các loại sinh vật và phân loại các Gen tƣơng đồng sẽ hiệu quả và chính xác hơn khi phân cụm các loại sinh vật theo các vùng có khí hậu, địa hình và môi trƣờng sống tƣơng đồng với nhau.  Y tế: Giúp khoanh vùng các địa phƣơng có tỷ lệ mắc bệnh cao để giúp trong việc quản lý và chữa trị.  Xã hội: Giúp khoanh vùng các điểm nóng về tội phạm.  v. v.
12 1.1.4. Ví dụ thực tế Miền Bắc 5,378 ca (7.7%) Miền Trung 34,21 ca (4.9%) Tây Nguyên 481 ca (0.7%) Miền Nam 60,596 ca (86.7%) Hình 1.1: Phân bố những trƣờng hợp mắc bệnh sốt xuất huyết tại Việt Nam năm 2011 (Tổng số ca 69,876) Hình 1.1 là ví dụ về ứng dụng của bài toán phân cụm dữ liệu địa lý cho bài toán tìm phân bố những trƣờng hợp mắc bệnh sốt xuất huyết tại Việt Nam năm 2011. Trong đó, màu đỏ thẫm đại diện cho những khu vực có tỷ lệ số ca bị mắc bệnh sốt xuất huyết là cao nhất, màu vàng nhạt đại diện cho những khu vực có tỷ lệ số ca bị mắc bệnh sốt xuất huyết là thấp nhất. Từ bản đồ phân bố những trƣờng hợp mắc bệnh sốt xuất huyết trên giúp các nhà nghiên cứu có thể khoanh vùng dịch bệnh; xác định vùng nguy cơ xảy ra
13 dịch bệnh từ đó đƣa ra những dự đoán để có hƣớng xửa lý kịp thời, hiệu quả nhất. Đây là những chức năng không thể thực hiện đƣợc một cách dễ dàng nếu áp dụng phƣơng pháp truyền thống. 1.2. Tổng quan về các thuật toán phân cụm dữ liệu địa lý 1.2.1. Một số khái niệm cơ bản  Định nghĩa 1-2: Định nghĩa tập mờ Không giống nhƣ tập rõ mà ta đã biết trƣớc đây, mỗi phần tử luôn xác định hoặc thuộc hoặc không thuộc nó, thì với tập mờ chỉ có thể xác định một phần tử liệu thuộc vào nó là nhiều hay ít, tức mỗi đối tƣợng chỉ là phần tử của tập mờ với một khả năng nhất định mà thôi. Tập mờ [24] F xác định trong không gian X đƣợc định nghĩa nhƣ sau: F   X ,  F ( x) | x  X  với  F ( x)  0,1 (1.3) Trong đó: -  F đƣợc gọi là hàm thuộc của tập mờ F -  F (x) là giá trị độ thuộc của x vào tập mờ F .  Định nghĩa 1-3: Tập mờ loại hai khoảng. Tập mờ truyền thống (tập mờ loại một) tiềm ẩn những mâu thuẫn nhất định. Đó là để phát triển bất cứ hệ logic mờ nào, ngƣời thiết kế phải xây dựng hàm thuộc cho các tập mờ sử dụng trong hệ hay là phải mô tả sự không chắc chắn bằng các hàm thuộc rõ ràng, chắc chắn. Điều đó có nghĩa là việc biểu diễn sự không chắc chắn lại sử dụng các độ thuộc mà bản thân chúng là các số thực chính xác. Tập mờ loại hai nhằm giải quyết vấn đề trên. Đó là thay vì độ thuộc là một số thực nhƣ tập mờ truyền thống, với tập mờ loại hai độ thuộc là một tập mờ loại một trên đoạn [0, 1]. Tập mờ loại hai thƣờng đƣợc sử dụng trong những trƣờng hợp khó xác định, chính xác giá trị độ thuộc của các phần tử trong không gian nền. Nhƣ vậy, mở rộng tập mờ loại một bằng cách cho phép các độ thuộc là các tập mờ loại một trong khoảng [0, 1] ta đƣợc khái niệm tập mờ loại hai.
14 ~ Một tập mờ loại hai khoảng [14] A xác định trên không gian X đƣợc định nghĩa nhƣ sau: Ã  (( x, u),  Ã ( x, u) | x  X , u  J x  0,1) (1.4) Trong đó: - x là một đối tƣợng thuộc không gian X -  Ã ( x, u) : Giá trị độ thuộc của ( x, u ) và tập mờ A ,  Ã ( x, u)  0,1 ~  Định nghĩa 1-4: Tập mờ Trực cảm ~ Một tập mờ trực cảm [2] A xác định trên không gian X đƣợc định nghĩa nhƣ sau: Ã  x,  A~ ( x),  A~ ( x) | x  X , (1.5) Trong đó: - x là một đối tƣợng thuộc không gian X , ~ -  A~ ( x) là độ thuộc của phần từ x X vào tập mờ A , ~ -  A~ ( x) là độ không thuộc của phần tử x X vào tập mờ A ,  A~ ( x),  A~ ( x)  0,1x  X , (1.6) 0   A~ ( x)   A~ ( x)  1, x  X , (1.7) -  A~ ( x)  1   A~ ( x)   A~ ( x), x  X đƣợc gọi là độ do dự của phần tử x X ~ vào tập mờ A . Khi  A~ ( x)  0 thì tập mờ trực cảm sẽ là tập mờ truyền thống.  Định nghĩa 1-5: Biến ngữ cảnh Một biến ngữ cảnh [17] trong Y  X Là ánh xạ: Y  0,1 yk  f k  A( yk ) (1.8) Trong đó: - X  X 1 , X 2 ,..., X N : tập dữ liệu gồm N điểm dữ liệu.
15 - Y : Biến ngữ cảnh giả thiết. - f k : Độ thuộc giữa điểm dữ liệu thứ k của tập X đến ngữ cảnh Y .  Định nghĩa 1-6: Hàm trọng số Hàm trọng số (Weighting Function - WF [10]) là một hàm: w: R R  R   popk  pop j b  pkjc  IM kjd  k j (1.9) (k , j )  wkj   d kja  0 else Trong đó: wkj là trọng số địa lý giữa hai cụm k và j , popk ( pop j ) là số điểm dữ liệu của cụm k ( j ) , d kj là khoảng cách lớn nhất giữa các điểm dữ liệu trong biên giới chung của hai cụm k và j , IM kj là tổng số điểm dữ liệu di cƣ từ cụm k tới cụm j và ngƣợc lại. a, b, c và d là các hằng số. Ta có một số các ràng buộc nhƣ sau: C  pop k  N 0 ,  k 1 (1.10)  p kj  d kj ,   IM kj  pop k  pop j  Trong đó: C là số lƣợng cụm, N 0 tổng số điểm dữ liệu của tất cả các cụm, khi pkj  0 thì N 0  N .  Định nghĩa 1-7: Mô hình tƣơng tác hiệu chỉnh không gian (SIM2) Mô hình tƣơng tác hiệu chỉnh không gian (SIM2) [10] đƣợc định nghĩa, k 1 1 C uk'    uk     wkj u 'j      wkj  u j j 1 A j k (1.11)     1 (1.12) Trong đó:
16 u k' (u k ) là độ thuộc mới (cũ) của các điểm dữ liệu vào cụm k .  ,  và  là các hằng số, A là tham số đảm bảo tổng độ thuộc của một điểm dữ liệu vào các cụm bằng 1. wkj là trọng số địa lý giữa hai cụm k và j đƣợc định nghĩa trong phƣơng trình (1.9). 1.2.2. Thuật toán FCM Thuật toán FCM [3] là thuật toán phân cụm đƣợc sử dụng rất rộng rãi. Mặc dù nó chƣa sử dụng các tham số địa lý nhƣng nó lại là tiền đề để phát triển các thuật toán phân cụm dữ liệu địa lý sau này. Thuật toán FCM đƣợc mô tả nhƣ sau:  Đầu vào: - Tập dữ liệu đầu vào X , số mờ m - Số điểm dữ liệu N , số cụm C , số chiều r - Ngƣỡng  .  Đầu ra: - C cụm dữ liệu sao cho thỏa mãn hàm mục tiêu: N C (1.13) J   u kjm X k  V j 2  min k 1 j 1  Các bƣớc thực hiện thuật toán: Bƣớc 1: Khởi tạo ma trận U (t ) với t  0 Bƣớc 2: Tính ma trận tâm V (t ) bởi công thức: N (1.14) u m ki Xk Vi  k 1 N ; i  1, C u k 1 m ki Bƣớc 3: Tính U(t+1) bởi công thức: u ki  1 ; i  1, C; k  1, N (1.15) 2 C  || X k  Vi ||  m    j 1  || X  V ||   k j 
17 Bƣớc 4: Nếu || U (t  1)  U (t ) ||  thì dừng thuật toán, ngƣợc lại thì quay lại bƣớc 2.  Ƣu điểm [3]: - Thuật toán đơn giản, dễ thực hiện.  Nhƣợc điểm [3]: - Nhạy cảm với các nhiễu và phần tử ngoại lai trong dữ liệu Đây là thuật toán phân cụm mờ nói chung, chƣa sử dụng các yếu tố địa lý. 1.2.3. Thuật toán NE Thuật toán NE [24] là thuật toán phân cụm dữ liệu có tính đến yếu tố địa lý đầu tiên, đƣợc đƣa ra bởi Feng và Flowerdew vào năm 1998. Thuật toán đƣợc mô tả nhƣ sau:  Đầu vào: - Tập dữ liệu đầu vào X , số mờ m - Số điểm dữ liệu N , số cụm C , số chiều r - Các tham số địa lý a,b, ,  - Ngƣỡng  .  Đầu ra: - C cụm dữ liệu sao cho thỏa mãn hàm mục tiêu: N C (1.16) J   u kjm X k  V j 2  min k 1 j 1  Các bƣớc thực hiện thuật toán: Bƣớc 1: Khởi tạo ma trận U (t ) với t  0 Bƣớc 2: Tính ma trận tâm V (t ) bởi công thức: N (1.17) u m ki Xk Vi  k 1 N ; i  1, C. u k 1 m ki
18 Bƣớc 3: Tính U (t  1) bởi công thức: u ki  1 ; i  1, C , k  1, N . (1.18) 2 C  || X k  Vi ||  m    j 1  || X  V ||   k j  Bƣớc 4: Nếu || U (t  1)  U (t ) ||  thì dừng thuật toán, ngƣợc lại thì quay lại bƣớc 2. Bƣớc 5: Hiệu chỉnh bởi các đặc trƣng địa lý: 1 C (1.19) uki'    uki      wij  uki ; i  1, C , k  1, N A j 1    1 (1.20) ( pij ) b (1.21) wij  a d ij Trong đó, pij là khoảng cách lớn nhất giữa các điểm trong phần biên chung giữa cụm i và cụm j , d ij là khoảng cách tâm cụm i và cụm j , A là hệ số để đảm bảo tổng độ thuộc của một phần tử vào tất cả các cụm luôn bằng 1.  Ƣu điểm [24]: - Kết hợp đặc trƣng địa lý và giúp cải thiện chất lƣợng phân cụm cho thuật toán FCM.  Nhƣợc điểm [24]: - Thuật toán bỏ qua các tác động của các khu vực mà không có biên chung. - Thuật toán loại trừ ảnh hƣởng của yếu tố dân số - một yếu tố quan trọng cho bài toán phân cụm dữ liệu địa lý. - Việc hiệu chỉnh địa lý chỉ đƣợc thực hiện trong bƣớc cuối cùng nên các cụm không gắn chặt với quan hệ không gian. 1.2.4. Thuật toán FGWC Thuật toán FGWC [12] đƣợc xây dựng bởi Mason và Jacobson vào năm 2007 nhằm khắc phục những hạn chế của thuật toán NE đƣợc trình bày ở trên. Thuật toán đƣợc mô tả nhƣ sau: