Chương 1: Tổng quan về phân cụm dữ liệu. Giới thiệu về phân cụm dữ liệu và các phƣơng pháp phân cụm. Chương 2: Lý thuyết tập thô. Trình bày tổng quan về lý thuyết tập thô bao gồm hệ thông tin, bảng quyết định, tính không phân biệt đƣợc và xấp xỉ tập hợp.
Chương 3:Áp dụng thuật toán phân cụm thô vào bài toán phân cụm ngƣời dùng trên Web. Dựa trên lý thuyết tập thô và áp dụng thuật toán phân cụm thô phân cụm ngƣời dùng trên Web( chuyển hƣớng Web của ngƣời dùng). LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 3 CHƢƠNG I TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 1.1 Phân cụm dữ liệu là gì Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu nhằm tìm kiếm, phát hiện các cụm, cácmẫu dữ liệu tự nhiên, tiềm ẩn, quan trọng trong tập dữ liệu lớn từ đó cung cấpthông tin, tri thức hữu ích cho việc ra quyết định. Phân cụm nhìn từ góc độ tự nhiên là một việc hết sức bình thƣờng mà chúng ta vẫn làm và thực hiện hàng ngày.
Ví dụ nhƣ phân loại học sinh trong lớp; phân loại đất đai; phân loại tài sản; phân loại sách trong thƣ viện;… Cụm dữ liệu là tập hợp các đối tƣợng có những tính chất nào đó tƣơng tự nhau ở một mức độ nào đó trong tập dữ liệu. Ở một mức cơ bản nhất, ngƣời ta đã đƣa ra định nghĩa phân cụm dữ liệu (PCDL) nhƣ sau:[3] “Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu (Data mining), nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, quan tâm trong tập dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho ra quyết định.” Quá trình PCDL là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao các phần tử trong cùng một cụm thì “tƣơng tự” nhau và các phần tử trong các cụm khác nhau thì “kém tƣơng tự” nhau. Số các cụm dữ liệu đƣợc phân ở đây có thể đƣợc xác định trƣớc theo kinh nghiệm hoặc có thể đƣợc tự động xác định theo phƣơng pháp phân cụm.1 Mô phỏng vấn đề phân cụm dữ liệu. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 Trong học máy, PCDL đƣợ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ƣa biết trƣớc các thông tin về cụm, các thông tin về tập huấn luyện hay thông tin nhãn của các lớp.
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 bƣớ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.[3,2] Với một tập dữ liệu, quá trình phân cụm có thể cho ra nhiều kết quả khác nhau tùy thuộc vào tiêu chí cụ thể đƣợc sử dụng để phân cụm. Các bƣớc cơ bản của quá trình phân cụm đƣợc thể hiện trong hình 1.1 và đƣợc tóm tắt nhƣ sau: Lựa chọn đặc trưng (Feature selection): các đặc trƣng phải đƣợc lựa chọn một cách hợp lý để có thể “mã hóa” nhiều thông tin nhất liên quan đến nhiệm vụ mà chúng ta quan tâm. Mục tiêu chính là giảm thiểu dƣ thừa thông tin giữa các đặc trƣng. Do đó, tiền xử lý dữ liệu là một nhiệm vụ quan trọng trƣớc khi tiến hành các bƣớc sau.
Lựa chọn thuật toán phân cụm (clustering algorithm selection): cần lựa chọn một sơ đồ thuật toán riêng biệt nhằm làm sáng tỏ cấu trúc của tập dữ liệu. Đánh giá kết quả phân cụm (validation of results): Khi đã có kết quả phân cụm thì ta phải kiểm tra tính đúng đắn của nó. Với cùng một tập dữ liệu, những cách tiếp cận khác nhau thƣờng dẫn tới các kết quả phân cụm khác nhau và ngay cả cùng một thuật toán với các tham số đầu vào khác nhau cũng cho ra các kết quả khác nhau. Vì vậy, các tiêu chuẩn và tiêu chí để đánh giá kết quả phân cụm là rất quan trọng.
Nó cung cấp cho ngƣời dùng mức độ tin cậy của các kết quả mà thuật toán phân cụm thực hiện. Giải thích kết quả (interpretation of results): Mục tiêu cuối cùng của việc phân cụm là cung cấp cho ngƣời sử dụng những hiểu biết ý nghĩa từ dữ liệu gốc. Các chuyên gia phải giải thích những phân vùng dữ liệu thu đƣợc. Trong nhiều trƣờng hợp, các chuyên gia trong các lĩnh vực ứng dụng phải tích hợp các kết quả phân cụm với các bằng chứng thực nghiệm khác và phân tích để rút ra những kết luận đúng.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Các bƣớc của quá trình phân cụm dữ liệu.2 Thế nào là phân cụm tốt Một phƣơng pháp phân cụm tốt sẽ sinh ra các cụm có chất lƣợng cao [3], trong đó: - Mức độ tƣơng tự giữa các đối tƣợng trong cùng một cụm là cao. - Mức độ tƣơng tự giữa các đối tƣợng nằm trong các cụm khác nhau là thấp.3 Tiêu chuẩn phân cụm. Chất lƣợng của kết quả phân cụm phụ thuộc vào cả độ đo tƣơng tự đƣợc sử dụng và cách thức thực hiện. Chất lƣợng của phƣơng pháp phân cụm cũng đƣợc đánh giá bởi khả năng phát hiện các mẫu tiềm ẩn.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 Các yêu cầu của phân cụm trong khai phá dữ liệu:[3,2] Việc xây dựng và lựa chọn một thuật toán phân cụm là bƣớc then chốt cho việc giải quyết vấn đề phân cụm, sự lựa chọn này phụ thuộc vào đặc tính dữ liệu cần phân cụm, mục đích của ứng dụng thực tế hoặc xác định độ ƣu tiên giữa chất lƣợng của các cụm hay tốc độ thực hiện thuật toán,. Hầu hết các nghiên cứu và phát triển thuật toán PCDL đều nhằm thỏa mãn các yêu cầu cơ bản sau: - Có khả mở rộng : Một số thuật toán có thể ứng dụng tốt cho tập dữ liệu nhỏ (khoảng 200 bản ghi dữ liệu) nhƣng không hiệu quả khi áp dụng cho tập dữ liệu lớn(khoảng 1 triệu bản ghi). - Thích nghi với các kiểu dữ liệu khác nhau: Thuật toán có thể áp dụng hiệu quả cho việc phân cụm các tập dữ liệu với nhiều kiểu dữ liệu khác nhau nhƣ dữ liệu kiểu số, kiểu nhị phân, dữ liệu định danh, hạng mục,…và thích nghi với dữ liệu hỗn hợp. - Khám phá ra các cụm với hình dạng bất kỳ: Do hầu hết các CSDL có chứa nhiều cụm dữ liệu với các hình thù khác nhau nhƣ: Hình lõm, hình cầu, hình que,…Vì vậy, để khám phá đƣợc các cụm có tính tự nhiên thì các thuật toán phân cụm cần phải có khả năng khám phá ra các cụm dữ liệu có hình thù bất kỳ.
- Tối thiểu lượng tri thức cần cho xác định các tham số vào: Do các giá trị đầu vào ảnh hƣởng rất lớn đến thuật toán phân cụm và rất phức tạp để xác định các giá trị vào thích hợp đối với các CSDL lớn. - Khả năng thích nghi với dữ liệu nhiễu: Hầu hết các dữ liệu phân cụm trong khai phá dữ liệu đều chứa đựng các dữ liệu lỗi, dữ liệu không đầy đủ, dữ liệu rác. Thuật toán phân cụm không những hiệu quả đối với các dữ liệu nhiễu mà còn tránh dẫn đến chất lƣợng phân cụm thấp do nhạy cảm với nhiễu. - Ít nhạy cảm với các tham số đầu vào: Nghĩa là giá trị của các tham số đầu vào khác nhau ít gây ra các thay đổi lớn đối với kết quả phân cụm.
- Có khả năng phân cụm với dữ liều có số chiều cao: Thuật toán có khả năng áp dụng hiệu quả cho dữ liệu có số chiều khác nhau. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 - Dễ hiểu, cài đặt và khả thi: Các yêu cầu này đồng thời là các tiêu chí để đánh giá hiệu quả của các phƣơng pháp PCDL, đây là những thách thức cho các nhà nghiên cứu trong lĩnh vực PCDL.3 Các ứng dụng của phân cụm dữ liệu Phân cụm dữ liệu là một trong những công cụ chính đƣợc ứng dụng trong nhiều lĩnh vực. Một số ứng dụng của phân cụm nhƣ: [3] Xử lý dữ liệu lớn: việc khám phá tri thức trong các cơ sở dữ liệu thƣờng phải xử lý khối lƣợng dữ liệu rất lớn, nhiều khi ngay cả các thuật toán với độ phức tạp tính toán là đa thức cũng không dùng đƣợc. Do đó, việc phân và xử lý theo các cụm là một giải pháp hữu hiệu.
Tạo giả thuyết: phân tích cụm đƣợc sử dụng để suy ra một số giả thuyết liên quan đến dữ liệu. Ví dụ: dựa trên tuổi tác và thời điểm mua hàng, chúng ta có thể tìm thấy trong một cơ sở dữ liệu bán lẻ có hai nhóm khách hàng quan trọng. Sau đó, chúng ta có thể suy ra một số giả thuyết cho dữ liệu là: "những người trẻ tuổi đi mua sắm vào buổi tối", "người già đi mua sắm vào buổi sáng". Kiểm định giả thuyết: Trong trƣờng hợp này, phân tích cụm đƣợc sử dụng cho việc xác minh tính hợp lệ của một giả thuyết cụ thể.
Ví dụ, chúng ta xem xét giả thuyết nhƣ sau: "Những người trẻ tuổi đi mua sắm vào buổi tối". Một cách để xác minh điều này là áp dụng phân tích cụm cho một tập đại diện các cửa hàng. Giả sử rằng mỗi cửa hàng đƣợc đặc trƣng bởi các chi tiết của khách hàng (tuổi tác, công việc, …) và thời điểm giao dịch. Nếu, sau khi áp dụng phân tích cụm, một cụm tƣơng ứng với "những người trẻ mua sắm vào buổi tối" đƣợc tạo thành, thì giả thuyết ban đầu đã đƣợc chứng minh là hợp lệ.
Cụ thể, 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 sau: Thương mại: Trong thƣơng mại, phân cụm dữ liệu 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 nhau và đặc tả họ từ các mẫu mua bán trong cơ sở dữ liệu khách hàng. Sinh học: Phân cụm dữ liệu đƣợ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 những hiểu biết bên trong những cấu trúc của quần thể. Phân tích dữ liệu không gian: Do một lƣợng lớn dữ liệu không gian có thể thu đƣợc từ các hình ảnh vệ tinh, thiết bị y tế, hệ thống thông tin địa lý (GIS), cơ sở dữ liệu hình ảnh thăm dò,… làm cho ngƣời dùng tốn kém và khó khăn để kiểm tra các LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 dữ liệu không gian một cách cụ thể. Phân cụm dữ liệu có thể giúp ngƣời dùng tự động phân tích và xử lý các dữ liệu không gian.