ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN GVHD : PGS. TS. Phan Huy Khánh HVTH : Nguyễn Thị Thùy Phan Thị Lệ Thuyền Nguyễn Văn Thẩm LỚP : Khoa học máy tính KHÓA : 11 (2009 – 2011) Đà Nẵng, tháng 04/2010 LỜI MỞ ĐẦU Trong thời đại ngày nay, với sự phát triển vượt bật của công nghệ thông tin các hệ thống thông tin có thể lưu trữ một khối lượng lớn dữ liệu về hoạt động hàng ngày của chúng. Những năm gần đây, khi nền khoa học công nghệ thông tin đang ngày càng phát triển như vũ bão thì vấn đề khai thác dữ liệu đã trở thành một trong những hướng nghiên cứu chính trong lĩnh vực khoa học máy tính và công nghệ tri thức. Khai thác dữ liệu đã và đang ứng dụng thành công vào rất nhiều các lĩnh vực khác nhau như: thương mại, tài chính, thị trường chứng khoán, y học, thiên văn học, sinh học, giáo dục và viễn thông v.v. Mỗi lĩnh vực hoạt động cần có một chuyên gia để hỗ trợ tư vấn trong quá trình hoạt động. Việc áp dụng hệ chuyên gia là một việc rất quan trọng, chúng ta có thể tạo ra một chuyên gia thật sự trên một lĩnh vực nào đó. Từ đó chúng ta có thể xây dựng nhiều chuyên gia khác nhau trên tất cả các lĩnh vực để phục vụ đời sống xã hội. Chữa bệnh bằng cây thuốc nam là lĩnh vực rất gần gũi và cần thiết trong cuộc sống của mỗi người. Nó hướng dẫn bạn biết tận dụng các loại cây cỏ rất quen thuộc xung quanh, thậm chí ở ngay trong khu vườn của bạn để điều trị một số loại bệnh hay gặp trong cuộc sống hằng ngày. Trong khuôn khổ đề tài này chúng tôi trình bày những hiểu biết về khai phá tri thức và bài tập hệ chuyên gia chẩn đoán và điều trị bệnh bằng thuốc nam. Đề tài gồm các phần chính như sau: Phần 1: Khai phá tri thức Chương 1: Tổng quan về khai phá tri thức Chương 2: Các ứng dụng thực tế áp dụng kỹ thuật khai phá tri thức Phần 2: Hệ chuyên gia Chương 1: Kiến thức cơ bản về hệ chuyên gia Chương 2: Bài toán xây dựng hệ chuyên gia trong lĩnh vực y học Mặc dù đã nghiên cứu kỹ phần lý thuyết để có được cách giải quyết bài tập đúng đắn nhưng chúng tôi không thể tránh khỏi những thiếu sót, kính mong nhận được sự góp ý kiến của Thầy giáo hướng dẫn PGS.TS. Phan Huy Khánh và các anh chị trong lớp để đề tài được tốt hơn. Chúng tôi xin chân thành cảm ơn thầy giáo PGS.TS. Phan Huy Khánh đã tận tình giảng dạy và hướng dẫn để chúng tôi hoàn thành tiểu luận này. Học viên thực hiện Nguyễn Thị Thùy Phan Thị Lệ Thuyền Nguyễn Văn Thẩm MỤC LỤC Phần 1. KHAI PHÁ TRI THỨC 1 Phần 2. HỆ CHUYÊN GIA 15 KẾT LUẬN 25 TÀI LIỆU THAM KHẢO 26 Tiểu luận Công nghệ tri thức GVHD: PGS.TS. Phan Huy Khánh Phần 1. KHAI PHÁ TRI THỨC Chương 1. Tổng quan về khai phá tri thức Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin trong nhiều lĩnh vực của đời sống kinh tế xã hội trong nhiều năm qua cũng đồng nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một tích luỹ nhiều lên. Họ lưu trữ các dữ liệu này vì cho rằng trong nó ẩn chứa những giá trị nhất định nào đó. Tuy nhiên, theo thống kê thì chỉ có một lượng nhỏ của những dữ liệu này (khoảng từ 5% đến 10%) là luôn được phân tích, số còn lại họ không biết sẽ phải làm gì hoặc có thể làm gì với chúng nhưng họ vẫn tiếp tục thu thập rất tốn kém với ý nghĩ lo sợ rằng sẽ có cái gì đó quan trọng đã bị bỏ qua sau này có lúc cần đến nó. Mặt khác, trong môi trường cạnh tranh, người ta ngày càng cần có nhiều thông tin với tốc độ nhanh để trợ giúp việc ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Với những lý do như vậy, các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng được thực tế đã làm phát triển một khuynh hướng kỹ thuật mới đó là Kỹ thuật khai phá tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining). Kỹ thuật khai phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng HVTH: Nguyễn Thị Thùy - Phan Thị Lệ Thuyền Nguy– ễn V n Thă ẩm 1 Có sẵn khối dữ liệu lớn: Có sẵn khối dữ liệu lớn: - Các CSDL khổng lồ - Dữ liệu từ Internet Tiểu luận Công nghệ tri thức GVHD: PGS.TS. Phan Huy Khánh 1.1 Khai phá tri thức là gì? Trong cuộc sống nói chung và trong tin học nói riêng, thông tin và tri thức hiện đang là tiêu điểm của một lĩnh vực mới trong nghiên cứu và ứng dụng về khai phá tri thức (Knowledge Discovery) và khai phá dữ liệu (Data Mining). Thông thường chúng ta coi dữ liệu như một dãy các bit, hoặc các số và các ký hiệu, hoặc các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một chương trình dưới một dạng nhất định. Chúng ta sử dụng các bit để đo lường các thông tin và xem nó như là các dữ liệu đã được lọc bỏ các dư thừa, được rút gọn tới mức tối thiểu để đặc trưng một cách cơ bản cho dữ liệu. Chúng ta có thể xem tri thức như là các thông tin tích hợp, bao gồm các sự kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể được hiểu ra, có thể được phát hiện, hoặc có thể được học. Nói cách khác, tri thức có thể được coi là dữ liệu có độ trừu tượng và tổ chức cao. Khai phá tri thức trong các cơ sở dữ liệu là một qui trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: hợp thức, mới, khả ích, và có thể hiểu được. 1.2 Quá trình phát hiện tri thức Hình 1: Quá trình phát hiện tri thức 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à 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à 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ữ HVTH: Nguyễn Thị Thùy - Phan Thị Lệ Thuyền Nguy– ễn V n Thă ẩm 2 Tiểu luận Công nghệ tri thức GVHD: PGS.TS. Phan Huy Khánh liệu, các lớp mẫu phù hợp và đạt tiêu chuẩn quan tâm so với mục đích. Tri thức mà ta nói ở đây là các 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, v.v… • 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 hồi quy, v.v…) • Đá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. Nếu phát hiện tri thức là toàn bộ quá trình chiết 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. HVTH: Nguyễn Thị Thùy - Phan Thị Lệ Thuyền Nguy– ễn V n Thă ẩm 3 Tiểu luận Công nghệ tri thức GVHD: PGS.TS. Phan Huy Khánh 1.3 Qui trình khai phá tri thức Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. Về lý thuyết thì có vẽ rất đơn giản nhưng thực sự đây là một quá trình rất khó khăn gặp phải rất nhiều vướng mắc như: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình,.v.v. Qui trình khai phá tri thức được mô tả tóm tắt trên Hình 2: Hình 2. Quy trình khai phá tri thức Bước thứ nhất là tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu. Bước thứ hai là thu thập và xử lý thô, còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu, xử lý việc thiếu dữ liệu, biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết, bước này thường chiếm nhiều thời gian nhất trong toàn bộ qui trình khai phá tri thức. Bước thứ ba là khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/và các mô hình ẩn dưới các dữ liệu. Bước thứ tư là hiểu tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực hiện. HVTH: Nguyễn Thị Thùy - Phan Thị Lệ Thuyền Nguy– ễn V n Thă ẩm 4 Tiểu luận Công nghệ tri thức GVHD: PGS.TS. Phan Huy Khánh Hình 3: Tiến trình KDD (Knowledge discovery in databases) tiêu biểu 1.4 Quá trình khai phá tri thức từ dữ liệu Quá trình khai phá tri thức từ dữ liệu bao gồm một số bước từ các bộ dữ liệu đến tri thức mới. • Làm sạch dữ liệu (Data cleaning) và tích hợp dữ liệu (Data integration): giai đoạn này là tạo ra nguồn dữ liệu cho việc khai phá tri thức. Dữ liệu được làm sạch từ các nguồn khác và và tích hợp với nhau. • Lựa chọn dữ liệu (Data selection): dữ liệu không liên quan được phân tích để quyết định giữ lại hay loại bỏ khỏi tập dữ liệu. Giai đoạn này thực hiện việc lựa chọn các trường của mỗi mẫu dữ liệu để thực hiện khai phá tri thức thu được kết quả cao. • Biến đổi dữ liệu (Data transformation): dữ liệu được lựa chọn được biến đổi vào các mẫu thích hợp cho quá trình khai phá. • Khai phá dữ liệu (Data mining): giai đoạn quyết định của quá trình khai phá tri thức từ dữ liệu. Các kỹ thuật được sử dụng trong giai đoạn này nhằm lấy ra các mẫu hữu ích tiềm ẩn. • Đánh giá các mẫu (Pattern evaluation): các mẫu biểu diễn tri thức hấp dẫn được nhận biết dựa trên các độ đo được đưa ra. • Biểu diễn tri thức (Knowledge representation): là giai đoạn cuối của quá trình khai phá tri thức từ dữ liệu, nhằm biểu diễn trực quan tri thức cho người dùng. Bước quan trọng này sử dụng các kỹ thuật trực quan để giúp người sử dụng hiểu và biểu diễn các kết quả khai phá dữ liệu. KDD là một quá trình lặp. Mỗi khi tri thức khai phá được biểu diễn cho người dùng, các độ đo đánh giá có thể được nâng cao, khai phá có thể được cải tiến trong HVTH: Nguyễn Thị Thùy - Phan Thị Lệ Thuyền Nguy– ễn V n Thă ẩm 5 Data Data mining mining Data Data mining mining Input data Input data Input data Input data Results Results Results Results Postprocessi Postprocessi ng ng Operational Operational Database Database Operational Operational Database Database S e l e c t i o n S e l e c t i o n S e l e c t i o n S e l e c t i o n Utilization Utilization Utilization Utilization Eval. of interes- tingness Raw data Time based selection Selecte d usable patter ns 1 3 2 Tiểu luận Công nghệ tri thức GVHD: PGS.TS. Phan Huy Khánh tương lai, dữ liệu mới có thể được chọn hoặc biến đổi trong tương lai, hoặc các nguồn dữ liệu mới có thể được tích hợp nhằm thu được các kết quả khác, thích hợp hơn. Khai phá dữ liệu đã được ứng dụng trong nhiều lĩnh vực khoa học khác nhau nhằm khai thác nguồn dữ liệu phong phú được lưu trữ trong các hệ thống thông tin. Tùy theo bản chất của từng lĩnh vực, việc vận dụng khai phá dữ liệu có những cách tiếp cận khác nhau. Trong lĩnh vực tài chính ngân hàng, khai phá dữ liệu đã được ứng dụng để phân tích rủi ro tín dụng, phát hiện gian lận, tiếp thị, quan hệ khách hàng, dự báo tỷ giá ngoại tệ, quản lý rủi ro tác nghiệp, làm sạch dữ liệu 1.5 Các phương pháp khai phá dữ liệu Với hai đích chính của khai phá dữ liệu là dự đoán (Prediction) và Mô tả (Description), người ta thường sử dụng các phương pháp sau cho khai phá dữ liệu: - Phân loại (Classification) - Hồi qui (Regression) - Phân nhóm (Clustering) - Tổng hợp (Summarization) - Mô hình ràng buộc (Dependency modeling) - Dò tìm biến đổi và độ lệch (Change and Deviation Dectection) - Biểu diễn mô hình (Model Representation) - Kiểm định mô hình (Model Evaluation) - Phương pháp tìm kiếm (Search Method) Một quá trình KPDL bao gồm năm giai đoạn chính sau: (1) Tìm hiểu nghiệp vụ và dữ liệu (2) Chuẩn bị dữ liệu (3) Mô hình hóa dữ liệu (4) Hậu xử lý và đánh giá mô hình (5) Triển khai tri thức Quá trình này có thể được lặp lại nhiều lần một hay nhiều giai đoạn dựa trên phản hồi từ kết quả của các giai đoạn sau. Tham gia chính trong quá trình khai phá dữ liệu là các nhà tư vấn và phát triển chuyên nghiệp trong lĩnh vực khai phá dữ liệu. HVTH: Nguyễn Thị Thùy - Phan Thị Lệ Thuyền Nguy– ễn V n Thă ẩm 6 [...]... sử dụng Tri thức phán đoán M y suy diễn Tri thức thực hành Cơ sở tri thức Hình 16 Quan hệ giữa m y suy diễn và cơ sở tri thức Từ vệc phân biệt hai loại tri thức, người ta nói m y suy diễn là công cụ tri n khai các cơ chế (hay kỹ thuật) tổng quát để tổ hợp các tri thức phán đoán và các tri thức thực hành Hình trên đ y mô tả quan hệ hữu cơ giữa m y suy diễn và cơ sở tri thức 1.4 Biểu diễn tri thức trong. .. trong hệ chuyên gia Có rất nhiều phương pháp biểu diễn tri thức trong m y  Dùng luật sản xuất, hệ chuyên gia dựa trên các luật  Mạng ngữ nghĩa  Ngôn ngữ nhân tạo  Bộ OAV(Object Attributes Values)  Khung (Frame) HVTH: Nguyễn Thị Th y - Phan Thị Lệ Thuyền – Nguyễn Văn Thẩm 17 Tiểu luận Công nghệ tri thức GVHD: PGS.TS Phan Huy Khánh Chương 2 Bài toán x y dựng hệ chuyên gia trong y học 2.1 Phát biểu... pháp khai phá dữ liệu và đạt được kết quả khác nhau, điều đó càng làm sáng tỏ khả năng ứng dụng thực tế to lớn đồng thời với những thách thức đối với kỹ thuật khai phá tri thức và khai phá dữ liệu trong các bài toán kinh tế - xã hội và trong nhiều lĩnh vực khác HVTH: Nguyễn Thị Th y - Phan Thị Lệ Thuyền – Nguyễn Văn Thẩm 14 Tiểu luận Công nghệ tri thức GVHD: PGS.TS Phan Huy Khánh Phần 2 HỆ CHUYÊN GIA. .. Phát biểu bài toán 2.1.1 Phát biểu X y dựng Hệ Chuyên Gia để chẩn đoán và điều trị bệnh bằng thuốc nam (từ các loại trái c y) 2.1.2 Mục đích Nắm được cơ sở lý thuyết liên quan Từ đó, áp dụng để x y dựng chương trình thực hiện các chức năng theo y u cầu bài toán Từ những kiến thức đã học được ta đi áp dụng vào bài toán thực tế Th y rõ được tầm quan trọng của môn hệ chuyên gia, nâng cao kỹ năng về lập... chuyên gia để giải quyết một vấn đề đặc trưng được gọi là lĩnh vực tri thức Lĩnh vực vấn đề (Problem Domain) Lĩnh vực tri thức (Knowledge Domain) Hình 14 Quan hệ giữa lĩnh vực vấn đề và lĩnh vực tri thức HVTH: Nguyễn Thị Th y - Phan Thị Lệ Thuyền – Nguyễn Văn Thẩm 15 Tiểu luận Công nghệ tri thức GVHD: PGS.TS Phan Huy Khánh 1.3 Kiến trúc của hệ chuyên gia Những thành phần cơ bản của một hệ chuyên gia: ... nghệ tri thức GVHD: PGS.TS Phan Huy Khánh Hình 4 Giao diện trực quan của môi trường KPDL Clementine 1.6 Các lĩnh vực liên quan đến Khai phá tri thức Khai phá tri thức và khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực: thống kê, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán học, tính toán song song và tốc độ cao, thu thập tri thức cho các hệ chuyên gia, quan sát dữ liệu Đặc biệt khai phá tri. .. của hệ chuyên gia dựa trên tri thức được minh họa như sau: Người sử dụng (User) Hệ thống giao tiếp (User Interface) Cơ sở tri thức (Knowledge Base) M y suy diễn (Interface Engine) Hình 13 Hoạt động của hệ chuyên gia Mỗi hệ chuyên gia chỉ đặc trưng cho một lĩnh vực vấn đề (problem domain) nào đó, như y học, tài chính, khoa học hay công nghệ ,… mà không phải cho bất cứ một lĩnh vực vấn đề nào Tri thức chuyên. .. hệ chuyên gia 1.1 Khái niệm Theo E Feigenbaum : Hệ chuyên gia (Expert System) là một chương trình m y tính thông minh sử dụng tri thức (knowledge) và các thủ tục suy luận (inference procedues) để giải những bài toán tương đối khó khăn đòi hỏi những chuyên gia mới giải được” 1.2 Hoạt động của một hệ chuyên gia Một hệ chuyên gia bao gồm ba thành phần chính là cơ sở tri thức (knowledge base), m y suy... trình logic, biết cách sử dụng thao tác với ngôn ngữ lập trình prolog Từ đề tài n y chúng ta có thể phát tri n được hệ chuyên gia với những đề tài phức tạp và khó hơn 2.1.3 Nội dung thực hiện - X y dựng tập các sự kiện - X y dựng tập các luật - Chuyển các luật, sự kiện trên thành logic mệnh đề - Chuyển các luật, sự kiện trên thành logic vị từ - X y dựng chương trình Prolog - X y dựng hệ thống đặt câu... phá tri thức và khai phá dữ liệu rất gần gũi với lĩnh vực thống kê, sử dụng các phương pháp thống kê để mô hình dữ liệu và khai phá các mẫu, luật Ngân hàng dữ liệu (Data Warehousing) và các công cụ phân tích trực tuyến (OLAP) cũng liên quan rất chặt chẽ với khai phá tri thức và khai phá dữ liệu 1.7 Các ứng dụng của Khai phá tri thức Mặc dù còn rất nhiều vấn đề mà khai phá dữ liệu quyết nhưng tiềm năng