Đề tài Phân cụm dữ liệu trong Dataming

hô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ộ. Thí dụ như : Nếu các đối tượng medoid của dữ liệu khởi tạo không nằm trong mẫu, khi đó kết quả thu được không đảm bảo là tốt nhất được. 2.1.4 Thuật toán CLARANS Thuật toán CLARANS được Ng & Han đề xuất năm 1994, nhằm để cải tiến cho chất lượng cũng như mở rộng áp dụng cho tập dữ liệu lớn. CLARANS cũng sử dụng các đối tượng trung tâm medoids làm đại diện cho các cụm dữ liệu. Như đã biết, PAM là thuật toán phân hoạch có kiểu k-medoids. Nó bắt đầu khởi tạo k tâm đại diện medoid và liên tục thay thế mỗi tâm bởi một đối tượng khác trong cụm cho đến khi là tổng khoảng cách của các đối tượng đến tâm cụm không giảm. CLARANS là thuật toán phân cụm dữ liệu 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 tâm này nếu việc thay thế này 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à láng giềng (Neighbor) 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á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 Í O là tập các đối tượng tâm medoid, NM = O - M là tập các đối tượng không phải tâm. Các đối tượng dữ liệu sử dụng trong thụâ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 điểm. 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à chúng 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 Euclidean : dist: P x P® R0+ 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 đượ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, chúng 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, chúng ta định nghĩa một cụm với tâm 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) = S S dist (o, mi) với mi ÎM, o Î cluster(mi ). Thuật toán chi tiết CLARANS như biểu diễn trong hình sau: Input : O, k, dist, numlocal, and maxneighbor; Output : k cụm dữ liệu; CLARANS (int k, function dist, int numlocal, int maxneighbor) BEGIN for (i = 1; i <= numlocal; i++) { current.create_randomly(k); j = 1; while (j < maxneighbor) { current.select_randomly(old, new); diff = current.calculate_distance_difference(old, new); if (diff < 0) { current.exchange(old, new); j = 1; } else j++; // end if } // end while dist = current.calculate_total_distance(); if (dist < smallest_dist) { best = current; smallest_dist = dist; } // end if } // end for END; Thuật toán CLARANS Trong đó : Create_Randomly(k) : tạo ngẫu nhiên k cụm dữ liệu, nghĩa là thuật toán lựa chọn ngẫu nhiên k đối tượng medoid từ n đối tượng dữ liệu. Select_randomly(old, new) : Thay thế một đối tượng tâm cụm medoid old bởi đối tượng khác new. Calculate_distance_difference(old, new) : Tính toán sự khác nhau về tổng khoảng cách giữa phân hoạch hiện thời và láng giềng của nó. Exchange(old, new) : Hoán đối giữa đối tượng tâm cụm medoid old với đối tượng không phải là medoid new, sau khi hoán đổi vai trò của chúng cũng được hoán đổi. Calculate_total_distance() : Tính tổng khoảng cách cho mỗi phân hoạch. 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ủa 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 tệ 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 (khi trường hợp xấu nhất xẩy ra). 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.1.5. Nhận xét chung về họ các thuật toán phân hoạch Thuật toán k-means chỉ thích hợp để tìm kiếm các cụm dữ liệu có dạng hình cầu, không thích hợp cho việc xác định các cụm với hình dạng bất kỳ, nhưng trong trường hợp các cụm khá gần nhau thì một số đối tượng của một cụm có thể là nằm cuối các trong các cụm khác. Thuật toán PAM là một cải tiến của k-means nhằm để khắc phục trong trường hợp dữ liệu chứa nhiễu hoặc các phần tử ngoại lai. CLARA và CLARANS là các thuật toán dựa trên hàm tiêu chuẩn của thuật toán PAM, đây là các thuật toán có khả năng áp dụng với tập dữ liệu lớn, nhưng hiệu quả của chúng phụ thuộc vào kích thước của các mẫu được phân. Thuật toán CLARANS hiệu quả hơn so với thuật toán CLARA. Hạn chế chung của các thuật toán phân cụm phân hoạch là chỉ thích hợp đối với dữ liệu số và ít chiều, và chỉ khám phá ra các cụm dạng hình cầu, thế nhưng chúng lại áp dụng tốt với dữ liệu có các cụm phân bố độc lập và trong mỗi cụm có mật độ phân bố cao. Các phương pháp dựa trên phân cấp Phương pháp phân cấp: tạo phân cấp cụm chứ không phải là một phân hoạch đơn thuần các đối tượng Không cần dữ liệu nhập là số cụm k Dùng ma trận làm tiêu chuẩn gom cụm Có thể có điều kiện kết thúc (ví dụ số cụm) Cây các cụm: phân cấp cụm thường tạo cây các cụm hay còn được gọi là dendrogram Các lá của cây biểu diễn các đối tượng riêng lẻ Các nút trong của cây biểu diễn các cụm Hai loại phương pháp tạo kiến trúc cụm: Gộp- agglomerative (từ dưới lên) Đưa từng đối tượng vào cluster riêng của nó Trộn ở mỗi bước hai cụm tương tự nhất cho đến khi chỉ còn một cụm hay thỏa điều kiện kết thúc Phân chia – divisive (từ trên xuống) Bắt đầu bằng một cụm lớn chứa tất cả các đối tượng Phân chia cụm phân biệt nhất thành các cụm nhỏ hơn và xử lý cho đến khi co n cụm hay thỏa điều kiện kết thúc Hai loại phương pháp tạo kiến trúc phân cấp cụm Step 0 Step 1 Step 2 Step 3 Step 4 b d c e a a b d e c d e a b c d e Step 4 Step 3 Step 2 Step 1 Step 0 Gộp-agglomerative Phân chia- divisive Các khoảng cách trong Thường có 3 cách được dùng để định nghĩa khoảng cách giữa các cụm: Phương pháp liên kết đơn (láng giềng gần nhất): Phương pháp liên kết hoàn toàn (láng giềng xa nhất): Phương pháp liên kết trung bình (trung bình cặp nhóm không có trọng ): Sức mạnh của các phương pháp phân cấp Khái niệm đơn giản Lý thuyết tốt Khi cụm được trộn/ tách, quyết định là vĩnh cửu => số các phương án khác nhau cần được xem xét bị rút giảm. Điểm yếu của phương pháp phân cấp Trộn/ tách các cụm là vĩnh cửu => các quyết định sai là không thể khắc phục về sau Các phương pháp phân chia là cần thời gian tính toán Các phương pháp là không scalable (mở rộng được) cho các tập dữ liệu lớn Phân tích outlier outliers Là các đối tượng bất tương tự với Có thể gây ra việc đo đạc hay lỗi thực hiện, hay Là kết quả của việc biến đổi dữ liệu kế thừa rất nhiều thuật toán khai phá dữ liệu cố gắng Giảm ảnh hưởng của outliers Giảm outliers Cực tiểu hóa ảnh hưởng của outliers và/ hay khử đi những outliers có thể gây ra mất mát thông tin Có thể quan tâm đến khai khác outlier mining Các ứng dụng của khai thác outlier Phát hiện phạm tội Tiếp thị Xử lý y khoa 2.2.1 Thuật toán BIRCH 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 tóan 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 của các cụm, BIRCH chỉ lưu một bộ ba (n, LS, SS), trong đó n là đố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ưa giữ trong một cây gọi là cây CF (CF tree). Người ta đã chứng minh rằng, các đại lượng thống kê chuẩn như độ đo khoảng cách, có thể xác định cây CF. Hình dưới đâ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 trong 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ụm dữ liệu Cây CF là cây cân bằng, nhằm để lưu trữ các đặc trưng của cụm (CF). Cây CF chứa các nút trong và nút là, nút trong là nút chứa các nút con và nút lá thì không có con. Nút trong lưu trữ tổng các đặc trưng cụm (CF) 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 (Branching Factor - B): nhằm xác định số tối đa các nút con của mỗi nút trong cây, và Ngưỡng (Threshloid-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 được 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 đến kích thước của cây CF. Thuật toán BIRCH thực hiện qua giai đoạn sau: Giai đoạn 1: BIRCH duyệt qua tất cả các đối tượng trong cơ sở dữ liệu và xây dựng một cây CF khởi tạo. Trong giai đoạn này, các đối tượng lần lượt được chèn vào nút lá gần nhất của cây CF (nút lá của cây đóng vai trò là cụm con) sau khi chèn xong thì tất cả các nút trong cây CF được cập nhật thông tin. Nếu đường kính của cụm con sau khi chèn là lớn hơn ngưỡng T, thì nút lá được tách. Quá trình này lặp cho đến khi tất cả các đối tượng đều được chèn vào trong cây. Ở đây ta thấy rằng, mỗi đối tượng trong cây chỉ được đọc một lần, để lưu toàn bộ cây CF trong bộ nhớ thì cần phải điều chỉnh kích thước của cây CF thông qua điều chỉnh ngưỡng T. Giai đoạn hai: BIRCH lựa chọn một thuật toán phân cụm dữ liệu (như thuật toán phân cụm chẳng hạn) để thực hiện phân cụm dữ liệu cho các nút lá của cây. Thuật toán BIRCH thực hiện qua các bước cơ bản như hình sau: Các đối tượng dữ liệu lần lượt được chèn vào cây CF, sau khi chèn hết các đối tượng ta thu được cây CF khởi tạo. Mỗi 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 vào nút lá thì 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. Nếu cây CF hiện thời không có đủ bộ nhớ trong thì tiến hành dựng cây CF nhỏ hơn: kích thước của cây CF được điều khiển bởi tham số T và vì vậy việc chọn một giá trị lớn hơn cho nó sẽ hòa nhập một số 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. 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 ví dụ như k-means và tạo ra một khởi tạo cho phân cụm 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 tùy 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. Với Với cấu trúc cây CF được sử dụng, BIRCH có tốc độ thực hiện phân cụm dữ liệu nhanh và có thể áp dụng đối với tập dữ liệu lớn, đặc biệt, BIRCH 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 tùy chọn, nghĩa là độ phức tạp của nó là O(n), với n là đố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 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 dữ liệu số. Mặc 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ụ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) là thuật toán sử dụng chiến lược dưới lên (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 (đối tượng thuộc về mỗi cụm) 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 phần tử đại diện cho các cụm, CURE có thể khám phá được các cụm có các hình thù và kích thước khác nhau trong cơ sơ dữ liệu 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ủ 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 dưới đây là ví dụ về các dạng và kích thước cụm dữ liệu được khám phá bởi CURE Các phương pháp 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 độ ở được xem như là các số các đối tượng láng giềng. Thuận 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). 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. Tìm tất cả các đối tượng mà các láng giềng của nó thuộc về lớp các đối tượng đã xác định ở trên, một cụm được xác định bằng một tập tất cả các đối tượng kiên thông mật độ với các láng giềng của 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 dữ liệu được chèn vào chỉ tác động đến một láng giềng xác định. Mặc 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, các tham số này khó mà xác định được tối ưu, thông thường nó được xác định bằng phép chọn ngẫu nhiên hoặc theo kinh nghiệm. Người ta á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 do vậy độ phức tạp của DBSCAN đã được cải tiến là O(nlogn) so với độ phức tạp của DBSCAN là O(n2) trong trường hợp nếu không áp dụng cấu trúc chỉ số. Khoảng cách Euclide được sử dụng để đo sự tương tác giữa các đối tượng nhưng không hiệu quả đối với dữ liệu đa chiều. 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. Dưới đây là các định nghĩa và bổ đề được sử dụng trong thuật toán DBSCAN. Định nghĩa 1: lân cận với ngưỡng Eps của một điểm (Eps – Neighborhood of a point) Lân cận với ngưỡng Eps của một điểm P kí hiệu là NEps(p) được xác định như sau: NEps(p) = {q Î D | khoảng cach Dist(p,q) ≤ Eps}, D là tập dữ liệu cho trước. Một điểm p muốn nằm trong một cụm C nào đó thì NEps(p) thì phải có tối thiểu Minpts điểm. Số điểm tối thiểu được chọn là bao nhiêu cũng là bài toán khó, vì: Nếu số điểm tối thiểu lớn thì chỉ những điểm nằm thực sự trong cụm C mới đạt đủ tiêu chuẩn, trong khi đó những điểm nằm ngoài biên của cụm không thể đạt được điều đó. Ngược lại nếu số điểm tối thiểu là nhỏ thì mọi điểm sẽ rơi vào một cụm. Theo định nghĩa trên, chỉ những điểm thực sự nằm trong cụm mới thỏa 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 thỏa 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ủa Eps của điểm nhân (Core point). Để tránh được điều này, chúng 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 vào 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: Đến được trực tiếp theo mật độ (Directly Density-reachable). Một điểm p được gọi là đến được trực tiếp từ điểm q với ngưỡng Eps nếu: p ∊ NEps(q) || NEps(q)|| ≥ Minpts (điều kiện nhân) Điểm q được gọi là điểm nhân (Core point). Có thể thấy là đến được trực tiếp 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 nếu một trong hai điểm đó không phải là điểm nhân. Định nghĩa 3: Đến được mật độ (Density- Reachable) 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 thỏa mãn pi+1 là có thể đến được trực tiếp từ pi với 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 thỏa 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 C mà cả hai điểm đều có thể đến được từ điểm đó. Để cho thuận tiện chúng ta sẽ đưa ra một định nghĩa liên thông mật độ (Density- Connectivity) Định nghĩa 4: Liên thông mật độ (Density- Connectivity) Một điểm p được gọi là liên thông với điểm q theo hai tham số Eps với Minpts nếu như tồn tại một điểm o mà cả hai điểm p, q đều có thể đến được theo tham số Eps và Minpts. Liên thông mật độ có tính chất đối xứng và phản xạ. Định nghĩa 5: Cụm (Clustering) 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 cụm (cluster) thep Eps và Minpts nếu thỏa mãn hai điều kiện: Với mọi p,q Î D, nếu p Î C và q có thể đến được từ p theo Eps và MinPts thì qÎ C. Với mọi p,q Î C, p liên thông mật độ với q theo Eps và MinPts. Định nghĩa 6 : Dữ liệu nhiễu (Noise) Giả sử C1, C2, …, Ck là các cụm 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 cụm nào trong các cụm C1, C2, …, Ck, tức là Noise = {p | với mọi i=1..k, p Ï Ci } Tiếp theo là hai bổ đề để chứng minh cho việc thuật toán phân cụm DBSCAN. Chúng phát biểu như sau: Với hai tham số Eps và MinPts cho trước, chúng 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ểm trong D trong đó || NEps(p)|| ≥ MinPts, tập O = {o|oÎD và o có thể đến được mật độ 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 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 có thể đến được mật độ từ p theo Eps và MinPts}. Thuật toán DBSCAN : DBSCAN khởi tạo điểm p tuỳ ý và lấy tất cả các điểm đến được mật độ từ p với Eps và MinPts. Nếu p là điểm nhân thì thủ tục trên tạo ra một cụm theo Eps và MinPts (Bổ đề 2), Nếu p là một điểm biên, không có điểm nào đến được mật độ từ p và DBSCAN sẽ đi thăm điểm tiếp theo của tập dữ liệu. Nếu chúng 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 theo định nghĩa 5 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}. Hình sau diễn tả thuật toán DBSCAN chi tiết: {----------Mô đun chương trình chính-------} DBSCAN (SetOfPoints, Eps, MinPts) // SetOfPoints is UNCLASSIFIED ClusterId := nextId(NOISE); FOR i FROM 1 TO SetOfPoints.size DO Point := SetOfPoints.get(i); IF Point.ClId = UNCLASSIFIED THEN IF ExpandCluster(SetOfPoints, Point, ClusterId, Eps, MinPts) THEN ClusterId := nextId(ClusterId) END IF END IF END FOR END; // DBSCAN {--------------Thủ tục Expand -------------} ExpandCluster(SetOfPoints, Point, ClId, Eps, MinPts) : Boolean; seeds:=SetOfPoints.regionQuery(Point,Eps); IF seeds.size<MinPts THEN // no core point SetOfPoint.changeClId(Point,NOISE); RETURN False; ELSE // all points in seeds are density- // reachable from Point SetOfPoints.changeClIds(seeds,ClId); seeds.delete(Point); WHILE seeds Empty DO currentP := seeds.first(); result := SetOfPoints.regionQuery(currentP, Eps); IF result.size >= MinPts THEN FOR i FROM 1 TO result.size DO resultP := result.get(i); IF resultP.ClId IN {UNCLASSIFIED, NOISE} THEN IF resultP.ClId = UNCLASSIFIED THEN seeds.append(resultP); END IF; SetOfPoints.changeClId(resultP,ClId); END IF; // UNCLASSIFIED or NOISE END FOR; END IF; // result.size >= MinPts seeds.delete(currentP); END WHILE; // seeds Empty RETURN True; END IF END; // ExpandCluster {--------------End---------------------} Hình : Thuật toán DBSCAN Trong đó, SetOfPoints hoặc là tập dữ liệu ban đầu hoặc là cụm được khám phá từ bước trước, CLId (clusterId) là nhãn đánh dấu phần tử dữ liệu nhiễu có thể thay đổi nếu chúng có thể đến được mật độ từ một điểm khác từ CSDL, điều này chỉ xẩy ra đối với các điểm biên của dữ liệu. Hàm SetOfPoints.get(i) trả về phần tử thứ i của SetOfPoints. Thủ tục SetOfPoints.regionQuery(point, Eps) trả về một danh sách các điểm dữ liệu lân cận với điểm Point trong ngưỡng Eps từ tập dữ liệu SetOfPoints. 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(log n). Thuật toán OPTICS Đây là thuật toán mở rộng cho thuật toán DBSCAN, bằng cách giảm bớt các tham số đầu vào. OPTICS (Ordering Points To Identify the Clustering Structure) sắp xếp các cụm theo thứ tự tăng dần nhằm tự động phân cụm dữ liệu. Thứ tự này diễn tả cấu trúc dữ liệu phân cụm dựa trên mật độ chứa thông tin tương đương với phân cụm dựa trên mật độ với một dãy các tham số đầu vào. OPTICS xem xét bán kính tối thiểu nhằm xác định các láng giềng phù hợp với thuật toán. DBSCAN và OPTICS tương tự với nhau về cấu trúc và có cùng độ phức tạp : O(nLogn) (N là kích thước của tập dữ liệu). Hình sau thể hiện về một thí dụ trong PCDL của thuật toán OPTICS [10][16]: thứ tự các cụm dữ liệu Khoảng cách đến được mật độ Chưa đánh dấuKh Thứ tự phân cụm của các đối tượng của OPTICS Thuật toán DENCLUE DENCLUE (DENsity - Based CLUstEring) là thuật toán PCDL dựa trên một tập các hàm phân phối mật độ. Ý tưởng chính của thuật toán này như sau [10][16]: Sự tác động của một đối tượng tới láng giềng của nó được xác định bởi hàm ảnh hưởng (Influence Function). Mật độ toàn cục của không gian các đối tượng được mô hình như là tổng tất cả các hàm ảnh hưởng của các đối tượng. Các cụm được xác định bởi các đối tượng mật độ cao (density attactors), các đối tượng này là các điểm cực đại của hàm mật độ toàn cục. Hàm ảnh hưởng được định nghĩa như sau : Cho x,y là hai đối tượng trong không gian d chiều Fd, hàm ảnh hưởng của đối tượng y lên đối tượng x được xác định như sau : : Fd , y =(x). Hàm ảnh hưởng là hàm tuỳ chọn, miễn là nó được xác định bởi khoảng cách d(x,y) của các đối tượng, thí dụ như khoảng cách Euclide. Một số thí dụ về hàm ảnh hưởng được cho như sau : Hàm sóng ngang : = , trong đó là một ngưỡng. Hàm Gaussian : Hàm mật độ của một đối tượng x Fd được tính bằng tổng tất cả các hàm ảnh hưởng của các đối tượng lên x. Giả sử ta có một tập dữ liệu D={x1, x2, ..., xn}. Hàm mật độ của x được xác định như sau : ; Hàm mật độ được thành lập dựa trên hàm ảnh hưởng Gauss được xác định như sau : . Thí dụ về kết quả PCDL của thuật toán DENCLUE với hàm chi phối Gaussian được biểu diễn như hình 21 sau. Các cực đại mật độ là các giá trị tại đỉnh của đồ thị. Một cụm cho một cực đại mật độ x* là tập con C, khi các hàm mật độ tại x* không bé hơn : Hình DENCLUE với hàm phân ph Gauss