- PHÂN CỤM DỮ LIỆU DỰA TRÊN ĐỒ THỊ SỬ DỤNG CÂY KHUNG CỰC TIỂU. - PHÂN CỤM DỮ LIỆU DỰA TrRÊN ĐỒ THỊ SỬ DỤNG CÂY KHUNG CỰC TIỂU. - Mêtric trên dữ liệu hỗn hợp. - CSDL Database Cơ sở dữ liệu. - KPDL Data mining Khai phá dữ liệu. - PCDL Clustering Data Phân cụm dữ liệu. - DW Data Warehouse Kho dữ liệu. - DM Data Mart Kho dữ liệu cục bộ. - KDD Knowledge Discovery in Data Khám phá tri thức trong dữ liệu MDL Minimum Description Length Chiều dài tối thiểu. - Hình 1.3: Phân cụm tập S. - Hình 1.5: Hai cụm dữ liệu có thể t m ƣợc nhờ DBSCAN. - H nh 3 14 ảng dữ liệu thử nghiệm lần 2. - Hiện nay, phân cụm dữ liệu vẫn là bài toán ng ƣợc nhiều ngƣời quan tâm nghiên cứu, tuy nhiên, trong các thuật toán thƣờng yêu cầu ngƣời ùng xác ịnh trƣớc số lƣợng cụm. - Trong luận v n n y em tr nh y khảo cứu của tác giả về tiếp cận phân cụm dữ liệu sử dụng cây khung cực tiểu Đặc biệt i sâu v o kỹ thuật phân cụm của thuật toán 2-MSTs.. - Trong chƣơng n y ể l m rõ hơn kỹ thuật phân cụm dữ liệu dựa trên đồ thị sử dụng cây khung cực tiểu , một số vấn ề li n qu n ến cây khung cực tiểu ƣợc tr nh y ngoài ra sẽ phân tích kỹ thuật phân cụm cây khung cực tiểu, tìm hiểu thuật toán phân cụm 2-MSTs.. - Khám phá tri thức trong các cơ sở dữ liệu là một quy trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với những t nh n ng: hợp thức, mới, khả ích và có thể hiểu ƣợc Đây l một quá trình nghiên cứu một khối lƣợng dữ liệu lớn b ng các phƣơng tiện tự ộng. - Mục ch của sự phát hiện tri thức và khai phá dữ liệu chính là tìm ra các mẫu v các m h nh ng t n t i trong các cơ sở dữ liệu nhƣng vẫn còn bị che khuất bởi hàng núi dữ liệu.. - Khai phá dữ liệu có thể ƣợc xem nhƣ l một kết quả của sự tiến hóa tự nhiên của công nghệ thông tin. - Lựa chọn dữ liệu: L ƣớc ta lựa chọn tập dữ liệu n ầu theo một số tiêu chí nhất ịnh từ tập dữ liệu lớn nhƣ: t se t w rehouses h y t repositories. - Tiền xử lý dữ liệu: ƣớc này làm s ch dữ liệu (xử lý với dữ liệu kh ng ầy ủ, dữ liệu nhiễu, dữ liệu không nhất quán. - rút gọn dữ liệu (sử dụng hàm nhóm và tính t ng, các phƣơng pháp nén ữ liệu, sử dụng histograms, lấy mẫu. - rời r c hóa dữ liệu (rời r c hóa dựa vào histograms, dựa vào entropy, dựa vào phân khoảng ) Qu ƣớc này, dữ liệu sẽ nhất quán ầy ủ ƣợc rút gọn v ƣợc rời r c hóa.. - Đổi dạng: L ƣớc chuẩn hóa và làm mịn dữ liệu ể ƣ ữ liệu về d ng phù hợp nhất nh m phục vụ cho các kỹ thuật khai phá ở ƣớc sau.. - Khai phá dữ liệu (Data mining): Đây l ƣớc áp dụng những kỹ thuật phân tích (phần nhiều là các kỹ thuật của học máy) nh m ể khai thác dữ liệu, trích chọn ƣợc những mẫu thông tin, những mối liên hệ ặc biệt trong dữ liệu Đây ƣợc xem l ƣớc quan trọng và tốn nhiều thời gian nhất của toàn quá trình KDD.. - Biểu diễn: Các mẫu thông tin và mối liên hệ trong dữ liệu ã ƣợc khám phá ở ƣớc tr n ƣợc chuyển d ng và biểu diễn ở một d ng gần gũi với ngƣời sử dụng nhƣ thị,. - Thu thập các tri thức từ dữ liệu có sẵn. - Nhiều cơ qu n ã thu nhập ƣợc nhiều n m một khối lƣợng lớn các dữ liệu họ sẽ phải làm gì và có thể làm gì với chúng?.. - Ngƣời t lƣu trữ các dữ liệu vì họ ngh r ng có thể có những của cải áng quý n o nó ng tiềm ẩn trong chúng. - Trong kinh doanh, dữ liệu hàm chứa các thông tin về thị trƣờng, về các ối thủ và về các khách hàng. - Chỉ có một lƣợng khá nhỏ (th ng thƣờng vào khoảng 5% ến 10%) dữ liệu ã ƣợc thu thập lu n lu n ƣợc phân tích.. - Các dữ liệu có thể chƣ o giờ ƣợc phân tích vẫn tiếp tục ƣợc thu thập rất tốn kém với ý ngh lo x r ng sau này sẽ có một cái g ó rất quan trọng có thể bỏ qua.. - Lƣợng dữ liệu quá lớn ối với cách thức phân tích c iển Đ i khi t kh ng thể xem ƣợc hoặc chứ ƣợc tất cả trong bộ nhớ.[9]. - Dữ liệu. - i u Dữ liệu. - Phân cụm dữ liệu (Data clustering) là quá trình phân chia một tập dữ liệu n ầu thành các cụm dữ liệu sao cho các phần tử trong một cụm "tƣơng tự". - Số các cụm dữ liệu ƣợc phân ở ây có thể ƣợc xác ịnh trƣớc hoặc có thể ƣợc tự ộng xác ịnh theo phƣơng pháp phân cụm. - Trong học máy PC L ƣợc xem là vấn ề học không có giám sát (unsupervised learning), vì nó phải giải quyết vấn ề tìm một cấu trúc trong tập hợp dữ liệu chƣ iết trƣớc các thông tin về cụm hay các thông tin về tập huấn luyện mà chỉ ơn thuần dựa v o t nh tƣơng ng củ các ối tƣợng dữ liệu. - Trong nhiều trƣờng hợp, nếu phân lớp ƣợc xem là vấn ề học có giám sát thì PCDL là một ƣớc trong phân lớp dữ liệu, nó sẽ khởi t o các lớp cho phân lớp b ng cách xác ịnh các nhãn cho các nhóm dữ liệu. - Hình 1.2: Mô phỏng vấn đề PCDL Các yêu cầu của phân cụm trong khai phá dữ liệu. - Giảm dữ liệu: Giả sử ta có một lƣợng lớn dữ liệu (N). - Phân cụm sẽ nhóm các dữ liệu này thành m cụm dữ liệu dễ nhận thấy và m <<. - Thích nghi với các kiểu dữ liệu khác nhau. - Thích nghi với dữ liệu nhiễu. - Hiện nay, phân cụm dữ liệu ng ƣợc nghiên cứu, ứng dụng trong nhiều l nh vực khác nhau, các kỹ thuật phân cụm dữ liệu ã ƣợc áp dụng cho một số ứng dụng iển hình trong các l nh vực:. - Thƣơng m i: Trong thƣơng m i, phân cụm có thể giúp các thƣơng nhân khám phá ra các nhóm khách hàng quan trọng có các ặc trƣng tƣơng ng nh u v ặc tả họ từ các mẫu mu án trong cơ sở dữ liệu khách hàng.. - Phân cụm có thể trợ giúp ngƣời dùng tự ộng phân tích và xử lý các dữ liệu không gi n nhƣ nhận d ng và chiết xuất các ặc tính hoặc các mẫu dữ liệu quan tâm có thể t n t i trong cơ sở dữ liệu không gian.. - Tóm tắt và giải thích dữ liệu bài toán: Nhiều bài toán, dữ liệu có thể ƣợc tóm tắt nhờ xem xét thuộc tính của các cụm dữ liệu mà không cần thiết xem xét thuộc tính của từng mẫu. - T o mẫu cho tiếp cận phân lớp thống kê: Trong nhiều bài toán phân lớp, việc thu thập dữ liệu mất nhiều thời gian và chi phí lớn. - Việc phân cụm dữ liệu ƣợc thực hiện ở gi i o n ầu ể ƣớc lƣợng phân phối lớp cho các tập mẫu nhỏ.. - Các lớp tài liệu này trợ giúp cho việc khám phá tri thức từ dữ liệu … [1,6]. - Với số lƣợng cụm ã ịnh, phƣơng pháp phân ho ch sẽ lần lƣợt phân các ối tƣợng dữ liệu vào các cụm s u ó thực hiện lặp quá tr nh iều chỉnh ể cực tiểu hàm mục ti u ƣợc chọn. - Với tập dữ liệu D g m n ối tƣợng trong không gian s chiều, các ối tƣợng ƣợc phân thành c cụm sao cho t ng nh phƣơng ộ lệch của mỗi mẫu tới tâm của nó là nhỏ nhất.. - Thuật toán k-means (MacQueue, 1967) chia tập dữ liệu cho trƣớc thành c cụm. - sao cho t ng nh phƣơng khoảng cách của mỗi ối tƣợng dữ liệu tới tâm cụm chứ nó t cực tiểu. - Khi tập dữ liệu không quá lớn th ngƣời t ùng iều kiện dừng 3.. - Nếu tập dữ liệu D g m n mẫu với số thuộc tính là s, phân thành c cụm và số lần lặp ở ƣớc 2 là t th ộ phức t p của thuật toán chỉ là O(tnsc) [14] nên rất thích hợp khi tập D g m lƣợng dữ liệu lớn.. - Trong phƣơng pháp n y tập dữ liệu ƣợc sắp xếp thành một cấu trúc có d ng hình cây gọi là cây phân cụm. - Thủ tục ệ quy kết thúc ta có tập duy nhất là toàn bộ dữ liệu. - Quá trình thực hiện thuật toán ƣợc biểu diễn thành cây và quyết ịnh phân dữ liệu thành bao nhiêu cụm sẽ o ngƣời dùng quyết ịnh Ngƣời ùng cũng ự tr n cây n y ể nhận ƣợc kết quả phân cụm.. - Quá trình thực hiện phƣơng pháp “ ƣới l n” phân cụm tập dữ liệu S = {a, c e} ƣợc mô tả trong ph ƣới cụ thể nhƣ s u:. - ƣớc 0: Mỗi ối tƣợng dữ liệu ƣợc gán cho mỗi cụm nhƣ vậy các cụm n ầu là: {a},{b},{c},{d},{e}.. - Phƣơng pháp phân cụm dựa vào mật ộ xem các cụm nhƣ l các vùng có mật ộ các ối tƣợng lớn trong không gian dữ liệu Các phƣơng pháp ựa vào mật ộ có thể sử dụng ể lo i bỏ nhiễu và phát hiện ra các cụm có hình d ng tự nhiên.. - Phân cụm dữ liệu theo thuật toán DBSCAN áp dụng các luật s u ây:. - Hình sau minh họa một trƣờng hợp với là bán kính của hình tròn và Minpts = 3, tập dữ liệu g m hai cụm và các phần tử ngo i lai rải rác Các ối tƣợng {o, p, q, r} là nhân c n s kh ng l ối tƣợng nhân nhƣng nó thuộc cụm vì là –láng giềng của một ối tƣợng là nhân.. - Hình sau minh họa một ví dụ về tập dữ liệu g m hai cụm ƣợc nhận biết nhờ phƣơng pháp n y m kh ng ùng phƣơng pháp phân ho ch ƣợc.. - Hình 1.5: Hai cụm dữ liệu có thể tìm được nhờ DBSCAN.. - Tiến tr nh n y ƣợc lặp l i cho ến khi tính chất cụm của dữ liệu trong mỗi xác ịnh rõ. - Việc phân cụm sẽ hoàn tất khi xác ịnh ƣợc quan hệ cụm giữa dữ liệu trong các ô. - Trong phân cụm các ối tƣợng dữ liệu thƣờng ƣợc diễn tả ƣới d ng các ặc tính hay còn gọi là thuộc tính, các thuộc tính này là các tham số ể giải quyết vấn ề phân cụm và sự lựa chọn chúng có tác ộng áng kể ến kết quả phân cụm.. - Phân lo i các kiểu thuộc tính khác nhau là vấn ề cần giải quyết ối với hầu hết các tập dữ liệu nh m cung cấp các phƣơng tiện thuận lợi ể nhận d ng sự khác nhau của các phần tử dữ liệu. - Các thuật toán phân cụm thƣờng sử dụng một trong hai cấu trúc dữ liệu sau:. - Ma trận dữ liệu (Data matrix, object-by-variable structure): Là mảng n hàng, p cột trong ó p l số thuộc tính của mỗi ối tƣợng. - Do vậy, nếu dữ liệu cần phân cụm ƣợc t chức ƣới d ng ma trận dữ liệu thì cần biến i về d ng ma trận phi tƣơng tự trƣớc khi tiến hành phân cụm. - Giả sử x = (x 1 ,...,x n ) và y = (y 1 ,...,y n ) l h i ối tƣợng dữ liệu hỗn hợp trên D, khoảng cách (x y) ƣợc tính bởi công thức:. - trong ó N j là kích cỡ của phân cụm j và N là t ng số lƣợng ối tƣợng dữ liệu.. - Hình (a) là mô hình nhỏ gọn minh họa mục tiêu phù hợp ể ối phó với các bộ dữ liệu hình cầu.. - Hình (b) là Mô hình gắn kết, mô tả mục tiêu kết nối xử lý bộ dữ liệu hình d ng tùy ý.. - Một thuật toán phân cụm t ng quát sẽ chia bộ dữ liệu x vào k cụm: C1,C2. - Phân t ch thị hai vòng MST của một số bộ dữ liệu rời v ộ i tƣơng ứng ƣợc ịnh ngh ở trên, chúng ta thấy r ng thị h i v ng MST v ộ dài có ba tính n ng tốt:. - Thuật toán 1. - (V, E), bộ dữ liệu củ thị ể phân vùng. - Output: S, tập hợp các bộ dữ liệu con ƣợc phân vùng.. - Nếu bảng Open trống, bộ dữ liệu con tƣơng ứng với thị con trong bảng Closed sẽ ƣợc ƣ v o S. - Hình (a) minh họa bộ dữ liệu con của hình 2.4(c);. - Hình (b) thuật toán phân cụm rời ƣợc áp dụng cho các bộ dữ liệu con. - Thuật toán 2. - Thuật toán phân cụm tự đ ng. - Input: T1 và T2, hai vòng MST của một bộ dữ liệu con ƣợc t o bởi thuật toán 1.. - Để làm sáng tỏ kỹ thuật phân cụm của thuật toán 2- MSTs ã tr nh y chƣơng tr nh sẽ thử nghiệm với 2 bộ dữ liệu li n qu n ến ngành hàng không, một bộ dữ liệu thực ƣợc thu thập từ t ng công ty hàng không Việt Nam, một bộ dữ liệu không thực(tự t o ể test thử chƣơng tr nh). - Tập dữ liệu g m 21 ối tƣợng và 10 thuộc tính, trong tập thuộc tính của dữ liệu có 7 thuộc tính có thông tin ảnh hƣởng trực tiếp ến quá trình phân cụm ó l các thuộc tính có dữ liệu số.. - Mỗi thuộc tính có dữ liệu số s u khi t nh toán T1 v T2 ể nhận ng tách cụm sẽ có 2 tập f i diện trong h nh 3 4 ã thể hiện iều ó.. - Nhƣ vậy với tập dữ liệu 1, sau khi sử dụng thuật toán 2 – MSTs t thu ƣợc 4 cụm nhƣ s u:. - Tập dữ liệu n y ƣợc thử nghiệm với 11 ối tƣợng và 10 thuộc tính, dữ liệu ƣ v o rất thiếu thực tế, không có tính logic nên t m gọi là dữ liệu không thực.. - Bảng dữ liệu thử nghiệm lần 2. - Với cách thức thử nghiệm tƣơng tự nhƣ với tập dữ liệu 1, sau khi phân cụm thuật toán cũng ƣ r ƣợc 4 cụm nhƣ s u:. - Vậy với dữ liệu không thực thì sau khi tiến hành thí nghiệm, kết quả vẫn cho ta là 4 cụm nhƣng thực chất là chỉ có 2 cụm vì có sự trùng lặp giữa các cụm. - Vậy với dữ liệu xa thực tế với ngƣời sử dụng, không có tính logic thì kết quả sẽ bị sai lệch.. - T ng hợp l i kiến thức về khám phá tri thức và phân cụm dữ liệu.. - Thử nghiệm thuật toán với 2 bộ dữ liệu li n qu n ến ng nh h ng kh ng v ƣ ra kết quả thử nghiệm, so sánh v ánh giá các kết quả.. - Trong thời gian tới, tôi sẽ cố gắng tìm hiểu nhiều hơn nữa về các phƣơng pháp phân cụm dữ liệu ặc biệt l phƣơng pháp phân cụm dữ liệu dự tr n thị sử dụng cây khung cực tiểu và cố gắng mở rộng ứng dụng của thuật toán vào nhiều bài toán thực tế.