Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số thuật toán phân cụm, phân lớp dữ liệu và ứng dụng

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

Thêm vào BST

Báo xấu

65
lượt xem 9
download

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

Bài nghiên cứu này trình bày một số vấn đề về phân cụm, phân lớp dữ liệu một trong những kỹ thuật cơ bản để khai phá dữ liệu nhưng lại được sử dụng rộng rãi và đem lại hiệu quả cao. Để hiểu rõ hơn mời các bạn cùng tham khảo nội dung chi tiết của luận văn này.

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ĩ Khoa học máy tính: Nghiên cứu một số thuật toán phân cụm, phân lớp dữ liệu và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN MINH TÂM NGHI N UM T THU T TO N PHÂN M PHÂN P I UV NG NG U N VĂN THẠ Ĩ KHOA HỌ M Y TÍNH THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN MINH TÂM NGHI N UM T THU T TO N PHÂN M PHÂN P I UV NG NG Chuyên ngành: Khoa học máy tính Mã số: 84 80 101 U N VĂN THẠ Ĩ KHOA HỌ M Y TÍNH Người hướng dẫn khoa học: TS. NGUYỄN VĂN NÚI THÁI NGUYÊN - 2019
LỜI CẢM ƠN Em xin chân thành cảm ơn Trƣờng Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên đã tạo điều kiện cho em thực hiện luận văn này. Em xin gửi lời cảm ơn sâu sắc tới thầy giáo TS. Nguyễn Văn Núi, Bộ môn công nghệ phần mềm - Trƣờng Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên đã trực tiếp hƣớng dẫn em trong quá trình thực hiện luận văn. Em cũng xin gửi lời cảm ơn tới các thầy, cô đã có những ý kiến đóng góp bổ ích và đã tạo mọi điều kiện tốt nhất cho em trong suốt thời gian thực hiện luận văn. Xin cảm ơn các bạn học đồng khóa đã thƣờng xuyên động viên, giúp đỡ tôi trong quá trình học tập. Cuối cùng, em xin gửi lời cảm ơn đến gia đình và đồng nghiệp vì sự ủng hộ và động viên đã dành cho em trong suốt quá trình học tập cũng nhƣ thực hiện luận văn này. Thái Nguyên, tháng 05 năm 2019 Học viên Nguyễn Minh Tâm
2 LỜI CAM ĐOAN Em xin cam đoan về nội dung đồ án tốt nghiệp với tên đề tài “ Nghi cứu t số thu t t h cụ h dữ i u v ứ g dụ g” không sao chép nội dung từ các luận văn khác, hay các sản phẩm tƣơng tự mà không phải do em làm ra. Sản phẩm luận văn là do chính bản thân em tìm hiểu và xây dựng nên. Nếu có gì sai em xin chịu mọi hình thức kỷ luật của Trƣờng Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên. Thái Nguyên, tháng 05 năm 2019 Học viên Nguyễn Minh Tâm
3 MỤC LỤC LỜI CẢM ƠN ............................................................................................................... 1 LỜI CAM ĐOAN ......................................................................................................... 2 MỞ ĐẦU ........................................................................................................................ 7 CHƢƠNG 1 TỔNG QUAN.......................................................................................... 9 1.1 Giới thiệu chung....................................................................................... 9 1.2 Các bƣớc trong khai phá dữ liệu ............................................................ 10 1.3 Các kỹ thuật áp dụng trong khai phá dữ liệu ......................................... 12 1.4 Ứng dụng của khai phá dữ liệu .............................................................. 14 1.5 Những thách thức trong khai phá dữ liệu .............................................. 15 CHƢƠNG 2 PHÂN CỤM DỮ LIỆU VÀ MỘT SỐ THUẬT TOÁN CƠ BẢN ..17 2.1 Định nghĩa về phân cụm dữ liệu ............................................................ 17 2.2 Mục tiêu của phân cụm dữ liệu .............................................................. 18 2.3 Bài toán phân cụm dữ liệu ..................................................................... 20 2.4 Một số kiểu dữ liệu ................................................................................ 20 2.5 Một số kỹ thuật phân cụm dữ liệu ......................................................... 23 2.5.1 Phương pháp phân cụm dữ liệu dựa trên phân cụm phân cấp ....... 23 2.5.2 Phương pháp phân cụm dữ liệu dựa trên mật độ ............................ 25 2.5.3 Phương pháp phân cụm phân hoạch ............................................... 29 2.6 Kết luận .................................................................................................. 33 CHƢƠNG 3 PHÂN LỚP DỮ LIỆU VÀ MỘT SỐ THUẬT TOÁN CƠ BẢN ...........34 3.1 Định nghĩa về phân lớp dữ liệu.............................................................. 34 3.2 Các vấn đề quan tâm của phân lớp dữ liệu ............................................ 34 3.2.1 Quá trình phân lớp dữ liệu: ............................................................. 34 3.2.2 So sánh các phương pháp phân lớp................................................. 36 3.3 Phân lớp bằng cây quyết định ................................................................ 36 3.3.1 Khái niệm về cây quyết định ............................................................ 36 3.3.2 Ưu, nhược điểm của cây quyết định ................................................ 39 3.3.3 Một số thuật toán của cây quyết định .............................................. 40
4 3.4 Phân lớp bằng Bayesian ......................................................................... 48 3.5 Phân lớp dựa trên sự kết hợp ................................................................. 51 3.5.1 Các khái niệm quan trọng về luật kết hợp ....................................... 51 3.5.2 Một số thuật toán về luật kết hợp .................................................... 52 3.6 Độ chính xác classifier ........................................................................... 57 3.7 Kết luận .................................................................................................. 59 CHƢƠNG 4 MỘT SỐ KẾT QUẢ THỬ NGHIỆM .................................................60 4.1. Giới thiệu về công cụ phân cụm, phân lớp dữ liệu Weka..................... 60 4.2. Ứng dụng phân cụm dữ liệu để phân nhóm khách hàng ...................... 62 4.3. Ứng dụng phân lớp dữ liệu để phân lớp ............................................... 68 4.3.1. Phân lớp dữ liệu với thuật toán Apriori ......................................... 68 4.3.2. Phân lớp dữ liệu với thuật toán Naive Bayes ................................. 71 KẾT LUẬN ..................................................................................................................75 TÀI LIỆU THAM KHẢO ...........................................................................................76 Tiếng Việt: ................................................................................................... 76 Tiếng Anh: ................................................................................................... 76
5 DANH MỤC CÁC HÌNH VẼ Hình 1.1. Các bƣớc trong khai phá dữ liệu ..................................................... 10 Hình 2.1. Mô phỏng vấn đề phân cụm dữ liệu................................................ 17 Hinh 2.2. Cụm dữ liệu đƣợc khám phá bởi giải thuật DBSCAN ................... 26 Hinh 2.3. Thứ tự phân cụm các đối tƣợng theo OPTICS ............................... 29 Hinh 2. 4. Phân cụm dựa trên phƣơng pháp k-means ..................................... 31 Hình 4. 1. Giao diện chính của phần mềm ...................................................... 61 Hình 4.2. Thông tin dữ liệu cơ bản của file bank-k.arff hiển thị bởi Weka ... 63 Hình 4.3. Lƣu đồ thuật toán K-Means ............................................................ 64 Hình 4.4. Bảng tham số sử dụng cho thuật toán K-Means: Hình (a) K=3; Hình (b): K=5 ........................................................................................................... 65 Hình 4.5. Kết quả phân cụm với thuật toán K-Means (K=3) ......................... 66 Hình 4.6. Kết quả phân cụm với thuật toán K-Means (K=5) ......................... 67 Hình 4.7. Giao diện Weka chọn thuật toán Apriori ........................................ 68 Hình 4.8. Giao diện Weka thiết lập tham số cho thuật toán Apriori .............. 69 Hình 4.9. Kết quả sinh luật bởi thuật toán Apriori ......................................... 70 Hình 4.10. Giao diện Weka lựa chọn thuật toán Naive Bayes ....................... 71 Hình 4.11. Kết quả sinh luật bởi thuật toán Naive Bayes ............................... 72 Hình 4.12. Giao diện Weka lựa chọn thuật toán C4.5 .................................... 73 Hình 4.13. Kết quả sinh luật bởi thuật toán C4.5............................................ 74
6 DANH MỤC CÁC TỪ VIẾT TẮT STT Từ viết tắt Viết đầy đủ Ghi chú 1 PLDL Phân lớp dữ liệu 2 CSDL Cơ sở dữ liệu 3 KPDL Khai phá dữ liệu Thuật toán tích đống 4 AGNES Agglomerative Nesting lồng Blanced Iterative Reducing 5 BIRCH and Clustering using Hỉeachies Đặc trƣng của phân 6 CF Clustering Feature cụm Density Based Spatial 7 DBSCAN Clustering of Application with Noise Ordering Point to Identify the 8 OPTICS Clustering Structure 9 PAM Partitioning Around Medoids 10 ID3 Interative Decision 3 Phân lớp dữ liệu Naive 11 NBC Native Bayes Classification Bayes 12 FP Frequent Pattern Mẫu thƣờng xuyên
7 MỞ ĐẦU Trong thời gian gần đây, sự phát triển mạnh mẽ của công nghệ thông tin, thƣơng mại điện tử vào nhiều lĩnh vực của đời sống, kinh tế xã hội đã sinh ra một lƣợng dữ liệu lƣu trữ khổng lồ. Sự bùng nổ này đã dẫn tới một nhu cầu cấp thiết cần có những kỹ thuật và công cụ để tự động chuyển đổi dữ liệu thành các tri thức có ích mà các phƣơng pháp quản trị và khai thác cơ sở dữ liệu truyền thống không còn đáp ứng đƣợc nữa. Trong những khuynh hƣớng kỹ thuật mới có kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD – Knowledge Discovery and Data Mining). Nhƣng để có thể khai phá dữ liệu một cách hiệu quả và chính xác, ta cần có những mô hình toán học, các giải thuật đáp ứng đƣợc điều đó. Vì vậy, trong luận văn này có trình bày một số vấn đề về phân cụm, phân lớp dữ liệu một trong những kỹ thuật cơ bản để khai phá dữ liệu nhƣng lại đƣợc sử dụng rộng rãi và đem lại hiệu quả cao. Bố cục của lu vă Nội dung chính của luận văn đƣợc chia thành 4 chƣơng nhƣ sau: Chương 1. Tổng quan: Chƣơng này giới thiệu một cách tổng quát về quá trình phát hiện tri thức nói chung và khai phá dữ liệu nói riêng. Đặc biệt, chƣơng trình còn liệt kê một số điểm chính về ứng dụng cũng nhƣ thách thức của khai phá dữ liệu và phát hiện tri thức. Chương 2. Phân cụm dữ liệu và một số thuật toán cơ bản: Chƣơng này trình bày các nội dung chính liên quan đến phân cụm dữ liệu. Một số thuật toán phân cụm dữ liệu cơ bản cũng đƣợc trình bày chi tiết trong chƣơng này. Chương 3. Phân lớp dữ liệu và một số thuật toán cơ bản: Chƣơng này trình bày các nội dung chính liên quan đến phân lớp dữ liệu và ứng dụng. Một số
8 thuật toán phân lớp dữ liệu bao gồm: ID3, C.4.5, Naive Bayes, Apriori, … cũng sẽ đƣợc trình bày chi tiết trong chƣơng này. Chương 4. Một số kết quả thử nghiệm: Chƣơng này trình bày và phân tích một số kết quả thử nghiệm các thuật toán phân cụm, phân lớp dữ liệu cơ bản. Kết quả phân tích chủ yếu đƣợc triển khai thực hiện dựa trên phần mềm Weka (Waikato Environment for Knowledge Analysis) - một bộ phần mềm học máy đƣợc trƣờng Đại học Waikato, New Zealand phát triển bằng Java. Weka là phần mềm tự do phát hành theo Giấy phép Công cộng GNU, hiện đang đƣợc sử dụng rất rộng rãi bởi cộng đồng những ngƣời làm về lĩnh vực khai phá dữ liệu và phát hiện tri thức.
9 CHƢƠNG 1 TỔNG QUAN 1.1 Gi i thi u chung Sự phát triển của khoa học công nghệ và việc ứng dụng công nghệ thông tin ở hầu hết các lĩnh vực trong nhiều năm qua cũng đồng nghĩa với lƣợng dữ liệu đã đƣợc thu thập và lƣu trữ ngày càng lớn. Các hệ quản trị cơ sở dữ liệu truyền thống cũng chỉ khai thác đƣợc một lƣợng thông tin nhỏ không còn đáp ứng đầy đủ những yêu cầu, những thách thức mới. Do vậy các phƣơng pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng đƣợc thực tế đã làm phát triển một khuynh hƣớng kỹ thuật mới đó là kỹ thuật phát hiện tri thức và khai phá dữ liệu. Tôi xin giới thiệu một cách tổng quan về phát hiện tri thức và khai phá dữ liệu cùng một số kỹ thuật cơ bản để trong khai phá dữ liệu để phát hiện tri thức và một số ứng dụng trong thực tế nhằm hỗ trợ cho tiến trình ra quyết định. Khai phá dữ liệu (Data Mining) hay có thể hiểu là phát hiện tri thức (Knowledge Discovery) có rất nhiều khái niệm khác nhau nhƣng về cơ bản đó là quá trình tự động trích xuất thông tin có giá trị (thông tin dự đoán - Predictive Information) ẩn chứa trong lƣợng dữ liệu lớn trong thực tế. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). Về bản chất, nó liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy (regularities) trong tập dữ liệu. Khai phá dữ liệu là một tiến trình sử dụng các công cụ phân tích dữ liệu khác nhau để khám phá ra các mẫu dƣới nhiều góc độ khác nhau nhằm phát hiện ra các mối quan hệ giữa các dữ kiện, đối tƣợng bên trong cơ sở dữ liệu, kết quả của việc khai phá là xác định các mẫu hay các mô hình đang tồn tại bên trong, nhƣng chúng nằm ẩn khuất ở các cơ sở dữ liệu. Để từ đó rút trích ra đƣợc các mẫu, các mô hình hay
10 các thông tin và tri thức từ các cơ sở dữ liệu. Để hình dung rõ hơn Data Mining là gì có thể hiểu đơn giản nó chính là một phần của quá trình trích xuất những dữ liệu có giá trị tốt, loại bỏ dữ liệu giá trị xấu trong rất nhiều thông tin trên Internet và các nguồn dữ liệu đang có. 1.2 C c bƣ c trong khai phá dữ li u Qúa trình phát hiện tri thức gồm 6 giai đoạn [1] đƣợc thể hiện nhƣ hình sau: Hình 1.1. C c bƣ c trong khai phá dữ li u Đầu vào là dữ liệu thô đƣợc lấy từ internet và đầu ra là các thông tin có giá trị. (1) Gom dữ liệu: Tập hợp dữ liệu là bƣớc đầu tiên trong quá trình khai phá dữ liệu. Đây là bƣớc đƣợc khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web.
11 (2) Trích lọc dữ liệu: Ở giai đoạn này những tập dữ liệu cần đƣợc khai phá từ các tập dữ liệu lớn ban đầu theo một số tiêu chí nhất định phục vụ mục đích khai thác. (3) Làm sạch, tiền xử lý và chuẩn bị trƣớc dữ liệu: Đối với dữ liệu thu thập đƣợc, cần xác định các vấn đề ảnh hƣởng là cho nó không sạch. Bởi vì, dữ liệu không sạch (những dữ liệu không đầy đủ, nhiễu, không nhất quán) thì các tri thức khám phá đƣợc sẽ bị ảnh hƣởng và không đáng tin cậy, dẫn tới các quyết định thiếu chính xác. Vậy, cần gán các giá trị thuộc tính còn thiếu, sữa chữa các dữ liệu nhiễu, lỗi, xác định loại bỏ các giá trị ngoại lai, giải quyết các mâu thuẫn dữ liệu. Sau bƣớ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. Đây là một quá trình rất quan trọng vì dữ liệu này nếu không đƣợc “làm sạch - tiền xử lý dữ liệu” thì sẽ gây nên những kết quả sai lệch nghiêm trọng. (4) Chuyển đổi dữ liệu: Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đƣa ra có thể sử dụng và điều khiển đƣợc bởi việc tổ chức lại nó, tức là dữ liệu sẽ đƣợc chuyển đổi về dạng thuận lợi nhất nhằm phục vụ quá trình khai phá ở bƣớc sau. (5) Khai phá dữ liệu: Ở giai đoạn này nhiều thuật toán khác nhau đã đƣợc sử dụng để trích ra các mẫu từ dữ liệu. Đây là bƣớc áp dụng những kỹ thuật phân tích (nhƣ 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à bƣớc quan trọng và tốn nhiều thời gian nhất của toàn quá trình khai phá dữ liệu. (6) Đánh giá các luật và biểu diễn tri thức: Ở giai đoạn này, những mẫu thông tin và mối liên hệ trong dữ liệu đã đƣợc khám phá ở bƣớc trên đƣợc biến đổi và biểu diễn ở một dạng gần gũi với ngƣời sử dụng nhƣ đồ thị, cây, bảng biểu, luật,…
12 Đồng thời bƣớ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. Trên đây là 6 giai đoạn của quá trình phát hiện tri thức, trong đó giai đoạn 5 khai phá dữ liệu (hay còn gọi đó là Data Mining) là giai đoạn đƣợc đánh giá là quan trọng nhất. 1.3 Các kỹ thu t áp dụng trong khai phá dữ li u Đứng trên quan điểm của học máy, thì các kỹ thuật trong KPDL, bao gồm: Học có giám sát: Là quá trình gán nhãn cho các phần tử trong CSDL dựa trên một tập các ví dụ huấn luyện và các thông tin về nhãn đã biết. Học không có giám sát: Là quá trình phân chia một tập dữ liệu thành các lớp hay cụm dữ liệu tƣơng tự nhau mà chƣa biết trƣớc các thông tin về lớp hay tập các ví dụ huấn luyện. Học nửa giám sát: Là quá trình phân chia một tập dữ liệu thành các lớp dựa trên một tập nhỏ các ví dụ huấn luyện và các thông tin về một số nhãn lớp đã biết trƣớc. Nếu căn cứ vào lớp các bài toán cần giải quyết, thì KPDL bao gồm các kỹ thuật áp dụng sau: - Kĩ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong cơ sở dữ liệu hiện có. Các kĩ thuật này có thể liệt kê: phân cụm (clustering), tóm tắt (summerization), trực quan hóa (visualization), phân tích sự phát hiện biến đổi và độ lệch, phân tích luật kết hợp (association rules)...; - Kĩ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đƣa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Các kĩ thuật này gồm có: phân lớp (classification), hồi quy (regression)...;
13 3 phƣơng pháp thông dụng nhất trong khai phá dữ liệu là: phân cụm dữ liệu, phân lớp dữ liệu và khai phá luật kết hợp. Ta sẽ xem xét từng phƣơng pháp: Phân cụm dữ liệu là nhóm các đối tƣợng tƣơng tự nhau trong tập dữ liệu vào các cụm sao cho các đối tƣợng thuộc cùng một cụm là tƣơng đồng còn các đối tƣợng thuộc các cụm khác nhau sẽ không tƣơng đồng. Phân cụm dữ liệu là một ví dụ của phƣơng pháp học không giám sát. Không giống nhƣ phân loại dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trƣớc các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học bằng quan sát (learning by observation), trong khi phân loại dữ liệu là học bằng ví dụ (learning by example). Trong phƣơng pháp này bạn sẽ không thể biết kết quả các cụm thu đƣợc sẽ nhƣ thế nào khi bắt đầu quá trình. Vì vậy, thông thƣờng cần có một chuyên gia về lĩnh vực đó để đánh giá các cụm thu đƣợc. Phân cụm dữ liệu đƣợc sử dụng nhiều trong các ứng dụng về phân đoạn thị trƣờng, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web… Ngoài ra phân cụm dữ liệu còn có thể đƣợc sử dụng nhƣ một bƣớc tiền xử lí cho các thuật toán khai phá dữ liệu khác. Phân lớp dữ liệu là xếp một đối tƣợng vào một trong những lớp đã biết trƣớc. Ví dụ nhƣ phân lớp các dữ liệu bệnh nhân trong hồ sơ bệnh án. Hƣớng tiếp cận này thƣờng sử dụng một số kỹ thuật của học máy nhƣ cây quyết định, mạng nơron nhân tạo,... Phân lớp dữ liệu còn đƣợc gọi là học có giám sát. Quá trình phân lớp dữ liệu thƣờng gồm 2 bƣớc xây dựng mô hình và sử dụng mô hình để phân lớp dữ liệu. Bƣớc 1: Một mô hình sẽ đƣợc xây dựng dựa trên việc phân tích các mẫu dữ liệu sẵn có. Mỗi mẫu tƣơng ứng với một lớp, đƣợc quyết định bởi một thuộc tính gọi là thuộc tính lớp. Các mẫu dữ liệu này còn đƣợc gọi là tập dữ liệu huấn luyện (training data set). Các nhãn của tập dữ liệu huấn luyện đều
14 phải đƣợc xác định trƣớc khi xây dựng mô hình, vì vậy phƣơng pháp này còn đƣợc gọi là học có thầy (supervised learning) khác với phân cụm dữ liệu là học không có thầy (unsupervised learning). Bƣớc 2: Sử dụng mô hình để phân lớp dữ liệu. Trƣớc hết chúng ta phải tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận đƣợc, mô hình sẽ đƣợc sử dụng để dự đoán nhãn cho các mẫu dữ liệu khác trong tƣơng lai. Khai phá luật kết hợp (Association Rule Mining) là kỹ thuật rất quan trọng trong lĩnh vực khai phá dữ liệu. Mục đích của việc khai phá luật kết hợp là tìm ra các mối quan hệ, sự kết hợp hay mối tƣơng quan giữa các đối tƣợng trong khối lƣợng lớn dữ liệu. Nói cách khác, thuật toán khai phá luật kết hợp cho phép tạo ra các luật mô tả các sự kiện xảy ra đồng thời (một cách thƣờng xuyên) nhƣ thế nào. Thuật toán này thực hiện thông qua 2 giai đoạn chính: - Giai đoạn đầu là đi tìm các sự kiện xảy ra thƣờng xuyên. - Giai đoạn hai là tìm luật. 1.4 Ứng dụng của khai phá dữ li u Mặc dù còn rất nhiều vấn đề mà KPDL cần phải tiếp tục nghiên cứu để giải quyết nhƣng tiềm năng của nó đã đƣợc khẳng định bằng sự ra đời của rất nhiều ứng dụng. Các ứng dụng của KPDL trong khoa học cũng đƣợc phát triển. Các công ty phần mềm lớn trên thế giới cũng rất quan tâm và chú trọng tới việc nghiên cứu và phát triển kỹ thuật khai phá dữ liệu: Oracle tích hợp các công cụ khai phá dữ liệu vào bộ Oracle9i, IBM đã đi tiên phong trong việc phát triển các ứng dụng khai phá dữ liệu với các ứng dụng nhƣ Intelligence Miner. Ta có thể đƣa ra một số ứng dụng trong các lĩnh vực nhƣ: Ngân hàng: Xây dựng mô hình dự báo rủi ro tín dụng, tìm kiếm tri thức, quy luật của thị trƣờng chứng khoán và đầu tƣ bất động sản.
15 Thƣơng mại điện tử: Công cụ tìm hiểu, định hƣớng, thúc đẩy, giao tiếp với khách hàng, phân tích khách hàng duyệt web, phân tích hành vi mua sắm trên mạng và cho biết thông tin tiếp thị phù hợp với từng loại khách hàng. Thiên văn học: Hệ thống SKICAT do JPL/Caltech phát triển đƣợc sử dụng cho các nhà thiên văn để tự động xác định các vì sao và các dải thiên hà trong một bản khảo sát lớn để có thể phân tích và phân loại. Sinh học phân tử: Hệ thống tìm kiếm các mẫu trong cấu trúc phân tử và trong các dữ liệu gen. Mô hình hóa những thay đổi thời tiết: các mẫu không gian, thời gian nhƣ lốc, gió xoáy đƣợc tự động tìm thấy trong các tập lớn dữ liệu mô phỏng và quan sát đƣợc. 1.5 Những thách thức trong khai phá dữ li u Mặc dù khai phá dữ liệu mang lại nhiều lợi ích và lợi thế, tuy nhiên nó vẫn gặp phải những thách thức cơ bản đó là những vấn đề sau đây: - Cơ sở dữ liệu lớn: kích thƣớc của cơ sở dữ liệu đƣợc nhận biết thông qua số lƣợng các mẫu tin, các thuộc tính (hay các biến) và các bảng, số lƣợng có thể là hàng trăm thuộc tính và bảng, hàng triệu các mẫu tin. Nhƣ vậy, kích thƣớc của cơ sở dữ liệu tính bằng terabyte đã bắt đầu xuất hiện. Dữ liệu với số chiều (tƣơng ứng với thuộc tính khi biểu diễn qua không gian các mẫu dữ liệu) lớn tạo nên sự gia tăng về kích thƣớc của không gian tìm kiếm trong việc quy nạp mô hình, một sự bùng nổ về tổ hợp. Khi xây dựng mô hình chỉ một tập con trong cơ sở dữ liệu tham gia, vì vậy tính may rủi trong các thuật toán khai phá sẽ tìm đƣợc các mẫu không có giá trị trong trƣờng hợp tổng quát. Một giải pháp cho vấn đề này là giảm bớt đáng kể số chiều của bài toán và sử dụng tri thức trƣớc (prior knowledge) để nhận biết các biến ít liên quan và loại bỏ chúng.
16 - Vấn đề “quá khớp” (Over-fitting): Khi thuật toán khai phá tìm kiếm với các tham số tốt nhất cho một mô hình đặc biệt và một giới hạn của tập dữ liệu, mô hình ấy có thể “quá khớp” trên tập dữ liệu ấy nhƣng lại thi hành không chính xác trên tập dữ liệu kiểm tra. Một giải pháp thƣờng đƣợc sử dụng là thẩm định chéo. - Thay đổi dữ liệu và tri thức: Dữ liệu là không tĩnh, dữ liệu luôn thay đổi nhanh chóng có thể dẫn đến những mẫu đã khai phá trƣớc đây không còn hiệu lực. Thêm vào đó, các biến đã đƣợc đo trong cơ sở dữ liệu ứng dụng đã bị thay đổi, bị xóa hoặc đã tăng lên với một độ đo mới. Điều này có thể đƣợc thực hiện bằng cách gia tăng các phƣơng thức cập nhật các mẫu và xem xét các thay đổi nhƣ là một cơ hội cho việc khám phá bằng việc sử dụng nó để xử lý thích hợp việc tìm kiếm các mẫu chỉ với sự thay đổi. - Dữ liệu thiếu và nhiễu: Đây là vấn đề rất đƣợc quan tâm trong khai phá dữ liệu, điều này thƣờng dẫn đến việc dự đoán thiếu chính xác. - Tích hợp với hệ thống: Hệ thống khai phá dữ liệu thực sự là hữu ích khi phải đƣợc tích hợp với cơ sở dữ liệu thông qua các giao diện nhƣ truy vấn, bảng tính và các công cụ trực quan khác. Hơn nữa, phải tạo ra một môi trƣờng thuận lợi cho việc tƣơng tác với ngƣời dùng.
17 CHƢƠNG 2 PHÂN CỤM DỮ LIỆU VÀ MỘT SỐ THUẬT TOÁN CƠ BẢN 2.1 Đị h ghĩa về phân cụm dữ li u Phân cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó thuộc lớp các phƣơng pháp học không giám sát trong Machine Learning. Có rất nhiều định nghĩa khác nhau về kỹ thuật này, nhƣng về bản chất ta có thể hiểu phân cụm là các qui trình tìm cách nhóm các đối tƣợng đã cho vào các cụm (clusters), sao cho các đối tƣợng trong cùng một cụm tƣơng tự (similar) nhau và các đối tƣợng khác cụm thì không tƣơng tự (dissimilar) nhau. Chúng ta có thể có thể minh hoạ vấn đề phân cụm nhƣ hình sau: Hình 2.1. Mô phỏng vấ đề phân cụm dữ li u Trong trƣờng hợp này, chúng ta dễ dàng xác định đƣợc 3 cụm dựa vào các dữ liệu đã cho, các tiêu chí “tƣơng tự” để phân cụm trong trƣờng hợp này
18 là khoảng cách hai hoặc nhiều đối tƣợng thuộc nhóm của chúng đƣợc “đóng gói” theo một khoảng cách nhất định. Điều này đƣợc gọi là phân cụm dựa trên khoảng cách. Một kiểu khác của phân cụm dữ liệu là phân cụm dữ liệu dựa vào khái niệm hai hay nhiều đối tƣợng thuộc cùng nhóm nếu có một định nghĩa khái niệm chung cho tất cả các đối tƣợng trong đó. Nói cách khác, đối tƣợng của nhóm phải phù hợp với nhau theo miêu tả các khái niệm đã đƣợc định nghĩa, không phải theo những biện pháp đơn giản tƣơng tự. Kỹ thuật phân cụm có thể áp dụng trong rất nhiều lĩnh vực như: - Marketing: Xác định các nhóm khách hàng (khách hàng tiềm năng, khách hàng giá trị, phân loại và dự đoán hành vi khách hàng,…) sử dụng sản phẩm hay dịch vụ của công ty để giúp công ty có chiến lƣợc kinh doanh hiệu quả hơn. - Sinh học: Phân nhóm động vật và thực vật dựa vào các thuộc tính của chúng. - Thƣ viện: Theo dõi độc giả, sách, dự đoán nhu cầu của độc giả. - Bảo hiểm, tài chính: 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 . - Mạng lƣới toàn cầu: Phân loại tài liệu, phân loại ngƣời dùng web. 2.2 Mục tiêu của phân cụm dữ li u Mục tiêu của phân cụm dữ liệu là để xác định các nhóm nội tại bên trong một bộ dữ liệu không có nhãn. Nhƣng để có thể quyết định đƣợc cái gì tạo thành một cụm tốt, làm thế nào để quyết định cái gì đã tạo nên một phân cụm dữ liệu tốt ? Nó có thể đƣợc hiển thị rằng không có tiêu chuẩn tuyệt đối “tốt nhất” mà sẽ là độc lập với mục đích cuối cùng của phân cụm dữ liệu.