Luận văn Thạc sĩ Công nghệ thông tin: Phân cụm dữ liệu dựa trên đồ thị sử dụng cây khung cực tiểu

Chia sẻ: Tomjerry001 | Ngày: | Loại File: PDF | Số trang:53

Thêm vào BST

Báo xấu

34
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung luận văn tóm gọn trong: Chương 1: Giới thiệu về khám phá tri thức và phân cụm dữ liệu. Chương 2: Thuật toán phân cụm sử dụng cây khung cực tiểu. Chương 3: Thực nghiệm ứng dụng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Phân cụm dữ liệu dựa trên đồ thị sử dụng cây khung cực tiểu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ------------------------------------------- TRẦN QUANG HÀO PHÂN CỤM DỮ LIỆU DỰA TRÊN ĐỒ THỊ SỬ DỤNG CÂY KHUNG CỰC TIỂU LUẬN VĂN THẠC SỸ C NG NGHỆ TH NG TIN Hà Nội – 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ --------------------- TRẦN QUANG HÀO PHÂN CỤM DỮ LIỆU DỰA TrRÊN ĐỒ THỊ SỬ DỤNG CÂY KHUNG CỰC TIỂU Ngành: Công Nghệ Thông Tin Chuyên ngành: Kỹ thuật Phần mềm (Software Engineering) Mã số: 60480103 LUẬN VĂN THẠC SỸ C NG NGHỆ TH NG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. HOÀNG XUÂN HUẤN Hà Nội – 2014
LỜI CẢM ƠN Điều ầu ti n tôi xin gửi lời cảm ơn sâu sắc nhất ến PGS.TS Hoàng Xuân Huấn. Thầy ã cung cấp cho tôi những kiến thức, tài liệu, phƣơng pháp khi nghi n cứu v l m luận v n. Tôi xin cảm ơn thầy về sự hỗ trợ chân thành và nhiệt tình trong suốt thời gian qua. Đối với t i thầy l một ngƣời thầy áng k nh v lu n hết l ng v học vi n T i xin gửi lời cảm ơn chân th nh ến các thầy c ộ ã giảng y các cán ộ trong kho c ng nghệ th ng tin kho s u i học ph ng t chức h nh ch nh T i xin gửi lời cảm ơn ến gi nh ng nghiệp v n những ngƣời ã ộng vi n t i rất nhiều trong quá tr nh học tập Hà Nội, ngày 2 tháng 12 n m 2014 Học viên Trần Quang Hào 1
LỜI CAM ĐOAN T i xin c m o n những kiến thức trình bày trong luận v n n y l o t i t m hiểu, nghiên cứu và trình bày theo cách hiểu của bản thân ƣới sự hƣớng dẫn trực tiếp của PGS.TS Hoàng Xuân Huấn. Trong quá trình làm luận v n t i có th m khảo các tài liệu có li n qu n v ã ghi rõ ngu n gốc tham khảo tài liệu ó Mọi sao chép không hợp lệ, vi ph m quy chế o t o tôi xin chịu hoàn toàn trách nhiệm. Hà Nội, ngày 2 tháng 12 n m 2014 Học viên Trần Quang Hào 2
MỤC LỤC LỜI CẢM ƠN ....................................................................................................................1 LỜI CAM ĐOAN ..............................................................................................................2 MỤC LỤC..........................................................................................................................3 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ...................................................5 DANH MỤC HÌNH VẼ ....................................................................................................6 LỜI MỞ ĐẦU ....................................................................................................................7 CHƢƠNG 1: GIỚI THIỆU VỀ KH M PH TRI TH C V PH N CỤM Ữ LIỆU ............................................................................................................................................8 1.1. Khám phá tri thức .......................................................................................................8 1.2. Vai trò và các mục tiêu chính của KDD ....................................................................9 1.3. Khái niệm phân cụm ữ liệu: .....................................................................................10 1.4. Các ứng dụng của phân cụm ......................................................................................11 1 5 Một số phƣơng pháp phân cụm iển h nh...................................................................12 1 5 1 Phƣơng pháp phân cụm phân ho ch ........................................................................12 1 5 2 Phƣơng pháp phân cụm phân cấp.............................................................................13 1 5 3 Phƣơng pháp phân cụm dựa trên mật ộ .................................................................16 1 5 4 Phƣơng pháp phân cụm dự tr n lƣới ......................................................................17 1.6. Một số vấn ề li n qu n ến phân cụm ......................................................................18 1.6.1. Mêtric trên dữ liệu hỗn hợp. ....................................................................................18 1.6.2.Độ tƣơng ng. .........................................................................................................20 1.6.3. Entropy .....................................................................................................................23 CHƢƠNG 2: THU T TO N PH N CỤM S ỤNG C Y KHUNG CỰC TIỂU ...24 2.1.Cây khung cực tiểu ......................................................................................................24 2 1 1 Đ nh ngh cây khung cực tiểu ................................................................................24 2 1 2 Thuật toán xây ựng cây khung cực tiểu .................................................................24 2.2. Một số khái niệm cần dùng .......................................................................................26 2.3. Cụm ƣợc mô tả bởi Zahn v H n l ..........................................................................27 2.4. Thiết lập i toán phân cụm ng thị: ...................................................................28 2 5 Độ phức t p củ thuật toán 2-MSTs ...................................................................... 35 3
CHƢƠNG 3: THỰC NGHIỆM NG ỤNG .................................................................37 3 1 Giới thiệu.....................................................................................................................37 3.2 Chƣơng tr nh v kết quả thử nghiệm..........................................................................37 3 2 1 Chƣơng tr nh ............................................................................................................37 3.2.2 Kết quả thử nghiệm .................................................................................................38 KẾT LU N ........................................................................................................................48 TÀI LIỆU THAM KHẢO .................................................................................................49 4
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Từ viết tắt Từ tiếng anh Từ hoặc cụm từ CSDL Database Cơ sở dữ liệu CQĐ Decision Tree Cây quyết ịnh KPDL Data mining Khai phá dữ liệu PCDL Clustering Data Phân cụm dữ liệu TB Average Trung bình CLS ConceptLearning System Hệ thống học khái niệm 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 MST Minimum spanning tree Cây khung cực tiểu 5
DANH MỤC HÌNH VẼ Hình 1.1 Quá trình phát hiện tri thức trong CSDL ............................................................. 9 Hình 1.2: Mô phỏng vấn ề PCDL ................................................................................... 10 Hình 1.3: Phân cụm tập S = { c e} theo phƣơng pháp “ ƣới l n” ...................... 15 Hình 1.4: Hai cụm ƣợc tìm bởi thuật toán DBSCAN. .................................................... 17 Hình 1.5: Hai cụm dữ liệu có thể t m ƣợc nhờ DBSCAN. ............................................. 17 Hình 1.6: Ba tầng liên tiếp nhau của cấu trúc STING. ..................................................... 18 Hình 2.1: Một số hình minh họa phân cụm bởi Zahn ....................................................... 27 Hình 2.2. Một số hình minh họa phân cụm bởi Handl ..................................................... 27 Hình 2.3. Minh họa MSTs hai vòng ................................................................................. 30 Hình 2.4. Minh họa cụm tách về mật ộ ........................................................................... 32 Hình 2.5. Minh họa cụm không thể t ch ƣợc hơn nữa ................................................... 32 Hình 2.6. Minh họa cụm với tỉ lệ cut khác nhau ............................................................... 33 Hình 3.1. Giao diện co e chƣơng tr nh ............................................................................. 38 Hình 3.2. Giao diện khi ch y chƣơng tr nh ....................................................................... 38 H nh 3 3 ảng kế ho ch khai thác bay ........................................................................... 39 H nh 3 4 ảng s u khi t nh toán T1 v T2 nhận ng tách cụm .................................... 39 Hình3.5: Bảng Gain của các thuộc tính ........................................................................... 40 Hình 3.5 : Bảng với f10 nhận giá trị 0............................................................................. 40 Hình 3.6: Bảng với f10 nhận giá trị 1............................................................................... 41 Hình 3.7: Bảng t nh G in củ các thuộc t nh lần 2 .......................................................... 41 Hình 3.8: Bảng f13 nhận giá trị b ng 0 ............................................................................ 42 Hình 3.9: Bảng f13 nhận giá trị b ng 1 ............................................................................. 42 Hình 3.10. Bảng kết quả phân cụm s u khi t nh entropy lần 1........................................ 43 Hình 3.11. Bảng kết quả phân cụm s u khi t nh entropy lần 1........................................ 44 6
Hình 3.12. Bảng kết quả phân cụm s u khi t nh entropy lần 2......................................... 45 Hình 3.13. Bảng kết quả phân cụm s u khi t nh entropy lần 2........................................ 45 H nh 3 14 ảng dữ liệu thử nghiệm lần 2 ....................................................................... 46 H nh 3 15 ảng s u khi t nh toán T1 v T2 nhận ng tách cụm .................................. 46 Hình 3.16. Bảng kết quả phân cụm s u khi t nh enropy lần 1 .......................................... 47 Hình 3.17. Bảng kết quả phân cụm s u khi t nh enropy lần 2 .......................................... 47 7
LỜI MỞ ĐẦU Ng y n y o sự phát triển m nh củ các ứng ụng c ng nghệ th ng tin trong các l nh vực nhƣ kinh tế xã hội kho học … ã t o r khối lƣợng cơ sở ữ liệu kh ng l Để kh i thác th ng tin hiệu quả i hỏi phải có một số kỹ thuật xử lý c o cấp ó l phân ho ch ữ liệu h y các cụm. 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. Số cụm là một tham số quan trọng và ảnh hƣởng nhiều tới kết quả của quá trình phân cụm, ứng với số lƣợng cụm khác nhau sẽ cho ra các kết quả phân cụm khác nhau, thật khó kh n ể quyết ịnh kết quả phân cụm nào là tốt nhất. 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. Ngo i phần mở ầu và kết luận, cấu trúc luận v n có 3 chƣơng:  Chƣơng 1: Gi i thi u về h m ph tr th c v ph n cụm ữ i u Chƣơng n y sẽ tr nh y các khái niệm cơ ản về khám phá tri thức v phân cụm ữ liệu tóm tắt một số phƣơng pháp phân cụm ữ liệu iển h nh  Chƣơng 2: Thuật to n ph n cụm sử ụng c hung cực tiểu 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.  Chƣơng 3: Thực nghi m ng ụng Trong phần thực nghiệm c i ặt thuật toán 2-MSTs v m phỏng thuật toán qu v ụ kh i thác y củ ng nh h ng kh ng. Phần kết luận trình bày tóm tắt về các nội dung thực hiện trong luận v n ng thời ƣ r các vấn ề nghiên cứu tiếp cho tƣơng l i 7
CHƢƠNG 1: GIỚI THIỆU VỀ H M PH TRI TH C V PH N CỤM DỮ IỆU 1.1. Khám phá tri th c 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. Các thông tin và kiến thức thu ƣợc có thể ƣợc sử dụng cho các ứng dụng khác nhau, ví dụ nhƣ phân t ch thị trƣờng, phát hiện gian lận v uy tr khách h ng ể kiểm soát sản xuất và khoa học th m dò. 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 Khái niệm KDD (Knowledge Discovery in Databases) ƣợc ịnh ngh l quá trình trích chọn các mẫu hoặc tri thức hấp dẫn, Quá trình KDD có thể phân thành các gi i o n sau: 1. 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 2. 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. 3. Đổ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. 4. 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. 5. 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ị, 8
cây, bảng biểu, luật Đ ng thời ƣớc n y cũng ánh giá những tri thức khám phá ƣợc theo những tiêu chí nhất ịnh [7,12,13] Các ƣớc thực hiện trong quá tr nh khám phá tri thức Biểu diễn tri Đ nh gi v Các mẫu Data Mining Tri thức giải thíchBiến đổi dữ li u Biến đổi dữ li u Dữ liệu Dữ liệu thô Tr ch chọn ữ Tiền xử ý ữ Biến đổi ữ i u i u Dữ liệu i u Tiền xử lý Hình 1.1 Quá trình phát hiện tri thức trong CSDL 1.2. Vai trò và các mục tiêu chính của KDD  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. Về ý ngh kho học thì dữ liệu chính là những quan sát ã ƣợc tập hợp l i một cách cẩn thận và công phu về một hiện tƣợng tự nhiên hay xã hội n o ó cần phải ƣợc nghiên cứu. - 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. Trong kỹ nghệ, dữ liệu chứa các thông tin về sản xuất, về vận hành và các khả n ng tối ƣu cũng nhƣ các giải pháp chủ yếu ể cải tiến các quy trình và giải quyết các sự cố. - 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] 9
1.3. Khái ni m phân cụm ữ i 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ự" với nhau và các phần tử trong các cụm khác nhau sẽ "kém tƣơng tự " với nhau. 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. [6] 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. [6]. V ụ minh họ về phân cụm ữ 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 Hầu hết các nghiên cứu và phát triển thuật toán PC L ều nh m thỏa mãn các yêu cầu cơ ản sau:  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
 Có khả n ng phân cụm với dữ liều có số chiều cao  Dễ hiểu c i ặt và khả dụng. 1.4. Các ng dụng của phân cụm 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.  Sinh học: Trong sinh học, phân cụm ƣợc sử dụng ể xác ịnh các lo i sinh vật, phân lo i các Gen với chức n ng tƣơng ng v thu ƣợc các cấu trúc trong các mẫu.  Phân tích dữ liệu không gian: Do sự sộ của dữ liệu kh ng gi n nhƣ ữ liệu thu ƣợc từ các hình ảnh chụp từ vệ tinh các thiết bị y học hoặc hệ thống th ng tin ịa lý (GIS) …l m cho ngƣời dùng rất khó ể kiểm tra các dữ liệu không gian một cách chi tiết. 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.  Lập quy ho ch thị: Nhận d ng các nhóm nhà theo kiểu và vị tr ị lý … nh m cung cấp thông tin cho quy ho ch thị.  Nghiên cứu trái ất: Phân cụm ể theo õi các tâm ộng ất nh m cung cấp thông tin cho nhận d ng các vùng nguy hiểm.  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. Trong nhiều lý thuyết khoa học, việc giải thích theo cụm cũng rất có ý ngh chẳng h n việc phân tích tiến hóa sinh học có thể thực hiện theo loài và nhóm.  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ỏ.  Để t o tâm cho các nơron nhân t o trong các bộ phân lớp lo i này: Khi dùng m ng nơron nhân t o ể phân lớp ngƣời t thƣờng dùng vector trung bình của các 11
vector ặc trƣng trong cụm làm tâm củ các nơron ể nhận biết các mẫu có ặc trƣng gần ó  Thƣ viện: Theo õi ộc giả, sách, dự oán nhu cầu củ ộc giả…  Bảo hiểm: Phân nhóm các ối tƣợng sử dụng bảo hiểm và các dịch vụ tài chính, dự oán xu hƣớng của khách hàng, phát hiện gian lận tài chính;  Địa lý: Phân lớp các ộng vật và thực vật ƣ r ặc trƣng của chúng.  Web Mining: Phân cụm có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý ngh trong m i trƣờng Web. 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] 1.5.M t s phƣơng ph p ph n cụm điển h nh 1.5.1.Phƣơng ph p ph n cụm phân hoạch 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. Thuật toán k-mean l thuật toán thông dụng nhất trong phƣơng pháp n y. Trong các thuật toán này, số lƣợng cụm k thƣờng ƣợc xác ịnh trƣớc hoặc ặt ƣới d ng tham số. 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. S u ây l thuật toán k-means, thuật toán iển hình củ phƣơng pháp n y Thuật toán k-means 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. Nhƣ vậy, hàm mục tiêu của thuật toán này là: (1.1) Trong ó: l tâm củ cụm tƣơng ứng Thuật toán n y thực hiện nhƣ s u: ƣớc 0: Xác ịnh trƣớc số lƣợng cụm c v iều kiện ừng; ƣớc 1: Khởi t o ngẫu nhi n c iểm l m các tâm cụm; ƣớc 2: Lặp khi iều kiện ừng chƣ thỏ mãn: 12
2 1 Phân ho ch th nh c cụm ng cách gán mỗi ối tƣợng v o cụm m nó gần tâm nhất; 2 2 T nh l i các tâm theo các ối tƣợng ã ƣợc phân ho ch ở ƣớc 2 1 Điều kiện ừng củ thuật toán thƣờng chọn từ các iều kiện s u: - Số lần lặp t = trong ó l số cho trƣớc; - Giá trị củ h m E nhỏ hơn một ngƣỡng n o ó ( ảm ảo chất lƣợng củ các cụm ủ tốt h y nó ã ch y ƣợc ủ số v ng lặp cần thiết) - Tới khi các cụm kh ng i 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. 1.5.2. Phƣơng ph p ph n cụm phân cấp 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. Cây này có thể ƣợc xây dựng nhờ kỹ thuật ệ quy theo hai phƣơng pháp t ng quát: phƣơng pháp ƣới l n ( ottom up) v phƣơng pháp tr n xuống (top down).  Phƣơng pháp ƣới lên (bottom up) Các thuật toán theo phƣơng pháp ƣới lên còn gọi là các thuật toán trộn n ầu, ngƣời ta khởi t o mỗi ối tƣợng làm một cụm và dùng thủ tục ệ quy ể trộn hai cụm gần nhất với nhau trong mỗi ƣớc ể có kết quả chia cụm mới. Thủ tục ệ quy kết thúc ta có tập duy nhất là toàn bộ dữ liệu. Các thuật toán phân biệt với nhau ở tiêu chuẩn ánh giá h i cụm nào là gần nhất dựa trên khoảng cách các cụm chọn trƣớc. Quy tắc ể chọn các cụm trộn n y ƣợc gọi là quy tắc liên kết. 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. Cụ thể, với cách tính khoảng cách ể chọn cặp cụm trộn với nh u cho trƣớc, các thuật toán trộn bao g m các ƣớc sau: 13
Khởi t o mỗi phần tử làm một cụm ,c=n Khi c ≠ 1 thực hiện lặp: 2.1. Chọn hai cụm gần nhất và theo quy tắc ã chọn 2.2. Trộn và thành // còn c-1 cụm 2.3. c c-1 Phƣơng pháp tr n xuống (top down). Phƣơng pháp tr n xuống còn gọi l phƣơng pháp tách ƣợc thực hiện theo trình tự ngƣợc với phƣơng pháp trộn. Trong mỗi ƣớc ngƣời ta chọn một cụm ể tách thành cụm con theo quy tắc ánh giá v tách cụm cho trƣớc Phƣơng pháp n y phức t p và lâu hơn phƣơng pháp ƣới l n v thƣờng chỉ ƣợc áp dụng khi ngƣời ta có thêm thông tin về phân bố cụm ể có phƣơng pháp tách phù hợp. Ví dụ: Trong ví dụ này, ta giải thiết ã có quy tắc liên kết và không bàn cụ thể tới cách chọn cụm trộn. 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}. ƣớc 1: { } v { } l ƣợc gộp vào thành một cụm lớn hơn l { } v các cụm thu ƣợc là: {a,b},{c},{d},{e}. ƣớc 2: Gộp cụm {d},{e} thành {d,e}, các cụm thu ƣợc là {a,b},{c},{d,e}. ƣớc 3: Gộp cụm {c} với {d,e} thành {c,d,e}, các cụm thu ƣợc là {a,b}, {c,d,e}. ƣớc 4: Gộp cụm hai cụm {c,d,e} với {a,b} thành {a,b,c,d,e}. 14
Bƣớc 0 Bƣớc 1 Bƣớc 2 Bƣớc 3 Bƣớc 4 a Chiều từ ƣới ab lên b abcde c cde d de e Hình 1.3: Phân cụm tập S = {a, b, c, d, e} theo phương pháp “dưới lên”. Các quy tắc liên kết Kết quả phân cụm của một thuật toán phụ thuộc v o m tric ƣợc ùng ể tính khoảng cách củ các ối tƣợng. Kết quả phân cụm phân cấp cũng phụ thuộc quy tắc liên kết hay cách tính khoảng cách (hoặc giả khoảng cách) giữa hai cụm và ểtmv trộn h i cụm có khoảng cách nhỏ nhất trong mỗi ƣớc Với m tric trong kh ng gi n ặc trƣng xác ịnh ởi một chuẩn ã có s u ây l một số quy tắc li n kết th ng ụng a) Liên kết đơn Ký hiệu l NN (Ne rest Neigh our) Trong quy tắc n y khoảng cách giữ h i cụm ƣợc xác ịnh nhờ khoảng cách nhỏ nhất giữ h i mẫu ( ối tƣợng) tƣơng ứng với h i cụm: (1.2a) b) Liên kết đầy Ký hiệu l FN (Furthest Neigh our) Trong quy tắc n y khoảng cách giữ h i cụm ƣợc xác ịnh nhờ khoảng cách lớn nhất giữ h i mẫu tƣơng ứng với h i cụm: (1.2b) c) Liên kết trung bình giữa các nhóm Ký hiệu l UPGMA (Un-Weighted Pair-Group Method using Arithmetic averages). Nhƣ t n gọi củ nó khoảng cách l trung nh củ khoảng cách giữ các cặp ối tƣợng thuộc h i cụm tƣơng ứng: (1.2c) Trong ó: và l số phần tử củ các cụm tƣơng ứng 15
Một số thuật toán phân cụm phân cấp iển h nh nhƣ CURE IRCH AGNES… 1.5.3. Phƣơng ph p ph n cụm dựa trên mật đ 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. Thuật toán dựa vào mật ộ ầu tiên là thuật toán DBSCAN (Ester et al, 1996), thuật toán này xem xét mật ộ theo lân cận của mỗi ối tƣợng, nếu số lƣợng các ối tƣợng trong khoảng cách của một ối tƣợng lớn hơn ngƣỡng MinPts th ối tƣợng ó ƣợc xem là n m trong một cụm. Thuật toán DBSCAN (Density – Based Spatial Clustering of Applications with Noise) Thuật toan DBSCAN nhóm các vùng có mật ộ ủ cao vào trong một cụm và thác triển dự tr n các ối tƣợng lõi ể có các cụm với hình d ng tự nhiên trong các tập không gi n ặc trƣng Thuật toán yêu cầu xác ịnh trƣớc hai tham số ầu vào là và Minpts. Phân cụm dữ liệu theo thuật toán DBSCAN áp dụng các luật s u ây: Các ối tƣợng n m trong hình cầu bán kính ε (ε–lân cận) của một ối tƣợng ƣợc gọi là ε–láng giềng củ ối tƣợng ó Đối tƣợng có ít nhất l Minpts ối tƣợng khác là ε–láng giềng th ƣợc gọi l ối tƣợng nhân. Một ối tƣợng có thể n m trong một cụm khi và chỉ khi nó n m trong ε –lân cận của một ối tƣợng nhân thuộc cụm ó Một ối tƣợng lõi o là ε–láng giềng của một ối tƣợng nhân p thì o thuộc cùng cụm với p. Hai cụm có giao khác rỗng thì nhập thành một cụm  Một ối tƣợng không là nhân r và không là –láng giềng của một ối tƣợng nhân n o th ƣợc xem là phần tử ngo i l i h y l ối tƣợng nhiễu. Ví dụ: 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. 16
Hình 1.4: Hai cụm được tìm bởi thuật toán DBSCAN. 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. 1.5.4. Phƣơng ph p ph n cụm dựa trên ƣ i Để nâng c o hiệu quả củ phân cụm một cách tiếp cận l phân chi miền kh ng gi n ặc trƣng chứ ữ liệu th nh một số hữu h n các t on n ng h nh lƣới v sử ụng các ặc trƣng thống k ể phân t ch các ữ liệu trong mỗi v quyết ịnh tách h y nhập chúng T l m quen với thuật toán STING ể hiểu cách tiếp cận n y Thuật to n STING (A STatistical INformation Grid approach) STING o W W ng v các cộng sự (1997) ề xuất phƣơng pháp n y t chức miền kh ng gi n chứ ữ liệu th nh lƣới h nh hộp mức ể phân t ch cụm theo thống k phân cấp tr n từng n ầu t chi miền ữ liệu th nh các h nh chữ nhật (hoặc h nh hộp khi kh ng gi n có số chiều c o) với chiều i các c nh ở mức 1 Việc phân t ch th ng tin ự tr n các ặc iểm thống k củ tập ữ liệu trong mỗi nhƣ:  Count: số ối tƣợng trong  M: vectơ trung nh củ ữ liệu trong  S: ộ lệch chuẩn củ mọi giá trị thuộc t nh trong  Min: giá trị cực tiểu củ các thuộc t nh trong  M x: giá trị cực i củ các thuộc t nh trong  istri ution: kiểu phân phối củ các giá trị thuộc t nh trong 17