Luận văn Khai phá dữ liệu Web bằng kỹ thuật phân cụm

âm. 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Om2 Om Op Oj 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Oj Om Op Om2 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 37 Hình 2.6. Trường hợp Cjmp= (Oj,Op)- d(Oj, Om,2) luôn âm - Kết hợp cả bốn trường hợp trên, tổng giá trị hoán chuyển Om bằng Op được xác định như sau: TCmp =  j jmpC . Thuật toán PAM gồm các bước thực hiện chính như sau: INPUT: Tập dữ liệu có n phần tử, số cụm k OUTPUT: k cụm dữ liệu sao cho chất lượng phân hoạch là tốt nhất. Bước 1: Chọn k đối tượng medoid bất kỳ; Bước 2: Tính TCmp cho tất cả các cặp đối tượng Om, Op. Trong đó Om là đối tượng medoid và Op là đối tượng không phải là modoid. Bước 3: Với mỗi cặp đối tượng Om và Op. Tính minOm, minOp, TCmp. Nếu TCmp là âm, thay thế Om bởi Op và quay lại bước 2. Nếu TCmp dương, chuyển sang bước 4. Bước 4: Với mỗi đối tượng không phải là medoid, xác định đối tượng medoid tương tự với nó nhất đồng thời gán nhãn cụm cho chúng. Hình 2.7. Thuật toán PAM Trong bước 2 và 3, có PAM phải duyệt tất cả k(n-k) cặp Om, Op. Với mỗi cặp, việc tính toán TCmp yêu cầu kiểm tra n-k đối tượng. Vì vậy, độ phức tạp tính toán của PAM là O(Ik(n-k)2), trong đó I là số vòng lặp. Như vậy, thuật toán PAM kém hiệu quả về thời gian tính toán khi giá trị của k và n là lớn. 0 1 2 3 4 5 6 7 8 9 1 0 0 1 2 3 4 5 6 7 8 9 1 0 Om2 Om Op Oj Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 38 2.1.3. Thuật toán CLARA CLARA (Clustering LARge Application) được Kaufman và Rousseeuw đề xuất năm 1990, thuật toán này nhằm khắc phục nhược điểm của thuật toán PAM trong trường hợp giá trị của k và n lớn. CLARA tiến hành trích mẫu cho tập dữ liệu có n phần tử và áp dụng thuật toán PAM cho mẫu này và tìm ra các các đối tượng medoid của mẫu này. Người ta thấy rằng, nếu mẫu dữ liệu được trích một cách ngẫu nhiên, thì các medoid của nó xấp xỉ với các medoid của toàn bộ tập dữ liệu ban đầu. Để tiến tới một xấp xỉ tốt hơn, CLARA đưa ra nhiều cách lấy mẫu rồi thực hiện phân cụm cho mỗi trường hợp này và tiến hành chọn kết quả phân cụm tốt nhất khi thực hiện phân cụm trên các mẫu này. Để cho chính xác, chất lượng của các cụm được đánh giá thông độ phi tương tự trung bình của toàn bộ các đối tượng dữ liệu trong tập đối tượng ban đầu. Kết quả thực nghiệm chỉ ra rằng, 5 mẫu dữ liệu có kích thước 40+2k cho các kết quả tốt. Các bước thực hiện của thuật toán CLARA như sau: INPUT: CSDL gồm n đối tượng, số cụm k. OUTPUT: k cụm dữ liệu 1. For i = 1 to 5 do Begin 2. Lấy một mẫu có 40 + 2k đối tượng dữ liệu ngẫu nhiên từ tập dữ liệu và áp dụng thuật toán PAM cho mẫu dữ liệu này nhằm để tìm các đối tượng medoid đại diện cho các cụm. 3. Đối với mỗi đối tượng Oj trong tập dữ liệu ban đầu, xác định đối tượng medoid tương tự nhất trong số k đối tượng medoid. 4. Tính độ phi tương tự trung bình cho phân hoạch các đối tượng dành ở bước trước, nếu giá trị này bé hơn giá trị tối thiểu hiện thời thì sử dụng giá trị này thay cho giá trị tối thiếu ở trạng thái trước, như vậy tập k đối tượng medoid xác định ở bước này là tốt nhất cho đến thời điểm hiện tại. End; Hình 2.8. Thuật toán CLARA Độ phức tạp tính toán của thuật toán là O(k(40+k)2 + k(n-k)), và CLARA có thể thực hiện đối với tập dữ liệu lớn. Chú ý đối với kỹ thuật tạo mẫu trong PCDL: kết quả phân cụm có thể không phụ thuộc vào tập dữ liệu khởi tạo nhưng nó chỉ đạt tối ưu cục bộ. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 39 2.1.4. Thuật toán CLARANS Thuật toán CLARANS (A Clustering Algorithm based on RANdomized Search) được Ng & Han đề xuất năm 1994, nhằm để cải tiến chất lượng cũng như mở rộng áp dụng cho tập dữ liệu lớn. CLARANS là thuật toán PCDL kết hợp thuật toán PAM với chiến lược tìm kiếm kinh nghiệm mới. Ý tưởng cơ bản của CLARANS là không xem xét tất cả các khả năng có thể thay thế các đối tượng tâm medoids bởi một đối tượng khác, nó ngay lập tức thay thế các đối tượng medoid này nếu việc thay thế có tác động tốt đến chất lượng phân cụm chứ không cần xác định cách thay thể tối ưu nhất. Một phân hoạch cụm phát hiện được sau khi thay thế đối tượng trung tâm được gọi là một láng giềng của phân hoạch cụm trước đó. Số các láng giềng được hạn chế bởi tham số do người dùng đưa vào là Maxneighbor, quá trình lựa chọn các láng giềng này là hoàn toàn ngẫu nhiên. Tham số Numlocal cho phép người dùng xác định số vòng lặp tối ưu cục bộ được tìm kiếm. Không phải tất các láng giềng được duyệt mà chỉ có Maxneighbor số láng giềng được duyệt. Một số khái niệm sử dụng trong thuật toán CLARANS được định nghĩa như sau: Giả sử O là một tập có n đối tượng và M là tập các đối tượng medoid, NMM là tập các đối tượng không phải medoid. Các đối tượng dữ liệu sử dụng trong thuật toán CLARANS là các khối đa diện. Mỗi đối tượng được diễn tả bằng một tập các cạch, mỗi cạnh được xác định bằng 2 đỉnh. Giả sử P R3 là một tập tất cả các điểm. Nói chung, các đối tượng ở đây là các đối tượng dữ liệu không gian và ta định nghĩa tâm của một đối tượng chính là trung bình cộng toán học của tất cả các đỉnh hay còn gọi là trọng tâm: Center: O  P Giả sử dist là một hàm khoảng cách, khoảng cách thường được chọn ở đây là khoảng cách Euclid: dist: P x PR0 + Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 40 Hàm khoảng cách dist có thể mở rộng cho các điểm của khối đa diện thông qua hàm tâm: dist: O x OR0 + sao cho dist (oi, oj) = dist (center(oi), center(oj)) Mỗi đối tượng được gán cho một tâm medoid của cụm nếu khoảng cách từ trọng tâm của đối tượng đó tới tâm medoid của nó là nhỏ nhất. Vì vậy, ta định nghĩa một tâm medoid như sau: medoid: OM Sao cho medoid (o) = mi, mi M, mj M: dist (o, mi) dist (o, mj), oO. Cuối cùng, ta định nghĩa một cụm với medoid mi tương ứng là một tập con các đối tượng trong O với medoid(o) = mi. Giả sử C0 là tập tất cả các phân hoạch của O. Hàm tổng để đánh giá chất lượng một phân hoạch được định nghĩa như sau: total_distance: C0R0 + sao cho total_distance(c) = dist (o, mi) với mi M, cluster(mi). Thuật toán CLARANS có thể được diễn tả như sau [10][19]: INPUT: Tập dữ liệu gồm n đối tượng, số cụm k, O, dist, numlocal, maxneighbor; OUTPUT: k cụm dữ liệu; For i=1 to numlocal do Begin Khởi tạo ngẫu nhiên k medois j = 1; while j < maxneighbor do Begin Chọn ngẫu nhiên một láng giềng R của S. Tính toán độ phi tương tự về khoảng cách giữa 2 láng giềng S và R. Nếu R có chi phí thấp hơn thì hoán đối R cho S và j=1 ngược lại j++; End; Kiểm tra khoảng cách của phân hoạch S có nhỏ hơn khoảng cách nhỏ nhất không, nếu nhỏ hơn thì lấy giá trị này để cập nhật lại khoảng cách nhỏ nhất và phân hoạch S là phân hoạch tốt nhất tại thời điểm hiện tại. End. Hình 2.9. Thuật toán CLARANS Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 41 Như vậy, quá trình hoạt động của CLARANS tương tự với quá trình hoạt động của thuật toán CLARA. Tuy nhiên, ở giai đoạn lựa chọn các trung tâm medoid cụm dữ liệu, CLARANS lựa chọn một giải pháp tốt hơn bằng cách lấy ngẫu nhiên một đối tượng của k đối tượng trung tâm medoid của cụm và cố gắng thay thế nó với một đối tượng được chọn ngẫu nhiên trong (n-k) đối tượng còn lại, nếu không có giải pháp nào tốt hơn sau một số cố gắng lựa chọn ngẫu nhiên xác định, thuật toán dừng và cho kết quả phân cụm tối ưu cục bộ. Trong trường hợp xấu nhất, CLARANS so sánh một đối tượng với tất các đối tượng Medoid. Vì vậy, độ phức tạp tính toán của CLARANS là O(kn2), do vậy CLARANS không thích hợp với tập dữ liệu lớn. CLARANS có ưu điểm là không gian tìm kiếm không bị giới hạn như đối với CLARA và trong cùng một lượng thời gian thì chất lượng của các cụm phân được là lớn hơn so với CLARA. 2.2. Phân cụm 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 “trên xuống” (Top down) và phương pháp “dưới lên” (Bottom up). Phương pháp 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 thoả 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. Phương pháp 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 thoả 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. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 42 Sau đây là minh họa chiến lược phân cụm phân cấp bottom up và Top down. Hình 2.10. Các chiến lược phân cụm phân cấp Trong 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 PCDL 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 KPDL. Một số thuật toán phân cụm phân cấp điển hình như CURE, BIRCH, Chemeleon, AGNES, DIANA,... 2.2.1. Thuật toán BIRCH BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies) do Tian Zhang, amakrishnan và Livny đề xuất năm 1996, là thuật toán phân cụm phân cấp sử dụng chiến lược 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 cụm dữ liệu, BIRCH chỉ lưu một bộ ba (n, LS, SS), với 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á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 CF=(n, LS, SS) (Cluster Features - CF) và được lưu giữ trong một cây được gọi là cây CF. Hình sau đây biểu thị một ví dụ về cây CF. Chúng ta thấy rằng, tất cả các nút 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 Bước 4 Bước 3 Bước 2 Bước 1 Bước 0 Bottom up Top Down Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 43 trong của cây lưu tổng các đặc trưng cụm CF của nút con, trong khi đó các nút lá lưu trữ các đặc trưng của các cụm dữ liệu. Hình 2.11. Cây CF được sử dụng bởi thuật toán BIRCH Cây CF là cây cân bằng, nhằm để lưu trữ các đặc trưng của cụm. Cây CF chứa các nút trong và nút lá. Nút trong lưu giữ tổng các đặc trưng cụm của các nút con của nó. Một cây CF được đặc trưng bởi hai tham số: - Yếu tố nhánh (B): Nhằm xác định số tối đa các nút con của mỗi nút trong của cây; - Ngưỡng (T): Khoảng cách tối đa giữa bất kỳ một cặp đối tượng trong nút lá của cây, khoảng cách này còn gọi là đường kính của các cụm con được lưu tại các nút lá. Hai tham số này có ảnh hưởng lớn đến kích thước của cây CF. Thuật toán BIRCH thực hiện qua giai đoạn sau: INPUT: CSDL gồm n đối tượng, ngưỡng T OUTPUT: k cụm dữ liệu Bước 1: Duyệt tất cả các đối tượng trong CSDL và xây dựng một cây CF khởi tạo. Một đối tượng được chèn vào nút lá gần nhất tạo thành cụm con. Nếu đường kính của cụm con này lớn hơn T thì nút lá được tách. Khi một đối tượng thích hợp được chèn CF1 child1 CF3 child3 CF2 child2 CF6 child6 CF1 child1 CF3 child3 CF2 child2 CF5 child5 CF1 CF2 CF6 prev next CF1 CF2 CF4 prev next B = 7 L = 6 Root Non-leaf node Leaf node Leaf node Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 44 vào nút lá, tất cả các nút trỏ tới gốc của cây được cập nhật với các thông tin cần thiết. Bước 2: Nếu cây CF hiện thời không có đủ bộ nhớ trong thì tiến hành xây dựng một cây CF nhỏ hơn bằng cách điều khiển bởi tham số T (vì tăng T sẽ làm hoà nhập một số các cụm con thành một cụm, điều này làm cho cây CF nhỏ hơn). Bước này không cần yêu cầu bắt đầu đọc dữ liệu lại từ đầu nhưng vẫn đảm bảo hiệu chỉnh cây dữ liệu nhỏ hơn. Bước 3: Thực hiện phân cụm: Các nút lá của cây CF lưu giữ các đại lượng thống kê của các cụm con. Trong bước này, BIRCH sử dụng các đại lượng thống kê này để áp dụng một số kỹ thuật phân cụm thí dụ như k-means và tạo ra một khởi tạo cho phân cụm. Bước 4: Phân phối lại các đối tượng dữ liệu bằng cách dùng các đối tượng trọng tâm cho các cụm đã được khám phá từ bước 3: Đây là một bước tuỳ chọn để duyệt lại tập dữ liệu và gán nhãn lại cho các đối tượng dữ liệu tới các trọng tâm gần nhất. Bước này nhằm để gán nhãn cho các dữ liệu khởi tạo và loại bỏ các đối tượng ngoại lai Hình 2.12. Thuật toán BIRCH Khi hòa nhập 2 cụm ta có CF=CF1+CF2= (n1+n2, LS1+LS2, SS1+SS2). Khoảng cách giữa các cụm có thể đo bằng khoảng cách Euclid, Manhatta,.... Ví dụ: ),LS(n,CF SS   , n là số đối tượng dữ liệu Hình 2.13. Ví dụ về kết quả phân cụm bằng thuật toán BIRCH Sử dụng cấu trúc cây CF làm cho thuật toán BIRCH có tốc độ thực hiện PCDL nhanh và có thể áp dụng đối với tập dữ liệu lớn, BIRCH đặc biệt hiệu quả khi áp dụng với tập dữ liệu tăng trưởng theo thời gian. BIRCH chỉ duyệt toàn bộ dữ liệu một lần với một lần quét thêm tuỳ chọn, nghĩa là độ phức tạp của nó là O(n) (n là số đối tượng dữ liệu). Nhược điểm của nó là chất lượng của các cụm được khám Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 45 phá không được tốt. Nếu BIRCH sử dụng khoảng cách Euclide, nó thực hiện tốt chỉ với các dữ liệu số. Mặt khác, tham số vào T có ảnh hưởng rất lớn tới kích thước và tính tự nhiên của cụm. Việc ép các đối tượng dữ liệu làm cho các đối tượng của một cụm có thể là đối tượng kết thúc của cụm khác, trong khi các đối tượng gần nhau có thể bị hút bởi các cụm khác nếu chúng được biểu diễn cho thuật toán theo một thứ tự khác. BIRCH không thích hợp với dữ liệu đa chiều. 2.2.2. Thuật toán CURE Việc chọn một cách biểu diễn cho các cụm có thể nâng cao chất lượng phân cụm. Thuật toán CURE (Clustering Using REpresentatives) được đề xuất bởi Sudipto Guha, Rajeev Rastogi và Kyuseok Shim năm 1998 [19] là thuật toán sử dụng chiến lược Bottom up của kỹ thuật phân cụm phân cấp. Thay vì sử dụng các trọng tâm hoặc các đối tượng tâm để biểu diễn cụm, CURE sử dụng nhiều đối tượng để diễn tả cho mỗi cụm dữ liệu. Các đối tượng đại diện cho cụm này ban đầu được lựa chọn rải rác đều ở các vị trí khác nhau, sau đó chúng được di chuyển bằng cách co lại theo một tỉ lệ nhất định. Tại mỗi bước của thuật toán, hai cụm có cặp đối tượng đại diện gần nhất sẽ được trộn lại thành một cụm. Với cách thức sử dụng nhiều hơn một điểm đại diện cho các cụm, CURE có thể khám phá được các cụm có các dạng hình thù và kích thước khác nhau trong CSDL lớn. Việc co các đối tượng đại diện lại có tác dụng làm giảm tác động của các phần tử ngoại lai. Vì vậy, CURE có khả năng xử lý đối với các phần tử ngoại lai. Hình sau thí dụ về các dạng và kích thước cụm dữ liệu được khám phá bởi CURE: Hình 2.14. Các cụm dữ liệu được khám phá bởi CURE Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 46 Để áp dụng với CSDL lớn, CURE sử dụng lấy mẫu ngẫu nhiên và phân hoạch. Mẫu dữ liệu được xác định ngẫu nhiên là phân hoạch đầu tiên, CURE tiến hành phân cụm trên mỗi phân hoạch. Quá trình này lặp lại cho đến khi ta thu được phân hoạch đủ tốt. Các cụm thu được sau đó lại được phân cụm nhằm để thu được các cụm con cần quan tâm. Thuật toán CURE được thực hiện qua các bước cơ bản như sau: Bước 1. Chọn một mẫu ngẫu nhiên từ tập dữ liệu ban đầu; Bước 2. Phân hoạch mẫu này thành nhiều nhóm dữ liệu có kích thước bằng nhau: Ý tưởng chính ở đây là phân hoạch mẫu thành p nhóm dữ liệu bằng nhau, kích thước của mỗi phân hoạch là n'/p (với n' là kích thước của mẫu); Bước 3. Phân cụm các điểm của mỗi nhóm: Ta thực hiện PCDL cho các nhóm cho đến khi mỗi nhóm được phân thành n'/(pq)cụm (với q>1); Bước 4. Loại bỏ các phần tử ngoại lai: Trước hết, khi các cụm được hình thành cho đến khi số các cụm giảm xuống một phần so với số các cụm ban đầu. Sau đó, trong trường hợp các phần tử ngoại lai được lấy mẫu cùng với quá trình pha khởi tạo mẫu dữ liệu, thuật toán sẽ tự động loại bỏ các nhóm nhỏ. Bước 5. Phân cụm các cụm không gian: Các đối tượng đại diện cho các cụm di chuyển về hướng trung tâm cụm, nghĩa là chúng được thay thế bởi các đối tượng gần trung tâm hơn. Bước 6. Đánh dấu dữ liệu với các nhãn tương ứng. Hình 2.15. Thuật toán CURE Độ phức tạp tính toán của thuật toán CURE là O(n2log(n)). CURE là thuật toán tin cậy trong việc khám phá các cụm với hình thù bất kỳ và có thể áp dụng tốt trên các tập dữ liệu hai chiều. Tuy nhiên, nó lại rất nhạy cảm với các tham số như là tham số các đối tượng đại diện, tham số co của các phần tử đại diện. Nhìn chung thì BIRCH tốt hơn so với CURE về độ phức tạp, nhưng kém về chất lượng phân cụm. Cả hai thuật toán này có thể xử lý các phần tử ngoại lai tốt. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 47 2.3. Phân cụm 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 và 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ả PCDL. Hình 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 CSDL khác nhau: Hình 2.16. Một số hình dạng khám phá bởi phân cụm dưa trên mật độ Các cụm có thể được xem như các vùng có mật độ cao, được tách ra bởi các vùng không có hoặc ít mật độ. Khái niệm mật độ ở đây được xem như là các số các đối tượng láng giềng. Một số thuật toán PCDL dựa trên mật độ điển hình như [2][3][13][20]: DBSCAN, OPTICS, DENCLUE, SNN,…. 2.3.1 Thuật toán DBSCAN Thuật toán phân cụm dựa trên mật độ thông dụng nhất là thuật toán DBSCAN (Density - Based Spatial Clustering of Applications 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 CSDL 1 CSDL 2 CSDL 3 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 48 mà có số đối tượng láng giềng lớn hơn một ngưỡng tối thiểu. Một cụm được xác định bằng tập tất cả các đối tượng liên thông mật độ với các láng giềng của nó. Thuật toán DBSCAN dựa trên các khái niệm mật độ có thể áp dụng cho các tập dữ liệu không gian lớn đa chiều. Sau đây là một số đị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 Dist(p,q) ≤ Eps}, D là tập dữ liệu cho trước. Hình 2.17. Lân cận của P với ngưỡng Eps Một điểm p muốn nằm trong một cụm C nào đó thì NEps(p) phải có tối thiểu MinPts điểm. Theo định nghĩa trên, chỉ những điểm thực sự nằm trong cụm mới thoả mãn điều kiện là điểm thuộc vào cụm. Những điểm nằm ở biên của cụm thì không thoả mãn điều kiện đó, bởi vì thông thường thì lân cận với ngưỡng Eps của điểm biên thì bé hơn lân cận với ngưỡng cũng Eps của điểm nhân . Để tránh được điều này, ta có thể đưa ra một tiêu chuẩn khác để định nghĩa một điểm thuộc vào một cụm như sau: Nếu một điểm p muốn thuộc một cụm C phải tồn tại một điểm q mà p  NEps(q) và số điểm trong NEps(q) phải lớn hơn số điểm tối thiểu. Điều này có thể được định nghĩa một cách hình thức như sau: Đị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: 1) p NEps(q) Với NEps(q) là tập con của D 2) ||NEps(q)|| ≥ MinPts Điều kiện đối tượng nhân. p Eps Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 49 Điểm q gọi là điểm nhân. Ta thấy rằng nó là một hàm phản xạ và đối xứng đối với hai điểm nhân và bất đối xứng nếu một trong hai điểm đó không phải là điểm nhân. Hình 2.18. Mật độ - đến được trực tiếp Định nghĩa 3: Mật độ - đến được (Density - Reachable) Một điểm p được gọi là mật độ- đến được từ một điểm q với hai tham số Eps và MinPts nếu tồn tại một dãy p = p1, p2,…, pn =q sao cho pi+1 là mật độ- đến được trực tiếp từ pi với i=1,..n-1. Hình 2.19. Mật độ đến được Hai điểm biên của một cụm C có thể không đến được nhau bởi vì cả hai có thể đều không thoả mãn điều kiện nhân. Mặc dù vậy, phải tồn tại một điểm nhân trong C mà cả hai điểm đều có thể đến được từ điểm đó. Đị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. Hình 2.20. Mật độ liên thông p q MinPts = 5 Eps = 1 cm p q p1 p q o Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 50 Định nghĩa 5: Cụm và nhiễu Cho D là một tập các đối tượng dữ liệu. Một tập con C khác rỗng của D được gọi là một cụm theo Eps và MinPts nếu thoả mãn hai điều kiện: 1) Cực đại: Với  p,qDnếu pC và q là mật độ- đến được p theo Eps và MinPts thì qC. 2) Với  p,q C, p là mật độ-liên thông với q theo Eps và MinPts. Mọi đối tượng không thuộc cụm nào cả thì gọi là nhiễu. Hình 2.21. Cụm và nhiễu Với hai tham số Eps và MinPts cho trước, ta có thể khám phá các cụm theo hai bước: Bước 1: Chọn một điểm bất kỳ từ tập dữ liệu ban đầu thoả mãn điều kiện nhân. Bước 2: Lấy tất cả các điểm đến được mật độ với điểm nhân đã chọn ở trên để tạo thành cụm. Hai bổ đề này có thể phát biểu một cách hình thức hơn như sau: Bổ đề 1: Giả sử p là một đối tượng trong D, trong đó ||NEps(p)|| ≥ MinPts, tập O = {o|oD và o là mật độ-đến được từ p theo Eps và MinPts} là một cụm theo Eps và MinPts. Như vậy, cụm C không hoàn toàn là duy nhất, tuy nhiên, mỗi một điểm trong C đến được mật độ từ bất cứ một điểm nhân nào của C, vì vậy C chứa đúng một số điểm liên thông với điểm nhân tuỳ ý. Bổ đề 2: Giả sử C là một cụm theo Eps và MinPts, p là một điểm bất kỳ trong 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}. Nhân Biên Nhiễu Eps = 1cm MinPts = 5 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 51 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. Bước 3: Nếu p là điểm nhân thì tạo ra một cụ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 2.22. Thuật toán DBSCAN Nếu ta chọn sử dụng giá trị trị toàn cục Eps và MinPts, DBSCAN có thể hoà nhập hai cụm thành một cụm nếu mật độ của hai cụm gần bằng nhau. Giả sử khoảng cách giữa hai tập dữ liệu S1 và S2 được định nghĩa là Dist(S1,S2) = min{dist(p,q)| pS1 và qS2}. Thuật toán DBSCAN có thể tìm ra các cụ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. Khi có một đối tượng được chèn vào chỉ tác động đến một láng giềng xác định. Mặt khác, DBSCAN yêu cầu người dùng xác định bán kính Eps của các láng giềng và số các láng giềng tối thiểu MinPts, thông thường các tham số này được xác định bằng phép chọn ngẫu nhiên hoặc theo kinh nghiệm. Trừ một số trường hợp ngoại lệ, kết quả của DBSCAN độc lập với thứ tự duyệt các đối tượng dữ liệu. Eps và MinPts là hai tham số toàn cục được xác định bằng thủ công hoặc theo kinh nghiệm. Tham số Eps được đưa vào là nhỏ so với kích thước của không gian dữ liệu, thì độ phức tạp tính toán trung bình của mỗi truy vấn là O(nlogn). 2.3.2. Thuật toán OPTICS Thuật toán OPTICS (Ordering Points To Identify the Cluste