Thuật toán phân cụm dữ liệu dựa vào lưới

2.6 Các thuật toán phân cụm dữ liệu

2.6.4 Thuật toán phân cụm dữ liệu dựa vào lưới

Phương pháp phân cụm dựa trên lưới thích hợp với dữ liệu nhiều chiều, và chủ yếu được dùng để phân cụm cho dữ liệu không gian. Phương pháp sử dụng cấu trúc dữ liệu lưới bằng cách chia không gian thành số hữu hạn các ô để hình thành cấu trúc lưới và mọi thao tác phân cụm đều thực hiện trên đó.

Ưu điểm là thời gian xử lý nhanh mà không bị ảnh hưởng bởi số các đối tượng dữ liệu, ngược lại nó phụ thuộc vào số các ô trong mỗi chiều của không gian được chia.

Cách tiếp cận dựa trên lưới hiệu quả hơn so với phương pháp dựa trên mật độ và phân cấp, vì chỉ làm việc với từng đối tượng trong từng ô mà không phải đối tượng dữ liệu, mặt khác phương pháp này không trộn/hòa nhập các ô như phân cấp.

Ví dụ về cấu trúc dữ liệu lưới chứa các ô trong không gian:

Hình 9: Mô hình cấu trúc dữ liệu lưới

39

2.6.4.1 STING

STING là kỹ thuật phân cụm đa phân giải dựa trên lưới, khám phá tính chất của cụm dựa vào cấu trúc chỉ số. STING chia miền không gian thành những ô lưới chữ nhật theo chiều ngang hoặc chiều dọc và đánh chỉ số cho từng ô lưới. Sau đó, mỗi đối tượng dữ liệu sẽ được đưa vào ô lưới tương ứng.

Một cấu trúc được sử dụng lên lưới của miền dữ liệu không gian. Mỗi một ô ở tầng i thì được chia thành k ô ở tầng kế tiếp.

STING lưu trữ tham số trong mỗi ô với mục đích có thể trả lời những yêu cầu về thống kê. Ngoài việc lưu trữ số điểm hoặc đối tượng trong từng ô, STING lưu trữ thêm một vài giá trị khác gồm:

- m – giá trị trung bình của tất cả các giá trị trong ô.

- s - mức deviation của tất cả các giá trị của thuộc tính trong một ô - min – giá trị nhỏ nhất của một thuộc tính trong một ô

- max – giá trị lớn nhất của một thuộc tính trong một ô.

- Dis – kiểu phân bố mà một thuộc tính trong một ô tuân theo. Kiểu phân bố có thể là: thường, đều, hàm số mũ hoặc không xác định. Kiểu phân bố có thể được xác định trước bởi người dùng hoặc xác định bằng phương pháp X2

Hình 10: Mô hình thuật toán STING

40

Các truy vấn không gian được thực hiện bằng cách xét các ô thích hợp tại mỗi mức của phân cấp. 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. Một câu truy vấn đưa ra một kết quả mà người sử dụng muốn tìm. Ví dụ như “Đưa ra vùng lớn nhất mà ít nhất có 100 ngôi nhà trong một đơn vị, có ít nhất 70%

nhà có giá trị trên $400 với độ tin cậy là 90%”.

Để xác định được câu truy vấn này, STING bắt đầu từ gốc (tầng cao nhất) của cấu trúc cây và tìm các ô thỏa mãn cho câu truy vấn. Ô thỏa mãn câu truy vấn được xác định trên khả năng của các đối tượng trong câu truy vấn. Chỉ những ô nhỏ thỏa mãn thì mới được xét tiếp tục và quá trình dừng lại khi lá thấp nhất được tìm thấy. Kết quả đưa ra là những ô ở tầng thấp nhất.

Độ phức tạp của STING là O(N), với N là số đối tượng trong cơ sở dữ liệu. STING chỉ cần duyệt qua toàn bộ cơ sở dữ liệu một lần để đưa ra được cấu trúc cây mà mỗi lần trả lời một câu truy vấn cần thời gian chạy là O(K) với K là số ô lưới. Chú ý là N >>K.

Ưu điểm:

- Tính toán dựa trên lưới là truy vấn độc lập vì thông tin thống kê được bảo quản trong mỗi ô đại diện nên chỉ cần thông tin tóm tắt của dữ liệu trong ô lưới chứ không phải 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ộ cơ sở dữ liệu cho một lần để tính toán các đại lượng thống kê cho mỗi ô, nên nó rất hiệu quả.

Nhược điểm:

Mặc dù STING có thể đưa ra một phân cụm tốt đáp ứng được yêu cầu của người sử dụng trong khoảng thời gian rất nhanh nhưng vẫn tồn tại hai vấn đề:

41

- Thuật toán chỉ dựa trên thuộc tính của các lá ở tầng cuối cùng.

- Thuật toán không dựa vào mối quan hệ giữa các nút con không cùng một cha

Vì thế, thuật toán đưa ra được cụm với biên là chiều ngang và chiều dọc nhưng không đưa ra được biên có chiều là đường chéo. Điều này cũng ảnh hưởng tới chất lượng của thuật toán.

2.6.4.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 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 CLIQUE:

- 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.

42

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, CLIQUE đượ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à tìm kiếm phân bố của dữ liệu, tiếp đến CLIQUE 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).

2.6.4 Thuật toán phân cụm dữ liệu dựa vào mật độ

Phương pháp dựa trên mật độ phân cụm các đối tượng dữ liệu dựa trên mối quan hệ của các đối tượng dữ liệu với các điểm lân cận của các điểm dữ liệu đó. Phân cụm dựa trên mật độ (có điều kiện cụm cục bộ) giống như các điểm có khả năng liên kết theo mật độ. Một cụm được mở rộng theo hướng bất kỳ mà mật độ dẫn theo, do đó phương pháp này có khả năng tìm ra các cụm có hình dạng phức tạp. Mặc dù chỉ duyệt dữ liệu một lần nhưng phương pháp này có khả năng loại bỏ phần tử nhiễu và phần tử ngoại lai. Phương pháp này phù hợp với các đối tượng có trường dữ liệu kiểu số, dữ liệu thuộc tính chỉ là thuộc tính mô tả thêm cho các đối tượng không gian.

Phương pháp này có thể tiếp cận theo 2 hướng chính: Liên kết dựa trên mật độ và hàm mật độ.

2.6.5.1 Thuật toán DBSCAN

DBSCAN được đề xuất năm 1996 bởi Ester, P.Kriegel và J.Sande, khi nghiên cứu thuật toán phân cụm dữ liệu không gian dựa trên định nghĩa cụm là tập tối đa các điểm liên thông về mật độ. Thuật toán thực hiện tốt trên

43

không gian 2 chiều, 3 chiều hay một số không gian nhiều chiều khác; thích hợp với cơ sở dữ liệu có mật độ phân bố dày đặc kể cả có phần tử nhiễu.

Hình 11: Hình dạng các cụm được khám phá bởi DBSCAN Một số khái niệm sử dụng trong giải thuật DBSCAN:

1. Lân cận với ngưỡng Eps của một điểm: 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 cách dist(p,q) ≤ Eps} với 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 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 bé hơn lân cận với ngưỡng cũng Eps của điểm nhân.

44

Để 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 q mà q  NEps(q) phải lớn hơn điểm tối thiểu. Điều này dẫn đến ba phép đo được sử dụng để mô tả thuộc tính của 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 thông được định nghĩa như sau:

2. Một điểm dữ liệu p được gọi là điểm nhân nếu miền lân cận của p với bán kính Eps có ít nhất là minpt điểm.

3. Mật độ - đến được trực tiếp: q được gọi là đến được theo mật độ trực tiếp nếu p là điểm nhân và q  Neighbor(p, Eps)

Hình 12: Mật độ - đến được trực tiếp

4. Mật độ - đến được: Một điểm p được gọi là mật độ - đến được từ điểm q theo tham số Eps và Minpt nếu tồn tại một dãy p = p0, p1, … , pn = q với pi là đến được theo mật độ trực tiếp từ pi+1.

Hình 13: Mật độ - đến được

Hai điểm của cụm C có thể không đến được với nhau bởi vì cả hai cùng 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 trong C mà cả hai điểm đều có thể đến được từ điểm đó.

45

5. Mật độ - liên thông: Một điểm p gọi là mật độ - liên thông với q nếu có một điểm 0 mà cả p và q đều là mật độ - đến được từ 0.

Hình 14: Mật độ - liên thông

6. Cụm: 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:

a. Với mọi p, q  D, nếu p  C và q có thể đến được từ p theo Eps và Minpts thì p  C.

b. Với mọi p, q  C, p liên thông theo mật độ với q theo Eps và Minpts.

7. Dữ liệu 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, một điểm dữ liệu nếu không thuộc vào cụm nào trong các cụm C1, C2, … , Ck thì gọi là nhiễu, tức là nhiễu = {p | i = 1

…k, p  Ci}

Hình 15: Cụm và nhiễu

Ngoài việc sử dụng các định nghĩa trên, DBSCAN còn có hai bổ đề quan trọng để kiểm tra tính đúng đắn của thuật toán. Với các tham số Eps và

46

Minpts đã cho trước chúng ta có thể phát hiện một cụm theo phương pháp mật độ theo hai bước sau:

- Thứ nhất chọn một điểm bất kì trong CSDL thỏa mãn điều kiện nhân, coi điểm này là hạt giống.

- Thứ hai tìm tất cả các điểm kề mật độ với điểm hạt giống trong cụm.

Bổ đề 1: Giả sử p là một điểm trong D và || NEps (p) || ≥ Minpts. Tập O

= {o | o  D và o có thể liên lạc từ p} là một cụm theo Eps và MinPts.

Không rõ ràng rằng cụm C được xác định bởi duy nhất một điểm nhân nào của nó. Tuy nhiên, mỗi điểm trong C là điểm kề cận với một điểm nhân bất kỳ của C và theo đó C chính xác chứa các điểm mà kề mật độ với một điểm nhân bất kỳ của C.

Bổ đề 2: Giả sử C là một cụm theo Eps và MinPts là đ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ể liên lạc theo Eps và MinPts}.

Thuật toán chi tiết:

B1: Tạo đồ thị gồm các đối tượng trong tập dữ liệu.

B2: Với mỗi điểm nhân c vẽ cạnh từ c tới mọi điểm p thuộc NEps(c).

B3: Gán N = số nút trên đồ thị.

B4: Nếu N không chứa bất kỳ điểm nhân nào thì dừng.

B5: Lấy điểm nhân c trong N.

B6: Gán X = tập các điểm mà từ c có thể đi tiếp đến B6.1: Tạo cụm chứa X  {c}

B6.2: Gán N = N \ (X  {c}) B7: Quay lại B4.

Thuật toán DBSCAN yêu cầu hai tham số là Eps và MinPts từ người dùng, việc xác định giá trị của hai tham số này có ảnh hưởng lớn đến các cụm

47

được phát hiện. Tham số Eps xác định tập các đối tượng lân cận của một đối tượng dữ liệu. MinPts là tham số ngưỡng mật độ của các đối tượng dữ liệu.

Việc xác định giá trị Eps và MinPts tối ưu là một bài toán cần tìm lời giải, bởi vì nếu các giá trị đủ lớn thì mọi điểm thuộc cụm đó đều phải thỏa mãn. Tuy nhiên nếu các giá trị đó nhỏ thì có thể rơi vào trường hợp mọi điểm trong tập dữ liệu đều thuộc một cụm.

Thuật toán này sử dụng cấu trúc cây R*-tree để lưu trữ tập dữ liệu.

DBSCAN có độ phức tạp tính toán chưa dùng cây chỉ mục để xử lý là O(n2) và sau khi dùng R*tree là O(n*log(n)).

2.6.5.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 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 cụm dữ liệu 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ảng 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 của các điểm dữ liệu đó là khoảng cách nhân và khoảng cách liên tụ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 sắp xếp. Thứ tự dựa trên cơ sở các điểm dữ liệu mà có khoảng cách nhân nhỏ

48

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 chọn 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.