Chương 1: Tổng quan về khai phá dữ liệu Chƣơng này trình bày tổng quan về khai phá dữ liệu và khai phá dữ liệu nhằm phát hiện tri thức từ một kho dữ liệu; hƣớng tiếp cận, kỹ thuật áp dụng và lĩnh vực ứng dụng. 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2: Luật kết hợp và thuật toán tìm luật kết hợp Trong chƣơng này ta đi tìm hiểu các kỹ thuật, thuật toán khai phá dữ liệu sử dụng luật kết hợp từ thuật toán đầu tiên Apriori tới các kỹ thuật cải tiến của thuật toán này nhằm nâng cao hiệu quả của quá trình tính toán. Chương 3: Ứng dụng luật kết hợp để khai phá dữ liệu tai nạn giao thông Chƣơng này trình bày bài toán và ứng dụng luật kết hợp để khai phá dữ liệu tai nạn giao thông. Nội dung trình bày trong chƣơng này bao gồm mục tiêu, yêu cầu của bài toán, kết quả phân tích, thiết kế và xây dựng chƣơng trình.
6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỹ 1980. Nó là quá trình khám phá những thông tin tiềm ẩn trong các cơ sở dữ liệu và có thể xem nhƣ là một bƣớc trong quá trình khám phá tri thức. Khai phá dữ liệu là giai đoạn quan trọng nhất trong tiến trình khai phá tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ trong việc ra quyết định. Để hình dung vấn đề này ta có thể sử dụng một ví dụ đơn giản nhƣ sau: Khai phá dữ liệu đƣợc ví nhƣ tìm một cây kim trong đáy bể (biển).
Trong ví dụ này, cây kim là một mảnh nhỏ tri thức hoặc một thông tin có giá trị và đáy bể (biển) là một kho cơ sở dữ liệu rộng lớn. Nhƣ vậy, những thông tin có giá trị tiềm ẩn trong kho cơ sở dữ liệu sẽ đƣợc chiết xuất ra và sử dụng một cách hữu ích nhờ khai phá dữ liệu. Chức năng của khai phá dữ liệu gồm có gộp nhóm phân loại, dự báo, dự đoán và phân tích các liên kết. Năm 1989 Fayyad, Smyth và Piatestsky-Shapiro đã dùng khái niệm Phát hiện tri thức từ cơ sở dữ liệu.
Trong đó, khai phá dữ liệu là một giai đoạn rất đặc biệt trong toàn bộ quá trình, nó sử dụng các kỹ thuật để tìm ra các mẫu từ dữ liệu. Định nghĩa: Khai phá dữ liệu là quá trình tìm kiếm các mẫu mới, những thông tin tiềm ẩn mang tính dự đoán trong các khối dữ liệu lớn. Những công cụ khai phá dữ liệu có thể phát hiện những xu hƣớng trong tƣơng lai, các tri thức mà khai phá dữ liệu mang lại cho các doanh nghiệp, các cơ quan quản lý chính sách có thể ra các quyết định kịp thời và trả lời những câu hỏi trong lĩnh vực kinh doanh mà trƣớc đây tốn nhiều thời gian để xử lý. Các dạng dữ liệu có thể khai phá: Có rất nhiều kiểu dữ liệu có thể đƣợc khai phá và các dạng dữ liệu điển hình có thể đƣợc khai phá là2: - Cơ sở dữ liệu quan hệ: là các cơ sở dữ liệu tác nghiệp đƣợc tổ chức theo mô hình dữ liệu quan hệ.
Hầu hết các hệ quản trị cơ sở dữ liệu đều hỗ trợ dữ liệu dạng này nhƣ Oracle, SQL Server, MS Access,. - Cơ sở dữ liệu đa chiều (data warehouse, data mart): là các kho dữ liệu đƣợc tập hợp, chọn lọc từ nhiều nguồn dữ liệu khác nhau. Dạng dữ liệu này mang tính lịch sử (tức 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com là có tính thời gian) và chủ yếu phục vụ cho quá trình phân tích cũng nhƣ khai phá tri thức nhằm hỗ trợi cho việc ra quyết định - Cơ sở dữ liệu dạng giao dịch (transactional database): là dạng cơ sở dữ liệu tác nghiệp nhƣng bản ghi thƣờng là các giao dịch. Dạng dữ liệu này thƣờng phổ biến trong lĩnh vực thƣơng mại và ngân hàng.
- Cơ sở dữ liệu quan hệ - đối tƣợng : là dạng cơ sở dữ liệu lai giữa hai mô hình quan hệ và hƣớng đối tƣợng. - Dữ liệu không gian và thời gian (spatial, time – series data): là dạng dữ liệu có tích hợp thuộc tính về không gian nhƣ dữ liệu bản đồ hoặc dữ liệu tích hợp thuộc tính về thời gian nhƣ dữ liệu chứng khoán. - Cơ sở dữ liệu đa phƣơng tiện: là dạng dữ liệu âm thanh, hình ảnh và phim ảnh, text & www,. Dạng dữ liệu này phổ biến trên Internet do sự ứng dụng rộng rãi của nó.
Quá trình khai phá dữ liệu: Quá trình khai phá dữ liệu sẽ tiến hành qua 6 giai đoạn nhƣ hình 1: Envalution of Rule Data Mining Transformat ion Cleansing Pre- Knowledge processing Preparation Pattern Selection Discovery Gatherin Transformed Data g Cleansed Preprocesse Target d Data Preparated Internet,. Data Hình 1: Quá trình khai phá dữ liệu 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức đƣợc chiết xuất ra. Về lý thuyết thì có vẽ rất đơn giản nhƣng thực sự đây là một quá trình rất khó khăn gặp phải rất nhiều vƣớng mắc nhƣ: quản lý các tập dữ liệu, phải lặp đi lặp lại các quá trình,. Gom dữ liệu (Gathering) 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. Trích lọc dữ liệu (Selection) Ở giai đoạn này dữ liệu đƣợc lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đó, ví dụ chọn tất cả những ngƣời có tuổi đời từ 25 – 35 và có trình độ đại học. Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu (Cleansing, Pre-processing and Preparation) Giai đoan thứ ba này là giai đoạn hay bị sao lãng, nhƣng thực tế nó là một bƣớc rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thƣờng mắc phải trong khi gom dữ liệu là tính không đủ chặt chẻ, logíc.
Vì vậy, dữ liệu thƣờng chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên. Những dữ liệu dạng này đƣợc xem nhƣ thông tin dƣ thừa, không có giá trị. Bởi vậy, đâ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ý - chuẩn bị trƣớc” thì sẽ gây nên những kết quả sai lệch nghiêm trọng.
Chuyển đổi dữ liệu (Transformation) 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ó. Dữ liệu đã đƣợc chuyển đổi phù hợp với mục đích khai thác. Phát hiện và trích mẫu dữ liệu (Pattern Extraction and Discovery) Đây là bƣớc mang tính tƣ duy trong 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.
Thuật toán thƣờng dùng là nguyên tắc phân loại, nguyên tắc kết hợp hoặc các mô hình dữ liệu tuần tự,. Đánh giá kết quả mẫu (Evaluation of Result) Đây là giai đoạn cuối trong quá trình khai phá dữ liệu. Ở giai đoạn này, các mẫu dữ liệu đƣợc chiết xuất ra bởi phần mềm khai phá dữ liệu. Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch.
Vì vậy, cần phải ƣu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức (Knowlege) cần chiết xuất ra. 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Trên đây là 6 giai đoạn trong quá trình khai phá dữ liệu, trong đó giai đoạn 5 là giai đoạn đƣợc quan tâm nhiều nhất hay còn gọi đó là khai phá dữ liệu. Các hƣớng tiếp cận cơ bản và kỹ thuật áp dụng: Khai phá dữ liệu có thể đƣợc phân chia theo các hƣớng tiếp cận chính sau: - Phân lớp và dữ đoán (classification and prediction): xếp một đối tƣợng vào một trong những lớp đã biết. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết.
Đối với hƣớng tiếp cận này thƣờng áp dụng một số kỹ thuật nhƣ học máy, cây quyết định, mạng noron nhân tạo. Hay lớp bài toán này còn đựoc gọi là học có giám sát. - Phân cụm (clustering/segmentation): Sắp xếp các đối tƣợng theo từng cụm nhƣng số lƣợng và tên các cụm chƣa biết trƣớc. Lớp bài toán phân cụm còn đựơc gọi là học không giám sát.
- Luật kết hợp(Association rules): là dạng biểu diễn tri thức ở dạng khá đơn giản. Ví dụ: “70% số vụ tai nạn xe máy do thanh niên điều khiển thì có tới 80% là do phóng nhanh vƣợt ẩu”. Hƣớng tiếp cận này đƣợc ứng dụng trong nhiều lĩnh vực nhƣ kinh doanh, y học, giáo dục. - Khai phá chuỗi theo thời gian: Cũng tƣơng tự nhƣ khai phá dữ liệu bằng 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 bởi chúng có tính dự đoán cao. - Mô tả khái niệm (concept description and summarization): Lớp bài toán này 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 5. Lĩnh vực ứng dụng: Phát hiên tri thức và khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực nhƣ: thống kê, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán học, tính toán song song và tốc độ cao, thu thập tri thức cho các hệ chuyên gia, quan sát dữ liệu,…Đặc biệt phát hiện tri thức và khai phá dữ liệu rát gần gũi với các lĩnh vực thống kê, sử dung các phƣơng pháp thống kê để mô hình dữ liệu và phát hiện các mẫu, luật,… Các ứng dụng của phát hiện tri thức và khai phá dữ liệu: Thông tin thƣơng mại.
Phân tích dữ liệu marketing, khách hàng. Phân tích đầu tƣ. Phê duyệt vay vốn. 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Phát hiện gian lận.
Thông tin kỹ thuật. Điều khiển và lập lịch trình,. Một số phƣơng pháp khai phá dữ liệu: 6. Phƣơng pháp suy diễn và quy nạp: Phƣơng pháp suy diễn: Rút ra thông tin là kết quả logic từ các thông tin nằm trong cơ sở dữ liệu dựa trên các quan hệ trong dữ liệu.
Phƣơng pháp suy diễn dựa trên các sự kiện chính để suy ra các tri thức mới từ các thông tin cũ. Phƣơng pháp này thƣờng sử dụng luật suy diễn để trích chọn các mẫu.