Khai phá dữ liệu ứng dụng luật kết hợp mờ

DANH MỤC CÁC TÊN VÀ CÁC THUẬT NGỮ VIẾT TẮT Tên Tên, thuật ngữ viết tắt Cơ sở dữ liệu CSDL Ngôn ngữ vấn đáp SQL Kho dữ liệu về dữ liệu Metadata Kho dữ liệu OLAP Knowledge Discovery in Database KDD Luật kết hợp Association Rules Fuzzy Logic Control FLC DANH SÁCH CÁC BẢNG Tên bảng Diễn giải Bảng 1 Ký hiệu sử dụng trong thuật toán Bảng 2 Ví dụ về dữ liệu giao dịch chứng khoán Bảng 3 Dữ liệu giao dịch chứng khoán chuyển sang dạng mờ DANH SÁCH CÁC HÌNH VẼ Tên hình Diễn giải Hình 1 Thông tin khách hàng vay Hình 2 Ví dụ về tập mờ Hình 3 Mô tơ suy diễn Hình 4 Hàm thuộc cho các tập mờ Già(Old) và Trẻ(Young) MỤC LỤC MỞ ĐẦU Ngày nay, cách mạng khoa học kỹ thuật diễn ra mọi lúc, mọi nơi, trên nhiều lĩnh vực của đời sống. Và Việt Nam cũng không nằm ngoài qui luật chung đó. Trong quá trình phát triển này, chúng ta đã thu thập được một khối lượng lớn dữ liệu. Và trong chính những cơ sở dữ liệu này tiềm ẩn rất nhiều tri thức có ích mà con người chưa khám phá. Ngoài ra, số lượng dữ liệu lớn được thu thập vượt quá khả năng phân tích của chúng ta mà không sử dụng những kỹ thuật phân tích tự động. Do vậy đã có một nhu cầu rất thiết thực là tìm kiếm được những tri thức trong những kho dữ liệu này. Xuất phát từ thực tế nói trên, và với mục đích tìm hiểu liên kết trong cơ sở dữ liệu, em đã quyết định lựa chọn đề tài “Khai Phá Dữ Liệu Sử Dụng Luật Kết Hợp Mờ” . Đề tài gồm 4 chương như sau: Chương I: Tổng quan về cơ sở dữ liệu Chương II. Khai phá dữ liệu Chương III. Luật kết hợp mờ trong khai phá dữ liệu Chương IV. Cài đặt. Trong quá trình thực hiện đồ án này, mặc dù đã rất cố gắng, song không thể tránh khỏi những sai sót, em rất mong nhận được sự chỉ bảo và giúp đỡ từ phía thầy giáo và các bạn. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU Tổ chức và khai thác cơ sở dữ liệu truyền thống: Việc dùng các phương tiện tin học để tổ chức và khai thác các cơ sở dữ liệu (CSDL) đã được phát triển từ những năm 60. Từ đó cho đến nay, rất nhiều CSDL đã được tổ chức, phát triển và khai thác ở mọi quy mô và ở khắp các lĩnh vực hoạt động của con người và xã hội. Theo như đánh giá cho thấy, lượng thông tin trên thế giới cứ sau 20 tháng lại tăng gấp đôi. Kích thước và số lượng cơ sở dữ liệu thậm chí còn thăng nhanh hơn. Năm 1989, tổng số cơ sở dữ liệu trên thế giới vào khoảng 5 triệu, hầu hết đều là các cơ sở dữ liệu cỡ nhỏ được phát triển trên DBaseIII. Với sợ phát triển mạnh mẽ của công nghệ điện tử tạo ra các bộ nhớ có dung lượng lớn, bộ xử lý tốc độ cao cùng với các hệ thống mạng viễn thông, người ta đã xây dựng các hệ thống thông tin nhằm tự động hoá mọi hoạt động kinh doanh của mình. Điều này đã tạo ra một dòng dữ liệu tăng lên không ngừng vì ngay từ các giao dịch đơn giản nhất như một cuộc gọi điện thoại, kiểm tra sức khoẻ, sử dụng thẻ tín dụng… đều được ghi vào trong máy tính. Cho đến nay, con số này đã trở nên khổng lồ bao gồm các cơ sở dữ liệu cực lớn cỡ gigabytes và thậm chí terabytes lưu trữ các dữ liệu kinh doanh ví dụ như dữ liệu thông tin khách hàng, dữ liệu sử dụng các giao dịch, dữ liệu bán hàng, dữ liệu các tài khoản, cáckhoản vay, sử dụng vốn… Nhiều hệ quản trị CSDL mạnh với các công cụ phong phú và thuận tiện đã giúp cho con người khai thác có hiệu quả các nguồn tài nguyên dữ liệu. Mô hình CSDL quan hệ và ngôn ngữ vấn đáp chuẩn (SQL) đã có vai trò hết sức quan trọng trong việc tổ chức và khai thác các CSDL đó. Cho đến nay, không một tổ chức kinh tế tổ chức là không sử dụng các hệ quản trị CSDL và các hệ công cụ báo cáo, ngôn ngữ hỏi đáp nhằm khai thác các CSDL phục vụ cho hoạt động tác nghiệp của mình. Bước phát triển mới của việc tổ chức và khai thác các CSDL. Cùng với việc tăng không ngừng khối lượng dữ liệu, các hệ thống thông tin cũng được chuyên môn hoá, phân chia theo các lĩnh vực ứng dụng như sản xuất, tài chính, buôn bán thị trường… Như vậy, bên cạnh chức năng khai thác dữ liệu có tính chất tác nghiệp, sự thành công trong kinh doanh không còn là năng suất của các hệ thống thông tin nữa mà là tính linh hoạt và sẵn sàng đáp lại những yêu cầu trong thực tế, CSDL cần đem lại những “tri thức” hơn là chính những dữ liệu đó. Các quyết định cần phải có càng nhanh càng tốt và phải chính xác dựa trên những dữ liệu sẵn có trong khi khối lượng dữ liệu cứ sau 20 tháng lại tăng gấp đôi làm ảnh hưởng đến thời gian ra quyết định cũng như khả năng hiểu hết được nội dung dữ liệu. Lúc này, các mô hình CSDL truyền thông và ngôn ngữ SQL đã cho thấy không có khả năng thực hiện được công việc này. Để lấy được những thông tin có tính “trí thức” trong khối dữ liệu khổng lồ này, người ta đã đi tìm những kỹ thuật có khả năng hợp nhất các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển đổi thành một tập hợp các cơ sở dữ liệu ổn định, có chất lượng được sử dụng chỉ riêng cho một vài mục đích nào đó. Các kỹ thuật đó được gọi chung là kỹ thuật tạo kho dữ liệu (data warehousing) và môi trường các dữ liệu có được gọi là các kho dữ liệu (data warehouse). Kho dữ liệu là một môi trường có cấu trúc các hệ thống thông tin, cung cấp cho người dùng các thông tin khó có thể truy nhập hoặc biểu diễn trong các CSDL tác truyền thống, nhằm mục dích hỗ trợ việc ra quyết dịnh mang tính lịch sử hoặc hiện đại. Theo W.H. Inmon, có thể định nghĩa kho dữ liệu như sau: “Một kho dữ liệu là một tập hợp dữ liệu tích hợp hướng chủ đề có tính ổn định, thay đổi theo thời gian nhằm hỗ trợ cho việc ra quyết định. Nói cách khác, một kho dữ liệu bao gồm: - Một hoặc nhiều công cụ để chiết xuất dữ liệu từ bất kỳ dạng cấu trúc dữ liệu nào. - Cơ sở dữ liệu tích hợp hướng chủ đề ổn định được tổng hợp từ các dữ liệu bằng cách lập các bản dữ liệu của dữ liệu.” Một kho dữ liệu có thể được coi là một hệ thống thông tin với những thuộc tính sau: - Là một CSDL được thiết kế có nhiệm vụ phân tích, sử dụng các dữ liệu từ các ứng dụng khác nhau. - Hỗ trợ cho một số người dùng có liên quan với các thông tin liên quan. - Là dữ liệu chỉ đọc. - Nội dung của nó được cập nhật thường xuyên theo cách thêm thông tin. - Chứa các bảng dữ liệu có kích thước lớn. - Một câu hỏi thường trả về một tập kết quả liên quan đến toàn bộ bảng và các liên kết nhiều bảng. Cấu trúc kho dữ liệu được xây dựng dựa trên hệ quản trị CSDL quan hệ, có chức năng giống như một kho lưu trữ thông tin qua trung tâm. Trong đó, dữ liệu tác nghiệp và phần xử lý được tách riêng khỏi quá trình xử lý kho dữ liệu. Kho lưu trữ trung tâm được bao quanh bởi các thành phần được thiết kế để làm cho kho dữ liệu có thể hoạt động, quản lý và truy nhập được từ người dùng đầu cuối cũng như từ các nguồn dữ liệu. Kho dữ liệu bao gồm 7 thành phần: - Dữ liệu nguồn (là các ứng dụng tác nghiệp hoặc các kho dữ liệu tác nghiệp) và các công cụ chiết xuất, làm sạch và chuyển đổi dữ liệu. - Kho dữ liệu về dữ liệu (Metadata). - Các kỹ thuật xây kho. - Kho dữ liệu thông minh hay dữ liệu theo chủ đề (Data marts): là nơi các dữ liệu được khoanh vùng theo chủ đề tới một giới hạn nào đó và có thể được thay đổi cho phù hợp với nhu cầu của từng bộ phận người dùng. Với các kho dữ liệu này, cũng có thể xây dựng một kho dữ liệu theo cách tiếp cận từng giai đoạn kế tiếp nghĩa là với một tập hợp các kho dữ liệu thông minh, ta tạo ra một kho dữ liệu; ngược lại, một kho dữ liệu có thể được phân tích thành nhiều kho dữ liệu thông minh. - Các công cụ vấn đáp (query), báo cáo (reporting), phân tích trực tiếp (OLAP) và khai phá dữ liệu (data mining). Đây chính là các cách khai thác kho dữ liệu để đem lại những “tri thức” hơn là đem lại chính những dữ liệu thô. Điểm mạnh và điểm yếu của các kỹ thuật này ta sẽ phân tích kỹ hơn ở các phần sau. - Quản trị kho dữ liệu. - Hệ thống phân phối thông tin. Nhưng chỉ có kho dữ liệu thôi chưa đủ để có các tri thức. Như đã đề cập ở trên, các kho dữ liệu được sử dụng theo ba cách chính: - Theo cách khai thác truyền thống, kho dữ liệu được sử dụng để khai thác các thông tin bằng các công cụ vấn đáp và báo cáo. Tuy nhiên, nhờ có việc chiến xuất, tổng hợp và chuyển đổi từ các dữ liệu thô sang dạng các dữ liệu chất lượng cao và có tính ổn định, kho dữ liệu đã giúp cho việc nâng cao các kỹ thuật biểu diễn thông tin truyền thống (hỏi đáp và báo cáo). Bằng cách tạo ra một tầng ẩn giữa người dùng và CSDL, các dữ liệu đầu vào của các kỹ thuật này được đặt vào một nguồn duy nhất. Việc hợp nhất này loại bỏ được rất nhiều lỗi sinh ra do việc phải thu thập và biểu dương thông tin từ rất nhiều nguồn khác nhau cũng như phải thu thập và biểu dương thông tin từ rấ nhiều nguồn khác nhau cũng như giảm bớt được sự chậm trễ do phải lấy rất nhiều nguồn khác nhau cũng như giảm bớt được sự chậm trễ do phải lấy các dữ liệu bị phân đoạn trong các CSDL khác nhau, tránh cho người dùng khỏi những câu lệnh SQL phức tạp. Tuy nhiên, đây mới chỉ là cách khai thác với kỹ thuật cao để đưa ra các dữ liệu tinh và chính xác hơn chứ chưa đưa ra được dữ liệu “tri thức”. - Thứ 2 là các kho dữ liệu được sử dụng để hỗ trợ cho phân tích trực tuyến (OLAP). Trong khi ngôn ngữ vấn đáp chuẩn SQL và các công cụ làm báo cáo truyền thống chỉ có thể miêu tả những gì có trong CSDL thì phân tích trực tuyến có khả năng phân tích dữ liệu, xác định xem giả thuyết đúng hay sai. Tuy nhiên, phân tích trực tuyến lại không có khả năng đưa ra được các giả thuyết. Hơn nữa, kích thước quá lớn và tính chất phức tạp của kho dữ liệu làm cho nó rất khó có thể được sử dụng cho những mục đích như đưa ra các giả thuyết từ các thông tin mà chương trình ứng dụng cung cấp (ví dụ như khó có thể đưa ra được giả thuyết giải thích được hành vi của một nhóm khách hàng). Trước đây, kỹ thuật học máy thường được sử dụng để tìm ra những giả thuyết từ các thông tin dữ liệu thu thập được. Tuy nhiên, thực nghiệm cho thấy chúng thể hiện khả năng rất kém khi áp dụng với các tập dữ liệu lớn trong kho dữ liệu này. Phương pháp thống kê tuy ra đời đã lâu nhưng không có gì cải tiến để phù hợp với sự phát triển của dữ liệu. Đây chính là lý do tại sao một khối lượng lớn dữ liệu vẫn chưa được khai thác và thậm trí được lưu chủ yếu trong các kho dữ liệu không trực tuyến (off-line). Điều này đã tạo nên một lỗ hổng lớn trong việc hỗ trợ phân tích và tìm hiểu dữ liệu, tạo ra khoảng cách giữa việc tạo ra dữ liệu và việc khai thác các dữ liệu đó. Trong khi đó, càng ngày người ta càng nhận thấy rằng nếu được phân tích thông minh thì dữ liệu sẽ là một nguồn tài nguyên quý giá trong cạnh tranh trên thương trường. Giới tin học đã đáp lại những thách thức trong thực tiễn cũng như trong nghiên cứu khoa học bằng cách đã đưa một phương pháp mới đáp ứng cả nhu cầu trong khoa học cũng như trong hoạt động thực tiễn, đó chính là công nghệ Khai phá dữ liệu (data mining). Đây chính là ứng dụng chính thứ ba của kho dữ liệu. Khai phá dữ liệu và quá trình phát hiện tri thức. Yếu tố thành công trong mọi hoạt động kinh doanh ngày nay là việc biết sử dụng thông tin một cách có hiệu quả. Điều đó có nghĩa là từ các dữ liệu sẵn có, phải tìm ra những thông tin tiềm ẩn có giá trị mà trước đó chưa được phát hiện, tìm ra những xu hướng phát triển và những yếu tố tác động lên chúng. Thực hiện công việc đó chính là thực hiện quá trình phát triển tri thức trong CSDL (Knowledge Discovery in Database - KDD) mà trong đó kỹ thuật cho phép ta lấy được các tri thức chính là kỹ thuật khai phá dữ liệu (data mining). Như John Naisbett đã nói: “Chúng ta đang chìm ngập trong dữ liệu mà vẫn đói tri thức”. Dữ liệu thường được cho bởi các giá trị mô tả các sự kiện, hiện tượng cụ thể. Còn tri thức (knowledge) là gì ? Có thể có những định nghĩa rõ ràng để phân biệt các khái niệm dữ liệu, thông tin và tri thức hay không ? Khó mà định nghĩa chính xác nhưng phân biệt chúng trong những ngữ cảnh nhất định là rất cần thiết và có thể làm được. Thông tin là một khái niệm rất rộng, khó có thể đưa ra một định nghĩa chính xác cho khái niệm này. Cũng không thể định nghĩa cho khái niệm tri thức cho dù chỉ hạn chế trong phạm vi những tri thức cho dù chỉ hạn chế trong phạm vi những tri thức được chiết xuất từ các CSDL. Tuy nhiên, ta có thể hiểu tri thức là một biểu thức trong một ngôn ngữ nào đó diễn tả một (hoặc nhiều) mối quan hệ giữa các thuộc tính trong các dữ liệu đó. Các ngôn ngữ thường được dùng để biểu diễn tri thức (trong việc phát hiện tri thức từ các CSDL) là các khung (frames), các cây và đồ thị, các luật (rules), các công thức trong ngôn ngữ logic mệnh đề hoặc tân từ cấp một, các hệ thống phương trình, … ví dụ như ta có các luật miêu tả các thuộc tính của dữ liệu, các mẫu thường xuyên xảy ra, các nhóm đối tượng trong CSDL… Phát hiện tri thức từ CSDL là một quá trình có sử dụng nhiều phương pháp và công cụ tin học nhưng vẫn là một quá trình mà trong đó con người là trung tâm. Do đó, nó không phải là một hệ thống phân tích tự động mà còn là một hệ thống bao gồm nhiều hoạt động tương tác thường xuyên giữa con người và CSDL, tất nhiên là với sự hỗ trợ của các công cụ tin học. Người sử dụng hệ thống ở đây phải là những người có kiến thức cơ bản về lĩnh vực cần phát hiện tri thức để có thể chọn được đúng các tập con dữ liệu, các lớp mẫu phù hợp và đạt tiêu chuẩn quân tâm so với mục đích. Tri thức mà ta nói ở đây là tri thức rút ra từ các CSDL, thường để phục vụ cho việc giải quyết một loạt nhiệm vụ nhất định trong một lĩnh vực nhất định. Do đó, quá trình phát hiện tri thức cũng mang tính chất hướng nhiệm vụ, không phải là phát hiện mọi tri thức bất kỳ mà là phát hiện tri thức nhằm giải quyết tốt nhiệm vụ đề ra. Vì vậy, quá trình phát hiện tri thức là một quá trình hoạt động tương tác giữa con người (người sử dụng hoặc chuyên gia phân tích) với các công cụ tin học để thực hiện các bước cơ bản sau: - Tìm một cách hiểu (bằng ngôn ngữ tin học) lĩnh vực ứng dụng và nhiệm vụ đặt ra, xác định các tri thức đã có và các mục tiêu của người sử dụng. - Tạo một tập dữ liệu đích bằng cách chọn từ CSDL một tập dữ liệu với các giá trị biến và các mẫu được quan tâm, trên đó ta thực hiện quá trình phát hiện tri thức. - Làm sạch và tiền xử lý dữ liệu. - Thu gọn và rút bớt số chiều của dữ liệu để tập trung vào những thuộc tính chủ chốt đối với việc phát hiện tri thức. - Chọn nhiệm vụ khai phá dữ liệu dựa vào mục tiêu của quá trình phát hiện tri thức: xếp loại, phân nhóm hay hồi quy… - Chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá dữ liệu để tìm được các mẫu hình (pattern) có ý nghĩa dưới dạng biểu diễn tương ứng (luật xếp loại; cây quyết định, luật sản xuất, biểu thức quy hồi…). - Đánh giá, giải thích, thử lại các mẫu hình đã được khai phá, có thể lặp lại một hoặc nhiều bước kể trên. - Củng cố, tinh chế các tri thức đã được phát hiện. Kết hợp các tri thức thành hệ thống. Giải quyết các xung đột tiềm tàng trong tri thức khai thác được. Sau đó, tri thức được chuẩn bị sẵn sàng cho ứng dụng. Lý luận và thực tiễn thực hiện các quá trình pháthiện tri thức mà ta xét ở đây là sự tiếp thu, sử dụng và phát triển nhiều thành tựu và công cụ của các lĩnh vực đã phát triển trước đó như: lý thuyết nhận dạng, hệ chuyên gia, trí tuệ nhân tạo,… Nhưng đặc điểm cơ bản của lý luận về phát hiện tri thức ở đây là phát hiện tri thức trực tiếp từ dữ liệu, do đặc điểm đó mà nó với những điểm mới, phân biệt với các ngành đã có từ trước. Thí dụ như với các hệ chuyên gia thì cơ sở tri thức được hình thành từ kinh nghiệm và các kiến thức của các chuyên gia là chủ yếu, với nhiều bài toán nhận dạng thì thường tập các dạng mẫu là cho trước… còn đối với lý thuyết phát hiện tri thức thì các tri thức, các dạng mẫu, các giả thuyết đều được phát hiện từ việc khai phá các kho dữ liệu. Nếu phát hiện tri thức là toàn bộ quá trình trừu xuất tri thức từ các CSDL thì khai phá dữ liệu là giai đoạn chủ yếu của quá trình đó. Như trên đã trình bày, trong quá trình phát hiện tri thức, khâu khai phá dữ liệu được thực hiện sau các khâu tinh lọc và tiền xử lý dữ liệu, tức là việc khai phá để tìm ra các mẫu hình có ý nghĩa được tiến hành trên tập dữ liệu có hy vọng là sẽ thích hợp với nhiệm vụ khai phá đó chứ không phải là khai phá hết dữ liệu với một thời gian đủ dài để lấy được một mẫu không thực sự có ích như khái niệm trong thống kê trước đây. Vì vậy, khai phá dữ liệu thường bao gồm việc thử tìm mô hình phù hợp với tập dữ liệu và tìm kiếm các mẫu từ tập dữ liệu theo mô hình đó. Thí dụ ta có mô hình là một luật kết hợp thì mẫu là các yếu tố tham gia cùng với các độ hỗ trợ (support) và độ tin cậy (confidence) trong các luật tương ứng. Mặc dù các mẫu có thể được trích lọc từ bất kỳ CSDL nào nhưng chỉ có những mẫu được xem là đáng quan tâm xét theo một phương diện nào đó mới được coi là tri thức. Các mẫu là đáng quan tâm nếu chúng là mới, có lợi, đáng được xem xét. Một mẫu được xem là mới phụ thuộc vào khung tham chiếu cho trước, có thể đó là phạm vi tri thức của hệ thống hoặc phạm vi tri thức của người dùng. Ví dụ như việc khai phá dữ liệu có thể tìm ra như sau: Nếu Gây_tai_nạn thì Tuổi>16. Đối với hệ thống, tri thức này có thể trước kia chưa biết và rất có ích nhưng đối với một người sử dụng đang thử phân tích các bản ghi về các yêu cầu bảo hiểm thì mẫu này lại không cần thiết và không đáng quan tâm vì không thể hiện được tri thức cần tìm. Ví dụ này cũng cho thấy khái niệm về tính hữu dụng. Tri thức là có ích khi nó có thể giúp đạt được mục đích của hệ thống hay của người sử dụng. Các mẫu hoàn toàn không liên quan đến các mục đích hiện tại ít được sử dụng và không tạo thành tri thức trong tình huống đã cho. Ví dụ như một mẫu miêu tả mối quan hệ Gây_tai_nạn với tuổi của lái xe được tìm ra trong khi mục đích của người sử dụng là phân tích các thông số bán hàng sẽ không có ích đối với người sử dụng. Tuy nhiên, độ hữu dụng và mới chưa đủ để đánh giá mẫu là tri thức cần tìm. Hầu hết các CSDL đều chứa rất nhiều các mẫu mới và có ích, tuy nhiên mẫu có giá trị với mục tiêu đặt ra phải là những mẫu không tầm thường. Để các mẫu trở nên không tầm thường, hệ thống phải làm nhiều hơn là chỉ mò mẫm thống kê vì kết quả của việc tính toán trực tiếp qua công tác thống kê đã có đối với người dùng. Một hệ thống tìm kiếm cần phải có khả năng quyết định cần thực hiện tính toán nào và kết quả có đáng quan tâm để tạo nên tri thức trong ngữ cảnh hiện tại hay không. Ta có thể coi khai phá dữ liệu giống như một quá trình phát hiện các mẫu mới đáp ứng được các yêu cầu trên, các tương quan mới có ý nghĩa, các xu hướng khai thác trong các khối dữ liệu của kho dữ liệu, sử dụng các kỹ thuật và các khái niệm của các lĩnh vực đã được nghiên cứu từ trước như: học máy, nhận dạng, thống kê, hồi quy, xếp loại, phân nhóm, các mô hình đồ thị, các mạng Bayes… Khai phá dữ liệu được sử dụng để tạo ra giả thuyết. Ví dụ như để xác định các yếu tố rủi ro khi cho vay tín dụng, kỹ thuật khai phá dữ liệu phải phát hiện được những người có thu nhập thấp và nợ nhiều là những người sẽ có mức rủ ro cao, ngoài ra kỹ thuật cũng có thể phát hiện ra những quy luật mà nhà phân tích có thể chưa tìm ra ví dụ như tỷ lệ giữa thu nhập trên nợ và tuổi cũng là các yếu tố xác định mức rủ ro. Để làm được điều này, khai phá dữ liệu sử dụng các thông tin trong quá khứ để học. Nó sẽ tìm kiếm các thông tin này trong các CSDL và sử dụng chúng để tìm ra các mẫu đáng quan tâm. Nếu xét về mặt ý tưởng và mục đích ứng dụng, khai phá dữ liệu là một nhu cầu tất yếu, một sự nhạy cảm đáp lại sự mong mỏi của giới kinh doanh thì về mặt kỹ thuật, đó thực sự là một khó khăn và là sự thách thức đối với những nhà khoa học. Khai phá dữ liệu được xây dựng dựa trên việc sử dụng các giải thuật mới, được định hướng theo nhu cầu kinh doanh để có thể giải quyết tự động các bài toán kinh doanh bằng các kỹ thuật dễ dùng và có thể hiểu được. Các kỹ thuật đang được nghiên cứu và sử dụng hiện nay bao gồm cây quyết định (CART, CHAID, AID), mạng neuron, phương pháp láng giềng gần nhất, các luật suy diễn… Khai phá dữ liệu không thuộc một ngành công nghiệp nào. Nó sử dụng các kỹ thuật thông minh để khai phá các tri thức tiềm ẩn trong dữ liệu. Có thể coi khai phá dữ liệu ngày nay đang ở trạng thái giống như việc quản trị dữ liệu vào những năm 60, khi mà các ứng dụng quản trị dữ liệu đều không tuân theo một nguyên tắc chung nào cho đến khi mô hình dữ liệu quan hệ ra đời cùng với sức mạnh của ngôn ngữ vấn đáp đã thúc đẩy việc phát triển các ứng dụng quản trị dữ liệu lên nhanh chóng. Tuy vậy, hiện nay trên thế giới đã có rất nhiều ngành công nghiệp sử dụng kỹ thuật khai phá dữ liệu để phục vụ cho hoạt động kinh doanh của mình và đã bước đầu thành công như ngành tài chính, y học, hoá học, bảo hiểm, sản xuất, giao thông, hàng không… Các kết quả đạt được cho thấy mặc dù kỹ thuật khai phá dữ liệu hiện nay vẫn còn nhiều vấn đề nổi cộm, nhưng với những tri thức mà chuyên gia con người cũng chưa cung cấp được thì khai phá dữ liệu có một tiềm năng to lớn trong việc tạo ra những lợi nhuận đáng kể trong nền kinh tế. I.4 Giới thiệu cơ sở thực tập I.4.1. Thành lập Năm 1993, một nhóm các nhà nghiên cứu, các chuyên gia CNTT đang làm việc tại các viện nghiên cứu, các trường Đại học, là những người có tâm huyết và say mê kỹ thuật, tập hợp lại với mục đích hợp tác, hỗ trợ nhau trong công tác nghiên cứu Khoa học - Kỹ thuật. Trong quá trình hoạt động, nhóm phát triển lên với con số 20 thành viên cơ hữu và hàng chục cộng tác viên là các chuyên gia có trình độ Đại học và trên Đại học tại các Doanh nghiệp hoạt động trong lĩnh vực CNTT, giàu năng lực và nhiệt tình. Các thành viên trong nhóm đã tham gia và hỗ trợ nhiều đề tài, công trình nghiên cứu Khoa học có giá trị, có nhiều sản phẩm đã được xã hội chấp nhận đưa vào ứng dụng, đạt được những uy tín nhất định trong lĩnh vực xây dựng và triển khai các hệ thống tích hợp công nghệ cao. Do nhu cầu của xã hội, đồng thời để đảm bảo quyền lợi cho các đơn vị sö dụng sản phẩm là kết quả các công trình nghiên cứu, tháng 10 năm 2002, Công ty ISYS được thành lập, hoàn toàn dựa trên cơ sở đội ngũ và cơ sở vật chất của nhóm nghiên cứu ban đầu. Một số thông tin về Công ty Tên Công ty: Công ty TNHH HỆ THỐNG TÍCH HỢP Tên giao dịch: ISYS Co.LTD Giám đốc: Lê Thành Trụ sở: 101B phố Pháo Đài Láng, Hà Nội Điện thoại: 04. 77 52 946 Fax: Số nhân viên: 20 I.4.2 Lĩnh vực hoạt động chính Sản xuất phần mềm tích hợp, phần mềm quản lý, hệ thống thông minh kết hợp công nghệ xử lý ảnh, video, tiếng nói trên các môi trường thiết bị hiện đại. Sản xuất phần cứng và phần mềm điều khiển theo đơn đặt hàng. Cung cấp các giải pháp, thiết bị CNTT, Tư vấn xây dựng mạng. Tư vấn các giải pháp an toàn hệ thống (Nguồn ổn định, chống sét …). Đào tạo và chuyển giao Công nghệ cao về phần mềm và phần cứng. Từ năm 1993, các cán bộ của Công ty đã tham gia vào nhiều dự án khác nhau về C«ng nghÖ th«ng tin, là những người chịu trách nhiệm chính hoặc trực tiếp điều hành các dự án cho các đơn vị nơi họ đang làm việc hoặc những đơn vị là đối tác hợp tác nghiên cứu. Kinh nghiệm và sản phẩm của Công ty trong các lĩnh vực gồm có: I.4.3 A. Cơ sở dữ liệu Năm 1994 - 1996: Xây dựng phần mềm quản lý và in thẻ bảo hiểm trên Foxpro for Windows cho các bảo hiểm y tế (BHYT) các tỉnh/thành phố (CSDL cho từng đơn vị lên tới 300.000 thẻ BH). 1994 - 1996: Phần mềm quản lý quán Bar. 2001: Hệ phần mềm Quản sinh - Tuyển sinh – Thi trắc nghiệm và giải pháp quản lý học sinh bằng thẻ từ (áp dụng thử nghiệm từ năm học 2002 – 2003 tại trường Công nghệ Hà nội – FSC). 2002: Phần mềm Quản lý bán hàng. I.4.4 B. Môi trường - Mạng – Internet 1998: Hệ môi trường soạn giảng qua mạng (E.T.T) - Sản phẩm được lựa chọn tham dự triển lãm Khoa học Công nghệ ASEAN lần thứ 5 (Tháng 10 / 1998 ). 2001 - 2002: Xây dựng các ứng dụng Web dựa trên nền tảng của Oracle, SQL Server, Java được ứng dụng tại: Nhà xuất bản Kim đồng. Công ty ONE: Giải pháp thương mại điện tử ( bán hàng qua mạng ). Trường Công nghệ Hà nội – FSC: Hệ thống soạn dạy trực tuyến ( đang triển khai thử nghiệm ). I.4.5 C. Phần mềm tiện ích và hệ thống thông minh 1994-1995: Chương trình thường trú truyền và nhận số liệu trên điện thoại bằng MODEM. 1996-1997: Chương trình đồ hoạ Monitor trên Visual C++ for Windows dùng cho mô phỏng phòng lái tập bay cho Viện nghiên cứu phòng không. 1998-1999: Tham gia chương trình vector hoá bản đồ tự động theo đơn đặt hàng của UNDP trên Visual C++ for Windows. 2002-2003: Ch­¬ng tr×nh qu¶n lý häc sinh qua m¹ng. Phát triển hệ thống sổ liên lạc điện tử qua mạng viễn thông, đã triển khai tại: + Tr­êng PTDL L­¬ng ThÕ Vinh - Hà nội. + Tr­êng Cao ®¼ng C«ng nghiÖp Hµ néi. + Trường THPT Chu Văn An. + Trường Hà Nội AMSTERDAM. 2002-2003: Xây dựng phần mềm Trang thông tin điện tử nội bộ cho UBND Quận Đống Đa. 2005-2007: Xây dựng phần mềm phòng khám nha khoa có tích hợp thẻ chip thông minh. 2007- nay: Xây dựng hệ thống Quản lý sau giao dịch chứng khoán BackOffice có kết nối với hệ thống ngân hàng trong nước. I.4.6 D. Hệ thống tích hợp phần cứng / phần mềm 2000 - 2001: Nghiên cứu và triển khai thành công các bảng thông báo điện tử (bảng LED) tích hợp phần cứng, phần mềm dựa trên Công nghệ ASIC, PC104, xử lý ảnh và Video với môi trường lập trình Visual C++ for Windows theo dự án của Bộ Khoa học Công nghệ và Môi trường. Sản phẩm đã được sử dụng tại các địa điểm: Ga Hà nội (phục vụ thông báo bán vé tự động), Đại häc S­ phạm Quy Nhơn, Đại học Sư phạm Vinh. 2002: Bảng thông báo tự động phục vụ cho trò chơi “ Chiếc kỳ diệu ” của VTV3. 2002: Bộ báo điểm phục vụ cho các trò chơi văn hoá của Đài Phát Thanh và Truyền Hình Thanh Hoá. Hiện nay, ISYS đã thành công với các bảng LED có kích thước lên tới hàng trăm inchs/256 màu ở cả hai chế độ v¨n b¶n (text) và đồ hoạ (graphic), kết nối với m¸y tÝnh qua mạng hoặc qua chuẩn RS-422. I.4.7 E. Đào tạo - Phổ biến tri thức Công nghệ 1. Viết sách: Lập trình và thuật toán Visual C++ for Windows (1000 trang, 2 cuốn - Xuất bản theo hợp ®ồng với Công ty ELICOM ). 2. Đào tạo chuyển giao Công nghệ: Công nghệ lập trình tích hợp hệ thống trên môi trường Visual C++ for Windows. Công nghệ lập trình mạng trên môi trường Web với SQL Server, Visual InterDev, ASP, Java. C¬ sö d÷ liÖu lín với Oracle. Công nghệ vi điện tử, lập trình chíp, lập trình tích hợp thiết bị vào hệ thống. Đào tạo quản trị mạng cao cấp theo giáo trình chuẩn của CISCO. 3. Đào tạo cho mục đích học vấn: Bên cạnh đào tạo chuyển giao Công nghệ, ISYS ®· vµ ®ang tiÕn hµnh c¸c kho¸ ®µo t¹o vÒ nh÷ng chuyªn ®Ò cã tÝnh häc thuËt cao vÒ c¸c khÝa c¹nh hiÖn ®¹i cña Tin häc, ch¼ng h¹n: Xö lý ¶nh, tiÕng nãi ... HÖ chuyªn gia vµ c¸c hç trî quyÕt ®Þnh. TÝnh to¸n mÒm (m¹ng n¬ ron, logic mê ...) cho c¸c hÖ thèng th«ng minh. C¸c thuËt to¸n b¶o mËt. KHAI PHÁ DỮ LIỆU Hiện nay trên sách báo, trong các cuộc hội thảo, tiếp thị sản phẩm ứng dụng công nghệ thông tin, người ta nói rất nhiều về khai phá dữ liệu hay có người còn gọi là đào mỏ dữ liệu (data mining). Và chắc chắn trong chúng ta không ai là không từng một lần được nghe thấy từ này. Vậy khai phá dữ liệu là gì ? Và tại sao lại có nhiều người nói đến vấn đề này trong cả công nghiệp máy tính lẫn trong hoạt động kinh doanh đến như vậy ? Khai phá dữ liệu là gì ? Khái niệm: 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ỷ 80. 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, khai phá dữ liệu 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 có tính chính quy (regularities) trong tập dữ liệu. Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện tri thức trong CSDL (Knowledge Discovery in Database-KDD) để chì toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn. Trong đó, khai phá dữ liệu là một bước đặc biệt trong toàn bộ quá trình, sử dụng các giải thuật đặc biệt để chiết suất ra các mẫu (pattern) (hay các mô hình) từ dữ liệu. Các bước của quá trình khai phá dữ liệu: Các giải thuật khai phá dữ liệu thường miêu tả từ những chương trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và thống kê trước đây, thường thì bước đầu tiên là các giải thuật nạp toàn bộ tệp dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được. Không chỉ bởi vì nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn vì khó có thể chiết xuất dữ liệu ra các tệp đơn giản để phân tích được. Quá trình xử lý khai phá dữ liệu bắt đầu bằng cách xác định chính xác vấn đề cần giải quyết. Sau đó sẽ xác định các dữ liệu liên quan dùng để xây dựng giải pháp. Bước tiếp theo là thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải thuật khai phá dữ liệu có thể hiểu được. Về lý thuyết thì có vẻ rất đơn giản nhưng khi thực hiện thì đây thực sự là một quá trình rất khó khăn, gặp phải rất nhiều vướng mắc như: các dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp), quản lý tập các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi)… Sẽ là quá cồng kềnh với một giải thuật khai phá dữ liệu nếu phải truy nhập vào toàn bộ nội dung của CSDL và làm những việc như trên. Vả lại, điều này cũng không cần thiết. Có rất nhiều các giải thuật khai phá dữ liệu thực hiện dựa trên những thống kê tóm tắt khá đơn giản của CSDL, khi mà toàn bộ thông tin trong CSDL là quá dư thừa đối với mục đích của việc khai phá dữ liệu. Bước tiếp theo là chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá dữ liệu để tìm được các mẫu (pattern) có ý nghĩa dưới dạng biểu diễn tương ứng với các ý nghĩa đó (thường được biểu diễn dưới dạng các luật xếp loại, cây quyết định, luật sản xuất, biểu thức hồi quy …) Đặc điểm của mẫu là phải mới (ít nhất là đối với hệ thống đó). Độ mới có thể được đo tương ứng với độ thay đổi trong dữ liệu (bằng cách so sánh các giá trị hiện tại với các giá trị trước đó hoặc tìm các giá trị mong muốn), hoặc bằng tri thức (mối liên hệ giữa phương pháp tìm mới và phương pháp cũ như thế nào). Thường thì độ mới của mẫu được đánh giá bằng một hàm logic hoặc hàm đo độ mới, độ bất ngờ của mẫu. Ngoài ra, mẫu phải có khả năng sử dụng tiềm tàng. Các mẫu này sau khi được xử lý và diễn giả phải dẫn đến những hành động có ích nào đó được đánh giá bởi một hàm lợi ích. Ví dụ như trong dữ liệu các khoản vay, hàm lợi ích đánh giá khả năng tăng lợi nhuận từ các khoản vay. Mẫu khai thác được phải có giá trị đối với các dữ liệu mới với độ chính xác nào đó. Với các giải thuật và các nhiệm vụ của khai phá dữ liệu rất khác nhau, dạng của các mẫu chiết xuất được cũng rất đa dạng. Theo cách đơn giản nhất, sự phân tích cho ra kết quả chiết xuất là một báo cáo về một loại (có thể bao gồm các phép do mang tính thống kê về độ phù hợp của mô hình,._. các dữ liệu lạ…) Trong thực tế đầu ra dưới dạng văn bản, một đồ thị mô tả các mối quan hệ là một mô tả xu hướng, có thể là dưới dạng văn bản, một đồ thị mô tả các mối quan hệ trong mô hình, cũng có thể là một hành động ví dụ như yêu cầu người dùng làm gì với những gì khai thác được trong dữ liệu. Một mẫu chiết xuất được từ một công cụ khai phá tri thức khác lại có thể là một dự đoán xem số lượng bánh kẹo bán ra vào dịp tết sẽ tăng lên bao nhiêu phần trăm… Hình 1 là một ví dụ minh hoạ kết quả của việc khai phá dữ liệu khách hàng xin vay vốn, với một lựa chọn t, mẫu chiết xuất được là một luật “Nếu thu nhập < t đồng thì khách hàng vay bị vỡ nợ”. Dạng của mẫu chiết xuất được có thể được phân loại bởi kiểu mẫu dữ liệu mà nó mô tả. Các mẫu liên vùng (interfield pattern) liên quan đến các giá trị của các trường trong cùng một bản ghi (ví dụ: nếu thủ tục = phẫu thuật thì ngày nằm viện > 5). Các mẫu liên bản ghi liên quan đến các giá trị được tổng hợp từ một nhóm các bản ghi ví dụ như bệnh nhân mắc bệnh đau dạ dày khó ăn gấp hai lần những người bình thường khác; hoặc xác định những phần có ích ví dụ như nhóm các công ty có lợi nhuận. Việc khai thác các mẫu liên bản ghi là dạng tổng kết dữ liệu. Đối với các dữ liệu phụ thuộc thời gian, mối quan hệ liên bản ghi có thể cùng xác định các xu hướng quan tâm (ví dụ như sản lượng bán hàng tăng 20% so với năm ngoái). Ta cũng có thể phân loại dạng mẫu chiết xuất được theo khả năng mô tả của chúng. Ví dụ như mẫu chiết xuất được của quá trình khai phá dữ liệu theo số lượng liên quan đến các giá trị trường số sử dụng các công thức toán học. Mẫu của quá trình khai phá dữ liệu theo chất lượng tìm ra một mối quan hệ logic giữa các trường. Ta phân biệt hai dạng này vì các kỹ thuật khai phá khác nhau thường được sử dụng trong các trường hợp khác nhau. Ví dụ như các mối quan hệ số lượng tuyến tính tìm thấy rất dễ dàng bằng các phương pháp quy hồi tuyến tính trong khi khai phá theo định tính lại không thể dùng được các phương pháp này. Kỹ thuật khai phá dữ liệu thực chất không có gì mới. Nó là sự kế thừa, kết hợp và mở rộng của các kỹ thuật cơ bản đã được nghiên cứu từ trước như học máy, nhận dạng, thống kê (quy hồi, xếp loại, phân nhóm), các mô hình đồ thị, mạng Bayes, trí tuệ nhân tạo, thu thập tri thức hệ chuyên gia… Tuy nhiên, với sự kết hợp tài tình của khai phá dữ liệu, kỹ thuật này có ưu thế hơn hẳn các phương pháp trước đó, đem lại nhiều triển vọng trong việc ứng dụng phát triển nghiên cứu khoa học cũng như làm tăng mức lợi nhuận trong các hoạt động kinh doanh. Ví dụ minh hoạ Để minh hoạ hoạt động cũng như mẫu chiết xuất được của quá trình khai phá dữ liệu, trong chương trình này ta sẽ dùng chủ yếu một ví dụ đơn giản như đã cho trên hình 1. Hình 1. miêu tả một tập dữ liệu 2 chiều gồm có 23 điểm mẫu. Mỗi điểm biểu thị cho một khách hàng đã vay ngân hàng. Trục hoành biểu thị cho thu nhập, trục tung biểu thị cho tổng dư nợ của khách hàng. Dữ liệu khách hàng được chia làm hai lớp: dấu x biểu thị cho khách hàng bị vỡ nợ, dấu o biểu thị cho khách hàng có khả năng trả nợ. Tập dữ liệu này có thể chứa những thông tin có ích đối với các tổ chức tín dụng trong việc ra quyết định có cho khách hàng vay nữa hay không. Ví dụ như ta có mẫu “Nếu thu nhập < t đồng thì khách hàng sẽ vay sẽ bị vỡ “nợ”. Hình 1 – Thông tin khách hàng vay. Nhiệm vụ chính của khai phá dữ liệu: Rõ ràng rằng mục đích của khai phá dữ liệu là các tri thức chiết xuất được sẽ được sử dụng cho lợi ích cạnh tranh trên thương trường và các lợi ích trong nghiên cứu khoa học. Do đó, ta có thể coi mục đích chính của khai thác dữ liệu sẽ là mô tả (description) và dự đoán (prediction). Các mẫu mà khai phá dữ liệu phát hiện được nhằm vào các mục đích này. Dự đoán liên quan đến việc sử dụng các biến hoặc các trường trong CSDL để chiết xuất ra các mẫu là các dự đoán những giá trị chưa biết hoặc những giá trị trong tương lai của các biến đáng quan tâm. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con người có thể hiểu được. Để đạt được hai mục đích này, nhiệm vụ chính của khai phá dữ liệu bao gồm như sau: Phân lớp (Clasification): Phân lớp là việc học một hàm ánh xạ (hay phân loại) một mẫu dữ liệu vào một trong số các lớp đã xác định (Hand 1981; Weiss & Kulikowski 1991; McLachlan 1992). Ví dụ về việc sử dụng phương pháp phân lớp các xu hướng trong thị trường tài chính (Apte & Hong) và ứng dụng tự động xác định các đối tượng đáng quan tâm trong các CSDL ảnh lớn (Fayyad, Djorgovski & Weir). Hồi quy (Regression): Hồi quy là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực. Có rất nhiều các ứng dụng khai phá dữ liệu với nhiệm vụ hồi quy, ví dụ như dự đoán số lượng biomass xuất hiện trong rừng biết các phép đo vi sóng từ xa, đánh giá khả năng tử vong của bệnh nhân biết các kết quả xét nghiệm chuẩn đoán, dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chi tiêu quảng cáo, dự đoán theo thời gian với các bến đầu vào là các giá trị của mẫu dự đoán trong quá khứ… Phân nhóm (Clustering): Là việc mô tả chung để tìm ra các tập xác định các nhóm hay các loại để mô tả dữ liệu (Titterington, Smith & Makov 1985; Jain & Dubes 1988). Các nhóm có thể tách riêng nhau hoặc phân cấp hoặc gối lên nhau. Có nghĩa là một dữ liệu có thể vừa thuộc nhóm này, vừa thuộc nhóm kia. Các ứng dụng khai phá dữ liệu có nhiệm vụ phân nhóm như phát hiện tập các khách hành có phản ứng giống nhau trong CSDL tiếp thị, xác định các loại quang phổ từ các phương pháp đo tia hồng ngoại (Cheeseman & Stutz). Hình 2.5 miêu tả các mẫu của quá trình khai phá dữ liệu với nhiệm vụ phân nhóm. Ở đây, các mẫu là các nhóm khách hàng được xếp thành ba nhóm gối lên nhau. Các điểm nằm trong cả hai nhóm chứng tỏ khách hàng có thể thuộc cả hai loại trạng thái. Chú ý rằng với nhiệm vụ này, khách hàng không được phân biệt như cũ nữa (không dùng các dấu x và o) mà được phân biệt theo nhóm (thay bằng dấu +). Liên quan chặt chẽ đến việc phân nhóm là nhiệm vụ đánh giá mật độ xác suất, bao gồm các kỹ thuật đánh giá dữ liệu, hàm mật độ xác suất đa biến liên kết của tất cả các biến/các trường trong CSDL (Silverman 1986). Tóm tắt (summarization): Liên quan đến các phương pháp tìm kiếm một mô tả tóm tắt cho một tập con dữ liệu. Ví dụ như việc lập bảng các độ lệch chuẩn và trung bình cho tất cả các trường. Các phương pháp phức tạp hơn liên quan đến nguồn gốc của các luật tóm tắt (Agrawal et al.), khai thác mối liên hệ hàm giữa các biến (Zembowicz & Zytkow). Các kỹ thuật tóm tắt thường được áp dụng cho các phân tích dữ liệu tương tác có tính thăm dò và tạo báo cáo tự động. Mô hình hoá phụ thuộc (Depedency Modeling): Bao gồm việc tìm kiếm một mô hình mô tả sự phụ thuộc đáng kể giữa các biến. Các mô hình phụ thuộc tồn tại dưới hai mức: mức cấu trúc của mô hình xác định (thường ở dạng đồ hoạ) các biến nào là phụ thuộc cục bộ với nhau, mức định lượng của một mô hình xác định độ mạnh của sự phụ thuộc theo một thước đo nào đó. Ví dụ như các mạng phụ thuộc xác suất sử dụng sự độc lập có điều kiện để xác định khía cạnh có cấu trúc của một mô hình và các xác suất hoặc tương quan để xác định độ mạnh của sự phụ thuộc (Heckerman; Glymour et al., 1987). Các mạng phụ thuộc độ xác suất đang ngày càng tìm thấy nhiều ứng dụng trong các lĩnh vực khác nhau như phát triển các hệ chuyên gia y tế áp dụng tính xác suất từ các CSDL, thu thập thông tin, mô hình hoá gen di truyền của người. Phát hiện sự thay đổi và lạc hướng (Change and Deviation Detection): Tập trung vào khai thác những thay đổi đáng kể nhất trong dữ liệu từ các giá trị chuẩn hoặc được đo trước đó (Berndt & Cliffort; Guyon et al.; Kloesgen; Matheus et al.; Basseville & Nikiforov 1993). Vì những nhiệm vụ khác nhau này yêu cầu số lượng và các dạng thông tin rất khác nhau nên chúng thường ảnh hưởng đến việc thiết kế và chọn giải thuật khai phá dữ liệu khác nhau. Ví dụ như giải thuật cây quyết định tạo ra được một mô tả phân biệt được các mẫu giữa các lớp nhưng không có các tính chất và đặc điểm của lớp. Các phương pháp khai phá dữ liệu: Quá trình khai phá dữ liệu là quá trình phát hiện mẫu trong đó, giải thuật khai phá dữ liệu tìm kiếm các mẫu đáng quan tâm theo dạng xác định như các luật, cây phân lớp, quy hồi, phân nhóm… Các thành phần của giải thuật khai phá dữ liệu: Giải thuật khai phá dữ liệu bao gồm 3 thành phần chính như sau: biểu diễn mô hình, đánh giá mô hình, tìm kiếm mô hình. Biểu diễn mô hình: Mô hình được biểu diễn bằng ngôn ngữ L để miêu tả các mẫu có thể khai thác được. Nếu sự mô tả quá bị hạn chế thì sẽ không thể học được hoặc sẽ không thể có các mẫu tạo ra được một mô hình chính xác cho dữ liệu. Ví dụ một miêu tả cây quyết định sử dụng phân chia các nút theo trường đơn, chia không gian đầu vào thành các mặt siêu phắng song song với các trục thuộc tính. Phương pháp cây quyết định như vậy không thể khai thác được từ dữ liệu dạng công tức x = y dù cho tập học có to đến đâu đi nữa. Vì vậy, việc quan trọng là người phân tích dữ liệu cần phải hiểu đầy đủ các giả thiết miêu tả. Một điều cũng khá quan trọng là người thiết kế giải thuật cần phải diễn tả được các giả thiết miêu tả nào được tạo ra bởi giải thuật nào. Khả năng miêu tả mô hình càng lớn thì càng làm tăng mức độ nguy hiểm do bị học quá và bị giảm đi khả năng dự đoán các dữ liệu chưa biết. Hơn nữa, việc tìm kiếm sẽ càng trở nên phức tạp hơn và việc giải thích mô hình cũng khó khăn hơn. Mô hình ban đầu được xác định bằng cách kết hợp biến đầu ra (phụ thuộc) với các biến độc lập mà biến đầu ra phụ thuộc vào. Sau đó phải tìm những tham số mà bài toán cần tập trung giải quyết. Việc tìm kiếm mô hình sẽ đưa ra được một mô hình phù hợp với các tham số được xác định dựa trên dữ liệu (trong một số trường hợp, mô hình được xây dựng độc lập với dữ liệu trong khi đối với một số trường hợp khác thì mô hình và các tham số lại thay đổi để phù hợp với dữ liệu). Trong một số trường hợp, tập dữ liệu được chia thành tập dữ liệu học và tập dữ liệu thử. Tập dữ liệu học được sử dụng để làm cho các tham số của mô hình phù hợp với dữ liệu. Mô hình sau đó sẽ được đánh giá bằng cách đưa các dữ liệu thử vào mô hình và thay đổi lại các tham số cho phù hợp nếu cần. Mô hình lựa chọn có thể là các phương pháp thống kê , … một số giải thuật học máy (ví dụ như suy diễn cây quyết định và các kỹ thuật học có thầy khác), mạng neuron, suy diễn hướng tình huống (case-based reasoning), các kỹ thuật phân lớp. Đánh giá mô hình: Đánh giá xem một mẫu có đáp ứng được các tiêu chuẩn của quá trình phát triển tri thức hay không. Việc đánh giá độ chính xác dự đoán dựa trên đánh giá chéo (cross validation). Đánh giá chất lượng miêu tả liên quan đến độ chính xác dự đoán, độ mới, khả năng sử dụng, khả năng hiểu được của mô hình. Cả hai chuẩn thống kê và chuẩn logic đều có thể được sử dụng để đánh giá mô hình. Ví dụ như luật xác suất lớn nhất có thể dùng để lựa chọn các tham số cho mô hình sao cho xử lý phù hợp nhất với tập dữ liệu học. Việc đánh giá mô hình được thực hiện qua kiểm tra dữ liệu (trong một số trường hợp kiểm tra với tất cả các dữ liệu, trong một số trường hợp khác chỉ kiểm tra với dữ liệu thử). Ví dụ như đối với mạng neuron, việc đánh giá mô hình được thực hiện dựa trên việc kiểm tra dữ liệu (bao gồm cả dữ liệu học và dữ liệu thử), đối với nhiệm vụ dự đoán thì việc đánh giá mô hình ngoài kiểm tra dữ liệu còn dựa trên độ chính xác dự đoán. Phương pháp tìm kiếm: phương pháp tìm kiếm bao gồm 2 thành phần: tìm kiếm tham số và tìm kiếm mô hình. Trong tìm kiếm tham số, giải thuật cần tìm kiếm các tham số để tối ưu hoá các tiêu chuẩn đánh giá mô hình với các dữ liệu quan sát được và với một miêu tả mô hình đã định. Việc tìm kiếm không cần thiết đối với những bài toán khá đơn giản: các đánh giá tham số tối ưu có thể đạt được bằng các cách đơn giản hơn. Đối với các mô hình chung thì không có các cách này, khi đó giải thuật “tham lam” thường được sử dụng lặp đi lặp lại. Ví dụ như phương pháp giảm gradient trong giải thuật lan truyền ngược (backpropagation) cho các mạng neuron. Tìm kiếm mô hình xảy ra giống như một vòng lặp qua phương pháp tìm kiếm tham số: miêu tả mô hình bị thay đổi tạo nên một họ các mô hình. Các phương pháp tìm kiếm mô hình thường sử dụng các kỹ thuật tìm hiếm heuristic vì kích thước của không gian các mô hình có thể thường ngăn cản các tìm kiếm tổng thế, hơn nữa các giải pháp đơn giản (closed form) không dễ đạt được. Một số phương pháp khai phá dữ liệu phổ biến Phương pháp quy nạp (induction): Một CSDL là một kho thông tin nhưng các thông tin quan trọng hơn cũng có thể được suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để thực hiện việc này là suy diễn và quy nạp Phương pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các thông tin trong CSDL. Ví dụ như toán tử liên kết áp dụng cho hai bảng quan hệ, bảng đầu chứa thông tin về các nhân viên và các phòng ban, bảng thứ hai chứa thông tin về các phòng ban và các trưởng phòng. Như vậy sẽ suy ra mối quan hệ giữa các nhân viên và các trưởng phòng. Phương pháp suy diễn dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết xuất được bằng cách sử dụng phương pháp này thường là các luật suy diễn. với tập dữ liệu khách hàng vay vốn ở trên, ta có mẫu chiết xuất được với ngưỡng thu thập t là một luật như sau: “nếu thu nhập của khách hàng lớn hơn t đồng thì khách hàng có khả năng trả nợ” Phương pháp quy nạp: phương pháp quy nạp suy ra các thông tin được sinh ra từ CSDL. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không phải bắt đầu với các tri thức đã biết trước. Các thông tin mà phương pháp này đem lại là các thông tin hay các tri thức cấp cao diễn tả về các đối tượng trong CSDL. Phương pháp này liên quan đến việc tìm kiếm các mẫu trong CSDL. Cây quyết định và luật: Cây quyết định: Cây quyết định là mô tả tri thức dạng đơn giản nhằm phân các đối tượng dữ liệu thành một lớp nhất định. Các nút của cây được gán nhãn là tên các thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các lá miêu tả các lớp khác nhau. Các đối tượng được phaâ lớp theo các đường đi trên cây, qua các cạnh tương ứng với giá trị của thuộc tính của đối tượng tới lá. Tạo luật: Các luật được tạo ra nhằm suy diễn một số mẫu dữ liệu có ý nghĩa về mặt thống kê. Các luật có dạng Nếu P thì Q, với P là mệnh đề đúng với một phần dữ liệu trong CSDL, Q là mệnh đề dự đoán. Ví dụ ta có một mẫu phát hiện được bằng phương pháp tạo luật; nếu giá 1 cân táo thấp hơn 5000 đồng thì số lượng táo bán ra sẽ tăng 5%. Những luật như thế này được sử dụng rất rộng rãi trong việc miêu tả tri thức trong hệ chuyên gia. Chúng có thuận lợn là dễ hiểu đối với người sử dụng. Cây quyết định và luật có ưu điểm là hình thức miêu tả đơn giản, mô hình suy diễn khá dễ hiểu đối với người sử dụng. Tuy nhiên, giới hạn của nó miêu tả cây và luật chỉ có thể biểu diễn được mộ số dạng chức năng và vì giới hạn cả đề độ chính xác của mô hình. Mẫu ví dụ như trong hình 1. cho thấy ảnh hưởng của một ngưỡng đơn giản như thế này đã hạn chế việc phân lớp với đường biên chính xác hơn mà ta có thể nhìn thấy được. Nếu mở rộng không gian của mô hình để cho phép có nhiều miêu tả hơn (ví dụ như các mặt siêu phẳng đã biến (multivariate hyperplane) tại các góc ngẫu nhiên) thì mô hình sẽ dự đoán tốt hơn nhưng lại rất khó hiểu. Cho đến nay, đã có rất nhiều giải thuật suy diễn sử dụng các luật và cây quyết định được áp dụng trong học máy và trong thống kê (Breiman et al. 1984; Quinlan 1992). Đối với quy mô lớn, người ta dự trên các phương pháp đánh gia mô hình theo xác suất với các mức độ hình thức phức tạp khác nhau. Các phương pháp tìm kiếm “tham lam”, liên quan đến việc tăng và rút gọn các luật và các cấu trúc cây, chủ yếu được sử dụng để khai thác không gian siêu mũ (super-exponential space) của các mô hình. Cây và luật chủ yếu được sử dụng cho việc mô hình hoá dự đoán, phân lớp (Apte & Hong; Fayyad, Djorgovski, & Wei) và hồi quy. Chúng ta có thể được áp dụng cho việc tóm tắt và mô hình hoá các miêu tả (Agrawal et al.) Phát hiện các 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 CSDL. 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ụ sang đơ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. Cho một lược đồ R = {A1,…, Ap} các thuộc tính với miền trị {0,1} và một quan hệ r trên R. Một luật kết hợp trên r được mô tả dưới dạng X => B với X Í R và B Î R/X. Về mặt trực giác, ta có thể phát biểu ý nghĩa của luật như sau: nếu một bản ghi của bảng r có giá trị 1 tại mỗi thuộc tính thuộc X thì giá trị của thuộc tính b cũng là 1 trong cùng bản đồ đó. Ví dụ ta có tập CSDL về các mặt hàng bán trong siêu thị, các hàng tương ứng với các ngày bán hàng, các cột tương ứng với các mặt hàng thì giá trị 1 tại ô (20/10, bánh mỳ) xác định rằng bánh mỳ đã được bán ngày hôm đó cũng kéo theo sự xuất hiện của giá trị 1 tại ô (20/10, bơ). Cho W Í R, đặt s(W,r) là tần số xuất hiện của W trong r được tính bằng tỷ lệ của các hàng trong r có giá trị 1 tại mỗi cột thuộc W. Tần số xuất hiện của luật X => B trong r được định nghĩa là s(XÈ{B},r) còn gọi là độ hỗ trợ của luật, độ tin cậy của luật là s(XÈ{B},r)/s(X,r). Ở đây X có thể gồm nhiều thuộc tính, B là giá trị không cố định. Nhờ vậy mà không xảy ra việc tạo ra các luật không mong muốn trước khi quá trình tìm kiếm bắt đầu. Điều đó cũng cho thấy không gian tìm kiếm có kích thước tăng theo hàm mũ của số lượng các thuộc tính ở đầu vào. Do vậy cần phải chú ý khi thiết kế dữ liệu cho việc tìm kiếm các luật kết hợp. Nhiệm vụ của việc phát hiện ra các luật kết hợp là phải tìm tất cả các luật X => B sao cho tần số của luật không nhỏ hơn ngưỡng s cho trước và độ tin cậy của luật không nhỏ hơn ngưỡng q cho trước. Từ một CSDL ta có thể tìm được hàng nghìn và thậm trí hàng trăm nghìn các luật kết hợp. Ta gọi một tập con X Í R là thường xuyên trong r nếu thoả mãn điều kiện s(X,r)³s. Nếu biết tất cả các tập thường xuyên trong r thì việc tìm kiếm các luật kết hợp rất dễ dàng. Vì vậy, giải thuật tìm kiếm các luật thường kết hợp trước tiên đi tìm tất cả các tập thường xuyên này, sau đó tạo dựng dần các luật kết hợp bằng cách ghép dần các tập thuộc tính dựa trên mức độ thường xuyên. Các luật kết hợp có thể là một cách hình thức hoá đơn giản. Chúng rất thích hợp cho việc tạo ra các kết quả có dữ liệu dạng nhị phân. Giới hạn cơ bản của phương pháp này là ở chỗ các quan hệ cần phải thưa theo nghĩa không có tập thường xuyên nào chứa nhiều hơn 15 thuộc tính. Giải thuật tìm kiếm các luật kết hợp tạo ra số luật ít nhất phải bằng số các tập thường xuyên và nếu như một tập thường xuyên có kích thước K thì phải có ít nhất là 2K tập thường xuyên. Thông tin về vác tập thường xuyên được sử dụng để ước lượng độ tin cậy của các tập luật kết hợp. Các phương pháp phân lớp và quy hồi phi tuyến. Các phương pháp này bao gồm một họ các kỹ thuật dự đoán để làm cho các kết hợp tuyến tính và phi tuyến của các hàm cơ bản (hàm sigmoid, hàm spline (hàm mành), hàm đa thức) phù hợp với các kết hợp của các giá trị biến vào. Các phương pháp thuộc loại này như mạng neuron truyền thẳng, phương pháp mành thích nghi… (Friedman 1989, Cheng & Titterington 1994, Elder & Pregibon). Mẫu minh hoạ trên hình 2.7 miêu tả một dạng đường biên phi tuyến mà mạng neuron tìm ra từ tập dữ liệu khách hàng vay. Xét về mặt đánh giá mô hình, mặc dù mạng neuron với kích thước tương đối hầu như lúc nào cũng có thể mô phỏng bất kỳ hàm nào gần đúng với một đọ chính xác mong muốn nào đó. Nhưng để tìm được một mạng có kích thước tối ưu cho một tập dữ liệu xác định lại là một việc khá công phu và không ai có thể biết chắc có tìm ra được kích thước đó hay không. Các phương pháp sai số bình phương chuẩn (standard squared error) và các hàm entroy (cross entropy loss function) được sử dụng để học có thể được xem như các hàm khả năng logarit (log-likelihood) functions) khi phân lớp và hồi quy. (Geman, Bienentstock & Doursat 1992; Ripley 1994). Lan truyền ngược sai số là một phương pháp tìm kiếm tham số thực hiện việc giảm gradient trong không gian tham số (ở đây là các trọng số) để tìm một giá trị cực đại cục bộ của hàm xác xuất bắt đầu từ các giá trị khởi tạo ngẫu nhiên. Các phương pháp hồi quy phi tuyến mặc dù rất có khả năng diễn tả nhưng lại rất khó diễn giải thành các luật. Phân nhóm và phân loại (clustering and segmentation) Kỹ thuật phân nhóm và phân loại là những kỹ thuật phân chia dữ liệu sao cho mỗi phần hoặc mỗi nhóm giống nhau theo một tiêu chuẩn nào đó. Mối quan hệ thành viên cùa các nhóm có thể dựa trên mức độ giống nhau của các thành viên trong nhóm. Một kỹ thuật phân nhóm khác là xây dựng nên các hàm đánh giá các thuộc tính của các thành phần như là hàm của các tham số của các thành phần. Phương pháp này được gọi là phương pháp phân hoạch tối ưu (opimal partitioning). Một ví dụ ứng dụng của phương pháp phân nhóm theo độ giống nhau là CSDL khách hàng, ứng dụng của phương pháp tối ưu ví dụ như phân nhóm khách hàng theo số các tham số và các nhóm thuế tối ưu có được khi thiết lập biểu thuế bảo hiểm. Mẫu đấu ra của quá trình khai phá dữ liệu sử dụng kỹ thuật này là các tập mẫu chứa các dữ liệu có chung những tính chất nào đó được phân tách từ CSDL. Khi các mẫu được thiết lập, chúng có thể được sử dụng để tái tạo các tập dữ liệu ở dạng dễ hiểu hơn, đồng thời cũng cung cấp các nhóm dữ liệu cho các hoạt động cũng như công việc phân tích. Đối với CSDL lớn, việc lấy ra các nhóm này rất là quan trọng. Các phương pháp dựa trên mẫu Sử dụng các mẫu miêu tả từ CSDL để tạo nên mô hình dự đoán các mẫu mới bằng cách rút ra các thuộc tính tương tự như các mẫu đã biết trong mô hình. Các kỹ thuật bao gồm phân lớp theo láng giềng gần nhất, các giải thuật hồi quy (Dasarathy 1991) và các hệ thống suy diễn dựa trên tình huống (case-based reasoning) (Kolodner 1993). Khuyết điểm của các kỹ thuật này là cần phải xác định được khoảng cách, độ đo giống nhau giữa các mẫu. Mô hình thường được đánh giá bằng phương pháp đánh giá chéo trên các lỗi dự đoán (Weiss $ Kulikowski, 1991). “Tham số” của mô hình được đánh giá có thể bao gồm một số láng giềng dùng để dự đoán và số đo khoảng cách. Giống như phương pháp hồi quy phi tuyến, các phương pháp này khá mạnh trong việc đánh giá xấp xỉ các thuộc tính, nhưng lại rất khó chiều vì mô hình không được định dạng rõ ràng mà tiềm ẩn trong dữ liệu. Mô hình phụ thuộc trên đồ thị xác suất. Các mô hình đồ thị xác định sự phụ thuộc xác suất giữa các sự kiện thông qua các liên hệ trực tiếp theo các cung đồ thị (Pearl 1988; Whittaker, 1990). Ở dạng đơn giản nhất, mô hình này xác định những biến nào phụ thuộc trực tiếp vào nhau. Những mô hình này chủ yếu được sử dụng với các biến có giá trị rời rạc hoặc phân loại. Tuy nhiên cũng được mở rộng cho một số trường hợp đặc biệt như mật độ Gaussian hoặc cho các biến giá trị thực. Trong trí tuệ nhân tạo và thống kê, các phương pháp này ban đầu được phát triển trong khuôn khổ các hệ chuyên gia. Cấu trúc của mô hình và các tham số (xác suất có điều kiện được gắn với các đường nối của đồ thị) được suy ra từ các chuyên gia. Ngày nay, các phương pháp này đã được phát triển, cả cấu trúc và các tham số mô hình đồ thị đều có thể học trực tiếp từ CSDL (Buntine; Heckerman). Tiêu chuẩn đánh giá mô hình chủ yếu là ở dạng Bayesia. Việc đánh giá tham số là một sự kết hợp các đánh giá dạng đóng (closed form estimate) và các phương pháp lặp phụ thuộc vào việc biến được quan sát trực tiếp hay ở dạng ẩn. Việc tìm kiếm mô hình dựa trên các phương pháp “leo đồi” trên nhiều cấu trúc đồ thị. Các tri thức trước đó, ví dụ như việc sắp xếp một phần các biến dựa trên các mối quan hệ nhân quả, có thể rất có ích trong việc làm giảm không gian tìm kiếm mô hình. Mặc dù các phương pháp này mới có ở giai đoạn đầu của việc nghiên cứu nhưng nó đã cho thấy nhiều hứa hẹn vì dạng đồ thị dễ hiểu hơn và biểu đạt được nhiều ý nghĩa hơn đối với con người. Mô hình học quan hệ Trong khi mẫu chiết xuất được bằng các luật suy diễn và cây quyết định gắn chặt với các mệnh đề logic (propositional logic) thì mô hình học quan hệ (còn được gọi là lập trình logic quy nạp – inductive logic programming) sử dụng ngôn ngữ mẫu theo thứ tự logic trước (first-order logic) rất linh hoạt. Mô hình này có thể dễ dàng tìm ra công thức: X = Y. Cho đến nay, hầu hết các nghiên cứu về các phương pháp đánh giá mô hình này đều theo logic trong tự nhiên. Khai phá dữ liệu văn bản (Text Mining) Kỹ thuật này được ứng dụng trong một loạt các công cụ phần mềm thương mại. Công cụ khai phá dữ liệu rất phù hợp với việc tìm kiếm, phân tích và phân lớp các dữ liệu văn bản không định dạng. Các lĩnh vực ứng dụng như nghiên cứu thị trường, thu thập tình báo… Khai phá dữ liệu dạng văn bản đã được sử dụng để phân tích câu trả lời cho các câu hỏi mở trong khảo sát thị trường, tìm kiếm các tài liệu phức tạp. Mạng neuron Mạng neuron là một tiếp cận tính toán mới liên quan đến việc phát triển các cấu trúc toán học với khả năng học. Các phương pháp là kết quả của việc nghiên cứu mô hình học của hệ thống thần kinh con người. Mạng neuron có thể đưa ra ý nghĩa từ các dữ liệu phức tạp hoặc không chính xác và có thể được sử dụng để chiết xuất các mẫu và phát hiện ra các xu hướng quá phức tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện được. Khi đề cập đến khai phá dữ liệu, người ta thường đề cập nhiều đến mạng neuron. Tuy mạng neuron có một số hạn chế gây khó khắn trong việc áp dụng và triển khai nhưng nó cũng có những ưu điểm đáng kể. Một trong số những ưu điểm phải kể đến của mạng neuron là khả năng tạo ra các mô hình dự đoán có độ chính xác cao, có thể áp dụng được cho rất nhiều các loại bài toán khác nhau đáp ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như phân lớp, phân nhóm, mô hình hoá, dự báo các sự kiện phụ thuộc vào thời gian… Mẫu chiết xuất bằng mạng neuron được thể hiện ở các nút đầu ra của mạng. Mạng neuron sử dụng các hàm số chứ không sử dụng các hàm biểu tượng (symbol function) để tính mức tích cực của các nút đầu ra và cập nhật các trọng số của nó. Trong mạng lan truyền ngược mà ta sẽ đề cập cụ thể ở phần sao, mỗi nút khái niệm được kết hợp với một ngưỡng, vì vậy mà trong mạng lan truyền ngược, các mẫu (hay các luật) của một khái niệm là sự kết hợp của các trọng số lớn hơn ngưỡng. Đặc điểm của mạng neuron là không cần gia công dữ liệu nhiều trước khi bắt đầu quá trình học như các phương pháp khác. Tuy nhiên, để có thể sử dụng mạng neuron có hiệu quả cần phải xác định các yếu tố khi thiết kế mạng như: - Mô hình mạng là gì ? - Mạng cần có bao nhiêu nút ? - Khi nào thì việc học dừng để tránh bị “học quá” ? - …. Ngoài ra còn có rất nhiều bước quan trọng cần phải làm để tiền xử lý dữ liệu trước khi đưa vào mạng neuron để mạng có thể hiểu được (ví dụ như việc chuẩn bị hoá dữ liệu, đưa tất cả các tiêu chuẩn dự đoán về dạng số). Mạng neuron được đóng gói với những thông tin trợ giúp của các chuyên gia đáng tin cậy và được các chuyên gia đảm bảo các mô hình này là việc tốt. Sau khi học, mạng có thể được coi là một chuyên gia trong lĩnh vực thông tin mà nó vừa được học. Giải thuật di truyền. Giải thuật di truyền, nói theo nghĩa rộng là mô phỏng lại hệ thống tiến hoá trong tự nhiên, chính xác hơn đó là các giải thuật chỉ ra tập các thể được hình thành, được ước lượng và biến đổi như thế nào. Ví dụ như xác định xem làm thế nào để lựa chọn các cá thể tạo giống và lựa chọn các thể nào sẽ bị loại bỏ. Giải thuật cũng mô phỏng lại yếu tố gen trong nhiễm sắc thể sinh học trên máy tính để có thể giải quyết nhiều bài toán thực tế khác nhau. Giải thuật di truyền là một giải thuật tối ưu hoá. Nó được sử dụng rất rộng rãi trong việc tối ưu hoá các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng neuron. Sự liên hệ của nó với các giải thuật khai phá dữ liệu là ở chỗ tối ưu hoá cần thiết cho các quá trình khai phá dữ liệu. Ví dụ như trong các kỹ thuật cây quyết định, tạo luật. Như đã đề cập ở phần trước, các luật mô hình hoá dữ liệu chứa các tham số được xác định các giải thuật tham số nào tạo ra các luật tốt nhất. Và vì vậy mà giải thuật di truyền đã được sử dụng trong các công cụ khai phá dữ liệu. Kỹ thuật này sẽ được tìm hiểu sâu hơn ở chương sau. Như vậy, nhìn vào các phương pháp giới thiệu ở trên, chúng ta thấy có nhiều các phương pháp khai phá dữ liệu. Mỗi phương pháp có những đặc điểm riêng phù hợp với một lớp các bài toán với các dạng dữ liệu và miền dữ liệu nhất định. Giả sử đối với bài toán dự đoán theo thời gian, trước kia người ta thường đặt nhiệm vụ cho việc khai phá các mẫu dạng này hồi quy đoán hoặc như các hàm phi tuyến, phương pháp dựa trên mẫu, mạng neuron đã được áp dụng để giải loại bài toán này. Như vậy, mặc dù nhìn bề ngoài ta thấy có rất nhiều các phương pháp và ứng dụng khai phá dữ liệu nhưng cũng không có gì là lạ khi nhận thấy chúng có một số thành phần chung. Hiểu quá trình khai phá dữ liệu và suy diễn được mô hình dựa trên những thành phần này là ta đã thực hiện được nhiệm vụ của khai phá dữ liệu. Lợi thế của khai phá dữ liệu so với các phương pháp cơ bản Như đã phân tính ở trên, ta thấy khai phá dữ liệu không có gì mới mà hoàn toàn dựa trên các phương pháp cơ bản đã biết. Vậy khai phá dữ liệu có gì khác so với các phương pháp đó ? Và tại sao khai phá dữ liệu lại có ưu thế hơn hẳn chúng? Các phân tích sau đây sẽ giải đáp những câu hỏi này. Học máy (Machine Learning) Mặc dù người ta đã cố gắng cải tiến các phương pháp học máy để có thể phù hợp với mục đích khai phá dữ liệu nhưng sự khác biệt giữa cách thiết kế, các đặc điểm của CSDL đã là cho phương pháp học máy trở nên không phù hợp với mục đích này, mặc dù cho đến nay, phần lớn các phương pháp khai phá dữ liệu vẫn dựa trên nền tảng cơ sở của phương pháp học máy. Những phân tích sau đây sẽ cho thấy điều đó. Trong quản trị CSDL, một CSDL là một tập hợp được tích hợp một cách logic của dữ liệu được lưu trong một hay nhiều tệp và được tổ chức để lưu trữ có hiệu quả, sửa đổi và lấy thông tin liên quan được dễ dàng. Ví dụ như trong CSDL q._.(T(x,y,z) với mọi 0 £x,y,z£ 1 Từ những tiên đề trên chúng ta suy ra ngay T(0,x). Hơn nữa tiên đề d) đảm bảo tính thác triển duy nhất cho hàm nhiều biến. Mệnh đề 5: Với t – chuẩn T thì: T5(x,y) £ T(x,y) £T1(x,y) = min(x,y) với mọi 0£x,y£1 Chứng minh : Thật vậy Nếu max(x,y) = 1 Khi x = 1, T(1,y) = y = min (x,y) hay T5(x,y) = T(x,y) = T1(x,y). Tương tự nếu y = 1. Nếu max(x,y)<1, T5(x,y) = 0 <T(x,y) Giả sử y = min(x,y), khi đó T(x,y) £T(1,y) = y =T1(x,y). Tương tự nếu x = min (x,y). Định nghĩa 11 : a. Một t – chuẩn T gọi là tiên tục nếu T là hàm liên tục trên [0,1]2. b. Hàm T gọi là Archimed nếu T(x,y)<x với mọi 0<x<1. c. Hàm T gọi là chặt nếu T tăng chặt trên (0,1)2 Định lý 2 : Cho T là một t-chuẩn, ta xác định Tf :[0,1] ´ [0,1] ® [0,1] bằng định nghĩa : Tf(x,y)=f-1(T(f(x),f(y))), với mọi 0 £x,y£1. Khi đó Tf là một t-chuẩn. Nếu T là Archimed thì Tf là Archimed. Định nghĩa 12: Ứng với t-chuẩn T, tập giao của hai tập mờ A,B là tập mờ (AÇTB) trên X với hàm cho bởi : (AÇTB)(x) = T(A(x),B(x)), "xÎX Việc lựa choạn phép giao tương ứng với t-chuẩn T nào tùy thuộc vào bài toán được quan tâm. Phép tuyển Giống như phép hội, phép tuyển hay toán tử logíc OR(disjunction) thông thường cần thỏa mãn các tiên đề sau : Định nghĩa 13 : Hàm S : [0,1]2 ® [0,1] gọi là phép tuyển (OR suy rộng) hay là t-đối chuẩn (t-conorm) nếu thỏa mãn các tiên đề sau : S(0,x) = x với mọi x Î[0,1] S có tính giao hoán: S(x,y) = S(x,y) với mọi 0 £ x,y £ 1 S không giảm:S(x,y) £ S(u,v) với mọi 0 £ x£u £ 1 và 0 £ y£v £ 1 S có tính kết hợp: S(x,S(y,z)) = S(S(x,y),z) với mọi 0£x,y,z£1 Từ định nghĩa ta thấy: S(0,1)£S(x,1) Û 1£S(x,1)£1 => S(x,1) = 1 Định lý 3: Với S là một t-đối chuẩn bất kỳ thì bất đẳng thức sau luôn đúng với x,yÎ[0,1]: S0(x,y) £ S(x,y) £S4(x,y) b) S0 £ S1 £ S2 £ S4 Mệnh đề 6: Nếu S là t-đối chuẩn thì: max(x,y) £ S(x,y) £ Z’(x,y) với mọi 0 £ x,y £ 1. Định nghĩa 14: Cho S là t-đối chuẩn. Khi ấy : S gọi là liên tục nếu S là hàm liên tục trên [0,1]2 Hàm S gọi là Archimed nếu S(x,x) > x với mọi 0 < x < 1 S gọi là chặt nếu S tăng chặt trên (0,1)2 Định lý 4: Cho S là một t-đối chuẩn, ta xác định: Sf: [0,1] ´ [0,1] ® [0,1] Sf(x,y)= f-1(S(f(x), f(y))). Khi đó Sf là một t-đối chuẩn. Nếu S là Archimed thì Sf là Archimed. Định nghĩa 15: Cho A và B là 2 tập mờ trên không gian nền X, với hàm thuộc A(x), B(x) tương ứng. Cho S là một t-đối chuẩn. Phép hợp (AÈSB) là một tập mờ trên X với hàm thuộc cho bởi biểu thức: (AÈSB)(x) = S(A(x), B(x), "xÎX. Việc lựa chọn phép hợp, tương ứng với t-đối chuẩn S nào tùy thuộc vào bài toán ta quan tâm. Định nghĩa 16 : Cho T là t-chuẩn, S là t-đối, n là phép phủ định mạnh. Chúng ta nói bộ ba (T,S,n) là một bộ ba De Morgan nếu thỏa mãn một trong 2 đẳng thức sau : S(x,y) = n(T(n(x),n(y))) hay T(x,y) = n(S(n(x),n(y))) Khi ấy ta nói T và S đối ngẫu với nhau. Quan hệ đối ngẫu giữa t-chuẩn và t-đối chuẩn có thể thấy qua định lý sau. Định lý 5: Cho n là phép phủ định mạnh a) S(x,y) là một t-đối chuẩn và T(x,y) cho bởi : T(x,y) = nT(S(n(x),n(y) với mọi 0£x,y£1 Khi đó T(x,y) là một t-chuẩn. b) Đối ngẫu, cho T(x,y) là t-chuẩn và S(x,y)cho bởi S(x,y) = nT(T(n(x),n(y)) với mọi 0£x,y£1 Khi đó S (x,y) là một t-chuẩn Phép kéo theo Phép kéo theo là công đoạn chủ chốt nhất của quá trình suy diễn trong mọi lập luận xấp xỉ, bao gồm cả lập luận mờ. Phép kéo theo (Implication) được xét như một mối quan hệ, một toán tử logíc. Khi mô hình hóa có thể xét tới các tiên đề sau cho hàm v(P1ÞP2): tđ0: v(P1ÞP2) chỉ phụ thuộc vào giá trị v(P1), v(P2) tđ1: Nếu v(P1) £ v(P2) thì v(P1ÞP2) ³ v(P3ÞP2) với mọi mệnh đề P2 tđ2: Nếu v(P1) £ v(P3) thì v(P1ÞP2) £ v(P1ÞP3) với mệnh đề P1 tđ3: Nếu v(P1) = 0 thì v(P1ÞP) = 1 với mỗi mệnh đề P tđ4: Nếu v(P1) = 1 thì v(PÞP1)=1 với mỗi mệnh đề P tđ5: Nếu v(P1) =1 và v(P2) = 0 thì v(P1ÞP2) = 0 Tính hợp lí của các tiên đề này chủ yếu dựa vào lôgic cổ điển và những tư duy trực tiếp về phép suy diễn. Từ tiên đề I0 ta khẳng định sự tồn tại của hàm I(x,y) xác định trên [0,1]2, với giá trị chân lí qua biểu thức sau: v(P1ÞP2) = I (v(P1), v(P2)) Định nghĩa 17: Phép kéo theo (implication) là một hàm số I: [0,1]2 ® [0,1] thỏa mãn các điều kiện sau: Nếu x £ z thì I(x,y) ³ I (z,y) với mọi y Î [0,1] Nếu y £ u thì I(x,y) £ I (x,u) với mọi x Î [0,1] I (0,x) = 1 với mọi x Î [0,1] I (x,1) = 1 với mọi x Î [0,1] I (1,0) = 0 Một số dạng hàm kéo theo cụ thể: Định nghĩa 18: Dạng kéo theo thứ nhất. Cho S(x,y) là một t-đối chuẩn, n(x) là một phủ định mạnh. Hàm IS(x,y) xác định trên [0,1]2 bằng biểu thức: IS(x,y) = S(n(x),y), " 0£x,y£1 Rõ ràng ẩn ý sau định nghĩa này là công thức từ logic cổ điển PÞQ Û (ØPÚQ) Định lý 6: Với bất kỳ t-chuẩn T, t- đối chuẩn S và phép phủ định mạnh n nào, IS được định nghĩa như trên là một phép kéo theo. Định nghĩa 19: Dạng kéo theo thứ hai. Cho T là một t-chuẩn, hàm IT(x,y) xác định trên [0,1]2 bằng biểu thức : IT(x,y) = sup{u:T(x,u) £y, " 0£x,y£1} Định lý 7: Với bất kỳ t-chuẩn T nào, IT được định nghĩa như trên là một phép kéo theo. Định nghĩa 20: Dạng kéo theo thứ ba. Cho (T, S,n) là bộ ba De Morgan với n là phép phủ định mạnh, phép kéo theo thứ ba IS(x,y) = S(T(x,y), n(x), " 0 £ x,y £1. Quan hệ mờ Quan hệ mờ và phép hợp thành Định nghĩa 19: Cho X, Y là hai không gian nền. R gọi là một quan hệ mờ trên X x Y nếu R là một tập mờ trên X x Y, tức là có một hàm thuộc mR: X x Y ® [0,1]. Ở đây mR(x,y) = R(x,y) là độ thuộc (membership degree) của (x,y) vào quan hệ R. Định nghĩa 20: Cho R1 và R2 là hai quan hệ mờ trên X x Y, ta có định nghĩa a. Quan hệ R1 È R2 với mR1 È R2(x,y) = max {x,y}, mR2(x,y), " (x,y) Î XxY b. Quan hệ R1 Ç R2 với mR1 Ç R2(x,y) = max {x,y}, mR2(x,y), " (x,y) Î XxY Định nghĩa 21: Quan hệ mờ trên những tập mờ. Cho tập mờ A với mA(x) trên X, tập mờ B với mR(x) trên Y. Quan hệ mờ trên các tập mờ A và B là quan hệ mờ R trên XxY thỏa mãn điều kiện: mB(x,y) £ mA(x). " y Î Y và mR(x,y) £ mB(x), " x Î X. Định nghĩa 22: Cho quan hệ mờ R trên XxY Phép chiếu của R lên X là: projXR = {(x, maxymR(x,y): xÎX)} Phép chiếu của R lên Y là: projYR = {(y, maxxmR(x,y): yÎY)} Định nghĩa 23: Cho quan hệ mờ R trên XxY. Thác triển R lên không gian tích XxYxZ là: extXYZR = {(x,y,z), mext(x,y,z) = mR(x,y), "z ÎZ} Phép hợp thành Định nghĩa 24: Cho R1 là quan hệ mờ trên XxY và R2 là quan hệ mờ trên YxZ. Hợp thành R1 ° R2 của R1, R2 là quan hệ mờ trên XxZ. a. Hợp thành max-min (max-min composition) được xác định bởi mR1°R2(x,z) = maxy{min(mR1(x,y),mR2(y,z)}, "(x,z) Î XxZ. b. Hợp thành max-prod cho bởi mR1°R2(x,z) = maxy{mR1(x,y),mR2(y,z)}, "(x,z) Î XxZ. c. Hợp thành max -* được xác định bởi toán tử *: [0,1]2 ® [0,1] mR1°R2(x,z) = maxy{mR1(x,y)*mR2(y,z)}, "(x,z) Î XxZ. Giả thiết (T, S, n) là bộ ba De Morgan, trong đó T là t-chuẩn, S là t-đối chuẩn, n là phép phủ định. Định nghĩa 25: Cho R1, R2 là quan hệ mờ trên XxY, phép T- tích hợp thành cho một quan hệ R1°TR2 trên XxY xác định bởi R1°TR2(x,z) = supyÎXT(R1(x,y), R2(y,z)) Định lý 8: Cho R1, R2, R3 là những quan hệ mờ trên XxX, khi đó: a. R1°T(R2R3) = (R1°TR2)°TR3 b. Nếu R1 Í R2 thì R1°TR3 Í R2°TR3 và R3°TR1 Í R3°TR2 Tính chuyển tiếp Định nghĩa 26: Quan hệ mờ R trên XxX gọi là: a. min –chuyển tiếp nếu min{R(x,y), R(y,z)} £ R(x,z) "x,y,z ÎX. b. chuyển tiếp yếu nếu "x, y, z Î X có R(x,y) > R(y,x) và R(y,z) > R(z,y) thì R(x,z) > R(z,x) c. chuyển tiếp tham số nếu có một số 0q>R(y,x) và R(y,z)>q>R(z,y) thì R(x,z)>q>R(z,x) "x,y,z Î X. Định lý 9: a. Nếu R là quan hệ mờ có tính chất min-chuyển tiếp thì R là quan hệ mờ có tính chất chuyển tiếp tham số với mọi 0<q<1. b. Nếu R là quan hệ mờ có tính chất chuyển tiếp tham số thì R là quan hệ mờ có tính chất chuyển tiếp yếu. Điều khiển mờ Như đã trình bày, những ứng dụng thực tiễn thành công nhất là điều khiển mở. Do vậy, thật tự nhiên chúng sẽ trình bày khá chi tiết về lĩnh vực hấp dẫn này. Cấu trúc cơ bản Tư tưởng cơ bản của điều khiển dựa vào logic mờ là đưa các kinh nghiệm chuyên gia của những người vận hành giỏi hệ thống vào trong thiết kế các bộ điều khiển các quá trình trong đó quan hệ vào – ra (input – output) được cho bởi một tập các luật điều khiển mờ (dạng luật if … then) Cấu trúc cơ bản (Basic architecture) Cấu trúc cơ bản của một bộ điều khiển dựa vào logic mờ (fuzzy logic control FLC) gồm bốn thành phần chính (hình 1): khâu mờ hóa (a fuzzifier), một cơ sở các luật mờ (a fuzzy rule base). Một môtơ suy diễn (an infernce engine) và khâu giải mờ (a defuzzifier). Nếu đầu ra sau công đoạn giải mờ không phải là một tín hiệu điều khiển (thường gọi là tín hiệu điều chỉnh) thì chúng ta có một hệ quyết định trên cơ sở logic mờ. Mờ hóa Mô tơ suy diễn Cơ sở luật mờ Giải mờ Đối tượng m(x) m(y) y Hình 3 – Mô tơ suy diễn Không gian input-output Vì mục tiêu của bộ điều khiển mờ là tính toán các giá trị của các biến điều khiển từ quan sát và đo lường các biến trạng thái của quá trình được điều khiển sao cho hệ thống vận hành như mong muốn. Như vậy, việc chọn các biến trạng thái và các biến điều khiển phải đặc trưng cho các phép toán (theo operator) của bộ điều khiển mờ và có tác động cơ bản lên sự quá trình thực hiện bộ FLC. Kinh nghiệm của các chuyên gia và các tri thức về công nghệ đóng vai trò rất quan trọng trong việc lựa chọn các biến. Ví dụ các biến vào thường là trạng thái (state) sai lầm trạng thái (state error, state error derivate, state error intergral, …). Khi sử dụng biến ngôn ngữ, biến ngôn ngữ đầu vào x sẽ gồm các biến ngôn ngữ input xi xác định trên không gian nền Ui và tương tự với biến đầu ra y trên không gian nền Uj. Khi đó: x = {(x1,Ui,{Axi(1), … Axi(ki)}. {mxi(ki)}: i = 1,2, …n} y = {(y1,Vi,{Ayi(1), … Ayi(ki)}. {myi(ki)}: i = 1,2, …m} ở đây xi là biến ngôn ngữ xác định trên không gian nền Ui, nhận từ - giá trị Axi với hàm thuộc mxi(k) với k = 1, 2, …, ki. Tương tự cho các biến output yj. Ví dụ x1 là biến tốc độ trên không gian nền là miền giá trị vật lý U1 = [0,200km/h]. Biến ngôn ngữ tốc độ có thể có các từ giá trị {rất chậm, chậm, trung bình, nhanh, rất nhanh} Mỗi giá trị ngôn ngữ của biến này được xác định bằng một tập mờ trên U với các hàm thuộc mchậm(u), …, mtrung bình(u). Khâu mờ hóa Vì nhiều luật cho dưới dạng dùng các biến ngôn ngữ với các từ thông thường. Như vậy với những giá trị (rõ) quan sát được, đo được cụ thể, để có thể tham gai vào quá trình điều khiển khi cần thiết phải mờ hóa. Có thể định nghĩa, mờ hóa là một ánh xạ (mapping) từ không gian các giá trị quan sát được (rõ) vào không gian của các từ - tập mờ trên không gian của các biến ngôn ngữ input. Ví dụ ứng với biến ngôn ngữ tốc độ, ta cho phép mờ hóa bằng ánh xạ. - Tốc độ một xe tải đo được: u = 75km/h - Từ đó có: (mrất chậm(75), mchậm(75),mtrung bình(75),mnhanh(75), mrất nhanh(75)). Cơ sở các luật mờ Dạng tổng quát của các luật điều khiển mờ là bộ các quy tắc mờ dạng IF … THEN, trong đó các điều kiện đầu vào và cả các biến ra (hệ quả sử dụng các biến ngôn ngữ. Viết ở dạng tổng quát, cơ sở các luật mờ trong các hệ thống nhiều biến vào (ouput) và một biến ra (output)(tức là với các hệ MISO) cho dưới dạng sau: Cho x1, x2, …, xm là các biến vào của hệ thống, y là biến ra (thường là các biến ngôn ngữ). Các tập Aij, Bj, với i =1, …, m; j = 1, …,n là các tập mờ trong các không gian nền tương ứng của các biến vào và biến ra đang sử dụng của hệ thống. Các Rj là các suy diễn mờ (các luật mờ) dạng “Nếu … thì” (dạng if … then). R1 Nếu x1 là A11 và … và xm là Am1 thì y là B1 R2 Nếu x1 là A12 và … và xm là Am2 thì y là B2 Rn Nếu x1 là A1n và … và xm là Amn thì y là Bn Cho: Nếu x1 là A1* và … và xm là Am* Tính: y là B* ở đây A1*, …, Am* là các giá trị đầu vào hay sự kiện (có thể mờ hoặc giá trị rõ). Một dạng tường minh các luật mờ thường cho dưới dạng Rj: Nếu x1 là A1j và … và xm là Amj thì y = fj (x1, x2, …, xm), j = 1, …, n. Ở đây fi(x1, x2, …, xm) là một hàm của các biến trạng thái. Mô tơ suy diễn Đây là phần cốt lõi nhất của FLC trong quá trình mô hình hoá các bài toán điều khiển và chọn quyết định của con ngường trong khuôn khổ vận dụng logic mờ và lập luận xấp xỉ. Do các hệ thống được xét dưới dạng hệ vào – ra nên luật suy diễn modus ponens suy rộng đóng một vai trò rất quan trọng. Như đã trình bày trong phần trước. Suy luận xấp xỉ, phép hợp thành và phép kéo theo của logic mờ sẽ quyết định trong công việc chính trong quá trình tính toán cũng như trong quá trình rút ra kết luận. Bảng sau đây giới thiệu một số phép kéo theo mờ (fuzzy implications) thường được sử dụng trong diễn đạt các luật mờ. Phép kéo theo Công thức Toán tử min [Mamdani] a =>b = min (a,b) Toán tử tích [Larsen] a =>b = a.b Tích bị chặn a =>b = max(0, a+b-1) Quy tắc số học [Zadeh] a => b= min (1, 1-a+b) Quy tắc max=min [Zadeh] a => b = max (1-a, min (a,b)) Suy diễn bình thường a=>b = 1 nếu a£ b 0 nếu a>b Logic Boole a => b = max (1-a, b) Logic Godel a => b = 1 nếu a £ b b nếu a > b Phép kéo theo Goguen a =>b = 1 nếu a £ b b b Khâu giả mờ Đây là khâu thực hiện quá trình xác định một giá trị rõ có thể chấp nhận được làm đầu ra từ hàm thuộc của giá trị mờ đầu ra. Có hai phương pháp giải mờ chính: Phương pháp cực đại và phương pháp trọng điểm. Tính toán theo các phương pháp phức tạp. Giới thiệu chung về luật kết hợp mờ Ngày nay, với bộ nhớ rất lớn của máy tính, một số lượng lớn các dữ liệu giao dịch sẽ được tập hợp và đsược lưu trữ trong máy tính. Ví dụ như các dữ liệu giao dịch hàng hoá, các bản ghi thông tin sinh viên, các bản ghi hồ sơ bệnh nhân v.v… Tuy nhiên, cơ sở dữ liệu giao dịch thuộc loại cơ sở dữ liệu định lượng - quantitative type, và như vậy chúng ta sẽ mất mát rất nhiều thông tin nếu chúng ta chuyển đổi cơ sở dữ liệu định lượng này thành kiểu nhị phân. Trong trường hợp này, một phương pháp mới được đề xuất để giải quyết vấn đề này. Những vấn đề liên quan thì cũng đã được trình bày trong các phần trên. Một trong những hướng giải quyết được đề xuất ở đây là luật liên kết định lượng, luật này sẽ ánh xạ những thuộc tính định lượng thành kiểu mờ. Ngoài ra, còn có một hướng giải quyết do Ramakrishnan Srikant và Rakesh Agrawal đề xuất. Ý tưởng chính của phương pháp này là ánh xạ những thuộc tính định lượng thành kiểu nhị phân. Với mỗi thuộc tính định lượng và phân loại, chúng ta sẽ ánh xạ các giá trị tới một tập các số tự nhiên liên tiếp nhau. Với mỗi giá trị của thuộc tính, độ support và độ tin cậy có thể được tìm thấy khi tạo ra các luật liên kết nhị phân. Giải thuật sẽ liên kết các giá trị số liền kề nhau của thuộc tính cho tới khi độ support là nhỏ hơn độ support do người dùng lựa chọn. Tuy nhiên, Kuok đã chỉ ra vấn đề về ranh giới cứng - sharp boundary problem, đồng ý rằng, vấn đề phân chia cứng của các thuộc tính số không phù hợp với những tri thức trực quan của dữ liệu. Ví dụ, giả sử rằng một thuộc tính là độ tuổi của con người, chúng ta mong muốn lấy ra được các luật liên quan tới lứa tuổi cao niên, trung niên và thanh thiếu niên. Nếu các khoảng tuổi được phân chia cứng, thì chúng ta sẽ có thể gặp phải một tình huống là 59 tuổi được coi là trung niên nhưng 60 tuổi thì lại được coi là cao niên, mặc dù chúng ta có thể hiểu rằng nó không có sự khác biệt lớn đến như vậy. Trong tài liệu của Kuok, thuộc tính tuổi được xác định bởi các tập tuổi mờ của cao niên, trung niên và thanh thiếu niên. Một tập mờ được biểu diễn bởi một hàm thuộc, hàm thuộc này sẽ gắn mỗi giá trị của thuộc tính vào một giá trị nằm trong khoảng (0,1). Ví dụ hàm thuộc của tuổi cao niên được gán giá trị 1.0 cho tuổi 80, 0.8 cho tuổi 50 và 0 cho tuổi 3; trong khi đó hàm thuộc của tuổi trung niên gán giá trị 0 cho tuổi 60, 1 cho tuổi 40, 0.5 cho tuổi 30 và 0 cho tuổi 3. Hình 4 - Hàm thuộc cho các tập mờ Già(Old) và Trẻ(Young) Cũng trong tài liệu của Kuok, luật liên kết mờ có dạng như sau: X A Y B Trong đó: X,Y là các tập mục, A, B là các tập mờ với các thuộc tính tương ứng. Luật trên có thể diễn giải ra rằng nếu X thuộc vào tập mờ A thì Y sẽ thuộc về tập mờ B, với một số lượng bản ghi đủ nhiều để support cho luật này. Một giải thuật mới được đề nghị để tìm ra các luật liên kết mờ có trọng số. Điều này sẽ giúp cải thiện tính ứng dụng thực tế của việc tìm kiếm luật liên kết. Các khái niệm mờ gắn liền với các thuộc tính định lượng và các trọng số được sử dụng để phản ánh tính quan trọng của các khái niệm mờ của mỗi thuộc tính định lượng. Giải thuật này cho phép chúng ta tìm ra các luật tin cậy được với tốc độ tương đối nhanh. Luật kết hợp mờ Mô tả bài toán Thuộc tính và cơ sở dữ liệu: Cho I là tập các thuộc tính I={I1,….In}, trong đó dom(Iv) là miền giá trị của thuộc tính Iv (ví dụ trong cơ sở dữ liệu quản lý về các tính năng kỹ thuật của xe gắn máy, thông số về lượng xăng tiêu thụ trung bình trên 100km là một thuộc tính, với dom=[0,100].Ta có một cơ sở dữ liệu D trên I là tập các bản ghi d. Với mọi bản ghi d thuộc D, ta có d[Iv] xác định giá trị iv thuộc dom(Iv) của thuộc tính Iv của d. Từ Xét I={I1,I2,…,In} là tập các thuộc tính, giả sử mỗi một thuộc tính Iv có thể được mô tả bằng một tập các từ Lv={L,L,…L}. Lấy ví dụ, thông số về lượng xăng tiêu thụ trung bình trên 100km có thể được mô tả bằng tập từ {thấp, trun bình, cao}. Các từ mô tả các thuộc tính khác nhau là khác nhau, mặc dù chúng có thể cùng nhãn, ví dụ như: “Thấp”, “Trung bình”, “Cao”. Xét L là một từ mô tả thuộc tính Iv của cơ sở dữ liệu, khi đó L được biểu diễn bằng một hàm thuộc: dom(Iv)à[0,1] biểu diễn mức độ đúng của việc sử dụng L để mô tả giá trị iv thuộc dom(Iv). Ký hiệu: - Mv là tập tất cả các hàm thuộc biểu diễn các từ mô tả thuộc tính Iv. - LI là tập tất cả các tập từ mô tả các thuộc tính của I, LI được gọi là mô tả của I. - MI là tập tất cả các hàm thuộc biểu diễn các từ trong mô tả LI của I, MI được gọi là biểu diễn của I ứng với LI. Mệnh đề Cho trước 1 cơ sở dữ liệu D trên tập thuộc tính I và các tập từ cũng như các hàm thuộc gắn với các thuộc tính này. Từ cơ sở dữ liệu này, bài toán tìm luật kết hợp mờ tìm cách rút ra các luật dạng : "Nếu X là A thì Y là B". Trước hết chúng ta có khái niệm mệnh đề. Định nghĩa a.3.1: Cho I là tập thuộc tính, X={ I,I,…I} I là tập các thuộc tính, cho A là tập các từ mô tả các thuộc tính trong X, nghĩa là A={ L,L,…L}, A được gọi là mô tả của X, khi đó một mệnh đề trên tập thuộc tính I và tập từ LI (hay gọi tắt mệnh đề)"X là A" ký hiệu hình thức . Chú ý rằng có tương ứng một một giữa A và X, theo nghĩa từ L trong A là một mô tả của thuộc tính I trong X. Chúng ta chỉ quan tâm đến luật kết hợp "có ý nghĩa đối", chúng ta sẽ tìm hiểu về một số tiêu chuẩn đánh giá 1 luật kết hợp mờ. Định nghĩa a.3.2: Cho cơ sở dữ liệu D trên tập các thuộc tính I, là một mệnh đề trên I và tập từ LI, MI là biểu diễn của của I ứng với LI. Xét d thuộc D là một bản ghi. Khi đó độ ủng hộ của d cho ứng với MI được cho bởi công thức sau: vote(d,X,A,MI)= (d[Ix1]).(d[Ix2])…(d[Ixp]) Ý nghĩa của biểu thức trên biểu diễn giá trị đúng đắn của mệnh đề "Ix1 là L và Ix2là L và Ixp là L . Định nghĩa a.3.3: Độ hỗ trợ của trong D ứng với MI: Supp(X,A,D,MI)= vote(d,X,A,MI) Bên cạnh khái niệm hỗ trợ chúng ta có thể sử dụng khái niệm độ quan trọng. Định nghĩa a.3.4: Độ quan trọng của trong D ứng với MI : Sign(X,A,D,MI)= Trong bài toán tìm luật kết hợp mờ, chúng ta chỉ quan tâm tới các mệnh đề có độ quan trọng (độ hỗ trợ) đử lớn, nghĩa là vượt 1 ngưỡng cho trước nào đó. Nói cách khác đó là những vấn đề có supp(X,A,D,MI) abs hay sign(X,A,D,MI) rel với abs và rel là các ngưỡng cho trước nào đó. Nếu một mệnh đề có độ quan trọng đủ lớn ta gọi mệnh đề đó là đáng kể. Định nghĩa a.3.5: tập các mệnh đề đáng kể trên D ứng với ngưỡng và MI được cho bởi: S(D, , MI)={| supp(X,A) } Luật kết hợp Định nghĩa b.1: Cho trước 1 tập thuộc tính I, LI là tập các từu mô tả I, MI là tập các hàm thuộc biểu diễn I ứng với LI, D là một cơ sở dữ liệu trên I. Mục tiêu của chúng ta là tìm các luật dạng "Nếu X là A thì Y là B" có biểu diễn hình thức à , trong đó X,Y I là tập các thuộc tính, XY={} A,B là các tập từ mô tả X,Y tương ứng. Phần được gọi là phần thân (hay tiền tố) của luật, được gọi là phần đầu (hay hệ quả) của luật. Ý nghĩa của luật này nói lên việc nếu "X là A" được thỏa mãn thì "Y là B" cũng được thỏa mãn. Định nghĩa b.2: Cho trước một tập thuộc tính I, tập tù LI mô tả I, MI là tập các hàm thuộc biểu diễn I ứng với LI . D là một cơ sở dữ liệu trên I. trong đó X,Y I là tập các thuộc tính, XY={} A,B là các tập từ mô tả X,Y tương ứng. - Độ hỗ trợ và độ quan trọng của luật à trên D ứng với MI được cho bởi: supp(à,D,MI)=supp(XY,AB, D,MI) sign(à,D,MI)=sign(XY,AB, D,MI) - Độ tin cậy của luật trên D ứng với MI được cho bởi: Conf((à,D,MI)= Conf((à,D,MI)= Luật được gọi là tin chắc nếu độ chắc chắn của nó vượt một ngưỡng độ chắc chắn tối thiểu cho trước nào đó. Vậy một luật được gọi là quan tâm nếu nó đáng kể và tin chắc. Định nghĩa b.3: Tập các luật quan tâm được ký hiệu: R(D,,,MI)={à|X,YI,XY={},S(D,, MI), Conf((à)} Thuật toán khai thác luật kết hợp mờ Thuật toán khai thác luật kết hợp mờ dựa trên thuật toán Apriori, và mục 3.3.5. Thuật toán chia làm 3 pha chính sau: Pha1: Mô hình hóa bài toán: chuyển dữ liệu ban đầu thông qua hàm thuộc của các tập mờ tương ứng với từng thuộc tính. Pha2 : Tìm tất cả các tập thuộc tính mờ phổ biến dạng có độ hỗ trợ lớn hơn độ hỗ trợ cực tiểu của người dùng nhập vào : fs()fminsupp Pha3 : Sinh các luật mờ tin cậy từ các tập phổ biến đã tìm thấy ở pha thứ nhất. Nếu là tập thuộc tính mờ phổ biến thì luật kết hợp mờ được sinh từ X có dạng X’ is A’ X\X’ is A\A’. Trong đó: X’ là tập con khác rỗng của X, X\X’ là hiệu của 2 tập hợp X và X’. fc là độ tin cậy của luật thỏa mãn fc fminconf (do người dùng xác định). A’ là tập con khác rỗng của A và là tập các tập mờ tương ứng với các thuộc tính trong X’. A\A’ là hiệu của 2 tập A và A’. Đầu vào của thuật toán: Cơ sở dữ liệu D với tập các thuộc tính I và các bản ghi T, ngưỡng hàm thuộc Wf , độ hỗ trợ tối thiểu fminsupp , độ tin cậy tối thiểu fminconf và toán tử Tnorm . Đầu ra của thuật toán: Tất cả các luật kết hợp mờ tin cậy. Ký hiệu sử dụng trong thuật toán khai phá luật kết hợp mờ: Ký hiệu Ý nghĩa D Cơ sở dữ liệu ban đầu. I Tập các thuộc tính trong D. T Tập các bản ghi trong D. Df Cơ sở dữ liệu mờ được tính toán từ cơ sở dữ liệu ban đầu thông qua hàm thuộc của các tập mờ tương ứng với từng thuộc tính. If Tập các thuộc tính trong Df, mối thuộc tính đểu được gắn với 1 tập mờ. Mỗi tập mờ f có 1 ngưỡng wf . Tf Tập các bản ghi trong Df , các thuộc tính trong mỗi bản ghi đã được chuyển sang một giá trị trong khoảng [0,1] nhờ hàm thuộc của các tập mờ tương ứng với từng thuộc tính. Fminsupp Độ hỗ trợ tối thiểu Fminconf Độ tin cậy tối thiểu Ck Tập các thuộc tính có kích thước k Fk Tập các thuộc tính phổ biến có kích thước bằng k F Tập tất cả các thuộc tính phổ biến FC Tập tất cả các luật mờ sinh ra từ Fk Bảng 1 – Ký hiệu sử dụng trong thuật toán Thuật toán khai thác luật kết hợp mờ: Begin (Df,Tf,If)=Mờ_Hóa(D,I,T); F1=Tạo_F1(Df,If,Tf,fminsupp); F=Φ,Cf=Φ; K=2; While (Fk-1Φ) {Ck=Tạo_F_k(Fk-1); Fk=Tính_SP_k(Ck,Df,fminsupp); CFk=Tìm_Luật(F,Fk,fminconf); F=FFk; CF=CFCFk; K=k+1;} END Thuật toán sử dụng một số chương trình con sau: Chương trình con Mờ_Hóa(D,I,T): Hàm này thực hiện nhiệm vụ chuyển đổi từ cơ sở dữ liệu gốc D ban đầu sang cơ sở dữ liệu mờ Df . Các thuộc tính của D được gắn thêm các tập mờ và giá trị của các thuộc tính ở bản ghi T trong D được ánh xạ thành một giá trị thuộc khoảng [0,1] thông qua các hàm thuộc. Chương trình con F1=Tạo_F1(Df,If,fminsupp,wf) Hàm này sinh ra F1 là tập tất cả các tập phổ biển có 1 phần tử. Các tập phổ biến này phải có độ hỗ trợ lớn hơn hoặc bằng fminsupp. Thuật toán tạo F1: F1=Tạo_F1(Df,If,fminsupp,wf) F1=Φ; For each I If If (fs({i},wf) fminsupp) then F1=F1{i}; End if Endfor Return F1 Chương trình con Ck=Tạo_F_k(Fk-1): Hàm này thực hiện kết nối các cặp thuộc tính mờ từ tập các thuộc tính mờ phổ biến Fk-1 có k-1 phần tử để sinh ra tập các thuộc tính mờ Ck có k phần tử. Thuật giải tạo Fk từ Fk-1: Insert into Ck Select P.item_1,P.item_2,…,P.itemk-1,Q.itemk-1 From Lk-1P,Lk-1Q Where (P.item_1 = Q.item_1) AND. . . AND (P.item_k-2 = Q.item_k-2) AND (P.item_k-1 < Q.item_k-1) Trong đó: P.item_j,Q.item_j là thuộc tính mờ thứ j trong Lk-1 P.item_o_j,Q.item_o_j là thuộc tính gốc của các thuộc tính mờ thứ j trong Lk-1. Với điều kiện P.itemk-1< Q.itemk-1 nhằm không phát sinh các bộ không trùng nhau. Tuy nhiên thuật giải trên sẽ phát sinh các tập k thuộc tính mờ khác nhau nhưng có cùng thuộc tính gốc và các luật sinh ra từ các tập thuộc tính mờ có cùng thuộc tính gốc là vô nghĩa.Nên cần thay đổi điều kiện của thuật giải như sau: Where (P.item_1 = Q.item_1) AND. . . AND (P.item_k-2 = Q.item_k-2) AND (P.item_k-1 < Q.item_k-1) AND (P.item_o_k-1 Q.item_o_k-1) Điều kiện (P.item_o_k-1 Q.item_o_k-1) sẽ đảm bảo không phát sinh các bộ thuộc tính mờ có cùng thuộc tính gốc. Chương trình con Fk=Tính_SP_k(Ck,Df,fminsupp,wf): Hàm này duyệt qua cơ sở dữ liệu Df, chọn ngưỡng wf và Tnormđể cập nhật độ hỗ trợ cho các thuộc tính trong Ck. Sau khi duyệt xong Tính_SP_k chỉ chọn những tập phổ biến có độ hỗ trợ lớn hơn hoặc bằng fminsupp để đưa vào trong Fk. Thuật giải: Fk=Φ; For(each X Fk-1) do For(each Y Fk-1 and XY) do Begin S=XY; If (|S| ==k and fs(|S|)fminsupp) then Fk=Fk{S}; Endif End Endfor Endfor Chương trình con CFk=Tìm_luật(Fk,fminconf) chương trình con này sinh luật kết hợp mờ tin cậy từ các tập phổ biến Fk . CÀI ĐẶT Bài toán tìm luật Cho trước I là tập thuộc tính, LI là tập các từ mô tả I, MI là tập các hàm thuộc biểu diễn I ứng với LI. D là cơ sở dữ liệu trên I, , tương ứng là các ngưỡng độ hỗ trợ và độ chắc chắn tối thiểu. Hãy tìm R(D, ,,MI)? Bài toán thực tế Ta có cơ sở dữ liệu(D) thông tin giao dịch chứng khoán (tập các thuộc tính I), LI là các từ mô tả các thuộc tính của I (“Tăng nhẹ”,”Tăng khá”,”Tăng mạnh”; “Khối lượng giao dịch thấp”,”Khối lượng giao dịch TB”,”Khối lượng giao dịch lớn”; “Nước ngoài mua ít”, “Nươc ngoài mua TB”, “Nước ngoài mua nhiều”). MI tập hàm thuộc biểu diễn I ứng với LI. Cho trước 2 giá trị là ngưỡng độ hỗ trợ, là ngưỡng độ tin cậy(độ chắc chắn) tối thiểu. Tìm R(D,,,MI) có nghĩa chúng ta đi tìm các luật và các ngưỡng hỗ trợ và ngưỡng tin cậy tương ứng, từ đó dựa vào % ngưỡng hộ trợ và % ngưỡng tin cậy để chúng ta đưa ra nhận định. Ví dụ dữ liệu giao dịch chứng khoán theo ngày: Ngày VNI tăng VNI giảm GTGD(tỉ) NNMUA(triệu CP) Y/Tố tâm lý VNI 12/10/2007 5.3 1323 1800000 1 1 11/10/2007 5.36 1095 2000000 1 0 10/10/2007 7.14 1156 2300000 1 1 09/10/2007 12.49 1314 1400000 1 1 08/10/2007 3.24 1269 1500000 1 1 05/10/2007 6.13 1494 2300000 1 0 04/10/2007 18.84 1683 2100000 1 0 03/10/2007 7.12 1575 1900000 1 1 02/10/2007 15 1750 2800000 1 1 01/10/2007 37.53 1723 1900000 1 1 28/09/2007 32.77 1395 2600000 1 1 27/09/2007 1.82 1084 2100000 1 0 26/09/2007 6.03 1311 1600000 1 1 Bảng 2 – Ví dụ về dữ liệu giao dịch chứng khoán Ta qui đinh khoảng của các LI như sau: VNIndex: VNI tăng >15 điểm à tăng mạnh 5< VNI tăng <15 điểm à tăng trung bình VNI tăng <5 điểm à tăng nhẹ Giá trị giao dịch: Gía trị giao dịch <600 tỉ à Giá trị giao dịch thấp Gía trị giao dịch >1000 tỉ à Giá trị giao dịch cao 600 tỉ <Gía trị giao dịch <1000 tỉ à Giá trị giao dịch trung bình Giao dịch của nước ngoài: Khối lượng nước ngoài mua < 500 nghìn cổ phiếu à Mua ít Khối lượng nước ngoài mua > 1 triệu cổ phiếu à Mua nhiều 500 nghìn<Khối lượng nước ngoài mua < 1 triệu cổ phiếu à Mua trung binh. Yếu tố tâm lý: 1: Yếu tố tâm lý thị trường tốt. 0: Yếu tố tâm lý thị trường không tốt. Sử dụng hàm Mờ_Hóa (3.3.6) để chuyển sang dữ liệu mờ, hàm này được xây dựng dựa trên: L là một từ mô tả thuộc tính Iv của cơ sở dữ liệu D, khi đó L được biểu diễn bằng một hàm thuộc: dom(Iv)à[0,1] biểu diễn mức độ đúng của việc sử dụng L để mô tả giá trị iv thuộc dom(Iv). Kết hợp hàm thuộc theo dạng tam giác theo nên ta có được dữ liệu sau: VNI tăng mạnh VNI tăng TB VNI tăng nhẹ VNI giảm mạnh VNI giamr TB VNI giảm nhẹ GTGD lớn GTGD TB GTGD thấp NN mua nhiều NN mua TB NN mua ít VNI up/down 0 0 0.67 0 0 0 0 0.76 0 0 0.78 0 1 0 0 0 0 0 0.6 0 0.55 0 0.8 0 0 0 0 0 0.6 0 0 0 0 0.6 0 0.85 0 0 1 0 0.57 0 0 0 0 0 0.71 0 0 0.56 0 1 0 0 0.5 0 0 0 0 0.68 0 0 0.59 0 1 … … … Bảng 3 – Dữ liệu giao dịch chứng khoán chuyển sang dạng mờ a, Dùng chương trình con Tạo_F1 (3.3.6) tập tất cả các tập phổ biến có 1 phần tử, các tập thuộc tính phổ biến này có độ hỗ trợ lớn hơn hoặc bằng . b, Chương trình con Tạo_F_k (3.3.6) thực hiện kết nối cặp các thuộc tính mờ từ tập các thuộc tính phổ biến Fk-1 để sinh ra tập các thuộc tính mờ ứng cử viên. c, Chương trình con Tìm_Luật (3.3.6) sinh ra luật kết hợp mờ tin cậy từ các tập phổ biến trong b. KẾT LUẬT Vấn đề tìm kiếm luật kết hợp trong khai phá dữ liệu thực sự rất hữu ích trong các lĩnh vực khai phá tri thức. Trong luận văn này, chúng ta đã giới thiệu phương pháp để tiếp cận với vấn đề luật kết hợp mờ. Bài toán tìm kiếm luật kết hợp mờ được ứng dụng cho nhiều lĩnh vực khác nhau. Cụ thể trong luận văn này em đã cài đặt một thuật toán tìm luật kết hợp mờ cho bài toán dự đoán chỉ số VNIndex. Chương trình đã đưa ra được % độ hỗ trợ và % độ tin cậy. Ngoài ra, chúng ta còn xem xét các giải thuật, kiểm nghiệm thực tế để giải quyết bài toán đặt ra và giới thiệu một số bài toán nâng cao. Tài liệu tham khảo [1] Bùi Công Cường, Nguyễn Doãn Phước - Hệ mờ mạng nơtron và ứng dụng. [2] Nguyễn Thanh Thủy - Khai phá dữ liệu, Kỹ thuật và ứng dụng. [3] Lê Bá Long, Đỗ Văn Thành, Trần Đình Khang - Trường thu hệ mờ và ứng dụng. [4] Bùi Công Cường, Lê Chí Ngọc - Báo cáo tại hội nghị khoa học FAIR 2005. [1] David Hand, Heikki Mannina, Padhraic Smyth - Principles of Data Mining. [2] Hồ Tú Bảo - Knowledge discovery and data mining techniques and practice. ._.