MỞ ĐẦU Trong những năm gần đây, công nghệ thông tin phát triển mạnh mẽ và đi sâu vào nhiều lĩnh vực trong cuộc sống. Công nghệ thông tin phát triển đi kèm với sự gia tăng không ngừng của cơ sở dữ liệu và nhu cầu sử dụng dữ liệu hiệu quả cũng trở nên ngày càng thiết yếu. Do đó, khai phá dữ liệu đã trở thành lĩnh vực phát triển mạnh với nhiều phƣơng pháp tiếp cận khác nhau. Thời gian đầu, phƣơng pháp tiếp cận quy nạp các luật dựa trên trên tập thô đƣợc sử dụng phổ biến với nhiều ứng dụng toàn diện để khai phá dữ liệu nhƣ dự báo tài chính, chuẩn đoán y tế.Các ứng dụng này đã chứng tỏ rằng rằng hƣớng tiếp cận này là rất hữu ích cho việc khai phá kiến thức bằng các luật quyết định từ cơ sở dữ liệu ban đầu.
Tuy nhiên, hƣớng nghiên cứu và các ứng dụng của khai phá tri thức chủ yếu tập trung trong các hệ thống thông tin tĩnh. Nghĩa là các đối tƣợng và các thuộc tính trong một hệ thống thông tin nhất định không đổi. Trong thực tế, các nguồn dữ liệu thực có đặc điểm động, phát triển lớn mạnh lên về cả thuộc tính và số lƣợng đối tƣợng với tốc độ nhanh chóng. Để duy trì hiệu quả kiến thức từ dữ liệu động, các nhà nghiên cứu đã đi theo hƣớng nghiên cứu tiếp cận gia tăng cho việc cập nhật tri thức.
Hiện nay, phƣơng pháp cận gia tăng dựa trên tập thô đã và đang đƣợc nhận rất nhiều quan tâm. Theo [6], dữ liệu động chủ yếu tập trung vào hai trƣờng hợp: (1) Tập các đối tƣợng trong hệ thống thông tin thay đổi theo thời gian trong khi các tập thuộc tính vẫn không đổi. (2) Tập các thuộc tính trong hệ thống thông tin thay đổi theo thời gian trong khi tập đối tƣợng vẫn không đổi. Do dữ liệu luôn thay đổi, các phân lớp dữ liệu cũng thay đổi theo.
Vì vậy, luận văn tập trung tìm hiểu và trình bày “ một số thuật toán khai phá luật quyết định trên sơ sở dữ liệu động” theo hƣớng tiếp cận gia tăng với kỹ thuật phân lớp dựa trên tập thô. Các luật quyết định có độ chính xác và độ phủ cao là những luật có thể cung cấp các tri thức quan trọng. Để khai phá các luật quyết định có ý nghĩa, ta cần đặt ra ngƣỡng của độ chính xác và độ phủ để khai phá đƣợc các tri thức quan tâm. Nội dung của luận văn tập trung vào hƣớng đã nêu trong trƣờng hợp (1) và (2).
Trong đó, luận văn gồm 3 chƣơng. Chƣơng 1: Trình các kiến thức cơ bản về khai phá dữ liệu và các khái niệm cơ bản trong tập thô nhƣ khái niệm tập hợp, tập thô, tập mờ, hệ thống thông tin, các mỗi quan hệ, bảng quyết định và luật quyết định. Chƣơng 2: Trình bày về thuật toán khai phá luật quyết định trên bảng dữ liệu khi có giá trị thuộc tính thay đổi (làm thô, làm mịn) theo hƣớng tiếp cận gia tăng ma trận độ hỗ trợ. Trong chƣơng này, luận văn tập trung trình bày các mối quan hệ của các lớp khi thuộc tính của dữ liệu khi đƣợc làm thô, làm mịn, thuật toán và đánh giá độ phức tap tính toán theo thời gian của thuật toán.
Chƣơng 3: Trình bày hai thuật toán khai phá luật quyết định trên bảng dữ liệu động khi có tập đối thƣợng thay đổi. Hai thuật toán này đều đƣợc xây dựng trên cùng một mô hình chỉ khác nhau về hƣớng tiếp cận. Thuật toán TIEU LUAN MOI download : skknchat@gmail.com 9 một là thuật toán khai phá luật quyết định theo hƣớng tiếp cận gia tăng ma trận độ chính xác và ma trận độ phủ. Thuật toán hai là thuật toán khai phá luật quyết định theo hƣớng tiếp cận gia tăng ma trận độ hỗ trợ.
Kết thúc là phần kết luận và đề xuất những vấn đề cần tiếp tục nghiên cứu. TIEU LUAN MOI download : skknchat@gmail.com 10 CHƢƠNG 1. CÁC KHÁI NIỆM CƠ BẢN 1. Khai phá dữ liệu là gì Khai phá dữ liệu đã thu hút rất nhiều sự chú ý trong ngành công nghệ thông tin và trong xã hội nói chung trong những năm gần đây.
Do sự sẵn và rộng của lƣợng lớn dữ liệu và sự cần thiết để chuyển đổi dữ liệu đó thành thông tin hữu ích. Nên khai thác dữ liệu ra đời và đƣợ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. Trình bày Khai phá tri thức Chuyển dữ liệu đổi dữ liệu Tiền xử lý Tri thức Lọc dữ liệu Dữ liệu đã Các mẫu Dữ liệu chuyển đổi Tích hợp tiền xử lý dữ liệu Hình 1.1: Quá trình khái phá tri thức trong cơ sở dữ liệu [3] Khai phá dữ liệu đƣợc liên tƣởng tới quá trình chiết lọc hoặc khai phá tri thức từ số lƣợng lớn dữ liệu. Khai phá dữ liệu là một bƣớc quan trọng của khám phá tri thức.
Khám phá tri thức là một quá trình bao gồm một chuỗi lặp đi lặp lại các bƣớc sau: 1. Lọc dữ liệu (loại bỏ tiếng ồn và dữ liệu không phù hợp) 2. Tích hợp dữ liệu (nơi nhiều nguồn dữ liệu có thể kết hợp đƣợc với nhau) 3. Lựa chọn dữ liệu (dữ liệu liên quan tới nhiệm vụ phân tích đƣợc lấy từ cơ sở dữ liệu) 4.
Chuyển đổi dữ liệu (dữ liệu đƣợc chuyển hoặc hợp nhất thành các hình thức thích hợp cho khai thác bằng cách thực hiện tóm tắt hoặc tập hợp) 5. Khai thác dữ liệu (một quá trình cần thiết mà các phƣơng pháp thông minh đƣợc áp dụng để trích xuất các mẫu dữ liệu) 6. Đánh giá các mẫu (để xác định các mẫu thực sự thú vị đại diện cho kiến thức dựa trên một số biện pháp) 7. Trình bày tri thức (nơi trực quan và kỹ thuật biểu diễn tri thức đƣợc sử dụng để trình bày các kiến thức khai thác cho ngƣời sử dụng) TIEU LUAN MOI download : skknchat@gmail.com 11 Một cách khái quát thì khai phá dữ liệu gồm 3 giai đoạn chính [9]: Giai đoạn tiền xử lý: Giai đoạn tiền xử lý đƣợc hiểu là các chức năng liên quan đến việc tiếp nhận, tổ chức và biến đổi dữ liệu.
Giai đoạn này có mục tiêu là chuẩn bị dữ liệu cho giai đoạn sau của việc khai thác dữ liệu. Giai đoạn này gồm các bƣớc từ 1 đến 4. Giai đoạn khai thác dữ liệu: Giai đoạn này đƣợc định nghĩa bởi việc sử dụng các thuật toán để trích rút các mẫu dữ liệu. Một số các kỹ thuật đƣợc sử dụng trong giai đoạn này nhƣ mạng neural, tập thô, thuật toán di truyền, mô hình thống kê và xác suất.
Giai đoạn hậu xử lý: Giai đoạn này chế biến dữ liệu thu đƣợc từ quá trình khai thác dữ liệu. Nó có khả năng xác nhận tính hữu ích của mẫu dữ liệu đƣợc khai phá. [4]Khai phá dữ liệu nhƣ là một thuật ngữ đƣợc sử cho các thiết lập cụ thể của sáu nhiệm vụ sau: Phân lớp dữ liệu, ƣớc lƣợng, dự báo, khai phá luật kết hợp, phân cụm, mô tả và trực quan. Trong đó ba nhiệm vụ đầu tiên – phân lớp dữ liệu, ƣớc lƣợng, dự báo là tất cả các ví dụ về hƣớng khai thác dữ liệu hoặc học có giám sát.
Trong hƣớng khai thác dữ liệu này, mục tiêu là sử dụng dữ liệu có sẵn để xây dựng một mô hình mô tả một hoặc nhiều thuộc tính cụ thể quan tâm (thuộc tính mục tiêu hoặc các thuộc tính lớp) trong giới hạn của phần còn lại của các thuộc tính có sẵn. Ba nhiệm vụ tiếp theo - luật kết hợp, phân nhóm và mô tả là các ví dụ về khai thác dữ liệu vô hƣớng tức (không có thuộc tính). Nó đƣợc chỉ ra nhƣ là mục tiêu. Mục tiêu là để thiết lập một số mối quan hệ giữa tất cả các thuộc tính.
Các nhiệm vụ trong khai phá dữ liệu đƣợc giới thiệu cụ thể dƣới đây: Phân lớp Phân lớp là nhiệm vụ khai thác dữ liệu phổ biến nhất của khai phá dữ liệu. Phân lớp bao gồm việc kiểm tra các đặc trƣng của một đối tƣợng mới và ánh xạ tới một lớp đã đƣợc định nghĩa trƣớc. Phân lớp đƣợc đặc trƣng bởi việc định nghĩa tốt các lớp và một tập huấn luyện bao gồm các ví dụ đã đƣợc phân lớp trƣớc đó. Nhiệm vụ phân lớp là xây dựng mô hình phân loại dữ liệu chƣa đƣợc phân lớp từ dữ liệu huấn luyện (các lớp dữ liệu đã biết trƣớc đó) và áp dụng các mô hình dữ liệu mới này để dự đoán cho các mục mới trong cùng một lĩnh vực.
Các kỹ thuật thƣờng dùng trong phân lớp: Cây quyết định, tập thô, mạng neuron, K - láng giềng, thuật toán di truyền, mạng Bayesian. Trong các kỹ thuật này thì kỹ thuật cây quyết định và tập thô đƣợc sử dụng nhiều nhất. Ƣớc lƣợng Dự đoán giao dịch với dữ liệu vào có thuộc tính là các giá trị liên tục. Đƣa ra một số dữ liệu đầu vào, chúng ta dùng dự đoán để đƣa ra giá trị của một số biến tiếp theo (của các giá trị đầu vào) mà chúng ta chƣa biết nhƣ thu nhập, chiều cao hoặc số dƣ của thẻ tín dụng.
Dự báo: TIEU LUAN MOI download : skknchat@gmail.com 12 Quá trình xây dựng mô hình dự đoán tƣơng tự nhƣ cho các mô hình phân lớp nhƣng điểm khác biệt của nó là sử dụng dữ liệu quá khứ để xây dựng mô hình đƣợc sử dụng để đƣa ra dự đoán về tƣơng lai. Khai phá luật kết hợp Phƣơng pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp tìm đƣợc. Ta có thể lấy một ví dụ đơn giản về luật kết hợp nhƣ sau: sự kết hợp giữa hai thành phần A và B có nghĩa là sự xuất hiện của A trong bản ghi kéo theo sự xuất hiện của B trong cùng bản ghi đó: A→B.
Phân cụm Phân cụm là một quá trình phân vùng hoặc phân nhóm một tập các đối tƣợng thành các nhóm. Trong đó, các đối tƣợng trong cùng một nhóm tƣơng tự nhƣ nhau và các đối tƣợng trong các nhóm khác nhau là không giống nhau. Phân cụm thƣờng đƣợc coi là phân lớp không giám sát. Nó thƣờng đƣợc dùng để phân nhóm các khách hàng.
Mô tả và trực quan Dữ liệu trực quan là một thế mạnh của khai thác dữ liệu mô tả. Nó thƣờng không dễ dàng cho các hình dung có ý nghĩa. Những hình ảnh đúng thực sự có thể đáng giá hàng nghìn luật kết hợp khi con ngƣời thực hiện các công việc trích xuất ý nghĩa từ những hình ảnh thực tế.