Lời mở đầu Mục lục Danh mục các hình vẽ. Danh mục từ viết tắt. Tổng quan khai phá dữ liệu. Các phương pháp khai phá dit liệu.
Ứng dụng thực tiễn của khai phá dữ liệu. Gom cụm dữ liỆu. Các ứng dụng thực tiên. Các yêu cau của gom cụm.
Các phương pháp gom cụm dit liệu.--------+©5+555+ 14 WA SRE? lGum ph nhOạch. Gom cụm phân cấp 1. Gom cụm dựa trên mật đỘ. cc sec S+Ssccvesxeerrrer 17 1.
Gom cụm dựa trên lưới 1. Gom cụm dựa trên mô hình. Gom cụm có ràng buộc Chương2. Gom cụm dữ liệu mờ.
ˆ Thuậttoán FCM oii sassccszscscasasnsatsstsesasassosasassssesassssasassssasossssstsseressevestisssssassn DO QLD. TRUGE TORI sscscxssssscasssssasesssaszssssasssssscssnsssosssnssssszosessszesneassosssasessssesessssssszs 23 2. Thuật toán Epsilon FCM. Khái NGM cecseecsecseecsessseeseesseeseesseessessesseessesseessesseesseessessessuesseesseeseesseesy 25 2.
Thuật OGM essesecsecsecsessessesceseesessesnesesseseesessesseseessesessssueseeseesseseeneseeseeneeses 26 Chương 3. Gom cụm dữ liệu mờ động. Gom cụm mờ động 3. Hàm mục tiêu của bài toán 3.
Ma trận trọng 3. Sự thay đổi theo thời gian. Bước cập nhật dit liệu. Gom cụm mờ động mở rộng.
Thuật toán gom cụm mờ truyện thong .2 đÊ NHh dt toán: ZOMICUMTIOTAGI IAM. Cấu trúc mau dữ liệu 3. Kết quả gom cụm và sự thay đổi theo thời gian. Trọng số thành phẩhn.
Ma trận khoảng cách 3. Thuật toán gom cụm mờ động mở rỘNg. Thuật toán EDFC đề xuấT.7225NI2)101DTHEC TAD Của CRUG EOÁN,. Cấu trúc mẫu dữ liệu.
Trọng số môn học. Sự thay đổi theo thời gian. Sự phụ thuộc trọng số môn học 4. Sự phụ thuộc trọng số thành ph 4.
So sánh kết quả gom cụm với thuật toán DFC. Kết lua Tài liệu tham khảo. Danh mục các hình vẽ Hình 1.1 - Các bước trong KDD [11] Hình 1.2 - Một ví dụ gom cụm dữ liệu .3 - Minh họa thuật toán K-Means. - - 6 65+ se Sxvxxeeevrvrrrrre 16 Hình 4.1 - File dữ liệu demo.2 - Sự thay đổi của 3 tâm cụm theo thời gian.3 - Sự thay đổi tâm cụm và một mẫu ““2 Ì”.cc¿¿+222vvvc+zztzcvccse+ 49 Hình 4.4 - Sự phụ thuộc trọng số môn học - lần Chạy Ì.5 - Sự phụ thuộc trọng số môn học - lần Chạy 2 .6 - Sự phụ thuộc trọng số môn học - lần CHẠY 20.7 - Sự phụ thuộc trọng số thành phần - lần chạy Ï.8 - Sự phụ thuộc trọng số thành phần - lần Chạy 2.
2105: ii 2:2 TP 54 Hình 4.9 - Sự phụ thuộc trọng số thành phần - lần chạy 3.10 - So sánh kết quả gom cụm với thuật toán DFC - lần chạy L.11 - So sánh kết quả gom cụm với thuật toán DFC - lần chạy 2.12 - So sánh kết quả gom cum với thuật toán DFC - lần chạy 3. 58 Danh mục từ viết tắt FCM: Fuzzy C-means. cFCM: c-Insensitive Fuzzy C-Means. CSDL: Cơ sở dữ liệu.
KDD: Knowleadge Discovery in Database. DFC: Dynamic Fuzzy Clustering. EDFC: Extended Dynamic Fuzzy Clustering. Tổng quan khai phá dữ liệu 1.
Khai phá dữ liệu là gì? Khoảng hơn một thập kỷ trở lại đây, lượng thông tin được lưu trữ trên các thiết bị điện tử (đĩa cứng, CD-ROM, băng từ, .) không ngừng tăng lên. Sự tích lũy dữ liệu này xảy ra với một tốc độ bùng nổ. Người ta ước đoán rằng lượng thông tin trên toàn cầu tăng gap đôi sau khoảng hai năm và theo đó số lượng cũng như kích cỡ của các cơ sở dữ liệu (CSDL) cũng tăng lên một cách nhanh chóng. Nói một cách trừu tượng là chúng ta đang “ngập” trong dir liệu nhưng lại “đói” tri thức.
Câu hỏi đặt ra là liệu chúng ta có thê khai thác được gì từ những “núi” dữ liệu tưởng chừng như “bỏ di” ấy không ? Khám phá tri thức hay phát hiện tri thức trong cơ sở dit liệu là một qui trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tinh năng: phân tích, tong hợp, hợp thức, khả dụng và có thể hiểu được. Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp dữ liệu khổng lồ và phức tap, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ liệu đó. Khai phá dữ liệu là một bước trong bảy bước của quá trình KDD như sau: > Làm sạch dữ liệu và tiền xử lý: loại bỏ nhiễu và các dữ liệu không cần thiết. > Tích hợp dữ liệu: quá trình hợp nhất dữ liệu thành những kho dữ liệu sau khi đã làm sạch và tiền xử lý.
> Trích chon dữ liệu: trích chọn dữ liệu từ những kho dit liệu và sau đó chuyền đổi về dạng thích hợp cho quá trình khai phá dữ liệu. Quá trình này bao gồm cả việc xử lý với dữ liệu nhiễu, dữ liệu không day đủ. > Chuyên đổi dữ liệu: các dữ liệu được chuyên đổi sang các dang phù hợp cho quá trình xử lý. > Khai phá dữ liệu: là một trong các bước quan trọng nhất, trong đó sử dụng những phương pháp thông minh đề chat lọc ra những mẫu dữ liệu.
> Ước lượng mẫu: quá trình đánh giá các kết quả tìm được thông qua các độ đo nào đó. > Biểu diễn tri thức: quá trình này sử dụng các kỹ thuật để biểu diễn và thé hiện trực quan cho người dùng. Evaluation ia ACTION Data Mining| Transformation KNOWLEDGE Preprocessing Selection == PATTERNS L] iDATA ay 1| TRANSFORMED QA DATA ⁄ PREPROCESSED < DATA DATA Hình 1.1 - Các bước trong KDD [11] 1. Các phương pháp khai phá dữ liệu Với hai mục đích chính trong khai phá dit liệu là mô tả và dự đoán, người ta thường sử dụng các phương pháp sau: > Mô tả khái niệm: thiên về mô tả, tổng hợp và tóm tắt khái niệm.
Ví dụ: tóm tắt văn bản. > Luật kết hợp: là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Vi dụ: “60 % nam giới vào siêu thị nếu mua bia thì có tới 80% trong số họ sẽ mua thêm thịt bò khô”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin học — sinh học, tài chính & thị trường chứng khoán.
Vv Phân lớp va dự đoán: xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Hướng tiếp cận này thường sử dụng một số kỹ thuật của máy học như cây quyết định, mạng nơ ron nhân tạo. Người ta còn gọi phân lớp là học có giám sát.
> Gom cụm: xếp các đối tượng theo từng cụm, số lượng cũng như tên của cụm chưa được biết trước. Người ta còn gọi gom cụm là học không giám sát. > Khai phá chuỗi: tương tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao.
Ứng dụng thực tiễn của khai phá dữ liệu Khai phá dữ liệu tuy là một hướng tiếp cận mới nhưng thu hút được rất nhiều sự quan tâm của các nhà nghiên cứu và phát triển nhờ vào những ứng dụng thực tiễn của nó. Chúng ta có thé liệt kê ra đây một số ứng dụng điền hình: Phân tích dữ liệu và hỗ trợ ra quyết định. VY Điều trị y học. Khai phá văn bản và khai phá web.
Tin học - sinh học. VYv Tài chính và thị trường chứng khoán. Gom cụm đữ liệu 1. Khái niệm Gom cụm dữ liệu là quá trình gom các đối tượng vào các cụm đối tượng mà trong cùng cụm các đối tượng có độ tương đồng cao nhất, còn giữa các cụm các đối tượng có độ tương đồng thấp nhất hoặc không tương đồng.
Gom cụm dữ liệu là phương pháp học không giám sát. Không giống như phân lớp, gom cụm 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 gom cụm dữ liệu là một cách học bằng quan sát, trong khi phân lớp dữ liệu là học bằng ví dụ. Ngoài ra gom cụm đữ 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 như phân loại và mô tả đặc điểm, có tác dụng trong việc phát hiện ra các cụm.
11 Gom cụm có ý nghĩa rất quan trọng trong hoạt động của con người. Gom cụm được sử dụng rộng rãi trong nhiều lĩnh vực như nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh, nghiên cứu thị trường, dự báo. Theo nghiên cứu cho thấy thì hiện nay chưa có một phương pháp gom cụm tổng quát nào có thé giải quyết tron vẹn cho tat cả các dang cấu trúc cơ sở dữ liệu. Hơn nữa, các phương pháp gom cụm cần có cách biéu diễn cấu trúc của các cơ sở dữ liệu, với mỗi cách biểu diễn khác nhau sẽ có tương ứng một thuật toán gom cụm phù hợp.
Vì vậy gom cụm dữ liệu vẫn đang là van đề khó và mở. Các ứng dung thực tiễn Gom cụm dữ liệu hiện đang áp dụng rất nhiều trong thực tiễn như: > Thương mại: tìm kiếm nhóm các khách hàng quan trọng có đặc trưng tương đồng và những đặc tả họ từ các bản ghi mua bán trong cơ sở dữ liệu. > Sinh học: phân loại các gen với các chức năng tương đồng và thu được các cấu trúc trong mẫu. > Thư viện: phân loại các cụm sách có nội dung và ý nghĩa tương đồng nhau dé cung cấp cho độc giả.
> Bảo hiểm: nhận dạng nhóm tham gia bảo hiểm có chỉ phí bồi thường cao, nhận dạng gian lận thương mại. > Qui hoạch đô thị: nhận dạng các nhóm nhà theo kiểu và vị trí dia lý. nhằm cung cấp thông tin cho quy hoạch đô thị. > Nghiên cứu trái đất: gom cụm dé theo dõ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.
> www: có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý nghĩa trong môi trường web. 12 > Dự báo: một hướng nghiên cứu mới hoàn toàn trong vai năm trở lại đây và được áp dụng hầu như trong mọi lĩnh vực, chẳng hạn: dự báo kết quả học tập sinh viên, dự báo chỉ số chứng khoán, dự báo thời tiết,. Các yêu cầu của gom cụm > Có khả năng mở rộng: nhiều thuật toán gom cụm làm việc tốt với những tập dữ liệu nhỏ, tuy nhiên một cơ sở dữ liệu lớn có thể chứa tới hàng triệu đối tượng. Việc gom cụm đối với một tập dữ liệu lớn có thé làm ảnh hưởng tới kết quả.
Do đó việc cần thiết là chúng ta phải phát triển các thuật toán gom cụm có khả năng mở rộng cao. đối với cơ sở dữ liệu lớn. > Khả năng thích nghỉ với các kiểu thuộc tính khác nhau: nhiều thuật toán được thiết kế cho việc gom cum dir liệu có kiêu khoảng (kiểu số).