Tài liệu Nghiên cứu tìm hiểu thuật toán cơ bản về phân nhóm dữ liệu trên cơ sở dữ liệu không gian

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP ........................................ KHỔNG MINH TỰ NGHIÊN CỨU, TÌM HIỂU MỘT SỐ THUẬT TOÁN CƠ BẢN VỀ PHÂN NHÓM DỮ LIỆU TRÊN CƠ SỞ DỮ LIỆU KHÔNG GIAN Chuyên ngành: KỸ THUẬT ĐIỆN TỬ Mã số: 60. 52. 02. 03 TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT THÁI NGUYÊN - 2014 1 Luận văn đƣợc hoàn thành tại: Trƣờng Đại học Kỹ thuật Công nghiệp - Đại học Thái Nguyên Ngƣời hƣớng dẫn khoa học: PGS. TS Lƣơng Chi Mai Phản biện 1: PGS.TS Đỗ Xuân Tiến Học viện Quân sự Phản biện 2: PGS.TS Nguyễn Hữu Công Đại học Thái Nguyên Luận văn đƣợc bảo vệ tại hội đồng chấm luận văn họp tại: Trƣờng Đại học Kỹ thuật Công nghiệp - Đại học Thái Nguyên Vào ngày 18 tháng 04 năm 2014 1 MỞ ĐẦU Trong vài thập kỷ gần đây, công nghệ thông tin có nhiều bước phát triển nhanh chóng và đã được ứng dụng rộng rãi trong mọi lĩnh vực, ngành nghề xã hội, đặc biệt là lĩnh vực quản lý – một lĩnh vực mà yếu tố công nghệ xử lý thông tin có tính chất quyết định. Từ đó, theo quá trình hoạt động của các hệ thống quản lý dẫn đến sự bùng nổ thông tin, kích thước của các kho dữ liệu có kích thước tăng nhanh chóng theo từng năm, từng thời kỳ, làm cho những nhà (lãnh đạo) quản lý rơi vào tình trạng “ngập lụt thông tin”. Kích thước dữ liệu tăng quá nhanh dẫn tới các phương pháp phân tích dữ liệu truyền thống không còn có thể đáp ứng được nữa. Sự ra đời của lĩnh vực khai phá dữ liệu đã mở ra nhiều hướng nghiên cứu mới thu hút sự quan tâm chú ý của nhiều nhà nghiên cứu thuộc nhiều lĩnh vực khác nhau. Đồng thời, dựa trên các kỹ thuật đưa ra trong lĩnh vực này rất nhiều các ứng dụng đã được xây dựng tạo ra được nhiều hệ thống trợ giúp đắc lực cho cuộc sống con người. 1. Tính cấp thiết của đề tài Dữ liệu không gian? Với lý do, ngoài nhu cầu lưu trữ và xử lý các kiểu dữ liệu thông thường như kiểu chuỗi, kiểu số, kiểu ngày tháng, … người sử dụng còn có thêm nhu cầu lưu trữ và xử lý dữ liệu không gian để lưu trữ các đối tượng như Point, Line, Polugon, … Dữ liệu không gian trong lĩnh vực điện tử, truyền thông? Trong hoạt động quản lý của các nhà cung cấp dịch vụ viễn thông, kích thước kho dữ liệu lưu trữ về các cuộc thoại di động tăng nhanh đáng kể. Khai phá dữ liệu không gian Để có thể trích rút các tri thức có ích như trình bày ở trên là một vấn đề quan trọng được nhiều nhà lãnh đạo quản lý quan tâm. Chính vì lý do đó mà em chọn đề tài “Nghiên cứu, tìm hiểu một số thuật toán cơ bản về phân nhóm dữ liệu trên Cơ sở dữ liệu không gian” làm hướng nghiên cứu chính cho luận văn của mình. 2. Mục tiêu đề tài Mục tiêu trọng tâm của đề tài là: - Nghiên cứu một số thuật toán phân nhóm dữ liệu trên cơ sở dữ liệu không gian. - Cài đặt thử nghiệm trên một số mẫu dữ liệu không gian. - Đưa ra bảng so sánh giữa các thuật toán. - Tìm cách xây dựng các tham số cho các thuật toán. 3. Đối tƣợng và phạm vi nghiên cứu - Các kỹ thuật thu thập và lưu trữ dữ liệu; - Các phương pháp phân nhóm dữ liệu; 2 Tập trung nghiên cứu một số thuật toán phân nhóm cơ bản dựa vào mật độ phân bố của các đối tượng dữ liệu không gian. 4. Ý nghĩa khoa học và thực tiễn của đề tài a. Ý nghĩa khoa học Vào cuối thập kỷ 90, kỹ thuật khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database -KDD) được đưa ra nhằm tìm kiếm các thông tin, tri thức cần thiết, có giá trị tiềm ẩn trong một khối dữ liệu lớn và phức tạp như dữ liệu không gian, dữ liệu đa phương tiện, … b. Ý nghĩa thực tiễn Kết quả nghiên cứu là tìm hiểu và đưa ra một số thuật toán phân nhóm có hiệu quả trên dữ liệu không gian, đặc biệt trong trường hợp dữ liệu lớn, bị nhiễu, đa chiều. Kết quả so sánh giữa các thuật toán cho thấy tính hiệu quả của mỗi thuật toán trên những đối tượng dữ liệu khác nhau. 5. Phƣơng pháp nghiên cứu Phương pháp tài liệu: Nghiên cứu các tài liệu (sách, báo, tạp chí khoa học, Internet, …) liên quan đến kỹ thuật phân nhóm dữ liệu trên CSDL không gian. Phương pháp thực nghiệm: Cài đặt thử nghiệm trên một số mẫu dữ liệu, từ đó đưa ra đánh giá về tính hiệu quả của các thuật toán đó. 6. Bố cục của luận văn Ngoài các phần Mở đầu, Mục lục, Danh mục hình, Kết luận, Tài liệu tham khảo. Nội dung chính của luận văn được trình bày trong 04 chương như sau: Chương 1: Tổng quan về khai phá tri thức trong cơ sở dữ liệu không gian. Chương 2: Các cách tiếp cận của kỹ thuật phân nhóm. Chương 3: Các giải thuật phân nhóm trên cơ sở dữ liệu không gian lớn. Chương 4: Xác định tham số, cài đặt thử nghiệm và đánh giá kết quả. - Chƣơng 1. TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ CƠ SỞ DỮ LIỆU KHÔNG GIAN 1.1. Khai phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD) 1.1.1. Sự ra đời của khai phá tri thức trong cơ sở dữ liệu Trong những năm gần đây, cùng với sự thay đổi và phát triển không ngừng của ngành công nghệ thông tin nói chung và trong các ngành công nghệ phần cứng, phần mềm, truyền thông và hệ thống các dữ liệu phục vụ trong các lĩnh vực kinh tế xã hội nói riêng đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng nhanh một cách chóng mặt. 1.1.2. Khái niệm khai phá dữ liệu Khai phá dữ liệu (Data Mining) là một khái niệm ra đời vào những năm cuối của thập kỷ 1980. Nó là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các CSDL, kho dữ liệu…. 3 1.1.3. Quá trình khai phá tri thức trong cơ sở dữ liệu Quá trình khai phá tri thức trong cơ sở dữ liệu bao gồm các giai đoạn sau: 1. Trước tiên cần xác định và hiểu rõ được lĩnh vực ứng dụng và nhiệm vụ đặt ra là xác định các tri thức đã có và mục đích của người sử dụ ng. 2. Tạo lập được một tập dữ liệu đích: Chọn lựa từ cơ sở dữ liệu một tập con dữ liệu với các giá trị biến và các mẫu được quan tâm mà trên đó ta có thể thực hiện việc tìm kiếm, phát hiện tri thức. 3. Làm sạch và tiền xử lý dữ liệu: Thực hiện các thao tác cơ bản như loại bỏ nhiễu hoặc loại bỏ các phần không cần thiết, bổ sung thêm các thông tin cần thiết 4. Thực hiện các phương pháp chuyển đổi để làm giảm bớt số chiều của dữ liệu để tập trung vào những thuộc tính chủ chốt đối với việc phát hiện tri thức. 5. Khai phá dữ liệu: Quá trình áp dụng các giải thuật về tìm kiếm tri thức để đưa ra được những thông tin cần thiết và tiềm ẩn trong tập dữ liệu. 6. Đánh giá, giải thích, thử lại các mẫu đã được khai phá, có thể lặp lại một hoặc nhiều bước kể trên để thu được các kết qu ả tốt hơn. 7. Sử dụng các tri thức phát hiện được: Hợp nhất các tri thức thu được vào một hệ thống làm việc, hoặc đưa ra các tài liệu về tri thức thu được từ dữ liệu về một vấn đề quan tâm. Hình 1.1: Các bước trong quá trình khám phá tri thức KDD 1.1.4. Các nhiệm vụ của khai phá dữ liệu Nhìn chung, mục đích chính của khai phá dữ liệu là dự đoán (prediction) và mô tả (description). 1.2. Phân nhóm (Clustering) và các cách tiếp cận chính 1.2.1. Phân nhóm và các ứng dụng a. Khái niệm Phân nhóm (clustering) là quá trình nhóm một tập các đối tượng vật lý hoặc trừu tượng thành các nhóm hay các lớp đối tượng tương tự nhau. Một lớp (cluster) là một tập các đối tượng dữ liệu trong đó các đối tượng trong cùng một lớp có sự tương tự hoặc giống nhau và ít tương tự hoặc khác nhau so với các đối tượng thuộc lớp khác. 4 Hình 1.2: Biểu đồ Hertzsprung-Russell b. Các ứng dụng của phân nhóm Đây là một hoạt động quan trọng của con người. Khi còn bé, con người học cách phân biệt giữa các đồ vật, giữa động vật và thực vật bằng cách liên tục thay đổi nhận thức trong quan niệm phân chia các đối tượng dựa vào mối tương quan giữa chúng. 1.2.2. Các cách tiếp cận chính Có rất nhiều các thuật toán phân nhóm khác nhau, việc chọn lựa một thuật toán thích hợp phụ thuộc vào kiểu dữ liệu cần thực hiện cũng như là mục đích của ứng dụng. a. Phƣơng pháp phân hoạch (Partioning methods) Ý tưởng chính của kỹ thuật này phương pháp phân hoạch là xác định số nhóm (lớp) trước và xác định luôn tính chất của từng lớp. b. Phƣơng pháp phân cấp (Hierarchical methods) Phương pháp phân cấp thực hiện bằng cách nhóm các đối tượng dữ liệu trên cây phân cấp. Phương pháp phân nhóm theo phân cấp được chia làm hai loại đó là phương pháp phân nhóm theo kiểu từ dưới lên (bottom up) và phương pháp phân nhóm từ trên xuống (top down). Hình 1.3: Mô tả cách phân nhóm theo phương pháp từ dưới lên và từ trên xuống c. Phƣơng pháp dựa vào mật độ (Density - Based Methods) Hầu hết các phương pháp phân nhóm theo phân hoạch chủ yếu dựa vào khoảng cách các đối tượng. d. Phƣơng pháp dựa vào mô hình (Model -based methods) Phương pháp chia lớp dựa vào mô hình thực hiện bằng cách đề xuất ra một mô hình cho mỗi lớp và tìm các dữ liệu phù hợp cho mỗi mô hình đó. 1.3. Hệ quản trị cơ sở dữ liệu không gian 1.3.1. Cơ sở dữ liệu không gian Dữ liệu không gian là dạng dữ liệu đặc biệt, mỗi điểm dữ liệu trong cơ sở dữ liệu ngoài những giá trị biểu thị cho điểm dữ liệu đó còn những giá trị biểu diễn vị trí và toạ độ của điểm đó. 5 1.3.2. Hệ quản trị cơ sở dữ liệu không gian  Hệ quản lý cơ sở dữ liệu không gian là một bộ các công cụ cho phép thực hiện tổ chức, lưu trữ, sắp xếp và tìm kiếm dữ liệu trong cơ sở dữ liệu không gian được nhanh chóng và hiệu quả. Hình 1.4: Những điểm nằm trong miền tô sẫm mới được xét đến khi tìm điểm gần nhất cho điểm x. Những điểm ngoài miền không cần xét đến 1.3.3. Phương pháp truy nhập không gian Các phương thức truy nhập không gian (Spatial Access Method - SAM) đã được phát triển để hỗ trợ hiệu quả cho xử lý các truy vấn trong hệ quản lý cơ sở dữ liệu không gian. Phương pháp chia lưới (grid file). Hình 1.5: Một cách chia lưới. Những ô mầu sẫm là những ô chứa dữ liệu và được lưu trữ. Những ô màu trắng là những ô không chứa dữ liệu a. Phƣơng pháp R*-TREE. R*-tree tạo ra một một cây nhị phân một chiều (1dimensional binary-tree) cho không gian dữ liệu d chiều. Đặc biệt là R*-tree quản lý những khối hình chữ nhật d chiều bằng một mảng một chiều gọi là khoá. Hình 1.6: Mô phỏng một R*-tree gồm 3 mức 1.4. Kết luận Qua chương này, chúng tôi đã trình bày tổng quan về khai phá tri thức trong cơ sở dữ liệu không gian. Tìm hiểu một số khái niệm và các vấn đề liên quan đến khai phá tri thức trong cơ sở dữ liệu, các tính chất và đặc trưng của cơ sở dữ liệu không gian. 6 Chƣơng 2. CÁC CÁCH TIẾP CẬN CỦA KỸ THUẬT PHÂN NHÓM 2.1. Thuật toán DBSCAN Thuật toán phân nhóm dựa trên mật độ thông dụng nhất là thuật toán DBSCAN (Density Based Spatial Clustering of Applicatins with Noise) do Ester, P. Kriegel và J. Sander đề xuất năm 1996. Thuật toán đi tìm các đối tượng mà có số đối tượng láng giềng lớn hơn một ngưỡng tối thiểu. 2.1.1. Các định nghĩa và bổ đề được sử dụng trong thuật toán DBSCAN Định nghĩa 1: Các lân cận của một điểm P với ngưỡng Eps, ký hiệu NEps(p) được xác định như sau: NEps(p) = {q  Dkhoảng cách (p, q)  Eps}, D là tập dữ liệu cho trước Hình 2.1: Lân cận của P với ngưỡng Eps Định nghĩa 2: Mật độ - đến được trực tiếp (directly density-reachable) Một điểm P được gọi là mật độ - đến được trực tiếp từ điểm q với ngưỡng Eps và MinPts trong tập đối tượng D nếu: p  NEps(q) Với NEps(q) là tập con của D || NEps(q) ||  MinPts Điều kiện đối tượng nhân. Hình 2.2: Mật độ - đến được trực tiếp Định nghĩa 3: Đến được mật độ (density-reachable) (để ngắn gọn, từ các phần tiếp sau ta gọi là đến được): Một điểm p được gọi là đến được từ một điểm q theo hai tham số Eps và MinPts nếu tồn tại một dãy p = p1, p2, . . ., pn = q thoả mãn pi+1 là có thể đến được trực tiếp từ pi với i = 1,..n -1. Hình 2.3: Mật độ đến được Định nghĩa 4: Mật độ liên thông (density-connected): Đối tượng p là mật độ liên thông với điểm q theo hai tham số Eps với MinPts nếu như có một đối tượng o mà cả hai đối tượng p, q điều là mật độ đến được o theo tham số Eps và MinPts. 7 Hình 2.4: Mật độ liên thông Định nghĩa 5: Nhóm và nhiễu Giả sử D là một tập các điểm dữ liệu. Một tập con C khác rỗng của D được gọi là một lớp (cluster) theo Eps và MinPts nếu thoả mãn hai điều kiện: 1) p, q  D, nếu p  C và q có thể đến được từ p theo Eps và MinPts thì q  C. 2) p, q  C, p liên thông mật độ với q theo Eps và MinPts. Mọi đối tượng không thuộc nhóm nào cả thì gọi là nhiễu Hình 2.5: Nhóm và nhiễu Định nghĩa 6: Dữ liệu nhiễu (noise): Giả sử C1, C2, . . , Ck là các lớp trong tập dữ liệu D theo tham số Eps và MinPts, điểm dữ liệu nhiễu là điểm dữ liệu không thuộc vào lớp nào trong các lớp C1, C2, ... , Ck tức là Noise = {p  D i = 1...k, p  Ci} Tiếp sau là hai bổ đề để chứng minh cho việc chia lớp của chúng ta theo cách trên là hoàn toàn đúng đắn. Bổ đề 1: Giả sử p là một điểm trong D và ||NEps(p)||  MinPts, tập O = {oo  D} và o có thể đến được từ p theo Eps và MinPts sẽ là một lớp theo Eps và MinPts. Bổ đề 2: Giả sử C là một lớp theo hai tham số Eps và MinPts và p là một điểm thuộc C với ||NEps(p)||  MinPts, khi đó C trùng với tập O = { oo  D và o là mật độ - đến được từ p theo Eps và MinPts}. 2.1.2. Thuật toán DBSCAN Để tìm ra các lớp, DBSCAN bắt đầu bằng cách xét một điểm p bất kì và tìm tất cả những điểm có thể đến được từ p. DBSCAN (SetOfPoints, Eps, MinPts) Begin // Mọi điểm trong tập điểm SetOfPoints được gán là chưa đánh dấu. For i = 1 to SetOfPoints.size do Point := SetOfPoints.get(i); SetOfPoints.ChangeClId(ResultP, UnClassified); Endfor CurrentId := 1; For i = 1 to SetOfPoints.size do Point := SetOfPoints.get(i); If Point.Cl_ID = UnClassified then 8 If ExpandCluster(SetOfPoints,Point, ClusterId, Eps, MinPts) then CurrentId := NextId(CurrentId); Endif Endif Endfor End Hình 2.6: Mô phỏng thuật toán DBSCAN Việc đánh dấu một điểm là điểm nhiễu có thể được thay đổi khi điểm đó lại thuộc vào một lớp được xét sau. ExpandCluster(SetOfPoints,Point,ClusterId,Esp,MinPts):Boolean; Seeds := SetOfPoints.RegionQuery(Point, Eps); If Seeds.size < MinPts then SetOfPoints.ChangeClId(Point, Noise); RETURN False; Else SetOfPoints.ChangeClId(Point, ClusterId); Seeds.delete(Point); While (seeds <> empty) do CurrentP := Seeds.GetFirst(); Result := SetOfPoints.RegionQuery(CurrentP, Eps); If (Result.size >= MinPts) Then For i := 1 to Result.size do ResultP := Result.get(i); If (ResultP.ClId in [UnClassifed, Noise]) then If ResultP.ClId = UnClassifed then Seeds.append(ResultP); Endif SetOfPoints.ChangeClId(ResultP, ClusterId); Endif Endfor Endif Seeds.Delete(CurrentP); Endwhile Endif Hình 2.7: Thủ tục ExpandCluster 2.2. Thuật toán DBCLASD Thuật toán DBCLASD (Distribution Based Clustering of LArge Spatial Databases) thực hiện dựa trên sự phân bố đồng đều của các điểm trong một lớp. Khi đó, mỗi lớp sẽ được đặc trưng bằng một phân bố xác suất khoảng cách của các điểm lân cận gần nhất. Hình 2.8: Ví dụ dữ liệu tập các điểm đƣợc chia thành 2 lớp 2.2.1. Một số định nghĩa Định nghĩa 7: (Lân cận gần nhất của 1 điểm và khoảng cách lân cận gần nhất) 9 Với q là điểm đang xét và S là tập các điểm. Lân cận gần nhất của q trong S, ký hiệu NNS(q) là một điểm p thuộc tập S - {q} có khoảng cách đến q là nhỏ nhất. Định nghĩa 8: (Tập các khoảng cách lân cận gần nhất của tập các điểm) Xét S là tập các điểm và ei là các thành phần trong S. Tập các khoảng cách lân cận gần nhất của S, ký hiệu là NNdistSet(S) để cho ngắn gọn gọi là tập khoảng cách, là tập các giá trị NNdistS(ei) Hình 2.9: Ảnh hƣởng của độ rộng ô lƣới đến việc xác định vùng xấp xỉ Một ô lưới được gọi là đang sử dụng nếu ô lưới đó có chứa ít nhất một điểm trong tập các điểm và vùng xấp xỉ của tập S chính là hợp của các ô lưới đang sử dụng. Hình 2.10 chỉ ra sự phù hợp giữa phân bố quan sát và phân bố mong đợi. Định nghĩa 9: (Lớp) DB là một tập các điểm. Một lớp C là một tập con không rỗng của DB thoả mãn các điều kiện sau: (1) NNDistSet(C) phải có sự phân bố mong đợi với một mức độ tin cậy xác định. (2) C có tính chất cực đại (maximality), nghĩa là khi thêm các điểm lân cận vào lớp C điều kiện (1) vẫn được thoả mãn. (3) C có tính chất liên thông (connectivity), nghĩa là với mỗi cặp điểm (a, b) thuộc lớp luôn tồn tại một đường đi qua các ô lưới đã sử dụng nối giữa a và b. Hình 2.10: Phân bố khoảng cách mong đợi và khoảng cách quan sát của lớp 1 trong hình 2.8 2.2.2. Thuật toán DBCLASD Dựa vào lý thuyết đã trình bày ở trên, trong phần này chúng ta sẽ tiến hành xây dựng thuật toán phân lớp dựa vào sự phân bố khoảng cách trong cơ sở dữ liệu không gian. DBCLASD là thuật toán tăng dần nghĩa là việc xác định một điểm thuộc lớp chỉ dựa vào những điểm đã được xử lý mà không phải dựa vào toàn bộ lớp hoặc cả cơ sở dữ liệu. 2.3. Thuật toán DENCLUE Hầu hết các giải thuật phân nhóm đều gặp phải vấn đề về tốc độ tính toán và độ chính xác của kết quả. Nhiễu (noise) thường xuất hiện trong các cơ sở dữ liệu không gian đa chiều, lớn và là nguyên nhân chính ảnh hưởng đến tốc độ tính toán và kết quả thu được. Vì vậy, để giải quyết các vấn đề trên, giải thuật DENCLUE (DENsity based CLUstEring) được đề xuất bởi Hinneburg và Keim năm 1998 được đưa ra. 10 2.3.1. Một số định nghĩa Định nghĩa 10: Hàm ảnh hưởng và hàm mật độ Cho x, y là hai đối tượng trong không gian d chiều ký hiệu là Fd, hàm ảnh hưởng của y lên x được xác định: f By : F d  R0 được định nghĩa trên hàm ảnh hưởng cơ sở f B: f By ( x)  f B ( x, y) - Hàm mật độ (density function) được xác định là tổng của các hàm ảnh hưởng của toàn bộ điểm dữ liệu. Giả sử có N đối tượng dữ liệu được thể hiện bằng một tập N các vecto x D d D={x1, x2,..., xN)  F , hàm mật độ của một điểm x được xác định như sau: f B ( x)   f B i ( x) i 1 Định nghĩa 11: Gradient N Gradient của một hàm f BD (x) được định nghĩa là: f BD ( x)   ( xi  x). f Bx ( x) i i 1 Định nghĩa 12: Điểm hút mật độ (density-attractor). - Một điểm x*Fd được gọi là một điểm hút mật độ đối với một hàm ảnh hưởng nếu như x* là cực đại địa phương của hàm mật độ f BD Định nghĩa 13: Lớp với tâm xác định (Center- Defined Cluster). Lớp với tâm xác định với hai tham số ,  đối với một điểm hút x* là một tập con C  D với x  C là điểm hút mật độ bởi x* và f BD ( x * )   . Định nghĩa 14: Lớp với hình dạng bất kì (Arbitrary-Shape Cluster). Một lớp dạng bất kì với hai tham số ,  cho tập các điểm hút mật độ X là một tập C  D thoã mãn: 1) x  C, x*  X: f BD ( x * )   , x là điểm được hút mật độ bởi x* 2) x1* , x 2*  X :  một đường P  Fd từ x1* đến x 2* với p  P: f BD ( p)   2.3.2. Những tính chất của phương pháp DENCLUE a. Tính tổng quát DENCLUE được mô tả như là phương pháp tổng quát của các phương pháp phân nhóm khác nhau như: Phương pháp phân nhóm theo phân hoạch, phương pháp phân nhóm theo thứ bậc, phương pháp phân nhóm dựa vào tính địa phương. b. Nhiễu bất biến (noise invariance) Giả sử D  Fd là một tập dữ liệu và DSD không gian dữ liệu (data space). Khi đó D bao gồm các nhóm (clusters) và những dữ liệu nhiễu (noise) và có thể biểu diễn bởi: D = DC  DN với DC gồm các nhóm và DN là nhiễu. Xét X = x1* , x 2* ,...x k* , là tập điểm hút mật độ   * * * được sắp xếp theo thứ tự thuộc D với hai tham số (, ) và XC =  x1 , x 2 ,..., x k  là các điểm  hợp. Giả sử ||S|| là số hút mật độ cho DC với (, c) với  và c được chọn một cách thích phần tử của S, ta có bổ đề sau: Bổ đề 3. Nhiễu bất biến (Noise - invariance) Số điểm hút mật độ của D và DC là như nhau và khả năng những điểm hút mật độ còn lại là đồng nhất với 1khi ||DN|| . Một cách hình thức: ||X|| = ||XC|| và   X  lim  P( d ( xi* , xi* )  0)   1 D N   i 1  11 2.3.3. Thuật toán DENCLUE Để có được một cách phân nhóm tốt, chúng ta phải tìm ra một hàm ảnh hưởng và các điểm hút mật độ tốt. a. Hàm mật độ địa phƣơng (Local Density Function) Một hàm mật độ địa phương là một xấp xỉ của hàm mật độ. Ý tưởng này là chỉ chú ý đến ảnh hưởng của những điểm ở gần và không quan tâm đến sự ảnh hưởng của những điểm ở xa. Định nghĩa 15. Hàm mật độ địa phương (local density function) fˆ D ( x)  f xi B xi near( x ) ( x) Gradient của hàm mật độ địa phương được định nghĩa tương tự như trong định nghĩa 11. Tiếp theo chúng ta sẽ định nghĩa near = k là một điểm giới hạn lỗi cho một hàm mật độ địa phương f D ( x) . Bổ đề 4. Giới hạn lỗi (error bound) Nếu điểm xi  D: d(xi, x) > k bị bỏ đi thì giới hạn lỗi (error bound) sẽ là error  e  d ( xi , x ) 2 2 2 xi D:d ( xi , x )  k  || {xi  D | d ( xi , x)  k } || .e  k2 2 b. Thuật toán DENCLUE Thuật toán DENCLUE gồm 2 bước. Bước một gọi là bước chuẩn bị. Bước 1: Việc chia nhỏ miền dữ liệu được thực hiện như sau: Chia miền dữ liệu đa chiều của chúng ta ra thành những miền đa chiều nhỏ với độ dài của cạnh là 2. 31 33 34 19 13 15 7 1 36 29 30 23 24 16 12 3 6 Hình 2.11: Ví dụ một cách chia và đánh số trong không gian hai chiều Bước 2: Bước tiếp theo của thuật toán là bước phân nhóm. Những khối với mật độ cao cùng với những khối liên thông với khối mật độ cao mới được xét đến khi xác định lớp. Tập con này của Cp được xác định như sau: Cr = Csp  { c  Cpcs  Csp và  connection (c, cs)} 12 Sử dụng cấu trúc dữ liệu trong bước 1, ta có thể tính toán một cách hiệu quả hàm mật độ địa phương f D ( x) . Với mỗi x  c và c, c1  Cr , xét tập near(x) = {xic1 d(mean(c1,x)  k và connection(c1, c)). 2.4. Kết luận Trong chương này, tìm hiểu một số thuật toán phân nhóm cơ bản dựa vào mật độ phân bố dữ liệu trong không gian như DBSCAN, DBCLASD và DENCLUE. Các thuật toán này dựa vào ý tưởng là các điểm trong một lận cận phải vượt qua một ngưỡng nào đó. Đây là một trong các thuật toán tiêu biểu và có hiệu quả đối các dữ liệu không gian có hình dạng tuỳ ý và tồn tại nhiễu. Chƣơng 3. CÁC GIẢI THUẬT PHÂN NHÓM TRÊN CƠ SỞ DỮ LIỆU KHÔNG GIAN LỚN 3.1. Một số khái niệm cần thiết khi tiếp cận phân nhóm dữ liệu 3.1.1. Phân loại các kiểu dữ liệu Cho một CSDL D chứa n đối tượng trong không gian k chiều trong đó x, y, z là các đối tượng thuộc D: x = (x1, x2,.., xk); y = (y1, y2,.., yk); z = (z1, z2,.., zk), trong đó xi, yi, zi với i = 1…k là các đặc trưng hoặc thuộc tính tương ứng của các đối tượng x, y, z. 3.1.2. Độ đo tương tự và phi tương tự Để phân nhóm, người ta phải đi tìm cách thích hợp để xác định “khoảng cách” giữa các đối tượng, hay là phép đo tương tự dữ liệu. 1. Không gian metric Tất cả các độ đo dưới đây được xác định trong không gian độ đo metric. Hình 3.1: Minh họa số đo chiều rộng, chiều cao một đối tượng (phụ thuộc vào scaling khác nhau dẫn đến phân nhóm khác nhau) 2. Thuộc tính khoảng cách Một thành phần quan trọng trong thuật toán phân nhóm là phép đo khoảng cách giữa hai điểm dữ liệu. Nếu thành phần của vectơ thể hiện dữ liệu thuộc trong cùng một đơn vị giống nhau thì nó tồn tại khoảng cách Euclidean có thể xác định được nhóm dữ liệu tương tự. - Khoảng cách Minkowski nhƣ sau: 13 1/ q  n  d(x, y) =   | xi  yi |q   i 1  - Khoảng cách Euclidean đƣợc định nghĩa nhƣ sau: n d(x, y) =  (x  y ) i 1 i 2 i Là khoảng cách giữa hai đối tượng trong trường hợp đặc biệt q = 2. - Khoảng cách Manhattan: n d(x, y) =  i 1 xi  yi Là khoảng cách trung bình giữa hai đối tượng trong trường hợp đặc biệt q = 1. - Khoảng cách Chebychev: d(x, y) = Max in 1 |xi - yi| Hình 3.2: Khoảng cách Euclidean 3.2. Thuật toán K-MEANS Thuật toán này dựa trên độ đo khoảng cách của các đối tượng dữ liệu đến phần tử là trung tâm của nhóm chứa nó. Hình 3.3: Các thiết lập để xác định ranh giới các nhóm ban đầu Giải thuật xử lý như sau: Trước tiên nó lựa chọn ngẫu nhiên k đối tượng, mỗi đối tượng đại diện cho một trung bình nhóm hay tâm nhóm. Bình phương sai số thường dùng làm hàm tiêu chuẩn hội tụ, định nghĩa như sau:   k E= i 1 xCi x  mi 2 Với x là điểm trong không gian đại diện cho đối tượng cho trước, mi là trung bình nhóm Ci (x và mi đều là đa chiều). Tiêu chuẩn này cố gắng cho kết quả k nhóm càng đặc biệt, càng riêng biệt càng tốt. 14 Hình 3.4: Tính toán trọng tâm của các nhóm mới Thuật toán K-Means bao gồm các bƣớc cơ bản sau:   k Đầu vào: Số nhóm k và hàm E E = i 1 x  mi xCi 2 Đầu ra: Các nhóm C[i] (1 ≤ i ≤ k) với hàm tiêu chuẩn E đạt giá trị tối thiểu Begin Bƣớc 1: Khởi tạo k Chọn ngẫu nhiên k tâm mi  m j  j 1 ban đầu trong không gian Rd (d là số chiều của dữ liệu). Mỗi nhóm được đại diện bằng các tâm của nhóm Bƣớc 2: Tính toán khoảng cách  x m  n D kj1 i 1 i 2 j Đối với mỗi điểm xi (1 ≤ i ≤ n), tính toán khoảng cách của nó tới mỗi trọng tâm mj (1 ≤ j ≤ k). Sau đó tìm trọng tâm gần nhất đối với mỗi điểm và nhóm chúng vào các nhóm gần nhất. Bƣớc 3: Cập nhật lại trọng tâm Đối với mỗi 1≤ j ≤ k, cập nhật trọng tâm nhóm mj bằng cách xác định trung bình cộng các vectơ đối tượng dữ liệu. Bƣớc 4: Gán lại các điểm gần trung tâm nhóm mới Nhóm các đối tượng vào nhóm gần nhất dựa trên trọng tâm của nhóm. Điều kiện dừng: Lặp lại các bước 2 và 3 cho đến khi các trọng tâm của nhóm không thay đổi. End. Ví dụ: Giả sử có một tập đối tượng được định vị trong hệ trục toạ độ X, Y. Cho: k = 3 tức người dùng cần phân các đối tượng vào trong 3 nhóm. Theo giải thuật, ta chọn ngẫu nhiên 3 trung tâm nhóm ban đầu (Hình K-means bước 1). Sau đó, mỗi đối tượng được phân vào trong các nhóm đã chọn dựa trên tâm nhóm gần nhất (Hình K-means bước 2). Cập nhật lại các tâm (Hình K-means bước 3). Đó là giá trị trung bình của mỗi nhóm được tính toán lại dựa trên các đối tượng trong nhóm. 15 Hình 3.5: Ví dụ các bước của thuật toán K-means 3.3. Giải thuật DBSCAN DBSCAN có thể tìm ra các nhóm với hình thù bất kỳ, trong khi đó tại cùng một thời điểm ít bị ảnh hưởng bởi thứ tự của các đối tượng dữ liệu nhập vào. Độ phức tạp của DBSCAN là O(n2), nhưng nếu áp dụng chỉ số không gian để giúp xác định các láng giềng của một đối tượng dữ liệu thì độ phức tạp của DBSCAN đã được cải tiến là O(nlogn). Hình 3.6: Một số hình dạng khám phá bởi phân nhóm dưa trên mật độ Các bước của thuật toán DBSCAN như sau: Bƣớc 1: Chọn một đối tượng p tuỳ ý Bƣớc 2: Lấy tất cả các đối tượng mật độ - đến được từ p với Eps và MinPts. 16 Bƣớc 3: Nếu p là điểm nhân thì tạo ra một nhóm theo Eps và MinPts. Bƣớc 4: Nếu p là một điểm biên, không có điểm nào là mật độ - đến được mật độ từ p và DBSCAN sẽ đi thăm điểm tiếp theo của tập dữ liệu. Bƣớc 5: Quá trình tiếp tục cho đến khi tất cả các đối tượng được xử lý. Hình 3.7: Thuật toán DBSCAN 3.4. Kết luận Chương này trình bày vắn tắt về các giải thuật trong phân nhóm dữ liệu, trong đó đi sâu vào tìm hiểu về 2 giải thuật toán phân nhóm dữ liệu điển hình: K-MEANS, DBSCAN. Chương 4. XÁC ĐỊNH THAM SỐ, CÀI ĐẶT THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ 4.1. Môi trƣờng thử nghiệm Thành phần Chỉ số CPU RAM HDD Hệ điều hành Intel core i3-2330M 2.20GHz 2G 500GB Windows 7 Professional Hình 4.1: Môi trường thử nghiệm 4.2. Công cụ thử nghiệm Để tiến hành thử nghiệm, Ngôn ngữ lựa chọn để cài đặt thuật toán là ngôn ngữ C++ bởi đây là một ngôn ngữ có cấu trúc hỗ trợ nhiều kỹ thuật cho phép viết cài đặt các thuật toán tối ưu và hiệu quả. 4.3. Xác định tham số Đối với hầu hết các thuật toán có tham số đầu vào (như DBSCAN, DENCLU,…), chất lượng của kết quả phân nhóm phụ thuộc vào sự lựa chọn thích hợp các tham số đầu vào. 4.3.1. Xác định tham số cho thuật toán DBSCAN Để xác định 2 tham số Eps và MinPts cho tập dữ liệu vào, chúng ta xác định 2 tham số Eps và MinPts cho lớp có mật độ ít nhỏ nhất (“thinnest”) trong cơ sở dữ liệu dựa vào heuristic. Hình 4.2. Đồ thị khoảng cách với k = 4. Dựa vào đồ thị khoảng cách đó ta có thể đưa ra được khoảng cách Eps một cách chính xác Ví dụ: Cho tập dữ liệu, mỗi điểm dữ liệu được biểu diễn bởi toạ độ (x,y) như hình 4.3.