Luận văn Phương pháp phân cụm và ứng dụng

đề xuất bởi Holland (1975) là một họ tính toán mô hình lấy cảm hứng từ tương tự của sự tiến hóa và di truyền dân số. Gas vốn song song và đặc biệt thích hợp cho việc giải quyết vấn đề tối ưu hóa phức tạp.Filho et al. (1994) trình bày một cuộc khảo sát của khí cùng với một GA đơn giản viết bằng C ngôn ngữ. Thông thường, chỉ có hai thành phần chính của GAS được vấn đề phụ thuộc: các vấn đề mã hóa và chức năng đánh giá (ví dụ, khách quan chức năng). Ngay cả đối với cùng một vấn đề, có thể sử dụng mã hóa khác nhau. Ví dụ, trong các k-có nghĩa là thuật toán di truyền, Krishna và Narasimha (1999) làm việc string-of-group-số mã hóa, trong khi Maulik và Bandyopadhyay (2000) được mã hóa các chuỗi sao cho mỗi chuỗi là một chuỗi các thực số đại diện cho các trung tâm cụm. Trong GAS, các tham số của không gian tìm kiếm được mã hoá trong các hình thức gọi là chuỗi nhiễm sắc thể. AGA maintains dân (set) của N chuỗi mã hoá cho một số dân số cố định kích thước N và tiến hóa qua các thế hệ. Trong mỗi thế hệ, ba nhà khai thác di truyền, nghĩa là, tự nhiên, lựa chọn, xuyên chéo , và đột biến, được áp dụng cho dân số hiện nay để sản xuất một số dân mới. Mỗi chuỗi trong dân số liên kết với một giá trị thể dục tùy thuộc vào giá trị của hàm mục tiêu. Dựa trên nguyên tắc sống còn của các lắp rắp , -47- một chuỗi vài trong số dân hiện hành được lựa chọn và từng được phân công một số bản sao, và sau đó một thế hệ mới của dây đang mang lại bằng cách áp dụng chéo và đột biến để các chuỗi được chọn. Nói chung, một GA điển hình có những năm thành phần cơ bản: mã hóa, khởi tạo, lựa chọn, crossover, và đột biến. Mã hóa là phụ thuộc vào vấn đề dưới xem xét. Trong giai đoạn khởi, dân số (set) của chuỗi sẽ được ngẫu nhiên tạo ra. Sau giai đoạn khởi, có một lặp của các thế hệ. Số lượng của các thế hệ được xác định bởi người sử dụng. Trong khí, chuỗi tốt nhất thu được cho đến nay được lưu trữ trong một vị trí riêng biệt bên ngoài dân số và sản lượng cuối cùng là chuỗi tốt nhất trong số tất cả có thể có chuỗi kiểm tra trong toàn bộ quá trình. Murthy và Chowdhury (1996) đề xuất một GA trong một nỗ lực để đạt được tối ưu giải pháp cho các vấn đề clustering. Trong thuật toán này, các chức năng đánh giá được xác định như là tổng của bình phương khoảng cách Euclide của các điểm dữ liệu từ các cụm tương ứng của họ trung tâm. Ngoài ra, đơn điểm chéo (Michalewicz, 1992), nghĩa là, các nhà điều hành chéo giữa hai dây, được thực hiện tại một vị trí, và các chiến lược elitist, nghĩa là, các chuỗi hay nhất được mang từ trước đến dân số kế tiếp, được sử dụng. Tseng và Yang (2001) đề xuất một cách tiếp cận di truyền được gọi là clustering đến tự động phân nhóm vấn đề. Clustering là phù hợp với phân nhóm dữ liệu với nhỏ gọn cụm hình cầu, và số cụm có thể được kiểm soát gián tiếp bởi một tham số w. Thuật toán sẽ sản xuất một số lượng lớn các cụm nhỏ gọn với một giá trị nhỏ của w và nó sẽ sản xuất một số lượng nhỏ hơn của cụm lỏng hơn với một giá trị lớn của w. A di truyền phân nhóm dựa trên thuật toán nhằm tìm ra các cụm nonspherical đã được đề xuất bởi Tseng và Yang (2000). Garai và Chaudhuri (2004) đề xuất một phân nhóm di truyền được hướng dẫn theo cấp bậc thuật toán mà có thể tìm thấy tùy tiện có hình cụm. Thuật toán này bao gồm hai giai đoạn. Lúc đầu, tập dữ liệu gốc là bị phân hủy thành một số nhóm phân mảnh để lây lan trong quá trình GAsearch ở giai đoạn thứ hai trong toàn bộ không gian. Sau đó, các thứ bậc Cụm trộn thuật toán (HCMA) được sử dụng. Trong quá trình sát nhập, một kỹ thuật gọi là các -48- cluster liền kề kiểm tra thuật toán (ACCA) được sử dụng để thử nghiệm kề của hai cụm phân đoạn để họ có thể được sáp nhập vào một nhóm. Krishna và Narasimha (1999) và Bandyopadhyay và Maulik (2002) đề xuất hai thuật toán phân nhóm khác nhau dựa trên GAS và k phổ biến có nghĩa là thuật toán. Trong di truyền k-có nghĩa là thuật toán (GKA), Krishna và Narasimha (1999) được sử dụng k-có nghĩa là nhà điều hành thay vì các nhà điều hành chéo để tăng tốc độ hội tụ, trong khi ở kga-clustering, Bandyopadhyay và Maulik (2002) được sử dụng các nhà điều hành crossover- đơn điểm. Cowgill et al. (1999) đề xuất một thuật toán-based clustering di truyền được gọi là COWCLUS. Trong COWCLUS, chức năng đánh giá là tỷ lệ phương sai (VR) được định nghĩa trong điều kiện cô lập cụm bên ngoài và tính đồng nhất cụm nội bộ. Mục tiêu của thuật toán là để tìm các phân vùng với VR tối đa. 4.2 J- Means Cho  1 2, , , nD x x x  là một tập đối tượng và SD được hiểu là tất cả các phần của D. 2 1 min D D i k i P S i x C x z     Nơi k là số lượng cụm , . được hiểu là Euclidean chuẩn tắc, và zi là tâm của cụm Ci 1 i i x Ci Z x C    Với i = 1, 2,…k Thuật toán J-mean : Bước 1 (khởi) Hãy để PD = (C1, C2,. . . , Ck) là một phân vùng ban đầu của D, zi là trọng tâm của cụm Ci, và fopt được mục tiêu hiện chức năng giá trị; S2 (điểm chiếm đóng) Tìm điểm trống, nghĩa là, điểm trong D không trùng với một cụm trọng tâm trong một dung sai nhỏ; -49- S3 (Bước khu phố) Tìm phân vùng tốt nhất DP và mục tiêu tương ứngchức năng giá trị f  trong các khu phố nhảy của giải pháp hiện tại PD: S31 (khai phá láng giềng) Đối với mỗi j (j = 1, 2,..., N), lặp lại sau bước sau: (a) tái định cư. Thêm một cụm mới centroid Z k+1 tại một số điểm trống xj vị trí và tìm thấy những chỉ số i của trọng tâm tốt nhất để xóa; cho vij biểu sự thay đổi trong giá trị hàm mục tiêu; (b) Giữ tốt nhất. Giữ đôi chỉ số i và j nơi vij là tối thiểu; S32 (chuyển hay thay thế) Nếu trọng tâm zi’ bởi xj và cập nhật các thành viên nhóm cho phù hợp để có được P phân vùng mới DP ; đặt ' ': opt i jf f v   S4 (Chấm dứt hoặc di chuyển) Nếu optf f  , dừng; nếu không, di chuyển đến láng giềng tốt nhất Giải pháp DP ; đặt DP là giải pháp hiện hành và quay về bước S2. 5. Thuật toán phân cụm dữ liệu dựa vào lƣới 5.1 STING STING là kỹ thuật phân cụm đa phân giải dựa trên lưới, trong đó vùng không gian dữ liệu được phân rã thành số hữu hạn các cells chữ nhât, điều này có ý nghĩa là các cells lưới được hình thành từ các cells lưới con để thực hiện phân cụm. Có nhiều mức của các cells chữ nhật tương ứng với các mức khác nhau của phân giải trong cấu trúc lưới, và các cells này hình thành cấu trúc phân cấp : mỗi cells ở mức cao được phân hoạch thành các số các cells nhỏ ở mức thấp hơn tiếp theo trong cấu trúc phân cấp. Các điểm dữ liệu được nạp từ CSDL, giá trị của các tham số thống kê cho các thuộc tính của đối tượng dữ liệu trong mỗi ô lưới được tính toán từ dữ liệu và lưu trữ thông qua các tham số thống kê ở các cell mức thấp hơn (điều này giống với cây CF). Các giá trị của các tham số thống kê gồm : số trung bình – mean, số tối đa – max, số tối thiểu – min, số đếm –count , độ lệch chuẩn –s,… Các đối tượng dữ liệu lần lượt được chèn vào lưới và các tham số thống kê ở trên được tính trực tiếp thông qua các đối tượng dữ liệu này. Các truy vấn không gian được thực hiện bằng cách xét các cells thích hợp tại mỗi mức -50- phân cấp. Một truy vấn không gian được xác định như là một thông tin khôi phục lại của dữ liệu không gian và các quan hệ của chúng. STING có khả năng mở rộng cao , nhưng do sử dụng phương pháp đa phân giải nên nó phụ thuộc chặt chẽ vào trọng tâm của mức thấp nhất. Đa phân giải là khả năng phân rã tập dữ liệu thành các mức chi tiết khác nhau. Khi hòa nhập các cells của cấu trúc lưới để hình thành các cụm, nó không xem xét quan hệ không gian giữa các nút của mức con không được hòa nhập phù hợp( do chúng chỉ tương ứng với các cha của nó) và hình dạng của các cụm dữ liệu khám phá là isothetic, tất cả ranh giới của các cụm có các biên ngang và dọc, theo biên của các cells và không có đường biên chéo được phát hiện ra. Các lợi thế của cách tiếp cận này so với các phương pháp phân cụm dữ liêu khác : - Tính toán dựa trên lưới là truy vấn độc lập vi thông tin thống kê được bảo quản trong mỗi cells đại diện nên chỉ cần thông tin tóm tắt của dữ liệu trong cells chứ không phải là dữ liệu thực tế và không phụ thuộc vào câu truy vấn. - Cấu trúc dữ liệu lưới thuận tiện cho quá trình xử lý song song và cập nhật liên tục. - Duyệt toàn bộ CSDL một lần để tính toán các đại lượng thống kê cho mỗi cells, nên nó hiệu quả và do đó độ phức tạp thời gian để tạo các cụm xấp xỉ O(n), trong đó n là tổng số các đối tượng. Sau khi xây dựng cấu trúc phân cấp, thời gian xử lý cho các truy vấn là O(g), trong đó g là tổng số cells lưới ở mức thấp (g<<n) Các hạn chế của thuật toán này : - Trong khi sử dụng cách tiếp cận đa phân giải để thực hiện phân tích cụm chất lượng của phân cụm STING hoàn toàn phụ thuộc vào tính chất hộp ở mức thấp nhất của cấu trúc lưới. Nếu tính chất hộp là mịn, dẫn đến chi phí thời gian xử lý tăng, tính toán trở nên phức tạp và nếu mức dưới cùng là quá thô thì nó có thể làm giảm bớt chất lượng và độ chính xác của phân tích cụm. Thuật toán STING : 1. Xác định tầng để bắt đầu 2. Với mỗi cái của tầng này, tính toán khoảng tin cậy (hoặc ước lượng khoảng) của xác suất mà cells này liên quan tới truy vấn 3. Từ khoảng tin cậy của tính toán trên,gán nhãn cho là có liên quan hoặc -51- không liên quan. 4. Nếu lớp này là lớp cuối cùng , chuyển sang Bước 6; nếu khác thì chuyển sang Bước 5 5. Duyệt xuống dưới của cấu trúc cây phân cấp một mức. Chuyển sang Bước 2 cho các cells mà hình thành các cells liên quan của lớp có mức cao hơn. 6. Nếu đặc tả được câu truy vấn, chuyển sang bước 8; nếu không thì chuyển sang bước 7. 7. Truy lục lại dữ liệu vào trong các cells liên quan và thực hiện xử lý. Trả lại kết quả phù hợp yêu cầu của truy vấn. Chuyển sang Bước 9. 8. Tìm thấy các miền có các cells liên quan. Trả lại miền mà phù hợp với yêu cầu của truy vấn. Chuyển sang bước 9 9. Dừng 5.2. Thuật toán CLIQUE Trong không gian đa chiều, các cụm có thể tồn tại trong tập con của các chiều hay còn gọi là không gian con. Thuật toán CLIQUE là thuật toán hữu ích cho PCDL không gian đa chiều trong các CSDL lớn thành các không gian con. Thuật toán này bao gồm các bước : - Cho n là tập lớn của các điểm dữ liệu đa chiều; không gian dữ liệu thường là không giống nhau bởi các điểm dữ liệu. Phương pháp này xác định những vùng gần, thưa và “đặc” trong không gian dữ liệu nhất định, bằng cách đó phát hiện ra toàn thể phân bố mẫu của tập dữ liệu. - Một đơn vị là dày đặc nếu phần nhỏ của tất cả các điểm dữ liệu chứa trong nó vượt quá tham số mẫu đưa vào. Trong thuật toán CLIQUE, cụm được định nghĩa là tập tối đa liên thông các đơn vị dày đặc. Các đặc trƣng của CLINQUE - Tự động tìm kiếm không gian con của không gian đa chiều, sao cho mật độ đặc của các cụm tồn tại trong không gian con. - Mẫn cảm với thứ tự của dữ liệu vào và không phù hợp với bất kỳ quy tắc phân bố dữ liệu nào. - Phương pháp này tỷ lệ tuyến tính với kích thước vào và có tính biến đổi tốt khi số chiều của dữ liệu tăng. -52- Nó phân hoạch tập dữ liệu thành các hình hộp chữ nhật và tìm các hình hộp chữ nhật đặc, nghĩa là các hình hộp này chứa một số các đối tượng dữ liệu trong số các đối tượng láng giếng cho trước. Hợp các hình hộp này tạo thành các cụm dữ liệu. Tuy nhiên , CLINQUE được bắt đầu bằng cách tiếp cận đơn giản do đó chính xác của kết quả phân cụm có thể bị ảnh hưởng dẫn tới chất lượng của các phương pháp này có thể giảm. Phương pháp bắt đầu nhận dạng các cells đặc đơn chiều trong không gian dữ liệu và tim kiếm phân bố của dữ liệu, tiếp đến CLINQUE lần lượt tìm các hình chữ nhật 2 chiều, 3 chiều,…., cho đến khi hình hộp chữ nhật đặc k chiều được tìm thấy, độ phức tạp tính toán của CLIQUE là O(n) 5.3. Thuật toán WaveCluster Thuật toán WaveCluster là phương pháp gần giống với STING, tuy nhiên thuật toán sử dụng phép biến đổi dạng sóng đẻ tìm ô đặc trong không gian. Đầu tiên kỹ thuật này tóm tắt dữ liệu bằng việc tận dụng cấu trúc dạng lưới đa chiều lên trên không gian dữ liệu. Tiếp theo nó sử dụng phép biến đổi dạng sóng để biến đổi không gian có đặc trưng gốc, tìm kiếm ô đặc trong không gian đã được biến đổi. Phương pháp này là phức tạp với các phương pháp khác chính là ở phép biến đổi. Ở đây, mỗi cells lưới tóm tắt thông tin các điểm của một nhóm ánh xạ vào trong cells. Đây là thông tin tiêu biểu thích hợp đưa vào bộ nhớ chính để sử dụng phép biến đổi dạng sóng đa phân giải và tiếp theo là phân tích cụm. Một phép biến đổi dạng sóng là kỹ thuật dựa trên cơ sở xử lý tín hiệu và xử lý ảnh bằng phân tích tín hiệu với tần số xuất hiện trong bộ nhớ chính. Bằng việc thực hiện một loạt các phép biến đổi ngược phức tạp cho nhóm này,nó cho phép các cụm trong dữ liệu trở thành rõ ràng hơn. Các cụm này có thể được xác định bằng tìm kiếm ô đặc trong vùng mới. Phương pháp này phức tạp, nhưng lại có những lợi thế : - Cung cấp cụm không giám sát, khử nhiễu các thông tin bên ngoài biên của cụm. Theo cách đó, vùng đặc trong không gian đặc trưng gốc hút các điểm ở gần và ngăn chặn các điểm ở xa. Vì vậy, các cụm tự động nổi bật và làm sạch khu vực xung quanh nó, do đó các kết quả tự động loại phần tử ngoại lai. -53- - Đa phân giải là thuộc tính hỗ trợ dò tìm các cụm có các mức biến đổi chính xác. - Thực hiện nhanh với độ phức tạp của thuật toán là O(n), trong đó n là số đối tượng trong CSDL. Thuật toán có thể thích hợp với xử lý song song. - Xử lý tập dữ liệu lớn có hiệu quả, khám phá các cụm có hình dạng bất kỳ, xử lý phần tử ngoại lai, mẫn cảm với thứ tự vào, và không phụ thuộc vào các tham số vào như số các cụm hoặc bán kính láng giềng. 6. Thuật toán phân cụm dữ liệu dựa vào mật độ 6.1 Thuật toán DBSCAN Thuật toán DBSCAN thích nghi với mật độ dầy để phân cụm và khám phá ra các cụm có hình dạng bất kỳ trong không gian CSDL có nhiễu. Nó có định nghĩa cụm là tập tối đa các điểm liên thông mật độ. Phân cụm dựa vào mật độ là tập các đối tương liên thông mật độ mà tối đa về liên lạc mật độ; mỗi đối tượng không được chứa trong cụm là được xem xét nhiễu. Trên thực tế DBSCAN tìm kiếm cho các cụm bằng cách kiểm tra các đối tượng mà có số đối tượng láng giềng nhỏ hơn một ngưỡng tối thiểu, tức là có tối thiểu MinPts đối tượng và mối đối tượng trong cụm tồn tại một đối tượng khác trong cụm giống nhau với khoảng cách nhỏ một ngưỡng Eps. 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 liên thông mật độ các láng giềng của nó. DBSCAN lặp lại tìm kiếm ngay khi các đối tượng liên lạc mật độ từ các đối tượng trung tâm, nó có thể bao gồm việc kết hợp một số cụm có mật độ liên lạc. Quá trình kết thúc khi không tìm được điểm mới nào có thể thêm vào bất cứ cụm nào. DBSCAN có thể tìm ra các cụm với hình thù bất kỳ, trong khi đo 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 sử dụng tham số Eps và MinPts trong thuật toán để kiểm soát mật độ của các cụm . DBSCAN bắt đầu với một điểm tùy ý và xây dựng mật độ láng giềng có thể được đối với Eps và MinPts, Vì vậy, DBSCAN yêu cầu người dùng xác định bán kính Eps của 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 -54- nghiệm. Độ 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 của DBSCAN được cải tiến là O(nlogn). Thuật toán DBSCAN có thể áp dụng cho các tập dữ liệu không gian lớn đa chiều, khoảng cách Eucle có thể áp dụng cho tập dữ liệu không gián lớn đa chiều, khoảng cách Eclide được sử dụng để đo sự tương tự giữa các đối tượng nhưng không hiệu quả đối với dữ liệu đa chiều [10][15] - Định nghĩa 1 : Lân cận với ngưỡng Eps của một điểm p 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. 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. 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 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. Để tránh được điều này, 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 thuộc 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 p  NEps (q) phải lớn hơn điểm tối thiểu. Điều này dẫn ba phép đo được sử dụng để mô tả thuộc tính cảu các điểm dữ liệu, là mật độ liên lạc trực tiếp, mật độ liên lạc và mật độ liên lạc và mật độ liên thông được định nghĩa như sau : - Định nghĩa 2 : Mật độ liên lạc trực tiếp Một điểm p được gọi là liên lạc trực tiếp từ điểm q với ngưỡng Eps nếu : 1. p  NEps (q) 2.  EspN q MinPts (điều kiện nhân), điểm q gọi là điểm nhân. -55- Có thể thấy liên lạc trực tiếp là một hàm phản xạ và đối xứng 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. - Định nghĩa 3 : Mật độ liên lạc Một điểm p được gọi là liên lạc từ một điểm q theo 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êm liên lạc trực tiếp từ pi với 1 1i n   Hai điểm biên của một cụm C có thể không liên lạc được với nhau bởi vì cả hai đều không thỏa mãn điều kiện nhân. - Định nghĩa 4 : Mật độ liên thông Một điểm p được gọi là liên thông với điểm q theo tham số Eps và MinPts nếu tồn tại một điểm O mà cả hai điểm p, q đều có thể liên lạc được theo tham số Eps và MinPts. Mật độ liên thông có tính chất đối xứng và phản xạ. - Định nghĩa 5 : Cụm Giả sử D là một tập 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 theo Eps và MinPts nếu thỏa mãn hai điều kiện : 1. Với ,p q D , nếu p C và q có thể liên lạc được từ p theo Eps và MinPts thì q C 2. Với ,p q C ,p liên thông với q theo Eps và MinPts. - Định nghĩa 6 : Nhiễu 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à N ={p/ với mọi I = 1,…,k  Ci}. Với hai tham số Eps và MinPts cho trước, 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 thỏa mãn điều kiện nhân. - Bước 2 : Lấy tất cả các điểm liên lạc với điểm nhân đã chọn để tạo thành cụm. Bổ đề 1 : Giả sử p là một điểm trong D, Es ( )pN p MinPts tập O ={o/o  D và có thể liên lạ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 điểm trong C liên lạc 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 tùy ý. -56- Bổ đề 2 : Giả sử C là một cum theo Eps và MinPts, p là một điểm bất kỳ trong C với Es ( )pN p MinPts . Khi đó, C trùng với tập O ={o/o  D và o có thể liên lạc từ p theo Eps và MinPts}. Thuật toán : DBSCAN khởi tạo điểm p tùy ý và lấy tất cả các điểm liên lạc mật độ từ p tớ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 liên lạ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 sử dụng giá trị toàn cục Eps và Minpts, DBSCAN có thể hòa nhập hai cụm ( Đị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à p  S2}. Thuật toán DBSCAN --------------main Module---------------- DBSCAN(SetOfPoints, Eps, MinOts) //SetOfPoints is UNCLASSIFIED Clusterid:=NextId(NOISE); FOR i FROM 1 TO SetOfPoints.size DO Point := SetOfPoints.get(i); IF PointClId = UNCLASSIFIED THEN IF ExpandCluster (SetOfPoints, Point, ClusterId, Eps, MinPts ) THEN ClusterId.= nextld(ClusterId) END IF END IF END FOR FOR END; I/DBSCAN --------ExpandCluster Procedure ------- ExpandClusster(SetOfPoints, Points, ClId, Eps, MinPts): Boolean; seeds:= SetOfPoints.regionQuery(Point, E ps) IF seeds.size < MinPts THEN // no core point SetOfPoints.changeclId(Point, NOISE), RETURN False; ELSE //all points in seeds are density-reachable from Point SetOfPoints.changeClId(seeds, ClId); seeds.delete(Point); WHILE -57- seeds Empty DO currentP:= seeds.firstO; result:= SetOfPoints.regionQuery(CurrentP, Eps); IF result.size >= MinPts THEN FOR i FROM 1 to result.size 00 resultpP:= result.get(i); IF resultp.ClId IN {UNCLASSIFIED, NOISE) THEN IF resultp.ClId = UNCLASSIFIED THEN seeds.append(resultP); END IF SetOfPoints.changeC1Id(resultP, C1Id), ENDIF; //UNCLASSIFIED or NOISE END FOR; END IF ;// result.size >= Minpts Seed.delete(CurrentP) END WHILE ;//seeds Empty RETURN True; END IF; END ;//ExpandCluster 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, C1Id (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ể liên lạc mật độ từ một điểm khác trong 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 SetOfPoint. Trừ một số trường hợp ngoại lệ, kết quả của DBSCAN là độ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(logn). 6.2. Thuật toán OPTICS Thuật toán này là mở rộng của DBSCAN, tuy nhiên nó cải tiến bằng cách giảm bớt các tham số đầu vào. Thuật toán này không phân cụm các điểm -58- dữ liệu mà thực hiện tính toán và sắp xếp trên các điểm dữ liệu theo thứ tự tăng dần nhằm tự động PCDL và phân tích cụm tương tác hơn là đưa ra phân cụm một tập dữ liệu rõ ràng. Đây là thứ tự mô tả cấu trúc phân dữ liệu cụm dựa trên mật độ của dữ liệu, nó chứa thông tin tương ứng với phân cụm dựa trên mật độ từ một dãy các tham số được thiết lập và tạo thứ tự của các đối tượng trong CSDL, đồng thời lưu trữ khoản cách lõi và khoảng cách liên lạc phù hợp của mỗi đối tượng. Hơn nữa, thuật toán được đề xuất rút ra các cụm dựa trên thứ tự thông tin. Như vậy thông tin đủ cho trích ra tất cả các cụm dựa trên mật độ khoảng cách bất kỳ  mà nhỏ hơn khoảng cách  được sử dụng trong sinh thứ tự. Việc sắp xếp thứ tự được xác định bởi hai thuộc tính riêng của các điểm dữ liệu đó là khoảng cách nhân và khoảng cách liên lạc. Các phép đo này chính là kích thước mà có liên quan đến quá trình của thuật toán DBSCAN, tuy nhiên, chúng được sử dụng để xác định thứ tự của các điểm dữ liệu đã được xắp xếp. Thứ tự dựa tren cơ sở các điểm dữ liệu mà có khoảng cách nhân nhỏ nhất và tăng dần độ lớn. Điều duy nhất về phương pháp này là người sử dụng không phải xác định giá trị  hoặc MinPts phù hợp. Thuật toán này có thể phân cụm các đối tượng đã cho với các tham số đầu vào như  và MinPts, nhưng nó vẫn cho phép người sử dụng tùy ý lựa chon các giá trị tham số mà sẽ dãn đến khám phá các cụm chấp nhận được. Các thiết lập tham số thường dựa theo kinh nghiệm tập hợp và khó xác định, đặc biệt là với các tập dữ liệu đa chiều. Tuy nhiên, nó cũng có độ phức tạp thời gian thực hiện như DBSCAN bởi vì có cấu trúc tương đương với DBSCAN : O(nlogn)- n là kích thước của tập dữ liệu. Thứ tự cụm của tập dữ liệu có thể được biểu diễn bằng đồ thị, và được minh họa trong hình sau, có thể thấy ba cụm, giá trị  quyết định số cụm 6.3. Thuật toán DENCLUDE DENCLUDE đưa ra cách tiếp cận khác với các thuật toán phân cụm dựa trên mật độ trước đó, cách tiếp cận này xem xét mô hình được sử dụng một công thức toán để mô tả mỗi điểm dữ liệu sẽ ảnh hưởng trong mô hình như thế nào được gọi là hàm ảnh hưởng có thể xem như một h