Luận văn Nghiên cứu một số kỹ thuật lấy tin tự động trên internet

dựa trên các mẫu duyệt để tìm ra sự liên quan giữa người dùng Web và các hành vi của họ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19 - Khai phá cấu trúc Web: WWW là hệ thống thông tin toàn cầu, bao gồm tất cả các Website. Mỗi một trang có thể được liên kết đến nhiều trang. Các siêu liên kết thay đổi chứa đựng ngữ nghĩa chủ đề của trang. Một siêu liên kết trỏ tới một trang Web khác có thể được xem như là một chứng thực của trang Web đó. Do đó, nó rất có ích trong việc sử dụng những thông tin ngữ nghĩa để lấy được thông tin quan trọng thông qua hân tích liên kết giữa các trang Web. Mục tiêu của khai phá cấu trúc Web là để phát hiện thông tin cấu trúc về Web. Nếu như khai phá nội dung Web chủ yếu tập trung vào cấu trúc bên trong tài liệu thì khai phá cấu trúc Web cố gắng để phát hiện cấu trúc liên kết của các siêu liên kết ở mức trong của tài liệu. Dựa trên mô hình hình học của các siêu liên kết, khai phá cấu trúc Web sẽ phân loại các trang Web, tạo ra thông tin như độ tương tự và mối quan hệ giữa các Website khác nhau. Nếu trang Web được liên kết trực tiếp với trang Web khác thì ta sẽ muốn phát hiện ra mối quan hệ giữa các trang Web này. - Quá trình tìm kiếm và phân cụm tài liệu: Về cơ bản, quá trình phân cụm kết quả tìm kiếm sẽ diễn ra theo các bước: + Tìm kiếm trang Web từ các Website thoả mãn nội dung truy vấn. + Trích rút thông tin mô tả từ các trang và lưu trữ nó cùng với các URL tương ứng. + Sử dụng kỹ thuật phân cụm dữ liệu để phân cụm tự động các trang Web thành các cụm, sao cho các trang trong cụm "tương tự" về nội dung với nhau hơn các trang ngoài cụm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 20 Hình 1.4: Các bước phân cụm kết quả tìm kiếm trên Web - Tìm kiếm dữ liệu trên Web: Nhiệm vụ chủ yếu của giai đoạn này là dựa vào tập từ khoá tìm kiếm để tìm kiếm và trả về tập gồm toàn văn tài liệu, tiêu đề, mô tả tóm tắt, URL... tương ứng với các trang đó. - Tiền xử lý dữ liệu: Quá trình làm sạch dữ liệu và chuyển dịch các tài liệu thành các dạng biểu diễn dữ liệu thích hợp. - Chuẩn hoá văn bản: Đây là giai đoạn chuyển hoá văn bản thô về dạng văn bản sao cho việc xử lý sau này được dễ dàng, đơn giản, thuận tiện, chính xác so với việc xử lý trực tiếp trên văn bản thô mà ảnh hưởng ít đến kết quả xử lý. - Xoá bỏ từ dừng: Trong văn bản có những từ mang ít thông tin quan trọng trong quá trình xử lý, những từ có tần số xuất hiện thấp, những từ xuất hiện với tần số lớn nhưng không quan trọng trong quá trình xử lý đều được loại bỏ. Theo một số nghiên cứu gần đây cho thấy việc loại bỏ các từ dừng có thể giảm bớt được khoảng 20 - 30% tổng số từ trong văn bản. - Kết hợp các từ có cùng gốc: Hầu hết trong các ngôn ngữ đều có rất nhiều các từ có chung nguồn gốc với nhau, chúng mang ý nghĩa tương tự nhau, do đó để giảm bớt số chiều trong biểu diễn văn bản, ta sẽ kết hợp với Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21 các từ có cùng gốc thành một từ. Ví dụ trong tiếng Anh từ user, users, used, using có cùng từ gốc và sẽ được quy về use. - Xây dựng từ điển: Việc xây dựng từ điển là một công việc rất quan trọng trong quá trình vector hoá văn bản, từ điển sẽ gồm các từ/ cụm từ riêng biệt trong toàn bộ tập dữ liệu. Từ điển sẽ gồm một bảng các từ, chỉ số của nó trong từ điển và được sắp xếp theo thứ tự. - Tách từ, số hoá văn bản và biểu diễn tài liệu: Tách từ là công việc hết sức quan trọng trong việc biểu diễn văn bản, quá trình tách từ, vector hoá tài liệu là quá trình tìm kiếm các từ và thay thế nó bởi chỉ số của từ đó trong từ điển. - Phân cụm tài liệu: Sau khi đã tìm kiếm, trích rút dữ liệu, tiền xử lý và biểu diễn văn bản chúng ta sử dụng kỹ thuật phân cụm để phân cụm tài liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22 Chương 2: MỘT SỐ THUẬT TOÁN PHÂN CỤM TÀI LIỆU 2.1. Phân cụm dữ liệu không gian và các tiếp cận Các kỹ thuật áp dụng để giải quyết vấn đề phân cụm dữ liệu đều hướng tới hai mục tiêu chung: Chất lượng của các cụm khám phá được và tốc độ thực hiện của thuật toán. Hiện nay, các kỹ phân cụm dữ liệu có thể phân loại theo các cách tiếp cận chính [5]: 2.1.1 Phân cụm phân hoạch Phương pháp phân cụm phân hoạch nhằm phân chia một tập dữ liệu có n phần tử cho trước thành k nhóm dữ liệu sao cho: mỗi phần tử dữ liệu chỉ thuộc về một nhóm dữ liệu và mỗi nhóm dữ liệu có tối thiểu một phần tử dữ liệu. Các thuật toán phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục cho vấn đề Phân cụm dữ liệu, do nó phải tìm kiếm tất cả các cách phân hoạch có thể được. Chính vì vậy, trên thực tế người ta thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lượng của các cụm cũng như để hướng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu. Với chiến lược này, thông thường người ta bắt đầu khởi tạo một phân hoạch ban đầu cho tập dữ liệu theo phép ngẫu nhiên hoặc theo heuristic, và liên tục tinh chỉnh nó cho đến khi thu được một phân hoạch mong muốn, thoả mãn ràng buộc cho trước. Các thuật toán phân cụm phân hoạch cố gắng cải tiến tiêu chuẩn phân cụm, bằng cách tính các giá trị đo độ tương tự giữa các đối tượng dữ liệu và sắp xếp các giá trị này, sau đó thuật toán lựa chọn một giá trị trong dãy sắp xếp sao cho hàm tiêu chuẩn đạt giá trị tối thiểu. Như vậy, ý tưởng chính của thuật toán phân cụm phân hoạch tối ưu cục bộ là sử dụng chiến lược ăn tham (Greedy) để tìm kiếm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 nghiệm. Một số thuật toán phân cụm phân hoạch điển hình như k-means, PAM, CLARA, CLARANS… sẽ được trình bày chi tiết ở những chương sau. 2.1.2 Phân cụm dữ liệu phân cấp Phân cụm phân cấp sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng hình cây, cây phân cấp này được xây dựng theo kỹ thuật đệ quy. Cây phân cụm có thể được xây dựng theo hai phương pháp tổng quát: phương pháp dưới lên (Bottom up) và phương pháp trên xuống (Top down) [5]. Phương pháp “dưới lên” (Bottom up): Phương pháp này bắt đầu với mỗi đối tượng được khởi tạo tương ứng với các cụm riêng biệt, sau đó tiến hành nhóm các đối tượng theo một độ đo tương tự (như khoảng cách giữa hai trung tâm của hai nhóm), quá trình này được thực hiện cho đến khi tất cả các nhóm được hòa nhập vào một nhóm (mức cao nhất của cây phân cấp) hoặc cho đến khi các điều kiện kết thúc thỏa mãn. Như vậy, cách tiếp cận này sử dụng chiến lược ăn tham trong quá trình phân cụm. Ví dụ: Dùng phương pháp "dưới lên" để phân cụm cho tập dữ liệu S= {a, b, c, d, e}. Các bước thực hiện phân cụm được diễn tả như sau : Bước 0: Mỗi đối tượng dữ liệu được gán cho mỗi cụm tương ứng, đồng thời xác định tâm D cho mỗi cụm, và tính độ tương tự cho các cặp cụm dữ liệu trên bằng cách xác định độ tương tự giữa cặp tâm của chúng. Như vậy ta sẽ có các cụm ban đầu là {a}, {b}, {c}, {d}, {e}. Bước 1: Xác định ngưỡng µ, các cặp cụm có độ tương tự bé hơn hoặc bằng ngưỡng µ thì được gộp vào một cụm. Các cặp cụm dữ liệu có độ tương tự lớn hơn µ thì xếp vào các cụm khác nhau. Trong thí dụ này chỉ có {a} và {b} là được gộp vào thành một cụm lớn hơn là {a, b}. Các cụm thu được sau bước này là: {a, b}, {c}, {d}, {e}. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24 Bước 2: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1, sau bước này ta gộp cụm {d}, {e} thành {d, e}. Các cụm thu được là {a, b}, {c}, {d, e}. Bước 3: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1, sau bước này ta gộp cụm {c} với {d, e} thành {c, d, e}. Các cụm thu được là {a, b}, {c, d, e}. Bước 4: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1, sau bước này ta gộp cụm hai cụm {c, d, e} với {a, b} thành {a, b, c, d, e}. Tuy nhiên, trong quá trình trên chúng ta có thể dừng ở một bước bất kỳ khi mà việc phân cụm đáp ứng tốt nhất các yêu cầu đã đặt ra. Các bước thực hiện trên được mô tả trực quan như hình 2.1 dưới đây. Hình 2.1: Phân cụm phân cấp theo phương pháp “dưới lên”-Bottom Up Phương pháp “trên xuống” (Top Down): Bắt đầu với trạng thái là tất cả các đối tượng được xếp trong cùng một cụm. Mỗi vòng lặp thành công, một cụm được tách thành các cụm nhỏ hơn theo giá trị của một phép đo độ tương tự nào đó cho đến khi mỗi đối tượng là một cụm, hoặc cho đến khi điều kiện dừng thỏa mãn. Cách tiếp cận này sử dụng chiến lược chia để trị trong quá trình phân cụm. Ví dụ: Dùng phương pháp "dưới lên" để phân cụm cho tập dữ liệu S= {a, b, c, d, e}. Các bước thực hiện phân cụm được diễn tả như sau: Bước 0 Bước 1 Bước 2 Bước 3 Bước 4 b d c e a a b d e c d e a b c d e Bottom up Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 Bước 0: Các đối tượng dữ liệu ban đầu được xếp vào một cụm, ta thu được cụm {a, b, c, d, e}. Tính độ tương tự giữa các đối tượng dữ liệu trong cụm {a, b, c, d, e}. Bước 1: Xác định ngưỡng µ , cụm ban đầu được tách ra thành các cụm sao cho các đối tượng dữ liệu trong mỗi cụm con tách ra có độ tương tự bé hơn hoặc bằng µ Sau bước này thì cụm {a, b, c, d, e} chia thành hai cụm {a, b} và {c, d, e}. Bước 2: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1 cho từng cụm con. Với ngưỡng µ, chỉ có cụm con {c, d, e} được tách ra thành hai cụm con lần lượt là {c} và {d, e}. Các cụm thu được sau bước này là {a, b}, {c}, {d, e}. Bước 3: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1 cho các cụm đã thu được ở bước 2, ở đây chỉ có cụm {d, e} được chia thành 2 cụm con {d}, {e}. Các cụm thu được sau bước này là {a, b}, {c}, {d}, {e}. Bước 4: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1 cho cụm {a, b} và sau bước này ta thu được các cụm: {a}, {b}, {c}, {d}, {e}. Tuy nhiên trong quá trình trên chúng ta có thể dừng ở một bước bất kỳ khi mà việc phân cụm đáp ứng tốt nhất các yêu cầu đã đặt ra. Các bước thực hiện trên được mô tả trực quan như hình 2.2 dưới đây: Hình 2.2 : Phân cụm phân cấp theo phương pháp “trên xuống”-Top Down B Bước 3 Bước 2 Bước 1 Bước 0 b d c e a a b d e c d e a b c d e Top Down Bước 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 Thực tế áp dụng, có nhiều trường hợp người ta kết hợp cả hai phương pháp phân cụm phân hoạch và phương phân cụm phân cấp, nghĩa là kết quả thu được của phương pháp phân cấp có thể cải tiến thông quan bước phân cụm phân hoạch. Phân cụm phân hoạch và phân cụm phân cấp là hai phương pháp Phân cụm dữ liệu cổ điển, hiện nay đã có nhiều thuật toán cải tiến dựa trên hai phương pháp này đã được áp dụng phổ biến trong Data Mining. 2.1.3 Phân cụm dữ liệu dựa trên mật độ Phương pháp này nhóm các đối tượng theo hàm mật độ xác định. Mật độ được định nghĩa như là số các đối tượng lân cận của một đối tượng dữ liệu theo một ngưỡng nào đó. Trong cách tiếp cận này, khi một cụm dữ liệu đã xác định thì nó tiếp tục được phát triển thêm các đối tượng dữ liệu mới miễn là số các đối tượng lân cận của các đối tượng này phải lớn hơn một ngưỡng đã được xác định trước. Phương pháp phân cụm dựa vào mật độ của các đối tượng để xác định các cụm dữ liệu có thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ. Tuy vậy, việc xác định các tham số mật độ của thuật toán rất khó khăn, trong khi các tham số này lại có tác động rất lớn đến kết quả phân cụm dữ liệu. Hình 2.3 dưới đây là một minh hoạ về các cụm dữ liệu với các hình thù khác nhau dựa trên mật độ được khám phá từ 3 Cơ sở dữ liệu khác nhau. Hình 2.3 : Một số hình dạng cụm dữ liệu khám phá được bởi kỹ thuật Phân cụm dữ liệu dựa trên mật độ CSDL 1 CSDL 2 CSDL 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 Một số thuật toán Phân cụm dữ liệu dựa trên mật độ điển hình như DBSCAN, OPTICS, DENCLUE… sẽ được trình bày chi tiết trong phần tiếp theo. 2.1.8 Phân cụm dữ liệu dựa trên lưới Kỹ thuật phân cụm dựa trên mật độ không thích hợp với dữ liệu nhiều chiều, để giải quyết cho đòi hỏi này, người ta đã dử dụng phương pháp phân cụm dựa trên lưới. Đây là phương pháp dựa trên cấu trúc dữ liệu lưới để Phân cụm dữ liệu, phương pháp này chủ yếu tập trung áp dụng cho lớp dữ liệu không gian [5]. Thí dụ như dữ liệu được biểu diễn dưới dạng cấu trúc hình học của đối tượng trong không gian cùng với các quan hệ, các thuộc tính, các hoạt động của chúng. Mục tiêu của phương pháp này là lượng hoá tập dữ liệu thành các ô (Cell), các cell này tạo thành cấu trúc dữ liệu lưới, sau đó các thao tác Phân cụm dữ liệu làm việc với các đối tượng trong từng Cell này. Cách tiếp cận dựa trên lưới này không di chuyển các đối tượng trong các cell mà xây dựng nhiều mức phân cấp của nhóm các đối tượng trong một cell. Trong ngữ cảnh này, phương pháp này gần giống với phương pháp phân cụm phân cấp nhưng chỉ có điều chúng không trộn các Cell. Do vậy các cụm không dựa trên độ đo khoảng cách (hay còn gọi là độ đo tương tự đối với các dữ liệu không gian) mà nó được quyết định bởi một tham số xác định trước. Ưu điểm của phương pháp Phân cụm dữ liệu dựa trên lưới là thời gian xử lý nhanh và độc lập với số đối tượng dữ liệu trong tập dữ liệu ban đầu, thay vào đó là chúng phụ thuộc vào số cell trong mỗi chiều của không gian lưới. Một thí dụ về cấu trúc dữ liệu lưới chứa các cell trong không gian như hình 2.4 sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 Hình 2.4 : Mô hình cấu trúc dữ liệu lưới Một số thuật toán Phân cụm dữ liệu dựa trên cấu trúc lưới điển hình như: STING, WAVECluster, CLIQUE… 2.1.9 Phân cụm dữ liệu dựa trên mô hình Phương pháp này cố gắng khám phá các phép xấp xỉ tốt của các tham số mô hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử dụng chiến lược phân cụm phân hoạch hoặc chiến lược phân cụm phân cấp, dựa trên cấu trúc hoặc mô hình mà chúng giả định về tập dữ liệu và cách mà chúng tinh chỉnh các mô hình này để nhận dạng ra các phân hoạch. Phương pháp Phân cụm dữ liệu dựa trên mô hình cố gắng khớp giữa dữ liệu với mô hình toán học, nó dựa trên giả định rằng dữ liệu được tạo ra bằng hỗn hợp phân phối xác suất cơ bản. Các thuật toán phân cụm dựa trên mô hình có hai tiếp cận chính: Mô hình thống kê và Mạng Nơron. Phương pháp này gần giống với phương pháp dựa trên mật độ, bởi vì chúng phát triển các cụm riêng biệt nhằm cải tiến các mô hình đã được xác định trước đó, nhưng đôi khi nó không bắt đầu với một số cụm cố định và không sử dụng cùng một khái niệm mật độ cho các cụm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 2.1.10 Phân cụm dữ liệu có ràng buộc Sự phát triển của phân cụm dữ liệu không gian trên Cơ sở dữ liệu lớn đã cung cấp nhiều công cụ tiện lợi cho việc phân tích thông tin địa lý, tuy nhiên hầu hết các thuật toán này cung cấp rất ít cách thức cho người dùng để xác định các ràng buộc trong thế giới thực cần phải được thoả mãn trong quá trình Phân cụm dữ liệu. Để phân cụm dữ liệu không gian hiệu quả hơn, các nghiên cứu bổ sung cần được thực hiện để cung cấp cho người dùng khả năng kết hợp các ràng buộc trong thuật toán phân cụm [5]. 2.2. Phân cụm dữ liệu dựa vào thuật toán K-means 2.2.1. Tư tưởng thuật toán K-means là một trong số những phương pháp học không có giám sát cơ bản nhất thường được áp dụng trong việc giải các bài toán về phân cụm dữ liệu. Mục đích của thuật toán k-means là sinh ra k cụm dữ liệu {C1, C2, …,Ck} từ một tập dữ liệu chứa n đối tượng trong không gian d chiều Xi = (xi1, xi2, …, xid) ( ni ,1 ), sao cho hàm tiêu chuẩn [5]:    k i x iC mxE i1 2 đạt giá trị tối thiểu. Trong đó: mi là trọng tâm của cụm Ci, là khoảng cách giữa hai đối tượng [2]. Trọng tâm của một cụm là một véc tơ, trong đó giá trị của mỗi phần tử của nó là trung bình cộng của các thành phần tương ứng của các đối tượng véc tơ dữ liệu trong cụm đang xét. Tham số đầu vào của thuật toán là số cụm k, và tham số đầu ra của thuật toán là các trọng tâm của các cụm dữ liệu. Độ đo khoảng cách d giữa các đối tượng dữ liệu thường được sử dụng là khoảng cách Euclide, bởi vì đây là mô hình khoảng cách dễ để lấy đạo hàm và xác định các cực trị tối thiểu. Hàm tiêu chuẩn và độ đo khoảng cách có thể được xác định cụ thể hơn tuỳ vào ứng dụng hoặc các quan điểm của người dùng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 Để dễ hình dung về thuật toán k-means ta xét ví dụ đơn giản sau: Cho tập dữ liệu bao gồm có 15 phần tử thực trong không gian 1 chiều S= {1, 4, 8, 5, 10, 15, 16, 23, 25, 27, 13, 37, 2, 18, 20}, người ta cần phân cụm dữ liệu này ra thành 3 cụm (k=3) theo thuật toán k-means. Các bước thực hiện của thuật toán được trình bày như sau: Bước khởi tạo: chọn 3 tâm ngẫu nhiên CL1 = 8, CL2= 16, CL3= 23 Ta thu được phân hoạch ban đầu như sau: Cụm 1, với tâm là CL1, gồm có các phần tử: 1, 2, 4, 5, 8, 10 Cụm 2, với tâm là CL2, gồm có các phần tử: 13, 15, 16, 18 Cụm 3, với tâm là CL3, gồm có các phần tử: 23, 25, 27, 20, 37 (Ở đây độ đo tương tự giữa hai đối tượng được xác định bằng công thức: d(a, b)=|a-b|) Như vậy, ta có : E = {(1-8)2 + (2-8)2 + (4-8)2+ (5-8)2+ (8-8)2+ (10 - 8)2} + {(13-16)2 + (15-16)2 + (16-16)2+ (18-16)2}+ {(25-23)2 + (23-23)2 + (27- 23)2+ (37-23)2+ (20-23)2} = 353. Bước lặp thứ nhất: Cập nhật lại tâm mới: Cl1 = (1+2+4+5+8+10)/6 = 5; Tương tự ta có: CL2=13; CL3=26.4; Phân hoạch tương ứng với các tâm mới như sau: Cụm 1, với tâm là CL1 gồm có các phần tử: 1, 2, 4, 5, 8 Cụm 2, với tâm là CL2 gồm có các phần tử: 10, 13, 15, 16, 18 Cụm 3, với tâm là CL3 gồm có các phần tử: 23, 25, 27, 20, 37 Với phân hoạch này ta có giá trị hàm mục tiêu là: E= 249.2. Do giá trị của hàm mục tiêu này bé hơn sơ với trạng thái của nó trước đó nên ta có bước lặp thứ hai như sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 Bước lặp thứ hai: Cập nhật lại tâm mới: Cl1 = (1+2+4+5+8)/5 = 4; Tương tự ta có: CL2=14.4; CL3=26.4; Phân hoạch tương ứng với các tâm mới như sau: Cụm 1, với tâm là CL1 gồm có các phần tử: 1, 2, 4, 5, 8 Cụm 2, với tâm là CL2 gồm có các phần tử: 10, 13, 15, 16, 18, 20 Cụm 3, với tâm là CL3 gồm có các phần tử: 23, 25, 27, 37 Với phân hoạch này ta có giá trị hàm mục tiêu là: E= 224.8 Do giá trị của hàm mục tiêu này bé hơn sơ với trạng thái của nó trước đó nên ta có bước lặp thứ ba như sau: Bước lặp thứ ba: Cập nhật lại tâm mới: Cl1 = (1+2+4+5+8)/5 = 4; Tương tự ta có: CL2=15.33; CL3=28; Phân hoạch tương ứng với các tâm mới như sau: Cụm 1, với tâm là CL1, gồm có các phần tử: 1, 2, 4, 5, 8 Cụm 2, với tâm là CL2, gồm có các phần tử: 10, 13, 15, 16, 20 Cụm 3, với tâm là CL3, gồm có các phần tử: 23, 25, 27, 37 Với phân hoạch này ta có giá trị hàm mục tiêu là: E= 209.33 Chúng ta thực hiện thuật toán với bước tiếp theo do giá trị của hàm mục tiêu thu được vẫn bé hơn giá trị trước đó. Ở bước tiếp theo ta thấy thuật tóan sẽ dừng do tâm mới cập nhật sẽ không bị thay đổi. Như vậy, kết quả phân cụm ta sẽ xác định giá trị của ba tâm như sau: CL1= 4; CL2=15.33; CL3=28; 2.2.2 Mô tả thuật toán Input: K, và dữ liệu về n mẫu của 1 Cơ sở dữ liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 Output: Một tập gồm K cluster sao cho cực tiểu về tổng sai-số vuông. Các bước thuật toán: Bước 1: Chọn ngẫu nhiên K mẫu vào K cluster. Coi tâm của cluster chính là mẫu có trong cluster. Bước 2: Tìm tâm mới của cluster. Bước 3: Gán các mẫu vào từng cluster sao cho khoảng cách từ mẫu đó đến tâm của cluster đó là nhỏ nhất. Bước 4: Nếu các cluster không có sự thay đổi nào sau khi thực hiện bước 3 thì chuyển sang bước 5, ngược lại sang bước 2. Bước 5: Dừng thuật toán. Ví dụ: Trong không gian hai chiều, cho 12 điểm (n = 12) cần phân 12 điểm này thành hai cluster (k=2). Đầu tiên, chọn hai điểm ngẫu nhiên vào hai cluster (chọn 2 điểm màu đỏ: (1,3); (9,4)) Coi điểm (1,3) là tâm của cluster 1 và điểm (9,4) là tâm của cluster 2. Tính toán khoảng cách từ các điểm khác đến hai điểm này và gán được các điểm còn lại này vào một trong hai cluster, những điểm có màu xanh lơ vào cluster 1, những điểm có màu xanh đậm vào cluster 2. Hiệu chỉnh lại tâm của hai cluster, điểm màu đỏ là tâm mới của hai cluster. Tính lại các khoảng cách các điểm đến tâm mới và gán lại các điểm này. Tiếp tục hiệu chỉnh lại tâm của hai cluster. Rồi, lặp lại cho đến khi không còn sự thay đổi nữa thì dừng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 Hình 2.5: Minh họa thuật toán K-means Độ phức tạp của thuật toán này là O(tKn). Trong đó n là số mẫu trong Cơ sở dữ liệu, K là số cluster, t là số lần lặp. Thông thường t, k << n. Nên thuật toán này có hiệu quả tương đối với các Cơ sở dữ liệu lớn [2]. 2.3 Phân cụm dữ liệu dựa vào thuật toán K-medios 2.3.1. Tư tưởng thuật toán Để tìm ra k cụm với n đối tượng thì k-medoids chọn ngẫu nhiên k đối tượng vào k cụm, coi mỗi đối tượng này là tâm của cụm. Phân bổ các đối tượng còn lại vào cụm mà sự khác nhau của nó với đối tượng tâm của cụm là gần nhất. Sau đó lặp lại quá trình: Thay đổi đối tượng tâm của mỗi cụm sao cho chất lượng của cụm được cải thiện. Chất lượng của cụm được lượng giá bởi một hàm đo sự khác nhau giữa một đối tượng và đối tượng tâm của cụm chứa nó. Quá trình lặp cho đến khi không còn sự thay đổi nào về lực lượng cũng như hình dạng của các cụm [2]. Để chọn một đối tượng không là đối tượng tâm Orandom thay thế tốt cho một đối tượng tâm Oj thì mỗi đối tượng p xét theo 4 trường hợp sau đây: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 Trường hợp 1: p đang thuộc vào cụm có tâm là Oj (từ nay gọi là cụm Oj). Nếu Oj được thay thế bởi Orandom và p gần nhất với Oi (ij) thì p được gán lại vào Oi Trường hợp 2: p đang thuộc vào Oj. Nếu Oj được thay thế bởi Orandom và p gần nhất với Orandom thì p được gán lại vào Orandom. Trường hợp 3: p đang thuộc vào Oi (ij). Nếu Oj được thay thế bởi Orandom và p vẫn gần nhất với Oi thì không thay đổi gì cả. Tức là p vẫn thuộc Oi. Trường hợp 4: p đang thuộc vào Oi (ij). Nếu Oj được thay thế bởi Orandom và p gần nhất với Orandom thì p được gán lại vào Orandom. Hình 2.6: Các trường hợp đối với điểm p 2.3.2. Mô tả thuật toán Input: Số nguyên k và Cơ sở dữ liệu gồm n đối tượng cần phân cụm. Output: Một tập gồm k cụm mà tổng giá trị của sự khác nhau của tất cả các đối tượng đến đối tượng tâm của nhóm chứa nó là nhỏ nhất. Thuật toán: Bước 1: Chọn k đối tượng bất kì vào k cụm. Coi mỗi đối tượng này là tâm của nhóm. Bước 2: Lặp Bước 3: Gán mỗi đối tượng còn lại vào một cụm mà nó gần với đối tượng tâm của cụm nhất. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 Bước 4: Chọn ngẫu nhiên một đối tượng không là đối tượng tâm, Orandom. Bước 5: Tính lại giá trị, S, đối với việc đổi Oj với Orandom. Bước 6: Nếu S<0 thì đổi Oj với Orandom để tạo ra một tập với đối tượngtâm mới. Bước 7: Đến khi không có sự thay đổi nào nữa thì dừng. Ví dụ: Trong không gian hai chiều cho n = 10 điểm, cần chia thành k =2 cụm. Các bước thực hiện của thuật toán k-medoids được chỉ ra: Hình 2.7: Các bước thực hiện của k-medoids Đầu tiên, chọn hai điểm bất kì vào hai cụm (điểm màu xanh đậm), rồi xét các điểm còn lại và đưa chúng vào một trong hai cụm với điểm tâm lần lượt là hai điểm đã chọn ban đầu. Tiếp theo, chọn một điểm bất kì khác điểm tâm (điểm màu đỏ). Tính giá của phép chuyển đổi điểm tâm từ điểm màu xanh -> điểm màu đỏ. Nếu giá này chất lượng hơn thì coi điểm đỏ là tâm của cụm mới và thực lặp lại quá trình đó cho đến khi không còn sự thay đổi nào. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 2.3.3 Nhận xét: Thuật toán k-medoids mạnh hơn thuật toán k-means trong các trường hợp dữ liệu có nhiễu vì k-medoids chịu ảnh hưởng ít hơn của nhiễu và các giá trị chênh lệnh so với giá trị trung bình. Tuy nhiên cả hai thuật toán này đều yêu cầu đưa vào số lượng cụm k [2]. 2.4. Phân cụm dữ liệu dựa vào thuật toán BIRCH 2.4.1. Tư tưởng thuật toán BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies) là thuật toán phân cụm phân cấp sử dụng chiến lược phân cụm trên xuống (top down). Ý tưởng của thuật toán là không cần lưu toàn bộ các đối tượng dữ liệu của các cụm trong bộ nhớ mà chỉ lưu các đại lượng thống kê. Đối với mỗi dữ liệu, BIRCH chỉ lưu một bộ ba (n, LS, SS), trong đó n là số đối tượng trong cụm, LS là tổng các giá trị thuộc tính của các đối tượng trong cụm và SS là tổng bình phương của các giá trị thuộc tính của các đối tượng trong cụm. Các bộ ba này được gọi là các đặc trưng của cụm (Cluster Features - CF) và được lưu giữ trong một cây được gọi là cây CF (CF-tree). Người ta đã chứng minh rằng [5][10], các đại lượng thống kê chuẩn, như là độ đo khoảng cách, có thể xác định từ cây CF. Hình 2.8 dưới đây biểu thị một ví dụ về cây CF. Chúng ta thấy