Đề tài Nghiên cứu một số phương pháp khai thác dữ liệu và ứng dụng

ng III.1 Phân cấp (Hierachical): Đối với phương pháp clustering phân cấp, kết quả các cluster được cấu trúc theo dạng cây được tạo ra bởi phân chia đệ quy (recursive partitioning) hoặc bằng cách kết hợp (combining, tích tụ-agglomerative) các cluster trước đó. Các cluster có thể có các cluster con bên trong. a. Phân chia (Divise): Ban đầu, xem tập dữ liệu như một cluster và chia thành 2 cluster mới trong mỗi bước tiếp theo. Theo đó, số lượng cluster tăng lên một sau mỗi bước lặp. b. Tích tụ (Agglomerative): Mỗi điểm dữ liệu được xem như một cluster và kết 2 cluster thành một cluster mới trong mỗi bước kết tiếp. Vì thế, số lượng cluster giảm đi một sau mỗi bước lặp. III.2 Không phân cấp (Nonhierachical): Đối với phương pháp clustering không phân cấp, kết quả quá trình clustering một tập dữ liệu thành một số (cho trước) cluster và mỗi cluster không có Thủ tục clustering Phân cấp Không phân cấp Tích tụ Phân chia Ngưỡng song song Tối ưu phân hoạchNgưỡng tuần tự Các PP biến đổi Các PP lấy trọng tâmCác PP liên kết Hoàn toàn Trung bình LK đơn Phương pháp Ward chứa lớp con nào bên trong nó. Một tên khác của clustering không phân cấp là clustering theo kiểu phân hoạch (partition). - Ngưỡng tuần tự: tiến trình clustering này thực hiện việc gán các điểm dữ liệu theo cơ chế tuần tự. Thuật giải dùng cho phương pháp này là K-means tuần tự. - Ngưỡng song song: tiến trình này ứng dụng các lý thuyết tính song song để cải tiến độ phức tạp của phương pháp ngưỡng tuần tự. Phương pháp này còn cho phép thực hiện trên bộ nhớ lớn hơn nhiều so với bộ nhớ thực của máy. Thuật giải K-means song song được sử dụng trong trường hợp này. - Tối ưu phân hoạch: đây là phương pháp tổng quát hóa thuật giải K-means. Nó sẽ gán các điểm dữ liệu vào các cluster theo phương pháp xác suất. Phương pháp này sử dụng thuật giải K-means mờ. IV. Các thuật giải clustering tĩnh IV.1 Thuật giải clustering phân cấp 1. Thuật giải Đối với phương pháp clustering phân cấp, có 4 biến thể phổ biến: liên kết đơn, liên kết hoàn toàn, liên kết trung bình và phương pháp lấy trọng tâm. Bốn phương pháp này đều có thuật giải chung như sau: • Bước 1 [Khởi tạo]: Tạo n cluster, mỗi cluster chứa chính xác một điểm dữ liệu từ tập dữ liệu. Khoảng cách hoặc độ tương tự giữa các đối tượng là biết được và được định nghĩa. Hầu hết các phương pháp lưu khoảng cách trong ma trận D (nxn) chiều. • Bước 2 [Tìm hàng xóm]: Tìm hai cluser i và j có khoảng cách gần nhất hoặc tương tự nhau nhất trong ma trận D. • Bước 3[Tích tụ]: Trộn hai cluster i và j thành một cluster mới (ij). Khoảng cách phải được tính lại theo phương pháp mà ta đã chọn. Việc thay đổi đó phải được thực hiện trên ma trận là xóa dòng i, cột j và thêm vào một dòng và một cột mới tương ứng với cluster mới. Số cluster và chiều của cluster giảm đi một trong mỗi lần lặp. Lặp lại bước 2 & 3 cho đến khi số cluster không thay đổi nữa. Chúng ta có thể thấy rằng, thuật giải dùng một ma trận khoảng cách D làm điều kiện clustering. Ngoài ra, phương pháp này không yêu cầu xác định trước số cluster nhưng bù lại, nó đòi hỏi phải có một điều kiện dừng. Sau khi kết thúc thuật giải, chúng ta sẽ có một tập các cluster ở dạng cây được gọi là cây phả hệ (dendrogram). Để xác định k cluster cần thiết, ta chỉ việc cắt cây nầy tại một mức nào đó (desired level) và mỗi thành phần liên thông tạo ra như vậy ứng với một cluster 2. Điều kiện xác định khoảng cách giữa hai cluster • Liên kết đơn (single linkage): sử dụng phương pháp tìm người láng giềng gần nhất (k-nearest neighbors) để tìm các cluster. Khoảng cách giữa hai cluster là khoảng cách giữa hai mẫu tin gần nhau nhất trên hai cluster. d(Cij, Ck) = min { d(Ci, Ck), d(Cj, Ck) } với k = 1, 2, …, n; k ≠ i,j; Ci là tập các mẫu tin trong cluster i. • Liên kết hoàn toàn (complete linkage): sử dụng phương pháp tìm người láng giềng xa nhất. Khoảng cách giữa hai cluster là khoảng cách xa nhất của hai điểm trên hai cluster. d(Cij, Ck) = max { d(Ci, Ck), d(Cj, Ck) } • Liên kết trung bình (Average linkage): khoảng cách giữa hai cluster là khoảng cách trung bình giữa các điểm trên hai cluster. kij n l n m ml kij nn zzd CCd ij k •= ∑ ∑= =1 1 ),(),( • Phương pháp lấy trọng tâm: khoảng cách giữa hai cluster là khoảng cách giữa hai trọng tâm của 2 cluster. ),(),( kijkij CCdCCd = Với ijC là trọng tâm của cluster (ij), kC là trọng tâm của cluster k. 3. Đánh giá - Ưu điểm: • Dễ dàng sử dụng mọi cách đo khoảng cách hay độ tương tự • Có khả năng áp dụng cho nhiều loại thuộc tính • Tính linh hoạt - Nhược điểm: • Điều kiện dừng mập mờ • Không thể hủy những thao tác đã thực hiện trước đó • Độ phức tạp lớn: O(n2) trong đó n là số mẫu tin trong cơ sở dữ liệu. IV.2 Thuật giải clustering không phân cấp IV.2.1 Thuật giải k-means cổ điển. Các thuật giải này cho ra tập các cluster rời nhau và do đó, công việc sẽ đạt hiệu quả khi một tập cho trước bao gồm một số lớp riêng biệt. Thuật giải clustering k-means là một thuật giải hiệu quả (effective) và dễ hiểu (straightforward) để tìm ra các cluster trong dữ liệu. 1. Mô tả thuật giải: - Bước 1: Hỏi người dùng số cluster k cần được phân hoạch dữ liệu vào đó - Bước 2: Gán ngẫu nhiên k mẫu tin làm vị trí khởi đầu cho k trọng tâm cluster. - Bước 3: với mỗi mẫu tin, tìm trọng tâm cluster gần nhất. Như vậy, theo một nghĩa nào đó (in a sense), mỗi trọng tâm cluster sở hữu (owns) một tập các mẫu tin, do đó, nó đại diện cho một phân hoạch của tập dữ liệu. Chúng ta có k cluster C1, C2, …, Ck, - Bước 4: với mỗi cluster trong k cluster, tìm ra trọng tâm của cluster (centroid) và cập nhật vị trí của trung tâm (center) cluster bằng giá trị mới của centroid. - Bước 5: lặp lại các bước từ 3 đến 5 cho tới khi có sự hội tụ (converence) hay gặp một điều kiện kết thúc (terminal criterion). Tiêu chuẩn gần nhất trong bước 3 thường là khoảng cách Euclide mặc dù có thể áp dụng tiêu chuẩn khác. Trọng tâm của cluster trong bước 4 được tìm như sau: giả sử ta có n điểm dữ liệu: (a1, b1, c1), (a2, b2, c2), …, (an, bn, cn), trọng tâm của các điểm này là trung bình (trung tâm) độ lớn của các điểm này và được đặt tại điểm ( )∑ ∑∑ ncnbna iii /,/,/ Chẳng hạn, ta có các điểm (1,1,1), (1,2,1), (1,3,1) và (2,1,1) thì trọng tâm là: )00.1,75.1,25.1( 4 1111, 4 1321, 4 1111 =⎟⎠ ⎞⎜⎝ ⎛ +++++++++ Thuật giải kết thúc khi trọng tâm không thay đổi. Nói cách khác, thuật giải kết thúc khi với mọi cluster C1, C2, …, Ck, các mẫu tin được sở hữu bởi trung tâm cluster còn lại trong cluster. Ngoài ra, thuật giải có thể kết thúc khi vài tiêu chuẩn hội tụ được thõa mãn chẳng hạn như không có sự giảm đáng kể (no significant shrinkage) trong tổng bình phương lỗi. ∑∑ = ∈ = k i Cp i i mpdSSE 1 2),( Trong đó, iCp∈ là một điểm dữ liệu trong cluster I và mi là trọng tâm của cluster i. 2. Đánh giá: - Ưu điểm: • Dễ dàng làm việc với các kiểu chuẩn hóa • Cho phép ứng dụng các lý thuyết tính toán song song • Không bị tác động bởi thứ tự của dữ liệu. • Độ phức tạp tương đối hiệu quả: O(tkn) trong đó t là số lần lặp, k là số cluster, n là tổng số mẫu tin. Thông thường, k, t << n. - Nhược điểm: • Phụ thuộc nhiều vào việc khởi tạo các trọng tâm cluster (centroid) • Thuật giải thường dừng tại một mức tối ưu cục bộ. Mức tối ưu toàn cục có thể tìm thấy nếu áp dụng các thuật giải như thuật giải di truyền… • Cần phải chỉ định số cluster k trước. • Nhạy cảm với nhiễu và dữ liệu outlier: một đối tượng với giá trị rất lớn có thể làm méo mó sự gom nhóm hay hình dạng của cluster. • Thiếu tính uyển chuyển • Chỉ áp dụng tốt cho các thuộc tính mang giá trị số • Không thích hợp cho việc phát hiện các cluster có dạng lõm. IV.2.2 Thuật giải k-medoids Một biến thể của thuật giải k-means là k-medoids. Thuật giải k-medoids sử dụng khái niệm điểm đại diện (medoid) thay vì centroid. Ý tưởng chính của nó là: Thay vì lấy giá trị trung bình của các đối tượng trong cluster làm điểm tham chiếu, ta lấy một đối tượng trong cluster làm điểm đại diện gọi là medoid sao cho nó là điểm nằm gần trung tâm cluster nhất. Tập các medoid ban đầu có thể được chọn tùy ý. Sau đó, lặp lại việc thay thế một medoid bởi một đối tượng không phải là medoid chừng nào tổng bình phương sai số của các mẫu tin trong kết quả gom nhóm còn được cải thiện. Thuật giải: Input: số cluster mong muốn k và CSDL chứa n đối tượng Output: một tập k cluster sao cho tối thiểu hóa tổng độ khác nhau giữa mọi đối tượng với medoids gần nhất của chúng. Mã giả: Function KMedoidsMethod(DataSet, k) Begin Init: m1, m2, …, mk; Repeat Phân loại n đối tượng trong DataSet theo mi gần nhất; Tính toán hàm mục tiêu f= tổng độ khác nhau giữa dataj với mi gần nhất; // hoán đổi mi với đối tượng y không là medoid nếu nó làm giảm hàm mục tiêu Foreach ((y in DataSet) && (y is not medoid)) If (f(y) < f(mi)) then Chọn y làm medoid mới thay mi; Until không có thay đổi trong mi; Return m1, m2, …, mk; End. V. Cơ chế clustering động V.1. Giới thiệu Các thuật giải giới thiệu trên đây chỉ phù hợp khi tập dữ liệu có sẵn tại một thời điểm nhất định hay không có thay đổi. Vì thế, chúng còn được gọi là các thuật giải clustering tĩnh. Trong thực tế, tập dữ liệu có thể bị thay đổi thường xuyên bởi việc cập nhật dữ liệu mới hay giải phóng dữ liệu cũ, và do đó, cần phải thiết kế một thuật giải clustering động để cập nhật các cluster khi có thay đổi tương đối trên tập dữ liệu. Việc clustering một khối lượng dữ liệu lớn là mất nhiều thời gian. Vì thế, có một cách tiếp cận tương đối hiệu quả là chúng ta bắt đầu clustering dữ liệu No<N. Sau đó, với mỗi lần có n (N-No) đối tượng dữ liệu mới thêm vào hay được giải phóng và làm ảnh hưởng đáng kể đến các thể hiện kết quả clustering, ta sẽ tiến hành việc clustering trên tập dữ liệu mới này. Nếu kết quả clustering thay đổi không đáng kể thì ta có thể khẳng định tiến trình đã ổn định. Cách tiếp cận này hiệu quả khi N là rất lớn và chi phí clustering không tuyến tính với N. Ngoài ra, ta cần phải biết số cluster và kiểu cluster sinh ra bởi dữ liệu cũng như ảnh hưởng của dữ liệu mới lên kết quả phân lớp. Đối với clustering động, dữ liệu mới có thể là được nhập thêm vào các cluster đang tồn tại hoặc hình thành các cluster mới hoặc xuất hiện như các dữ liệu lạc loài không phụ thuộc vào một cluster nào cả. Mặt khác, dữ liệu mới nhập thêm vào các cluster cũng có thể làm cho cluster phình to ra và thay đổi tính chất phân bố dẫn đến việc tách cluster thành hai hay nhiều cluster khác. V.2. Khảo sát các tình huống thay đổi trên tập dữ liệu Trong phần này, chúng ta sẽ xem xét các trường hợp thay đổi trên kết quả clustering. Do dữ liệu mới là tương đối nhiều (n) nên kết quả cluster trong lần trước có thể xẩy ra các tình huống sau: a. Sự hấp thu dữ liệu (Absorption of data): dữ liệu mới được thêm vào trong một số cluster, các cluster khác không bị thay đổi. b. Trộn các cluster (Merging of clusters): hai hay nhiều cluster đang tồn tại có thể được trộn lại hoặc được kết nối thành một bởi dữ liệu mới. c. Sự hình thành cluster mới: các cluster đang tồn tại có thể bị tách ra thành các cluster mới do sự ảnh hưởng của tập dữ liệu thêm vào làm thay đổi tính chất phân bố của cluster đó. d. Dữ liệu lạc loài: là dữ liệu mới thêm vào nhưng không thuộc một cluster nào cả. Dữ liệu này là các dữ liệu mà kĩ thuật clustering không thành công. e. Một cluster có thể xuất hiện như hai hoặc nhiều cluster vì một số lớn dữ liệu được thêm vào. Trường hợp này xảy ra khi một số dữ liệu mới đã đến. V.3. Các nguyên lý clustering động: V.3.1 Sự hấp thu dữ liệu Việc hấp thu dữ liệu trong một cluster đang tồn tại dựa vào các nguyên lý sau: a. Một lượng dữ liệu mới p có thể được hấp thu trong cluster gần nhất nó Ci. Khoảng cách giữa Ci và p có thể là khoảng cách Euclide nhỏ nhất của tất cả các điểm trong Ci với p. b. Gọi qo là lượng dữ liệu trong Ci gần nhất với p. Khi đó, p sẽ được nhập thêm vào Ci nếu các khoảng cách lân cận gần nhất của các điểm qi nằm trong lân cận của qo là tương tự với khoảng cách giữa p và qo. Gọi ∑ =+= m i idm d 01 1 trong đó, di là khoảng cách giữa qi với lân cận gần nhất của nó. m là số lượng dữ liệu trong qo. Thông thường, m được chọn là số nguyên nhỏ nhất lớn hơn 10% số dữ liệu có trong Ci. Gọi khoảng cách giữa p và qo là d. Khi đó, p sẽ được nhập thêm vào Ci nếu dd ≈ . V.3.2 Trộn các cluster Việc trộn các cluster dựa vào và nguyên lý sau: a. Chỉ có các cluster nhập thêm dữ liệu mới tại các giai đoạn trước được xem xét để trộn. b. Nếu khoảng cách giữa một cluster còn lại thõa a ở trên và bất kỳ cluster nào khác bị giảm đi thì chỉ hai cluster này được xem xét để trộn. Khoảng cách sẽ giảm đi nếu việc nhập thêm dữ liệu làm cluster đó phình ra. Thông thường, khoảng cách được tính theo khoảng cách Euclide tối thiểu giữa các điểm trong 2 cluster. c. Với hai cluster Ci và Cj, gọi p thuộc Ci và q thuộc Cj sao cho khoảng cách giữa p và q là nhỏ nhất. Khi đó, hai cluster có thể được trộn với nhau tại hai điểm này. d. Vai trò của Ci và Cj là như nhau đối với p và q nếu việc trộn xảy ra. Xét m lân cận gần nhất của p và m lân cận gần nhất của q trong Ci U Cj. Gọi mp,i là số lân cận gần nhất của p mà thuộc Ci, .v.v. Ta có: mp,i + mp,j = m = mq,i + mq,j. Ta xét số lượng J như sau: m m m m J iqjp ,, += Khi đó, Ci và Cj được trộn nếu J = 1 và Ci và Cj sẽ không được trộn nếu J = 0. Chúng ta cũng có thể sử dụng một ngưỡng T sao cho 0 < T < 1 để quyết định hai cluster có được trộn hay không. Nếu J>=T thì hai cluster được trộn. V.3.3 Dò tìm dữ liệu lạc loài Dữ liệu không được nhập thêm trong bất kỳ cluster nào gọi là dữ liệu lạc loài và có thể hình thành nên các cluster mới. Chúng ta sử dụng thuật giải sau để tìm các cluster mới đó. a. Tìm cây bao trùm tối thiểu của dữ liệu mới mà không được nhập thêm vào bất kì cluster nào trong bước trước. b. Tìm khoảng cách trung bình của mỗi tập dữ liệu và lân cận gần nhất của nó trong các cluster đang tồn tại. Gọi nó là 0d . Xóa các cạnh có chiều dài lớn hơn 0dα với 1>α . Cây bao trùm tối thiểu bây giờ biến thành một tập các cây con. c. Nếu số nút trong một cây con ít hơn một số cho trước mo thì xem tất cả dữ liệu của cây con như là dữ liệu lạc loài. Ngược lại, một cây con tương ứng với một cluster mới. V.4 Chia cluster Một lượng dữ liệu lớn mới được nhập vào có thể thay đổi cấu trúc của một cluster dẫn đến việc cluster phình ra và có thể bị tách thành 2 hay nhiều cluster. Tiêu chuẩn phân chia sẽ được kiểm tra tại một khoảng thời gian là trΔ . Các thuật giải chia cluster dựa trên 2 nguyên lý sau: a. Mật độ tại mỗi vùng dữ liệu trong cluster là tính được. Việc ước lượng mật độ tại một điểm p có thể nhận được bằng cách tiếp cận dựa vào nhân hoặc bằng cách tiếp cận k điểm lân cận gần nhất. b. Gọi mật độ cao nhất và thấp nhất của các điểm là hμ và lμ . Xét phân số )/( lh μμβ − . Gọi )(0 lh μμβμ −= . Bỏ qua tất cả các điểm có mật độ thấp hơn 0μμ +l và phát sinh cây bao trùm tối thiểu với dữ liệu còn lại. Tìm độ dài trung bình các cạnh của cây. Nếu chiều dài cạnh lớn nhất lớn hơn nhiều so với chiều dài cạnh trung bình thì xóa cạnh này thì mỗi cây con tạo nên một cluster riêng biệt. V.5 Thuật giải DBSCAN Hiện nay, có nhiều thuật giải clustering động như DBRS, VLDB, OPTICS… Đa số các thuật giải này clustering dựa vào mật độ hay phân bố (density). Vì thế, trong phần này, chúng tôi chỉ trình bày thuật giải DBSCAN (Density Based Spatial Clustering of Applications with Noise) như một cơ sở cho các thuật giải clustering động nói chung. Mặt khác, thuật giải DBSCAN còn có hai lợi điểm nữa là: - DBSCAN là một trong những thuật giải hữu hiệu nhất cho CSDL lớn - DBSCAN có thể được áp dụng cho bất kỳ CSDL nào chứa dữ liệu từ một không gian trọng số (metric) bất kỳ, chỉ cần định nghĩa một hàm khoảng cách. Thuật giải này cũng có thể áp dụng như thuật giải clustering tĩnh. Ý tưởng chính của nó là clustering dựa vào phân bố hay mật độ (density). Với mỗi đối tượng của một cluster lân cận với một bán kính cho trước (Eps) phải chứa ít nhất một số MinPts đối tượng. Đặc trưng chính của phương pháp này là: - Phát hiện các cluster với hình dạng bất kỳ - Quản lý được nhiễu và outlier - Chỉ quét một lần - Cần có các tham số làm điều kiện dừng. Trước hết, chúng ta sẽ xem xét một số khái niệm và các định nghĩa liên quan đến clustering động. V.5.1 Một số khái niệm Phân bố trong lân cận của một điểm được xác định bằng một hàm đo khoảng cách giữa hai đối tượng, ký hiệu là dist(p,q) với p, q là hai điểm dữ liệu. Eps-lân cận của một điểm p (Eps-neighborhood of a point), ký hiệu là NEps(p), xác định bởi: }),(|{)( EpsqpdistDqpN Eps ≤∈= MinPts là số điểm dữ liệu tối thiểu trong lân cận Eps của một điểm dữ liệu. Đối tượng nòng cốt (core point): là đối tượng mà lân cận Eps của nó chứa ít nhất là MinPts đối tượng khác. Đối tượng biên (border point): là đối tượng nằm trên biên của cluster. Đối tượng nhiễu (noise point): là những đối tượng không phải đối tượng nòng cốt cũng không phải đối tượng biên. V.5.2 Các định nghĩa a. Định nghĩa 1: Phân bố có thể đi đến trực tiếp Một đối tượng p phân bố có thể đi đến trực tiếp từ một đối tượng q wrt.Eps và MinPts nằm trong tập đối tượng D nếu: - p thuộc NEps(q) và - Card(NEps(q)) >= MinPts (điều kiện cho đối tượng nòng cốt) b. Định nghĩa 2: Phân bố có thể đi đến được Một đối tượng p là phân bố có thể đi đến được từ một đối tượng q wrt.Eps và MinPts nằm trong tập đối tượng D, ký hiệu là p>Dq nếu có một dây chuyền các đối tượng p1,p2, …, pn với p1=q, pn=p sao cho pi thuộc D và pi+1 là phân bố có thể đi đến trực tiếp từ pi wrt.Eps và MinPts. c. Định nghĩa 3: Phân bố liên thông Một đối tượng p là phân bố liên thông với đối tượng q wrt.Eps và MinPts trong tập các đối tượng D nếu có một đối tượng o thuộc D sao cho cả p và q đều là phân bố có thể đi đến được từ o wrt.Eps và MinPts. Phân bố liên thông là một quan hệ đối xứng và phản xạ. Bây giờ, ta có thể định nghĩa lại khái niệm cluster dựa trên phân bố như sau: Một cluster là một tập các đối tượng phân bố liên thông có độ phân bố có thể đi đến được là lớn nhất và nhiễu là tập các đối tượng không thuộc vào bất kỳ cluster nào. d. Định nghĩa 4: Cluster Cho D là một tập các đối tượng. Một cluster C wrt.Eps và MinPts trong D là một tập con khác rỗng của D thõa các điều kiện sau: - Tính cực đại: với mọi p,q thuộc D: nếu p thuộc C và q>Dp wrt.Eps và MinPts thì q thuộc C. - Tính liên thông: với mọi p,q thuộc C: p là phân bố liên thông với q wrt.Eps và MinPts trong D. e. Định nghĩa 5: Đối tượng lạc loài nhiễu (noise) Cho C1,C2, …, Ck là các cluster wrt.Epsi và MinPtsi trong D với i=1,2,…,k. Ta định nghĩa nhiễu là tập các đối tượng trong cơ sở dữ liệu D mà không thuộc vào bất kỳ cluster Ci nào, nghĩa là }:|{ iCpiDpnoise ∉∀∈= Cho hai tham số Eps và MinPts, chúng ta có thể phát hiện một cluster qua hai bước như sau: - Chọn một đối tượng tùy ý từ CSDL thõa mãn điều kiện đối tượng nòng cốt làm hạt giống. - Tìm tất cả các đối tượng có thể đi đến được từ hạt giống này và hình thành nên cluster. f. Bổ đề 1: Cho p là một đối tượng trong D và |NEps(p)| >= MinPts thì tập O = {o | o thuộc D và o là phân bố có thể đi đến được từ p wrt.Eps và MinPts} là một cluster wrt.Eps và MinPts. g. Bổ đề 2: Cho C là một cluster wrt.Eps và MinPts và p là một điểm bất kỳ trong C sao cho |NEps(p)|>=MinPts thì C={o | o là phân bố có thể đi đến được từ p wrt.Eps và MinPts}. V.5.3 Thuật giải DBSCAN tĩnh Về mặt lý tưởng, chúng ta phải biết giá trị các tham số Eps và MinPts thích hợp cho từng cluster và ít nhất một đối tượng tương ứng với cluster đó. Nhưng không phải dễ dàng để lấy được những thông tin này cho mọi cluster trong CSDL. Tuy nhiên, có một cách tìm đơn giản để xác định các tham số Eps và MinPts cho cluster nhỏ nhất (thinnest) trong CSDL một cách hiệu quả. Thuật giải DBSCAN sử dụng các tham số này như các biến toàn cục, tức là cho mọi cluster. Đây là một cách tốt để có độ phân bố nhỏ nhất và không phải quan tâm đến nhiễu. Hình 2. Sự hình thành các cluster. Thuật giải: - Nếu Eps và MinPts đã được xác định, chọn ngẫu nhiên một đối tượng p - Tìm các vùng lân cận của p (mọi đối tượng có thể đi đến trực tiếp từ p wrt.Eps và MinPts) bằng cách thực hiện truy vấn vùng (region query) hay tìm kiếm trên R*-Tree - Nếu lân cận của p thưa thớt hay chứa ít hơn MinPts đối tượng thì p được tạm gán nhãn là nhiễu. Thuật giải sẽ xét đối tượng tiếp theo trong CSDL. - Ngược lại, một cluster được hình thành và chứa tất cả các đối tượng trong lân cận của p. Sau đó, lân cận của những điểm này sẽ được khảo sát để xem liệu nó có được thêm tiếp vào cluster này hay không. - Nếu cluster không thể mở rộng thêm được nữa, thuật giải chọn ngẫu nhiên một đối tượng p khác chưa xét và lặp lại quá trình trên. - Thuật giải sẽ lặp cho đến khi mọi đối tượng đều được gom nhóm hay được đánh dấu là nhiễu. Với một CSDL có n mẫu tin, cần phải truy vấn vùng n lần. Hình 3. Kết quả clustering bởi DBSCAN. Đánh giá: - Ưu điểm: • Có thể phát hiện các cluster có hình dạng bất kỳ • Chỉ yêu cầu một hàm đo khoảng cách và hai tham số đầu vào: Eps và MinPts. • Cho ra kết quả tốt và thực thi hiệu quả trên nhiều tập dữ liệu. - Nhược điểm: • Không thích hợp cho việc tìm các cluster trong CSDL cực lớn • Nếu tập dữ liệu có mật độ thay đổi lớn, thuật giải quản lý kém hiệu quả. - Độ phức tạp: • Thông thường, MinPts = 4. Vì thế, ta chỉ còn phải xác định Eps. Để xác định Eps, DBSCAN tính toán khoảng cách giữa một đối tượng với 4 đối tượng khác với mọi mẫu tin trong toàn CSDL. Mặt khác, DBSCAN dựa trên cấu trúc R*-Tree. Độ phức tạp trung bình cho một truy vấn vùng là O(log(N)) • Vậy độ phức tạp của thuật giải DBSCAN là O(N log(N)). V.5.4 Thuật giải DBSCAN động Thuật giải trên áp dụng cho cơ sở dữ liệu tĩnh. Tuy nhiên chúng ta có thể biến đổi đôi chút để có thể áp dụng cho dữ liệu động. Trước tiên, ta sẽ tìm hiểu một số định nghĩa khác và cùng khảo sát các trường hợp cập nhật động các cluster sau khi thêm hoặc xóa dữ liệu. V.5.4.1. Các định nghĩa Sau khi thêm vào vài đối tượng p, các đối tượng trong NEps(p) có thể thay đổi đặc tính đối tượng nòng cốt của chúng, nghĩa là các đối tượng không phải nòng cốt có thể trở thành các đối tượng nòng cốt. Bởi vì, các phân bố liên thông mới có thể được thiết lập tạo ra một dây chuyền p1, p2, …, pn, p1 = r, pn = s với pi+1 là phân bố có thể đi đến trực tiếp từ pi và hai đối tượng r, s không có phân bố có thể đi đến được với nhau trước khi dữ liệu mới thêm vào. Tương tự, khi xóa vài đối tượng p, các đối tượng nòng cốt trong NEps(p) có thể trở thành đối tượng không nòng cốt, nghĩa là không còn tồn tại dây chuyền p1, p2, …, pn, p1=r, pn=s để r và s có phân bố có thể đi đến trực tiếp với nhau. Định nghĩa 6: Các đối tượng bị ảnh hưởng Gọi D là một CSDL gồm đối tượng q và p là một vài đối tượng (ở trong hoặc ngoài D). Chúng ta định nghĩa tập các đối tượng trong D bị ảnh hưởng bởi việc thêm hoặc xóa p như sau: ( ) ( ) ( ){ }oqpNoqpNpAffected pDEpsEpsD }{| ∪>∧∈∃∪= Bổ đề 1: Cho D là một tập các đối tượng và p là các đối tượng. Khi đó: ( ) { } { }oqqoqqpAffectedoDo pDpDD }{}\{ ||: ∪>=>⇒∉∈∀ Bổ đề 2: Cho D là một tập các đối tượng. Ngoài ra, D*=D U {p} sau khi thêm vào một đối tượng p hoặc D*=D\{p} sau khi xóa đối tượng p và gọi c là một đối tượng nòng cốt trong D*. Khi đó, C={o | o>D*c} là một cluster trong D* và ( )pAffectedC D⊆ qcqNqqNqqq DEpsEps *),('),'(:', >∈∈∃⇔ , q là đối tượng nòng cốt trong D* và q’ là đối tượng nòng cốt trong D U {p}. Định nghĩa 7: Các đối tượng hạt giống cho việc cập nhật Cho D là một tập các đối tượng và p là một đối tượng được thêm hoặc xóa. Ta có các khái niệm sau: - UpdSeedIns = {q | q là một đối tượng nòng cốt trong D U {p}, tồn tại q’: q’ là đối tượng nòng cốt trong D U {p} nhưng không ở trong D và q thuộc NEps(q’)} - UpdSeedDel = { q | q là một đối tượng nòng cốt trong D \ {p}, tồn tại q’: q’ là đối tượng nòng cốt trong D nhưng không ở trong D \ {p} và q thuộc NEps(q’)} V.5.4.2. Trường hợp thêm dữ liệu Dựa vào các khái niệm trên đây, khi thêm một đối tượng p vào CSDL, ta phân biệt các trường hợp sau để điều chỉnh thuật giải DBSCAN làm việc với dữ liệu động. a. Lạc loài UpdSeedIns là rỗng, nghĩa là không có các đối tượng nòng cốt mới sau khi thêm p. Vì thế, p là một đối tượng lạc loài và không có thay đổi nào khác. b. Tạo lập UpdSeedIns chỉ chứa các đối tượng nòng cốt không phụ thuộc vào một cluster nào trước khi thêm p, nghĩa là, chúng là các đối tượng lạc loài hoặc bằng p và cluster mới